/* 

  Search examples in Picat.

  From Nilsson & Matuszynski: "Logic, Programming and Prolog"
  Page 201ff (Chapter 11: Searching in State-Space)

  This model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import v3_utils.

main => go.

%
% Simple "graph" search
%
go ?=>
  if path(a,c) then
    println($path(a,c)=ok)
  else
    println($path(a,c)=not_ok)
  end,

  path(a,X),
  println(a=X),
  fail,
  
  nl.
go => true.

%
% "Graph" search with path
% 
go2 ?=>
  path2(a,X,Path),
  println(X=Path),
  fail,
  
  nl.
go2 => true.

%
% Water jug problem
% There are 27 different solutions (as stated in the book, page 206)
/*
p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(4,0),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(4,3),p(1,3),p(4,0),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(0,3),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(0,3),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(3,0),p(0,3),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(3,0),p(0,3),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,3),p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
[p(2,0),p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(4,3),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
*/
go3 ?=>
  path3(X),
  println(X),
  fail,
  nl.
go3 => true.

%
% Water jug problem: (First) shortest solution:
% [p(2,3),p(4,1),p(0,1),p(1,0),p(1,3),p(4,0),p(0,0)]
%
% Note: There is another solution of the same length
% [p(2,0),p(0,2),p(4,2),p(3,3),p(3,0),p(0,3),p(0,0)]
% 
go4 ?=>
  length(X,_),
  path3(X),
  println(X),
  % fail, % show the path in increasing order (but loops forever)
  nl.
go4 => true.

%
% BSF (graph)
% 
% Picat> path4(a,X),println(X),fail
% a
% b
% c
% d
% e
% f
% g
% h
% 
go5 ?=>
  path4(a,X),
  println(X),
  fail,
  nl.
go5 => true.


%
% page 203
%
edge(a,b). edge(b,a). % cycle!
edge(a,c).
edge(b,d). edge(b,e).
edge(c,e). edge(d,f).
edge(e,f). edge(e,g).

path(X,Y) :- path(X,Y,[X]).
path(X,X,_Visited).
path(X,Z,Visited) :-
  edge(X,Y),
  not member(Y,Visited),
  path(Y,Z,[Y|Visited]).


path2(X,Y,Path) :-
  path2(X,Y,[X],Path).
path2(X,X,Visited,Visited).
path2(X,Z,Visited,Path) :-
  edge(X,Y),
  not member(Y,Visited),
  path2(Y,Z,[Y|Visited],Path).


%
% Water Jugs problem
% page 204ff
% The book use X:Y for the path, here we use p(X,Y)
action(p(X,Y), p(0,Y)) :- X > 0.
action(p(X,Y), p(X,0)) :- Y > 0.
action(p(X,Y), p(4,Y)) :- X < 4.
action(p(X,Y), p(X,3)) :- Y < 3.

action(p(X,Y), p(4,Z)) :- X < 4, Z is Y - (4 - X), Z>= 0.
action(p(X,Y), p(Z,3)) :- Y < 3, Z is X - (3 - Y), Z>= 0.
action(p(X,Y), p(Z,0)) :- Y > 0, Z is X + Y, Z =< 4.
action(p(X,Y), p(0,Z)) :- X > 0, Z is X + Y, Z =< 3.

path3(X) :-
  path3($p(0,0),$[p(0,0)],X).
path3(p(2,_X),Visited,Visited).
path3(State,Visited,Path) :-
  action(State,NewState),
  not member(NewState,Visited),
  path3(NewState,[NewState|Visited],Path).


%
% Breadth First Search (BFS), page 208ff
% Searching a graph.
%
children(a,[b,c]).
children(b,[d,e]).
children(c,[f]).
children(e,[g,h]).

%
% Note: There's some typos in the book (page 209):
% It shows "leaf" but it should be "Leaf".
% 
path4(X,Y) :- bf_path([[X]],Y).
bf_path([[Leaf|_Branch]|_Branches],Leaf).
bf_path([[Leaf|Branch]|Branches],Goal) :-
  children(Leaf,Adjacent),
  expand([Leaf|Branch],Adjacent,Expanded),
  append(Branches,Expanded,NewBranches),
  bf_path(NewBranches,Goal).
bf_path([[Leaf|_Branch]|Branches],Goal) :-
  not children(Leaf,_Leaves), % unsafe not
  bf_path(Branches,Goal).

expand(_X,[],[]).
expand(X,[Y|Z],[[Y|X]|W]) :-
  expand(X,Z,W).