How many liters is a pitcher of water?

These puzzles are used in some IQ tests, so many people come across them in schools. To solve the problem, you must pour water from one pitcher to another. In this particular problem, there are six steps in the shortest solution:

1. Fill the three-liter pitcher from the river.
2. Pour the three liters from the three-liter pitcher into the seven-liter pitcher.
3. Fill the three-liter pitcher from the river again.
4. Pour the three liters from the three-liter pitcher into the seven-liter pitcher (which now contains six liters).
5. Fill the three-liter pitcher from the river yet again.
6. Pour from the three-liter pitcher into the seven-liter pitcher until the latter is full. This requires one liter, since the seven-liter pitcher had six liters of water after step 4. This step leaves two liters in the three-liter pitcher.

This example is a relatively hard pitcher problem, since it requires six steps in the solution. On the other hand, it doesn't require pouring water back into the river, and it doesn't have any unnecessary pitchers. An actual IQ test has several such problems, starting with really easy ones like this:

You are at the side of a river. You have a three-liter pitcher and a seven-liter pitcher. The pitchers do not have markings to allow measuring smaller quantities. You need four liters of water. How can you measure four liters?

and progressing to harder ones like this:

You are at the side of a river. You have a two-liter pitcher, a five-liter pitcher, and a ten-liter pitcher. The pitchers do not have markings to allow measuring smaller quantities. You need one liter of water. How can you measure one liter?

The goal of this project is a program that can solve these problems. The program should take two inputs, a list of pitcher sizes and a number saying how many liters we want. It will work like this:

? pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4
? pour [2 5 10] 1
Pour from river to 5
Pour from 5 to 2
Pour from 2 to river
Pour from 5 to 2
Final quantities are 2 1 0

How do people solve these problems? Probably you try a variety of special-purpose techniques. For example, you look at the sums and differences of the pitcher sizes to see if you can match the goal that way. In the problem about measuring four liters with a three-liter pitcher and a seven-liter pitcher, you probably recognized right away that 7−3=4. A more sophisticated approach is to look at the remainders when one pitcher size is divided by another. In the last example, trying to measure one liter with pitchers of two, five, and ten liters, you might notice that the remainder of 5/2 is 1. That means that after removing some number of twos from five, you're left with one.

Such techniques might or might not solve any given pitcher problem. Mathematicians have studied ways to solve such problems in general. To a mathematician, a pitcher problem is equivalent to an algebraic equation in which the variables are required to take on integer (whole number) values. For example, the problem at the beginning of this chapter corresponds to the equation

In this equation, x represents the number of times the three-liter pitcher is filled and y represents the number of times the seven-liter pitcher is filled. A positive value means that the pitcher is filled from the river, while a negative value means that it's filled from another pitcher.

An equation with two variables like this one can have infinitely many solutions, but not all the solutions will have integer values. One integer-valued solution is x=3 and y = -1. This solution represents filling the three-liter pitcher three times from the river (for a total of nine liters) and filling the seven-liter pitcher once from the three-liter pitcher. Since the seven-liter pitcher is bigger than the three-liter pitcher, it has to be filled in stages. Do you see how this analysis corresponds to the sequence of steps I gave earlier?

An equation with integer-valued variables is called a Diophantine equation. In general, a Diophantine equation will have infinitely many solutions, but they won't all be practical as solutions to the original problem. For example, another solution to the equation we've been considering is x = -4 and y=2. This solution tells us to fill the seven-liter pitcher from the river twice, and the three-liter pitcher from the seven-liter pitcher four times. Here's how that works out as a sequence of steps:

1. Fill the seven-liter pitcher from the river.
2. Fill the three-liter pitcher from the seven-liter pitcher. (This leaves four liters in the seven-liter pitcher.)
3. Empty the three-liter pitcher into the river.
4. Fill the three-liter pitcher from the seven-liter pitcher. (This leaves one liter in the seven-liter pitcher.)
5. Empty the three-liter pitcher into the river.
6. Pour the contents of the seven-liter pitcher (one liter) into the three-liter pitcher.
7. Fill the seven-liter pitcher from the river (for the second and last time).
8. Fill the three-liter pitcher (which already had one liter in it) from the seven-liter pitcher. (This leaves five liters in the seven-liter pitcher.)
9. Empty the three-liter pitcher into the river.
10. Fill the three-liter pitcher from the seven-liter pitcher. This leaves the desired two liters in the seven-liter pitcher.

