-2
\$\begingroup\$

Introduction

The well-known "Die Hard with a Vengeance" water jugs puzzle challenges the two heroes to get 4L of water in a 5L container, provided an unlimited supply of water and another container of 3L. This problem has a solution because 4 is less or equal than the largest container and is a multiple of the gcd(5, 3) = 1 as per number theory. The same goes for other combinations of container sizes as long as the Greatest Common Divisor (GCD) requirements are satisfied for a target value.

Task

In one sentence, the task is to brute-force two solutions by filling and emptying two containers as well as transferring amounts between one another for any given container sizes and target value. The brute-force lies on repeatedly transferring amounts from one container to another, refilling the first when it runs out and emptying the second when it fills up, until any of them contain the target value.

The program should make two runs to respectively find two solutions by swapping container positions (i.e., the container receiving water from the other swaps with that one). The container states should be printed throughout all steps (refilling or emptying and transferring water).

This is code golf, so lowest byte count wins.

Examples

Examples follow below for (5, 3, 4) and (17, 5, 7) with 4 and 7 being the target values. Comments added for description purposes.

5 3 4
[5, 0] # initial state
[2, 3] # transferring
[2, 0] # emptying
[0, 2] # transferring
[5, 2] # refilling
[4, 3] # transferring, solution found
3 5 4
[3, 0]
[0, 3]
[3, 3]
[1, 5]
[1, 0]
[0, 1]
[3, 1]
[0, 4]

17 5 7
[17, 0] # initial state
[12, 5] # transferring
[12, 0] # emptying
[7, 5]  # transferring, solution found
5 17 7
[5, 0]
[0, 5]
[5, 5]
[0, 10]
[5, 10]
[0, 15]
[5, 15]
[3, 17]
[3, 0]
[0, 3]
[5, 3]
[0, 8]
[5, 8]
[0, 13]
[5, 13]
[1, 17]
[1, 0]
[0, 1]
[5, 1]
[0, 6]
[5, 6]
[0, 11]
[5, 11]
[0, 16]
[5, 16]
[4, 17]
[4, 0]
[0, 4]
[5, 4]
[0, 9]
[5, 9]
[0, 14]
[5, 14]
[2, 17]
[2, 0]
[0, 2]
[5, 2]
[0, 7]
\$\endgroup\$
  • 3
    \$\begingroup\$ Related: codegolf.stackexchange.com/q/20754/12012 \$\endgroup\$ – Dennis Jan 3 '17 at 18:49
  • \$\begingroup\$ Should it brute-force using any specific algorithm? \$\endgroup\$ – wizzwizz4 Jan 3 '17 at 18:57
  • \$\begingroup\$ @wizzwizz4 The brute-force part refers to repeatedly refilling or emptying as necessary and transferring water from one container to another. \$\endgroup\$ – dfernan Jan 3 '17 at 19:01
  • \$\begingroup\$ @dfernan What determines "as necessary"? \$\endgroup\$ – wizzwizz4 Jan 3 '17 at 19:02
  • 2
    \$\begingroup\$ I think this is performing a simple naive search based on a couple of rules. Let me see if I can code something up. \$\endgroup\$ – Gabriel Benamy Jan 3 '17 at 19:08
2
\$\begingroup\$

Batch, 218 bytes

@echo off
set/al=r=0
:l
echo %l% %r%
set/at=r+l
if %l% neq %3 if %r% neq %3 ((if %r%==%2 (set r=0)else if %l%==0 (set l=%1)else if %t% leq %2 (set/ar=t,l=0)else set/ar=%2,l=t-%2)&goto l)
if "%4"=="" %0 %2 %1 %3 .

Putting everything into one big if statement saves 11 bytes. %4 is just used to make the file loop twice with the arguments exchanged.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Python 2 - 222/384, 190 174/360 352 336 Bytes

This version that only outputs the solution is 174 bytes.

a,b,c=input()
d,e=0,0
for i in range(2):
 while d!=c and e!=c:
   if e<b:
     if d>0:
       if e+d<=b:e+=d;d=0
       else:n=d+e-b;e=b;d=n 
     else:d=a 
   else:e=0
 print d,e
 b,a,d,e=a,b,0,0

Try it here!

Example Output:

![enter image description here

Explanation:

a,b,c=input()                      # Value of jug 1, jug 2, target value
d,e=0,0                            # Water held in each jug
for i in range(2):                 # Loop twice
  while d!=c and e!=c:             # While no solution
    if e<b:                        # If jug 2 can hold more water
      if d!=0:                     # If jug 1 has water 
        if e+d<=b:e+=d;d=0         # If no overfill, pour all of jug 1 into 2
        else:n=d+e-b;e=b;d=n       # Else fill up as much as possible
      else:d=a                     # Else jug 1 has no water, fill it
    else:e=0                       # Else jug 2 is full, empty it
  print d,e                        # Print solution
  b,a,d,e=a,b,0,0                  # Switch the two jugs' values, empty all jugs

It implements this algorithm. With the new edit, the code becomes 326 bytes:

a,b,c=input(),input(),input()
d,e=0,0
g=[d,e]
for i in"xx":
 while d!=c and e!=c:
   g=[d,e]
   if e<b:
     if d!=0:
       if e+d<=b:e+=d;d=0;print"Transferring Water"
       else:n=d+e-b;e=b;d=n;print"Transferring Water" 
     else:d=a;print"Filling Water"
   else:e=0;print"Emptying Water"
   print g
 print[d,e],"Solution Found"
 b,a,d,e=a,b,0,0;print"Resetting"

Try this version here

Explanation and Output

Explanation is the same except with text and g is used to output the values of the two jugs and final solution. Output:

enter image description here

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 16 bytes by changing your first two lines to a,b,c,d,e=input(),0,0 and taking input all together. \$\endgroup\$ – Theo Jan 3 '17 at 21:06
  • \$\begingroup\$ @Theo This doesn't work if I enter a number with n digits where n is not divisible by three \$\endgroup\$ – Anthony Pham Jan 3 '17 at 21:12
  • \$\begingroup\$ You don't use i so for i in range(2) can become for i in'xx':. Also d!=0 can be d>0. Saves a few. \$\endgroup\$ – ElPedro Jan 3 '17 at 21:23
  • \$\begingroup\$ Also use single spaces for your indents and it should go well under 200. \$\endgroup\$ – ElPedro Jan 3 '17 at 21:25
  • \$\begingroup\$ @ElPedro I just edited my post to use single space indents. I used double space indents in my explanation for readability \$\endgroup\$ – Anthony Pham Jan 3 '17 at 21:25

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