/*

  Maze problem in Picat.

  Maze problem from Chapter 4 of 
  Peter Norvig's Paradigms of Artificial Intelligence Programming (PAIP)

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

*/

import planner.
import bplan.

main => go.


go => 
   % Norvig's problem
   Init = 1,
   Final = 25,
   problem(1,Maze),
   solve_maze(Maze, Init,Final,Plan),
   print_plan(Init, Final, Plan),
   nl.


%
% Solve all problems in the Norvig's Maze and
% also show the longest plans.
%
go2 => 
   problem(1,Maze),
   PlanLens = [],
   foreach(Init in 1..25, Final in 1..25, Init != Final)
      printf("Problem %d -> %d\n", Init, Final),
      if solve_maze(Maze, Init,Final, Plan) then
         print_plan(Init, Final, Plan),
         PlanLens := PlanLens ++ [[Init,Final,Plan.length,Plan]]
      else 
         println("No solution.\n"),
         PlanLens := PlanLens ++ [[Init,Final,0,[]]]
      end
   end,
   println("Longest plans:"),
   MaxLen = max([Len : [_,_,Len,_] in PlanLens]),
   writeln(maxLen=MaxLen),
   MaxLens=[[Init,Final,Plan] : [Init,Final,Len,Plan] in PlanLens, Len == MaxLen ],
   foreach([Init,Final,Plan] in MaxLens) print_plan(Init,Final,Plan) end,
   nl.


solve_maze(Maze,Init,Final, Plan) =>

   Facts = [$[maze(From,To), maze(To,From)] : [From,To] in Maze].flatten() ++ [$final(Final)], % undirected
   % Facts = [$[maze(From,To)] : [From,To] in Maze].flatten() ++ [$final(Final)], % directed graph
   % writeln(facts=Facts),
   cl_facts(Facts),

   time(planner.best_plan(Init,Plan)),
   % print_plan(Init, Final, Plan),
   write(len=Plan.length),nl.


print_plan(Init, Final, Plan) => 
   printf("\nFrom %w -> %w\n", Init, Final),
   foreach([From,To] in Plan) printf("%w -> %w\n", From,To) end, 
   nl.


problem(1,Maze) => 
   Maze = 
      [[1,2],[2,3],[3,4],[4,9],[9,14],[9,8],[8,7],[7,12],[12,13],
       [12,11],[11,6],[11,16],[16,17],[17,22],[21,22],[22,23],
       [23,18],[23,24],[24,19],[19,20],[20,15],[15,10],[10,5],[20,25]].


action(From,To,Move,Cost) => 
   maze(From,To),
   Move = [From,To],
   Cost = 1.