This solution works, but it's more complicated than the one I used in the first place.

One way to solve Diophantine equations is graphically. For example, consider the problem about measuring one liter of water with pitcher capacities two, five, and ten liters. It turns out that the ten-liter pitcher is not actually needed, so let's forget it for now and consider the simpler but equivalent problem of using just the two-liter and the five-liter pitchers. This problem gives rise to the equation

For the moment, never mind that we are looking for integer solutions. Just graph the equation as you ordinarily would. The graph will be a straight line; probably the easiest way to draw the graph is to find the x-intercept (when y=0, 2x=1 so x=1/2) and the y-intercept (when x=0, y=1/5).

Once you've drawn the graph, you can look for places where the line crosses the grid points of the graph paper. In this case, two such points of intersection are (-2,1) and (3,-1). The first of these points represents the solution shown earlier, in which the five-liter pitcher is filled from the river and then used as a source of water to fill the two-liter pitcher twice. The second integer solution represents the method of filling the two-liter pitcher from the river three times, then pouring the water from the two-liter pitcher to the five-liter pitcher each time. (On the third such pouring, the five-liter pitcher fills up after only one liter is poured, leaving one liter in the two-liter pitcher.) What about the original version of this problem, in which there were three pitchers? In this case, we have a Diophantine equation with three variables:

The graph of this equation is a plane in a three-dimensional coordinate system. An example of a solution point that uses all three pitchers is (-2,-1,1). How would you interpret this as a series of pouring steps?

By the way, not all pitcher problems have solutions. For example, how could you measure one liter with a two-liter pitcher and a ten-liter pitcher? The answer is that you can't; since both pitchers hold an even number of liters, any amount of water measurable with them will also be even.*

*You can find a computational algorithm to solve (or show that there are no solutions to) any linear Diophantine equation with two variables on page 50 of Courant and Robbins, What Is Mathematics? (Oxford University Press, 1941).

Tree Search

My program does not solve pitcher problems by manipulating Diophantine equations. Instead, it simply tries every possible sequence of pouring steps until one of the pitchers contains the desired amount of water. This method is not feasible for a human being, because the number of possible sequences is generally quite large. Computers are better than people at doing large numbers of calculations quickly; people have the almost magical ability to notice the one relevant pattern in a problem without trying all the possibilities. (Some researchers attribute this human ability to "parallel processing"--the fact that the human brain can carry on several independent trains of thought all at once. They are beginning to build computers designed for parallel processing, and hope that these machines will be able to perform more like people than traditional computers.)

The possible pouring steps for a pitcher problem form a tree. The root of the tree is the situation in which all the pitchers are empty. Connected to the root are as many branches as there are pitchers; each branch leads to a node in which one of the pitchers has been filled from the river. Each of those nodes has several branches connected to it, corresponding to the several possible pouring steps. Here is the beginning of the tree for the case of a three-liter pitcher and a seven-liter pitcher. Each node is represented in the diagram by a list of numbers indicating the current contents of the three-liter pitcher and the seven-liter pitcher; for example, the list

to process :node
if emptyp last :node [print :node]
end

Actually, I have simplified this tree by showing only the meaningful pouring steps. The program must consider, and of course reject, things like the sequence

1. Fill the three-liter pitcher from the river.
2. Empty the three-liter pitcher into the river.

and individual meaningless steps like pouring from a pitcher into itself, pouring from an empty pitcher, and pouring into a full pitcher. For a two-pitcher problem there are three possible sources of water (the two pitchers and the river) and three possible destinations, for a total of nine possible pouring steps. Here is the top of the full tree:

At each level of the tree, the number of nodes is multiplied by nine. If we're trying to measure two liters of water, a six-step problem, the level of the tree at which the solution is found will have 531,441 nodes! You can see that efficiency will be an important consideration in this program.

In some projects, a tree is represented within the program by a Logo list. That's not going to be the case in this project. The tree is not explicitly represented in the program at all, although the program will maintain a list of the particular nodes of the tree that are under consideration at a given moment. The entire tree can't be represented as a list because it's infinitely deep! In this project, the tree diagram is just something that should be in your mind as a model of what the program is doing: it's searching through the tree, looking for a node that includes the goal quantity as one of its numbers.

Depth-first and Breadth-first Searching

