riddler_mult.py

#!/usr/bin/env python3
#
# The solution to 538's Riddler for 1/15/2021
#
# https://fivethirtyeight.com/features/can-you-hunt-for-the-mysterious-numbers/

from itertools import permutations


def find_breakdowns(n, digits, highest):
    """
    Finds the all possible ways to break down n in to digits single-digit factors (in descending order)
    """
    if digits == 1:
        if n <= highest:
            yield [n]
    else:
        for i in range(highest, 0, -1):
            if n % i == 0:
                for result in find_breakdowns(n // i, digits - 1, i):
                    yield [i] + result


def solve(values, bottom_totals):
    """
    Do a depth-first solution to the problem. Note: at the end, bottom_totals should all be 1,
    so we do a sanity check for that
    """
    if len(values) == 0:
        assert (sum(bottom_totals) == 3)
        return []
    for breakdown in find_breakdowns(values[0], 3, 9):
        for perm in permutations(breakdown):
            if bottom_totals[0] % perm[0] == 0 and bottom_totals[1] % perm[1] == 0 and bottom_totals[2] % perm[2] == 0:
                new_totals = []
                for i in range(3):
                    new_totals.append(bottom_totals[i] // perm[i])
                result = solve(values[1:], new_totals)
                if result is not None:
                    return [perm] + result
    return None


side_numbers = [294, 216, 135, 98, 112, 84, 245, 40]
bottom_numbers = [8890560, 156800, 55566]
solution = solve(side_numbers, bottom_numbers)

for side, digits in zip(side_numbers, solution):
    print('{}{}{}  -> {}'.format(digits[0], digits[1], digits[2], side))