/* 

  Blocks world problem in Picat.

  I start with the problem from:
  http://www.idi.ntnu.no/emner/tdt4136/PRO/blocksworld.txt
  (AIMA, Ch. 11.1  Example The blocks world)

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

*/

import util.
import gps_utils.
import planner.

main => go.


% Problem from 
% http://www.idi.ntnu.no/emner/tdt4136/PRO/blocksworld.txt
%
%  B             
%  A       ==>       A
%  C              B  C
% -----         -------
% 
% Solved in 0.02s
%
go =>
  println("BAC -> B,AC"),
  Init = $[on(b,a), on(a,c), on(c,table), clear(table), clear(b)],
  Final = $[on(b,table), on(c,table), on(a,c)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),  
  nl.

% 
%   A          C 
%   B    ==>   B
%   C          A
%   ----      -------
%
% Solved in 0.02s
%
go2 => 
  println("ABC->CBA"),
  Init = $[on(a,b), on(b,c), on(c,table), clear(table), clear(a)],
  Final = $[on(a,table), on(b,a), on(c,b)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),  
  nl.


% Sussman's Anomaly:
% (It's a problem for linear planners.)
%                 A
%      C    ==>   B
%    B A          C
%   ----      -------
%
% Solved in 0.02s
%
go3 => 
  println("Sussman's Anomaly: B,CA -> ABC"),
  Init = $[on(a,table), on(b,table), on(c,a), clear(table), clear(b),clear(c)],
  % Final = $[on(a,b), on(b,c), on(c,table)],
  Final = $[on(c,table), on(a,b), on(b,c)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),  
  nl.


%
%   A       H
%   B       G
%   C       F
%   D   =>  E
%   E       D
%   F       C
%   G       B
%   H       A
%  ---     ---
%
% Solved in 0.02s
%
go4 => 
  println("A..H -> H..A"),
  Init = $[on(a,b), on(b,c), on(c,d), on(d,e), on(e,f), on(f,g), on(g,h),
           on(h,table), clear(table), clear(a)],
  Final = $[on(a,table), on(b,a), on(c,b), on(d,c), on(e,d), on(f,e), 
            on(g,f),on(h,g)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  nl.


% From
%   Naresh Gupta, Dana S. Nau: On the Complexity of Blocks-World Planning
%   (Artificial Intelligence, 56(2-3):223-254, August 1992),
%   page 11, Figure 5
%
%             J                J
%    A  D  G  K       A  D  G  C
%    B  E  H  L   =>  K  L  M  F
%    C  F  I  M       B  E  H  I
%    -----------      ------------
%
% Solved in 0.15s
%
go5 =>
  Init = $[on(a,b), on(b,c), on(c,table),
           on(d,e), on(e,f), on(f,table),
           on(g,h), on(h,i), on(i,table),
           on(j,k), on(k,l), on(l,m), on(m,table),
           clear(a),clear(d),clear(g),clear(j),clear(table)],
  Final =$[on(a,k), on(k,b), on(b,table),
           on(d,l), on(l,e), on(e,table),
           on(g,m), on(m,h), on(h,table),
           on(j,c), on(c,f), on(f,i), on(i,table)
           ,clear(a),clear(d),clear(g),clear(j)
           ],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  % gps_plan(Init),
  nl.

%
% From
%   Naresh Gupta, Dana S. Nau: On the Complexity of Blocks-World Planning
%   (Artificial Intelligence, 56(2-3):223-254, August 1992),
%   page 12, Figure 6: "A problem that contains a deadlock but 
%                       no deleted-condition interactions".
%
%  
%   A  B      B  A
%   C  D  =>  C  D
%   -----     -----
%
% Solved in 0.02s
%
go6 => 
  Init = $[on(a,c),on(c,table),on(b,d), on(d,table),
           clear(a),clear(b),clear(table)],
  Final = $[on(b,c),on(c,table),on(a,d),on(d,table)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  % gps_plan(Init),
  nl.
 
%
% From http://code.google.com/p/prose/wiki/BlocksWorld
%
%            G
%      B     H       A  D  G
%      C  E  I   =>  B  E  H
%   A  D  F  J       C  F  I  J
%   ------------     ----------
%
% Solved in 0.34s
% 
go7 =>
  Init = $[on(a,table),
           on(b,c),on(c,d),on(d,table),
           on(e,f),on(f,table),
           on(g,h),on(h,i),on(i,j),on(j,table),
           clear(a),clear(b),clear(e),clear(g),clear(table)
            ],
  Final = $[on(a,b),on(b,c),on(c,table),
            on(d,e),on(e,f),on(f,table),
            on(g,h),on(h,i),on(i,table),
            on(j,table)],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  nl.

%
% From
% Cecilia Nugraheni and Luciana Abednego:
% "Modelling Sudoku Puzzles as Block-world Problems"
% 
%
%  A               E
%  C        =>  A  D
%  D  B  E      B  C
%  -------      ----
%
% Solved in 0.02s
%
go8 =>
   Init = $[on(a,c),on(c,d),on(d,table),on(b,table),on(e,table),    
            clear(a),clear(b),clear(e)],
   Final = $[on(a,b),on(b,table),on(e,d),on(d,c),on(c,table)],
   cl_facts($[final2(Final)]),
   gps_best_plan(Init),
   nl.

%
% A harder variant of go5/0 (adding n,o,p,q)
%
%             J  Q      Q        J
%    A  D  G  K  P      A  D  G  C  N
%    B  E  H  L  O  =>  K  L  M  F  O
%    C  F  I  M  N      B  E  H  I  P
%    -------------      ------------
%
% Solved in 0.5s
%
go9 =>
  Init = $[on(a,b), on(b,c), on(c,table),
           on(d,e), on(e,f), on(f,table),
           on(g,h), on(h,i), on(i,table),
           on(j,k), on(k,l), on(l,m), on(m,table),
           on(q,p), on(p,o), on(o,n),on(n,table),
           clear(a),clear(d),clear(g),clear(j),clear(q), clear(table)],
  Final =$[on(q,a), on(a,k), on(k,b), on(b,table),
           on(d,l), on(l,e), on(e,table),
           on(g,m), on(m,h), on(h,table),
           on(j,c), on(c,f), on(f,i), on(i,table),
           on(n,o), on(o,p), on(p,table)
           , clear(q),clear(d),clear(g),clear(j), clear(n)
           ],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  nl.


%
% A variant of go9, just shifting the bottom row.
%
%             J  N               J  N
%    A  D  G  K  O      A  D  G  K  O
%    B  E  H  L  P  =>  B  E  H  L  P
%    C  F  I  M  Q      Q  C  F  I  M
%    -------------      ------------
%
% Solved in 59s: 27 moves
%
go10 =>
  Init = $[on(a,b), on(b,c), on(c,table),
           on(d,e), on(e,f), on(f,table),
           on(g,h), on(h,i), on(i,table),
           on(j,k), on(k,l), on(l,m),on(m,table),
           on(n,o), on(o,p), on(p,q),on(q,table),
           clear(a),clear(d),clear(g),clear(j),clear(n), clear(table)],
  Final =$[on(a,b), on(b,q), on(q,table),
           on(d,e), on(e,c), on(c,table),
           on(g,h), on(h,f), on(f,table),
           on(j,k), on(k,l), on(l,i),on(i,table),
           on(n,o), on(o,p), on(p,m),on(m,table) 
           , clear(a),clear(d),clear(g),clear(j), clear(n)
           ],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init), % 59s: 27 moves
  % gps_plan(Init,1000), % 13.7s: 981 moves
  % gps_plan(Init,900), % 19.2s 881 moves
  % gps_plan(Init,100), % 19.3s 81 moves
  % gps_plan(Init,70), % 8.3s 51 moves
  % gps_best_plan(Init,70), % 1:03min 31 moves
  % gps_best_plan(Init,70), % 1:03min 31 moves
  % gps_best_plan(Init,27*4), 
  nl.


%
%
%    A  C  E  G  =>  B  D  F  H
%    B  D  F  H      A  C  E  G
%    -------------   -------------
%
% Solved in 0.03s, 22 moves
%
go11 =>
  Init = $[on(a,b), on(b,table),on(c,d), on(d,table),on(e,f), on(f,table),
           on(g,h), on(h,table),
           clear(a),clear(c),clear(e),clear(g),clear(table)],
  Final =$[on(b,a), on(a,table),on(d,c), on(c,table),on(f,e), on(e,table),
           on(h,g), on(g,table)
           %, clear(b),clear(d),clear(f),clear(h)
           ],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init),
  nl.

%
% A variant of go9, just shifting the two bottom rows.
%
%    A  D  G  K  O      A  D  G  K  O
%    B  E  H  L  P  =>  P  B  E  H  K
%    C  F  I  M  Q      Q  C  F  I  M
%    -------------      ------------
%
% Solved in 
%
go12 =>
  Init = $[on(a,b), on(b,c), on(c,table),
           on(d,e), on(e,f), on(f,table),
           on(g,h), on(h,i), on(i,table),
           on(k,l), on(l,m),on(m,table),
           on(o,p), on(p,q),on(q,table),
           clear(a),clear(d),clear(g),clear(k),clear(o), clear(table)],
  Final =$[on(a,p), on(p,q), on(q,table),
           on(d,b), on(b,c), on(c,table),
           on(g,e), on(e,f), on(f,table),
           on(k,h), on(h,i),on(i,table),
           on(o,k), on(k,m),on(m,table) 
           , clear(a),clear(d),clear(g),clear(k), clear(o),clear(table)
           ],
  cl_facts($[final2(Final)],$[final2(-)]),
  gps_best_plan(Init), % 
  % gps_plan(Init,30), % 
  % gps_plan(Init,900), % 
  % gps_plan(Init,100), % 
  % gps_best_plan(Init,70), % 
  % gps_best_plan(Init,70), %
  % gps_best_plan(Init,27*4), 
  nl.



%
% ensure that all goals in final2/1 are in the list L.
% Note: If using gps_best_plan* then this might be
%       activated a couple of times, for each solution.
%
final(L) =>
  final2(Final2),
  pre(L,Final2),
  % final_check(L, Final2),
  writeln(final=L),
  print_world(L).


%
% Prints the block world
%
print_world(L) =>
  println("\nWorld:"),
  On = [E : E in L, E=$on(_X,_Y)],
  foreach(X in [X : E in L, E=$on(X,table)])
    printf("table %w ", X),
    while (member($on(T,X),On))
      printf("%w ", T),
      X := T
    end,
    nl
  end,
  nl.


% table


action(From,To,Move,Cost),
  pre(From,$[clear(X),clear(Z),on(X,Y)]) ?=> 
  X != table, X != Y, X != Z, Y != Z,
  To = From.del($[clear(Z),on(X,Y)]).add($[clear(Y),on(X,Z)]),
  check_resource_bound(To),
  Move = [move,X,from,Y,to,Z],
  Cost = 1.

check_resource_bound(L) =>
    Dist = dist(L),
    % println([current_resource=current_resource(), dist=Dist]),
    current_resource() > Dist.


dist(L) = Dist =>
  final2(Final),
  % Dist = L.length*([1 : E in Final, E = $on(_X,_Y)].length - sum([1 : E in L, E = $on(_X,_Y), member(E,Final)])).
  % Dist = 1*(Final.length - sum([1 : E in L, E = $on(_X,_Y), member(E,Final)])). 
  % Dist = 3.42*(Final.length - sum([1 : E in L, E = $on(_X,_Y), member(E,Final)])). % better!
  % Note: by making the constant larger, e.g. 13.42, then a solution will come quicker but with (much) longer path.
  Dist = 3.42*(Final.length - sum([1 : E in L, member(E,Final)])).
  % Dist = (Final.length - sum([1 : E in L, member(E,Final)])).
  % Dist = 4.0*sum([1 : E in L, not member(E,Final)]).