Project Euler 189 - Tri-colouring a triangular grid

Official link:

Thought Process

This problem was a roller coaster for me.

I wrote 2 recursive functions

  1. gen_string(mask, pos, prev)

    • It would take a string, mask, and return all the possible strings for the next row

    • For example gen_string("R", 0, "") = ['RGR', 'RGB', 'RBR', 'RBG', 'GBR', 'GBG', 'BGR', 'BGB']

  2. compute(row, mask)

    • This would take a the first row, so just "R", "G", or "B" and compute all the possible triangle configurations with this first row

    • I generate all possible configurations, x, for the next row using gen_string(mask, 0, "")

    • Then I add compute(row - 1, x) to a running total

    • When I reach the 2nd last row, I return all the possibilities using gen_string

  3. The final answer is 3*compute(7, "R") because Red, Green, or Blue is the same, and we are counting down to 0

What was very interesting is with memoization on both functions I could not get the final answer, I waited for one hour and got nothing, but I could solve for the first 7 rows in around 30 seconds, then by chance I accidentally stopped memoizing gen_string and my code dropped to 5 seconds for the first 7 rows.

Needless to say I was stunned and attempted the final answer and it worked it just about 60 seconds!

I suspect as the number got larger I was just using too much memory, and my computer could not handle it

Interactive Code

Enter a number (yourinput)

Code will output the number of distinct valid colourings given yourinput number of rows of the triangle