Project Euler 209

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

Q209.
τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0
を常に満たす、真偽表τはいくつあるか

6つの変数をまとめて6ビットの整数として考えると分かりやすくなる。その整数に対して0か1を対応させるのが真偽表、ということになる。
上の式に対応する2つの整数の組は、少なくともどちらかが0でなければならない。この対応をグラフで表す。そうすると、グラフの点の次数は2以下であることが確認できる。よって、グラフはループになっている。今回の場合、いくつかのループに分かれている。それらのループの大きさに対して、隣同士が1にならないような組合せが分かる。これは適当に調べればいい。



def convert(n):
a = (n & 32) >> 5
b = (n & 16) >> 4
c = (n & 8) >> 3
return ( (n & 31) << 1) | (a ^ (b & c))

def make_graph():
g = [ [ ] for i in range(64) ]
for n in range(64):
m = convert(n)
g[n].append(m)
g[m].append(n)
return g

def C(n, m):
if m == 0:
return 1
return C(n, m - 1) * (n - m + 1) / m

def H(n, m):
return C(n + m - 1, m)

def count_valid_loop(n):
s = 0
for m in range(n / 2 + 1):
if m == 0:
s += 1
elif m == 1:
s += n
else:
s += 2 * H(m, n - 2 * m)
if n >= 2 * m + 1:
s += H(m + 1, n - 2 * m - 1)
return s

def gen_connected_subgraph(g):
unused = set(range(64))
while len(unused):
s = set()
e0 = unused.pop()
while True:
s.add(e0)
unused.discard(e0)
e1 = g[e0][0]
if e1 not in unused:
e1 = g[e0][1]
if e1 not in unused:
yield s
break
e0 = e1

g = make_graph()
print reduce(max, map(len, g))
def mul(x, y): return x * y
print reduce(mul, map(count_valid_loop, map(len, gen_connected_subgraph(g))))