Project Euler 62: cubic permutations, logic

Question

Problem 62 of Project Euler goes

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.

Now I have written the following code to handle the problem. In essence I iterate over the cubes, and sort the numbers from highest to lowest. These values I use as keys in a dictionary. When the count reaches the desired amount (5) i break the loop.

Well that is almost correct, or it was my first code. It gave me the correct answer, however someone made the following remark:

Even if the chain of permutations is 5, it is possible that you will find permutations later on that increases the count.

To overcome this silly issue i do the following: if the count is right i add them to a list of possible candidates. Once the number of digits in the current cube is larger than the number of digits in the candidates, i iterate over the candidates. Here i again check the number of cube permutations (it is still stored in the dictionary) and find the smallest one. If none of the candidates are valid, we clear the candidate list and start over.

It seems like quite a convoluted way of doing things.. and I do not like the logic of my try's and exceptions. I also think there is a logic break if the best permutation is the one where we go from $n$ to $n+1$ digits, since then it will be added to the list of permutations, and then removed.

Question: Is there a clearer way to code my reasoning in this problem? Does my code cover the corner / limit cases?

When I look at the code of others solving the same excercise their code looks so tiny and compact in comparison to mine =(

# Sorts a number from highest to lowest
def num2highest(num):
    string = sorted(str(num))
    rev_string = string[::-1]
    return int(''.join(map(str, rev_string )))


def cube_perms(perms, limit):
    checked = dict()
    cube_lst = []
    candidates = []
    len_cand = len(str(limit**3)) + 1

    for i in range(min(10**6, limit)):
        cube = i**3
        low_perm = num2highest(cube) #Sort the cube

        # Add sorted cube as a key in dict
        if checked.has_key(low_perm): 
            count, cube_lst = checked[low_perm]
            cube_lst.append(i)
        else:
            count = 0
            low_cube = cube
            cube_lst = [i]
        checked[low_perm] = count+1, cube_lst #Increases the count of one

        # If the count is -1 of the wanted number of perms
        # add it to a list of possible candidates (since the count might increase)
        if count == perms - 1:
            if low_perm not in candidates:
                candidates.append(low_perm)
            len_cand = len(str(cube))

        # If the number of digits of the current cube is greater than the candidates
        # iterate over the possible candidates
        if len(str(cube)) > len_cand and len_cand < (len(str(limit**3)) + 1):
            the_one = choosen(candidates, perms, checked)
            if the_one > 0:
                count, cube_lst = checked[the_one]            
                return sorted(cube_lst)
            else:
                candidates = set()
                len_cand = len(str(limit**3)) + 1


# Iterates over the possible candidates, finding the smallest one
def choosen(candidates, perms, checked):
    choosen = 0
    minimal = candidates[0]
    for cand in candidates:
        count, cubes = checked[cand]
        if count == perms:
            temp_minimal = min(cubes)
            if temp_minimal < minimal:
                    minimal = temp_minimal
                    choosen = cand
    return choosen


if __name__ == '__main__':

    print cube_perms(5, 10**6)

Answer 1

Return Value

The question is asking for the smallest cube (127035954683), your code returns the list of values whose cubes permute to that ([5027, 7061, 7202, 8288, 8384]), so it's technically wrong.

Signature

The problem as described suggests a function that takes a single argument as input: the number. You additionally require a limit. What's the limit for? How do you know that the limit you picked isn't too small? You happen to pick a good limit, but what if we needed to go up in digits? What if we wanted to find the smallest cube with 7 permutations?

try/catch

You have this code:

try:
    return choosen
except:
    return 0

It took me a lot of squinting to actually realize what it is you were catching. Ohhh... NameError on choosen. And then you have the same thing in the interior - you're catching not an exception but an undefined name. That is awkward code to understand.

First, you can just up-front declare choosen = 0, that lets you drop the last try/except block completely.

Next, you can up-front declare minimal to be None and change that block to be:

if minimal is None or temp_minimal < minimal:
    minimal = temp_minimal

Or you could declare minimal to be sys.maxint. Also there, you're assigning to a variable named min_cand but never reading it, so not sure what that is for.

Algorithm

I think you're overthinking the problem somewhat. You have the right approach with keeping track of a dictionary with the sorted permutation. But then you kind of lose me with the digit counting. I chuckled at the_one = chosen(...), but I have no idea what that function is doing.

Here's my thoguht process. When our count for a particular permutation reaches the goal count, we have to verify that there aren't any future cubes that would end up here. That remark is correct. However, we know exactly which things we need to test - so we should just explicitly test those:

To start with:

def my_cube_perm(num_perms):
    def as_str(x):
        return ''.join(sorted(str(x)))

    counts = collections.defaultdict(int)
    smallest = {}

    for i in itertools.count(start=1): # no limit!
        cube = i**3
        cube_str = as_str(i**3)
        counts[cube_str] += 1
        smallest.setdefault(cube_str, cube)

        if counts[cube_str] == num_perms:
           # ok what, now?

The next smallest possible cube that could produce cube_str is i+1. The largest possible cube that produce it comes from reverse-sorting cube_str and taking its cube root. So just walk that range:

max_possible = int(int(''.join(reversed(cube_str)))**(1/3.))
if not any(as_str(p**3) == cube_str
           for p in xrange(i+1, max_possible+1)):
    return smallest[cube_str]

This is ~2.3x faster (38ms vs 87ms), but more importantly I think is easier to follow the logic and is much shorter.

Algorithm Update

N3buchadnezzar makes a good point in that the first solution I found isn't necessarily the smallest. We could have 5 permutations of one cube all fall in between the first and next 4 permutations of another. So we have to keep track of some more state. If we find a value that we think is the answer - we save it and the length of its cube. Once we get to a cube with more digits, if we have anything saved, return at that point.

Full solution looks like this:

def my_cube_perm(num_perms):
    def as_str(x):
        return ''.join(sorted(str(x)))

    counts = collections.defaultdict(int)
    smallest = {}

    best = None
    best_len = 0 

    for i in itertools.count(start=1):
        cube = i**3
        cube_str = as_str(cube)

        # got an answer that is definitely shorter?
        if best is not None and len(cube_str) > best_len:
            return best

        counts[cube_str] += 1
        smallest.setdefault(cube_str, cube)

        if counts[cube_str] == num_perms:
            # check all the possibilities!
            max_possible = int(int(''.join(reversed(cube_str)))**(1/3.))
            if not any(as_str(p**3) == cube_str
                       for p in xrange(i+1, max_possible)):
                # update our best solution - if appropriate
                if best is None or smallest[cube_str] < best:
                    best = smallest[cube_str]
                    best_len = len(cube_str)

This increases runtime to 46ms. But then again, runtime of an incorrect algorithm doesn't really matter. And still ~1.9x faster.

Answer 2

This sounds like a good approach...

if the count is right i add them to a list of possible candidates. Once the number of digits in the current cube is larger than the number of digits in the candidates, i iterate over the candidates. Here i again check the number of cube permutations (it is still stored in the dictionary) and find the smallest one. If none of the candidates are valid, we clear the candidate list and start over.

...but to simplify, I would not bother keeping track of the candidates while looping through the cubes. Whenever the number of digits in the cube increases, we can look for the solution in the counts dictionary.

Using Barry's code as starting point, I propose this:

def my_cube_perm(num_perms):
    def as_str(x):
        return ''.join(sorted(str(x)))

    counts = collections.defaultdict(int)
    smallest = {}
    digits = 0

    for i in itertools.count(start=1):
        cube = i**3
        cube_str = as_str(cube)

        if len(cube_str) > digits:
            digits = len(cube_str)
            solutions = [key for key, value in counts.iteritems() if value == num_perms]
            if solutions:
                return min(smallest[key] for key in solutions)
            #reset
            counts = collections.defaultdict(int)
            smallest = {}

        counts[cube_str] += 1
        smallest.setdefault(cube_str, cube)

I timed this at 25 ms vs. 29 ms for Barry's version, using num_perms=5.