14
3
You may have seen this one in Die Hard: With a Vengeance... This question is based on the famous 3 and 5 Litre Jug Puzzle, but with a slightly different slant.
Golf up some code that when given an integer between 1 and 100 will provide you with the quickest instructions to measure out into a tank, the corresponding number of litres of water from a fountain, using a 3 litre jug and a 5 litre jug.
There are no gradations on either of the jugs; the fountain is abundant in supply of water, and the tank is assumed to be emptied out upon the start of each execution of the code.
You cannot access water from the tank once it goes into the tank.
The format of execution is as follows:
Input:
4
for example.
Output
Output each numbered step, as shown, followed by a tally of the volumes of the 5L jug, the 3L jug and the tank. Tally format also shown below. The number of steps must also be outputted at the end of the steps.
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into 3L jug
5L: 2, 3L: 3, T: 0
3) Empty 3L jug
5L: 2, 3L: 0, T: 0
4) Pour from 5L jug into 3L jug
5L: 0, 3L: 2, T: 0
5) Fill 5L jug
5L: 5, 3L: 2, T: 0
6) Pour from 5L jug into 3L jug
5L: 4, 3L: 3, T: 0
7) Pour from 5L jug into tank
5L: 0, 3L: 3, T: 4
Volume measured out in 7 turns
Example 2
Input: 8
Output:
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 3L jug
5L: 0, 3L: 3, T: 5
4) Pour from 3L jug into tank
5L: 0, 3L: 0, T: 8
Volume measured out in 4 turns
Conventions
Fill xL jug
- fills the associated jug to the top from the fountainEmpty xL jug
- empties the contents of the associated jug into the fountainPour from xL jug into yL jug
- Pours the contents of the xL jug into the yL jugPour from xL jug into tank
- Pours the contents of the xL jug into the tank
Shortest code wins.
possible duplicate of Water-Bucket problem
– Howard – 2014-02-13T05:20:18.9034@Howard, the old question is ill-specified (has no winning criteria) and was abandoned, so I think that this one is better and should not be closed. – Victor Stafusa – 2014-02-13T10:01:16.423
Call me crazy, but isnt the optimal solution going to be 1. Add as many 5L as possible, 2. Add 3L if needed, 3. Add an already solved 2L or 1L portion as required? – None – 2014-02-13T22:11:42.577
1@LegoStormtroopr When it all boils down, true. But I'm expecting it to be code-golfed accordingly. – WallyWest – 2014-02-13T22:13:32.583
3@LegoStormtroopr I thought that too, but aren't 6 and 9 counterexamples? – Paul Prestidge – 2014-02-14T01:47:05.807
@Chron Good point, I hadn't thought of that. – None – 2014-02-14T02:33:50.133
What do you exactly mean by "quickest instructions". Is filling a 6L tank with (5L + 1L) accepted? Or it should be filled with (3L + 3L). I'm asking this because some answers down there use the first approach (greedy filling with 5L then 3L then 2L then 1L) – Dr. belisarius – 2014-02-22T15:48:12.540
I'm happy to work with either @belisarius. In the case of 6L a greedy 5L fill process followed by a 4/3/2/1L woudl be fine; or a greedy 3L fill. I think I'm going to be flexible on the approach... If you can provide code that can give the solution, fantastic... – WallyWest – 2014-02-23T06:53:44.847