[GDD2010][DevQuiz] PAC-MAN（入力2まで）のソースコード

Google Developer Day 2010のDevQuizで出題された「PAC-MAN」の入力2までを解いた際に使用したソースコードです。言語にはPythonを使用しました。標準出力からマップデータを入れると、標準出力に経路を出力するスクリプトです。

本スクリプトでは、A*アルゴリズムを使ってパックマンの動きを探索しました。しかしただ単に探索したのでは探索範囲が爆発的に膨れあがってしまうため、敵と衝突するような動きは避けるようにしました。また、次の交差点まで移動するような経路も隣接する経路にくわえ、次の交差点まで移動する経路はスコアが半分になるようにしました。本スクリプトでは、スコアが少ないほど良いスコアであるため、次の交差点まで一気に移動する経路が優先的に選ばれます。こうすることで、探索の高速化を図りました。

スコアは、「(残りのドット数)×1000 + (消費した時間)」とし、挟み撃ちに合うなどして敵と衝突すると、「(残りのドット数)×1000」の部分を残り時間と乗算しました。

本スクリプトに至るまでには、紆余曲折がかなりありました。まずはじめは、反復深化深さ優先探索を実装してみたのですが、答えがなかなか返ってこなかったため断念しました。次にA*アルゴリズムを実装したのですが、スコアにさまざまなヒューリスティクスを加えてみたものの、入力1のみしか解けず入力2は答えが返ってこない状況となりました。加えるヒューリスティクスのネタも尽きたところで、一発奮起して遺伝的アルゴリズムを実装してみました。ところが、あともう少しでドットを食べきれるところで探索が終了してしまいました。

しかし、A*アルゴリズム版から遺伝的アルゴリズム版へ至る間に、探索の効率化やスコア計算の簡略化を行っていました。遺伝的アルゴリズムを実装する前までは敵と衝突するような経路も探索候補に入れていました。ところが遺伝的アルゴリズムでは効率的な遺伝子の設計が求められます。そこで、敵と衝突するような経路は探索範囲から外すようにしました。スコア計算についても、処理に時間のかかるヒューリスティクスはやめて、単純な計算で済むような方法としました。

このような改良を、なかばやけくそでA*アルゴリズム版にも施してみました。すると、入力2も解けてしまったのです。同じようにして入力3も解けないものかとスクリプトを実行してみたのですが、残念ながらDevQuizの締め切りまでに回答は出ませんでした。

探索に関して新しいアイディアを出すには、別の方法で実装してみるというのも十分に有効だと感じました。

#!/usr/bin/env python
# coding: UTF-8

import bisect
import math
import sys

# 左上隅の座標
START_X = 1
START_Y = 1

MAX_SCORE = sys.maxint
MIN_SCORE = -sys.maxint - 1

class Wall:
    u"""
    壁を表す。
    """
    def __str__(self):
        return u'#'

class Dot:
    u"""
    ドットを表す。
    """
    def __str__(self):
        return u'.'

# 壁のインスタンス。マップ内で同一のインスタンスを使い回す。
WALL = Wall()
# ドットのインスタンス。マップ内で同一のインスタンスを使い回す。
DOT = Dot()

# マップの評価結果
# 何も起こらなかった。
NOTHING = 0
# 敵と衝突した。
CRASH = 1
# ドットをとった。
ATE_DOT = 2
# 時間内にすべてのドットをとった。
CLEAR = 3
# 時間切れになった。
TIME_OVER = 4

class Character:
    u"""
    敵やパックマンを表すベースクラス。
    """
    def __init__(self, x, y):
        self.position = (x, y)
        self.history = []

    def set_position(self, x, y):
        u"""
        現在の位置を設定する。
        """
        self.history.append(self.position)
        self.position = (x, y)

    def undo(self):
        u"""
        1つ前の状態に戻す。
        """
        self.position = self.history.pop()

class Packman(Character):
    u"""
    パックマンを表す。
    """
    def __init__(self, x, y):
        Character.__init__(self, x, y)

    def __str__(self):
        return u'@'

