/* 

  Can the Robot reach the Target? in Picat.

  From https://medium.com/puzzle-sphere/can-the-robot-reach-the-target-2674fba3d73f
  """  
  A robot is at (0, 0) on a grid. A target is at (36, 25). The robot is 
  only programmed to make two moves. It can move one step to the left and two 
  steps up or it can move two steps to the left and one step up.

  Can the robot reach the target? If not, how close can it get?
  """

  Note: It should be "one [two] step(s) to the _right_", not to the left.

  No, it cannot reach the target.

  See below for more experiments on this problem.

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

*/

import planner.
import cp.

main => go.

/*

  Note: We assume that the number of steps are <= 100.
  Here's the output.

  target = [36,25]
  [36,25] = not_possible
  % Searching with the bound 0
  % Searching with the bound 1
  ...
  % Searching with the bound 99
  % Searching with the bound 100
  No plan!

  

*/
go ?=>
  % nolog,
  Start = [0,0],
  Target = [36,25],
  println(target=Target),

  if is_possible(Target[1],Target[2],Len) then
    println(Target=possible=Len)
  else
    println(Target=not_possible)
  end,

  cl_facts($[final(Target)]),
  
  if best_plan(Start,100,Plan,Cost) then
    println(Plan),
    foreach(P in Plan)
      println(P)
    end,
    println(Target=Cost)
  else
    println("No plan!")
  end,
  nl.
go => true.

