Project Euler 189 - Tri-colouring a triangular grid
Official link: https://projecteuler.net/problem=189
This problem was a roller coaster for me.
I wrote 2 recursive functions
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']
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
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
Enter a number (yourinput)
Code will output the number of distinct valid colourings given yourinput number of rows of the triangle