/* 

  ATM puzzle in Picat.

  From 
  Muhammad Zain Sarwar: Solve this Impossible Interview Puzzle of ATM -
  How Much Money Can You Really Withdraw?
  https://medium.com/puzzle-sphere/solve-this-impossible-atm-puzzle-9c30b7708dfa
  """
  Imagine you need cash urgently. Unfortunately, your only option is a peculiar ATM that 
  seems to have a mind of its own. The ATM has just two operations:

  - It allows withdrawals of exactly $300.
  - It permits deposits of exactly $198.

  You check your bank account and see it has only $500 in total. Your goal is to withdraw 
  as much cash as possible. 

  ....

  Solution
  Find the maximum amount you can extract:

  - Since both $300 and $198 are multiples of 6, then your balance will always remain a multiple of 6.
  - The largest multiple of 6 that is less than $500 is $498.
  - This means you can extract at most $500–498 = $2 in remaining balance.

  """

  Solution of this model: z = 498 (i.e. $2 left at the ATM).

  n = 84
  z = 498
  x = [0,2,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,2]
  y = [500,302,104,404,206,8,308,110,410,212,14,314,116,416,218,20,320,122,422,224,26,326,128,428,230,32,332,134,434,236,38,338,140,440,242,44,344,146,446,248,50,350,152,452,254,56,356,158,458,260,62,362,164,464,266,68,368,170,470,272,74,374,176,476,278,80,380,182,482,284,86,386,188,488,290,92,392,194,494,296,98,398,200,2]


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

*/

import cp.
import util.
import planner.

main => go.

/*
  Here we check the best length of operations.
*/
go ?=>
  nolog,
  Map = get_global_map(),
  Map.put(z,0),
  member(N,2..100),
  % Operations:
  % 0: Do noting 1: withdraw £300, 2. deposit $198
  X = new_list(N),  
  X :: 0..2, 

  % The ATM: What is left of the account at time T?
  Y = new_list(N),
  Y :: 0..500,

  % Initial 
  Y[1] #= 500, % There are $500 at the acount
  X[1] #= 0,   % Dummy op for time T=1
  foreach(T in 2..N)
   X[T] #> 0,
   X[T] #= 0 #<=> Y[T] #= Y[T-1],
   X[T] #= 1 #<=> Y[T] #= Y[T-1]+300, % Withdraw
   X[T] #= 2 #<=> Y[T] #= Y[T-1]-198, % Deposit
  end,
  Z #= 500-Y[N], % What's the total I've withdrawn
  Vars = X ++ Y,
  solve($[max(Z),ff,split],Vars),
  if Z > Map.get(z) then
    Map.put(z,Z),
    Map.put(x,X),
    Map.put(y,Y),
    Map.put(n,N),
    println(n=N),
    println(z=Z),
    println(x=X),
    println(y=Y),    
    nl,
  end,
  fail,
  nl.
go => true.