/*
  Plan and the number of steps for the solvable problem (0,0) -> (1..20,1..20)

  [1,2] = [[1,2]] = 1
  [2,1] = [[2,1]] = 1
  [2,4] = [[1,2],[2,4]] = 2
  [3,3] = [[1,2],[3,3]] = 2
  [3,6] = [[1,2],[2,4],[3,6]] = 3
  [4,2] = [[2,1],[4,2]] = 2
  [4,5] = [[1,2],[2,4],[4,5]] = 3
  [4,8] = [[1,2],[2,4],[3,6],[4,8]] = 4
  [5,4] = [[1,2],[3,3],[5,4]] = 3
  [5,7] = [[1,2],[2,4],[3,6],[5,7]] = 4
  [5,10] = [[1,2],[2,4],[3,6],[4,8],[5,10]] = 5
  [6,3] = [[2,1],[4,2],[6,3]] = 3
  [6,6] = [[1,2],[2,4],[4,5],[6,6]] = 4
  [6,9] = [[1,2],[2,4],[3,6],[4,8],[6,9]] = 5
  [6,12] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12]] = 6
  [7,5] = [[1,2],[3,3],[5,4],[7,5]] = 4
  [7,8] = [[1,2],[2,4],[3,6],[5,7],[7,8]] = 5
  [7,11] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11]] = 6
  [7,14] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14]] = 7
  [8,4] = [[2,1],[4,2],[6,3],[8,4]] = 4
  [8,7] = [[1,2],[2,4],[4,5],[6,6],[8,7]] = 5
  [8,10] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10]] = 6
  [8,13] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13]] = 7
  [8,16] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16]] = 8
  [9,6] = [[1,2],[3,3],[5,4],[7,5],[9,6]] = 5
  [9,9] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9]] = 6
  [9,12] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12]] = 7
  [9,15] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15]] = 8
  [9,18] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[9,18]] = 9
  [10,5] = [[2,1],[4,2],[6,3],[8,4],[10,5]] = 5
  [10,8] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8]] = 6
  [10,11] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11]] = 7
  [10,14] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14]] = 8
  [10,17] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[10,17]] = 9
  [10,20] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[9,18],[10,20]] = 10
  [11,7] = [[1,2],[3,3],[5,4],[7,5],[9,6],[11,7]] = 6
  [11,10] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9],[11,10]] = 7
  [11,13] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12],[11,13]] = 8
  [11,16] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15],[11,16]] = 9
  [11,19] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[9,18],[11,19]] = 10
  [12,6] = [[2,1],[4,2],[6,3],[8,4],[10,5],[12,6]] = 6
  [12,9] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8],[12,9]] = 7
  [12,12] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11],[12,12]] = 8
  [12,15] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14],[12,15]] = 9
  [12,18] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[10,17],[12,18]] = 10
  [13,8] = [[1,2],[3,3],[5,4],[7,5],[9,6],[11,7],[13,8]] = 7
  [13,11] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9],[11,10],[13,11]] = 8
  [13,14] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12],[11,13],[13,14]] = 9
  [13,17] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15],[11,16],[13,17]] = 10
  [13,20] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[9,18],[11,19],[13,20]] = 11
  [14,7] = [[2,1],[4,2],[6,3],[8,4],[10,5],[12,6],[14,7]] = 7
  [14,10] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8],[12,9],[14,10]] = 8
  [14,13] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11],[12,12],[14,13]] = 9
  [14,16] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14],[12,15],[14,16]] = 10
  [14,19] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[10,17],[12,18],[14,19]] = 11
  [15,9] = [[1,2],[3,3],[5,4],[7,5],[9,6],[11,7],[13,8],[15,9]] = 8
  [15,12] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9],[11,10],[13,11],[15,12]] = 9
  [15,15] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12],[11,13],[13,14],[15,15]] = 10
  [15,18] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15],[11,16],[13,17],[15,18]] = 11
  [16,8] = [[2,1],[4,2],[6,3],[8,4],[10,5],[12,6],[14,7],[16,8]] = 8
  [16,11] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8],[12,9],[14,10],[16,11]] = 9
  [16,14] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11],[12,12],[14,13],[16,14]] = 10
  [16,17] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14],[12,15],[14,16],[16,17]] = 11
  [16,20] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[8,16],[10,17],[12,18],[14,19],[16,20]] = 12
  [17,10] = [[1,2],[3,3],[5,4],[7,5],[9,6],[11,7],[13,8],[15,9],[17,10]] = 9
  [17,13] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9],[11,10],[13,11],[15,12],[17,13]] = 10
  [17,16] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12],[11,13],[13,14],[15,15],[17,16]] = 11
  [17,19] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15],[11,16],[13,17],[15,18],[17,19]] = 12
  [18,9] = [[2,1],[4,2],[6,3],[8,4],[10,5],[12,6],[14,7],[16,8],[18,9]] = 9
  [18,12] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8],[12,9],[14,10],[16,11],[18,12]] = 10
  [18,15] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11],[12,12],[14,13],[16,14],[18,15]] = 11
  [18,18] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14],[12,15],[14,16],[16,17],[18,18]] = 12
  [19,11] = [[1,2],[3,3],[5,4],[7,5],[9,6],[11,7],[13,8],[15,9],[17,10],[19,11]] = 10
  [19,14] = [[1,2],[2,4],[3,6],[5,7],[7,8],[9,9],[11,10],[13,11],[15,12],[17,13],[19,14]] = 11
  [19,17] = [[1,2],[2,4],[3,6],[4,8],[5,10],[7,11],[9,12],[11,13],[13,14],[15,15],[17,16],[19,17]] = 12
  [19,20] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[7,14],[9,15],[11,16],[13,17],[15,18],[17,19],[19,20]] = 13
  [20,10] = [[2,1],[4,2],[6,3],[8,4],[10,5],[12,6],[14,7],[16,8],[18,9],[20,10]] = 10
  [20,13] = [[1,2],[2,4],[4,5],[6,6],[8,7],[10,8],[12,9],[14,10],[16,11],[18,12],[20,13]] = 11
  [20,16] = [[1,2],[2,4],[3,6],[4,8],[6,9],[8,10],[10,11],[12,12],[14,13],[16,14],[18,15],[20,16]] = 12
  [20,19] = [[1,2],[2,4],[3,6],[4,8],[5,10],[6,12],[8,13],[10,14],[12,15],[14,16],[16,17],[18,18],[20,19]] = 13



*/
go2 ?=>
  nolog,
  Start = [0,0],
  _ = random2(),
  % Target = [random(1,99) : _ in 1..2],
  member(Target, [[X,Y] : X in 1..20, Y in 1..20]),
  % println(target=Target),

  cl_facts($[final(Target)]),

  if is_possible(Target[1],Target[2],NumMoves) then
    println(Target=possible=NumMoves)
  end, 
  if best_plan(Start,100,Plan,Cost) then
    println(Target=Plan=Cost),
    nl
    % println(Target=Cost)
  % else
  %   println(Target=no_plan)
  end,
  % println(Plan),
  % foreach(P in Plan)
  %   println(P)
  % end,
  % println(Target=Cost),
  % nl,
  fail,
  nl.
go2 => true.


