The Sequence Problem

Now we consider the problem of finding a ground expression Ge having the following property [Wir1973]:
  1. Ge contains no parentheses, and any symbol appearing in Ge is either 1, 2, or 3.

  2. The length of Ge is equal to a given number Len.

  3. 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 >;

Bibliography

[Wir1973] N.Wirth. Systematic Programming. An Introduction.. Prentice-Hall, Inc.. Englewood Cliffs, New Jersey. 1973.