Homeの6問目(Open Labyrinth)
迷路のルートを見つける問題ですね。
最短でなくても、コースアウトさえしなければよいというかんじでしょうか。
進める方向は上下左右("S","N","W","E")のみ。
とりあえず現在地の上下左右が移動可能か判断して2方向以上移動可能だった場合、
元いた場所以外の方向に走査を進める、3方向以上であった場合、そこまでのbranchを作って元いた場所以外のどちらかに進む、1方向しかない場合直近のbranchまで戻る、branchがない場合は起点まで戻る。
って感じで考えてみたのですが、かなり複雑な感じでどはまりしました。
def checkio(maze_map):
current = [1, 1]
moves = [[1, 0], [-1, 0], [0, -1], [0, 1]]
dist = ["S", "N", "E", "W"]
dist_negative = ["N", "S", "W", "E"]
movedlog = ""
for i in range(15):
S = [current[0]+moves[0][0], current[1]+moves[0][1], maze_map[current[0]+moves[0][0]][current[1]+moves[0][1]]]
N = [current[0]+moves[1][0], current[1]+moves[1][1], maze_map[current[0]+moves[1][0]][current[1]+moves[1][1]]]
E = [current[0]+moves[2][0], current[1]+moves[2][1], maze_map[current[0]+moves[2][0]][current[1]+moves[2][1]]]
W = [current[0]+moves[3][0], current[1]+moves[3][1], maze_map[current[0]+moves[3][0]][current[1]+moves[3][1]]]
distmap = [S, N, E, W]
movable = {}
movacount = 0
for i, j in enumerate(distmap):
if not j :
movable.update({i : j})
movacount += 1
moved = movable.popitem()
if movacount > 2 :
altmove = movedlog[:]
branch = current
branchdist = moved
branchalt = movable
print("branchdist",branchdist)
elif movacount < 2 :
print(dist_negative[moved[0]])
if dist_negative[moved[0]] == movedlog[len(movedlog)-1] :
current = branch
moved = branchalt.popitem()
moveddist = dist[moved[0]]
current = [current[0]+moves[moved[0]][0],current[1]+moves[moved[0]][1]]
movedlog += moveddist
print (movedlog)
return "SSSSSEENNNEEEEEEESSWWWWSSSEEEESS"
一旦ループを15回にしてprintで吐き出しながら書いて見たのですが、
正直かなり無駄な感じでしんどかったのでこの方向は一旦ギブアップ。
とりあえず、色々調べて
http://qiita.com/MasayaMizuhara/items/86099ad721a329e1d6cd
を参考に、幅優先アルゴリズムで書いてみることに。
def checkio(maze_map):
start = [1, 1]
goal = [10, 10]
moves = [[1, 0], [-1, 0], [0, -1], [0, 1]]
dist = ["S", "N", "E", "W"]
cue =
movedlog =
route =
distlog = ""
flag = True
cue.append(start)
while flag:
moved = cue.pop()
route.append(moved)
S = [[moved[0]+moves[0][0], moved[1]+moves[0][1]], maze_map[moved[0]+moves[0][0]][moved[1]+moves[0][1]]]
N = [[moved[0]+moves[1][0], moved[1]+moves[1][1]], maze_map[moved[0]+moves[1][0]][moved[1]+moves[1][1]]]
E = [[moved[0]+moves[2][0], moved[1]+moves[2][1]], maze_map[moved[0]+moves[2][0]][moved[1]+moves[2][1]]]
W = [[moved[0]+moves[3][0], moved[1]+moves[3][1]], maze_map[moved[0]+moves[3][0]][moved[1]+moves[3][1]]]
distmap = [S, N, E, W]
for i, j in enumerate(distmap) :
if not j[1] :
cue.append(j[0])
if j[0] != goal :
if route.count(j[0]) > 0 :
cue.pop()
else :
route.append(j[0])
flag = False
print("cue", route)
print(route)
return "SSSSSEENNNEEEEEEESSWWWWSSSEEEESS"
なんか、だいぶ近づいた。。。んですかね？
あとはルートを変更した際の挙動をなんとかすればいけるんですかね。
あー、ようやく理解できました。
歩数を付け足すわけですね。
[歩数, x, y]]
で、前の歩数に対して足していく、
ルートが変わった場合、分岐時点の歩数から足していくと。
def checkio(maze_map):
start = [[1, 1], 0]
goal = [10, 10]
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
dist = ["S", "N", "E", "W"]
cue =
movedlog =
route =
distlog = ""
cue.append(start)
while len(cue) > 0:
moved = cue.pop()
route.append(moved)
movedlog.append(moved[0])
S = [[moved[0][0]+moves[0][0], moved[0][1]+moves[0][1]], maze_map[moved[0][0]+moves[0][0]][moved[0][1]+moves[0][1]]]
N = [[moved[0][0]+moves[1][0], moved[0][1]+moves[1][1]], maze_map[moved[0][0]+moves[1][0]][moved[0][1]+moves[1][1]]]
E = [[moved[0][0]+moves[2][0], moved[0][1]+moves[2][1]], maze_map[moved[0][0]+moves[2][0]][moved[0][1]+moves[2][1]]]
W = [[moved[0][0]+moves[3][0], moved[0][1]+moves[3][1]], maze_map[moved[0][0]+moves[3][0]][moved[0][1]+moves[3][1]]]
distmap = [S, N, E, W]
for i, j in enumerate(distmap) :
if not j[1] :
cue.append([j[0], moved[1]+1])
if j[0] != goal :
if movedlog.count(j[0]) > 0 :
cue.pop()
else :
route.append([j[0], moved[1]+1])
cue =
checker = route.pop()
routelist =
while len(route) > 0 :
checked = route.pop()
if checker[1] - 1 == checked[1] :
routelist.append([checker[0][0]-checked[0][0], checker[0][1]-checked[0][1]])
checker = checked
routelist.reverse()
for i in routelist :
for n, m in enumerate(moves) :
if i == m :
distlog += dist[n]
return distlog
いやー、これに3日くらい使いました。。。
そしてリファクタリングする気にもなりません。。。
で、評価されてる回答見るのはすごい時間かかりそうだったので、
ランダムに見ていった中で好きだったのが下記です。
def checkio(maze):
q = [(1,1)]
maze[1][1] = ''
for i, j in q:
for move, I, J in zip('NSWE', (i-1,i+1,i,i), (j,j,j-1,j+1)):
if maze[I][J] == 0:
maze[I][J] = maze[i][j] + move
q += [(I,J)]
if I == J == 10:
return maze[I][J]
超シンプル！！！！
うーん。これはどういう知識があれば思い付くのだろう。。
やっていることとしては全探索だけど、
ここまでシンプルにできるんですね。
勉強しよう。
