17×17 Research: Using a binary representation to achieve greater speeds

This week I fundamentally changed how my code works to store the colored grids. Before, grids would be stored in a 2D-array of ints, with each int representing the color of that cell. Now, grids are stored as a 2D-array of binary values – with each index [row][color] representing that particular color.

Previously:

[[0,1,3,2],
 [1,2,2,2],
 [0,0,1,3],
 [3,1,3,2]]

Now:

[[0b1000, 0b0100, 0b0001, 0b0010],
 [0b0000, 0b1000, 0b0111, 0b0000],
 [0b1100, 0b0010, 0b0000, 0b0001],
 [0b0000, 0b0100, 0b0001, 0b1010]]

I do this because it allows me to do a neat trick to speed up the score calculation: I can take two rows’ color values, perform a binary AND on them, count the number of bits in the resulting value as n, and then the number of rectangles between them is n * (n-1) / 2. This removes a for loop from my previous approach, and the process is now O(n^3) instead of O(n^4).

I performed some speed tests on the new code compared to the old, and here are the results:

For a 17×17 grid, the new score calculation algorithm is over 3x faster! This is a big improvement.

Time to Solve a 15×15 Grid: New vs. Old

This boxplot shows just how much faster the new score calculation is in practice. The plots were generated from datasets of 12 samples each.