/*
  Here's another approach using a fixed list of 100:
  - M: Time of the best value
  - Z: The value at Y[M]
  - The only action after M is X[T] = 0, i.e. no op.

  Here we also print the individual operations.

  z = 2 = 498
  x = [0,2,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  y = [500,302,104,404,206,8,308,110,410,212,14,314,116,416,218,20,320,122,422,224,26,326,128,428,230,32,332,134,434,236,38,338,140,440,242,44,344,146,446,248,50,350,152,452,254,56,356,158,458,260,62,362,164,464,266,68,368,170,470,272,74,374,176,476,278,80,380,182,482,284,86,386,188,488,290,92,392,194,494,296,98,398,200,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
  m = 84
  [t = 1,o = 0,a = na,atm = 500,my_pocket = 0]
  [t = 2,o = 2,a = 198,atm = 302,my_pocket = 198]
  [t = 3,o = 2,a = 198,atm = 104,my_pocket = 396]
  [t = 4,o = 1,a = -300,atm = 404,my_pocket = 96]
  [t = 5,o = 2,a = 198,atm = 206,my_pocket = 294]
  [t = 6,o = 2,a = 198,atm = 8,my_pocket = 492]
  [t = 7,o = 1,a = -300,atm = 308,my_pocket = 192]
  [t = 8,o = 2,a = 198,atm = 110,my_pocket = 390]
  [t = 9,o = 1,a = -300,atm = 410,my_pocket = 90]
  [t = 10,o = 2,a = 198,atm = 212,my_pocket = 288]
  [t = 11,o = 2,a = 198,atm = 14,my_pocket = 486]
  [t = 12,o = 1,a = -300,atm = 314,my_pocket = 186]
  [t = 13,o = 2,a = 198,atm = 116,my_pocket = 384]
  [t = 14,o = 1,a = -300,atm = 416,my_pocket = 84]
  [t = 15,o = 2,a = 198,atm = 218,my_pocket = 282]
  [t = 16,o = 2,a = 198,atm = 20,my_pocket = 480]
  [t = 17,o = 1,a = -300,atm = 320,my_pocket = 180]
  [t = 18,o = 2,a = 198,atm = 122,my_pocket = 378]
  [t = 19,o = 1,a = -300,atm = 422,my_pocket = 78]
  [t = 20,o = 2,a = 198,atm = 224,my_pocket = 276]
  [t = 21,o = 2,a = 198,atm = 26,my_pocket = 474]
  [t = 22,o = 1,a = -300,atm = 326,my_pocket = 174]
  [t = 23,o = 2,a = 198,atm = 128,my_pocket = 372]
  [t = 24,o = 1,a = -300,atm = 428,my_pocket = 72]
  [t = 25,o = 2,a = 198,atm = 230,my_pocket = 270]
  [t = 26,o = 2,a = 198,atm = 32,my_pocket = 468]
  [t = 27,o = 1,a = -300,atm = 332,my_pocket = 168]
  [t = 28,o = 2,a = 198,atm = 134,my_pocket = 366]
  [t = 29,o = 1,a = -300,atm = 434,my_pocket = 66]
  [t = 30,o = 2,a = 198,atm = 236,my_pocket = 264]
  [t = 31,o = 2,a = 198,atm = 38,my_pocket = 462]
  [t = 32,o = 1,a = -300,atm = 338,my_pocket = 162]
  [t = 33,o = 2,a = 198,atm = 140,my_pocket = 360]
  [t = 34,o = 1,a = -300,atm = 440,my_pocket = 60]
  [t = 35,o = 2,a = 198,atm = 242,my_pocket = 258]
  [t = 36,o = 2,a = 198,atm = 44,my_pocket = 456]
  [t = 37,o = 1,a = -300,atm = 344,my_pocket = 156]
  [t = 38,o = 2,a = 198,atm = 146,my_pocket = 354]
  [t = 39,o = 1,a = -300,atm = 446,my_pocket = 54]
  [t = 40,o = 2,a = 198,atm = 248,my_pocket = 252]
  [t = 41,o = 2,a = 198,atm = 50,my_pocket = 450]
  [t = 42,o = 1,a = -300,atm = 350,my_pocket = 150]
  [t = 43,o = 2,a = 198,atm = 152,my_pocket = 348]
  [t = 44,o = 1,a = -300,atm = 452,my_pocket = 48]
  [t = 45,o = 2,a = 198,atm = 254,my_pocket = 246]
  [t = 46,o = 2,a = 198,atm = 56,my_pocket = 444]
  [t = 47,o = 1,a = -300,atm = 356,my_pocket = 144]
  [t = 48,o = 2,a = 198,atm = 158,my_pocket = 342]
  [t = 49,o = 1,a = -300,atm = 458,my_pocket = 42]
  [t = 50,o = 2,a = 198,atm = 260,my_pocket = 240]
  [t = 51,o = 2,a = 198,atm = 62,my_pocket = 438]
  [t = 52,o = 1,a = -300,atm = 362,my_pocket = 138]
  [t = 53,o = 2,a = 198,atm = 164,my_pocket = 336]
  [t = 54,o = 1,a = -300,atm = 464,my_pocket = 36]
  [t = 55,o = 2,a = 198,atm = 266,my_pocket = 234]
  [t = 56,o = 2,a = 198,atm = 68,my_pocket = 432]
  [t = 57,o = 1,a = -300,atm = 368,my_pocket = 132]
  [t = 58,o = 2,a = 198,atm = 170,my_pocket = 330]
  [t = 59,o = 1,a = -300,atm = 470,my_pocket = 30]
  [t = 60,o = 2,a = 198,atm = 272,my_pocket = 228]
  [t = 61,o = 2,a = 198,atm = 74,my_pocket = 426]
  [t = 62,o = 1,a = -300,atm = 374,my_pocket = 126]
  [t = 63,o = 2,a = 198,atm = 176,my_pocket = 324]
  [t = 64,o = 1,a = -300,atm = 476,my_pocket = 24]
  [t = 65,o = 2,a = 198,atm = 278,my_pocket = 222]
  [t = 66,o = 2,a = 198,atm = 80,my_pocket = 420]
  [t = 67,o = 1,a = -300,atm = 380,my_pocket = 120]
  [t = 68,o = 2,a = 198,atm = 182,my_pocket = 318]
  [t = 69,o = 1,a = -300,atm = 482,my_pocket = 18]
  [t = 70,o = 2,a = 198,atm = 284,my_pocket = 216]
  [t = 71,o = 2,a = 198,atm = 86,my_pocket = 414]
  [t = 72,o = 1,a = -300,atm = 386,my_pocket = 114]
  [t = 73,o = 2,a = 198,atm = 188,my_pocket = 312]
  [t = 74,o = 1,a = -300,atm = 488,my_pocket = 12]
  [t = 75,o = 2,a = 198,atm = 290,my_pocket = 210]
  [t = 76,o = 2,a = 198,atm = 92,my_pocket = 408]
  [t = 77,o = 1,a = -300,atm = 392,my_pocket = 108]
  [t = 78,o = 2,a = 198,atm = 194,my_pocket = 306]
  [t = 79,o = 1,a = -300,atm = 494,my_pocket = 6]
  [t = 80,o = 2,a = 198,atm = 296,my_pocket = 204]
  [t = 81,o = 2,a = 198,atm = 98,my_pocket = 402]
  [t = 82,o = 1,a = -300,atm = 398,my_pocket = 102]
  [t = 83,o = 2,a = 198,atm = 200,my_pocket = 300]
  [t = 84,o = 2,a = 198,atm = 2,my_pocket = 498]


*/
go2 ?=>
  nolog,
  N = 100,
  X = new_list(N),  
  X :: 0..2, % 0: Do noting 1: withdraw £300, 2. deposit $198

  % What is left of the account?
  Y = new_list(N),
  Y :: 0..500,

  % Time of the best (smallest) value at the ATM (i.e. Y)
  M :: 2..N,

  Y[1] #= 500,
  X[1] #= 0,  
  foreach(T in 2..N)
   % If we reached M then we only got no ops (X[T] = 0)
   T #> M #<=> (Y[T] #= Y[T-1] #/\ X[T] #= 0),
   X[T] #= 0 #<=> Y[T] #= Y[T-1],
   X[T] #= 1 #<=> Y[T] #= Y[T-1]+300, % Withdraw
   X[T] #= 2 #<=> Y[T] #= Y[T-1]-198, % Deposit
  end,
  % Get the value of Z at time M: Z = Y[M]
  element(M,Y,Z),
  
  Vars = X ++ Y ++ [M],
  solve($[min(Z),ff,split],Vars),
  
  println(z=Z=(500-Z)),
  println(x=X),
  println(y=Y),
  println(m=M),
  % The individual exchanges
  foreach(T in 1..M)
    O = X[T],
    if T == 1 then
      A = na
    else
      A = cond(X[T] == 1, -300, +198)
    end,
    println([t=T,o=O,a=A,atm=Y[T],my_pocket=(500-Y[T])])
  end,
  nl,
  fail,
  nl.
go2 => true.