|
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/ 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 |