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
nas input? \$\endgroup\$