3 ms·

Here's a gist in Prolog that I believe solves this puzzle: https://gist.github.com/deosjr/7314659509333ee2ad67dbf276e8d487 https://gist.github.com/deosjr/731465

• jodrellblank 2y ago
  Here's my Prolog code which solves (small inputs) of the puzzle, taking the core grammar of moves//3 from the Water Jug solution in Markus Triska's Power of Prolog video "Sparrows on Eagles: Delegate your work to Prolog!"[1] (I couldn't have written that style myself from scratch): :- use_module(library(dif)). % Sound inequality :- table split/2, merge/3, moves//3. % Replace one number H from a list with % two A and B which sum to that number. split([], []). split([H|T], [A,B|T]) :- between(1,H, A), between(1,H, B), dif(A,B), H is A+B. split([H|T], [H|T2]) :- split(T, T2). % Merge two adjacent numbers A and B from a list by % summing into H, unless that would exceed list Max. merge([], _, []). merge([H|T], Max, [H|T2]) :- merge(T, Max, T2). merge([A,B|T], Max, [H|T]) :- H is A + B, H =< Max. % Describes moves from starting state S0 % to Target state, by splitting, merging, % and checking for duplicates using sort. moves(S0, _, Target) --> { member(Target, S0) }. moves(S0, Max, Target) --> [Ns], { select(Ns0, S0, S), (split(Ns0, Ns) ; merge(Ns0, Max, Ns)), sort(Ns, NsSet), same_length(Ns, NsSet) }, moves([Ns|S], Max, Target). solve(S0, [S0|Moves]) :- max_list(S0, Max), reverse(S0, Target), phrase(moves([S0], Max, Target), Moves). e.g. with the query: ?- between(1, 20, MoveCount), length(Moves, MoveCount), solve([5,1,20], Moves). Answer: Moves = [[7, 5, 3], [7, 1, 4, 3], [2, 5, 1, 4, 3], [2, 6, 4, 3], [2, 1, 5, 4, 3], [2, 1, 5, 7], [3, 5, 7]], MoveCount = 7 It will run in https://swish.swi-prolog.org/ https://swish.swi-prolog.org/ clicking the 'Empty' then 'Program' and pasting the code in, querying (without the ?- and trailing .) in the lower right. Taking the technique from the video; the query uses length/2 to lengthen the list of answer moves one at a time before the answer is sought, this code does iterative deepening and will find the shortest sequence of moves first. [1] https://www.youtube.com/watch?v=vdabv9EkYrY https://www.youtube.com/watch?v=vdabv9EkYrY