CODEWITHSUNDEEP
pythonnested-loops
nebffa
nebffa

Reputation: 1549

How can I avoid "IndentationError: too many levels of indentation" from deeply nested for loops?

I am doing a Project Euler question for programming practice in order to self-teach myself. I know perfectly well how to do the question mathematically, as well as how to do it programmatically.

However, I have to have come up with some insane code to do it; 100 nested loops and Python hilariously raises this error, and probably rightfully so, on 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 have looked through google for solutions but this issue is so rare it has almost no literature on the subject and I could only find this other stack overflow question ( Python IndentationError: too many levels of indentation ) which I could not find much useful in for my question.

My question is - is there a way to take my solution and find some workaround or refactor it in a way that has it work? I am truly stumped.

Upvotes: 4

Views: 357

Answers (4)

lvc
lvc

Reputation: 35079

To do this using exactly your algorithm (restricting each next number to one that can possibly fit in the required sum), you really do need recursion - but the true brute force method can be a one-liner:

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

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

Upvotes: 1

kampu
kampu

Reputation: 1421

The most effective solution is based on the idea of arithmetic carrying. You have lists of maximum values and steps, and also a list of current values. For each time you want to update those 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 an IndexError is raised, you've finished looping (run out of 'digits' to carry into.)

Upvotes: 0

nneonneo
nneonneo

Reputation: 179452

A recursive solution should do nicely, though I'm certain there is an entirely different solution to the problem that doesn't 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 enough, if you memoize this function, it will actually have a reasonable running time (such is the power of dynamic programming). Have fun!

Upvotes: 5

Raymond Hettinger
Raymond Hettinger

Reputation: 226376

One way to avoid the indentation error is to put the loops in separate functions, each one nested only one level deep.

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

That being said, your algorithm will have an impossibly long running time no matter how you code it. You need a better algorithm :-)

Upvotes: 1

Related Questions