Out-of-bounds debugging lab in Python

Why this lab matters

An index that runs past the end of a list is one of the most common bugs in beginner Python code. Python checks every list access while the program runs. When an index is too big, Python stops the program and prints a traceback. A traceback is the report of where the error happened, and it names the line and the kind of error. Unlike some languages, Python's message does not give the bad index or the length, so you have to work them out from the code. That takes practice, and this lab gives it.

This lab gives you five broken programs. Each one crashes with the same kind of error, but the cause is different in each. Try to find the bad index before you read the explanation. The lab uses the list basics from the one-dimensional lists lesson and the loop basics from earlier in the course. Lab 3 uses a list of lists, which is a list whose items are other lists. The matrix lessons in this module use grids in more depth.

Reading the error message

When an index is outside the list, Python prints something like this:

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    total += readings[i]
             ~~~~~~~~^^^
IndexError: list index out of range

Read it in three parts.

• The last line, IndexError: list index out of range, is the name of the error and its reason. An exception is Python's word for an error that happens while the program runs. IndexError means "an index was outside the list". The message does not give the index or the length.
• The lines that start with File form the traceback. The first of them is the outer call, and the last is the line where the error happened. line 4 means line 4 of the file main.py.
• The line under the code, with ~ and ^ marks, points at the part of the line that failed. Here it points at readings[i].

The line in the traceback is the place where the bad access happened. It is not always the place where the bug is. The bug is usually in the loop or the calculation that produced the index. When the traceback points at a loop, look at the loop's start value, its end test and its step.

Because the message has no numbers, you need to work them out. Write down the value of the index on the last pass of the loop, and write down the length of the list. Those two numbers are what a message with the index and length would show.

A method you can use on every program

Use these steps in order on each lab.

1. Read the traceback and find the line that failed. Find the list access on that line.
2. Find the variable that makes up the index. Often it is a loop variable.
3. Work out the value of that variable on the last pass of the loop. Use the loop test to help. If the test is i <= len(readings), the last value of i is the length itself.
4. Compare with the valid range, which is 0 up to the length minus 1. If the index is outside it, you have found the bad access.
5. Check which list the length belongs to. A length that is correct for one list can be wrong for another.
6. Check for negative indexes too. Python does not fail on a negative index in the range from minus the length up to minus 1. It counts from the end, so the wrong box is read with no error at all. Lab 6 below shows this.

Do not change the code until you know the cause. Changing numbers at random can make the crash disappear without fixing the logic, and then the program gives wrong answers with no error at all.

To run any lab, save the code in a file named main.py inside its own folder. Then run python3 main.py from that folder. Python reads the file and runs it at once, so there is no separate compile step.

Reading a loop test in plain words

Most bugs in this lab sit in a loop test. Read the test in plain words before you run the code. The line for i in range(len(readings) + 1): says: count from 0 up to, but not including, the length plus one. With a length of 5, that allows i to be 5.

Write down the first value and the last value of the loop variable on paper. The first value is usually 0. The last value is the one that the range still produces. If the last value equals the length, the loop is one step too far. This takes a few seconds and catches most of the bugs in this lab. Remember that range(n) stops before n, so range(len(a)) is the safe form for walking a list.

Lab 1: the loop that goes one too far

Read this program and find the bad index before you run it.

readings = [12, 7, 9, 4, 15]
total = 0
for i in range(len(readings) + 1):
    total += readings[i]
print("Total:", total)

Running it gives this output.

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    total += readings[i]
             ~~~~~~~~^^^
IndexError: list index out of range

The traceback points at line 4, which reads readings[i]. The loop uses range(len(readings) + 1), which produces the numbers 0 to 5. On the last pass, i is 5, and Python looks for box 5, which does not exist. The list has length 5, so the valid indexes are 0 to 4.

The usual fix is to stop at the length. The range function stops before its end value, so range(len(readings)) gives 0 to 4.

for i in range(len(readings)):

