Cubic Permutations | Project Euler #62

Question

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). 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.

The following code can find find three permutations under a second, but it's taking very long for finding five permutations.

How do I improve runtime?

#! /usr/bin/env python

import itertools


def is_cube(n):
    return round(n ** (1 / 3)) ** 3 == n



def main():
    found = False
    n = 100
    while not found:
        n += 1
        cube = n ** 3
        perms = [
            int("".join(map(str, a)))
            for a in itertools.permutations(str(cube))
        ]
        perms = [perm for perm in perms if len(str(perm)) == len(str(cube))]
        filtered_perms = set(filter(is_cube, perms))
        if len(filtered_perms) == 5:
            found = True
            print(filtered_perms)


if __name__ == "__main__":
    main()

Answer 1

Tend to use one style

perm for perm in perms if len(str(perm)) == len(str(cube))

and

filter(is_cube, perms)

are almost the same: an iterator that applies some filter. Don't confuse the reader - use the same style for both... or even join them in one expression.

Don't create collections until needed

perms is a list of permutations. For a 9-digit number there will be roughly 9!=362880 permutations, and they are filtered afterwards. You can use a generator, so all filters will be applied together:

perms = (int("".join(map(str, a)))
            for a in itertools.permutations(str(cube)))
perms = (perm for perm in perms if len(str(perm)) == len(str(cube)))
filtered_perms = set(filter(is_cube, perms))

First two expressions won't actually do anything; the third will run all the actions because set needs to be populated. So you'll save some memory and allocation/deallocation operations.

Use break keyword instead of found variable

Yes, it's not structural, but makes code more readable if there's only one break (or several are located together in a long loop). Instead of setting found = True just break the loop.

Use itertools.count

I think for n in itertools.count(100): looks better than while True: and all operations with n.

Algorithm

As I've said, there's too many permutations. And then you do extra work because you're checking permutations you've checked again on different numbers. Instead of that, just turn every cube into a kind of fingerprint - a string of sorted digits, ''.join(sorted(str(n**3))), and count the times you've met each fingerprint (it a dict or collections.Counter). All permuted numbers will have the same fingerprint. The only possible problem is when you meet some fingerprint 5 times, you should also check if it won't be met the 6th time.