Python3 - Index out of range for existing element

Question

I'm trying to solve Problem 18 from Project Euler. My code is:

lines = []
lines.append([3])
lines.append([7, 4])
lines.append([2, 4, 6])
lines.append([8, 5, 9, 3])

i = len(lines) - 1
while i != -1:
    for j in range(0, len(lines[i - 1])):
        a = lines[i][j]
        b = lines[i][j + 1]
        if a > b:
            lines[i - 1][j] = a
        else:
            lines[i - 1][j] = b
    i -= 1

the result in the console is:

    E:\path_to_python\Python3\python.exe E:/path_to_python/Projects/ProjectEuler/18.py
    Traceback (most recent call last):
      File "E:/path_to_script/18.py", line 33, in <module>
        b = lines[i][j + 1]
    IndexError: list index out of range

    Process finished with exit code 1

the confusing part is that

    print("lines[{}][{}] = {} > {} = lines[{}][{}]".format(i,j,lines[i][j], lines[i][j+1], i,j+1))

creates the output:

Traceback (most recent call last):
      File "E:/path_to_scripter/18.py", line 31, in <module>
        print("lines[{}][{}] = {} > {} = lines[{}][{}]".format(i,j,lines[i][j], lines[i][j+1], i,j+1))
    IndexError: list index out of range
    lines[3][0] = 8 > 5 = lines[3][1]
    lines[3][1] = 5 > 9 = lines[3][2]
    lines[3][2] = 9 > 3 = lines[3][3]
    lines[2][0] = 8 > 9 = lines[2][1]
    lines[2][1] = 9 > 9 = lines[2][2]
    lines[1][0] = 9 > 9 = lines[1][1]

so every element exists but is at the same time out of range? What is my mistake here?

Answer 1

Here is a visual of the code at the point of error:

So you can see that at line 11, you are trying to access the element at index 1 of the 0th sub-array, but this array only has one element at index 0, thus the out-of-range error.

Hope this helps you to debug and solve that challenge :D

Answer 2

In the for loop, you each time obtain: lines[i][j], lines[i][j + 1], lines[i-1][j], so that means that j < n-1 with n the length of the list lines[i]. So you should write:

for j in range(0, len(lines[i])-1):

instead of:

for j in range(0, len(lines[i - 1])):

Note that furthermore you can make the code more elegant:

for i in range(len(lines)-1,0,-1):
    for j in range(0, len(lines[i])-1):
        a = lines[i][j]
        b = lines[i][j + 1]
        if a > b:
            lines[i-1][j] = a
        else:
            lines[i-1][j] = b

So we can use another range(..) for i. If we translate it exactly, it should be range(len(lines)-1,-1,-1). But in case i = 0, the second for loop will be empty, so we can stop at i = 1, hence the range(len(lines)-1,0,-1).