With that change the program prints Total: 47. Check it by hand: 12 + 7 + 9 + 4 + 15 is 47.

The pattern to remember: when you loop over a list with an index, the range should end at len(list), which stops before the length. Writing len(list) + 1 is the most common cause of this error. When you only need the values, write for value in readings: and avoid indexes altogether.

Lab 2: looking at the next box

This program counts how many times a temperature goes up from one day to the next. To do that, it compares each entry with the entry after it, using temps[i + 1].

temps = [18, 21, 19, 25]
rises = 0
for i in range(len(temps)):
    if temps[i + 1] > temps[i]:
        rises += 1
print("Rises:", rises)

Running it gives this output.

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    if temps[i + 1] > temps[i]:
       ~~~~~^^^^^^^
IndexError: list index out of range

The loop range(len(temps)) is correct for temps[i]. The problem is the second access, temps[i + 1]. When i is 3, the code asks for temps[4]. The last box is at index 3, so there is no box after it.

This is an off-by-one error. An off-by-one error is a mistake of one step in a count, a start point or an end point. Here the bug is that the loop uses the same range for i as for i + 1, but i + 1 needs one fewer step.

There are two correct ways to fix it. The first is to stop one step early.

for i in range(len(temps) - 1):

With that change the output is Rises: 2. Check it by hand: 18 to 21 is a rise, 21 to 19 is not, and 19 to 25 is a rise. That makes 2.

The second way is to keep the loop as it is and check the bounds inside it. This version is longer, but it shows the rule clearly.

for i in range(len(temps)):
    if i + 1 < len(temps) and temps[i + 1] > temps[i]:
        rises += 1

Both give the same result. The rule is the same for every neighbour check. If the code reads i + 1, the loop must stop before the last index. If the code reads i - 1, the loop must start at index 1, not index 0. Lab 6 shows what happens when that rule is broken in Python.

Lab 3: the grid with the wrong length

A list of lists has two lengths. len(seats) is the number of rows. len(seats[row]) is the number of columns in that row. This program uses the row count where it needed the column count.

seats = [
    [1, 0],
    [0, 1],
    [1, 1],
]
booked = 0
for row in range(len(seats)):
    for col in range(len(seats)):
        booked += seats[row][col]
print("Booked:", booked)

Running it gives this output.

Traceback (most recent call last):
  File "main.py", line 9, in <module>
    booked += seats[row][col]
              ~~~~~~~~~~^^^^^
IndexError: list index out of range

The grid has 3 rows and 2 columns. The inner loop, range(len(seats)), runs for col from 0 to 2. For row 0, the row has only 2 boxes, so col reaches 2 and Python looks for seats[0][2]. The message does not say which length was wrong. You need to check which length the loop used. Here the inner loop used len(seats), which is 3, and the row has length 2.

The fix is to use the length of the row being read.

for col in range(len(seats[row])):

With that change the output is Booked: 4. Check it by hand: the three rows hold 1, 1 and 2 bookings, which makes 4.

This is a good habit for every grid loop. Write len(grid) only when you mean the number of rows. Write len(grid[row]) when you mean the number of columns in one row. Python does not require every row to have the same length. The jagged lists lesson in this module covers rows of different lengths, and for those grids len(grid[row]) is the only safe choice.

Lab 4: months that start at 1, boxes that start at 0

The program below prints the English name of each month. The month numbers are 1 for January through 12 for December. The names are stored in a list, and the list starts at index 0.

month_names = [
    "January", "February", "March", "April", "May", "June",
    "July", "August", "September", "October", "November", "December",
]
months = [1, 6, 12]
for m in months:
    print(m, "=", month_names[m])

Running it gives this output.

1 = February
6 = July
Traceback (most recent call last):
  File "main.py", line 7, in <module>
    print(m, "=", month_names[m])
                  ~~~~~~~~~~~^^^
IndexError: list index out of range

