Solving the water bucket riddle! 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 &gt; 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 -&gt; ['F 1']
[1, 2, 3, 4], 2 -&gt; ['F 2']
[1, 2, 3, 4], 3 -&gt; ['F 3']
[1, 2, 3, 4], 4 -&gt; ['F 4']
[13, 17], 1 -&gt; ['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 -&gt; ['F 6', 'P 6 4']
[1, 4, 6], 2 -&gt; ['F 6', 'P 6 4']
[3, 4, 6], 2 -&gt; ['F 6', 'P 6 4']
[4, 5, 6], 2 -&gt; ['F 6', 'P 6 4']
[4, 6, 7], 2 -&gt; ['F 6', 'P 6 4']
[1, 3, 5], 2 -&gt; ['F 3', 'P 3 1']
[7, 9], 4 -&gt; ['F 9', 'P 9 7', 'E 7', 'P 9 7', 'F 9', 'P 9 7']
[8, 9, 13], 6 -&gt; ['F 9', 'P 9 8', 'P 8 13', 'P 9 8', 'F 13', 'P 13 8']
[8, 9, 13], 7 -&gt; ['F 8', 'P 8 9', 'F 8', 'P 8 9']
[8, 9, 11], 10 -&gt; ['F 8', 'P 8 9', 'F 11', 'P 11 9']
[8, 9, 12], 6 -&gt; ['F 9', 'P 9 12', 'F 9', 'P 9 12']
[8, 9, 12], 5 -&gt; ['F 8', 'P 8 12', 'F 9', 'P 9 12']
[23, 37, 41], 7 -&gt; ['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 -&gt; ['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
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&gt;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.