Many programming problems can be represented as searches through trees. For example, a chess-playing program has to search through a tree of moves. The root of the tree is the initial board position; the second level of the tree contains the possible first moves by white; the third level contains the possible responses by black to each possible move by white; and so on.

There are two general techniques for searching a tree. These techniques are called depth-first search and breadth-first search. In the first technique, the program explores all of the "descendents" of a given node before looking at the "siblings" of that node. In the chess example, a depth-first search would mean that the program would explore all the possible outcomes (continuing to the end of the game) of a particular opening move, then go on to do the same for another opening move. In breadth-first search, the program examines all the nodes at a given level of the tree, then goes on to generate and examine the nodes at the next level. Which technique is more appropriate will depend on the nature of the problem.

In a programming language like Logo, with recursive procedures and local variables, it turns out that depth-first search leads to a simpler program structure. Suppose that we are given an operation called

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

In this program, the structure of the tree is reflected in the structure of recursive invocations of

to process :node
if emptyp last :node [print :node]
end

It might be worthwhile to consider a specific example of how this program works. One of the suggested activities in Chapter 11 was to write a program that takes a telephone number as input and prints out all possible spellings of that number as letters. (Each digit can represent any of three letters. To keep things simple, I'm going to ignore the problem of the digits zero and one, which don't represent any letters on telephone dials in the United States.) Here is a partial picture of the tree for a particular telephone number. Each node contains some letters and some digits. (In the program, a node will be represented as a Logo list with two members, a word of letters and a word of digits.) The root node is all digits; the "leaf" nodes will be all letters.

The operation

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

The top-level procedure has to turn a number into a root node and invoke a depth-first search:

to spell :number
depth.first list " :number
end

What about the

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

» Try this program. To get the tree illustrated above, use the instruction

spell 8689827

Then try again, but investigate the order in which the program searches the nodes of the tree by using a different version of

to process :node
if emptyp last :node [print :node]
end

to process :node
print :node
end

This will let you see the order in which the program encounters the nodes of the tree.

Writing a breadth-first search is a little more complicated because the program must explicitly arrange to process all the nodes of a given level before processing those at the next level. It keeps track of the nodes waiting to be processed in a queue, a list in which new nodes are added at the right and the next node to be processed is taken from the left. Here is the program:

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

This breadth-first search program uses the same

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

spell 8689827

spell 8689827

spell 8689827

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

The telephone number speller is an unusual example of a tree-search program for two reasons. First, the tree is finite; we know in advance that it extends seven levels below the root node, because a telephone number has seven digits. Second, the goal of the program requires searching the entire tree. It's more common that the program is looking for a solution that's "good enough" in some sense, and when a solution is found, the program stops looking. For example, in the pitcher problem program, once we find a sequence of steps to measure the desired amount of water, we don't care if there is also a second way to do it.

For the pitcher problem solver, I decided that a breadth-first search is appropriate. The main reason is that I wanted to present the shortest possible solution. To do that, first I see if any one-step sequences solve the problem, then I see if any two-step sequences solve it, and so on. This is a breadth-first order.

Data Representation

At first, I thought that I would represent each node of the tree as a list of numbers representing the contents of the pitchers, as in the diagram I showed earlier. I called this list of quantities a state. This information is enough to be able to generate the children of a node. Later, though, I realized that when I find a winning solution (one that has the goal quantity as one of the quantities in the state list) I want to be able to print not only the final quantities but also the sequence of pouring steps used to get there. In a depth-first search, this information is implicitly contained in the local variables of the procedure invocations leading to the winning solution. In a breadth-first search, however, the program doesn't keep track of the sequence of events leading to a given node. I had to remember this information explicitly.

The solution I chose was to have an extra member in the list representing a state, namely a list of pourings. A pouring is a list of two numbers representing the source and the destination of the water being poured. Zero represents the river; numbers greater than zero are pitcher numbers. (A pitcher number is not the same as the size of the pitcher. If you enter the instruction

pour [2 5 10] 1

then the two-liter pitcher is pitcher number 1, the five-liter is number 2, and the ten-liter is number 3.) The list of pourings is the first member of the expanded state list; pourings are added to that list at the front, with

spell 8689827

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

the extended state information for the final solution state is

to depth.first :node
process :node
foreach (children :node) "depth.first
end

In this list, the sublist

to process :node
print :node
end

