The Sequence Problem

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 Ge_a, Ge_b, and Ge_c that Ge_c is non-empty, and there holds
```
    Ge = Ge_a Ge_c Ge_c Ge_b
```
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 Ge_a Ge_c Ge_c Ge_b, where Ge_c 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

    Ge_a Ge_c Ge_c

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.