// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 115 Solution

Project Euler 115 Solution

Project Euler 115: Fill an empty row with blocks, a minimum length of 50 units, until the size of the row exceeds 1,000,000 units.


Problem Description

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.

Analysis

This problem could easily be solved by playing with the interactive solution on the Problem 114 page. Just change m to 50 and play with n until it first exceeeds one million. The value of n won’t be very big because we start m at 50.

Again, i opted out of a recursive solution or generating functions because, after a while, dynamic programming becomes so intuitive for solving counting problems.

Also, I didn’t bother with an F() function as I wanted to simply make a few changes to the previous problem and finish it. Instead of a fixed-size array, I dynamically increase it as necessary since I have no clue as to how big it should be to start with.

Well, actually, I do have a clue, but not if the parameters of this problem were changed.

Project Euler 115 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 115 Solution Python 2.7 source.

Afterthoughts

Project Euler 115 Solution last updated

Discussion

No comments yet.

Post a comment