あほくさスライドパズルソルバー

ahokusa.py

import re
import queue

CARDS = {
    0: ':void:',
    1: ':ahokusa-top-left:',
    2: ':ahokusa-top-center:',
    3: ':ahokusa-top-right:',
    4: ':ahokusa-bottom-left:',
    5: ':ahokusa-bottom-center:',
    6: ':ahokusa-bottom-right:',
}
INV_CARDS = {v: k for k, v in CARDS.items()}

# board: 18-bit integer
def get_initial():
    s = ''.join(input() for _ in range(2))
    return [INV_CARDS[c] for c in re.findall(r'\:.*?\:', s)]
def encode(l):
    return sum(l[i] << 3 * i for i in range(6))
def decode(b):
    return [b >> 3 * i & 0b111 for i in range(6)]
MAX = 1 << 18

# adjacent states
def neighbors(b):
    for z in range(6):
        if b >> 3 * z & 0b111 == 0: break
    if z < 3:
        x = b >> 3 * (z + 3) & 0b111
        c = b & ~(0b111 << 3 * (z + 3)) | (x << 3 * z)
        yield (c, '上')
    if z >= 3:
        x = b >> 3 * (z - 3) & 0b111
        c = b & ~(0b111 << 3 * (z - 3)) | (x << 3 * z)
        yield (c, '下')
    if z % 3 != 2:
        x = b >> 3 * (z + 1) & 0b111
        c = b & ~(0b111 << 3 * (z + 1)) | (x << 3 * z)
        yield (c, '左')
    if z % 3 != 0:
        x = b >> 3 * (z - 1) & 0b111
        c = b & ~(0b111 << 3 * (z - 1)) | (x << 3 * z)
        yield (c, '右')
def goal(b0):
    l0 = decode(b0)
    for i in range(1, 7):
        if i not in l0:
            return encode([x if x != i else 0 for x in range(1, 7)])

# BFS
def bfs(b0):
    dist = [MAX for _ in range(MAX)]
    backtrace = [(-1, '') for _ in range(MAX)]
    que = queue.Queue()
    dist[b0] = 0
    que.put(b0)
    while not que.empty():
        b = que.get()
        for c, op in neighbors(b):
            if dist[c] == MAX:
                dist[c] = dist[b] + 1
                backtrace[c] = b, op
                que.put(c)
    b = goal(b0)
    if dist[b] == MAX: return '不成立'
    move = []
    while b != b0:
        b, op = backtrace[b]
        move.append(op)
    return ''.join(reversed(move))

if __name__ == '__main__':
    initial = get_initial()
    print(bfs(encode(initial)))