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 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)