mardi 4 août 2015

Project Euler 92

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.



via Chebli Mohamed

Aucun commentaire:

Enregistrer un commentaire