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