/*

   Longest common subsequence in Picat.

  From http://rosettacode.org/wiki/Longest_common_subsequence
  """
  The longest common subsequence (or LCS) of groups A and B is the 
  longest group of elements from A and B that are common between the 
  two groups and in the same order in each group. For example, the 
  sequences "1234" and "1224533324" have an LCS of "1234":

  1234
  1224533324

  For a string example, consider the sequences "thisisatest" and 
  "testing123testing". An LCS would be "tsitest":

  thisisatest
  testing123testing

  In this puzzle, your code only needs to deal with strings. Write a 
  function which returns an LCS of two strings (case-sensitive). 
  You don't need to show multiple LCS's. 
  """


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

*/

main => go.

go => 
   println("lcs():"),
   time(println(lcs("thisisatest","testing123testing"))),
   time(println(lcs("XMJYAUZ", "MZJAWXU"))),
   time(println(lcs("1234", "1224533324"))),

   println("lcs2():"),
   time(println(lcs2("thisisatest","testing123testing"))),
   time(println(lcs2("XMJYAUZ", "MZJAWXU"))),
   time(println(lcs2("1234", "1224533324"))),

   println("lcs3():"),
   time(println(lcs3("thisisatest","testing123testing"))),
   time(println(lcs3("XMJYAUZ", "MZJAWXU"))),
   time(println(lcs3("1234", "1224533324"))),

   println("lcs4():"),
   time(println(lcs4("thisisatest","testing123testing"))),
   time(println(lcs4("XMJYAUZ", "MZJAWXU"))),
   time(println(lcs4("1234", "1224533324"))),


   nl.


lcs(X,Y) = V => 
  [C, _Len] = lcs_length(X,Y),
  V = backTrace(C,X,Y,X.length+1,Y.length+1).


% From 
% http:%en.wikipedia.org/wiki/Longest_common_subsequence
% with added trickery for a 1-based language.
%
lcs_length(X, Y) = V=>
  M = X.length, 
  N = Y.length,
  C = [[0 : J in 1..N+1]  : I in 1..N+1],
  foreach(I in 2..M+1,J in 2..N+1)
     if X[I-1] == Y[J-1] then
        C[I,J] := C[I-1,J-1] + 1
     else
        C[I,J] := max([C[I,J-1], C[I-1,J]])
     end
  end,
  V = [C, C[M+1,N+1]].

% table
backTrace(C, X, Y, I, J) = V =>
  if I == 1; J == 1 then
    V := ""
  elseif X[I-1] == Y[J-1] then
    V := backTrace(C, X, Y, I-1, J-1) ++ [X[I-1]]
  else 
    if C[I,J-1] > C[I-1,J] then
      V := backTrace(C, X, Y, I, J-1)
    else 
      V := backTrace(C, X, Y, I-1, J)
    end
  end.


% From the ADA solution
% Using table speed it up considerably.
table
lcs2(A,B) = V =>
  ALen = A.length,
  BLen = B.length,
  A1 = [A[I] : I in 1..ALen-1],
  B1 = [B[I] : I in 1..BLen-1],
  if A == ""; B == "" then 
     V := ""
  elseif A[ALen] == B[BLen] then
     V := lcs2(A1, B1) ++ [A[ALen]]
  else 
     X = lcs2(A, B1),
     Y = lcs2(A1, B),
     if X.length > Y.length then
        V := X
     else 
        V := Y
     end
  end.


%
% Inspired by the SETL version
% http:%rosettacode.org/wiki/Longest_common_subsequence#SETL 
%
longest(A, B) = V =>
    V := cond(A.length > B.length, A, B).

% without table lcs3/2 is faster than lcs2/2 without table, 
% but slower than lcs/2. 
table
lcs3(A, B) = V =>
  if A == ""; B == "" then
    V := ""
  elseif A[1] == B[1] then
    V := [A[1]] ++ lcs3(butfirst(A), butfirst(B))
  else 
    V := longest(lcs3(butfirst(A), B), lcs3(A, butfirst(B)))
  end.

% but first
butfirst(A) = [A[I] : I in 2..A.length].


% Rule based version of lcs3/2 (as a proof-of-concept).
% Note: using table don't work for some reason 
%       (and is therefore slower than lcs3/2)
table
lcs4(A, B) = "", (A == ""; B == "") => true.
lcs4(A, B) = [A[1]] ++ lcs4(butfirst(A), butfirst(B)), A[1] == B[1] => true.
lcs4(A, B) = longest(lcs4(butfirst(A), B), lcs4(A, butfirst(B))) => true.