4
$\begingroup$

Recently there was a jug pouring competition, and I got to thinking if this was the question with the most number of moves. It turned out that it was. If you have three different sized jugs all less than or equal to 10 litres, and only one of those jugs full, what target volume would give you the most number of steps.

You can get as many as 8 steps required. (10,9,2) → 8; (10,9,1) → 5; (10,9,1) → 4; and (10,7,3) → 5. So the question has pretty much the only interesting optimal result.

Here's another one for you (since I wrote the code already, it seems a waste not to use it).

Starting with 15l in a 15l jug, an empty 11l jug, and an empty 4l jug try to get to 13l.

$\endgroup$
  • $\begingroup$ math.stackexchange.com/questions/1178368/… $\endgroup$ – RobPratt Apr 11 at 0:37
  • $\begingroup$ That's cool, @RobPratt! I thought someone must have looked at it. $\endgroup$ – Dr Xorile Apr 11 at 0:39
  • $\begingroup$ While there are many different definitions of "a single step", the optimal solution to find $c$ litres from $a$ and $b$ litres-capacity jugs is solving the equation of either $ax-by=c$ or $bx-ay=c$ while minimizing the $x$ and $y$ which are usually describing the steps. (Well to be fair, the equation should be tweaked a bit for $c>a$ or $c>b$, but only constant steps will be done.) $\endgroup$ – athin Apr 11 at 5:11
3
$\begingroup$

Took me 13 steps. Target is to remain with 2l in one of the jugs at the end and then work backwards. Sequence of quantity is (15l, 11l, 4l)

(15l, 11l, 4l)

15,0,0

4,11,0

4,7,4

8,7,0

8,3,4

12,3,0

12,0,3

1,11,3

1,10,4

5,10,0

5,6,4

9,6,0

9,2,4

13,2,0

| improve this answer | |
$\endgroup$
  • $\begingroup$ I got this, too, but you posted before I could type it up. Nice job. $\endgroup$ – Lanny Strack Apr 11 at 0:54
  • $\begingroup$ Yes it's the same thing. I guess this is the only optimal way to go about this one $\endgroup$ – Vijay Apr 11 at 1:08
2
$\begingroup$

Revised: (note: this is the same as @Vijay, who posted earlier, but I independently achieved it).

13 steps:

  15L| 11L| 4L
 ----|----|----
  15 | 0  | 0
 ----|----|----
  4  | 11 | 0
 ----|----|---- 
  4  | 7  | 4
 ----|----|----
  8  | 7  | 0
 ----|----|----
  8  | 3  | 4
 ----|----|----
  12 | 3  | 0
 ----|----|----
  12 | 0  | 3
 ----|----|----
  1  | 11 | 3
 ----|----|----
  1  | 10 | 4
 ----|----|----
  5  | 10 | 0
 ----|----|----
  5  | 6  | 4
 ----|----|----
  9  | 6  | 0
 ----|----|----
  9  | 2  | 4
 ----|----|----
  13 | 2  | 0
 ----|----|----

Earlier attempt: There's bound to be a more optimal way, but here is one way to do it. 16 steps. Note that I dump water on the third to last step.

  15L| 11L| 4L
 ----|----|----
  15 | 0  | 0
 ----|----|----
  11 | 0  | 4
 ----|----|---- 
  11 | 4  | 0
 ----|----|----
  7  | 4  | 4
 ----|----|----
  7  | 8  | 0
 ----|----|----
  3  | 8  | 4
 ----|----|----
  3  | 11 | 1
 ----|----|----
  14 | 0  | 1
 ----|----|----
  14 | 1  | 0
 ----|----|----
  10 | 1  | 4
 ----|----|----
  10 | 5  | 0
 ----|----|----
  6  | 5  | 4
 ----|----|----
  6  | 9  | 0
 ----|----|----
  2  | 9  | 4
 ----|----|----
  0  | 9  | 4     ----> dumped
 ----|----|----
  9  | 0  | 4
 ----|----|----
  13 | 0  | 4
 ----|----|----

| improve this answer | |
$\endgroup$
  • $\begingroup$ Looks good, but not optimal. Funnily enough I didn't allow dumping in my code. I should switch that on and see whether it changes things... $\endgroup$ – Dr Xorile Apr 11 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.