/*
  Generate an endless random and possible targets in the range (1..999,1..999) and
  solve the problems. Use the information about the length to speed things up
  using best_plan_bb which starts from the stated max length.
 
  For targets in range (1..999,1..999) the solutions are fast (< 1s),
  For target in range (1..9999,1..9999) it's much slower.

*/ 
go3 ?=>
  % nolog,
  Start = [0,0],
  _ = random2(),
  Target = false,
  PlanLen = _,
  while (Target == false)
    X = random_cp(1,999),
    Y = random_cp(1,999),
    if is_possible(X,Y,Len) then
      Target := [X,Y],
      PlanLen := Len,
      println(target=Target=Len)
    end
  end,

  cl_facts($[final(Target)]),
  
  best_plan_bb(Start,PlanLen,Plan,Cost),
  println(Plan),
  % foreach(P in Plan)
  %   println(P)
  % end,
  println(Target=Cost),
  nl,
  fail,
  nl.
go3 => true.

/* 
  What are the valid solutions?

  (This is from the Linear Algebra discussion op.cit.)

  For x in 1..20, y in 1..20, what targets (x,y) are possible?
  - a is the number of the first move
  - b is the number of the second move,
  Thus, a+b is the total number of moves.

  [x = 1,y = 2,a = 1,b = 0,ab = 1]
  [x = 2,y = 1,a = 0,b = 1,ab = 1]
  [x = 2,y = 4,a = 2,b = 0,ab = 2]
  [x = 3,y = 3,a = 1,b = 1,ab = 2]
  [x = 3,y = 6,a = 3,b = 0,ab = 3]
  [x = 4,y = 2,a = 0,b = 2,ab = 2]
  [x = 4,y = 5,a = 2,b = 1,ab = 3]
  [x = 4,y = 8,a = 4,b = 0,ab = 4]
  [x = 5,y = 4,a = 1,b = 2,ab = 3]
  [x = 5,y = 7,a = 3,b = 1,ab = 4]
  [x = 5,y = 10,a = 5,b = 0,ab = 5]
  [x = 6,y = 3,a = 0,b = 3,ab = 3]
  [x = 6,y = 6,a = 2,b = 2,ab = 4]
  [x = 6,y = 9,a = 4,b = 1,ab = 5]
  [x = 6,y = 12,a = 6,b = 0,ab = 6]
  [x = 7,y = 5,a = 1,b = 3,ab = 4]
  [x = 7,y = 8,a = 3,b = 2,ab = 5]
  [x = 7,y = 11,a = 5,b = 1,ab = 6]
  [x = 7,y = 14,a = 7,b = 0,ab = 7]
  [x = 8,y = 4,a = 0,b = 4,ab = 4]
  [x = 8,y = 7,a = 2,b = 3,ab = 5]
  [x = 8,y = 10,a = 4,b = 2,ab = 6]
  [x = 8,y = 13,a = 6,b = 1,ab = 7]
  [x = 8,y = 16,a = 8,b = 0,ab = 8]
  [x = 9,y = 6,a = 1,b = 4,ab = 5]
  [x = 9,y = 9,a = 3,b = 3,ab = 6]
  [x = 9,y = 12,a = 5,b = 2,ab = 7]
  [x = 9,y = 15,a = 7,b = 1,ab = 8]
  [x = 9,y = 18,a = 9,b = 0,ab = 9]
  [x = 10,y = 5,a = 0,b = 5,ab = 5]
  [x = 10,y = 8,a = 2,b = 4,ab = 6]
  [x = 10,y = 11,a = 4,b = 3,ab = 7]
  [x = 10,y = 14,a = 6,b = 2,ab = 8]
  [x = 10,y = 17,a = 8,b = 1,ab = 9]
  [x = 10,y = 20,a = 10,b = 0,ab = 10]
  [x = 11,y = 7,a = 1,b = 5,ab = 6]
  [x = 11,y = 10,a = 3,b = 4,ab = 7]
  [x = 11,y = 13,a = 5,b = 3,ab = 8]
  [x = 11,y = 16,a = 7,b = 2,ab = 9]
  [x = 11,y = 19,a = 9,b = 1,ab = 10]
  [x = 12,y = 6,a = 0,b = 6,ab = 6]
  [x = 12,y = 9,a = 2,b = 5,ab = 7]
  [x = 12,y = 12,a = 4,b = 4,ab = 8]
  [x = 12,y = 15,a = 6,b = 3,ab = 9]
  [x = 12,y = 18,a = 8,b = 2,ab = 10]
  [x = 13,y = 8,a = 1,b = 6,ab = 7]
  [x = 13,y = 11,a = 3,b = 5,ab = 8]
  [x = 13,y = 14,a = 5,b = 4,ab = 9]
  [x = 13,y = 17,a = 7,b = 3,ab = 10]
  [x = 13,y = 20,a = 9,b = 2,ab = 11]
  [x = 14,y = 7,a = 0,b = 7,ab = 7]
  [x = 14,y = 10,a = 2,b = 6,ab = 8]
  [x = 14,y = 13,a = 4,b = 5,ab = 9]
  [x = 14,y = 16,a = 6,b = 4,ab = 10]
  [x = 14,y = 19,a = 8,b = 3,ab = 11]
  [x = 15,y = 9,a = 1,b = 7,ab = 8]
  [x = 15,y = 12,a = 3,b = 6,ab = 9]
  [x = 15,y = 15,a = 5,b = 5,ab = 10]
  [x = 15,y = 18,a = 7,b = 4,ab = 11]
  [x = 16,y = 8,a = 0,b = 8,ab = 8]
  [x = 16,y = 11,a = 2,b = 7,ab = 9]
  [x = 16,y = 14,a = 4,b = 6,ab = 10]
  [x = 16,y = 17,a = 6,b = 5,ab = 11]
  [x = 16,y = 20,a = 8,b = 4,ab = 12]
  [x = 17,y = 10,a = 1,b = 8,ab = 9]
  [x = 17,y = 13,a = 3,b = 7,ab = 10]
  [x = 17,y = 16,a = 5,b = 6,ab = 11]
  [x = 17,y = 19,a = 7,b = 5,ab = 12]
  [x = 18,y = 9,a = 0,b = 9,ab = 9]
  [x = 18,y = 12,a = 2,b = 8,ab = 10]
  [x = 18,y = 15,a = 4,b = 7,ab = 11]
  [x = 18,y = 18,a = 6,b = 6,ab = 12]
  [x = 19,y = 11,a = 1,b = 9,ab = 10]
  [x = 19,y = 14,a = 3,b = 8,ab = 11]
  [x = 19,y = 17,a = 5,b = 7,ab = 12]
  [x = 19,y = 20,a = 7,b = 6,ab = 13]
  [x = 20,y = 10,a = 0,b = 10,ab = 10]
  [x = 20,y = 13,a = 2,b = 9,ab = 11]
  [x = 20,y = 16,a = 4,b = 8,ab = 12]
  [x = 20,y = 19,a = 6,b = 7,ab = 13]

*/
go4 ?=>
  Max = 20,
  TargetX :: 0..Max,
  TargetY :: 0..Max,

  A :: 0..Max,
  B :: 0..Max,

  A + 2*B #= TargetX #/\ 2*A + B #= TargetY,
  
  Vars = [TargetX,TargetY,A,B],
  solve(Vars),
  println([x=TargetX,y=TargetY,a=A,b=B,ab=(A+B)]),
  fail,
  nl.
go4 => true.

is_possible(X,Y,NumMoves) =>
  Max = max(X,Y),
  A :: 0..Max,
  B :: 0..Max,

  A + 2*B #= X #/\ 2*A + B #= Y,
  Vars = [A,B],
  solve($[ff,split],Vars),
  NumMoves = A+B.
  


% final(Goal) => Goal = [36,25].
% """
% The robot is only programmed to make two moves.
% It can move one step to the left and two steps up or
% it can move two steps to the left and one step up.
% """
% I assume that it should be "one/two step to the _right_", not left
action(From,To,Move,Cost) ?=>
  [X,Y] = From,
  % Valid = [[X+X2,Y+Y2] : X2 in [-2,-1,1,2],Y2 in [1,2], (abs(X2) == 1, abs(Y2) == 2 ;
  %                                                        abs(X2) == 2, abs(Y2) == 1)
  %                                                        % , X2 >= 0, Y2 >= 0
  %                                                              ],
  Valid = [ [X+1,Y+2], [X+2,Y+1]],
  member(To,Valid),
  To != From,

  Move = To,
  Cost = 1.

% A random which can be used with fail/0
random_cp(MinVal,MaxVal) = X =>
  X :: MinVal..MaxVal,
  solve($[rand],X).