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.