0
\$\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\$
8
  • 3
    \$\begingroup\$ Related: codegolf.stackexchange.com/q/20754/12012 \$\endgroup\$
    – Dennis
    Jan 3, 2017 at 18:49
  • \$\begingroup\$ Should it brute-force using any specific algorithm? \$\endgroup\$
    – wizzwizz4
    Jan 3, 2017 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, 2017 at 19:01
  • \$\begingroup\$ @dfernan What determines "as necessary"? \$\endgroup\$
    – wizzwizz4
    Jan 3, 2017 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\$ Jan 3, 2017 at 19:08

2 Answers 2

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.

\$\endgroup\$
0
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

\$\endgroup\$
7
  • 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, 2017 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\$ Jan 3, 2017 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, 2017 at 21:23
  • \$\begingroup\$ Also use single spaces for your indents and it should go well under 200. \$\endgroup\$
    – ElPedro
    Jan 3, 2017 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\$ Jan 3, 2017 at 21:25

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