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になれます

せっかく自前のハッシュを作ったので終了判定はハッシュをつかいました