ALDS1_13_B: 8 Puzzle (続き3)

といったところを考慮して書き直し
盤面を1次元で覚えたら見た目がだいぶすっきりしていい気分
ハッシュ関数は消して、盤面をタプルにしてからsetに入れてみた

from sys import stdin
from collections import deque
from copy import deepcopy

class State:
    pass

def read_board():
    s = State()
    s.b = [int(x) for x in stdin.read().split()]
    s.z = s.b.index(0)
    s.c = 0
    return s

def move_zero(s, h):
    ns = deepcopy(s)
    ns.z += h
    ns.b[s.z], ns.b[ns.z] = ns.b[ns.z], ns.b[s.z]
    ns.c += 1
    return ns

def push_hands(q, s):
    if s.z % 3 != 0:
        q.append(move_zero(s, -1))
    if s.z % 3 != 3 - 1:
        q.append(move_zero(s, 1))
    if s.z // 3 != 0:
        q.append(move_zero(s, -3))
    if s.z // 3 != 3 - 1:
        q.append(move_zero(s, 3))

def solve(s):
    hist = set()
    q = deque([])
    while True:
        t = tuple(s.b)
        if t == (1, 2, 3, 4, 5, 6, 7, 8, 0):
            return s.c
        if t not in hist:
            push_hands(q, s)
            hist.add(t)
        s = q.popleft()

def main():
    b = read_board()
    print(solve(b))

main()

TLE
なんでや

タプルをsetに入れるのをやめて自前のハッシュ関数に戻したら？ → TLE
setをやめてbytearrayに戻したら？ → TLE
deepcopyをdupに戻したら？ → AC
おまえか

class State:
    def dup(self):
        ns = State()
        ns.b = self.b[:]
        ns.z = self.z
        ns.c = self.c
        return ns

def move_zero(s, h):
    ns = s.dup()
    ns.z += h
    ns.b[s.z], ns.b[ns.z] = ns.b[ns.z], ns.b[s.z]
    ns.c += 1
    return ns

ここ直してAC 01.50s 56288KB

前回 02.95s 84156KB だから
倍速くなってメモリもけっこう節約した
これくらいでよかろう

deepcopyは循環参照を避けるためにコピーしたオブジェクトを覚えておくとか
そういうののせいで重いのかなあ

The deepcopy() function avoids these problems by:
keeping a memo dictionary of objects already copied during the current copying pass;

お

In order for a class to define its own copy implementation, it can define special methods copy() and deepcopy().

そんなこともできるのか
元のソースでこうしても動く？

class State:
    def __deepcopy__(self, memo):
        ns = State()
        ns.b = self.b[:]
        ns.z = self.z
        ns.c = self.c
        return ns

動いたしACだったけど遅くなった 02.91s 56516 KB
deepcopy()を間に挟むだけでそんなに負荷なん？