/* 

  Longest increasing subsequence (Rosetta code) in Picat.

  From http://rosettacode.org/wiki/Longest_increasing_subsequence
  """
  Calculate and show here a longest increasing subsequence of the list:

    {3,2,6,4,5,1} 

  And of the list:

    {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15} 

  Note that a list may have more than one subsequence that is of the maximum length.
  """

  Also, see:
  - http://en.wikipedia.org/wiki/Longest_increasing_subsequence
  - http://www.youtube.com/watch?v=4fQJGoeW5VE
  - http://en.wikipedia.org/wiki/Patience_sorting


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

*/

import sat. % for go3/0 and go4/0
% import cp.


main => go.

go => 
  Ss = [
        [3,2,6,4,5,1],
        [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
        [1,1,1,1],
        [4,65,2,-31,0,99,83,782,1],
        [f,o,o,b,a,r]
       ],
  foreach(S in Ss)
    lis(S,Lis,N),
    println([S,Lis,N])
  end,
  nl.

go2 =>
  % _ = random2(),
  N = 1+random() mod 100,
  println(n=N),
  S = [(random() mod 1000)-100 : _ in 1..N],
  println(s=S),
  lis(S,Lis,Len),
  println(lis=Lis),
  println(len=Len),
  nl.

%
% using cp/sat
%
go3 =>
  nolog,
  Ss = [
        [3,2,6,4,5,1],
        [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
        [1,1,1,1],
        [4,65,2,-31,0,99,83,782,1]
       ],
  foreach(S in Ss)
    lis_cp(S, X,Z),
    println([S,[S[I] : I in 1..S.len, X[I] == 1],Z])
  end,
  nl.

%
% Using cp
%
go4 =>
  nolog,
  % _ = random2(),
  N = 1+random() mod 100,
  println(n=N),
  S = [(random() mod 1000)-100 : _ in 1..N],
  println(s=S),
  lis_cp(S,X,Z),
  Selected = [S[I] : I in 1..S.len,X[I] == 1],
  println(selected=Selected),
  println(z=Z),
  nl.



% Inspired by the Prolog version
table(+,+,max)
lis(In, Out,OutLen) =>
  one_is(In, [], Is),
  Out = reverse(Is),
  OutLen = Out.length.

one_is([], Current, Current2) => Current = Current2.
one_is([H|T], Current, Final) =>
	( Current = [], one_is(T, [H], Final));
	( Current = [H1|_], H1 @< H, one_is(T, [H|Current], Final));
	one_is(T, Current, Final).


%
% Constraint modelling version
%
lis_cp(S, X,Z) =>
  Len = S.len,
  X = new_list(Len),
  X :: 0..1,

  increasing_except_0_strict($[X[I]*S[I] : I in 1..Len]),
  Z #= sum(X),

  solve($[max(Z),max,updown],X).

% 
% Ensures that array a is increasing if we disregard any 0's
% 
increasing_except_0_strict(A) =>
  increasing_except_C_strict(A,0).

increasing_except_C_strict(A,C) =>
  N = A.len,
  foreach(I in 1..N, J in I+1..N)
    (A[I] #!= C #/\ A[J] #!= C) #=> (A[I] #< A[J])
  end.