Project Euler 215

プロジェクトオイラー
http://projecteuler.net/index.php

Q215.
2×1と3×1のレンガを積んで、32×10の壁を作る。ただし、上下で同じ位置にレンガの切れ目があってはならない。レンガの積み方は何通りあるか。

1列の並べ方をグラフの点と考えて、上下に並べられるとき線で結ぶ。最初はバイナリ法のようなものを考えていて、5列と5列を結合するのに5列の一番上と下のレンガの並びが必要なので、両方をもって状態と考えていた。しかし、そうではなく、一番上の並びだけ状態と考え、その上に可能な1列を並べる、と考える。レンガではなく、純粋にグラフで考えるほうがわかりやすかった。グラフ理論では正確にどう呼ぶのか知らないが、長さが9の道を考える。そのとき始点に対して、隣の点を始点とする長さ8の道の数を足し合わせればよい。

from itertools import combinations

import time
def make_row_core(n, e):

    t = ()

    j = 0

    s = 0

    for i in range(n - 1):

        if j < len(e) and i == e[j]:

            s += 3

            j += 1

        else:

            s += 2

        t += (s,)

    return t
def make_row(len):

    a = [ ]

    n0 = len % 2

    for n in range(n0, len / 3 + 1, 2):

        m = (len - n * 3) / 2

        for e in combinations(range(n + m), n):

            a.append(make_row_core(n + m, e))

    return a
def is_match(r1, r2):

    if abs(len(r1) - len(r2)) >= 2:

        return False

    if len(r1) < len(r2):

        r1, r2 = r2, r1

    if len(r1) > len(r2):

        if r1[0] >= r2[0]:

            return False

        offs = 1

    else:

        offs = 0

    

    for i in range(len(r2)):

        if r1[i+offs] == r2[i]:

            return False

    return True
def is_match(r1, r2):

    for e in r1:

        if r2.count(e):

            return False

    return True
def make_graph(a):

    n = len(a)

    g = [ [ ] for i in xrange(n) ]

    for i in xrange(n):

        for j in xrange(i + 1, n):

            if is_match(a[i], a[j]):

                g[i].append(j)

                g[j].append(i)

    return g
def mul(g, a):

    return [ sum(map(lambda k: a[k], e)) for e in g ]
def pow(g, n):

    if n == 2:

        return [ len(e) for e in g ]

    

    return mul(g, pow(g, n - 1))
t = time.clock()

N = 32

M = 10

a = make_row(N)

print len(a)

g = make_graph(a)

print sum(pow(g, M))

print time.clock() - t