/*

  1D Rubik's Cube in Picat.

  From
  http://www.mail-archive.com/programming@jsoftware.com/msg05817.html
  """
  1D Rubik's Cube

  Oleg Kobchenko
  Mon, 11 Jun 2007 19:09:55 -0700

  I found an interesting game, as found on Andrew Nikitin's 
  MSX-BASIC page http://nsg.upor.net/msx/basic/basic.htm ,
  and I am not sure if its solver has been given as a puzzle.
  Here it goes.

  1D Rubik's Cube is a line of 6 numbers with
  original position:

    1 2 3 4 5 6

  which can be rotated in 3 different ways
  in groups of four:
      _______                _______
     (1 2 3 4)5 6  --(0)->  (4 3 2 1)5 6
        _______                _______
      1(2 3 4 5)6  --(1)->   1(5 4 3 2)6
          _______                _______
      1 2(3 4 5 6) --(2)->   1 2(6 5 4 3)

  Given a scrambled line, return the shortest sequence of 
  rotations to restore the original position.

  Examples:

     solve 1 3 2 6 5 4
  1 2 1
     solve 5 6 2 1 4 3
  0 2
     solve 6 5 4 1 2 3
  0 1 2

  """


  This version use the built-in module planner.

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

*/

import planner,cp.

main => go.

go =>
   initial_state(Init),
   time(best_plan(Init, L)),
   println(moves=L), 
   Len=length(L),
   println(len=Len),
   nl.

% increasing the allowed length
go2 =>
   initial_state(Init),
   foreach(Len in 1..25)
      nl,
      println(len=Len),
      (time(best_plan(Init,Len,L)) ; true),
      println(moves=L),
      nl
   end.

% same as go2/0 using indomain/1
go3 =>
   initial_state(Init),
   nolog,
   Len :: 1..25,
   indomain(Len),
   println(len=Len),
   time(best_plan(Init,Len,L)),
   println(moves=L),
   nl.

% random instance
go4 =>
   N = 12,
   NumMoves = 20,
   generate_moves(N,NumMoves,Init,Moves),
   println(init=Init),
   println(generatedMoves=Moves),
   time(best_plan(Init,NumMoves,L)),
   println(moves=L),
   println(len=L.len),
   nl.

generate_moves(N,NumMoves, Init, Moves) =>
   Init1 = 1..N,
   Moves1 = [],
   _ = random2(),
   foreach(I in 1..NumMoves)
     Move = 1 + random() mod 9, % There are 9 moves for the 1..12 puzzle
     Moves1 := Moves1 ++ [Move],
     action(Init1,Init2,Move,_Cost),
     Init1 := Init2
   end, 
   Init = Init1,
   Moves = Moves1.



%
% Length 6 (original problem)
%
% index(-)
% % initial_state([1,3,2,6,5,4]). % Moves: 2,3,2
% % initial_state([5,6,2,1,4,3]). % Moves: 1,3
% % initial_state([6,5,4,1,2,3]). % Moves: 1,2,3
% % initial_state([2,1,5,4,3,6]). % Moves: 1,2,1
% % initial_state([5,1,2,3,4,6]). % Moves: 1,2,1,2
% % initial_state([5,4,3,2,1,6]). % Moves: 1,2,1,2,1
% %% These two takes 11 steps (no problem at all).
% % initial_state([6,3,5,2,4,1]).   % GAP: x3*x1*x2*x1*x3*x2*x1*x2*x1*x3*x1
% % initial_state([6,4,2,5,3,1]).   % GAP: x1*x3*x2*x3*x2*x1*x3*x2*x3*x2*x1
% % initial_state([6,5,4,3,1,2]). % moves 1,3,2,1,3,1,2,1
% % initial_state([6,3,4,5,2,1]). % 1,3,2,1,3

% index(-)
% final([1,2,3,4,5,6]).

% table
% % action(From, Move, To).
% action([M4,M3,M2,M1,M5,M6],To,M,Cost) ?=> Cost=1, M=1, To=[M1,M2,M3,M4,M5,M6]. % move 1
% action([M1,M5,M4,M3,M2,M6],To,M,Cost) ?=> Cost=1, M=2, To=[M1,M2,M3,M4,M5,M6]. % move 2
% action([M1,M2,M6,M5,M4,M3],To,M,Cost)  => Cost=1, M=3, To=[M1,M2,M3,M4,M5,M6]. % move 3

%
% Length 8
%

% index(-)
% initial_state([2,4,1,7,5,3,8,6]). % GAP: x2*x3*x2*x4*x3*x5*x4*x1*x2*x1
% % initial_state([8,7,6,3,2,5,4,1]).  % GAP: x3*x1*x2*x3*x1*x4*x5*x1*x3*x1

% index(-)
% final([1,2,3,4,5,6,7,8]).

% table
% action([M4,M3,M2,M1,M5,M6,M7,M8],To,M,Cost) ?=> Cost=1,M=1,To=[M1,M2,M3,M4,M5,M6,M7,M8]. % move 1
% action([M1,M5,M4,M3,M2,M6,M7,M8],To,M,Cost) ?=> Cost=1,M=2,To=[M1,M2,M3,M4,M5,M6,M7,M8]. % move 2
% action([M1,M2,M6,M5,M4,M3,M7,M8],To,M,Cost) ?=> Cost=1,M=3,To=[M1,M2,M3,M4,M5,M6,M7,M8]. % move 3
% action([M1,M2,M3,M7,M6,M5,M4,M8],To,M,Cost) ?=> Cost=1,M=4,To=[M1,M2,M3,M4,M5,M6,M7,M8]. % move 4
% action([M1,M2,M3,M4,M8,M7,M6,M5],To,M,Cost)  => Cost=1,M=5,To=[M1,M2,M3,M4,M5,M6,M7,M8]. % move 5


%
% Length 12
%
% Using current_resouce and heuristics works and solves the two test problems in 0.3s
%

% table
action([M4,M3,M2,M1,M5,M6,M7,M8,M9,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=1,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 1
action([M1,M5,M4,M3,M2,M6,M7,M8,M9,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=2,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 2
action([M1,M2,M6,M5,M4,M3,M7,M8,M9,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=3,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 3
action([M1,M2,M3,M7,M6,M5,M4,M8,M9,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=4,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 4
action([M1,M2,M3,M4,M8,M7,M6,M5,M9,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=5,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 5
action([M1,M2,M3,M4,M5,M9,M8,M7,M6,M10,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=6,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 6
action([M1,M2,M3,M4,M5,M6,M10,M9,M8,M7,M11,M12],To,M,Cost) ?=> 
       Cost=1,M=7,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 7
action([M1,M2,M3,M4,M5,M6,M7,M11,M10,M9,M8,M12],To,M,Cost) ?=> 
       Cost=1,M=8,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 8
action([M1,M2,M3,M4,M5,M6,M7,M8,M12,M11,M10,M9],To,M,Cost)  => 
       Cost=1,M=9,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12], check_resource_bound(To). % move 9

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

dist(L) = sum([1 : I in 1..L.length, L[I] != I]). % simple heuristisc
% dist(L) = sum([abs(I-L[I]) : I in 1..L.length]).

%% number of moves: 12
index(-)
initial_state([7,5,11,8,9,1,10,3,4,2,6,12]).
%% number of moves: 12
% initial_state([12,2,7,3,4,11,1,10,8,9,6,5]).

index(-)
final(1..12).