Project Euler 126: Exploring the number of cubes required to cover every visible face on a cuboid.

Problem 126 of Project Euler is a really awesome geometric challenge. It reads

The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.

If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.

We shall define C(n) to represent the number of cuboids that contain n cubes in one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118) = 8.

It turns out that 154 is the least value of n for which C(n) = 10.

Find the least value of n for which C(n) = 1000.

Deducing a formula for each layer

The first thing we should do is to figure out if we can deduce a formula to calculate the number of cubes needed to cover the previous layer.

If we have a cuboid with side lengths x,y,z then the nth will need be given by the function  C(x,y,z,n).

First layer

We have a cuboid with side lengths x,y,z then the first layer will need

C(x,y,z,1) = 2(xy + yz  x*z)

The beautiful mark up shows where we get each of the terms from.  So for the cuboid x=3, y=2, z= 1. We have that xy is the red part, yz is the green/yellow part and the blue part is x*z. And then we need all of this twice in order to cover the faces that turns away from us as well.

Second layer

I have tried to make a mark up of the second layer covering as well

The red part can be calculated as the first layer.

blue + green + black which are given as (x+y+z). And we need those 4 times in order to cover both front/back and upper/lower part.

C(x,y,z,2) = C(x,y,z,1) + 4(x+y+z)

Third layer

I have tried to make a third layer, it was a tad difficult, but I hope you can see what I mean

We can see we have an additional blue and green phase as well as 2 extra black phases

That means we can write C(x,y,z,3) = C(x,y,z,1) + 4(x+y+z )2 + 4.
Which can be generalised to  C(x,y,z,n) = 2(x
y + yz +  xz) + 4(x+y+z + n -2 )*(n-1)

This function can also be used for at least the first three layers.

Checking the function

Without being completely certain that this formula will hold for every layer, let us check it for the example given in the problem formulation

C(3,2,1,1) = 2(32 + 21 + 31) + 4(3+2+1+1-2)(1-1) = 22

C(3,2,1,2) = 2(32 + 21 + 31) + 4(3+2+1+2-2)(2-1) = 46

C(3,2,1,3) = 2(32 + 21 + 31) + 4(3+2+1+3-2)(3-1) = 78

C(3,2,1,4) = 2(32 + 21 + 31) + 4(3+2+1+4-2)(4-1) = 118

So at least it works for the example we have been given. My gut feeling also tells me that me that this is correct.

Finding a brute force solution

Now that we have a way to calculate the number of cubes in a layer it is time to find the minimal solution for C(?) = 1000.

I have taken a brute force approach to this. I have assumed that the solution is less than 30000. Furthermore  I will only check solutions where z ≤  y ≤ x.  So this is just a matter of adding layers to a cuboid until we reach the limit we have defined. This can be implemented as

int limit = 30000;
int[] count = new int[limit + 1];
for (int z = 1; Cubes(z, z, z, 1) <= limit; ++z)
    for (int y = z; Cubes(z, y, z, 1) <= limit; ++y)
        for (int x = y; Cubes(z, y, x, 1) <= limit; ++x)
            for (int n = 1; Cubes(z, y, x, n) <= limit; ++n) 
                count[Cubes(z, y, x, n)]++; 

with cubes being

private int Cubes(int x, int y, int z, int n) {
    return 2 * (x * y + y * z + x * z ) + 4* (x + y + z + n - 2) * (n - 1);
}

I think you can see where this is going. We are just calculating all cuboid layerings where the total is less than 30.000 and adding them in an array. I can do that in less than 25ms.

With the result being

Minimal solution C(18522)=1000

Since I haven’t found a really clever solution to this, I am quite curious to hear your solution to this problem.
You can find my source code right here.

Posted by Kristian

9 comments

Jean-Marie Hachey

Hi Kristian,

You wrote :

[…]
« Which can be generalised to C(x,y,z,n) = 2(x*y + y*z x*z) + 4(x+y+z + n -2 )*(n-1)
This function can also be used for at least the first three layers. »
[…]

Table 1 just confirms your « feeling » :

___

Table 1
Project Euler 126 (cubes)
Basic cuboid: 6 cubes (3x2x1)
C(x,y,z,n) = 2(x*y + y*z + x*z) + 4(x+y+z + n -2 )*(n-1) [Eqn.1] :

http://img259.imageshack.us/img259/5082/table1pe126f.jpg

However, results in Table 1 show differences between the two methods of calculation (Eqn [1] and algo [2]).

In order to get results for higher values of n, the value of « int limit » in the algorithm [2] was increased from 30 000 to 5 000 000 : no output after 60 sec.
(As predicted, with an « int limit » of 30000, the answer (18522) for n=1000 is obtained;
t= 639 ms).

___

Typos :
Plus signs are missing between y*z and x*z :

___

I have tested the general applicability of your proposed [Eqn1] with success for the few cases examined. More comments to come on this matter.

Your approach to this problem is highly appreciated.

Jean-Marie

Hi Jean-Marie

I have fixed the typo. Regarding the algorithm output, I get the same output as you get from the equation, afterall those should be the same anyway. So I am not sure I understand where the problem is with that.

/Kristian

Jean-Marie Hachey

Hi Kristian,

Thank you for your answer.

Maybe I missed something with your algorithm.

Here is the way I used it to generate the values reported in my previous comment.

These results were obtained by changing the variable 1000 by successive values of n.

The variables (0, 1, 2, …, 10, 1000) were successively input in this line :
Array.IndexOf(count,1000)]

The justification for that general formula is easier to see if you start drawing layers on a 2x2x2 cuboid. Using z = 1 just confuses which 1’s are z’s, which are (n-2)’s, and which are always 1’s.

