brainwagon

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.

Addendum²: 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.