Look at the first line of output before you look at the error. Month 1 printed "February", which is wrong. The program did not crash on month 1, so the wrong value is the first clue. Python does not know that month numbers start at 1. It uses the number as a box index. Index 1 is the second name, February. Month 12 asks for index 12, and the list has only the indexes 0 to 11, so Python stops.

The fix is to subtract 1 from the month number before using it as an index.

print(m, "=", month_names[m - 1])

The output becomes 1 = January, 6 = June and 12 = December. Check that: index 0 is January, index 5 is June, and index 11 is December.

Whenever a number from the outside world is used as an index, ask whether it starts at 0. Counts such as months, days and seats often start at 1. A conversion like m - 1 belongs right next to the list access, so that the reader can see it.

Lab 5: binary search with a high value that is one too big

Binary search is a way to find a value in a sorted list by checking the middle and throwing away the half that cannot contain the value. Each check keeps three numbers. low is the first index still under consideration. high is the last index still under consideration. mid is the index in the middle of those two.

This program searches a sorted list. The search function sets high to the length of the list when it should set it to the length minus 1.

def index_of(sorted_values, target):
    low = 0
    high = len(sorted_values)
    while low <= high:
        mid = (low + high) // 2
        if sorted_values[mid] == target:
            return mid
        elif sorted_values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
sorted_values = [2, 5, 8, 12, 16, 23, 38, 56]
print("Found 23 at", index_of(sorted_values, 23))
print("Found 99 at", index_of(sorted_values, 99))

Running it gives this output.

Found 23 at 5
Traceback (most recent call last):
  File "main.py", line 16, in <module>
    print("Found 99 at", index_of(sorted_values, 99))
                         ~~~~~~~~^^^^^^^^^^^^^^^^^^^
  File "main.py", line 6, in index_of
    if sorted_values[mid] == target:
       ~~~~~~~~~~~~~^^^^^
IndexError: list index out of range

The first search works, because it finds 23 before it reaches index 8. The second search looks for 99, which is bigger than every value in the list. Each step moves low upward, so the search keeps looking at the right-hand side. The table below shows each step.

The traceback has two frames. The last frame is inside index_of, at line 6, where sorted_values[mid] is read. The frame above it is at line 16, in the main code, where index_of was called. The last frame shows where the access failed. The bug is in the line high = len(sorted_values), because high can reach the length of the list, which is one past the last valid index.

The fix is to start high at the last valid index.

high = len(sorted_values) - 1

With that change the output is:

Found 23 at 5
Found 99 at -1

The search for 99 now ends with low greater than high, and the function returns -1, which is the usual sign for "not found". Check it by hand: the search looks at indexes 3, 5, 6 and 7, and then stops because low passes high.

Lab 6: the error that does not happen

Some bugs in Python never raise an error. A negative index is the main case. Python counts from the end of the list when the index is negative, so an index of -1 is the last box. A loop that is meant to look at the box before the first one is a common example. Read this program before you run it.

temps = [18, 21, 19, 25]
total = 0
for i in range(len(temps)):
    total += temps[i - 1]
print("Total of the box before each day:", total)

The program prints a number and stops without any error. On the first pass i is 0, so temps[i - 1] is temps[-1], which is the last value, 25. The loop then adds 18, 21 and 19 as well. The total is 25 + 18 + 21 + 19, which is 83. The program looks correct, and the wrong answer shows no sign of the bug.

The fix depends on what the question asks. If the question is about the day before each day, the first day has no earlier day. Start the loop at 1, so that i - 1 never goes below 0.

for i in range(1, len(temps)):
    total += temps[i - 1]

With that change the total is 18 + 21 + 19, which is 58. Check it by hand: 18 + 21 + 19 is 58. The lesson is that a negative index is not an error in Python, so the check has to come from you. Test the first and last positions of the loop with a small list, and compare the answer with what you expect.

Mistakes that look like this error

Some mistakes produce a different message, but students often confuse them with this error, so it helps to know the difference.

A negative index is the one that does not fail, as lab 6 showed. A negative index beyond the start of the list does fail, with the same error as before.

