Project Euler 92

Question

My code for solving problem 92 was correct but too slow and hence I tried to modify it by considering only one number for each possible permutation of that number, effectively reducing the size of the problem to 11439 from the original 10 million. Here's my code

import time
from Euler import multCoeff

start = time.time()

def newNum(n):
    return sum([int(dig)**2 for dig in str(n)])

def chain(n, l):
    if n in l:
        return n, l
    else:
        l.append(n)
        return chain(newNum(n), l)

nums = []

for i in range(1,10000000):
    if all(str(i)[j] <= str(i)[j+1] for j in range(len(str(i))-1)):
        nums.append(i)

count = 0   

for i in nums:
    if 89 in chain(i,[])[1]: 
        perms = multCoeff(i)
        count += perms

end = time.time() - start            

print count, end

multCoeff is a method that I created which is basically equivalent to len(set(permutations([int(j) for j in str(i)]))) and works just fine. Anyway, the problem is that the result I get is not the correct one, and it looks like I'm ignoring some of the cases but I can't really see which ones. I'd be really grateful if someone could point me in the right direction. Thanks.

Answer 1

We're missing the code for multCoeff, so I'm guessing here.

You're trying to filter from 1 to 999,999,999 by excluding numbers that do not have digits in ascending order and then re-calculating their permutations after.

Your problem is 0.

According to your filter 2, 20, 200, 2000, 20000, 200000, 2000000 are all represented by 2, however you're probably not adding back this many permutations.

---

General observations about your code:

• item in list has O(n) time complexity; try to avoid doing this for large lists.
• You are throwing away the results of many computations; any number in a chain that results in 89 or 1 will always have that end result.
• Every function call has a time cost; try to keep the number of functions in looping calls low.
• Casting str to int is somewhat expensive; try to keep the number of casts to a minimum.