/* 

  Optimal Binary Search Tree in Picat.

  From the B-Prolog program:
  http://www.probp.com/examples/tabling/obst.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(_, _),
   obst([(a, 22), (am, 18), (and, 20), (egg, 5), (if, 25), 
   (a, 2), (am, 7), (and, 20), (egg, 5), (if, 25),   
   (a, 12), (am, 8), (and, 4), (egg, 5), (if, 5),   
   (a, 22), (am, 10), (and, 20), (egg, 15), (if, 25),   
   (a, 32), (am, 20), (and, 23), (egg, 5), (if, 25),   
   (a, 42), (am, 4), (and, 20), (egg, 5), (if, 5),   
   (a, 32), (am, 18), (and, 3), (egg, 15), (if, 25),   
   (a, 23), (am, 19), (and, 20), (egg, 5), (if, 5),   
   (a, 24), (am, 9), (and, 20), (egg, 15), (if, 25),   
   (a, 21), (am, 38), (and, 20), (egg, 5), (if, 5),   
   (a, 2), (am, 8), (and, 21), (egg, 5), (if, 25),   
   (a, 16), (am, 18), (and, 20), (egg, 5), (if, 25),   
   (the, 2), (two, 8)], N, _T),
   statistics(_, [_, B]),
   printf("Optimal value is %d\n", N),
   printf("execution time = %dms.\n", B), 
   nl.


% Optimal Binary Search Tree

table(+,min,-)
obst(A, B1, B2) ?=> B1=B2, base(A, B1).
obst(FF, N, T) =>
    FF = [F1, F2 |L],
    break([F1, F2 | L], L1, L2, (_W, P)),
    obst(L1, N1, T1),
    obst(L2, N2, T2),
    T = T1 + T2 + P,
    N = T + N1 + N2.

table
base(WP,P) ?=> WP=[], P=0.
base(WP,P)  => WP=[(_W, P)].

table
break(FF, A, B, F) ?=> 
   A = [],
   B = [],
   FF = [F].
break(FF, A, FF2, F1) ?=> 
   A = [],
   FF = [F1, F2 | L],
   FF2 = [F2 | L].
break(FF, FF2, L2, F) =>
    FF = [F1, F2 | L],
    FF2 = [F1 | L1],
    break([F2 | L], L1, L2, F).