Skip to main content

Lesson 5-3 · From Pencil to Program

Module 5 · Pathfinding Around Obstacles

Lesson 5-3 · From Pencil to Program

60–70 minGraphs and dictionariesThe grid in code
👩‍🏫

Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.

Lesson 5-2 ended with a review of breadth-first search in plain words. Before it can become Python, there's one more question: what does the program have to remember to do each part of it? Answering it brings in a new way to see the grid, a graph, and a new kind of Python data, the dictionary. By the end of the lesson the grid is in robot.py.

Learning Objectives

By the end of this lesson you will be able to:

  • Say, for each part of the algorithm, what the program has to remember to do it
  • Describe the grid as a graph: nodes, edges and neighbors, and what blocking a node removes
  • Create a dictionary, look up a value by key, and check for a key with in
  • Build build_grid_graph(rows, cols) in a new GRID GRAPH section of robot.py, one printed step at a time

What the program has to remember​

Go back through Lesson 5-2's review of the algorithm and ask, for each part, what the program has to know to do it. Every answer is something you kept on paper:

Part of the algorithmThe question it asksOn paperIn the program
Look at each open neighbor"Which open intersections are next to this one?"The grid drawingA graph, this lesson
Look at each open neighbor"Which intersections are blocked?"The X'sA list, BLOCKED (Lesson 5-4)
Number each neighbor; skip it if it already has a number; walk downhill"What is this intersection's number? Does it have one yet?"The numbers on the gridA dictionary, distance (Lesson 5-5)
Take from the front, add to the end"Which one is next?"The to-visit listA list (Lesson 5-5)
Write down each intersection on the walk downhill"What is the route so far?"The path you wrote downA list, path (Module 4)

Three of these are lists, which you know from Module 4. The other two are looked up by intersection: you have (1, 2) and want its neighbors, or its number. A list finds things by position (path[0]), not by what they are. That needs something new. First, though, the program needs the grid written down precisely.

The grid as a graph​

The step "for each open neighbor" needs to know exactly which intersections are joined. Computer scientists write that down as a graph: a set of nodes (points) connected by edges (links). A road map is one (intersections and streets), so is a social network (people and friendships), and so is airline routes (airports and flights). A graph captures what connects to what. (In computer science, "graph" never means a bar chart.)

Our grid is a graph. Every intersection is a node, named by its coordinate like (1, 2). Every line between adjacent intersections is an edge. A node's neighbors are the nodes its edges lead to.

The 3 by 3 grid drawn as a graph: nine nodes labeled (x, y) with (0, 0) at the bottom-left, joined by edges to their neighbors left, right, below and above. The four corner nodes have 2 neighbors, the four edge nodes 3, and the center node 4.
Every intersection is a node; every line between neighbors is an edge. The shading counts neighbors.

A corner has 2 neighbors, an edge node 3, an interior node 4.

Knowledge Check

On a 3×3 grid, how many neighbors does the interior node (1,1) have?

On paper, an X was never numbered and never anyone's neighbor. In the graph that means a blocked intersection is removed: the node and all its edges. Block (1,1):

The 3 by 3 graph with (1, 1) blocked: the node is crossed out and its four edges are removed, so the four nodes that touched it, (0, 1), (1, 0), (1, 2) and (2, 1), have each lost a neighbor.
Blocking (1, 1) removes the node and its four edges.

Blocking one node changes its neighbors too: (0,1), (1,0), (1,2) and (2,1) have each lost one. That's the second half people forget, and it matters: a search that still sees an edge into (1,1) will happily step into the wall.

Knowledge Check

After (1,1) is blocked, how many neighbors does (0,1) have?

This lesson's skeleton​

A new section for a new kind of data. Paste it into robot.py above RUN, after the NAVIGATOR section. Like the MANHATTAN PLANNER, nothing in it drives.

# ===== GRID GRAPH =====
# The grid as a graph, in a dictionary: every intersection is
# a key, and its value is the list of neighbors it is joined
# to. The BFS PLANNER searches this graph. Starts with the
# open grid; Lesson 5-4 adds the blocked list, so a blocked
# intersection is neither a key nor anyone's neighbor.
ROWS = 4 # the grid is ROWS x COLS intersections
COLS = 4

def build_grid_graph(rows, cols):
"""Return the open grid as a dictionary: every (x, y)
maps to the list of its on-grid neighbors."""
pass

ROWS and COLS are the size of your taped grid. The function takes the size as parameters, so you can build a small 3×3 while the settings say 4×4.

Activity · Build the graph, one piece at a time​

You will grow build_grid_graph() in six small steps. Each one prints something, so before every run write down what you expect to see, then run it and compare. While you work, set the run line to

build_grid_graph(3, 3)

so it builds a 3×3 grid, small enough to check by eye. The robot stays on the desk.

Step 1 · Visit every intersection​

