12
\$\begingroup\$

Context

The water buckets riddle or the water jugs riddle is a simple riddle that can be enunciated in a rather general form as:

Given \$n > 0\$ positive integers \$a_1, a_2, \cdots, a_n\$ representing the capacities (in units of volume) of \$n\$ buckets and a positive integer \$t \leq \max(a_1, a_2, \cdots, a_n)\$, find a sequence of "moves" that places \$t\$ units of volume of water in some bucket \$i\$.

To define the valid "moves", let \$c_1, c_2, \cdots, c_n\$ represent the units of volume of water each bucket \$i\$ contains, with \$0 \leq c_i \leq a_i\ \forall i\$. Then, at each step you can do any of the following:

  • fill a bucket \$i\$ entirely, setting \$c_i = a_i\$
  • empty a bucket \$i\$ entirely, setting \$c_i = 0\$
  • pour a bucket \$i\$ over a bucket \$j\$, setting

$$\begin{cases} c_i = \max(0, c_i - (a_j - c_j)) \\ c_j = \min(a_j, c_j + c_i) \end{cases}$$

i.e you pour bucket \$i\$ over bucket \$j\$ until bucket \$i\$ becomes empty or bucket \$j\$ becomes full, whatever happens first (or both if both things happen at the same time).

Task

Given the bucket capacities and the target measurement, your task is to output a minimal sequence of movements that places \$t\$ units of volume of water in one of the buckets.

Input

The capacities of the buckets are positive integers. You can assume these capacities are unique and ordered. You can take them in a number of reasonable formats, including but not limited to:

  • a list of integers
  • arguments to a function

Additionally, you will take a positive integer t that is not larger than the maximum number present in the input capacity list.

You can assume the input parameters specify a solvable instance of the water buckets problem.

Output

Your program/function/etc should output the shortest sequence of moves that places t units of volume of water in one of the buckets. If several such sequences exist you can output any one sequence. Please note that some moves commute and that also introduces multiple solutions to some problems.

Your program can print the sequence or return it as a list of moves or any other sensible thing.

To identify the moves and the buckets, you can choose any encoding suitable for your needs, as long as it is consistent across test cases and completely unambiguous. A suggestion is, use three letters to identify the three moves, like "E" for emptying a bucket, "F" for filling and "P" for pouring and use numbers to identify the buckets (0-index or 1-indexed or using its total capacity, for example).

With this encoding, to identify a move you always need one letter and a number. In case of a "pouring" move, a second integer is also needed. It is up to you to consistently use "P" n m as n was poured over m or m was poured over n.

Test cases

We use the encoding above and "P" n m means "pour bucket n over bucket m".

