/* 

  Longest Valid Parentheses in Picat.

  From https://codegolf.stackexchange.com/questions/258511/longest-valid-parentheses
  """
  Longest Valid Parentheses

  Given a string of parentheses ( and ), find the length of the longest substring that 
  forms a valid pair of parentheses.

  Valid pairs of parentheses are defined as the following:

  An empty string is a valid pair of parentheses. If s is a valid pair of parentheses, then (s) 
  is also a valid pair of parentheses. If s and t are both valid pairs of parentheses, then 
  st is also a valid pair of parentheses. For example, the longest valid 
  substring of (()()) is (()()), with length 6.

  Write a function or program that takes a string of parentheses as input and outputs the 
  length of the longest valid substring.

  Example:

  Input: (()()) Output: 6
  Input: )()()) Output: 4
  Input: ()(()) Output: 6
  Input: ()(() Output: 2
  Input: )) Output: 0
  Input:   Output: 0

  Code golf rules:

  Write a function or program that takes a string of parentheses as input and outputs the 
  length of the longest valid substring, using as few characters as possible.

  The score of your solution will be the number of characters in your code. The solution 
  with the shortest code wins. In case of ties, the earlier submission wins.

  You can assume the input string contains only the characters ( and ).
  """

  Solution:
  (()()) = 6
  )()()) = 4
  ()(()) = 6
  ()(() = 2
  )) = 0
  [] = 0


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

*/

import planner.

main => go.
go ?=>
  TT = ["(()())",
        ")()())",
        "()(())",
        "()(()",
        "))",
        ""],
  foreach(T in TT)
    println(T=t(T))
  end.
% 110 chars
b-->"". b-->"(",b,")",b.
t(S)=L=>N=S.len,B=[(J-I+1):I in 1..N,J in I..N,b(S[I..J],[])],L=cond(B=="",0,B.max).

/*
go ?=>
  TT = ["(()())",
        ")()())",
        "()(())",
        "()(()",
        "))",
        ""],
  foreach(T in TT)
    println(T=t(T))
  end
.
  t(S) = L =>
    N = S.len,
    % Brute force: Testing all ranges
    B = [(J-I+1) : I in 1..N, 
                   J in I..N,
                   b(S[I..J],[])
        ],
    L = cond(B == "", 0, B.max).

% DCG: ensure balanced brackets
b --> "". 
b --> "(", b, ")" ,b.

*/