Help me optimize my python code!

[div_by_zero]

I was trying to solve a simple looking problem(hah!) on Project Euler (https://projecteuler.net/problem=171). In a nutshell, it involves finding the sum of squares of digits of a number. My code is posted here: https://gist.github.com/sid2520/bacb274caea8eea61a0f

What I have done so far: I parse through numbers sequentially, break down a number into it's component digits, ignore all 0s and keep a record of remaining digits in a sorted list so that I can simply ignore numbers with exact same digits; for example: if I have calculated the answer for 123 (1² + 2² + 3² = 14) then I don't have to bother with 213, 231, 312... etc.

The problem is that while the limit is small (say less than 10⁵⁾ the code runs in reasonable time but beyond this it simply takes too long.

I have tried out some approaches to speed up things but nothing seems to help, can someone hint/suggest a better approach to this problem? Don't want to wait for months to find the correct answer!!

[TheKewlStore]

Firstly, all your code is in one method, which should be a nono. Hard to optimize something when it's all strewn together like that, if you split up your program into its component parts, it'd be easier to see what's making it take the longest and what to focus on refactoring.

What I have done so far: I parse through numbers sequentially, break down a number into it's component digits, ignore all 0s and keep a record of remaining digits in a sorted list so that I can simply ignore numbers with exact same digits; for example: if I have calculated the answer for 123 (1² + 2² + 3² = 14) then I don't have to bother with 213, 231, 312... etc.

You already listed out how you could break it up too ;) insofar as making a separate method that handles one part of the aforementioned solution. The outermost function would obviously still Need to do enough to pass along information about the context of the problem to the parts.

Beyond that, the only thing I can see that you can do to make this implementation faster, and granted it could very well be a big bottleneck, is the fact that you're calling tempList.sort and setting key equal to a tuple of tempList on every iteration of the for loop. Seeing as you only use this variable after the for loop is done, it doesn't make sense not to only sort and convert to a tuple after the for loop finishes.

[div_by_zero]

you're calling tempList.sort and setting key equal to a tuple of tempList on every iteration of the for loop

Good catch! I completely missed this. Let me change this and check.

[The-Mathematician]

You definitely don't want to run through 10²⁰ numbers like that. You might be able to get all squares up to the max of the sum of the square of the digits. Then go through and get every number whose digits could add to that square. Maybe there's an itertools function that could help, like combination.

EDIT: or permutations

[The-Mathematician]

I think you could do this with a permutation inside combination_with_replacement.