## 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.Use this link to get the Project Euler 90 Solution Python 2.7 source.

#### 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.