% -*- mode: Prolog -*-

% A simple puzzle solver, showing the use of EDCG notation.
% Solves https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_puzzle

:- use_module('../prolog/edcg.pl').  % :- use_module(library(edcg)).
:- use_module(library(apply)).
:- use_module(library(lists)).

%! print_solutions is semidet.
% Find all the solutions and print them out.
print_solutions :-
    setof(Moves, puzzle_moves(Moves), Solutions),
    print_term(Solutions, []).

% The "move" accumulator is a standard DCG-like accumulator
edcg:acc_info(move, T, Out, In, Out=[T|In]).

% The "state" accumulator keeps a list of seen states in reverse order
% and when a new state is added, checks that the state hasn't already
% been seen.
edcg:acc_info(state, NewState, States0, States, add_state(NewState, States0, States)).

add_state(NewState, SeenStates, [NewState|SeenStates]) :-
    \+ memberchk(NewState, SeenStates).

% The "final_state" accumulator is an example of passing a "context".
edcg:pass_info(final_state).

% The puzzle//2 predicate takes 2 parameters (Side, State) and
% implicitly passes around 3 accumulators, for a total of 5 extra
% parameters (1 for final_state, 2 for move, 2 for state).
edcg:pred_info(puzzle, 2, [final_state, move, state]).

%! puzzle_moves(-Moves) is nondet.
% Find one solution, putting the moves into the Moves parameter.
puzzle_moves(Moves) :-
    puzzle(hither,  % initial side
           state{farmer:hither, fox:hither, goose:hither, beans:hither},  % initial state
           state{farmer:yon,    fox:yon,    goose:yon,    beans:yon},     % final state
           Moves, [],  % move accumulator
           [], _       % seen_states accumulator
          ).

%! puzzle(+Side, +State) is nondet.
%         accumulators: [final_state, move, state]
% Given the current Side (hither, yon) and a State, compute a new
% move; terminate if already at the final state.
puzzle(_Side, State) -->>
    State/final_state,  % FinalState/final_state, FinalState = State
    !.
puzzle(Side, State) -->>
    % The "{...}" isn't needed because there are no edcg:pred_info/3
    % clauses for these predicates, but it's good documentation.
    { other_side(Side, OtherSide),
      cross_in_boat(State, Passengers),
      new_state(Passengers, OtherSide, State, State2),
      valid_state(State2),
      select(farmer, Passengers, PassengersWithoutFarmer)
    },
    [ State2 ]:state,
    [ PassengersWithoutFarmer:Side->OtherSide:State2 ]:move,
    puzzle(OtherSide, State2).

%! cross_in_boat(+State, -Passengers:list) is nondet.
% Select a passenger (or none) from the State; Passengers is either
% the farmer or farmer plus a single passenger.
cross_in_boat(_State, [farmer]).
cross_in_boat(State, [farmer, Passenger]) :-
    get_dict(Passenger, State, State.farmer), % Select passenger from same location as farmer
    Passenger \= farmer.

:- det(new_state/4).
%! new_state(+Passengers, +OtherSide, +State, -State2) is det.
% Generate a new State2 with the Passengers (which will also include
% the farmer) on the OtherSide.
new_state(Passengers, OtherSide, State, State2) :-
    foldl(state_move_passenger(OtherSide), Passengers, State, State2).

:- det(state_move_passenger/4).
%! state_move_passenger(+OtherSide, +Passenger, +State, -State2)  is det.
% Create a new state with the Passenger on the OtherSide.
state_move_passenger(OtherSide, Passenger, State, State2) :-
    put_dict(Passenger, State, OtherSide, State2).

%! valid_state(+State) is semidet.
% Test whether a State is valid (fox can't eat goose, goose can't eat beans)
valid_state(state{farmer:FarmerSide, fox:FoxSide, goose:GooseSide, beans:BeansSide}) :-
    (FoxSide \= GooseSide; FoxSide = FarmerSide),
    (GooseSide \= BeansSide; GooseSide = FarmerSide).

%! other_side(+Side, -OtherSide) is det.
% Enumerate the hither/yon, yon/hither values for switching sides.
other_side(hither, yon).
other_side(yon,    hither).