Project Euler Problem 90 Statement

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?

Solution

HackerRank Project Euler Problem 90 overview:

In this problem, you choose digits for $M$ (1, 2, or 3) dice so that they can collectively display a set of square numbers (for instance, all two-digit squares from 01 up to 81). Each die has six faces, and the digit 6 can represent both 6 and 9 by flipping it. You must ensure that every square number in the given range can be formed by some orientation of the dice—accounting for leading zeros (like 01) and allowing dice faces to be swapped (e.g., die A shows the first digit, die B shows the second). The goal is to count how many distinct dice configurations achieve this, treating dice and face arrangements that differ only by ordering as the same configuration.

Solution Summary

This solution systematically enumerates all possible dice (each as a 6-digit subset of 0-9), accounts for the 6/9 flip, and then checks whether every required square can be formed by those dice. For $M=1$, a single die must cover all relevant digits; for $M=2$, every two-digit square must be displayed by some pairing of two dice (checking both digit orders); and for higher $M$, the logic extends to triplets (or more) of dice.

Detailed Explanation of the Script

Below is a step-by-step explanation of how this script works. Although the original Project Euler Problem 90 specifically involves two dice that can display certain two-digit squares, this code generalizes the idea to handle \( M \)-digit squares by using \( M \) dice (when \( M \le 3 \) in this example).

1. Reading Input and Building the List of Squares

N, M = map(int, input().split())
sq = [list(map(int, f"{i*i:0{M}d}")) for i in range(1, N+1)]

• N, M = map(int, input().split())
  Reads two integers from input: \( N \) is the range of squares (from \(1^2\) up to \(N^2\)), and \( M \) is the number of digits we need for each square (e.g., \( M=2 \) for two-digit numbers like 01, 04, 09, 16, etc.).
• f"{i*i:0{M}d}"
  Formats the square \( i^2 \) as an \( M \)-digit string with leading zeros if necessary (e.g., if \( M=2 \) and \( i=3 \), we get "09" for 3^2=9).
• sq = [...]
  Each formatted square string is converted into a list of digits. For \( M=2 \) and \( N=9 \), sq would look like \[ [[0,1], [0,4], [0,9], [1,6], [2,5], [3,6], [4,9], [6,4], [8,1]] \] which will be used later to check whether the dice can display these digit-pairs.

2. Handling the Digits 6 and 9 Interchangeably

c = lambda d, x: x in d or (x in [6, 9] and (6 in d or 9 in d))

A single die face that shows a 6 or 9 is considered able to show both 6 and 9 by rotating the die 180°. c(d, x) checks whether the digit \( x \) can appear on the set of faces \( d \). If \( x \neq 6\) and \( x \neq 9\), it just checks if \( x \in d\). Otherwise, it ensures that at least one of 6 or 9 is in \( d \).

3. Checking All Squares for Two Dice (When \( M=2 \))

cp = lambda d1, d2: all(
    (c(d1, x) and c(d2, y)) or (c(d1, y) and c(d2, x)) 
    for x, y in sq
)

• d1 and d2 represent two sets of 6 digits each (the faces on each of the two dice).
• We loop over each pair \((x,y)\) that represents a square in sq. To display the 2-digit number \((x,y)\), the first die must show \( x \) and the second die \( y \), or vice-versa (\((y,x)\)).
• We use all(...) to ensure that every square \((x,y)\) can be displayed.

4. Generating All Dice Faces

d = list(itertools.combinations(range(10), 6))
dl = len(d)

• itertools.combinations(range(10), 6) generates all ways to pick 6 distinct digits from the ten possible 0..9.
• Each 6-digit combination represents one possible die configuration (order doesn't matter).
• d is the list of all such combinations, and dl is its length.

5. Counting Valid Dice (Depending on $M$)

If we only need to show single-digit numbers (e.g., the squares are 1, 4, 9, 16 — which, if zero-padded to 1 digit, become just 1, 4, 9, 6, etc.), we only need one die that can display all those digits. We compute \(\{s[0] : s \in sq\}\) — all the unique digits from our list sq — and check if each 6-digit die has those digits (taking the 6 — 9 trick into account). The sum of all dice that pass this check is printed.

if M == 1:
    print(sum(all(c(die, x) for x in {s[0] for s in sq}) for die in d))

This is the classic Project Euler Problem 90 scenario: two dice must together display all 2-digit squares. We use nested loops \((i, j)\) with \( j \ge i \) to avoid counting the same pair of dice twice. For each pair (d[i], d[j]), we check if cp(...) returns True for all squares. We sum up all valid pairs.

elif M == 2:
    print(sum(cp(d[i], d[j]) for i in range(dl) for j in range(i, dl)))

Now the logic extends to three dice in order to show 3-digit squares. We consider all triplets \((i, j, k)\) of the dice from d, again restricting \( j \ge i \) and \( k \ge j \) to avoid duplicates.

For each square $[s[0], s[1], s[2]]$, we check if any permutation of the dice can display these digits. For example:

• Die d[i] shows \( s[0] \)
• Die d[j] shows \( s[1] \)
• Die d[k] shows \( s[2] \)

But we also check other permutations like \((i, k, j)\), etc., to see if there is a valid assignment for each square. If all squares can be displayed by that triplet of dice in at least one permutation, we count the triplet as valid.

else:
    print(sum(
        all(
            any(
                c(d[x[0]], s[0]) and c(d[x[1]], s[1]) and c(d[x[2]], s[2])
                for x in ((i,j,k), (i,k,j), (j,i,k), (j,k,i), (k,i,j), (k,j,i))
            )
            for s in sq
        )
        for i in range(dl) for j in range(i, dl) for k in range(j, dl)
    ))

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 90

HackerRank Project Euler 89 (easy? maybe, but very tedious) increases/decreases the number of dice to 1, 2, or 3 cubes to allow for all of the first $N$ square numbers ($1 ≤ N ≤ 10^{M/2}$) to be displayed?