Project Euler Problem #215

My solution is seperated into three distinct steps, each one abstrated quite well in the main() function.

1. Generate all the possible wall rows.  Start with all 2s, then replace them one by one with 3 blocks until they become longer than 32 units, then replace the next one.  This is done in the gen_rows() function.
2. Interlink all the possible rows.  Once a list of all the possible rows is generated, iterate through each possible pair and check to see if they can stack.  If they can, add the pointer to eachother's list of possible rows above or below each.
3. Use the list of possible stack mates from step 2 to build a 10 row high wall.  Itterating through all the rows for the bottom row, then recursively go through the stored list of rows to stack on top of this first row, etc.  I cached the result of each row in each height of the wall, since a specific row in the 3rd row will always have the same number of possible walls built upon it, but not if it happens to be in the 4th row.

The greatest shortfall of my solution that could be changed to improve runtime is that it stores the location of each crack as ints in an int[].  A significantly faster way to handle where the cracks are is to store the cracks in a 32 bit bitmap, then to check for overlapping cracks, simply bitwise and the two rows together (if (a&b != 0), they can't stack)

Runtime: 3.608 seconds

PE215_c

This solution uses the linked list library I wrote.

Return to list of solutions