ALDS1_13_B: 8 Puzzle (続き2)
前の記事で書けなかったメモを書いていく
解説やサンプルコードは意外とおんなじようなことが書いてあった
書き方は違うけど考え方は同じ(だと思う
class State:
def dup(self):
ns = State()
ns.b = []
for row in self.b:
ns.b.append(row[:])
ns.z = self.z
ns.c = self.c
return ns
このState
をキューに入れて探索してるわけですが最初は
盤面をキューに入れるの?次の手をキューに入れるの?
などと考えておりました
結局のところ、ある局面をすっかり再現できる情報が必要なんだということに気づき
名前もState
に
なんかコンテキストスイッチみたいなもんだなと思うと
GoだったらGoroutineをいっぱい生やすみたいな解放もあるのかなと思ったり
スケジューリング次第で解が変わったりしかねませんが
サンプルコードは1次元配列で表現してた
どっちで書いても書けるけど、1次元だと二重ループ書かなくていいのが楽かな
それで簡単に済むときはそれでいこうか
ところで最近
Pythonのクラスをどうやって書いたらいいのかわからなくなっており
メソッドいらなくねと思ってnamedtupleを使ってみたり
今回はdef __init__(self, b=[]):
などと書いてハマるパターンを具現化させました
これはやっちゃいけないやつだってそういえば何かに書いてあったんだけど
正しくはdef __init__(self, b=None): if b is None: b = []
とかする
今回はs = State()
からのs.b = ...
でやってる
そして調べてみたらここで作ったdup
はcopy.deepcopy
でできるってこともわかり
class State: pass
になってしまうという
いっそのことdictで{"b": ..., "z": ..., "c": ...}
とかしてもいいのではという気も
def read_board():
s = State()
s.b = [None] * 3
for r in range(3):
s.b[r] = [int(x) for x in input().split()]
if 0 in s.b[r]:
s.z = (r, s.b[r].index(0))
s.c = 0
return s
特に大したことなし
どうもこういう2次元配列の書き方ってまどろっこしい気がするんですけど
いかがですか皆さん
def move_zero(s, h):
ns = s.dup()
z = ns.z
nz = (z[0] + h[0], z[1] + h[1])
ns.b[nz[0]][nz[1]], ns.b[z[0]][z[1]] = ns.b[z[0]][z[1]], ns.b[nz[0]][nz[1]]
ns.z = nz
ns.c += 1
return ns
1次元配列だったらもうちょっと見やすかったか
それと、リストじゃなくてタプルですんなり書ける方法ないかな
特定の要素だけ変更しつつ複製を作るみたいな
タプルならそのままset
で覚えておくことができるんだけど
classの使い道があるとすれば、こういうのをなんかの演算子に割り当てて
s * h
とか書けるようにする、みたいなことかなあ
def push_hands(q, s):
if s.z[0] != 0:
q.append(move_zero(s, (-1, 0)))
if s.z[0] != 3 - 1:
q.append(move_zero(s, (1, 0)))
if s.z[1] != 0:
q.append(move_zero(s, (0, -1)))
if s.z[1] != 3 - 1:
q.append(move_zero(s, (0, 1)))
とても素直に書いた
配列を使えば短くなるかもしれないけどこれはこれでいい気がしている
def hash(b):
return reduce(lambda acc, a: acc * 9 + a, sum(b, [])[:-1])
無理くり考えたハッシュ関数
サンプルコードではライブラリ使ってた
わたしもすなおにset
使います
sum(b, [])
で2次元配列をflattenできるというのは知らなかった
def solve(s):
end = hash([[1, 2, 3], [4, 5, 6], [7, 8, 0]])
hist = bytearray(hash([[8, 7, 6], [5, 4, 3], [2, 1, 0]]) + 1)
q = deque([])
while True:
h = hash(s.b)
if h == end:
return s.c
if not hist[h]:
push_hands(q, s)
hist[h] = True
s = q.popleft()
bytearray
のところ
[False] * (hash([[8, 7, 6], [5, 4, 3], [2, 1, 0]]) + 1)
などと書いても答えは出ますがそこだけでTLEになれます
せっかく自前のハッシュを作ったので終了判定はハッシュをつかいました