Project Euler 189

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

Q189.
辺の長さ8の正三角形を、辺の長さ1の小正三角形にわける。それを隣が同じ色にならないように赤・青・緑の3色で塗り分ける。塗り分け方は何通りあるか。

辺の長さ7の正三角形の有効な塗り分けで、下の辺に接する小正三角形の色の組合せが何通りあるかを求める。そして、それに接する下の小正三角形の色の組合せに対し、同じ色にならない辺の長さ7の正三角形の有効な塗り分けの数を数える。そして、そのそれぞれの組合せについて、隣の下に接する小三角形の塗り分けの組合せに対する数を数える。このように再帰的に求める。最後の辺の長さ8だけは最後合計の数だけ求めればいいから、本当はずっと速くなるが、ソースが長くなるのでやめる。
最初、4つの正三角形にわける方法を考えたが、どこを間違えているのか答えがあわなかった。辺の長さ4まではあっていたのに。またいつか考え直すかも。

from itertools import product
def is_match(t1, t2):

    for c1, c2 in zip(t1, t2):

        if c1 == c2:

            return False

    return True
def calc_match_top_bottom(t_bottom, a):

    s = 0

    for t_top, n in a.iteritems():

        if is_match(t_top, t_bottom):

            s += n

    return s
def gen_colors(t, k = 0):

    n = len(t)

    if k == n:

        for c in range(1, 4):

            if c != t[n-1]:

                yield (c,)

    else:

        g = gen_colors(t, k + 1)

        if k == 0:

            for c, a in product(range(1, 4), g):

                if c != t[0]:

                    yield (c,) + a

        else:

            for c, a in product(range(1, 4), g):

                if c != t[k-1] and c != t[k]:

                    yield (c,) + a
def add(b, e, s):

    if e in b:

        b[e] += s

    else:

        b[e] = s
def calc_match_right_left(t, s, b):

    for e in gen_colors(t):

        add(b, e, s)
def triangle(n):

    if n == 1:

        return { (1,): 1 }

    

    a = triangle(n - 1)

    

    b = { }

    for t in product(range(1, 4), repeat = n - 1):

        s = calc_match_top_bottom(t, a)

        calc_match_right_left(t, s, b)

    return b
N = 8

print sum(triangle(N).itervalues()) * 3