## Project Euler 90: An unexpected way of using two cubes to make a square.

#### Problem Description

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}

{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

#### Analysis

**Let’s reword this problem a bit:**

Take two cubes and inscribe every side with six numbers from the set {0-9} in such a way that when they are placed side-by-side they show every perfect square from the set {01, 04, 09, 16, 25, 36, 49, 64, 81}.

As an example, one possibility could be {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other. The cubes can be positioned in any way that forms the perfect square. Also, a cube with the combination {9, 8, 7, 0, 5, 6} is the same as (NOT distinct from) another cube with the same numbers but in a different order {0, 5, 6, 7, 8, 9}.

To make the problem a bit more challenging, let’s say that you can turn a cube upside down so the 6 could serve as a 9. This makes the numbers to inscribe on the cube as {0, 1, 2, 3, 4, 5, 6, 7, 8, 6}.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

**To solve this problem we are going to use:**

*combinations*function from itertools*enumerate*function*all*function- list comprehensions with a conditional

**Step-by-step analysis:**

Firstly, we create a list of desired outcomes that include (0,1), (0,4), (0,6)^{*}, (1,6), (2,5), (3,6), (4,6)^{*}, and (8,1). Note that (6,4) is missing because the cubes can be set side-by-side in either way so (4,6) is the same as (6,4).

^{*}(the 6 can be flipped for a 9)

Secondly, we build a list of tuples (which didn’t need to be tuples, but they looked cleaner in source) for all the possibilities of 10 numbers chosen 6 at a time. This is _{10}C_{6} or 210 possible combinations.

As this may be confusing, here is a simplified version to look at using 4 numbers chosen 2 at a time (_{4}C_{2} or 6 possible combinations):

```
>>> from itertools import combinations
>>> cube = list(combinations([0,1,2,3], 2))
>>> cube
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
>>>
```

Notice that the combination function produces a list of tuples for each iteration.

We’ll hold off on the valid function for a moment and focus on the double list comprehension.

The *enumerate* function is a cleaner and more efficient way of replacing:

```
for n in range(len(my_list)):
print n, my_list[n]
```

with:

```
for n, item in enumerate(my_list):
print n, item
```

So, *enumerate* returns both the index and the element. This is useful for comparing every item in a list to every other item in the list. Here’s an example continuing from above:

```
for i,c1 in enumerate(cube):
print 'first loop',i,c1
for c2 in cube[:i]:
print " second loop", i,c2
```

**Output:**

first loop 0 (0, 1) first loop 1 (0, 2) second loop 1 (0, 1) first loop 2 (0, 3) second loop 2 (0, 1) second loop 2 (0, 2) first loop 3 (1, 2) second loop 3 (0, 1) second loop 3 (0, 2) second loop 3 (0, 3) first loop 4 (1, 3) second loop 4 (0, 1) second loop 4 (0, 2) second loop 4 (0, 3) second loop 4 (1, 2) first loop 5 (2, 3) second loop 5 (0, 1) second loop 5 (0, 2) second loop 5 (0, 3) second loop 5 (1, 2) second loop 5 (1, 3)

Thirdly, the valid function simply returns True for those cases that a square can be made from a perspective set of two cubes in either direction. The *all* function will return **True** only if all the generated list items are **True**.

Lastly, all that’s left to do is count valid combinations. Duplicates are ignored inherently by only checking a possible cube against all other combinations that come before it. That’s why we use *cube*[:*i*] in the second loop and not just *cube*. Which is also why *enumerate* is so nice, because it gives us the index, *i*.

#### Project Euler 90 Solution

Runs < 0.750 seconds in Python 2.7.```
from itertools import combinations
squares = [(0,1), (0,4), (0,6), (1,6), (2,5), (3,6), (4,6), (8,1)]
cube = list(combinations([0,1,2,3,4,5,6,7,8,6], 6))
def valid(c1, c2):
return all(x in c1 and y in c2 or x in c2 and y in c1 for x, y in squares)
print "Project Euler 90 Solution =", sum(1 for i,c1 in enumerate(cube)
for c2 in cube[:i]
if valid(c1, c2))
```

Use this link to get the Project Euler 90 Solution Python 2.7 source.#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### Afterthoughts

- As an exercise, one may ask how many combinations are there if the 6/9 reversal was NOT allowed, but instead, just the digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}?
By changing these two lines:

squares = [(0,1), (0,4), (0,9), (1,6), (2,5), (3,6), (4,9), (6,4), (8,1)]

dice = list(combinations([0,1,2,3,4,5,6,7,8,9], 6))The answer would be: 205

*Project Euler 90 Solution last updated*

## Discussion

## No comments yet.