June 2014 IBM Research Ponder This Challenge

Every month, IBM Research hosts the Ponder This challenge, which usually can be solved with pure mathematics but is often easier if combined with a little programming.

I solved the June, 2014 Ponder This challenge, which was:

Design 25 cubes so that each cube's six faces display integer numbers in the range 0,1,...,31 such that:

1. On each cube, all the numbers are different
2. Any given two cubes share exactly one common number

Please give your answer as 25 lines of six numbers.

Bonus question: Use as small a range of numbers as possible.

Now that the challenge is over and the official solution has been posted, I wanted to share my slightly different solution.

The problem immediately reminded me of combinatorial design. Designs are related to projective planes, which the official solution used. They’re also related to codes, which is the approach I used.

Suppose we encode each cube as a binary vector of length N, where \(N \le 32\) is the number of digits needed for a solution. Each position of the vector will be 1 if the digit appears on a face of the cube, and 0 otherwise.

Each cube is then a vector with Hamming weight 6 because there are 6 faces on the cube, each with a distinct digit. The Hamming distance between any pair of cube vectors is 10, because the cubes have exactly one digit in common: They are equal in that position, different in the other 5 digit positions (where the cube with that digit has a 1 and the other cube has a 0) for a total of 10 positions where they differ, and equal in all the other positions (where they are both 0).

Consequently, a solution to this challenge is equivalent to constructing a constant-weight code with weight 6, distance 10, and at least 25 codewords.

The maximum number of codewords in such a code is written \(A(n, d, w)\), so we want to find the smallest n such that \(A(n, 10, 6) \ge 25\) and then give an example of such a code with exactly 25 codewords.

According to this research page by Andries E. Brouwer, there is a code such that \(A(30,10,6) = 25\). Thus, there exists a solution with 30 digits.

The superscript s indicates that this corresponds to a shortened (31,10,6) or (31,11,6) code, and links to another table. At this point, I became stuck in the theory, and spent some time exploring some Galois field structures (including working through this 1979 paper by Graham & Sloane), before realizing that I have forgotton most of the coding theory I learned in a EE/CS/MA class at Caltech over 20 years ago.

I then switched over to a combination of manual reasoning and software. I started out by designing the first five codewords by hand, so that each word has weight 6 and each pair of words has distance 10:

After some trial-and-error, I managed to extend this to:

where the question marks indicate unknown values. At this point, the search space was small enough to allow a quick brute-force software approach to find the remaining unknown values:

# Encode the words found so far:
c=[0b111110000000000000000000010000,
0b000001111100000000000000010000,
0b000000000011111000000000010000,
0b000000000000000111110000010000,
0b000000000000000000001111110000,
#
0b100001000010000100001000001000,
0b010000100001000010000100001000,
0b001000010000100001000010001000,
0b000100001000010000100001001000,
0b000010000100001000010000101000,
#
0b100000100000100000100000100100,
0b010000010000010000011000000100,
0b001000001000001100000100000100,
0b000100000110000010000010000100,
0b000011000001000001000001000100]
from itertools import product
def hamming_weight(x):
    """Calculate the Hamming weight of a number."""
    x -= (x >> 1) & 0x5555555555555555
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    return ((x * 0x0101010101010101) & 0xffffffffffffffff ) >> 56
def hamming_distance(x,y):
    """Calculate the Hamming distance between two binary vectors."""
    return hamming_weight(x^y)
def brute_force(code, bottom):
    """Brute-force search the remainder of the solution."""
    for (h,i,j,k,l) in product([1,2,4,8,16], repeat=5):
        t = (i | (j | (k | (l | h<<5)<<5)<<5)<<5)<<5 | bottom
        keep = True
        for w in code:
            if (hamming_distance(w, t)!= 10):
                keep = False
                break
        if (keep):
            code.append(t)
    return code
extended = brute_force(c[:], 2)
solution = brute_force(extended, 1)

And finally, convert that solution into the required submission format:

for v in solution:
    faces = []
    for i in range(0,30):
        if (v & (1<<i)):
            faces.append(i)
    print " ".join(str(x) for x in faces)

4 25 26 27 28 29
4 20 21 22 23 24
4 15 16 17 18 19
4 10 11 12 13 14
4 5 6 7 8 9
3 9 14 19 24 29
3 8 13 18 23 28
3 7 12 17 22 27
3 6 11 16 21 26
3 5 10 15 20 25
2 5 11 17 23 29
2 9 10 16 22 28
2 8 14 15 21 27
2 7 13 19 20 26
2 6 12 18 24 25
1 6 13 15 22 29
1 5 12 19 21 28
1 9 11 18 20 27
1 8 10 17 24 26
1 7 14 16 23 25
0 7 10 18 21 29
0 6 14 17 20 28
0 5 13 16 24 27
0 9 12 15 23 26
0 8 11 19 22 25