Euler Project 92
My code for solving problem 92 was correct, but too slow, and so I tried to change it to consider 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 I created that is mostly equivalent len(set(permutations([int(j) for j in str(i)])))
and works great. Anyway, the problem is that the result I am getting is not correct and it looks like I am ignoring some of the cases, but I cannot figure out which ones. I would be very grateful if someone could point me in the right direction. Thank.
source to share
We are missing the code for multCoeff
, so I guess here.
You are trying to filter from 1 to 999 999 999 by excluding numbers that have no digits in ascending order, and then recalculating their permutations after.
Your problem 0
.
According to your filter, 2, 20, 200, 2000, 20000, 200000, 2000000
everything is represented 2
, however you probably don't add back many permutations.
General notes about your code:
-
item in list
hasO(n)
time complexity ; try to avoid this for large lists. - You are discarding the results of many calculations ; any number in the string that results in
89
or1
will always have that end result. - Each function call has a time cost; try to keep the number of functions in the loops low.
- Casting
str
toint
a few expensive; try to keep the number of casts to a minimum.
source to share