A year ago today, I blogged that Tom Duff had shown me Russell Cox’s blog. I hadn’t kept up with it, so I went over there and found this interesting article on a nifty problem in combinatorics. I solved a somewhat similar problem (counting the precise number of possible checkers positions) but sadly, I couldn’t find my code to do it. So, I reimplemented it. Here it is. I only used the most obvious optimizations that Cox illustrates in his example: I bet that I could do a lot better if I thought this through.
#!/usr/bin/env python
import locale
d = { }
def fact(n):
if n == 0:
return 1
else:
return n*fact(n-1)
def comb(a, b):
return fact(a) / (fact(b)*fact(a-b))
def num(bk, wk, bm, wm, f):
s = (bk, wk, bm, wm, f)
if d.has_key(s):
return d[s]
else:
val = comb(4, f) * comb(24, bm-f) * comb(28-(bm-f), wm) * comb(32-bm-wm, bk) * comb(32-bm-wm-bk, wk)
d[s] = val
return val
total = { }
for n in range(1, 24+1):
for bm in range(0, min(n, 12)+1):
for bk in range(0, min(n, 12)-bm+1):
for wm in range(0, min(n-bm-bk, 12)+1):
for wk in range(0, min(n-bm-bk, 12)-wm+1):
for f in range(0, min(bm, 4)+1):
val = num(bk, wk, bm, wm, f)
total[n] = total.get(n, 0) + val
locale.setlocale(locale.LC_ALL, "en_US")
mxlen = 0
for n in range(1, 25):
mxlen = max(mxlen, len(locale.format("%d", (total[n]-1) - (total.get(n-1, 1) - 1), True)))
print '-' * (mxlen + 3)
for n in range(1, 25):
print "%2d" % n, locale.format("%d", (total[n]-1) - (total.get(n-1, 1) - 1), True).rjust(mxlen)
print '-' * (mxlen + 3)
print " ",locale.format("%d", (total[24]-1), True)
Here’s the output:
------------------------------
1 120
2 6,972
3 261,224
4 7,092,774
5 148,688,232
6 2,503,611,964
7 34,779,531,480
8 406,309,208,481
9 4,048,627,642,976
10 34,778,882,769,216
11 259,669,578,902,016
12 1,695,618,078,654,976
13 9,726,900,031,328,256
14 49,134,911,067,979,776
15 218,511,510,918,189,056
16 852,888,183,557,922,816
17 2,905,162,728,973,680,640
18 8,568,043,414,939,516,928
19 21,661,954,506,100,113,408
20 46,352,957,062,510,379,008
21 82,459,728,874,435,248,128
22 118,435,747,136,817,856,512
23 129,406,908,049,181,900,800
24 90,072,726,844,888,186,880
------------------------------
500,995,484,682,338,672,639
Addendum: It’s actually a tad subtle to determine why caching works so well in this program. I’ll have to think about it some more.
Addendum2: I actually wasn’t entirely precise before. Strictly speaking, these aren’t all valid checkers positions, since obviously some of them cannot be reached from the starting position for the game.