to process :node
print :node
end

Abstract Data Types

Up to this point I've continued to call this expanded data structure a state. That's what I did in the program, also, until I found that certain procedures needed the new version, while other procedures dealt with what I had originally considered a state, with only the final quantities included in the list. As a result, my program had local variables named

to process :node
print :node
end

to process :node
print :node
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

while

to process :node
print :node
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

The trouble with using a list of lists of lists in a program is that it can become very complicated to keep track of all the uses of selectors like

to process :node
print :node
end

spell 8689827

to process :node
print :node
end

to process :node
print :node
end

to process :node
print :node
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

assuming that we have a procedure

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

spell 8689827

to process :node
print :node
end

spell 8689827

spell 8689827

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

spell 8689827

to process :node
print :node
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

That unreadable instruction shown earlier would now be written this way:

to depth.first :node
process :node
foreach (children :node) "depth.first
end

At first glance this may not seem like much of an improvement, since the new names are longer and less familiar than the old ones. But we can now read the instruction and see that it calls a constructor

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

» Invent a constructor and selectors for a move data type.

to breadth.first :root breadth.descend (list :root) end to breadth.descend :queue if emptyp :queue [stop] process first :queue breadth.descend sentence (butfirst :queue) ~ (children first :queue) end 9 as a Combiner

The general breadth-first search program I showed earlier contains this procedure:

to depth.first :node
process :node
foreach (children :node) "depth.first
end

The most common use of

pour [2 5 10] 1

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

pour [2 5 10] 1

pour [2 5 10] 1

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

Recursive procedures that manipulate non-flat lists generally use

spell 8689827

to process :node
print :node
end

spell 8689827

pour [2 5 10] 1

pour [2 5 10] 1

to process :node
if emptyp last :node [print :node]
end

to process :node
if emptyp last :node [print :node]
end

Finding the Children of a Node

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

spell 8689827

spell 8689827

to depth.first :node
process :node
foreach (children :node) "depth.first
end

The predicate

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

to depth.first :node
process :node
foreach (children :node) "depth.first
end

If

spell 8689827

Here is a simplified version of

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

To allow

spell 8689827

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

The version of

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to process :node
print :node
end

to process :node
print :node
end

You should be wondering, at this point, why

to depth.first :node
process :node
foreach (children :node) "depth.first
end

pour [2 5 10] 1

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to process :node
if emptyp last :node [print :node]
end

pour [2 5 10] 1

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

This also eliminates the use of

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

pour [2 5 10] 1

The reason for the use of

pour [2 5 10] 1

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

pour [2 5 10] 1

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

With this version of

to depth.first :node
process :node
foreach (children :node) "depth.first
end

pour [2 5 10] 1

to depth.first :node
process :node
foreach (children :node) "depth.first
end

To create the variable

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to process :node
if emptyp last :node [print :node]
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

Here we are taking advantage of a feature of

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

Computing a New State

The job of

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

The new state is harder to compute. There are four cases.

1. If the destination is the river, then the thing to do is to empty the source pitcher.
2. If the source is the river, then the thing to do is to fill the destination pitcher to its capacity.
3. If source and destination are pitchers and the destination pitcher has enough empty space to hold the contents of the source pitcher, then the thing to do is to add the entire contents of the source pitcher to the destination pitcher, setting the contents of the source pitcher to zero.
4. If both are pitchers but there is not enough room in the destination to hold the contents of the source, then the thing to do is fill the destination to its capacity and subtract that much water from the source.

Here is the procedure to carry out these computations:

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

Each instruction of this procedure straightforwardly embodies one of the four numbered possibilities.

Helper procedures are used to compute a new list of amounts of water, replacing either one or two old values from the previous list:

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

to depth.first :node
process :node
foreach (children :node) "depth.first
end

Remember that

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

If the destination is the river, the output state is the same as the input state except that the pitcher whose number is

to process :node
print :node
end

More Data Abstraction

The instructions in

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to children :node
if emptyp last :node [output []]
output map [child (first :node) ? (butfirst last :node)] ~
           letters first last :node
end

to letters :digit
output item :digit [[] abc def ghi jkl mno prs tuv wxy]
end

to child :letters :this :digits
output list (word :letters :this) :digits
end

?show children [tnt 9827]
[[tntw 827] [tntx 827] [tnty 827]]

To underscore the importance of data abstraction, here is what

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

