Project Euler Solution 62: Cubic permutations
Project Euler Problem 62: Cubic permutations is about digit permutations again.
The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube.
We just need to go through all the cubes and group them by their digits. Once we have found a digit representation with five cubes that correspond to it, we're done.
First we write a helper function that iterates all the cubes:
def iter_cubes() -> Iterator[int]: for i in itertools.count(1): yield i**3
And then we write another one which produces a list of digits from a number in a sorted way.
def sort_digits(number: int) -> list[int]: return sorted(str(number))
And then we just go through the cubes and build a mapping from digits to cubes. Once one has five elements, we're done.
def solution() -> int: digit_dict = collections.defaultdict(list) for cube in iter_cubes(): digits = tuple(sort_digits(cube)) digit_dict[digits].append(cube) if len(digit_dict[digits]) == 5: return min(digit_dict[digits])
This computes the correct answer in 12 ms. It would be possible that the cube that we have found has more than five permutations. We would have to continue the search until the we have exhausted all numbers with the current number of digits. But apparently we are lucky and this is not the case.