Project Euler Problem 90 Solution

Project Euler Problem 90 Solution

Cube Digit Pairs

by {BetaProjects} | Project Euler & HackerRank

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.

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

This problem is complicated (about 30 lines, uncommented). So I thought I would document the solution using internal comments instead of discussing all the horrible details in paragraphs of text.

HackerRank version

HackerRank logo

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\le N\le 10^{\frac{M}{2}}$)) to be displayed?

Python Source Code

from itertools import combinations

def can(die, digit):
    """
    Checks if a digit can be formed by a die, considering 6 and 9 as interchangeable.

    Args:
        die: A tuple representing the numbers on a die.
        digit: The digit to check.

    Returns:
        True if the digit can be formed, False otherwise.
    """
    return digit in die or (digit in (6, 9) and (6 in die or 9 in die))

def check_pair(d1, d2, sq, cache):
    """
    Checks if two dice can form all the square numbers.

    Args:
        d1: A tuple representing the numbers on the first die.
        d2: A tuple representing the numbers on the second die.
        sq: A list of lists, where each inner list represents the digits of a square number.
        cache: A dictionary to store the results of previous checks.

    Returns:
        True if the dice pair can form all square numbers, False otherwise.
    """
    key = (d1, d2) if d1 <= d2 else (d2, d1)  # Ensure consistent key order
    if key not in cache:
        cache[key] = all(
            (can(d1, s[0]) and can(d2, s[1])) or (can(d1, s[1]) and can(d2, s[0]))
            for s in sq
        )
    return cache[key]

def PE90(n, m):
    """
    Calculates the number of distinct arrangements of dice that can form all square numbers up to n^2.

    Args:
        n: The upper limit for generating square numbers (up to n^2).
        m: The number of digits in the square numbers (e.g., 2 for two-digit squares).

    Returns:
        The number of distinct arrangements of dice.
    """
    dice = list(combinations(range(10), 6))  # Generate all possible 6-sided dice
    sq = [[int(x) for x in f"{i*i:0{m}d}"] for i in range(1, n + 1)]  # Generate square numbers
    
    cache = {} # Initialize the cache for check_pair results

    if m == 1:
        # For single-digit squares, we only need to check if each die can form the required digits.
        req = {s[0] for s in sq}  # Get the unique digits required
        return sum(all(can(d, x) for x in req) for d in dice)

    if m == 2:
        # For two-digit squares, we need to check pairs of dice.
        count = 0
        for i in range(len(dice)):
            for j in range(i, len(dice)):
                if check_pair(dice[i], dice[j], sq, cache):
                    count += 1
        return count
    
    # For three-digit or more squares, we need to check combinations of three dice.
    count = 0
    for i in range(len(dice)):
        for j in range(i, len(dice)):
            for k in range(j, len(dice)):
                if all(
                    any(
                        can(dice[p[0]], s[0])
                        and can(dice[p[1]], s[1])
                        and can(dice[p[2]], s[2])
                        for p in ((i,j,k), (i,k,j), (j,i,k), (j,k,i), (k,i,j), (k,j,i))
                    )
                    for s in sq
                ):
                    count += 1
    return count

# Get input from the user
N, M = map(int, input().split())

# Calculate and print the result
print(PE90(N, M))

Last Word