to spell :number
depth.first list " :number
end

Printing the Results

When

spell 8689827

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to spell :number
depth.first list " :number
end

Efficiency: What Really Matters?

The

to process :node
if emptyp last :node [print :node]
end

to spell :number
depth.first list " :number
end

would strain the memory capacity of many computers as well as taking forever to run!

When you're trying to make a program more efficient, the easiest improvements to figure out are not usually the ones that really help. The easy things to see are details about the computation within some procedure. For example, the

to breadth.first :root
breadth.descend (list :root)
end

to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) ~
                         (children first :queue)
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to spell :number
depth.first list " :number
end

This expression represents the amount of empty space in the destination pitcher. Perhaps it would be faster to compute this number only once, and store it in a variable? I haven't bothered trying to decide, because the effect is likely to be small either way. Improving the speed of computing each new node is much less important than cutting down the number of nodes we compute. The reason is that eliminating one node also eliminates all its descendants, so that the effect grows as the program moves to lower levels of the tree.

The best efficiency improvement is likely to be a complete rethinking of the algorithm. For example, I've mentioned that a numerical algorithm exists for solving two-variable linear Diophantine equations. This algorithm would be a much faster way to solve two-pitcher problems than even the best tree search program. I haven't used that method because I wanted a simple program that would work for any number of pitchers, but if I really had to solve such problems in practice, I'd use the Diophantine equation method wherever possible.

Avoiding Meaningless Pourings

We have already modified

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to spell :number
depth.first list " :number
end

The local variable

to process :node
print :node
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to process :node
print :node
end

The important changes are the two new

to depth.first :node
process :node
foreach (children :node) "depth.first
end

To underscore what I said earlier about what's important in trying to improve the efficiency of a program, notice that these added tests slow down the process of computing each new node, and yet the overall effect is beneficial because the number of nodes is dramatically reduced.

Eliminating Duplicate States

It's relatively easy to find individual pourings that are absurd. A harder problem is to avoid sequences of pourings, each reasonable in itself, that add up to a state we've already seen. The most blatant examples are like the one I mentioned a while back about filling a pitcher from the river and then immediately emptying it into the river again. But there are less blatant cases that are also worth finding. For example, suppose the problem includes a three-liter pitcher and a six-liter pitcher. The sequence

to spell :number
depth.first list " :number
end

leads to the same state (

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to spell :number
depth.first list " :number
end

The latter isn't an absurd sequence of pourings, but it's silly to pursue any of its children because they will have the same states as the children of the first sequence, which is one step shorter. Any solution that could be found among the descendents of the second sequence will be found one cycle earlier among the descendents of the first.

To avoid pursuing these duplicate states, the program keeps a list of all the states found so far. This strategy requires changes to

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to spell :number
depth.first list " :number
end

The change in

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

Stopping the Program Early

The breadth-first search mechanism we're using detects a winning path as it's removed from the front of the queue. If we could detect the winner as we're about to add it to the queue, we could avoid the need to compute all of the queue entries that come after it: children of nodes that are at the same level as the winning node, but to its left.

It's not easy to do this elegantly, though, because we add new nodes to the queue several at a time, using the procedure

to process :node
if emptyp last :node [print :node]
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

spell 8689827

The most elegant way to do this in Berkeley Logo uses a primitive called

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

to depth.first :node
process :node
foreach (children :node) "depth.first
end

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

to spell :number
depth.first list " :number
end

The procedure

?pour [3 7] 4
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4

Further Explorations

» Is it possible to eliminate more pieces of the tree by more sophisticated analysis of the problem? For example, in all of the specific problems I've presented, the best solution never includes pouring from pitcher A to pitcher B and then later pouring from B to A. Is this true in general? If so, many possible pourings could be rejected with an instruction like

to spell :number
depth.first list " :number
end

in

to depth.first :node
process :node
foreach (children :node) "depth.first
end

» Do some research into Diophantine equations and the techniques used to solve them computationally. See if you can devise a general method for solving pitcher problems with any number of pitchers, based on Diophantine equations.

» Think about writing a program that would mimic the way people actually approach these problems. The program would, for example, compute the differences and remainders of pairs of pitcher sizes, looking for the goal quantity.

How many liters are in a pitcher?

How much water is in a pitcher?

How much fluid does a pitcher hold?

Is a liter the same as a pitcher?