Ge contains no parentheses, and any symbol appearing in Ge is either 1, 2, or 3.
The length of Ge is equal to a given number Len.
Ge = Gea Gec Gec Gebi.e. Ge does not contain two adjacent non-empty equal subexpressions.
Gea Gec Gec
$func? IsUnacceptable e.String = ; IsUnacceptable e.String = <Div <Length e.String> 2> :: s.Max, { s.Max : 0 = $fail; = 1 $iter \{ <Lt (sK) (s.Max)> = <Add sK 1>; } :: sK, <Right 0 sK <Middle 0 sK e.String>> :: eU, <Right 0 sK e.String> :: eV, eU : eV; };
Now we can define the function Extend trying to add a digit to the expression, until the sequence has the desired length. If the expression cannot be extended, the function "backtracks", and tries to change previous digits.
$func? Extend s.Len e.String = e.String; Extend s.Len e.String = { <Length e.String> : s.Len = e.String; = 1 $iter \{ <Lt (s.Digit) (3)> = <Add s.Digit 1>; } :: s.Digit, e.String s.Digit :: e.String, # <IsUnacceptable e.String>, <Extend s.Len e.String>; };
And, finally, we define the function FindString, taking as argument the length of the desired sequence, and returning either the desired sequence (if found), or a failure (if the desired sequence does not exist).
$func? FindString s.Len = e.String; FindString s.Len = <Extend s.Len >;