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$
3
  • $\begingroup$ math.stackexchange.com/questions/1178368/… $\endgroup$
    – RobPratt
    Apr 11, 2020 at 0:37
  • $\begingroup$ That's cool, @RobPratt! I thought someone must have looked at it. $\endgroup$
    – Dr Xorile
    Apr 11, 2020 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, 2020 at 5:11

2 Answers 2

2
$\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

$\endgroup$
2
  • $\begingroup$ I got this, too, but you posted before I could type it up. Nice job. $\endgroup$ Apr 11, 2020 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, 2020 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
 ----|----|----

$\endgroup$
1
  • $\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, 2020 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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