/* 

  Longest common subsequence in Picat.
 
  Ported from the B-Prolog program
  http://www.probp.com/examples/tabling/lcs.pl
  """
  Taken from "Simplifying Dynamic Programming via Mode-directed Tabling"
  Software Practice and Experience, 38(1): 75-94, 2008, by Hai-Feng Guo, Gopal Gupta
  """

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

*/


% import util.
% import cp.


main => go.


go =>
   statistics(_, _),
   lcs([50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       7, 3, 60, 38, 20, 39, 83, 92, 30, 19,
       6, 20, 20, 30, 9, 30, 20, 20, 30, 9, 
       30, 20, 500, 20, 40, 4, 92, 30, 92, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
       30, 20, 500, 20, 40, 4, 92, 30, 92, 20,
      50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30], 
     [ 7, 20, 25, 30, 9, 35, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 405, 30, 35, 20, 10, 5, 30, 20,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 405, 30, 35, 20, 10, 5, 30, 20,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      30, 8, 3, 5, 9, 200, 10, 400, 20, 30,
      50, 10, 403, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 37, 20, 500, 20, 40,
     50, 10, 400, 30, 30, 20, 10, 5, 30, 20,
       6, 20, 20, 30, 9, 39, 20, 500, 20, 40,
       6, 20, 20, 30, 19, 30, 20, 500, 20, 40,
      30, 8, 3, 5, 9, 210, 10, 400, 22, 30
     ],  V),
   statistics(_, [_, B]),
   print('The length of the longest common subsequence is '), print(V), nl,
   print('execution time = '), print(B), print(' ms'), nl.


table (+,+,max)
lcs(L1, L2, N) ?=> N=0,emptyOr(L1, L2).
lcs(FL1, FL2, N) ?=>
   FL1 = [F|L1],
   FL2 = [F|L2],
   lcs(L1, L2, N1),
   N = N1 + 1.
lcs(F1L1, F2L2, N) ?=>
   F1L1 = [F1|L1],
   F2L2 = [F2|L2],
   F1 != F2,
   lcs(L1, [F2|L2], N).
lcs(F1L1, F2L2, N) =>
   F1L1 = [F1|L1],
   F2L2 = [F2|L2],
   F1 =\= F2,
   lcs([F1|L1], L2, N).

emptyOr([], _) ?=> true.
emptyOr(_, []) => true.