Haunted House の続き

Haunted House で、他の人の解答を見てみた。
他の人の解答を読むだけでも、かなり難しくて頭が混乱してしまう。

私は、Open Labyrinth で初めてグラフという言葉を知ったのだけど、どうしても、グラフ探索＝迷路の探索、という狭いイメージで捉えてしまっていた。今回の問題でも、各部屋がグラフの頂点（ノード）で、頂点を渡り歩いてゴールまで行く、というふうに考えていたので、幽霊が動くとなると、どうしたらいいかわからず行き詰まってしまったのだ。
グラフの頂点は「状態」として考えるべきだった。今回の問題も、迷路の探索ではなく、オセロのように交互に盤面を変化させていく問題、というイメージで捉えるとわかりやすい。

その点で、すごく参考になったのがSim0000さんの解答。twitterで説明していただいたのだが、ステファンの位置と幽霊の位置をグラフの頂点として最短経路を求めている。キューに（ステファンの位置、幽霊の位置、一つ前のステファンの位置、一つ前の幽霊の位置、移動方向）を入れている。
一部を抜粋したのがこちら。

    seen = {}
    q = deque([(stephan, ghost, 0, 0, 4)])
    while len(q) != 0:
        s, g, s0, g0, d = q.popleft()
        if s == g or (s, g) in seen: continue
        seen[(s, g)] = (s0, g0, d)
        if s == 1: break

        # stephan move
        for d in range(4):
            if 'WENS'[d] in house[s - 1]: continue
            s1 = s + (-1, 1, -4, 4)[d]
            # ghost move
            g1 = ghost_move(house, s1, g)
            q.append((s1, g1, s, g, d))
    else:
        print('not found')
        return 'N'

http://www.checkio.org/mission/haunted-house/publications/Sim0000/python-3/first/
こんなシンプルに解けるなんて・・・。

こちらは、あらかじめすべてのパターンを計算しておくという解法。(長いので引用はしない)
http://www.checkio.org/mission/haunted-house/publications/htamas/python-3/first/

precompute()でstrategyを計算しておてcheckio()では参照するだけ。
strategyは、key=(ステファンの位置,幽霊の位置)、value=(何手先でゴールできるか,移動方向) の辞書となっている。strategyの計算部分がややこしくて、まだちゃんと理解できていないのだが。(^^;

コメント欄をみると、アルファ・ベータ法というのを使って、計算をもっと効率的に行うことができるようだ。（しかし、もう私の体力はゼロなのでパス・・・。）

いやー、難しい問題だった。他の問題を終えたら、再度挑戦してみたい。
さて、次はDropBox島へ。