Project Euler 244 - inamori’s diary

Q244.
15パズルのようなもので、タイルを赤と青にしたものを用意する。
図のSからEに動かすのに、最短手数のものの経路を考える。この経路は問題文にあるように整数に変換できる。最短経路を整数に変換したものの和を求めよ。

状態は、20ビットあれば表せるから、整数にできる。
それで可能な状態を探っていくと、簡単に最短手数が分かる。しかし、可能な経路も記憶していくと、メモリが足りない。最初と最後の両側からやってみてもやはりメモリが足りない。方針を変えて、まず各ステップの状態を最短手数が可能な状態のみに絞る。そのとき、最初と最後から始めて中央の可能な状態を得て、区間を狭めて同じことをやっていくと各ステップが可能な状態が出てくる。しかし遅いが面倒でない、最初からやってみた状態と最後からやってみた状態の同じステップでの状態の集合の交わりを取る方法を使った。こうして各ステップの可能な状態を得て、また最初から、今度は経路も整数に変換しながら記録していった。



dir_dx = (-4, 1, 4, -1)

char = [ 68, 76, 85, 82 ]
def is_slidable(x, dx):

    if x >> 2 == 0:

        if dx == -4:

            return False

    elif x >> 2 == 3:

        if dx == 4:

            return False

    

    if (x & 3) == 0:

        if dx == -1:

            return False

    elif (x & 3) == 3:

        if dx == 1:

            return False

    

    return True
def next_status(s, dir):

    dx = dir_dx[dir]

    x = s >> 16

    next_x = x + dx

    if is_slidable(x, dx):

        color = (s >> next_x) & 1

        if color:   # blue

            s |= 1 << x

            s ^= 1 << next_x

        s = (s & 0xffff) | (next_x << 16)

        return s

    else:

        return -1
def next(stats):

    new_stats = set()

    for s in stats:

        for dir in range(4):

            s_new = next_status(s, dir)

            if s_new != -1:

                new_stats.add(s_new)

    return new_stats
def prev(stats):

    new_stats = set()

    for s in stats:

        for dir in range(4):

            s_new = next_status(s, (dir + 2) % 4)

            if s_new != -1:

                new_stats.add(s_new)

    return new_stats
def calc_status(s0, s1, f):

    ary_stats = [ set() ]

    ary_stats[0].add(s0)

    n = 0

    while s1 not in ary_stats[n]:

        ary_stats.append(f(ary_stats[n]))

        n += 1

    return ary_stats
def calc_probable_status(s0, s1):

    stats_forward = calc_status(s0, s1, next)

    stats_backward = calc_status(s1, s0, prev)

    min_length = len(stats_backward)

    for n in range(min_length):

        stats_forward[n] &= stats_backward[min_length-1-n]

    return stats_forward
def calc_checksum(c, dir):

    m = char[dir]

    return (c * 243 + m) % 100000007
def add(dic, k, v):

    if k in dic:

        dic[k].append(v)

    else:

        dic[k] = [ v ]
def step(dic_stats, stats):

    new_stats = { }

    for s, paths in dic_stats.iteritems():

        for dir in range(4):

            s_new = next_status(s, dir)

            if s_new in stats:

                for path in paths:

                    add(new_stats, s_new, calc_checksum(path, dir))

    return new_stats
s0 = 0xcccc

s1 = 0x5a5a

ary_stats = calc_probable_status(s0, s1)

dic_stats = { s0: [ 0 ] }

for stats in ary_stats[1:]:

    dic_stats = step(dic_stats, stats)

print sum(map(sum, dic_stats.itervalues()))