A stack hands back the newest thing. A queue hands back the oldest: whoever has waited longest goes first. Change that one rule and a different family of problems opens up. The most important of them is finding the shortest way from one place to another, through a maze, across a board, or along a chain of friends. This module builds that search from nothing, and shows that it is the same dozen lines every time.
Before this, you can: use a list as a stack and guard an empty one; keep a grid as a list of lists, and use pairs as keys of a dictionary or members of a set; write a function from its contract and test it with asserts.
By the end you will be able to use a queue, say why a list makes a poor one, search a grid ring by ring, mark places at the right moment, build a map of distances, recover the shortest path by walking back, run the same search on things that are not grids, and start it from several places at once.
Before you read on, decide what this prints:
waiting = ["Ana", "Ben", "Chen"]
print(waiting.pop(), waiting.pop(0))
Chen Anapop() takes from the end: the newest, as a stack does. pop(0) takes from the front: the oldest. Ana joined first, and a queue serves her first.
A queue has two operations. Something joins at the back. Something leaves from the front. Nothing else is allowed: no jumping the line, no leaving from the middle.
queue = []
queue.append("Ana")
queue.append("Ben")
queue.append("Chen")
first = queue.pop(0)
queue.append("Dev")
print(first, queue)
Ana ['Ben', 'Chen', 'Dev']The order is first in, first out. It is the order of a line at a shop, of documents sent to a printer, and of anything that should be dealt with in the order it arrived.
A list is a good stack and a poor queue. Its items sit in numbered places, starting at 0. Take away the item at position 0 and every other item has to move down one place to close the gap. With five items that is four moves. With a million it is nearly a million, for every single item that leaves.
Python has a structure made for this job, the deque (said "deck", short for double-ended queue). It gives up an item from either end without moving the others.
from collections import deque
queue = deque()
queue.append("Ana")
queue.append("Ben")
queue.append("Chen")
print(queue.popleft(), queue.popleft(), len(queue))
Ana Ben 1append joins at the back, as for a list. popleft leaves from the front. deque(["Ana", "Ben"]) makes one that already holds some items, and while queue: and len(queue) work as they do for a list. From here on, a queue is always a deque.
Here is a small maze. # is a wall and . is open floor. You start at the top left corner and may step up, down, left or right.
. . . #
. # . .
. . . .
Which cells can you reach, and how soon? Think of dropping a stone in a pond: the ripple reaches everything one step away, then everything two steps away, and so on. A queue produces exactly that order. Put the start in the queue. Then, over and over: take the cell at the front, and add to the back every neighbour of it that has not been seen before.
from collections import deque
def neighbours(grid, cell):
row, col = cell
result = []
for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if r >= 0 and r < len(grid) and c >= 0 and c < len(grid[0]) and grid[r][c] != "#":
result.append((r, c))
return result
def search_order(grid, start):
order = []
seen = {start}
queue = deque([start])
while queue:
cell = queue.popleft()
order.append(cell)
for step in neighbours(grid, cell):
if step not in seen:
seen.add(step)
queue.append(step)
return order
maze = ["...#",
".#..",
"...."]
print(search_order(maze, (0, 0)))
[(0, 0), (1, 0), (0, 1), (2, 0), (0, 2), (2, 1), (1, 2), (2, 2), (1, 3), (2, 3)]A cell is a pair, (row, column). neighbours gives the cells you can step to: the four around it, less any that are off the grid or walls.
Read the order. First the start. Then (1, 0) and (0, 1), the two cells one step away. Then (2, 0) and (0, 2), two steps away. Then three cells at three steps, and so on. Cells come out in rings because of the queue: a cell found later always stands behind every cell found earlier, and a cell is found by a cell one ring nearer the start.
This is breadth-first search. Use a stack where the queue is, and the same code runs off down one corridor as far as it will go before trying another. It still visits everything, but not in order of distance.
seen is the set of cells that have ever been put in the queue. The line that adds to it sits beside the line that adds to the queue, and that placing is the one thing in this function that is easy to get wrong.
Suppose a cell were marked as seen only when it left the queue. Between joining and leaving it is not yet marked, so each of its other neighbours would add it again. In a maze of corridors that happens rarely and nobody notices. On open ground every cell has several neighbours, the copies make copies, and for a long while the queue grows faster than it empties. The search does end, because the set of seen cells keeps growing and there are only so many cells. But the work multiplies with the size of the grid: on a floor of twelve by twelve it is already more than a program is given time for. The answers have not changed. The program has become too slow to give them.
The rule: mark a place at the moment it joins the queue. Then every place joins once, leaves once, and the whole search does work in step with the number of places, by the argument you met in Stacks: each item is added once and removed once.
The ring a cell is in is its distance from the start, in steps. To record it, keep a dictionary in place of the set: it says which cells have been seen, as the set did, and what number each one got.
def distances(grid, start):
steps = {start: 0}
queue = deque([start])
while queue:
cell = queue.popleft()
for step in neighbours(grid, cell):
if step not in steps:
steps[step] = steps[cell] + 1
queue.append(step)
return steps
far = distances(maze, (0, 0))
print(far[(2, 3)], far[(1, 2)], (0, 3) in far)
5 3 FalseA cell gets its number when it joins the queue: one more than the cell it was reached from. The wall at (0, 3) never joins, so it has no number.
Why is that number the shortest distance, and not just some distance? Because of the rings. Every cell at distance 1 joins the queue before any cell at distance 2 leaves it, and so on outwards. When a cell is first reached, it is reached from a cell in the nearest ring that touches it. Any other way of reaching it comes later, from a ring at least as far out, and cannot be shorter. The first time is the best time, which is why a cell that already has a number is never given another.
This argument leans on one fact: every step costs the same. If some steps were longer than others, a way with more steps could be shorter, and this search would be the wrong tool.
A distance says how far, not which way. For the path, remember one more thing about each cell: the cell it was reached from.
def came_from_map(grid, start):
came_from = {start: None}
queue = deque([start])
while queue:
cell = queue.popleft()
for step in neighbours(grid, cell):
if step not in came_from:
came_from[step] = cell
queue.append(step)
return came_from
came_from = came_from_map(maze, (0, 0))
print(came_from[(2, 3)], came_from[(1, 3)], came_from[(0, 0)])
(2, 2) (1, 2) Nonecame_from[(2, 3)] is the cell from which (2, 3) was first reached. Ask the same of that cell, and of the answer, and you walk back along a shortest way until you arrive at the start, whose entry is None.
cell = (2, 3)
path = []
while cell is not None:
path.append(cell)
cell = came_from[cell]
path.reverse()
print(path)
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3)]The walk collects the cells from the goal back to the start, so the list is turned round at the end. Six cells: five steps, which agrees with the distance.
This maze has more than one way of five steps to that corner: another goes along the top and down the right-hand side. The search gives the one it happened to find first, which depends on the order neighbours lists the four directions. Every way it can give is a shortest one. Which shortest one is an accident.
One search answers the question for every goal at once. And if the goal is not a key of came_from, it was never reached: there is no way to it.
Nothing in the search knows that it is looking at a maze. It needs a place to start, and a way of asking "where can I go from here?". Give it a different answer to that question and it searches something else.
knows = {"Ana": ["Ben", "Chen"], "Ben": ["Ana", "Dev"], "Chen": ["Ana"],
"Dev": ["Ben", "Eli"], "Eli": ["Dev"], "Fay": []}
def steps_from(knows, person):
steps = {person: 0}
queue = deque([person])
while queue:
name = queue.popleft()
for friend in knows[name]:
if friend not in steps:
steps[friend] = steps[name] + 1
queue.append(friend)
return steps
print(steps_from(knows, "Ana"))
{'Ana': 0, 'Ben': 1, 'Chen': 1, 'Dev': 2, 'Eli': 3}A place is now a name, and its neighbours are the people it knows. Eli is three introductions from Ana, and Fay, whom nobody knows, is never reached.
A square on a chessboard, with the squares a knight can jump to. A word, with the words that differ from it by one letter. Whenever you can say what a place is and what its neighbours are, and every step counts the same, the shortest way is this search.
Two fire stations serve a town. How far is each house from its nearest station? You could search from each station and keep the smaller number for every house. There is a neater way: put both stations in the queue before the loop begins, each with the number 0.
def nearest(grid, starts):
steps = {}
queue = deque()
for start in starts:
steps[start] = 0
queue.append(start)
while queue:
cell = queue.popleft()
for step in neighbours(grid, cell):
if step not in steps:
steps[step] = steps[cell] + 1
queue.append(step)
return steps
near = nearest(maze, [(0, 0), (2, 3)])
print(near[(1, 2)], near[(2, 0)], near[(1, 3)])
2 2 1The loop is unchanged. The two ripples spread together, and each cell is claimed by whichever reaches it first, which is the nearer one. (1, 2) was three steps from the corner alone; with the second start it is two.
You will trace a queue beside a stack, count what the front of a list costs, follow the rings on a small grid, and see what marking too late does. You will work out a map of distances by hand, count the rooms of a floor plan, repair a search that is right on small plans and too slow to finish on large ones, turn a shortest way into directions for a robot, and search a circle of friends given as pairs. Then four assignments: sprinklers that all start at once, a knight crossing a chessboard, a path finder that finds a way but not the shortest, and one problem that does not tell you a search is the way in.