% ======================================================================= %
% Prolog Homework #4                                                      %
% 05/10/2018                                                              %
% Sam Titarsolej, 12206385, s.titarsolej@gmail.com                        %
% ======================================================================= %

% ======================================================================= %
% ||                                                                   || %
% ||                          Exercise 1                               || %
% ||                                                                   || %
% ======================================================================= %

% ======================================================================= %
%                                 A                                       %
% ======================================================================= %

% State zoals in B?

% ======================================================================= %
%                                 B                                       %
% ======================================================================= %

/*
Using the implementations for the different possible arithmetic operations,
we can implement the move/2 predicate. First we select two unique integers
from the current state list, using select/3 and member/2
*/

move(Target:State, Target:NewState) :-
    select(A, State, State1),
    member(B, State1),
    (move(Target:State, [A + B], Target:NewState); % Either +
    move(Target:State, [A - B], Target:NewState); % Or -
    move(Target:State, [A * B], Target:NewState); % Or *
    move(Target:State, [A / B], Target:NewState)). % Or B

/*
Different implementations for each of the possible arithmetic operations.
For each operation we expect three arguments: the current state, the
arithmetic operation we want to execute, and the resulting state. The
second argument must be in the form [A {OPERATION} B], where A and B are
numbers from the current state. This way we can simply add the operation to
the head of the resulting state. We also have to remove A and B from the
resulting state list. We can do this using the select/3 predicate.
*/

move(Target:State, [A + B], Target:[A + B | State3]) :-
    select(A, State, State2),
    select(B, State2, State3).

move(Target:State, [A - B], Target:[A - B | State3]) :-
    select(A, State, State2),
    select(B, State2, State3).

move(Target:State, [A * B], Target:[A * B | State3]) :-
    select(A, State, State2),
    select(B, State2, State3).

/*
For division we need to do two more checks; whether the arthitmetic
expression in B is not zero (to prevent a zero divisor), and whether A/B
results in an integer.
*/

move(Target:State, [A / B], Target:[A / B | State3]) :-
    \+ (0 =:= B),
    0 =:= A mod B,
    select(A, State, State2),
    select(B, State2, State3).

% ======================================================================= %
%                                  c                                      %
% ======================================================================= %

goal(Target:State) :-
    nth1(1, State, X),
    Goal =.. [is, Target, X],
    call(Goal).

% ======================================================================= %
%                                   D                                     %
% ======================================================================= %

solve(Target, State, Solution) :-
    id(Target:State, Path),
    last(Path, Target:SolutionList),
    nth1(1, SolutionList, Solution).

% ======================================================================= %
% ||                                                                   || %
% ||                        Search algorithms                          || %
% ||                                                                   || %
% ======================================================================= %

solve_depthfirst(Node, [Node|Path]) :-
    depthfirst(Node, Path).

depthfirst(Node, []) :-
    goal(Node).

depthfirst(Node, [NextNode|Path]) :-
    move(Node, NextNode),
    depthfirst(NextNode, Path).

solve_depthfirst_cyclefree(Node, Path) :-
    depthfirst_cyclefree([Node], Node, RevPath),
    reverse(RevPath, Path).

depthfirst_cyclefree(Visited, Node, Visited) :-
    goal(Node).

depthfirst_cyclefree(Visited, Node, Path) :-
    move_cyclefree(Visited, Node, NextNode),
    depthfirst_cyclefree([NextNode|Visited], NextNode, Path).

move_cyclefree(Visited, Node, NextNode) :-
    move(Node, NextNode),
    \+ member(NextNode, Visited).

solve_depthfirst_bound(Bound, Node, Path) :-
    depthfirst_bound(Bound, [Node], Node, RevPath),
    reverse(RevPath, Path).

depthfirst_bound(_, Visited, Node, Visited) :-
    goal(Node).

depthfirst_bound(Bound, Visited, Node, Path) :-
    Bound > 0,
    move_cyclefree(Visited, Node, NextNode),
    NewBound is Bound - 1,
    depthfirst_bound(NewBound, [NextNode|Visited], NextNode, Path).

id(Node, Path) :-
    id(Node, 0, Path).

id(Node, N, Path) :-
    solve_depthfirst_bound(N, Node, Path).

id(Node, N, Path) :-
    \+ solve_depthfirst_bound(N, Node, Path),
    N1 is N + 1,
    id(Node, N1, Path).