Replace pass with two for loops, one inside the other: the outer one over every x (range(cols)), the inner one over every y (range(rows)). Inside, print the intersection (x, y).

Before you run it: how many lines will print, and which number changes fastest, x or y?

Step 2 · List every neighbor​

Inside the inner loop, make an empty list called neighbors and append the four intersections next to (x, y): left, right, down, up, in that order (the order Lesson 5-1's trace used, so your program's paths will match the paper ones). Then print the intersection followed by its list.

Before you run it: what will (0, 0) print?

Look at your output. Every intersection got four neighbors, but the graph figure above says a corner has only 2. Circle every neighbor in your output that isn't really there. What do they have in common?

Step 3 · Throw out the ones off the grid​

A neighbor is off the grid when one of its numbers is below 0 or past the last row or column. Put an if in front of each append, so each neighbor is added only when it is on the grid. Each direction needs its own test, and each test compares just one number.

Before you run it: how many neighbors should a corner, an edge and the middle have?

Step 4 · Keep them in a dictionary​

Printing the neighbors is how you check them. BFS needs to keep them, and look them up later by intersection: "what are the neighbors of (1, 1)?" A list can't do that; it finds things by position (path[0]), not by what they are. Python's tool for looking up by name is the dictionary.

A cartoon of an open printed dictionary with four entries, each a bold word with its definition: graph, nodes and edges; motor, turns a wheel; robot, senses and acts; sensor, measures the world. Letter tabs run down the edge, and a magnifying glass hovers over the highlighted entry for sensor, where the word is labeled key and the definition is labeled value. Beside it, the same entries as a Python dictionary called glossary, with words as keys and definitions as values, and glossary of sensor giving measures the world.
The word you look up is the key; what's printed beside it is the value. Python's dictionary works the same way.

The syntax is all you need:

graph = {} # an empty dictionary
graph[(0, 0)] = [(1, 0), (0, 1)] # store: key (0, 0), value a list
print(graph[(0, 0)]) # look up: [(1, 0), (0, 1)]
print(len(graph)) # how many keys: 1

A key must be something that can't change, like a number or a tuple, so an (x, y) tuple works.

Now change your function:

  • make graph = {} before the loops
  • replace the print inside the loop with a line that stores neighbors under the key (x, y)
  • after the loops (not inside them), print len(graph), then the neighbors of (1, 1), then the neighbors of (0, 0)

Before you run it: what three lines will print?

Left: the 3 by 3 graph with (1, 1) highlighted and its four neighbors shaded. Right: the dictionary as key and value rows. Key (0, 0) maps to [(1, 0), (0, 1)]; key (0, 1) maps to [(1, 1), (0, 0), (0, 2)]; key (1, 1) maps to [(0, 1), (2, 1), (1, 0), (1, 2)]. graph[(1, 1)] jumps straight to that list.
What you just built: one entry per node, the node is the key and its neighbor list is the value.
Knowledge Check

In our graph dictionary, what are the keys and what are the values?

Step 5 · Hand the graph back, and test it​

A function that only prints is no use to BFS; it needs the graph itself. Delete the three prints, end the function with return graph, and write test_grid_graph(): build the 4×4 graph from ROWS and COLS and print the same three things. Set the run line to test_grid_graph().

Then end the test by printing the whole graph, one intersection per line. A for loop over a dictionary hands you each key in turn, and the key looks up its value:

for node in graph:
print(node, graph[node])

Before you run it: which of the first three lines change on a 4×4? How many lines does the loop print, and how many of them should have exactly 2 neighbors?

Step 6 · Ask whether a key is there​

Add these to the end of test_grid_graph() and predict each line before you run it:

print((3, 3) in graph)
print((4, 4) in graph)
print(graph[(4, 4)])

BFS uses in all the time. Its numbers will be a dictionary too, called distance: each intersection is a key, and its steps to the destination is the value. "Does this neighbor have a number yet?" is then one in. You will write it in Lesson 5-5.

Knowledge Check

Given distance = {(2,2): 0, (1,2): 1}, what does (1,2) in distance return, and what does it mean?

Optional: open it if you have time. Nothing later depends on it.

Real-world connections​

Navigation

Road maps

A navigation app stores the streets as a graph: intersections are nodes, roads are edges, and a closed road is an edge taken out.

Web

User profiles

A username maps to a profile: any user, found instantly by key.

Games

Inventories

Item name maps to quantity: "how many potions?" with no searching.

Wrap-up​

  • What does the program need to remember that a list can't look up easily? (Things found by intersection: its neighbors, and its number.)
  • What are a node, an edge, and a neighbor? (A point, a link between adjacent points, and the points a node links to.)
  • What does blocking a node remove? (The node and all its edges, so it is nobody's neighbor.)
  • How is a dictionary different from a list? (Looked up by key, not by position.)

Resources​