The Jug filling Problem is a very interesting problem which can quickly take you into some fairly deep territory in the overlap between Maths and Computer Science. It is closely related to the Euclidean Algorithm, which is a method for finding the greatest common divisor of two numbers. (In the UK you might be more familiar with the term “highest common factor”). The ancient Greeks were doing some amazing stuff with algorithms in their time, and I sometimes wonder what they would have made of some of the modern innovations we take for granted. For example, what if a TI-84 graphing calculator made it’s way back through time into Euclid’s hands – he would probably think Athena of Apollo had bestowed a magical gift upon him.
Using the TI-84, we can explore the Jug Filling Problem with the help of a little TI-Basic programming.
You can download the 8XP (TI-Basic) file for this program here.
The goal is to use the options to end up with a value of 1 in one of the jugs. There are multiple solutions.
Once you’ve mastered the idea, you could try modifying the code to have different sizes of jug. If you like coding in TI-Basic (which can be a little frustrating compared to other languages), you could replace the hard-coded jug sizes with more easily modified constants.
Let me know what you think in the comments. If you want any part of the code explained I will try and help too.
Enjoy!
0->X
0->Y
Lbl ST
ClrHome
Disp ""
Disp ""
Disp ""
Disp "1: FILL SMALL"
Disp "2: FILL BIG"
Disp "3: POUR SMALL TO BIG"
Disp "4: POUR BIG TO SMALL"
Disp "5: EMPTY SMALL"
Disp "6: EMPTY BIG"
Output(1,1,"SMALL: "
Output(1,8,X
Output(2,1,"BIG: "
Output(2,8,Y
Repeat max(Ans={92,93,94,82,83,84
getKey
End
If Ans=92
3->X
If Ans=93
5->Y
If Ans=83
0->X
If Ans=84
0->Y
If Ans=94
Then
min(X,5-Y)->C
Y+C->Y
X-C->X
End
If Ans=82
Then
min(Y,3-X)->C
X+C->X
Y-C->Y
End
Goto ST