arr = [4, 8, 15]
print(arr[-4])

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(arr[-4])
          ~~~^^^^
IndexError: list index out of range

A list has a length from len, and no attribute called length. Using length as an attribute gives an error when the line runs.

arr = [4, 8, 15]
print(arr.length)

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(arr.length)
          ^^^^^^^^^^
AttributeError: 'list' object has no attribute 'length'

The fix is len(arr). The message names the problem exactly: a list has no attribute called length.

Strings can be read with square brackets in Python, so word[0] gives the first letter. A string cannot be changed that way, which is a different error.

word = "abc"
print(word[0])
word[0] = "x"

The first line prints a. The second line stops the program with TypeError: 'str' object does not support item assignment, as the reversal lesson of this module showed.

Practice

Each exercise has a short program. Try to answer before you read the answer. Save each program as main.py and run it to check your answer.

Exercise 1

What does this program print, and which index fails?

scores = [55, 61, 70]
for i in range(1, len(scores) + 1):
    print(scores[i])

Show the answer

It prints 61, then 70, then fails. On the first pass i is 1, so it prints scores[1], which is 61. On the second pass i is 2, so it prints 70. On the third pass i is 3, and scores[3] does not exist. The error is IndexError: list index out of range. The fix is to start at 0 and stop at len(scores).

Exercise 2

A program prints the names in reverse order. It crashes at once and prints nothing. Find the bad index.

names = ["Ana", "Ben", "Chi"]
for i in range(len(names), -1, -1):
    print(names[i])

Show the answer

The first value of i is 3, so names[3] is read on the first pass. The error is IndexError: list index out of range. The fix is to start at len(names) - 1. The corrected loop prints Chi, Ben and Ana.

Exercise 3

This program adds up the list by reading the box before each index. Which index fails, and what is the answer?

a = [1, 2, 3]
total = 0
for i in range(len(a)):
    total += a[i - 1]
print("Sum:", total)

Show the answer

No index fails. On the first pass i is 0, so the code reads a[-1], which is the last value, 3. That is a valid negative index, so Python does not stop. The program prints Sum: 6, which is the correct sum, because the loop still reads each value once, only shifted by one box. The bug is hidden, and the program gives no sign of it. Reading a[i] with i starting at 0 is the fix, or a loop that starts at 1 if the question is about the box before each value.

Exercise 4

This program is meant to fill the first row of a grid with 1s. It has 4 rows and 3 columns. Which index fails?

grid = [[0] * 3 for _ in range(4)]
for c in range(len(grid)):
    grid[0][c] = 1
print("Row 0 set")

Show the answer

The loop uses len(grid), which is 4, the number of rows. It should use len(grid[0]), which is 3, the number of columns in row 0. When c reaches 3, the code writes to grid[0][3], which does not exist. The error is IndexError: list assignment index out of range, and the assignment inside the loop raises it.

Exercise 5

Write a loop that prints the names in ["Ana", "Ben", "Chi"] in reverse order, with no crash. Then say why your loop starts where it does.

Show the answer

This loop works.

Output:

Chi
Ben
Ana

The loop starts at len(names) - 1, which is 2, the last valid index. The range stops before -1, so it goes down to 0, the first valid index. Python's range stops before its end value, so the end value is -1, and the loop still includes index 0. Python also offers reversed(names), which gives the same values in reverse order without any index.

Summary

• The traceback gives the line where the access failed. Python's message does not give the bad index or the length, so work those out from the loop.
• Most out-of-bounds bugs come from a range that is one step too far, usually range(len(a) + 1) where range(len(a)) is needed.
• A neighbour access such as i + 1 needs the loop to stop one step earlier. A check such as i - 1 needs the loop to start one step later.
• In a list of lists, len(grid) is the number of rows and len(grid[row]) is the number of columns in that row.
• A number that comes from the outside world, such as a month, may start at 1, while Python lists start at 0.
• A negative index that is within the list does not raise an error, so a wrong i - 1 can give a wrong answer with no sign of trouble.