One puzzle, two solutions

Introduction

Today, I wanted to switch back to a lighter subject. Therefore I decided to have a look at my favorite Project Euler website.

I picked the problem 116 as I have not tried to solve it yet. Interestingly, it turned out that there are two ways to approach this puzzle, so I thought to share them here.

The post was written under Julia 1.10.0.

The puzzle

The Project Euler puzzle 116 can be briefly stated as follows:

Given a row of 50 grey squares is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four). How many different ways can the grey tiles be replaced if colours cannot be mixed and at least one coloured tile must be used?

(If you want to see some visual examples of valid tilings, I encourage you to visit the puzzle 116 page.)

The first approach

When we think of this problem, it is natural to generalize it. By C(n, d) we can define the number of ways that n gray squares can be replaced with tiles of length d. Then the solution to our problem is C(n, 2) + C(n, 3) + C(n, 4). So let us focus on computing C(n, d) (assuming d is positive).

The first approach is to ask how many tiles of length d can be put. There must be at least 1, and we cannot put more than n ÷ d (here I use the ÷ notation taken from Julia that denotes integer division; in other words the integer part of n / d).

So now assume that we want to put i blocks of length d (assuming i is valid). In how many ways can we do it. Well, we put i long blocks and we are left with n - d*i gray blocks. In total we have i + (n - d*i) blocks. You can then think of it as you have that many slots from which you need pick i slots to put the long blocks. The number of ways you can do it is given by the value of binomial coefficient. In Julia notation it is: binomial(BigInt(i + (n - d*i)), BigInt(i)).

Now you might ask why I put the BigInt wrapper around the passed numbers? The reason is that binomial coefficient gets large pretty quickly, so I want to make sure I will not have issues with integer overflow.

Given these considerations the first function that produces C(n, d) can be defined as:

function C1(n::Integer, d::Integer)
    @assert d > 0 && n >= 0
    return sum(i -> binomial(BigInt(i + (n - d*i)), BigInt(i)), 1:n ÷ d; init=big"0")
end

Note that I use the init=big"0" initialization statement in the sum to ensure the correct handling of the cases when n < d when we are given an empty collection to sum over.

The second approach

However, there is a different way how we can think of computing C(n, d).

Assume we know the values of C(n, d) for values of n smaller than the requested one.

We look at the last tile in our row.

If it is empty, then we are down to n-1 tiles to be filled. This can be done in C(n-1, d) ways (remember that this value takes care of the fact that at least one block of length d has to be used).

But what if the last tile in our row is filled with a block of length d? Then we have two options. Either all other blocks are left gray (which gives us 1 combination) or we are left with n-d tiles that are filled with at least one block of length d. The second value is exactly C(n-d, d).

In summary we get that C(n, d) = C(n-1, d) + C(n-d, d) + 1.

This formula assumes n is at least d. But clearly for n < d we have 0 ways to arrange the blocks.

Let us write down the code that performs the required computation:

function C2(n::Integer, d::Integer)
    @assert d > 0 && n >= 0
    npos = Dict{Int,BigInt}(i => 0 for i in 0:d-1)
    for j in d:n
        npos[j] = npos[j-1] + npos[j-d] + 1
    end
    return npos[n]
end

Note in the code that I used the npos dictionary to flexibly allow for any potential integer values of n. The dictionary has Dict{Int,BigInt} type, again, to ensure that the results of the computations are stored correctly even if they are large.

Testing

Now we have two functions C1 and C2 that look completely differently. Do they produce the same results. Let us check:

julia> using Test

julia> @testset "test C1 and C2 equality" begin
           for n in 0:200, d in 1:20
               @test C1(n, d) == C2(n, d)
           end
       end;
Test Summary:           | Pass  Total  Time
test C1 and C2 equality | 4020   4020  0.9s

Indeed we see that both C1 and C2 functions produce the same results.

To convince ourselves that using arbitrary precision integers was indeed needed let us check some example values of the functions:

julia> C1(200, 2)
453973694165307953197296969697410619233825

julia> C2(200, 2)
453973694165307953197296969697410619233825

julia> typemax(Int)
9223372036854775807

Indeed, if we were not careful, we would have an integer overflow issue.

Conclusions

As usual I will not show the value of the solution to the problem to encourage you to run the code yourself. You can get it by executing either sum(d -> C1(50, d), 2:4) or sum(d -> C2(50, d), 2:4). (We have just checked that the value produced in both cases is the same).