Bucket Puzzle
Summary
Given a bucket of volume A and a bucket of volume B, measure out a
volume C.
Details
You will implement a solver for the classic "bucket puzzle"
(apparently an instance of this puzzle appeared in "Die Hard 3").
You have two buckets, A and B, an infinite amount of water with which
to fill your buckets, and you need to measure out some volume of water
C. You have 6 operations that you can perform on these
buckets:
- Fill bucket A
- Fill bucket B
- Empty bucket A
- Empty bucket B
- Pour from bucket A into bucket B: No more water can be transferred
than what started in A, and you cannot overflow bucket B.
- Pour from bucket B into bucket A: No more water can be transferred
than what started in B, and you cannot overflow bucket A.
Your job is not only to find a solution to this puzzle, but to find
the quickest solution to this puzzle in terms of number of
operations that must be performed. In the case of ties, favor
solutions that utilize operations higher on this list earlier. (That
is, if two solutions are the same length and the first step that they
differ has "Empty bucket A" for one solution and "Pour B into A" for
the second, you will favor the first.)
If no solution exists, you will print out "No solution." If a
solution does exist, you will print out the operations necessary to
measure out volume C in either bucket A or bucket B, followed by
"Success". The only things your program should output are the
following list:
- No solution.
- Fill A
- Fill B
- Empty A
- Empty B
- Pour A into B
- Pour B into A
- Success
We will be grading you based on having exact, perfect output. So
testing your code against our sample output is important.
After reading in one puzzle, continue reading until the end of
standard input. (See test #6)
The Algorithm
This is nothing more than Breadth First Search. You will need
to track which states are visited (a state is simply a pair of ints a
and b, although you'll need additional information in order to find
the shortest path.
Test Cases
as4test1.in as4test1.out
as4test2.in as4test2.out
as4test3.in as4test3.out
as4test4.in as4test4.out
as4test5.in as4test5.out
as4test6.in as4test6.out
Your program will be graded automatically for producing identical
outputs on the same inputs. It is strongly recommended that you use
diff like in lab to verify your program's correctness.