Layered on top of the six faces of the cuboid are faces of the same area as the faces, one cube thick (your red phases).
Total cubes: (xy+xy+xz+Xz+yz+YZ).

Layered on top of each of the 12 edges of the cuboid are 1×1 strips of the same length as the edge (your blue, green phases and the part of the black phase that is between reds) . Each layer must cover the previous layer, so the number of such strips increases by 1 each layer.
Total cubes: (n-1) * (x+x+x+x+y+y+y+y+z+z+z+z)

Layered on top of each of 8 the corners of the cuboid is a triangle of cubes that fills in the space between the edges. (the uppermost black cube in your 3rd layer drawing, it becomes 1+2 in the 4th layer)
Total cubes: 8 * the (n-2)th triangular number, or 8 * (n-1)(n-2)/2.

Which all add up to the general formula:
cubes = 2(ab+ac+bc) + 4(n-1)(x+y+z) + 4(n-1)(n-2)

Note that each layer is essentially 2-dimensional because it has a 1-cube width. The sections covering the cuboid’s faces don’t grow because they’re already 2D. The sections covering edges grow linearly because the edges are 1D. And the sections covering 0D vertices grow as n^2 because both dimensions need to come from n.

Jean-Marie Hachey

Using the general formula presented in the above article :
C(x,y,z,n) = 2(x*y + y*z + x*z) + 4(x+y+z + n -2 )*(n-1)
and a spreadsheet (here Excel).
The following results are obtained :

C(22)=2 :
C(3,2,1,1)=22
C(5,1,1,1)=22

C(46)=4 :
C(3,2,1,2)=46
C(5,3,1,1)=46
C(7,2,1,1)=46
C(11,1,1,1)=46

C(78)=5 :
C(1,2,3,3)=78
C(1,3,9,1)=78
C(1,4,7,1,)=78
C(3,3,5,1)=78
C(19,1,1,1)=78

C(118)=8 :
C(3,2,1,4)=118
C(7,5,2,1)=118
C(8,3,1,2)=118
C(9,5,1,1)=118
C(11,4,1,1)=118
C(14,3,1,1)=118
C(19,2,1,1)=118
C(29,1,1,1)=118

C(154)=10 :
C(4,3,3,3)=154
C(5,2,1,4)=154
C(7,3,3,2)=154
C(7,7,2,1)=154
C(9,4,1,2)=154
C(11,3,1,2)=154
C(12,5,1,1)=154
C(18,1,1,2)=154
C(25,2,1,1)=154
C(38,1,1,1)=154

Jean-Marie Hachey

Adding layers to a cube…

C(x,y,z,n)
C(1,1,1,1) = 6
C(1,1,1,2) = 18
C(1,1,1,3) = 38
C(1,1,1,4) = 66
C(1,1,1,5) = 102
C(1,1,1,6) = 146
C(1,1,1,7) = 198
C(1,1,1,8) = 258
C(1,1,1,9) = 326
C(1,1,1,10) = 402
C(1,1,1,100) = 40002

The same sequence has been found elsewhere.
A005899 Number of points on surface of octahedron: a(0) = 1; for n>0, ( or ) a(n) = 4n^2 + 2, coordination sequence for cubic lattice.
(Formerly M4115)
https://oeis.org/A005899

You’ve made a mistake in the sentence “That means we can write C(x,y,z,3) = C(x,y,z,1) + 4(x+y+z )*2 + 4.” This should be +8 instead of +4, because:

C(1,2,3,1) = 22 as you’ve proved and is provided in the challenge description, and 4*(1+2+3)*2 = 8*(1+2+3) = 48
22+48 = 70, and we’re expecting 78. So the +4 should be +8.

The rest of your description is correct. There are indeed two more black boxes, but this applies to all four ‘corners’ (hence the 8). And you’re derived formula is also correct, as you’ve proved. Just the +4 is incorrect.

Greetings,
Kevin

Carl J Appellof

I spent a lot of time on this problem, and even wrote “Cuboid” and “Cubesolid” classes with operations to build up layers based on “exposed faces”. After a while I got the pattern and used finite differences to come up with the same polynomial you have for the number of cubes in a given layer (although my “n” was 0-based.) Thanks for adding the limit test to the nested loops. That was the key piece I was missing to make the solution go fast. Using fixed limits make my first try take about 20000 ms. After making your modifications, it was down to about 20 ms, a reduction of 1000x !

Fred Schneider

I spent a few hours on this today and solved it before checking here. I couldn’t get the formula for a cuboid with all sides > 1 but I did find a recurrence relation involving a few variables.

My breakthrough was imagining that I was staring straight down at the stelated cuboid, with the aerial view spreading out progressively.

Say we start with 1 x 1 x b. This is a view of the first few steps staring straight down.

Keep a running total of the double sum of the “cross sections”
Each new total = that running total + the current cross section * c
Each cover = total – prev total

Level 0
x

Level 1
0
0x0
0

Level 2
x
x0x
x0x0
x0x
x

void compute(int a, int b, int c) {
int lastTotal = a * b * c;
int lastCrossSec = a * b;
int lastCrossSub = 2 * lastCrossSec;
int lvl = 0;
int planePerim = 2 * (a + b);

while (true) {
lvl++;
int crossSec = lastCrossSec + (planePerim + (lvl – 1) * 4);
int total = lastCrossSub + c * crossSec;
int cover = total – lastTotal;
if (cover > MAX_COVER) return;
solCt[cover]++;

lastCrossSub += 2 * crossSec;
lastCrossSec = crossSec;
lastTotal = total;

}
}

Leave a Reply