John Stechschulte

IBM has a monthly Ponder this challenge. The December challenge was straightforward to solve using Go. My code is on GitHub.

Read the challenge page for the details of the problem. If we call the row and column sums of a bit matrix its “signature,” my solution simply iterates over all matrices of a given size, calculates the signature of each, and counts the number of times it has seen each signature in a map. Go’s advantage over C in this problem is native hash tables (the map type).

Since the problem limited the matrix to 50 bits, it was simple to represent it in a 64-bit word. To efficiently calculate row counts, I precomputed population counts for all bytes. For columns, I created a table where each byte is expanded to a 64-bit word by inserting seven 0s between each bit, so that I can do pocketed addition for the columns.

My original plan was to investigate small cases by hand, and then try to generalize the pattern so that I could handcraft a solution. Since the problem was limited to 50 bit matrices, I suspected the smallest solution would be ~40 bits, and therefore too big for my laptop to find (by counting 2^40 matrices). However, the smallest solutions are just 24 bits (4x6), and my program runs in 5 seconds. I also found the 25 bit solutions (in about 10 seconds).

One final curious note. I noticed that many of the solutions looked similar. At least for the two matrix sizes that I calculated, all the solutions are essentially the same. To convert one to another, apply a row permutation and column permutation, and possibly invert the entire matrix. If we consider these solutions equivalent, I’m curious how large a matrix would be required to generate two distinct solutions.