Note: This notebook takes the form of a conversation/collaboration between two problem solvers, Ali and Bo.
Ali: Huh. This is interesting. You know how, in a board game like Monopoly, you roll two dice, add them up, and then move that number of spaces?
Bo: Right.
Ali: And a sum like 2 can only be made one way, 1 + 1, but 9 can be made multiple ways.
Bo: Yeah. 9 can be made 4 ways: 3 + 6, 4 + 5, 5 + 4, or 6 + 3.
Ali: The interesting thing is that people have been playing dice games for 7,000 years. But it wasn't until 1977 that Colonel George Sicherman asked whether is is possible to have a pair of dice that are not "standard" dice (standard dice have [1, 2, 3, 4, 5, 6] on their six sides) but have the same distribution of sums as a standard pair–so the pair of Sicherman dice would also have one way of making a 2 and four ways of making 9, but it could be different ways; maybe 8+1 could be one way. Like standard dice, each of the sides on a Sicherman die is a positive integer, but some of them could be greater than 6.
Bo: And what did Sicherman find?
Ali: Wouldn't it be more fun to figure it out for ourselves?
Bo: OK!
Ali: How could we proceed?
Bo: When in doubt, use brute force: we can write a program to enumerate and check the possibilities:
Ali: Good. First I'll write down some data types:
from typing import *
Side = int # Type for a side of a die: a positive integer, e.g. 3
Die = list # Type for a die: a list of numbers on sides, e.g. [1, 2, 2, 4, 8, 9]
Pair = tuple # Type for a pair of dice, e.g. ([1, 3, 4, 4, 5, 8], [1, 2, 2, 4, 8, 9])
Ali: Now I can code up your description almost verbatim. I'll also keep track of our TO DO list:
def sicherman() -> List[Pair]:
"""A list of nonstandard pairs of dice that have the same
distribution of sums as a standard pair of dice."""
return [pair for pair in all_pairs(all_dice())
if distribution_of_sums(pair) == standard_sums
and pair != standard_pair]
def all_pairs(dice) -> List[Pair]:
"""Return all dice pairs (A, B) where A <= B (so, not also (B, A))."""
return [(A, B) for A in dice for B in dice if A <= B]
# TODO: all_dice(), distribution_of_sums(pair), standard_sums, standard_pair
Bo: Looks good to me. We should test all_pairs
to make sure it works:
all_pairs(['a', 'b', 'c'])
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
Ali: Now for distribution_of_sums(pair)
: we need some way to represent all the 36 possible sums from a pair of dice. We want a representation that will be the same for two different pairs if all 36 sums are the same, but where the order of the sums doesn't matter.
Bo: So we want a set of the sums?
Ali: Well, it can't be a set, because we need to know that, say, a 9 is made four times in the pair's distribution of sums, not just that 9 is a member of the set of sums. The technical term for a collection where order doesn't matter but where you can have repeated elements is a multiset or bag. What's a good representation for that?
Bo: Well if we don't want order to matter, the easiest representation is just a sorted list.
Ali: OK, so Bag
is just the function sorted
and here's some code for distribution_of_sums
, and for "standard" dice.
Dice start at one, not zero, so I can't use range(6)
for the possible sides of a die; instead I decided to define ints
and use ints(1, 6)
.
Bag = sorted # Implement a bag as a sorted list
def distribution_of_sums(pair) -> List[int]:
"All possible sums of a side from one die plus a side from the other."
(A, B) = pair
return Bag(a + b for a in A for b in B)
def ints(start, end) -> range:
"The integers from start to end, inclusive."
return range(start, end + 1)
standard_die = Die(ints(1, 6))
standard_pair = (standard_die, standard_die)
standard_sums = distribution_of_sums(standard_pair)
# TODO: all_dice()
Bo: Let's check the standard_sums
:
assert len(standard_sums) == 36
print(standard_sums)
[2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12]
Bo: Looks good! Now only one more thing on our TO DO list:
Ali: all_dice()
should generate all possible dice, where by "possible" I mean the dice that could feasibly be part of a pair that is a solution to the Sicherman problem. Do we know how many dice that will be? Is it a big enough number that efficiency will be a problem?
Bo: Let's see. A die has six sides. If each side can be a number from, say, 1 to 10, that's 106 or a million possible dice; a million is a small number for a computer.
Ali: True, a million is a small number. But how many pairs of dice will there be?
Bo: Ah. That's right. A million squared is a trillion. That's a big number even for a computer. An empty loop that just counts to a million takes milliseconds in Python, but counting to a trillion takes hours. Checking a trillion pairs will take days.
Ali: So we really need to pare down the number of possible dice. What about permutations?
Bo: Good point! If I have the die [1, 2, 3, 4, 5, 7], then I don't need the different permutations–that is, dice like [2, 4, 7, 1, 3, 5]. We can arrange to only generate dice whose sides are in sorted order.
Ali: Any other constraints on the sides?
Bo: Here's something: the distribution of sums for a standard pair has exactly one 2. The only way to get a sum of 2 from two positive integers is 1+1. So that means that each die must have exactly one 1; no more, no less.
Ali: You said the sides can range from 1 to 10. Are you sure that 11 can't be part of a legal solution?
Bo: I was just guessing, but now I can see that it is true. The distribution of sums for a pair has a 12, and nothing higher. Assume one die had an 11 on some side. We know the other die can only have one 1, so it must have some sides that are greater than 1, so the pair would make some sums that are greater than 12. That's wrong, so that means the assumption must be wrong: it can't be true that a die has an 11.
Ali: So all together the smallest number must be 1, the next smallest is at least 2, they're all 10 or less, and we'll make sure the numbers are in non-decreasing order to avoid listing two permutations of the same die. We can code that up:
def all_dice() -> List[Die]:
"""A list of all feasible 6-sided dice for the Sicherman problem."""
return [[1, b, c, d, e, f]
for b in ints(2, 10)
for c in ints(b, 10)
for d in ints(c, 10)
for e in ints(d, 10)
for f in ints(e, 10)]
Ali: Let's see how many dice there are:
len(all_dice())
1287
Ali: Nice! We got down from a million to 1287 different dice, which means the number of pairs is reduced from a trillion to under a million! I don't want to look at all 1287 of them, but here's every hundreth die:
all_dice()[::100]
[[1, 2, 2, 2, 2, 2], [1, 2, 2, 4, 7, 8], [1, 2, 3, 3, 10, 10], [1, 2, 4, 4, 6, 8], [1, 2, 5, 6, 8, 9], [1, 3, 3, 3, 3, 8], [1, 3, 3, 7, 8, 9], [1, 3, 5, 5, 5, 6], [1, 3, 7, 8, 8, 8], [1, 4, 4, 8, 8, 9], [1, 4, 7, 7, 7, 7], [1, 5, 6, 6, 8, 8], [1, 6, 7, 7, 8, 8]]
Ali: I think we're ready to run sicherman()
. Any bets on what we'll find out?
Bo: I bet that Sicherman is remembered because he discovered a pair of dice that works. If he just proved the non-existence of a pair, I don't think there would be an article about him.
Ali: Makes sense. Here goes:
sicherman()
[([1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8])]
Bo: Look at that!
Ali: It turns out you can buy a pair of dice with just these numbers, and there are some nice charts and tables on Wikipedia explaining it all.
Ali: We could stop here. Or ... what if we looked at other-shaped dice?
Ali: I know 4-, 8–, 12-, and 20-sided dice are common. Let's try to handle any N-sided dice.
Bo: Well, the number of dice pairs is going to be O(N2N), because when you add an N-th side to a die it can have (almost) N possible values, and then the number of pairs is proportional to the square of the number of dice. So my guess is we won't get up to 20 before our program becomes too slow. But we can go about parameterizing sicherman
and the other pieces for now, and worry about efficiency later:
def sicherman(N=6) -> List[Pair]:
"""A list of pairs of N-sided dice that have the same
distribution of sums as a standard pair of N-sided dice."""
standard_pair = nth_standard_pair(N)
standard_sums = distribution_of_sums(standard_pair)
return [pair for pair in all_pairs(all_dice(N))
if distribution_of_sums(pair) == standard_sums
and pair != standard_pair]
def nth_standard_pair(N) -> Die: return (Die(ints(1, N)), Die(ints(1, N)))
# TODO: all_dice(N)
Ali: Now, for all_dice(N)
, I think most of the analysis from N=6
still holds:
2 * N - 2
For the old version of all_dice()
, we had five nested loops for the five sides after the first. But the number of nested loops in a program is detemined at compile time; I can't write a program that has N - 1
nested loops. We'll have to find some other implementation technique.
Bo: Here's an iterative approach: we keep track of a list of partially-formed dice, and on each iteration, we add a side to all the partially-formed dice in all possible ways, until the dice all have N
sides. Our list starts with just one partially-formed die, with a single side containing a 1:
dice = [ [1] ]
Suppose N = 4
. Then the biggest number on any side is 6, and we get these partially-formed dice with 2 sides:
dice = [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6]
To extend to 3 sides we would add a number to each of those five in all possible ways, giving:
dice = [[1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6],
[1, 3, 3], [1, 3, 4], [1, 3, 5], [1, 3, 6],
[1, 4, 4], [1, 4, 5], [1, 4, 6],
[1, 5, 5], [1, 5, 6],
[1, 5, 6]]
The final iteration would add one more side to each of these. Here's how the code looks:
def all_dice(N=6) -> List[Die]:
"""All feasible Sicherman dice with N sides."""
dice = [ [1] ] # The first side must be 1
for _ in range(N - 1): # Add N - 1 sides, each nondecreasing, between 2 and 2N-2
dice = [die + [side]
for die in dice
for side in ints(max(2, die[-1]), 2 * N - 2)]
return dice
assert len(all_dice(6)) == 1287 # Make sure this hasn't changed
Ali: Let's try sicherman(N)
for some small values of N
.
%time {N: sicherman(N) for N in ints(2, 6)}
CPU times: user 2.52 s, sys: 22.1 ms, total: 2.55 s Wall time: 2.58 s
{2: [], 3: [], 4: [([1, 2, 2, 3], [1, 3, 3, 5])], 5: [], 6: [([1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8])]}
Bo: It is certainly reassuring that we get the same result for sicherman(6)
as with the old version of sicherman()
.
Ali: And comforting that the run time is about the same.
Bo: And we learned something new: there is a result for sicherman(4)
but not for 2, 3, and 5. That's interesting!
Ali: Maybe there can be no solution for primes? How much farther can we go beyond N = 6
?
Bo: Let's count how many possible dice there are for various values of N
:
{N: len(all_dice(N)) for N in ints(2, 9)}
{2: 1, 3: 6, 4: 35, 5: 210, 6: 1287, 7: 8008, 8: 50388, 9: 319770}
Ali: That doesn't look encouraging. With run time proportional to the square of the number of dice, it looks like it will be on the order of a minute for N=7
, an hour for N=8
, and days for N=9
.
Ali: We still need to pare down the number of dice! Can we tighten up the constraints on sides?
I think it would be helpful to me to have a look at a table of distributions of sums:
from collections import Counter
for N in ints(2, 7):
ctr = Counter(distribution_of_sums(nth_standard_pair(N)))
print(f"N = {N}: {dict(ctr)}")
N = 2: {2: 1, 3: 2, 4: 1} N = 3: {2: 1, 3: 2, 4: 3, 5: 2, 6: 1} N = 4: {2: 1, 3: 2, 4: 3, 5: 4, 6: 3, 7: 2, 8: 1} N = 5: {2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 4, 8: 3, 9: 2, 10: 1} N = 6: {2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 5, 9: 4, 10: 3, 11: 2, 12: 1} N = 7: {2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 7, 9: 6, 10: 5, 11: 4, 12: 3, 13: 2, 14: 1}
Bo: You're right! That is helpful! I'm reminded of the very first die generated by the first version of all_dice()
:
all_dice()[0]
[1, 2, 2, 2, 2, 2]
Bo: I had a feeling that was too many twos, and could never be part of a solution. I can see now that every nth_standard_sums
distribution has at most one 2, two 3s, three 4s, and so on. How does the distribution relate to the dice? We know every die has a 1. So a die with five 2s, when paired with any other die, would make six 3s. That's too many; we can only have two 3s in a distribution. That means that a die can never have more two 2s, three 3s, four 4s, and so on. It all works becuase we know the other die has to have a 1.
I'm going to define a function lower_bounds(N)
which will produce a list of integers that are the lower bounds for each side of an N
-sided die. Previously, our lower bounds for a 6-sided die were implicitly specified as [1, 2, 2, 2, 2, 2], but we now know that's not right: we don't want to allow a die with five 2s.
Ali: Before you do that, I thought of something else: the first side is special in that there can only be one copy of it; otherwise we'd get two 2s, and we only want one 2. The last side should be similarly special. We don't know what the last value will be, but we do know that we only want one of them, because if there were more than one, then we'd get more than one of the biggest sum in the distribution of sums, and we know we only want one.
Bo: Very good. That means the lower bound of the last side must be one more than the lower bound of the penultimate side. Here we go:
def lower_bounds(N):
"A list of lower bounds for respective sides of an N-sided die."
bounds = [1] # First side is 1
while len(bounds) < N:
s = bounds[-1] + 1
bounds.extend(s * [s]) # Allow two 2s, three 3s, etc.
bounds = bounds[:N] # If we added too many s's, drop the extras
bounds[-1] = bounds[-2] + 1 # Last side is one more than second-to-last
return bounds
lower_bounds(6)
[1, 2, 2, 3, 3, 4]
lower_bounds(10)
[1, 2, 2, 3, 3, 3, 4, 4, 4, 5]
Ali: Yeah, that looks right.
Bo: And now for the upper bounds. For, say, N=10, the biggest sum in the distribution of sums is 20. One of the lower bounds for N=10 is 5, meaning that every 10-sided die will have a 5 or higher. That implies that 15 is an upper bound for every side: no 10-sided die can have a number more than 15, because otherwise there would be a sum over 20.
Ali: So 15 is the upper bound for the final side (and 1 is the upper bound for the first side). And as I just said, we know that whatever the biggest number is, there can only be one of them, so the upper bound for the penultimate number is one less than the final number. What else do we know?
Bo: It gets complicated. It was easier with the lower bounds, because we know every die has a 1. We don't know exactly what the biggest number will be on a die. So I'm happy letting all the upper bounds between the first and last sides be one less than the last:
def upper_bounds(N):
"A list of upper bounds for respective sides of an N-sided die."
biggest = 2 * N - lower_bounds(N)[-1]
middle = (N - 2) * [biggest - 1]
return [1, *middle, biggest]
Bo: I'll make a little thing to display the bounds:
def show_bounds(Ns):
for N in Ns:
print(f'N = {N:2}: ' + ' | '.join(f'{L}-{U:<2}' for L, U in zip(lower_bounds(N), upper_bounds(N))))
show_bounds((6, 8, 10, 12, 13))
N = 6: 1-1 | 2-7 | 2-7 | 3-7 | 3-7 | 4-8 N = 8: 1-1 | 2-10 | 2-10 | 3-10 | 3-10 | 3-10 | 4-10 | 5-11 N = 10: 1-1 | 2-14 | 2-14 | 3-14 | 3-14 | 3-14 | 4-14 | 4-14 | 4-14 | 5-15 N = 12: 1-1 | 2-17 | 2-17 | 3-17 | 3-17 | 3-17 | 4-17 | 4-17 | 4-17 | 4-17 | 5-17 | 6-18 N = 13: 1-1 | 2-19 | 2-19 | 3-19 | 3-19 | 3-19 | 4-19 | 4-19 | 4-19 | 4-19 | 5-19 | 5-19 | 6-20
Bo: I can use the bounds to make a more constrained version of all_dice(N)
, like this:
def all_dice(N=6) -> List[Die]:
"""All feasible Sicherman dice with N sides."""
uppers = upper_bounds(N)
dice = [ [1] ] # The first side must be 1
for i in range(1, N): # Add N - 1 more sides
dice = [die + [side]
for die in dice
for side in ints(die[-1] + (i == (N - 1)), uppers[i])
if die.count(side) < side]
return dice
Ali: What's up with (i == (N - 1))
?
Bo: Oh. In Python a Boolean expression is equivalent to 0 or 1, so this says "the lower bound for the next side is the same as the lower bound for the previous side, die[-1]
, except that if this is the last side, then the lower bound is one more."
Ali: How come you don't even reference lower_bounds(N)
within all_dice(N)
? And how come you have the if die.count(side) < side]
clause? Is this code repetition intentional, or did you forget that lower_bound(N)
already dealt with having only two 2s, three 3s, etc.?
Bo: It is intentional, but I agree with you that it is confusing and look repetitious. Even though lower_bounds
is not used in all_dice
, it is used in upper_bounds
; without it, the bounds wouldn't be as tight. The difference is that in lower_bounds(N)
we're answering the question "what's the lowest possible value for side s across every single N-sided die?" In all_dice(N)
, we're considering a different question: "for this particular dice, what numbers can come next?" That's two different things, so we need two pieces of code.
Suppose that with N = 6
we have the partial die [1, 3, 3, 3]
. The lower bound for the next side is 3, and there are many die that have a 3 on the 5th side. But for this particular die we can't allow a fourth 3; that's why all_dice(N)
needs to check, and can't rely on lower_bounds(N)
alone.
Ali: I got it.
Let's see how much we have reduced the numbers of all_dice
:
{N: len(all_dice(N)) for N in ints(2, 10)}
{2: 1, 3: 1, 4: 10, 5: 31, 6: 226, 7: 1555, 8: 5728, 9: 39416, 10: 266931}
Ali: Wow! For N = 6
we're down from 1287 to 226 dice.
Bo: Let's check out some of the all_dice(6)
; hopefully we got rid of the die with five 2s:
list(all_dice(6))[::20]
[[1, 2, 2, 3, 3, 4], [1, 2, 2, 4, 5, 7], [1, 2, 3, 3, 4, 5], [1, 2, 3, 5, 5, 6], [1, 2, 4, 5, 5, 6], [1, 2, 6, 6, 6, 7], [1, 3, 3, 4, 5, 7], [1, 3, 4, 4, 5, 7], [1, 3, 5, 5, 7, 8], [1, 4, 4, 5, 5, 6], [1, 4, 6, 6, 6, 7], [1, 6, 6, 6, 6, 7]]
Ali: Let's rerun sicherman(N)
on small values of N
:
%time {N: sicherman(N) for N in ints(2, 6)}
CPU times: user 74.7 ms, sys: 1.29 ms, total: 76 ms Wall time: 75.2 ms
{2: [], 3: [], 4: [([1, 2, 2, 3], [1, 3, 3, 5])], 5: [], 6: [([1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8])]}
Ali: Awesome! We get the same results, but faster. Let's proceed cautiously on to 7:
%time sicherman(7)
CPU times: user 4.76 s, sys: 49.9 ms, total: 4.81 s Wall time: 4.86 s
[]
Ali: Too bad! Too bad we didn't get a solution for N = 7, and too bad that it took 60 times longer than N = 6. We could do N = 8 with a wait of a few minutes, but N = 9 will take hours.
Bo: We need a brand new approach; there are just too many dice. I'm not sure what to do to reduce them.
Ali: Maybe we could concentrate on considering fewer pairs of dice, without worrying about considering fewer dice?
Bo: How could we do that? Isn't the number of pairs always determined by the number of dice?
Ali: Remember, we're looking for feasible pairs. So if there was some way of knowing ahead of time that two dice were incompatible as a pair, we wouldn't even need to consider the pair; we'd spend zero run time on them.
Bo: By incompatible, you mean they can't form a pair that is a solution.
Ali: Right. Consider this: in any valid pair, the sum of the biggest number on each die must be 2N. For example, with N = 6:
([1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8]) sum of biggests = 4 + 8 = 12
([1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]) sum of biggests = 6 + 6 = 12
So if we have a 6-sided die with biggest number 7, what dice should we consider pairing it with?
Bo: Only ones with biggest number 5.
I get it: we sort all the die into bins labeled with their biggest number. Then we look at each bin, and for the "7" bin, we pair them up with the dice in the "5" bin. In general, the B bin can only pair with the 2N - B bin.
Ali: Exactly.
Bo: Cool. I can see how that can cut the amount of work by a factor of 10 or so. But I was hoping for a factor of a million.
Ali: There are other properties of a feasible pair.
Bo: Like what?
Ali: Well, what about the number of 2s in a pair?
Bo: Let's see. We know that any distribution of sums has to have two 3s, and the only way to make a 3 is 2+1. And each die has only one 1, so that means that each pair of dice has to have a total of exactly two 2s.
Ali: Does it have to be one 2 on each die?
Bo: No. It could be one each, or it could be two on one die and none on the other. So a die with x twos can only pair with dice that have 2 - x twos.
Ali: How about the number of 3s in a pair?
Bo: Hmm. A sum has to have three 4s, and the 4s have to come from either 2 + 2 or 3 + 1. So it is not as straightforward as with 2s. Let's make a table of allowable combinations for two dice, A and B:
A 1s |
A 2s |
A 3s |
B 1s |
B 2s |
B 3s |
ways to sum to 4 |
---|---|---|---|---|---|---|
1 | 0 or 2 | 0 | 1 | 2 or 0 | 3 | 1+3, 1+3, 1+3 |
1 | 0 or 2 | 1 | 1 | 2 or 0 | 2 | 3+1, 1+3, 1+3 |
1 | 0 or 2 | 2 | 1 | 2 or 0 | 1 | 3+1, 3+1, 1+3 |
1 | 0 or 2 | 3 | 1 | 2 or 0 | 0 | 3+1, 3+1, 3+1 |
1 | 1 | 0 | 1 | 1 | 2 | 2+2, 1+3, 1+3 |
1 | 1 | 1 | 1 | 1 | 1 | 2+2, 3+1, 1+3 |
1 | 1 | 2 | 1 | 1 | 0 | 2+2, 3+1, 3+1 |
Bo: It looks like the number of 3s in a pair totals three if one die has both 2s, or to two if the 2s are split.
Ali: Great. I've got one more property we could use. Consider the sums of 6-sided Sicherman and standard pairs:
sum([1, 2, 2, 3, 3, 4] + [1, 3, 4, 5, 6, 8])
42
sum([1, 2, 3, 4, 5, 6] + [1, 2, 3, 4, 5, 6])
42
Bo: They're the same. Is that the question that 42 is the answer to? But does a Sicherman pair always have to have the same sum as a standard pair? I guess it does, because the sum of distribution_of_sums(pair)
is just all the sides added up N times each, so two pairs have the same sum of distribution_of_sums(pair)
if and only if they have the same sum.
Ali: So consider the die [1, 3, 3, 3, 4, 5]. What do we know about the dice that it can possibly pair with?
Bo: OK, that die has a biggest side of 5, so it can only pair with dice that have a biggest side of 12 - 5 = 7. It has a sum of 19, so it can only pair with dice that have a sum of 42 - 19 = 23. It has no 2s, so it can only pair with dice that have two 2s. And it has three 3s (and no 2s), so it can only pair with dice with no 3s.
Ali: I wonder how many such dice there are, out of all 226 all_dice(6)
?
[die for die in all_dice(6)
if max(die) == 7 and sum(die) == 23 and die.count(2) == 2 and die.count(3) == 0]
[[1, 2, 2, 5, 6, 7]]
Bo: There's only one! So, [1, 3, 3, 3, 4, 5] only has to try to pair with one die, rather than 226. Nice improvement!
Ali: In general, what's the sum of the sides of a standard pair?
Bo: Easy, that's N × (N + 1). Gauss knew that when he was in elementary school!
Bo: OK, we can code this up easily enough. The point of all the code below is to redefine all_pairs(dice)
to be more efficient::
from collections import defaultdict, namedtuple
Label = namedtuple('Label', 'sum, max, twos, threes')
def label(die) -> Label:
"""Return a tuple of the sum of the die, the biggest side, and the number of 2's and 3's."""
return Label(sum(die), max(die), die.count(2), die.count(3))
def all_pairs(dice: List[Die]) -> Iterable[Pair]:
"""Yield all pairs of dice that could possibly be a solution to the Sicherman problem."""
table = tabulate_dice(dice)
N = len(dice[0])
for label1 in table:
label2 = compatible_label(label1, N)
if label1 <= label2 and label2 in table:
for A in table[label1]:
for B in table[label2]:
yield (A, B)
def tabulate_dice(dice: List[Die]) -> Dict[Label, List[Die]]:
"""Put all dice into bins in a hash table, keyed by label(die).
Each bin holds a list of dice with that key."""
# Example: {(21, 6, 1): [(1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 4, 7), ...]
table = defaultdict(list)
for die in dice:
table[label(die)].append(die)
return table
def compatible_label(label: Label, N) -> Label:
"""Return a bin Label that is compatible with `label` for N-sided dice."""
threes = (2 if label.twos == 1 else 3) - label.threes
return Label(N * (N + 1) - label.sum, 2 * N - label.max, 2 - label.twos, threes)
Bo: let's see what a table looks like. Here's with N = 5:
dict(tabulate_dice(all_dice(5)))
{Label(sum=12, max=4, twos=2, threes=1): [[1, 2, 2, 3, 4]], Label(sum=13, max=5, twos=2, threes=1): [[1, 2, 2, 3, 5]], Label(sum=14, max=6, twos=2, threes=1): [[1, 2, 2, 3, 6]], Label(sum=14, max=5, twos=2, threes=0): [[1, 2, 2, 4, 5]], Label(sum=15, max=6, twos=2, threes=0): [[1, 2, 2, 4, 6]], Label(sum=16, max=6, twos=2, threes=0): [[1, 2, 2, 5, 6]], Label(sum=13, max=4, twos=1, threes=2): [[1, 2, 3, 3, 4]], Label(sum=14, max=5, twos=1, threes=2): [[1, 2, 3, 3, 5]], Label(sum=15, max=6, twos=1, threes=2): [[1, 2, 3, 3, 6]], Label(sum=15, max=5, twos=1, threes=1): [[1, 2, 3, 4, 5]], Label(sum=16, max=6, twos=1, threes=1): [[1, 2, 3, 4, 6]], Label(sum=17, max=6, twos=1, threes=1): [[1, 2, 3, 5, 6]], Label(sum=16, max=5, twos=1, threes=0): [[1, 2, 4, 4, 5]], Label(sum=17, max=6, twos=1, threes=0): [[1, 2, 4, 4, 6]], Label(sum=18, max=6, twos=1, threes=0): [[1, 2, 4, 5, 6]], Label(sum=19, max=6, twos=1, threes=0): [[1, 2, 5, 5, 6]], Label(sum=14, max=4, twos=0, threes=3): [[1, 3, 3, 3, 4]], Label(sum=15, max=5, twos=0, threes=3): [[1, 3, 3, 3, 5]], Label(sum=16, max=6, twos=0, threes=3): [[1, 3, 3, 3, 6]], Label(sum=16, max=5, twos=0, threes=2): [[1, 3, 3, 4, 5]], Label(sum=17, max=6, twos=0, threes=2): [[1, 3, 3, 4, 6]], Label(sum=18, max=6, twos=0, threes=2): [[1, 3, 3, 5, 6]], Label(sum=17, max=5, twos=0, threes=1): [[1, 3, 4, 4, 5]], Label(sum=18, max=6, twos=0, threes=1): [[1, 3, 4, 4, 6]], Label(sum=19, max=6, twos=0, threes=1): [[1, 3, 4, 5, 6]], Label(sum=20, max=6, twos=0, threes=1): [[1, 3, 5, 5, 6]], Label(sum=18, max=5, twos=0, threes=0): [[1, 4, 4, 4, 5]], Label(sum=19, max=6, twos=0, threes=0): [[1, 4, 4, 4, 6]], Label(sum=20, max=6, twos=0, threes=0): [[1, 4, 4, 5, 6]], Label(sum=21, max=6, twos=0, threes=0): [[1, 4, 5, 5, 6]], Label(sum=22, max=6, twos=0, threes=0): [[1, 5, 5, 5, 6]]}
Ali: That's good! Every die has its own singleton bin, so each die will only have to be paired with one other.
Bo: Let's look at some statistics for N = 8:
N = 8
table = tabulate_dice(all_dice(N))
len(all_dice(N)), len(table), len(list(all_pairs(all_dice(N))))
(5728, 938, 1559)
Bo: This says there are 5,728 8-sided dice; they're sorted into 938 labeled bins, and all_pairs
only needs to look at 1,559 pairs, not the 32 million pairs that the old version of all_pairs
would need to consider.
Ali: That's fantastic. Why are there so few pairs to consider? Less than one pair per die?
Bo: I'm not sure. I can get a Counter of how many times we see each size bin, as we go through table
:
Counter(len(table.get(compatible_label(label1, N), [])) for label1 in table).most_common()
[(0, 603), (1, 123), (2, 54), (3, 36), (4, 28), (5, 23), (11, 15), (7, 12), (6, 12), (16, 5), (8, 5), (12, 5), (9, 4), (18, 3), (20, 3), (30, 2), (29, 2), (19, 2), (42, 1)]
Bo: OK, that was kind of dense, but what it says is:
Ali: Amazing!
Bo: I think this will be a lot faster. Let's try to go up to 9:
%time {N: sicherman(N) for N in ints(2, 9)}
CPU times: user 217 ms, sys: 1.88 ms, total: 219 ms Wall time: 218 ms
{2: [], 3: [], 4: [([1, 2, 2, 3], [1, 3, 3, 5])], 5: [], 6: [([1, 2, 2, 3, 3, 4], [1, 3, 4, 5, 6, 8])], 7: [], 8: [([1, 2, 2, 3, 3, 4, 4, 5], [1, 3, 5, 5, 7, 7, 9, 11]), ([1, 2, 2, 3, 5, 6, 6, 7], [1, 3, 3, 5, 5, 7, 7, 9]), ([1, 2, 3, 3, 4, 4, 5, 6], [1, 2, 5, 5, 6, 6, 9, 10])], 9: [([1, 2, 2, 3, 3, 3, 4, 4, 5], [1, 4, 4, 7, 7, 7, 10, 10, 13])]}
Ali: Excellent! Very fast; we got the same answers as before for 2–7, and we got three solutions for 8 and one for 9, all in a few milliseconds!
I'm confident we can go to 11:
%time sicherman(10) # here 7.22 s ([1, 2, 2, 3, 3, 4, 4, 5, 5, 6], [1, 3, 5, 6, 7, 8, 9, 10, 12, 14])]
CPU times: user 2.07 s, sys: 17.4 ms, total: 2.09 s Wall time: 2.09 s
[([1, 2, 2, 3, 3, 4, 4, 5, 5, 6], [1, 3, 5, 6, 7, 8, 9, 10, 12, 14])]
%time sicherman(11)
CPU times: user 26.4 s, sys: 299 ms, total: 26.7 s Wall time: 26.8 s
[]
Bo: Why not 12? It will take 5 minutes or so, so we can go get a coffee and come back to see the result.
%time sicherman(12)
CPU times: user 5min 18s, sys: 2.05 s, total: 5min 20s Wall time: 7min 30s
[([1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6], [1, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 18]), ([1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7], [1, 3, 5, 7, 7, 9, 9, 11, 11, 13, 15, 17]), ([1, 2, 2, 3, 3, 4, 7, 8, 8, 9, 9, 10], [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14]), ([1, 2, 2, 3, 5, 6, 6, 7, 9, 10, 10, 11], [1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13]), ([1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8], [1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16]), ([1, 2, 3, 3, 4, 5, 7, 8, 9, 9, 10, 11], [1, 2, 4, 5, 5, 6, 8, 9, 9, 10, 12, 13]), ([1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9], [1, 2, 3, 7, 7, 8, 8, 9, 9, 13, 14, 15])]
Ali: Wow! Seven distinct solutions for N = 12. Why 7?
Bo: I don't know. I can make a table summarizing the results, but I can't explain or predict them.
N Count First of Dice Pair Second of Dice Pair
― ――――― ―――――――――――――――――― ―――――――――――――――――――
2 0
3 0
4 1 [1, 2, 2, 3] [1, 3, 3, 5]
5 0
6 1 [1, 2, 2, 3, 3, 4] [1, 3, 4, 5, 6, 8]
7 0
8 3 [1, 2, 2, 3, 3, 4, 4, 5] [1, 3, 5, 5, 7, 7, 9, 11]
[1, 2, 2, 3, 5, 6, 6, 7] [1, 3, 3, 5, 5, 7, 7, 9]
[1, 2, 3, 3, 4, 4, 5, 6] [1, 2, 5, 5, 6, 6, 9, 10]
9 1 [1, 2, 2, 3, 3, 3, 4, 4, 5] [1, 4, 4, 7, 7, 7, 10, 10, 13]
10 1 [1, 2, 2, 3, 3, 4, 4, 5, 5, 6] [1, 3, 5, 6, 7, 8, 9, 10, 12, 14]
11 0
12 7 [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6] [1, 4, 5, 7, 8, 9, 10, 11, 12, 14, 15, 18]
[1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7] [1, 3, 5, 7, 7, 9, 9, 11, 11, 13, 15, 17]
[1, 2, 2, 3, 3, 4, 7, 8, 8, 9, 9, 10] [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14]
[1, 2, 2, 3, 5, 6, 6, 7, 9, 10, 10, 11] [1, 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13]
[1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8] [1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16]
[1, 2, 3, 3, 4, 5, 7, 8, 9, 9, 10, 11] [1, 2, 4, 5, 5, 6, 8, 9, 9, 10, 12, 13]
[1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9] [1, 2, 3, 7, 7, 8, 8, 9, 9, 13, 14, 15]
Bo: I think we can stop here.
Ali: I agree. But I still have some questions:
Bo: Good questions, but I think I'd rather leave those for the reader to deal with. (Hi, reader!)
Ali: Hi reader! Let us know what you find out!