class Enemy(Character):
    u"""
    敵を表すベースクラス。
    """
    def __init__(self, x, y):
        Character.__init__(self, x, y)
        self.id = u'%s,%s' % (x, y)

    def get_first_next(self, neighborhoods):
        u"""
        時刻t = 0での移動先を返す。
        """
        x, y = self.position
        if (x, y + 1) in neighborhoods:
            return (x, y + 1)
        elif (x - 1, y) in neighborhoods:
            return (x - 1, y)
        elif (x, y - 1) in neighborhoods:
            return (x, y - 1)
        elif (x + 1, y) in neighborhoods:
            return (x + 1, y)

    def get_next(self, neighborhoods):
        u"""
        次の移動先を返す。
        """
        if len(self.history) == 0:
            return self.get_first_next(neighborhoods)
        else:
            if len(neighborhoods) == 1:
                return neighborhoods[0]
            elif len(neighborhoods) == 2:
                for a_neighborhood in neighborhoods:
                    if self.history[-1] != a_neighborhood:
                        return a_neighborhood
            else:
                return self.get_next_on_crossing(neighborhoods)

    def get_differ_to_packman(self):
        u"""
        敵から見たパックマンとの距離を返す。
        """
        return (self.packman.position[0] - self.position[0],
                self.packman.position[1] - self.position[1])

    def get_state(self):
        u"""
        現在の状態を文字列として表現する。
        """
        state = u''
        if 0 < len(self.history):
            state += u'(%s, %s)->' % (self.history[-1][0], self.history[-1][0])
        state +=  u'(%s, %s) ' % (self.position[0], self.position[1])
        return state