[1, 2, 3, 4], 1 -> ['F 1']
[1, 2, 3, 4], 2 -> ['F 2']
[1, 2, 3, 4], 3 -> ['F 3']
[1, 2, 3, 4], 4 -> ['F 4']
[13, 17], 1 -> ['F 13', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17', 'E 17', 'P 13 17', 'F 13', 'P 13 17']
[4, 6], 2 -> ['F 6', 'P 6 4']
[1, 4, 6], 2 -> ['F 6', 'P 6 4']
[3, 4, 6], 2 -> ['F 6', 'P 6 4']
[4, 5, 6], 2 -> ['F 6', 'P 6 4']
[4, 6, 7], 2 -> ['F 6', 'P 6 4']
[1, 3, 5], 2 -> ['F 3', 'P 3 1']
[7, 9], 4 -> ['F 9', 'P 9 7', 'E 7', 'P 9 7', 'F 9', 'P 9 7']
[8, 9, 13], 6 -> ['F 9', 'P 9 8', 'P 8 13', 'P 9 8', 'F 13', 'P 13 8']
[8, 9, 13], 7 -> ['F 8', 'P 8 9', 'F 8', 'P 8 9']
[8, 9, 11], 10 -> ['F 8', 'P 8 9', 'F 11', 'P 11 9']
[8, 9, 12], 6 -> ['F 9', 'P 9 12', 'F 9', 'P 9 12']
[8, 9, 12], 5 -> ['F 8', 'P 8 12', 'F 9', 'P 9 12']
[23, 37, 41], 7 -> ['F 41', 'P 41 23', 'P 41 37', 'P 23 41', 'F 41', 'P 41 23', 'P 41 37', 'F 41', 'P 41 37', 'E 37', 'P 41 37', 'E 37', 'P 41 37', 'F 41', 'P 41 37']
[23, 31, 37, 41], 7 -> ['F 23', 'P 23 37', 'F 31', 'P 31 37', 'P 31 41', 'P 37 31', 'P 31 41']

You can check a vanilla Python reference implementation here

\$\endgroup\$
  • \$\begingroup\$ Can I take n as input? \$\endgroup\$ – Surculose Sputum Mar 22 at 4:56
  • \$\begingroup\$ @SurculoseSputum in languages such as C and related ones, where you need such a parameter to know when the array ends, yes. If you are coding in python, then I'm afraid not. \$\endgroup\$ – RGS Mar 22 at 6:46
6
\$\begingroup\$

Python 3, 243 239 bytes

-4 bytes thanks to @JonathanFrech!

def f(a,t,k=1):
 while g(a,t,[0]*len(a),[],k):k+=1
def g(a,t,c,p,k):n=len(a);k,i=k//n,k%n;k,j=k//n,k%n;exec(["c[i]=0","c[i]=a[i]","x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x"][k%3]);p+=k%3,i,j;return g(a,t,c,p,k//3)if k>2else{t}-{*c}or print(p)

Try it online!

Input: a list of bucket capacities a, and the target t.
Output: to stdout, a list of integers, where each triplet m,i,j denotes a move: m is the move type (0,1,2 corresponds to empty, fill, pour), and i,j are the bucket indices (0-index). For move types empty and fill, the 2nd bucket is ignored.

How: Each sequence of moves p can be encoded by an integer k using modular arithmetic. g is a recursive function that checks if the sequence p encoded by k will result in the target t. If so, that sequence is printed to stdout, and a Falsy value is returned.

Old solution using itertools.product

Python 3.8 (pre-release), 279 249 bytes

Whopping -30 thanks to @ovs's double product trick!

from itertools import*
P=product
a,t=eval(input())
for r in count():
 for p in P(*tee(P((0,1,2),R:=range(n:=len(a)),R),r)):
  c=[0]*n;[exec(["c[i]=0","c[i]=a[i]","x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x"][m])for m,i,j in p]
  if t in c:print(p);exit()

Try it online!

Slow, ugly and can probably be golfed more.

Input: from stdin, a,t where a is the list of bucket capacities, and t is the goal.
Output: to stdout, the optimal list of moves, each move has the form (m, i, j) where:

  • m is the move type 0,1,2 (empty, fill, pour)
  • i and j are the target buckets' indices (0-index).
  • The moves empty and fill only affects the 1st bucket i, and thus the irrelevant 2nd bucket j is set to an arbitrary value.
  • The move (2,i,j) pours the water from bucket i to bucket j.

How: This program simply tries all possible sequence of move, in order of length.

To generate all sequence of r moves:

  • product((0,1,2), range(n), range(n)) generates a list of all possible moves by performing the Cartesian product between all move types 0,1,2, all values of i and all values of j.
  • tee(product(...), r) clones the move list into r lists.
  • product(*tee(...)) takes the Cartesian product ofrmove lists, which results in all possible sequence ofr` moves.

To perform a sequence of move p:

  • c[i]=0,c[i]=a[i], and x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x respectively handles emptying, filling, and pouring between bucket i and j. Note that pouring can handle i==j, which results in a no-op.
  • exec(["handle E", "handle F", "handle P"][m]) selects the correct handler for move type m.
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ The inner for-loop is a little shorter with another product: for p in product([x for x in product((0,1,2),R,R)if x[1]^x[2]],repeat=r): \$\endgroup\$ – ovs Mar 22 at 6:57
  • 1
    \$\begingroup\$ And you don't really need to check if i and j are distinct: for p in product(product((0,1,2),R,R),repeat=r) (this is even slower than before) \$\endgroup\$ – ovs Mar 22 at 7:07
  • 1
    \$\begingroup\$ I found by hand that the correct k was 2358833, which when reached produces the correct sequence. \$\endgroup\$ – Surculose Sputum Mar 22 at 15:13
  • 1
    \$\begingroup\$ Ok, thanks for taking your time to verify this! Cool solution :D \$\endgroup\$ – RGS Mar 22 at 15:51
  • 1
    \$\begingroup\$ p+=[(k%3,i,j)]; ~> p+=(k%3,i,j),;. \$\endgroup\$ – Jonathan Frech Mar 22 at 23:42
3
\$\begingroup\$

JavaScript (ES6),  197 191  188 bytes

Takes input as (a)(t).

Returns a string of concatenated operations Fx, Ex or Px>y, with 0-indexed buckets.

a=>F=(t,N)=>(g=(b,n,o)=>[...b,0].some((V,i,x)=>(x=a[i])-V^t?n&&b.some((v,j,[...B])=>(s='F',B[j]=i-j?x?(v+=V)-(B[s=`P${i}>`,i]=x<v?x:v):a[s='E',j]:0,g(B,n-1,[o]+s+j))):O=o))(a,N)?O:F(t,-~N)

Try it online!

The above test link inserts spaces between operations for readability. Some longer test cases have been removed.

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

Javascript, 364 bytes

I'm sure this can be golfed much better pretty easily.

S=t=>G=>{L=t.length;r=(f,n,a,i,e=0)=>{if(0==n)return f.indexOf(G)>=0&&[];a=(A,B,C,D)=>(X=f.slice(),X[A]=B,X[C]=D,X);for(;e<L;++e){for(K of[0,t[e]])if(F=r(a(e,K),n-1))return[[+!K,e]].concat(F);for(i=0;i<L;++i)if(i!=e&&(O=r(a(e,Math.max(0,f[e]-t[i]+f[i]),i,Math.min(t[i],f[e]+f[i])),n-1)))return[[2,e,i]].concat(O)}};for(T=1;!(E=r(Array(L).fill(0),T));++T);return E}

Returns an array of arrays. Each array is in the format [n, i] if n=0 (fill) or n=1 (empty), or [2, i, j] for "pour bucket i into bucket j". The buckets are always given as indices, starting from 0.

Uses the same basic search method as the other answers. Unminified version:

var S = (capacities, target) => {
    let n = capacities.length;
    var waterBuckets = (levels, maxSteps) => {
      if (maxSteps == 0) return levels.indexOf(target) >= 0 ? [] : false;
      let getCopy = () => levels.slice();
      for (let i = 0; i < n; ++i) {
        for (let level of [0, capacities[i]]) {
          let levelsCopy = getCopy();
          levelsCopy[i] = level;
          let res = waterBuckets(levelsCopy, maxSteps - 1);
          if (res) return [[+!level, i]].concat(res);
        }
        for (let j = 0; j < n; ++j) {
          if (i === j) continue;
          let levelsCopy = getCopy();
          levelsCopy[i] = Math.max(0, levels[i] - capacities[j] + levels[j]);
          levelsCopy[j] = Math.min(capacities[j], levels[i] + levels[j]);
          let res = waterBuckets(levelsCopy, maxSteps - 1);
          if (res) return [[2, i, j]].concat(res);
        }
      }
    };
    for (let s = 1;; ++s) {
      let r = waterBuckets(Array(n).fill(0), s);
      if (r) return r;
    }
};
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 112 104 bytes

⊞υEθ⁰Fυ¿¬ⅈ¿№…ιLθη⪫✂ιLθLι¹ «FLθF²⊞υ⁺Eι⎇⁼κν∧λ§θκμ⟦§EFλκ⟧FLθFLθ¿⁻λκ«≔⌊⟦§ιλ⁻§θκ§ικ⟧ε⊞υ⁺Eι⎇⁼κν⁺με⎇⁼λν⁻μεμ⟦Pλκ

Try it online! Link is to verbose version of code. Could save 6 bytes by including the final bucket state in the output. The code spends most of its time emptying or pouring empty buckets, so don't try it on the harder problems. Explanation:

⊞υEθ⁰

Start off with all buckets empty and no operations so far. (Each entry comprises n buckets plus an unspecified number of operations.)

Fυ¿¬ⅈ

Perform a breadth-first search until a solution has been printed. (This relies on t being positive, as that means that at least one step is necessary.)

¿№…ιLθη⪫✂ιLθLι¹ «

If one of the first n buckets contains t then this is a solution in which case output it, otherwise:

FLθF²

Loop over each bucket and whether it's being emptied or filled.

⊞υ⁺Eι⎇⁼κν∧λ§θκμ⟦§EFλκ⟧

Calculate the new bucket values and append the result with the additional operation.

FLθFLθ¿⁻λκ«

Loop over each pair of distinct buckets.

≔⌊⟦§ιλ⁻§θκ§ικ⟧ε

Calculate the amount that can be poured from one bucket to the other.

⊞υ⁺Eι⎇⁼κν⁺με⎇⁼λν⁻μεμ⟦Pλκ

Calculate the new bucket values and append the result with the additional operation. Adding an extra ¿ε to the beginning of this block does make the code a bit faster but it wasn't significant enough to be able to solve the harder problems on TIO.

|improve this answer|||||
\$\endgroup\$

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.