Hacker News new | past | comments | ask | show | jobs | submit login

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




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: