197k views
0 votes
In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes the puzzle.

You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can take: (1) fill a jug, (2) empty a jug, and (3) pour water from one jug to the other. The action of pouring water from one jug to the other stops when either (a) the first jug is empty or (b) the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
Accessary Functions
A. Define rules for the basic operations of the two jugs, as described below:
Fill-A/3 – fill Jug A, Fill-B/3 Empty-A/3 Empty-B/3 A-to-B/3 – pour everything from A to B B-to-A/3 Each of these functors takes 3 (list) parameters (hence the /3): Size, Current, Next, or more specifically, [Size-A, Size-B], [Current-in-A, Current-in-B], [Next-in-A, Next-in-B]. For example:
?- A-to-B([5,3], [4,2], [A,B]).
A = 3
B = 3
?- A-to-B([5,3], [4,2], Next).
Next = [3,3]
You will then define a functor named move which combines all these operations, ex.,
Move(Size, Current, New) :- Fill-A(Size,Currect,New);Fill-B(Size,Current,New) ..
Alternatively, you could just name all 6 operations move. In any case, when a move is attempted, all 6 operations will be tried in the order in which they are listed. For example:
?- move([5, 3], [4, 2], [A, B]).
A = 5
B = 2 ;
A = 4
B = 3 ;
A = 0
B = 2 ;
A = 4
B = 0 ;
A = 3
B = 3 ;
A = 5
B = 1 ;
B. Define a functor printJugs/1 which accept as argument a list describing the solution path in the form of [state1, state2, …., goalState], where each state is a list of two numbers indicating the amount of water in jugs A and B. It should print the list of move as indicated in the solution path. See prolog2out.doc for sample output. Depth-first Search (40 points)
Write prolog rules that will allow a depth-first search by SWI Prolog to solve the jugs problem. Be sure to study class examples such as FWGC as your solution could be very similar the example. Note that the top level rule should be named jugs and should take 3 arguments: [SizeA, SizeB], GoalSize, and SolutionPath, where SizeA and SizeB are the sizes of the two jugs A and B, respectively, with SizeA >= SizeB, GoalSize is the desired amount of water in the larger jugs, and SolutionPath is the variable which will be instantiated with the solution path when it’s found. Since the SolutionPath could be longer than what swi-porlog is willing to display with full details, your rule must call the printJugs functor to print the list of moves when a solution is found.

User Epic Chen
by
8.5k points

1 Answer

2 votes

Final answer:

The problem asks for a solution to the jugs problem involving two jugs of different capacities and the goal of measuring a specific amount of water. The solution involves implementing a depth-first search algorithm in SWI Prolog, using a set of rules for the basic operations and a 'move' functor to combine the operations and find a solution.

Step-by-step explanation:

The question is asking for a solution to the jugs problem, which involves using two jugs of different capacities to measure a specific amount of water. In this case, the goal is to fill the 5-gallon jug with exactly 4 gallons. The problem provides a set of rules for the basic operations that can be performed on the jugs, such as filling, emptying, and pouring water from one jug to the other.

To solve the problem, a depth-first search algorithm can be implemented in SWI Prolog. The top-level rule, named 'jugs', would take three arguments: the sizes of the two jugs, the desired amount of water in the larger jug, and a variable for the solution path. The rule would then call the 'move' functor, which combines all the operations, and iterate through all possible moves until it finds a solution. When a solution is found, the 'printJugs' functor can be called to print the list of moves.

User Aldi Unanto
by
8.2k points

Related questions