Project Euler 116: Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Problem 116 of Project Euler reads

A row of five black square tiles 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).

If red tiles are chosen there are exactly seven ways this can be done.

If green tiles are chosen there are three ways.

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the black tiles in a row measuring five units in length.

How many different ways can the black tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?

Analysis of the differences

Apart from the added color this is not very different from problem 114. So we probably still want to solve it with a recursive function. However, we can’t directly reuse the one we have.  So lets look into the differences.

1. There are no blacks between blocks. That one should be easy to correct
2. The blocks have to be the same length. So if we have started with red blocks we need to only use red blocks. The easiest thing to do then is probably to design a function that keeps the block length constant and then call it with block length 2, 3 and 4.
3. Only black blocks does not count anymore.

Implementation

Based on that I have implemented a function G(m,n) which does take these three points into account. It looks like this in C#

private long G(int m, int n) {
long solutions = 0;

//we can't fill out more
if (n > m) return solutions;

if (cache[m] != 0) return cache[m];
for (int startpos = 0; startpos <= m-n; startpos++) {
solutions++; //We can fill in a block
solutions += G(m - startpos - n, n);
}

cache[m] = solutions;
return solutions;
}

In order to take point 1 into account. I don’t subtract one in line 10.  That means I don’t add an “empty” block to all calls.

In order to deal with point 2. I have removed the variable block size length. So now we have to call it three times, but the issue has been dealt with.

Point 3 have been dealt with in the sense that I don’t automatically have 1 solution for each call. I only increment the solutions if I can actually add a block. That way I avoid the all black blocks.

All we have to do now is to call the recursive function and print the result

long solutions = 0;
int m = 50;
int nmin = 2;
int nmax = 4;
for(int i = nmin; i <= nmax; i++){
cache = new long[m + 1];
solutions += G(m, i);
}

So there we go. This gives us the following solution in less than 0.2ms

you can fill a row of length 50 in 20492570929 ways

Wrapping up

I am aware that there are other solutions out there, and I would love to get a full explanation to them. However, I think this approach works really well for this kind of problem, and I am really proud of myself to have implemented a recursive method successfully. So I will not go into more details with other solutions unless you bring it up.

The source code for this solution can be found here.

Posted by Kristian

Hi, great solution. I was stuck here (I am not good at recursion) so I look at the problem description you wrote. I developed the identical method apart from little change in the recursive function. I simply get rid of subtraction, but not a great speed improvment.

Code C++

#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <string>
#include <fstream>

using namespace std;
typedef long long Long;

Long mem[100];

Long recurse(int n, int p)
{
if(n < p)
return 0;

if(mem[n] != 0)
return mem[n];

Long countSol = 0;
for(int i = n-p; i>=0; i--)
countSol += recurse(i, p) + 1;

//cout<<n<<'\t'<<countSol<<endl;
mem[n] = countSol;
return countSol;
}

int main()
{

time_t start = clock();
ofstream file("PE.txt");

Long sol = 0;
int i = 2;
while(i <= 4)
{
sol += recurse(50, i);
i++;

for(int j = 0; j<55; j++)
mem[j] = 0;
}

cout<<sol<<endl;
file<<sol<<endl;
file<<"Program last:\t"<<(clock() - start)<<endl;
file.close();
return 0;

}
Kristian

I doubt that it will make any kind of noticeable speed change to avoid subtraction. After all computers are pretty good at addition and subtraction 🙂

Jean-Marie Hachey

Euler Project
Problem 116

A derivative … 🙂

Do you agree with all the values listed in this table ?

http://imageshack.us/a/img145/43/epprobl116.jpg

___

Five values are missing in this table.
Can you complete it ?

Dav2.71828

Code reuse is always a good idea, but after Bjarki suggested learning Haskell in one of the previous posts I came up with a different solution.
It’s based on the idea that you can kind of treat a colored block as having length 1 and using the binomial equation to calculate the number of different options with 1,2,3,… colored blocks

nCr :: (Integral x)=> x->x->x
nCr n r = (product [max r (n-r) +1.. n]) `div` (product [1..min r (n-r)])

p116 :: (Integral x)=> x->x
p116 total = sum (map boxes [2,3,4])
where
boxes len = sum [nCr a b|(b,a)<-zip [1..total] [total-(len-1),total-2*(len-1)..],b<=a]

Shanecruise

Only a little different from yours
Initialized solutions=1
no need for solutions++
and G(m,i)-1 gives the right ans

BabakSairafi

Time=0 for each method

Method1:f(n,k)=n-k+1+Sigma f(n-k-i,k) from i=0 to n-2k

class Program
{
static long func1(int n, int k)
{
long[] f = new long[n + 1];
f[0] = f[1] = 0;
for (int j = 2; j <= n; j++)
{
f[j] = j – k + 1;
for (int h = 0; h n / 2)
k = n – k;
long s = 1;
for (int i = n; i >= n – k + 1; i–)
s = s * i / (n + 1 – i);
return s;
}

static long func2(int n, int k)
{
long s = 0;
for (int i = 1; i <= n / k; i++)
s += comb(n – i * (k – 1), i);
return s;
}

static void Main(string[] args)
{
long a;
a = func2(50, 2) + func2(50, 3) + func2(50, 4);
Console.WriteLine(a);
}
}

BabakSairafi

Time=0 for each method

Method1:f(n,k)=n-k+1+Sigma f(n-k-i,k) from i=0 to n-2k

class Program
{
static long func1(int n, int k)
{
long[] f = new long[n + 1];
f[0] = f[1] = 0;
for (int j = 2; j <= n; j++)
{
f[j] = j – k + 1;
for (int h = 0; h <= j – 2 * k; h++)
f[j] += f[j – k – h];
}
return f[n];
}

static void Main(string[] args)
{
long a;
a = func1(50, 2) + func1(50, 3) + func1(50, 4);
Console.WriteLine(a);
}
}

Method2:f(n,k)=sigma combination(n-i(k-1),i) from i=1 to [n/k]

class Program
{

static long comb(int n, int k)
{
if (k > n / 2)
k = n – k;
long s = 1;
for (int i = n; i >= n – k + 1; i–)
s = s * i / (n + 1 – i);
return s;
}

static long func2(int n, int k)
{
long s = 0;
for (int i = 1; i <= n / k; i++)
s += comb(n – i * (k – 1), i);
return s;
}

static void Main(string[] args)
{
long a;
a = func2(50, 2) + func2(50, 3) + func2(50, 4);
Console.WriteLine(a);
}
}

YesIam

I used the same idea as Dav2.71828 where you threat a colored block as just a block of length 1. Instead of Haskell I used Python:

from misc import nCr

color_lengths = [2, 3, 4]

n = 50

print sum(sum(nCr(n + i * (1 - l), i) for i in range(1, n / l + 1)) for l in color_lengths)