Python IndentationError - how to refactor?

Question

I am doing Project Euler a question for programming practice, in order to teach myself. I know very well how to solve a problem mathematically, as well as how to do it programmatically.

However, I have to come up with some crazy code to do this; 100 nested loops and Python cheerfully raise this error, and probably rightfully, at 100 levels of indentation:

IndentationError: too many levels of indentation tally = 0 ceiling = 100 for integer_1 in range(0, 100, 1): for integer_2 in range(0, 100 - integer_1, 2): for integer_3 in range(0, 100 - integer_1 - integer_2, 3): for integer_4 .... for integer_5 .... etc. etc. all the way to integer_100 

I scanned Google for solutions, but the problem is so rare that it is almost no literature on the subject, and I could only find this other question ( the Python IndentationError: too much indentation levels ), I could not find much useful for my question .

My question is: is there a way to make my decision and find some solution or reorganize it so that it works? I am really puzzled.

EDIT:

Thanks to nneonneo's answer, I was able to resolve the issue. My code here is only for future references to people who are looking for ways to properly reorganize their code.

 from time import time t = time() count_rec_dict = {} # for finding ways to sum to 100 def count_rec(cursum, level): global count_rec_dict # 99 is the last integer that we could be using, # so prevent the algorithm from going further. if level == 99: if cursum == 100: return 1 else: return 0 res = 0 for i in xrange(0, 101-cursum, level+1): # fetch branch value from the dictionary if (cursum+i, level+1) in count_rec_dict: res += count_rec_dict[(cursum+i, level+1)] # add branch value to the dictionary else: count_rec_dict[(cursum+i, level+1)] = count_rec(cursum+i, level+1) res += count_rec_dict[(cursum+i, level+1)] return res} print count_rec(0, 0) print time() - t 

which runs at an astounding 0.041 seconds on my computer. WOW !!!!! Today I learned something new.

Answer 1

A recursive solution should be good, although I am sure that there is a completely different solution to the problem that does not require this kind of manipulation.

 def count_rec(cursum, level): if level == 100: return 1 res = 0 for i in xrange(0, 100-cursum, level+1): res += count_rec(cursum+i, level+1) return res print count_rec(0, 0) 

Interestingly, if you remember this function, it really will have a reasonable runtime (such is the power of dynamic programming). Enjoy!

Answer 2

One way to avoid indentation errors is to put loops in separate functions, each of which is nested only at one level.

Alternatively, you can use recursion to call the function again and again, each time with a smaller range and a higher level of nesting.

By saying this, your algorithm will have an incredibly long life, no matter how you code it. You need a better algorithm :-)

Answer 3

To do this, using exactly your algorithm (limiting each next number to one that can fit in the required amount), you really need recursion, but the true brute force method can be single-line:

 sum(sum(i) == 100 for i in itertools.product(xrange(100), repeat=100)) 

Naturally, this will be a fair bit slower than the actual refactoring of your algorithm (in fact, as mentioned in the comments, it turns out to be unsolvable).

Answer 4

The most effective solution is based on the idea of ​​arithmetic carrying. You have lists of maximum values ​​and steps, as well as a list of current values. For every time you want to update these 100 variables, you do this:

 inc_index = -1 currentvalue[inc_index] += stepval[inc_index] # I use >= rather than > here to replicate range()s behaviour that range(0,100) generates numbers from 0 to 99. while currentvalue[inc_index] >= maxval[inc_index]: currentvalue[inc_index] = 0 inc_index -= 1 currentvalue[inc_index] += stepval[inc_index] # now regenerate maxes for all subordinate indices while inc_index < -1: maxval[inc_index + 1] = 100 - sum (currentvalue[:inc_index]) inc_index += 1 

When the IndexError is raised, you have finished the loop (finish the “digits” for the carry.)