This reading focuses on techniques for debugging and improving small programs. We follow the locate → understand → fix process and use print statements to guide understanding. This heuristic is introduced through the “flood-fill” problem which is then extended to solve mazes.
We’ve been discussing the environment model in depth in the past few readings. We will now zoom out to a higher level and think about how to construct a program.
Useful Python Features
Zip
zip lets us find corresponding elements in multiple iterable objects, where in this case iterable is useful because we can use for loops to step through their elements.
Example
x = [100, 200, 300, 400]y = [9, 8, 7, 6]print(zip(x, y)) # prints <zip object at 0x...>
This isn’t very interesting on its own, but zip objects are meant to be looped over. Each element that the zip object makes is a tuple containing corresponding elements from x and y.
zip can be used in conjunction with multiple assignment to name each element of a tuple, i.e.
i,j = (100,9)
Example
for x_value, y_value in zip(x, y): print(x_value + y_value)
The * Unpacking Operator
We can use * to extract the parts of a tuple/list. For instance:
get_pixel(image, *location)
which in this case is the same as
get_pixel(image, location[0], location[1])
List Comprehensions
A list comprehension is a concise way to build a new list by applying an expression to each item in an iterable. The basic syntax is [expression for item in iterable]. You can also add an optional if clause to filter elements: [expression for item in iterable if condition].
Exercise 1
Assuming we have a list of numbers defined for us called y, write a list comprehension that makes a new list containing the squares of all the numbers in y.
Solution
squares = [val**2 for val in y]
Exercise 2
Consider the following piece of code, which constructs a list called out:
out = []for val in x: if val < 0: out.append(-val)
Write a list comprehension that produces the same list (you may assume that x is defined for you).
Solution
out = [-val for val in x if val < 0]
Flood Fill
We continue using a similar image representation to the one used in Labs 1 and 2, adding a new feature known as “flood fill” (i.e. the paint-bucket tool). The idea is that when clicking on a particular spot in an image, the color that was clicked on is replaced with a new color, but only in the contiguous region around the pixel that was clicked.
We approach this problem by writing a function called flood_fill:
def flood_fill(image, location, new_color): """ Given an image, replace the same-colored region around a given location with a given color. Mutates the original image to reflect the change. Parameters: * image: the image to operate on * location: a (row, col) tuple representing the starting location of the flood-fill process * new_color: the replacement color, as an (r, g, b) tuple where all values are between 0 and 255, inclusive """ pass
Helper Functions
Throughout this reading, we will make use of a few helper functions to make reading and writing the code a little bit nicer:
get_width(image): given an image, return its width in pixels (as an integer).
get_height(image): given an image, return its height in pixels (as an integer).
get_pixel(image, row, col): return the color of the pixel at location (row, col) in the given image.
set_pixel(image, row, col, color): mutate the given image to replace the color at location (row, col) with the given color.
Maintain a list of locations to color (the “agenda”)
While locations remain: remove one, color it, add its valid neighbors
First Attempt
def flood_fill(image, location, new_color): original_color = get_pixel(image, *location) def get_neighbors(cell): row, col = cell return [(row+1, col), (row-1, col), (row, col+1), (row, col-1)] to_color = [] while to_color: this_cell = to_color.pop(0) set_pixel(image, *this_cell, new_color) for neighbor in get_neighbors(this_cell): to_color.append(neighor)
Check Yourself
Which of the following most accurately describes the code as written above?
It contains a Python syntax error.
It will raise an exception when it runs.
It will not raise an exception but it will color in too many spots.
It will not raise an exception but it will color in too few spots.
It will work as expected.
Solution to_color starts empty so the loop never executes.
It will not raise an exception but it will color in too few spots.
Debugging
Bugs in the first attempt:
to_color starts empty — starting location never added
Typo: neighor instead of neighbor
No color checking — fill bleeds into all regions
Out-of-bounds access at image edges
Pixels added to agenda multiple times — exponential slowdown
General debugging approach:
Read the error message — it tells you what happened and where
Add print statements to track control flow (e.g. “before loop”, “inside loop”)
For visual domains (images), update the display as you go to see intermediate results (e.g. uncommenting pygame.display.flip() after each set_pixel)
Use the traceback (stack trace) to trace the chain of calls that led to the error — the actual bug is often higher up in the call stack than where the error surfaces
IndexError: pixel index out of range in get_pixel doesn’t mean the bug is in get_pixel — it means flood_fill passed an out-of-bounds coordinate because get_neighbors didn’t filter for valid bounds
Even after fixing bounds and color checking, the code may slow to a crawl without crashing — repeated locations in the print output reveal that pixels are being re-added to the agenda. The color check alone doesn’t prevent this because neighbors get added before they’re colored. This is why a visited set is needed.
Getting Neighbors
def get_neighbors(cell): row, col = cell potential_neighbors = [(row+1, col), (row-1, col), (row, col+1), (row, col-1)] return [ (nr, nc) for nr, nc in potential_neighbors if 0 <= nr < get_height(image) and 0 <= nc < get_width(image) ]
The Visited Set
Track every location ever added to the agenda so we only add each pixel once.
Using visited as a list doesn’t actually speed things up — not in on a list is O(n), so the membership checks cost roughly as much as the redundant work they prevent (~0.58s for the sky region).
Switching visited to a set gives ~10x speedup (~0.07s) because set membership is O(1) via hashing. The two changes:
visited = [location] → visited = {location}
visited.append(neighbor) → visited.add(neighbor)
Sets vs lists:
Sets can only contain hashable elements (tuples work, lists don’t)
Elements have no order and can’t appear more than once
Membership tests (in) are O(1) regardless of size
Which of these are legal ways to make a set in Python?
{3}
{"abc"}
{[1, 2]}
{(1, 2)}
{([1], [2])}
Solution {3}, {"abc"}, and {(1, 2)} are legal — ints, strings, and tuples are all hashable. {[1, 2]} and {([1], [2])} are illegal because lists aren't hashable (and a tuple containing lists isn't hashable either).
Final Implementation
def flood_fill(image, location, new_color): original_color = get_pixel(image, *location) def get_neighbors(cell): row, col = cell potential_neighbors = [(row+1, col), (row-1, col), (row, col+1), (row, col-1)] return [ (nr, nc) for nr, nc in potential_neighbors if 0 <= nr < get_height(image) and 0 <= nc < get_width(image) ] to_color = [location] visited = {location} while to_color: this_cell = to_color.pop(0) set_pixel(image, *this_cell, new_color) for neighbor in get_neighbors(this_cell): if (neighbor not in visited and get_pixel(image, *neighbor) == original_color): to_color.append(neighbor) visited.add(neighbor)
Finding a Path Through a Maze
The same agenda-based exploration pattern from flood fill can find a path through a maze. Instead of coloring pixels, we search for a route from start to goal.
Key changes from flood fill:
Track predecessors — for each discovered cell, record which cell led to it
Stop when the goal is reached
Reconstruct the path by following predecessors back from goal to start
The algorithm explores outward from the start, expanding through open (white) cells and avoiding walls, until the goal is found. The visited set prevents revisiting cells, just like in flood fill.