Now we consider the problem of finding a ground expression Ge having the
following property [Wir1973]:
-
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.
-
There is no such ground expressions Gea,
Geb, and Gec that
Gec is non-empty, and there holds
Ge = Gea Gec Gec Geb
i.e. Ge does not contain two adjacent non-empty equal subexpressions.
The desired expression can be found in the following way. We may start with an empty
expression, and then try to extend it, adding digits to it one by one. Upon adding a digit, we
have to check the expression thus obtained, to make sure that the expression does not have the
form Gea Gec Gec Geb, where
Gec is non-empty. A moment's thought reveals that, actually,
it is sufficient to check that the expression obtained by adding a digit does not have the
form
Gea Gec Gec
Here is the definition of the predicate IsUnacceptable, which determines
whether the argument has the above form:
$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 >;