Project Euler Problem #114

Problem #114 concerns partitioning a row of blocks with contiguous red sections and contiguous grey sections. The question reads:

My solution for this problem involves dynamic programming. Here’s my solution:

Solution #1: Dynamic Programming Approach

It suffices to recursively find the number of ways a row of n units can be filled such that the last square is red and the number of ways a row of n units can be filled such that the last square is grey. If the number of ways ending in a red square is a_n and the number of ways ending in a grey square is b_n, then a_n = b_(n-3)+b_(n-2) + … + b_0 and b_n = a_(n-1) + b_(n-1). Thus, with these recursions, the values of a_50 and b_50 can be determined, and the answer is simply a_50+b_50. Giving initial values of a_0, a_1, a_2, a_3, b_0, b_1, b_2, and b_3, it is easy to dynamically find the answer. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #114
 '''
 
 import time
 
 def projectEulerProblemOneHundredFourteen(n):
     rTotals = [0,0,0,1]
     gTotals = [1,1,1,1]
     sumG = sum(gTotals)
     l = len(gTotals)
     while(l<=n+1):
         rValue = sumG - gTotals[l-1]-gTotals[l-2]
         gValue = rTotals[l-1]+gTotals[l-1]
         rTotals.append(rValue)
         gTotals.append(gValue)
         sumG+=gValue
         l+=1
     return rTotals[n]+gTotals[n]
 start = time.time()
 print projectEulerProblemOneHundredFourteen(50)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 16475640049
 --- 3.40938568115e-05 seconds ---
 
 for input of n = 50.
 ''' 

And with that, we’re done. This is a great example of the powers of dynamic programing. Over 16 billion cases could be counted in under a tenth of a millisecond.

Thanks for reading! See you tomorrow.