Snake (Incinerator) - ヘビゲーム
どんな問題？
Snake
http://www.checkio.org/mission/snake/
ヘビゲームをクリアせよ。
フィールドは10x10の大きさで、チェリーが1つある。ヘビを動かしてチェリーを食べると、次のチェリーが現れる。チェリーを5つ食べるとゲームクリア。途中で障害物（木、外壁、自分の体）に当たるとゲームオーバー。
最初、ヘビの長さは5だが、チェリーを1つ食べるごとに長さが1ずつ増えていく。
なお、250ステップ以下でクリアしないとゲームオーバーとなる。
マインスイーパーと同じように、checkio()関数が繰り返し呼ばれるタイプの問題だ。
引数は、list of string で現在のフィールドデータが渡される。文字列は以下の要素から成る。
| . | 空きマス |
| T | 木 |
| C | チェリー |
| 0 | ヘビの頭 |
| 1-9 | ヘビの胴体 |
戻り値はヘビの動作を文字列として返す。動作の途中でチェリーを食べたら、残りの動作は無視される。
| F | 前に移動 |
| L | 左に移動 |
| R | 右に移動 |
問題文にヒントが書いてあった。
- 幅優先探索(BFS)を使うなら注意しよう。状況によってはすごく時間がかかる。
- ヘビは最初にしっぽが動いて、最後に頭が動く。だから頭がしっぽを追いかけてもぶつからない。
- 新しいチェリーは一番外側のマスには現れない。([0,0],[9,9]など）ただし、最初のチェリーは外側のマスにも配置されることがある。
例題：
checkio([
".T.....T..",
".C........",
".....T....",
"..T....T..",
"..........",
".0...T....",
".1........",
".2.T...T..",
".3...T....",
".4........"
])
どうやって解く？
ヒントにBFSうんぬんって書いてあるし、探索の問題なんだろう。別に最短経路である必要はないが、全部で250ステップという制限があるので、短い方が望ましいのはたしか。
やっかいなのがヘビの胴体。胴体は頭の通った後を付いてくるので、1歩進む毎に、迷路が変化するようなものか。
．．．．．．．．．． ．．．．．．．．．． ．．．．．．．．．． ．．．．．．．．．． ．．．．．．．．．． ．．．．．．．．．． ．０．．．．．．．． Ｔ１．．．．．．．． Ｃ２．．．．．．．． ．３．．．．．．．． ．４．．．．．．．．
例えば、こういうケースだと、0（頭）からC（チェリー）の経路が、胴体でふさがれている状態だが、ヘビが動くことによって経路が現れることになる。こんな場合は、経路が現れるまで、とりあえず動いてみる、という感じかな。
なんだかややこしそうだなぁ。また深く考えすぎてるかな？
まずは、単純にヘビの頭からチェリーまでの経路を探す問題として解いてみた。前のOpen Labyrinthとほぼ同じ内容（ヒープキューを使ったA*探索）で、コードも使い回し。スタートからゴールまでを方角(NEWS)の並びで取得する。それを、アクション(FLR)に変換するために route_to_action() 関数を作成してある。
コードはこちら
import heapq DIRS = {'N': (0, -1), 'S': (0, 1), 'W': (-1, 0), 'E': (1, 0)} def checkio(field_map): def get_cell(pt): # 位置からセルの値を取得 return field_map[pt[1]][pt[0]] def get_position_of(cell): # セルの値から位置を取得 return [(x, y) for y in range(10) for x in range(10) if get_cell((x, y)) == cell][0] def is_safe(pt): # 指定位置は安全に進めるか return 0 <= pt[0] < 10 and 0 <= pt[1] < 10 and get_cell(pt) in ['.', 'C'] def get_path(): # visitedフラグを逆にたどってルート(NEWSの並び)を取得 pt = goal route = '' while pt != start: action, prev = visited[pt] route = action + route pt = prev return route def route_to_action(route): # ルート(NEWSの並び)を、アクションに変換 route = first_dir + route result = '' for i in range(len(route) - 1): r = route[i:i + 2] if r in ['NN', 'EE', 'WW', 'SS']: result += 'F' elif r in ['NE', 'ES', 'SW', 'WN']: result += 'R' elif r in ['NW', 'EN', 'SE', 'WS']: result += 'L' return result def get_next_position(pt, direction): # 隣マスの位置を取得 move = DIRS[direction] return pt[0] + move[0], pt[1] + move[1] def get_direction(pt, prev): # 一つ前の位置と現在位置から、向きを取得 move = pt[0] - prev[0], pt[1] - prev[1] return [k for k, v in DIRS.items() if v == move][0] def push(pt): # ヒープキューにpush distance = abs(pt[0] - goal[0]) + abs(pt[1] - goal[1]) heapq.heappush(q, (distance, pt)) def pop(): # ヒープキューからpop return heapq.heappop(q)[1] start = get_position_of('0') # ヘビの頭 neck = get_position_of('1') # ヘビの首 goal = get_position_of('C') # チェリー first_dir = get_direction(start, neck) # 当初のヘビの頭の向き visited = dict() # {(x,y): (direction, prev)} q = [] push(start) while len(q) > 0: pos = pop() if pos == goal: return route_to_action(get_path()) for d in ['N', 'E', 'W', 'S']: new_pos = get_next_position(pos, d) if is_safe(new_pos) and new_pos not in visited: visited[new_pos] = (d, pos) push(new_pos)
ヘビの頭(0)と首(1)の位置関係から、ヘビがどの方角を向いているかを調べている。
ひとまず、これで Run & Check ……
うまくいったか、とおもいきや、最後の最後でFAIL。
心配していたように、初期位置のヘビの体(0～9)が邪魔をしているケースで失敗になったようだ。
障害物判定を改善する
先ほどのコードだと、ヘビがどれだけ動いても0～9は障害物のままだ。実際には、ヘビが移動すれば、ヘビの体があった場所は通過できるようになるわけだから、それを考えて障害物判定を修正することにする。
まず、ヘビの長さを調べる。field_mapに使われている最大の数字＋１がヘビの長さとなる。例えば、'012345'であれば、ヘビの長さは 6 だ。最初は'012345'のすべてが障害物だが、1ステップ後には、新しく進んだセルと'01234'は障害物だが、'5'は通過可能になる。このように、ステップによって障害物が変化するようにした。
ヘビの長さを調べるコードはこちら。
def get_body_length(): return max([int(cell) for lst in field_map for cell in lst if cell in '123456789']) body_length = get_body_length()
次に、現在のステップ数をわかるようにしておく。これは、ヒープキューに、位置だけでなく、ステップ数も保存するようにする。
def push(pt, step): distance = abs(pt[0] - goal[0]) + abs(pt[1] - goal[1]) heapq.heappush(q, (distance, pt, step))
ヘビの長さとステップ数を使って、障害物判定を行う。
def is_safe(pt): snake_body = '0123456789'[:max(0, body_length - step)] return 0 <= pt[0] < 10 and 0 <= pt[1] < 10 and get_cell(pt) not in 'T' + snake_body
まとめてみた
def checkio(field_map): def get_cell(pt): return field_map[pt[1]][pt[0]] def get_position_of(cell): return [(x, y) for y in range(10) for x in range(10) if get_cell((x, y)) == cell][0] def get_body_length(): return max([int(cell) for lst in field_map for cell in lst if cell in '123456789']) + 1 def is_safe(pt): snake_body = '0123456789'[:max(0, body_length - step)] return 0 <= pt[0] < 10 and 0 <= pt[1] < 10 and get_cell(pt) not in 'T' + snake_body def get_path(): """ Get route string ex. 'NNEWSS' """ pt = goal result = '' while pt != start: direction, prev = visited[pt] result = direction + result pt = prev return result def route_to_actions(route): """ Convert route string to action string ex: 'NNEES' -> 'FRFR' """ route = first_dir + route result = '' for i in range(len(route) - 1): r = route[i:i + 2] if r in ['NN', 'EE', 'WW', 'SS']: result += 'F' elif r in ['NE', 'ES', 'SW', 'WN']: result += 'R' elif r in ['NW', 'EN', 'SE', 'WS']: result += 'L' return result def get_next_position(pt, direction): move = DIRS[direction] return pt[0] + move[0], pt[1] + move[1] def get_direction(pt, prev): move = pt[0] - prev[0], pt[1] - prev[1] return [k for k, v in DIRS.items() if v == move][0] def push(pt, step): distance = abs(pt[0] - goal[0]) + abs(pt[1] - goal[1]) heapq.heappush(q, (distance, pt, step)) def pop(): return heapq.heappop(q)[1:] start = get_position_of('0') neck = get_position_of('1') goal = get_position_of('C') body_length = get_body_length() first_dir = get_direction(start, neck) visited = dict() # key=(x,y), value=(direction, prev_pos) q = [] push(start, 0) while len(q) > 0: pos, step = pop() if pos == goal: return route_to_actions(get_path()) for d in ['N', 'E', 'W', 'S']: new_pos = get_next_position(pos, d) if is_safe(new_pos) and new_pos not in visited: visited[new_pos] = (d, pos) push(new_pos, step + 1)
これでクリア。
でも、現在位置の4方向(NEWS)を探索しているけど、動けるのは(FRL)の3方向だけだから、ちょっと無駄だよなぁ。NEWSの並びをアクションに変換する部分も無くせそうだ。全体的に直してみる。
リニューアル版
def checkio(field_map): def get_cell(pt): return field_map[pt[1]][pt[0]] def get_position_of(cell): return [(x, y) for y in range(10) for x in range(10) if get_cell((x, y)) == cell][0] def get_body_length(): return max([int(cell) for lst in field_map for cell in lst if cell in '123456789']) + 1 def is_safe(pt): snake_body = '0123456789'[:max(0, body_length - step)] return 0 <= pt[0] < 10 and 0 <= pt[1] < 10 and get_cell(pt) not in 'T' + snake_body def get_path(): pt = goal result = '' while pt != start: action, prev = visited[pt] result = action + result pt = prev return result def get_next_position(pt, direction, action): if action == 'F': new_direction = direction elif action == 'R': new_direction = {'N': 'E', 'E': 'S', 'S': 'W', 'W': 'N'}[direction] else: # action == 'L': new_direction = {'N': 'W', 'W': 'S', 'S': 'E', 'E': 'N'}[direction] move = DIRS[new_direction] new_position = pt[0] + move[0], pt[1] + move[1] return new_position, new_direction def get_direction(pt, prev): move = pt[0] - prev[0], pt[1] - prev[1] return [k for k, v in DIRS.items() if v == move][0] def push(pt, direction, step): distance = abs(pt[0] - goal[0]) + abs(pt[1] - goal[1]) heapq.heappush(q, (distance, pt, direction, step)) def pop(): return heapq.heappop(q)[1:] # pt, direction, step start = get_position_of('0') neck = get_position_of('1') goal = get_position_of('C') body_length = get_body_length() visited = dict() # key=(x,y), value=(action, prev_pos) q = [] push(start, get_direction(start, neck), 0) while len(q) > 0: pos, dir, step = pop() if pos == goal: return get_path() for act in ['F', 'R', 'L']: new_pos, new_dir = get_next_position(pos, dir, act) if is_safe(new_pos) and new_pos not in visited: visited[new_pos] = (act, pos) push(new_pos, new_dir, step + 1)
route_to_actions() がなくなったので、少しすっきりしたかな。
