It’s been a while since I’ve taken the time to solve some Project Euler problems. I thought today would be a good day to pick it up and try solving one I had not been able to solve the last time I tried.
I’m going to speak generically about the problem because I don’t want to spoil it for anyone who may be trying to solve it. In brief, I had written a brute-force method for solving the problem, but as Project Euler so often does, they made the scale so huge that brute-force methods often fail. I turned to the internet to try to find a clue to point me in the right direction.
Sadly, one of the links I clicked didn’t have a clue, but just said “This is a Fibonacci sequence problem.”
I couldn’t unsee it, and it was clearly the way the problem was intended to be solved at scale. It felt like it was ruined, and I regretted trying to find assistance.
I decided to go do another problem without getting any aids or accidentally cheating. The problem I chose was another problem that scales quickly. The problem is stated as follows:
A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one grey square. There are exactly seventeen ways of doing this.
How many ways can a row measuring fifty units in length be filled?
I decided to start this problem with a brute force approach, even though I knew it wouldn’t scale. I wrote a recursive function to create rows filled with tiles. I started with the length of 7 they provided in the example, and I too got the correct 17.
function recurse(array){
// Find the length of the array
let s = tile_sum(array);
// If the array it too long, abort
if (s > limit)
return;
// If the array is correct size,
// check for uniqueness and record, abort
if (s == limit){
record(array);
return;
}
// Add tiles sized 1-limit and recurse
for (let t=1; t<=limit; t++){
if (t == 2) continue; // Tiles length 2 don't exist
// Add a single tile spacer in if we are adding a red tile
if (array[array.length-1] != 1 && t > 1)
array.push(1);
// Add tile to the array and recurse
recurse(array.slice().concat([t]));
}
}
I slowly increased the length by one to make sure nothing would break in my algorithm. I also noted the numbers as it computed them.
f(7) = 17
f(8) = 27
f(9) = 42
f(10) = 72
I thought that having learned my lesson from the previous problem I might have some luck by identifying this series of numbers. I went to the OEIS (Online Encyclopedia of Integer Sequences) and entered in these integers.
Spoilers below…
The OEIS search provided a result! It was A004695, the Fibonacci sequence… (but halved). Sure enough, computing the correct number in the Fibonacci sequence, and halving it yielded the correct answer for this problem.
I can’t believe two problems in a row ended up having the same shortcut. I wonder if the next one will as well…