1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 1 ch 14: Example: Pitcher Problem Solver</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 1:
<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT
<H1>Example: Pitcher Problem Solver</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls1.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/v1ch14.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v1ch13/v1ch13.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v1ch15/v1ch15.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT
Press web page for Computer Science Logo Style</A>
</TABLE></TABLE>
<HR>
<P>Program file for this chapter: <A HREF="pour.lg"><CODE>pour</CODE></A>
<P>
You have probably seen puzzles like this one many times:
<BLOCKQUOTE>
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 two liters of water. How can you measure
two liters?
</BLOCKQUOTE>
<P>
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:
<OL>
<LI> Fill the three-liter pitcher from the river.
<LI> Pour the three liters from the three-liter pitcher into the
seven-liter pitcher.
<LI> Fill the three-liter pitcher from the river again.
<LI> Pour the three liters from the three-liter pitcher into the
seven-liter pitcher (which now contains six liters).
<LI> Fill the three-liter pitcher from the river yet again.
<LI> 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.
</OL>
<P>
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:
<BLOCKQUOTE>
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?
</BLOCKQUOTE>
<P>
and progressing to harder ones like this:
<BLOCKQUOTE>
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?
</BLOCKQUOTE>
<P>
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:
<PRE>
? <U>pour [3 7] 4</U>
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4
? <U>pour [2 5 10] 1</U>
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
</PRE>
<P>
How do <EM>people</EM> 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.
<P>
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
<P><CENTER>3<I>x</I>+7<I>y</I>=2</CENTER>
<P>In this equation, <I>x</I> represents the number of times the
three-liter pitcher is filled and <I>y</I> 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.
<P> 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 <I>x</I>=3 and <I>y</I> = -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?
<P> An equation with integer-valued variables is called a
<EM>Diophantine</EM> 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 <I>x</I> = -4 and <I>y</I>=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:
<OL>
<LI> Fill the seven-liter pitcher from the river.
<LI> Fill the three-liter pitcher from the seven-liter pitcher. (This
leaves four liters in the seven-liter pitcher.)
<LI> Empty the three-liter pitcher into the river.
<LI> Fill the three-liter pitcher from the seven-liter pitcher. (This
leaves one liter in the seven-liter pitcher.)
<LI> Empty the three-liter pitcher into the river.
<LI> Pour the contents of the seven-liter pitcher (one liter) into the
three-liter pitcher.
<LI> Fill the seven-liter pitcher from the river (for the second and
last time).
<LI> 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.)
<LI> Empty the three-liter pitcher into the river.
<LI> Fill the three-liter pitcher from the seven-liter pitcher. This
leaves the desired two liters in the seven-liter pitcher.
</OL>
<P>
This solution works, but it's more complicated than the one I
used in the first place.
<P>
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
<P><CENTER>2<I>x</I>+5<I>y</I>=1</CENTER>
<P>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
<I>x</I>-intercept (when <I>y</I>=0, 2<I>x</I>=1 so <I>x</I>=1/2)
and the <I>y</I>-intercept (when <I>x</I>=0, <I>y</I>=1/5).
<P><CENTER><IMG SRC="graph.gif" ALT="<P>figure: graph"></CENTER>
<P>
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:
<P><CENTER>2<I>x</I>+5<I>y</I>+10<I>z</I>=1</CENTER>
<P>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?
<P>
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.*
<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>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, <CITE>What Is Mathematics?</CITE> (Oxford University Press,
1941).</SMALL></BLOCKQUOTE></SMALL>
<H2>Tree Search</H2>
<P>
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.)
<P>
The possible pouring steps for a pitcher problem form a <EM>tree.</EM> 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 <CODE>[3 4]</CODE> means that the three-liter pitcher is
full and the seven-liter pitcher contains four liters.
<P><CENTER><IMG SRC="poursome.gif" ALT="<P>figure: poursome"></CENTER>
<P>
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
<OL>
<LI> Fill the three-liter pitcher from the river.
<LI> Empty the three-liter pitcher into the river.
</OL>
<P>
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:
<P><CENTER><IMG SRC="pourall.gif" ALT="<P>figure: pourall"></CENTER>
<P>
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.
<P>
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
<EM>searching</EM> through the tree, looking for a node that includes the
goal quantity as one of its numbers.
<H2>Depth-first and Breadth-first Searching</H2>
<P>
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.
<P>
There are two general techniques for searching a tree. These techniques are
called <EM>depth-first search</EM> and
<EM>breadth-first search.</EM> 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.
<P>
<A NAME="depth.first">In</A> 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
<CODE>children</CODE> that takes a node as input and gives us as its output
a list of all the children (one level down) of that node. Suppose we also
are given a command called <CODE>process</CODE> that takes a node as input
and does whatever the program needs to do for each node of the tree. (You
can just use <CODE>print</CODE> in place of <CODE>process</CODE> if you want
to see what's in the tree.) Here is how to do a depth-first search:
<PRE>
to depth.first :node
process :node
foreach (children :node) "depth.first
end
</PRE>
<P>
In this program, the structure of the tree is reflected in the
structure of recursive invocations of <CODE>depth.first.</CODE>
<P>
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.
<P><CENTER><IMG SRC="phonetree2.jpg" ALT="<P>figure: phonetree"></CENTER>
<P>
The operation <CODE>children</CODE> must output a list of three nodes, selecting
each of the three possible letters for the first remaining digit. If the
input to <CODE>children</CODE> is a leaf node (one with all letters), it must
output the empty list to indicate that there are no children for that node.
<PRE>
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
?<U>show children [tnt 9827]</U>
[[tntw 827] [tntx 827] [tnty 827]]
</PRE>
<P>
The top-level procedure has to turn a number into a root node and
invoke a depth-first search:
<PRE>
to spell :number
depth.first list " :number
end
</PRE>
<P>
What about the <CODE>process</CODE> command? The program wants to print only leaf
nodes:
<PRE>
to process :node
if emptyp last :node [print :node]
end
</PRE>
<P>
» Try this program. To get the tree illustrated above,
use the instruction
<PRE>
spell 8689827
</PRE>
<P>
Then try again, but investigate the order in which the program
searches the nodes of the tree by using a different version of <CODE>process</CODE>:
<PRE>
to process :node
print :node
end
</PRE>
<P>
This will let you see the order in which the program encounters
the nodes of the tree.
<P>
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 <EM>queue,</EM> 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:
<PRE>
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
</PRE>
<P>
This breadth-first search program uses the same <CODE>children</CODE> and
<CODE>process</CODE> subprocedures as the depth-first version. You can try a
breadth-first listing of telephone number spellings simply by changing the
top-level <CODE>spell</CODE> procedure to invoke <CODE>breadth.first</CODE>
instead of <CODE>depth.first</CODE>. What you'll find is that (with the
version of <CODE>process</CODE> that only prints leaf nodes) the two
versions produce the same results, but the depth-first program trickles the
spellings out one by one, while the breadth-first version prints nothing for
a long time and then spits out all the spellings at once. If you use the
version of <CODE>process</CODE> that prints all the nodes, you can see why.
<P>
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
<EM>entire</EM> 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.
<P>
For the pitcher problem solver, I decided that a breadth-first search is
appropriate. The main reason is that I wanted to present the
<EM>shortest</EM> 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.
<H2>Data Representation</H2>
<P>
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 <EM>state.</EM> 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.
<P>
The solution I chose was to have an extra member in the list representing a
state, namely a list of <EM>pourings.</EM> 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
<PRE>
pour [2 5 10] 1
</PRE>
<P>
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 <CODE>fput</CODE>. For example, in the interaction
<PRE>
?<U>pour [3 7] 4</U>
Pour from river to 7
Pour from 7 to 3
Final quantities are 3 4
</PRE>
<P>
the extended state information for the final solution state is
<PRE>
[[[2 1] [0 2]] 3 4]
</PRE>
<P>
In this list, the sublist <CODE>[0 2]</CODE> represents pouring water
from the river into pitcher number 2, which is the seven-liter pitcher.
The sublist <CODE>[2 1]</CODE> represents pouring water from pitcher number 2 into
pitcher number 1.
<H2>Abstract Data Types</H2>
<P>
Up to this point I've continued to call this expanded data
structure a <EM>state.</EM> 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 <CODE>state</CODE> in several procedures, some of which contained
the old kind of state, and some the new kind. I thought this might be
confusing, so I did what I should have done in the first place: I invented a
new name for the expanded data structure. It's now called a <EM>path</EM>;
when you read the program you can confidently assume that <CODE>:state</CODE>
represents a list like
<PRE>
[3 4]
</PRE>
<P>
while <CODE>:path</CODE> represents a list like
<PRE>
[[[2 1] [0 2]] 3 4]
</PRE>
<P>
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
<CODE>first</CODE> and constructors like <CODE>fput</CODE>. For example,
suppose the value of the variable <CODE>oldpath</CODE> is a path, and we
decide to pour water from pitcher number <CODE>:from</CODE> to pitcher
number <CODE>:to</CODE>. We now want to construct a new path, which will
include a new state (computed from the old state and the two pitcher
numbers) and a new list of moves, with the new move added to the existing
ones. We'd end up saying
<PRE>
make "newpath fput (fput (list :from :to) first :oldpath) ~
(newstate butfirst :oldpath :from :to)
</PRE>
<P>
assuming that we have a procedure <CODE>newstate</CODE> that computes the
new state. This instruction is hard to read! The two invocations of
<CODE>fput</CODE> have quite different purposes. One adds a new move to a
list of moves, while the other connects a list of moves to a state in order
to form a path. We can clarify instructions like this one if we make up
synonyms for procedures like <CODE>first</CODE> and <CODE>fput</CODE> to be
used in particular contexts. For example, we make a new path using
<CODE>fput</CODE>, but we'll call it <CODE>make.path</CODE> when we're using
it for that purpose. Just as <CODE>fput</CODE> is a constructor, and
<CODE>first</CODE> a selector, for lists, we can invent constructors and
selectors for <EM>abstract</EM> data types (ones that we make up, rather
than ones built into Logo) such as paths:
<PRE>
to make.path :moves :state
output fput :moves :state
end
to path.moves :path
output first :path
end
to path.state :path
output butfirst :path
end
</PRE>
<P>
That unreadable instruction shown earlier would now be written this way:
<PRE>
make "newpath make.path (fput (list :from :to) path.moves :oldpath) ~
(newstate (path.state :oldpath) :from :to)
</PRE>
<P>
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 <CODE>make.path</CODE>
with two inputs, one that seems to have to do with moves, and the other that
seems to have to do with states. If we remember that a path has two parts,
a list of moves and a state, this makes sense.
<P>
» Invent a constructor and selectors for a <EM>move</EM> data type.
<H2><CODE>Sentence</CODE> as a Combiner</H2>
<P>
The general breadth-first search program I showed earlier contains this
procedure:
<PRE>
to breadth.descend :queue
if emptyp :queue [stop]
process first :queue
breadth.descend sentence (butfirst :queue) (children first :queue)
end
</PRE>
<P>
The most common use of <CODE>sentence</CODE> is in generating English
sentences. In that use, the input and output lists are <EM>sentences</EM> or
flat lists. You're supposed to think, "<CODE>Sentence</CODE> takes two words or
sentences as inputs; its output is a sentence containing all the words of
the inputs." In this program, we're using <CODE>sentence</CODE> in a different
way, more like what is called <CODE>append</CODE> in Lisp. Here you're supposed to
think, "<CODE>Sentence</CODE> takes two lists as inputs; its output is a list
containing the members of the inputs." Those members could be words or
lists, but in this case they'll be lists, namely paths.
<P>
Recursive procedures that manipulate non-flat lists generally use
<CODE>fput</CODE> as the combiner. That wouldn't work here for two
reasons. First, the queue structure that we need to implement breadth-first
search requires that we add new entries at the opposite end of the list from
where we look for the next node to process. If we use <CODE>first</CODE> to
select a node and <CODE>fput</CODE> to add new candidate nodes, then instead
of a queue we'd be using a <EM>stack,</EM> in which the newest entries are
processed first instead of the oldest ones first. That would give us a
depth-first tree search algorithm. We could solve that problem by using
<CODE>lput</CODE> as the combiner, but the second reason for choosing
<CODE>sentence</CODE> is that we don't generate new entries one at a time.
Instead, <CODE>children</CODE> gives us several children to add to the queue
at once. That means we must append the list output by <CODE>children</CODE>
to the list that represents the nodes already queued.
<H2>Finding the Children of a Node</H2>
<P>
<CODE>Pour</CODE> is going to work essentially by invoking <CODE>breadth.first</CODE> on a
root node containing zeros for all the current quantities. But in this case
we want to pick a single node that satisfies the conditions of the problem,
so we must modify <CODE>breadth.first</CODE> to make it an <EM>operation</EM> that
outputs the first such node:
<PRE>
to breadth.first :root
output breadth.descend (list :root)
end
to breadth.descend :queue
if emptyp :queue [output []]
if winnerp first :queue [output first :queue]
output breadth.descend sentence (butfirst :queue) ~
(children first :queue)
end
</PRE>
<P>
The predicate <CODE>winnerp</CODE> will output <CODE>true</CODE> if its input is
a node that satisfies the problem conditions:
<PRE>
to winnerp :path
output memberp :goal path.state :path
end
</PRE>
<P>
If <CODE>breadth.first</CODE> runs out of nodes without finding a
solution, it returns an empty list to indicate failure.
<P>
Here is a
simplified version of <CODE>pour</CODE>:
<PRE>
to pour :sizes :goal
win breadth.first make.path [] all.empty :sizes
end
to all.empty :list
output map [0] :list
end
</PRE>
<P>
<CODE>All.empty</CODE> is an operation that outputs a state in which all
of the values are zeros. The number of zeros in the list is equal to the
number of members in its input, which is the number of pitchers. <CODE>Pour</CODE>
combines this initial state with an empty list of moves to produce the
first path.
<P> To allow <CODE>breadth.first</CODE> to work, we must have an operation
called <CODE>children</CODE> that outputs a list of the children of a node.
Starting from a particular state, what are the possible outcomes of a single
pouring? As I mentioned earlier, the source of a pouring can be the river
or any of the pitchers, and the destination can also be the river or any of
the pitchers. If there are <I>n</I> pitchers, then there are <I>n</I>+1
sources, <I>n</I>+1 destinations, and therefore (<I>n</I>+1)<SUP>2</SUP>
possible pourings. Here is how the program structure reflects this. I'm
assuming that we've created (elsewhere in the program) a variable called
<CODE>pitchers</CODE> whose value is a list of all the integers from zero to
<I>n</I>.
<PRE>
to children :path
output map.se [children1 :path ?] :pitchers
end
to children1 :path :from
output map.se [child :path :from ?] :pitchers
end
to child :path :from :to
output (list make.path (fput (list :from :to) path.moves :path)
(newstate (path.state :path) :from :to))
end
</PRE>
<P>
The version of <CODE>child</CODE> presented here is simpler than the one
in the actual project, but the other procedures are the real versions.
We'll see later how <CODE>child</CODE> is expanded. The immediately important
point is to see how <CODE>children</CODE> and <CODE>children1</CODE> ensure that every
possible source (<CODE>:from</CODE>) and destination (<CODE>:to</CODE>) from zero to the
number of pitchers are used.
<P>
You should be wondering, at this point, why <CODE>children1</CODE> uses
<CODE>sentence</CODE> as a combiner. (That's what it means to use
<CODE>map.se</CODE> rather than <CODE>map</CODE>.) It makes sense for
<CODE>children</CODE> to combine using <CODE>sentence</CODE> because, as I
discussed earlier, the things it's combining are lists of nodes, the outputs
from invocations of <CODE>children1</CODE>. But <CODE>children1</CODE> is
not combining lists of nodes; it's combining the outputs from invocations of
<CODE>child</CODE>. Each invocation of <CODE>child</CODE> computes a single
child node. It would be more straightforward to write the program this way:
<PRE>
to children1 :path :from ;; simplified
output map [child :path :from ?] :pitchers
end
to child :path :from :to ;; simplified
output make.path (fput (list :from :to) path.moves :path) ~
(newstate (path.state :path) :from :to)
end
</PRE>
<P>
This also eliminates the use of <CODE>list</CODE> in <CODE>child</CODE>, needed
in the other version to turn a single node into a singleton (one-member)
list of nodes, which is what <CODE>sentence</CODE> needs to function properly as a
combiner.
<P>
The reason for the use of <CODE>sentence</CODE> in <CODE>children1</CODE> is that we are
later going to modify <CODE>child</CODE> so that sometimes it rejects a possible
new node for efficiency reasons. For example, it makes no sense to have
nodes for pourings in which the source and the destination are the same.
When it wants to reject a node, <CODE>child</CODE> will output the empty list.
Using <CODE>sentence</CODE> as the combiner, this empty list simply doesn't affect
the accumulated list of new nodes. Here is a version of <CODE>child</CODE>
modified to exclude pourings to and from the same place:
<PRE>
to child :path :from :to
<U>if equalp :from :to [output []]</U>
output (list make.path (fput (list :from :to) path.moves :path)
(newstate (path.state :path) :from :to))
end
</PRE>
<P>
With this version of <CODE>child</CODE>, the use of <CODE>sentence</CODE> in
<CODE>children1</CODE> may seem more sensible to you.
<P>
To create the variable <CODE>pitchers</CODE> we modify the top-level <CODE>pour</CODE>:
<PRE>
to pour :sizes :goal
<U>local "pitchers</U>
<U>make "pitchers fput 0 (map [#] :sizes)</U>
win breadth.first make.path [] all.empty :sizes
end
</PRE>
<P>
Here we are taking advantage of a feature of <CODE>map</CODE> that I haven't
mentioned earlier. The number sign (<CODE>#</CODE>) can be used in a
<CODE>map</CODE> template to represent the position in the input, rather
than the value, of a member of the input data list. That is,
<CODE>#</CODE> is replaced by 1 for the first member, 2 for the second, and
so on. In this example, these position numbers are all we care about; the
template does not contain the usual question mark to refer to the values of
the data.
<H2>Computing a New State</H2>
<P>
The job of <CODE>child</CODE> is to produce a new child node, that is to say, a new
path. Its inputs are an old path and the source and destination of a new
pouring. The new path consists of a new state and a new list of pourings.
The latter is easy; it's just the old list of pourings with the new one
inserted. <CODE>Child</CODE> computes that part itself, with the expression
<PRE>
fput (list :from :to) path.moves :path
</PRE>
<P>
The new state is harder to compute. There are four cases.
<OL>
<LI> If the destination is the river, then the thing to do is to empty the
source pitcher.
<LI> If the source is the river, then the thing to do is
to fill the destination pitcher to its capacity.
<LI> 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.
<LI> 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.
</OL>
<P>
Here is the procedure to carry out these computations:
<PRE>
to newstate :state :from :to
if riverp :to [output replace :state :from 0]
if riverp :from [output replace :state :to (size :to)]
if (water :from) < (room :to) ~
[output replace2 :state ~
:from 0 ~
:to ((water :from)+(water :to))]
output replace2 :state ~
:from ((water :from)-(room :to)) ~
:to (size :to)
end
</PRE>
<P>
Each instruction of this procedure straightforwardly embodies one
of the four numbered possibilities.
<P>
Helper procedures are used to compute a new list of amounts of
water, replacing either one or two old values from the previous list:
<PRE>
to replace :list :index :value
if equalp :index 1 [output fput :value butfirst :list]
output fput first :list (replace butfirst :list :index-1 :value)
end
to replace2 :list :index1 :value1 :index2 :value2
if equalp :index1 1 ~
[output fput :value1 replace butfirst :list :index2-1 :value2]
if equalp :index2 1 ~
[output fput :value2 replace butfirst :list :index1-1 :value1]
output fput first :list ~
replace2 butfirst :list :index1-1 :value1 :index2-1 :value2
end
</PRE>
<P>
<CODE>Replace</CODE> takes as inputs a list, a number
representing a position in the list, and a value. The output is a copy of
the first input, but with the member selected by the second input replaced
with the third input. Here's an example:
<PRE>
?<U>show replace [a b c d e] 4 "x</U>
[a b c x e]
</PRE>
<P>
<CODE>Replace2</CODE> has a similar purpose, but its output has
<EM>two</EM> members changed from their values in the input list.
<P>
Remember that <CODE>newstate</CODE> has as one of its inputs a state, that
is, a list of numbers representing quantities of water.
<CODE>Newstate</CODE> uses <CODE>replace</CODE> to change the amount of
water in one of the pitchers. The second input to <CODE>replace</CODE> is
the pitcher number, and the third is the new contents of that pitcher. For
example, if the destination is the river then we want to empty the source
pitcher. This case is handled by the instruction
<PRE>
if riverp :to [output replace :state :from 0]
</PRE>
<P>
If the destination is the river,
the output state is the same as the input state except that the pitcher
whose number is <CODE>:from</CODE> has its contents replaced by zero. The other
cases are handled similarly, except that two replacements are necessary if
both source and destination are pitchers.
<H2>More Data Abstraction</H2>
<P>
The instructions in <CODE>newstate</CODE> use some procedures I haven't written
yet, such as <CODE>riverp</CODE> to test whether a source or destination is the
river, and <CODE>room</CODE> to find the amount of empty space in a pitcher.
If we think of a pitcher as an abstract data type, then these can be
considered selectors for that type. Here they are:
<PRE>
to riverp :pitcher
output equalp :pitcher 0
end
to size :pitcher
output item :pitcher :sizes
end
to water :pitcher
output item :pitcher :state
end
to room :pitcher
output (size :pitcher)-(water :pitcher)
end
</PRE>
<P>
To underscore the importance of data abstraction, here is what <CODE>newstate</CODE>
would look like without these selectors. (I actually wrote it this way at
first, but I think you'll agree that it's unreadable.)
<PRE>
to newstate :state :from :to
if equalp :to 0 [output replace :state :from 0]
if equalp :from 0 [output replace :state :to (item :to :sizes)]
if ((item :from :state) < ((item :to :sizes)-(item :to :state))) ~
[output replace2 :state ~
:from 0 ~
:to ((item :from :state)+(item :to :state))]
output replace2 :state ~
:from ((item :from :state)-
((item :to :sizes)-(item :to :state))) ~
:to (item :to :sizes)
end
</PRE>
<H2>Printing the Results</H2>
<P>
When <CODE>breadth.first</CODE> finds a winning path, the top-level procedure
<CODE>pour</CODE> invokes <CODE>win</CODE> with that path as its input.
<CODE>Win</CODE>'s job is to print the results. Since the list of moves is
kept in reverse order, <CODE>win</CODE> uses the Logo primitive operation
<CODE>reverse</CODE> to ensure that the moves are shown in chronological
order.
<PRE>
to win :path
if emptyp :path [print [Can't do it!] stop]
foreach (reverse path.moves :path) "win1
print sentence [Final quantities are] (path.state :path)
end
to win1 :move
print (sentence [Pour from] (printform first :move)
[to] (printform last :move))
end
to printform :pitcher
if riverp :pitcher [output "river]
output size :pitcher
end
</PRE>
<H2>Efficiency: What Really Matters?</H2>
<P>
The <CODE>pour</CODE> program as described so far would run extremely slowly. The
rest of the commentary in this chapter will be on ways to improve its
efficiency. The fundamental problem is one I mentioned earlier: the
number of nodes in the tree grows enormously as the depth increases. In a
problem with two pitchers, the root level has one node, the next level nine
nodes, the third level 81, the fourth level 729, the fifth level 6561, and
the sixth level 59049. A six-step problem like
<PRE>
pour [3 7] 2
</PRE>
<P>
would strain the memory capacity of many computers as well as
taking forever to run!
<P>
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 <CODE>newstate</CODE> procedure described earlier calls the
<CODE>room</CODE> procedure twice to compute the amount of room available in
the destination pitcher. Each call to <CODE>room</CODE> computes the
quantity
<PRE>
(item :to :sizes)-(item :to :state)
</PRE>
<P>
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 <EM>number</EM>
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.
<P>
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 <EM>much</EM> 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.
<H2>Avoiding Meaningless Pourings</H2>
<P>
We have already modified <CODE>child</CODE> to avoid one kind of meaningless
pouring, namely ones in which the source is the same as the destination.
Two other avoidable kinds of meaningless pourings are ones from an empty
source and ones to a full destination. In either case, the quantity of
water poured will be zero, so the state will not change. Here is a modified
version of <CODE>child</CODE> that avoids these cases:
<PRE>
to child :path :from :to
<U>local "state</U>
if equalp :from :to [output []]
<U>make "state path.state :path</U>
<U>if not riverp :from ~</U>
<U>[if equalp (water :from) 0 [output []]]</U>
<U>if not riverp :to ~</U>
<U>[if equalp (water :to) (size :to) [output []]]</U>
output (list make.path (fput list :from :to path.moves :path)
(newstate :state :from :to))
end
</PRE>
<P>
The local variable <CODE>state</CODE> is set up because the procedure
<CODE>water</CODE> needs it. (<CODE>Water</CODE> relies on Logo's dynamic scope to give
it access to the <CODE>state</CODE> variable provided by its caller.)
<P>
The important changes are the two new <CODE>if</CODE> instructions. The first
avoids pouring from an empty pitcher; the second avoids pouring into a full
one. In both cases, the test makes sense only for actual pitchers; the
river does not have a size or a current contents.
<P>
To underscore what I said earlier about what's important in trying to
improve the efficiency of a program, notice that these added tests
<EM>slow down</EM> the process of computing each new node, and yet the overall
effect is beneficial because the number of nodes is dramatically reduced.
<H2>Eliminating Duplicate States</H2>
<P>
It's relatively easy to find individual pourings that are absurd. A harder
problem is to avoid <EM>sequences</EM> 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
<PRE>
Pour from river to 6
Pour from 6 to 3
</PRE>
<P>
leads to the same state (<CODE>[3 3]</CODE>) as the sequence
<PRE>
Pour from river to 3
Pour from 3 to 6
Pour from river to 3
</PRE>
<P>
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.
<P>
To avoid pursuing these duplicate states, the program keeps a list of all
the states found so far. This strategy requires changes to <CODE>pour</CODE> and
to <CODE>child</CODE>.
<PRE>
to pour :sizes :goal
<U>local [oldstates pitchers]</U>
<U>make "oldstates (list all.empty :sizes)</U>
make "pitchers fput 0 (map [#] :sizes)
win breadth.first make.path [] all.empty :sizes
end
to child :path :from :to
<U>local [state newstate]</U>
if equalp :from :to [output []]
make "state path.state :path
if not riverp :from ~
[if equalp (water :from) 0 [output []]]
if not riverp :to ~
[if equalp (water :to) (size :to) [output []]]
<U>make "newstate (newstate :state :from :to)</U>
<U>if memberp :newstate :oldstates [output []]</U>
<U>make "oldstates fput :newstate :oldstates</U>
output (list make.path (fput list :from :to path.moves :path) <U>:newstate</U>)
end
</PRE>
<P>
The change in <CODE>pour</CODE> is simply to initialize the list of
already-seen states to include the state in which all pitchers are empty.
There are two important new instructions in <CODE>child</CODE>. The first
rejects a new node if its state is already in the list; the second adds a
new state to the list. Notice that it is duplicate <EM>states</EM> we look
for, not duplicate <EM>paths</EM>; it's in the nature of a tree-search
program that there can never be duplicate paths.
<H2>Stopping the Program Early</H2>
<P>
The breadth-first search mechanism we're using detects a winning path as
it's <EM>removed</EM> from the front of the queue. If we could detect the
winner as we're about to <EM>add</EM> 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.
<P>
It's not easy to do this elegantly, though, because we add new nodes to the
queue several at a time, using the procedure <CODE>children</CODE> to compute them.
What we need is a way to let <CODE>child</CODE>, which constructs the winning node,
prevent the computation of any more children, and notify <CODE>breadth.first</CODE>
that a winner has been found.
<P>
The most elegant way to do this in Berkeley Logo uses a primitive called
<CODE>throw</CODE> that we won't meet until the second volume of this series.
Instead, in this chapter I'll use a less elegant technique, but one that
works in any Logo implementation. I'll create a variable named <CODE>won</CODE>
whose value is initially <CODE>false</CODE> but becomes <CODE>true</CODE> as soon as a
winner is found. Here are the necessary modifications:
<PRE>
to pour :sizes :goal
local [oldstates pitchers <U>won</U>]
make "oldstates (list all.empty :sizes)
make "pitchers fput 0 (map [#] :sizes)
<U>make "won "false</U>
win breadth.first make.path [] all.empty :sizes
end
to breadth.descend :queue
if emptyp :queue [output []]
<U>if :won [output last :queue]</U>
op breadth.descend sentence (butfirst :queue) ~
(children first :queue)
end
to child :path :from :to
local [state newstate]
<U>if :won [output []]</U>
if equalp :from :to [output []]
make "state path.state :path
if not riverp :from ~
[if equalp (water :from) 0 [output []]]
if not riverp :to ~
[if equalp (water :to) (size :to) [output []]]
make "newstate (newstate :state :from :to)
if memberp :newstate :oldstates [output []]
make "oldstates fput :newstate :oldstates
<U>if memberp :goal :newstate [make "won "true]</U>
output (list make.path (fput list :from :to path.moves :path) :newstate)
end
</PRE>
<P>
The procedure <CODE>winnerp</CODE> is no longer used; we are now checking
a state, rather than a path, for the goal amount.
<H2>Further Explorations</H2>
<P>
» 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
<PRE>
if memberp list :to :from path.moves :path [output []]
</PRE>
<P>
in <CODE>child</CODE>.
<P>
» 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.
<P>
» 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.
<P>
» What other types of puzzles can be considered as tree searching problems?
<P>
<TABLE width="100%"><TR><TD><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v1ch13/v1ch13.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v1ch15/v1ch15.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<H2>Program Listing</H2>
<PRE>
;; Initialization
to pour :sizes :goal
local [oldstates pitchers won]
make "oldstates (list all.empty :sizes)
make "pitchers fput 0 (map [#] :sizes)
make "won "false
win breadth.first make.path [] all.empty :sizes
end
to all.empty :list
output map [0] :list
end
;; Tree search
to breadth.first :root
op breadth.descend (list :root)
end
to breadth.descend :queue
if emptyp :queue [output []]
if :won [output last :queue]
op breadth.descend sentence (butfirst :queue) ~
(children first :queue)
end
;; Generate children
to children :path
output map.se [children1 :path ?] :pitchers
end
to children1 :path :from
output map.se [child :path :from ?] :pitchers
end
to child :path :from :to
local [state newstate]
if :won [output []]
if equalp :from :to [output []]
make "state path.state :path
if not riverp :from ~
[if equalp (water :from) 0 [output []]]
if not riverp :to ~
[if equalp (water :to) (size :to) [output []]]
make "newstate (newstate :state :from :to)
if memberp :newstate :oldstates [output []]
make "oldstates fput :newstate :oldstates
if memberp :goal :newstate [make "won "true]
output (list make.path (fput list :from :to path.moves :path) :newstate)
end
to newstate :state :from :to
if riverp :to [output replace :state :from 0]
if riverp :from [output replace :state :to (size :to)]
if (water :from) < (room :to) ~
[output replace2 :state ~
:from 0 ~
:to ((water :from)+(water :to))]
output replace2 :state ~
:from ((water :from)-(room :to)) ~
:to (size :to)
end
;; Printing the result
to win :path
if emptyp :path [print [Can't do it!] stop]
foreach (reverse path.moves :path) "win1
print sentence [Final quantities are] (path.state :path)
end
to win1 :move
print (sentence [Pour from] (printform first :move)
[to] (printform last :move))
end
to printform :pitcher
if riverp :pitcher [output "river]
output size :pitcher
end
;; Path data abstraction
to make.path :moves :state
output fput :moves :state
end
to path.moves :path
output first :path
end
to path.state :path
output butfirst :path
end
;; Pitcher data abstraction
to riverp :pitcher
output equalp :pitcher 0
end
to size :pitcher
output item :pitcher :sizes
end
to water :pitcher
output item :pitcher :state
end
to room :pitcher
output (size :pitcher)-(water :pitcher)
end
;; List processing utilities
to replace :list :index :value
if equalp :index 1 [output fput :value butfirst :list]
output fput first :list (replace butfirst :list :index-1 :value)
end
to replace2 :list :index1 :value1 :index2 :value2
if equalp :index1 1 ~
[output fput :value1 replace butfirst :list :index2-1 :value2]
if equalp :index2 1 ~
[output fput :value2 replace butfirst :list :index1-1 :value1]
output fput first :list ~
replace2 butfirst :list :index1-1 :value1 :index2-1 :value2
end
</PRE>
<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v1ch13/v1ch13.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v1ch15/v1ch15.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|