Module Overview · The Big Picture
The Big Picture
Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.
Here's the problem this module solves: get the robot from where it starts to a destination on the grid, all by itself.
A taxi in Manhattan has the same problem. Buildings fill every block, so it can't drive straight from A to B; it drives along the streets, 2 blocks east, then 3 blocks north. The robot is the same: it can only drive along the tape. So the route comes from one rule:
Go east or west until we are at the destination avenue, then north or south until we're at the destination street.
That's the whole algorithm. It's called the Manhattan algorithm.
Learning Objectives
By the end of this overview you will be able to:
- Describe the problem Module 4 solves: drive to a destination on its own, then to several in a row
- Split a complex problem into simpler parts: plan the route first, test it with no robot, then drive it
- Name the planner (
compute_manhattan_path), the driver (drive_path), and the list of (x, y) coordinates between them - Say what building a program top-down means: the main program first, with stand-ins for the parts below it
Breaking down a complex problem
Now you know how to find the route. Getting the robot to do it is the next problem.
Street and avenue names are hard to use in a robot program, so we number each intersection instead: a column number, x, and a row number, y. The taxi's trip becomes (1, 1) to (3, 4).
"Drive over there" sounds like one job, but it's too much to get right in one go. One way to tackle a complex problem is to break it into simpler sub-problems and solve each one. That's called problem decomposition (or top-down design).
Discuss · How would you split it?
- Before the robot moves, could you write down every intersection it will drive through?
- How could you check that list is right, without the robot?
- Once the list is right, what's left for the robot to do?
Here is that split, one level at a time:
Plan first, then drive
That's one way to split the problem, and the one this module uses: plan the whole route first, then drive it.
- Plan. The planner,
compute_manhattan_path, works out the whole route. It never moves the robot, so you can test it without a robot: print the route and check it against the grid. - Drive. Once the plan is right, the driver,
drive_path, takes the plan and drives it, then reports where the robot ended up.
Each intersection is an (x, y) pair, so the plan is a list of coordinates, the one
thing the two functions share.
One job each is called separation of concerns, and it makes bugs easy to find: a wrong route is a planner problem; a wrong turn is a driver problem.
Why plan the whole route first, as its own function, before writing the code that drives?
From one destination to several
Picture a delivery driver with packages for several houses, each with its own address. The driver plans a route to the first house and drives it, then plans from there to the next, until every package is delivered.
The robot does the same. Once it can reach one destination, several is just a loop: plan from where it is, drive, repeat.
Build it from the top down
You'll build this program top-down: the top of the tree first, then one level at a time. The main program comes first, in the very next lesson, and it runs the day you write it, because every part below it starts as a stub: a stand-in function that does just enough for the program to run, and prints what the real one would do.
Then you swap the stubs for real functions, one per lesson, and run the program after every change. The printout tells you right away whether it still works. The robot only drives in Lesson 4-6, so you never have to wonder whether a bug is in your code or in the robot.
The Python arrives the same way. A position like (1, 1) is a Python tuple, and a
route is a Python list. You won't study them first: each lesson teaches the piece of
tuples and lists it needs, right where the program needs it. Lesson 4-7 puts it all
together.
The module at a glance
- 4-1: the main program, with stubs
- 4-2: the planner, part 1: a path that grows
- 4-3: the planner, part 2: every direction, and tests
- 4-4: the driver
- 4-5: turning
- 4-6: the stubs out, the robot on the grid
- 4-7: tuples and lists: what you now know
Wrap-up
- What problem does Module 4 solve? (Drive the robot from where it starts to a destination on its own, then to several destinations in a row.)
- Why plan first? (The planner never moves the robot, so its list of coordinates can be printed and checked with no robot at all. Then the driver only has to follow a plan you already trust.)
- What are the two halves and their jobs? (
compute_manhattan_pathplans;drive_pathdrives.) - What is a stub? (A stand-in function that lets the program run before the real function is written.)