A First Taste of Algorithms · Lab 5: Dots and Lines

3. A maze is a graph wearing a costume

Build a maze as a list of strings — # wall, . floor, S start, E exit:

maze = [
    "#########",
    "#S..#...#",
    "#.#.#.#.#",
    "#.#...#.#",
    "#.###.#.#",
    "#.....#E#",
    "#########",
]

Where is the graph? Every floor cell is a vertex; two floor cells side-by-side share an edge. We never build the dictionary — the maze answers neighbor queries on demand (look up, down, left, right; a graph is anywhere that can answer “who are your neighbors?”).

A cell’s name is its (row, column) position — and here the second tool arrives with its debt. Positions must live in the seen set and the dist notebook, and Python’s rule is that set members and notebook keys must be unchangeable things; a list, which can be appended to and edited, is not allowed. The unchangeable list is called a tuple: written (5, 7) with round brackets, indexed like a list, frozen forever at birth. Positions are tuples because positions must be lookupable.

def maze_bfs(maze, start):
    queue = [start]
    head = 0
    seen = {start}
    dist = {start: 0}
    while head < len(queue):
        here = queue[head]
        head = head + 1
        r = here[0]
        c = here[1]
        for next_pos in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
            if maze[next_pos[0]][next_pos[1]] != "#":
                if next_pos not in seen:
                    seen.add(next_pos)
                    dist[next_pos] = dist[here] + 1
                    queue.append(next_pos)
    return dist

distances = maze_bfs(maze, (1, 1))      # S is at row 1, column 1
print(distances[(5, 7)])                # E is at row 5, column 7

The ripple’s answer is the shortest path length in steps. Verify it by tracing the maze with a pencil — then design your own maze (keep the # border, it is what spares the code from falling off the edge) with at least two routes from S to E of different lengths, and confirm BFS reports the shorter.

4. The one word

The chapter claimed BFS and DFS differ by which end of the line you serve. Test the claim with the smallest possible edit — serve the back:

def dfs(graph, start):
    line = [start]
    seen = {start}
    order = []
    while len(line) > 0:
        here = line.pop()               # .pop(): remove and return the LAST item
        order.append(here)
        for neighbor in graph[here]:
            if neighbor not in seen:
                seen.add(neighbor)
                line.append(neighbor)
    return order

print(dfs(hallways, "gym"))
print(bfs(hallways, "gym"))

(.pop() is the one new move: take the last item off a list. A line served from the back is called a stack — the call stack of Chapter 3 is one, which is why the chapter could say DFS is recursion.) Compare the two visit orders on the school, then on your maze (adapt as in §3): the ripple sweeps level by level; the thread plunges. Same dots, same lines, opposite temperaments, one word.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses