# Thought Process

This problem was a roller coaster for me.

I wrote 2 recursive functions

• 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

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