class EnemyV(Enemy):
    u"""
    敵Vを表す。
    """
    def __init__(self, x, y):
        Enemy.__init__(self, x, y)
        self.packman = None

    def get_next_on_crossing(self, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        dx, dy = self.get_differ_to_packman()
        if dy != 0:
            candidate = (self.position[0], self.position[1] + (dy / abs(dy)))
            if candidate in neighborhoods:
                return candidate
        if dx != 0:
            candidate = (self.position[0] + (dx / abs(dx)), self.position[1])
            if candidate in neighborhoods:
                return candidate
        return self.get_first_next(neighborhoods)

    def __str__(self):
        return u'V'

class EnemyH(Enemy):
    u"""
    敵Hを表す。
    """
    def __init__(self, x, y):
        Enemy.__init__(self, x, y)
        self.packman = None

    def get_next_on_crossing(self, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        dx, dy = self.get_differ_to_packman()
        if dx != 0:
            candidate = (self.position[0] + (dx / abs(dx)), self.position[1])
            if candidate in neighborhoods:
                return candidate
        if dy != 0:
            candidate = (self.position[0], self.position[1] + (dy / abs(dy)))
            if candidate in neighborhoods:
                return candidate
        return self.get_first_next(neighborhoods)

    def __str__(self):
        return u'H'

class EnemyLRActionBase:
    u"""
    敵L,Rの動作を共通化したベースクラス。
    """
    def __init__(self, history, search):
        self.history = history
        self.search = search

    def get_next_on_crossing(self, position, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        previous_position = self.history[-1]
        previous_diff = (previous_position[0] - position[0],
                previous_position[1] - position[1])
        start = self.search.index(previous_diff) + 1
        for index in range(start, start + len(self.search)):
            next_diff = self.search[index % len(self.search)]
            candidate = (position[0] + next_diff[0], position[1] + next_diff[1])
            if candidate in neighborhoods:
                return candidate

class EnemyLAction(EnemyLRActionBase):
    u"""
    敵Lの動作を表す。
    """
    SEARCH = [(0, -1), (1, 0), (0, 1), (-1, 0)]

    def __init__(self, history):
        EnemyLRActionBase.__init__(self, history, EnemyLAction.SEARCH)

class EnemyL(Enemy):
    u"""
    敵Lを表す。
    """
    def __init__(self, x, y):
        Enemy.__init__(self, x, y)
        self.action = EnemyLAction(self.history)

    def get_next_on_crossing(self, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        return self.action.get_next_on_crossing(self.position, neighborhoods)

    def __str__(self):
        return u'L'

class EnemyRAction(EnemyLRActionBase):
    u"""
    敵Rの動作を表す。
    """
    SEARCH = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def __init__(self, history):
        EnemyLRActionBase.__init__(self, history, EnemyRAction.SEARCH)

class EnemyR(Enemy):
    u"""
    敵Rを表す。
    """
    def __init__(self, x, y):
        Enemy.__init__(self, x, y)
        self.action = EnemyRAction(self.history)

    def get_next_on_crossing(self, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        return self.action.get_next_on_crossing(self.position, neighborhoods)

    def __str__(self):
        return u'R'

class EnemyJ(Enemy):
    u"""
    敵Jを表す。
    """
    def __init__(self, x, y, field):
        Enemy.__init__(self, x, y)
        self.action_r = EnemyRAction(self.history)
        self.action_l = EnemyLAction(self.history)
        self.current_action = self.action_l
        self.action_history = []
        self.field = field

    def set_position(self, x, y):
        Enemy.set_position(self, x, y)
        self.action_history.append(self.current_action)
        previous_position = self.history[-1]
        if 3 <= self.field.get_neighborhoods_count(
                previous_position[0], previous_position[1]):
            self.change_action()

    def change_action(self):
        if self.current_action == self.action_r:
            self.current_action = self.action_l
        else:
            self.current_action = self.action_r

    def get_next(self, neighborhoods):
        self.on_crossing = False
        return Enemy.get_next(self, neighborhoods)

    def get_next_on_crossing(self, neighborhoods):
        u"""
        交差点での次の移動先を返す。
        """
        return self.current_action.get_next_on_crossing(self.position, neighborhoods)

    def undo(self):
        Enemy.undo(self)
        self.current_action = self.action_history.pop()

    def get_state(self):
        return Enemy.get_state(self) + str(self.current_action)

    def __str__(self):
        return u'J'

class Field:
    u"""
    現在のマップの状態を表す。
    """
    def __init__(self, field_file = None):
        if field_file:
            self.make_field(field_file)
        else:
            pass

    def get_neighborhoods_count(self, x, y):
        u"""
        進入可能な通路の数を返す。
        """
        neighborhood_count = 0
        if WALL not in self.field[y - 1][x]:
            neighborhood_count += 1
        if WALL not in self.field[y + 1][x]:
            neighborhood_count += 1
        if WALL not in self.field[y][x + 1]:
            neighborhood_count += 1
        if WALL not in self.field[y][x - 1]:
            neighborhood_count += 1
        return neighborhood_count

    def get_fast_way_one(self, candidate, neighborhood):
        u"""
        隣接する交差点までの1経路を返す。
        """
        forward_x = neighborhood[0] - candidate[0]
        forward_y = neighborhood[1] - candidate[1]
        previous_x = candidate[0]
        previous_y = candidate[1]
        current_x = candidate[0] + forward_x
        current_y = candidate[1] + forward_y
        fast_way = [(previous_x, previous_y), (current_x, current_y)]
        while True:
            neighborhoods = self.get_neighborhoods_on_position(current_x, current_y)
            if 3 <= len(neighborhoods):
                return fast_way
            elif (current_x + forward_x, current_y + forward_y) not in neighborhoods:
                list = [a_neighborhood for a_neighborhood in neighborhoods
                        if a_neighborhood != (previous_x, previous_y)]
                if len(list) == 0:
                    return None
                next = list[0]
                if len(next) == 0:
                    return fast_way
                forward_x = next[0] - current_x
                forward_y = next[1] - current_y
            previous_x = current_x
            previous_y = current_y
            current_x = current_x + forward_x
            current_y = current_y + forward_y
            fast_way.append((current_x, current_y))

    def get_fast_ways(self, candidate):
        u"""
        隣接する交差点までの全経路を返す。
        """
        neighborhoods = [a_neighborhood for a_neighborhood
                in self.get_neighborhoods_on_position(candidate[0], candidate[1])
                if a_neighborhood != self.packman.position]
        fast_ways = []
        for a_neighborhood in neighborhoods:
            fast_way = (self.get_fast_way_one(candidate, a_neighborhood))
            if fast_way:
                fast_ways.append(fast_way)
        return fast_ways

    def get_neighborhoods_on_position(self, x, y):
        u"""
        隣接する通路の座標を返す。
        """
        neighborhoods = []
        if WALL not in self.field[y - 1][x]:
            neighborhoods.append((x, y - 1))
        if WALL not in self.field[y + 1][x]:
            neighborhoods.append((x, y + 1))
        if WALL not in self.field[y][x + 1]:
            neighborhoods.append((x + 1, y))
        if WALL not in self.field[y][x - 1]:
            neighborhoods.append((x - 1, y))
        return neighborhoods

    def get_neighborhoods(self, character):
        u"""
        指定のキャラクターから見た、隣接する通路の座標を返す。
        """
        return self.get_neighborhoods_on_position(
            character.position[0], character.position[1])

    def get_next_candidates(self):
        u"""
        次に移動可能な座標を返す。
        """
        candidates = self.get_neighborhoods(self.packman)
        candidates.append(self.packman.position)
        for an_enemy in self.enemies:
            enemy_next = an_enemy.get_next(self.get_neighborhoods(an_enemy))
            for a_candidate in candidates[:]:
                if an_enemy.position == a_candidate or enemy_next == a_candidate:
                    candidates.remove(a_candidate)
        return candidates

    def move_character(self, character, x, y):
        u"""
        キャラクターを指定の座標に動かす。
        """
        self.field[character.position[1]][character.position[0]].remove(character)
        self.field[y][x].add(character)
        character.set_position(x, y)

    def undo_character(self, character):
        u"""
        指定のキャラクターを1つ前の時刻の状態に戻す。
        """
        self.field[character.position[1]][character.position[0]].remove(character)
        character.undo()
        self.field[character.position[1]][character.position[0]].add(character)

    def is_crashed(self):
        u"""
        パックマンが敵と衝突したか否かを返す。
        """
        if 0 < len(self.field[self.packman.position[1]][self.packman.position[0]] &
                self.enemies_on_field):
            return True
        if 2 <= len(self.packman.history):
            packman_previous_position = self.packman.history[-1]
            candidate_enemies = \
                    self.field[packman_previous_position[1]][packman_previous_position[0]] & \
                        self.enemies_on_field
            for a_candidate_enemy in candidate_enemies:
                if a_candidate_enemy.history[-1] == self.packman.position:
                    return True
        return False

    def evalute(self):
        u"""
        現在のフィールドの状態について評価を行う。
        """
        if self.time < 0:
            self.dot_ate_history.append(None)
            return TIME_OVER
        if self.is_crashed():
            self.dot_ate_history.append(None)
            return CRASH
        if DOT in self.field[self.packman.position[1]][self.packman.position[0]]:
            self.field[self.packman.position[1]][self.packman.position[0]].remove(DOT)
            self.dot_count -= 1
            self.dot_ate_history.append(self.packman.position)
            if self.dot_count == 0:
                return CLEAR
            else:
                return ATE_DOT
        else:
            self.dot_ate_history.append(None)
            return NOTHING

    def next(self, x, y):
        u"""
        指定の座標にパックマンを移動させる。
        """
        for an_enemy in self.enemies:
            next_x, next_y = an_enemy.get_next(self.get_neighborhoods(an_enemy))
            self.move_character(an_enemy, next_x, next_y)
        self.move_character(self.packman, x, y)
        self.time -= 1
        return self.evalute()

    def undo(self):
        u"""
        1つ前の時刻の状態にフィールドを戻す。
        """
        for an_enemy in self.enemies:
            self.undo_character(an_enemy)
        self.undo_character(self.packman)
        previous_dot = self.dot_ate_history.pop()
        if previous_dot:
            self.field[previous_dot[1]][previous_dot[0]].add(DOT)
            self.dot_count += 1
        self.time += 1

    def undo_all(self):
        u"""
        初期状態に戻す。
        """
        for i in range(0, len(self.packman.history)):
            self.undo()

    def set_packman_to_enemies(self):
        u"""
        各EnemyオブジェクトにPackmanオブジェクトを設定する。
        """
        for an_enemy in self.enemies:
            an_enemy.packman = self.packman

    def make_field(self, file):
        u"""
        フィールドを作成する。
        """
        lines = file.readlines()
        # 1行目: 時間
        self.time = int(lines[0])
        # 2行目: <幅> <高さ>
        self.width, self.height = [int(a_number) + 1 for a_number in lines[1].split()]
        # マスク処理での境界値処理を省略するために、一回り大きなフィールドを作成する。
        self.field = []
        for row_index in range(0, self.height + 1):
            current_row = []
            self.field.append(current_row)
            for column_index in range(0, self.width + 1):
                current_row.append(set())
        # フィールドの作成
        self.dot_count = 0
        self.enemies = []
        field_source = lines[2:]
        y = START_Y
        for a_row in field_source:
            x = START_X
            for a_column in a_row:
                self.field[y][x].clear()
                element = self.get_element(a_column, x, y)
                if element:
                    self.field[y][x].add(element)
                    if isinstance(element, Dot):
                        self.dot_count += 1
                    elif isinstance(element, Packman):
                        self.packman = element
                    elif isinstance(element, Enemy):
                        self.enemies.append(element)
                x += 1
            y += 1
        self.set_packman_to_enemies()
        self.packman_on_field = frozenset([self.packman])
        self.enemies_on_field = frozenset(self.enemies)
        self.dot_on_field = frozenset([DOT])
        self.dot_ate_history = []
        self.initial_time = self.time
        self.initial_dot_count = self.dot_count

    def get_element(self, element_character, x, y):
        u"""
        テキスト表現のマップの指定の要素からオブジェクトを生成する。
        """
        if element_character == u'#':
            return WALL
        elif element_character == u' ':
            return None
        elif element_character == u'.':
            return DOT
        elif element_character == u'@':
            return Packman(x, y)
        elif element_character == u'V':
            return EnemyV(x, y)
        elif element_character == u'H':
            return EnemyH(x, y)
        elif element_character == u'L':
            return EnemyL(x, y)
        elif element_character == u'R':
            return EnemyR(x, y)
        elif element_character == u'J':
            return EnemyJ(x, y, self)

    def __str__(self):
        map = u''
        for y in range(START_Y, self.height):
            for x in range(START_X, self.width):
                elements = self.field[y][x]
                if WALL in elements:
                    map += str(WALL)
                elif self.packman in elements:
                    if 0 < len(elements - self.packman_on_field):
                        map += u'x'
                    else:
                        map += str(self.packman)
                elif 0 < len(elements & self.enemies_on_field):
                    enemies = list(elements & self.enemies_on_field)
                    map += str(enemies[0])
                elif DOT in elements:
                    map += str(DOT)
                else:
                    map += u' '
            map += u'\n'
        return map

class Node:
    u"""
    フィールド上のある場面を表す。
    """
    def __init__(self, current_field, result):
        if 2 <= len(current_field.packman.history):
            self.route = current_field.packman.history[1:]
            self.route.append(current_field.packman.position)
        elif 1 == len(current_field.packman.history):
            self.route = [current_field.packman.position]
        else:
            self.route = []
        self.is_fast = False
        self.position = current_field.packman.position
        self.score = self.calculate_score(current_field, result)
        self.original_score = self.score
        self.enemy_state = u''
        for an_enemy in current_field.enemies:
            self.enemy_state += an_enemy.get_state()
        self.string = u'%s,%s,%s' % (
                str(len(self.route)), str(self.position), self.enemy_state)

    def __str__(self):
        return self.string

    def calculate_score(self, current_field, result):
        u"""
        スコアを計算する。
        """
        if result == TIME_OVER:
            return MAX_SCORE
        if current_field.time <= current_field.dot_count:
            return MAX_SCORE
        dot_score = (current_field.dot_count * 1000)
        if result == CRASH:
            dot_score *= current_field.time
        score = len(self.route) + dot_score
        return score 

    def set_fast(self):
        u"""
        高速移動（次の交差点まで移動）するノードか否かを設定する。
        """
        self.is_fast = True
        self.score /= 2

    def setup_field(self, field):
        u"""
        Fieldオブジェクトを、本ノードが表す状態にする。
        """
        if self.route == field.packman.history[1:]:
            return
        field.undo_all()
        for a_next in self.route:
            field.next(a_next[0], a_next[1])

    def __cmp__(x, y):
        return x.score - y.score

class ClosedNode():
    u"""
    調査が終わったノードを表す。
    bisectモジュールは、__cmp__関数を用いるため、
    クローズリストでbisectモジュールを使用するには本クラスが必要。
    """
    def __init__(self, node):
        self.node = node
        self.score = node.score
        self.original_score = node.original_score

    def __cmp__(x, y):
        return cmp(str(x.node), str(y.node))

def find_node_index(node, list):
    u"""
    指定のリストからノードを探し、そのインデックスを返す。
    """
    i = bisect.bisect_left(list, node)
    if i < len(list) and list[i] == node:
        return i
    else:
        return -1

def insert_node(node, list):
    u"""
    指定のリストにノードを挿入する。
    """
    bisect.insort(list, node)

def pop_node(node, list):
    u"""
    指定のリストから指定のノードを取り出す。
    """
    index = find_node_index(node, list)
    if 0 <= index:
        list.pop(index)
    else:
        return None

def find_index_from_close_list(node, close_list):
    u"""
    クローズリストからノードを探し、そのインデックスを返す。
    """
    return find_node_index(ClosedNode(node), close_list)

def find_index_from_open_list(node, open_list):
    u"""
    オープンリストからノードを探し、そのインデックスを返す。
    """
    for index in range(0,len(open_list)):
        if str(node) == str(open_list[index]):
            return index
    else:
        return -1

def decode_start_to_next(start, next):
    u"""
    1回分の移動を表現する文字を返す。
    """
    diff_x = next[0] - start[0]
    diff_y = next[1] - start[1]
    if diff_x == -1:
        return u'h'
    elif diff_y == 1:
        return u'j'
    elif diff_y == -1:
        return u'k'
    elif diff_x == 1:
        return u'l'
    elif diff_x == 0 and diff_y == 0:
        return u'.'
    else:
        return u'?'

def decode_route(start, route):
    u"""
    指定の経路を表現する文字列を返す。
    """
    result = u''
    for next in route:
        result += decode_start_to_next(start, next)
        start = next
    return result

def a_search(field):
    u"""
    経路を探索する。
    """
    first_node = Node(field, NOTHING)
    start_position = field.packman.position
    open_list = [first_node]
    open_list_strs = [str(first_node)]
    close_list = []
    min_dot_count = field.initial_dot_count
    while 0 < len(open_list):
        current_node = open_list.pop(0)
        insert_node(ClosedNode(current_node), close_list)
        current_node.setup_field(field)
        if field.dot_count < min_dot_count:
            min_dot_count = field.dot_count
            print field
            print u'%s/%s' % ((field.initial_dot_count - field.dot_count),
                    field.initial_dot_count)
            print decode_route(
                    start_position, field.packman.history[1:] + [field.packman.position])
        if field.dot_count == 0:
            return current_node.route
        candidates_1x = field.get_next_candidates()
        candidates_nx = []
        for a_candidate_1x in candidates_1x:
            candidates_nx.extend(field.get_fast_ways(a_candidate_1x))
        for a_candidate_nx in candidates_nx:
            next_count = 0
            result = NOTHING
            created_nodes = []
            for a_next in a_candidate_nx:
                result = field.next(a_next[0], a_next[1])
                next_count += 1
                if result == CRASH or result == TIME_OVER:
                    break
                else:
                    node = Node(field, result)
                    if node.score != MAX_SCORE:
                        created_nodes.append(node)
                    if result == CLEAR:
                        break
            if 0 < len(created_nodes):
                created_nodes[-1].set_fast()
                for a_node in created_nodes:
                    if pop_node(str(a_node), open_list_strs):
                        open_list_index = find_index_from_open_list(a_node, open_list)
                        if 0 <= open_list_index:
                            if a_node.original_score < \
                                    open_list[open_list_index].original_score:
                                insert_node(ClosedNode(open_list[open_list_index]),
                                        close_list)
                                del open_list[open_list_index]
                                insert_node(a_node, open_list)
                                insert_node(str(a_node), open_list_strs)
                            continue
                    close_list_index = find_index_from_close_list(a_node, close_list)
                    if 0 <= close_list_index:
                        if a_node.original_score < \
                                close_list[close_list_index].original_score:
                            del close_list[close_list_index]
                            insert_node(a_node, open_list)
                            insert_node(str(a_node), open_list_strs)
                        continue
                    insert_node(a_node, open_list)
                    insert_node(str(a_node), open_list_strs)
            for i in range(0, next_count):
                field.undo()
    else:
        print u'失敗'

def print_result(route, field):
    u"""
    結果を標準出力に出力する。
    """
    decoded_route = decode_route(field.packman.position, route)
    print decoded_route
    print u'-- initial --'
    print str(field)
    index = 0
    for a_next in route:
        field.next(a_next[0], a_next[1])
        print u'-- %s --' % (decoded_route[index])
        print str(field)
        index += 1
    print u'%s steps.' % (len(decoded_route))
    print decoded_route

def main():
    initial_field = Field(sys.stdin)
    route = a_search(initial_field)
    initial_field.undo_all()
    print_result(route, initial_field)

if __name__ == '__main__':
    main()