Problem #115 concerns separating rows of blocks into red sections and black sections. The question reads:
Project Euler Problem 115: Counting block combinations II NOTE: This is a more difficult version of Problem 114. A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. Let the fill-count function, F(m, n), represent the number of ways that a row can be filled. For example, F(3, 29) = 673135 and F(3, 30) = 1089155. That is, for m = 3, it can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million. In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million. For m = 50, find the least value of n for which the fill-count function first exceeds one million.
My solution is almost identical to my solution for Problem #114. Therefore, I will not repeat the details for the recursions that I used. Here’s my solution:
Solution #1: Dynamic Programming Approach
As I did in Problem #114, we separate the recursion into tilings that end in a red square and tilings that end in a grey square. The recursions are nearly identical to the ones in Problem #114, and the initial conditions can easily be extended to account for the larger minimal red tilings. From this point, it is only a matter of applying the recursion repeatedly until a value with over 1000000 different tilings is obtained. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Dynamic Approach to Project Euler Problem #115
'''
import time
def projectEulerProblemOneHundredFifteen(m,n):
rTotals = [0]*m
rTotals.append(1)
gTotals = [1]*(m+1)
sumG = sum(gTotals)
l = len(gTotals)
v = rTotals[l-1]+gTotals[l-1]
while(v<=n):
rValue = sumG
for x in range(1,m):
rValue-=gTotals[l-x]
gValue = v
rTotals.append(rValue)
gTotals.append(gValue)
sumG+=gValue
l+=1
v = rTotals[l-1]+gTotals[l-1]
return l-1
start = time.time()
print projectEulerProblemOneHundredFifteen(50, 1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
168
--- 0.000357866287231 seconds ---
for input of m = 50, n = 1000000.
'''
And with that, we’re done. Once again, dynamic programming proves to be invaluable at solving recursive problems.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 