The problem of the Longest Ribbon

The problem of the Longest Ribbon

This is a continuation of EWD942 in the sense that we shall use its notation and results.

In an integer sequence, a segment is "a ribbon of width $w$ " if no two of its elements are more than $w$ apart. Formally

(0) $b \cdot x \cdot y \equiv \left( {A,i,j : x \leq i < j < y : a\text{abs.}\left( {{P}{i} - {P}{j}}\right) \leq w}\right)$ .

The program should determine the maximum length of a ribbon of width $w$ in $p(i:0\leq i < N)$

The monotonicity assumption is satisfied, so the theory of EWD942 is applicable, and our job is the implementation of

$$ {h = g, n } h := g. (n + 1) {h = g. (n + 1) } $$

A quadratic algorithm readily presents itself; the purpose of this note is to develop an $N \cdot \log N$ algorithm.

Our first step is inspired by the knowledge - gathered in experience- that the absolute value is an awkward function that we therefore would like to eliminate from the functional specification. The best start is usually the use of

(1) $\operatorname{abs.}X = X\max - X$

This yields for the term in (0) the rewriting

$$ \begin{array}{l} a b s. (f _ {i} - f _ {j}) \leq w \ = {(i) } \quad (\mathrm {p . i} - \mathrm {f . j} \max = \mathrm {f . j} - \mathrm {p . i}) \leq w \ \end{array} $$

$$ \begin{array}{l} = {\mathrm {p r o p e r t h e s} \vert \max = \ p _ {i} ^ {\prime} - p _ {j} ^ {\prime} \leq w _ {i} \land p _ {j} ^ {\prime} - p _ {i} ^ {\prime} \leq w \ = {a r i t h m e t i c } \ p _ {i} \leq p _ {j} + w \land p _ {i} \geq p _ {j} - w \ \end{array} $$

That is, we have

$$ b. x. y \equiv b ^ {\prime}. x. y \wedge b ^ {\prime \prime}. x. y, w i t h $$

$$ \begin{array}{l} b. x. y \equiv (\underline {{A}} i, j: x \leq i < j < y: f. i \leq f. j + w) \quad a n d \ b ^ {n} x. y \equiv (\underline {{A}} i, j: x < i < j < y: f. i \geq f. j + w) \ \end{array} $$

This looks like a nice result in view of Theorem 1, EwD942. [I should probably not have introduced the term "right-strengthening":

$$ (A X, Y: B. (X Y): B. X) $$

is usually rendered by saying that "(the set of strings satisfying) B is prefix-closed".]

Does this help? Can we solve the problem for b.x.y if we can solve it for the simpler b'.x.y and b".x.y ? Let us explore this, in view of Theorem 1, EwD942, for disjunction and conjunction.

Let $g.n$ , $g'n$ , and $g''n$ be the smallest natural solutions of $x: b.x.n$ , $x: b'.x.n$ , and $x: b''.x.n$ respectively. Then

(i) for $b \cdot x \cdot y \equiv {b}^{\prime } \cdot x \cdot y \vee {b}^{\prime \prime } \cdot x \cdot y$ , $g \cdot n$ is the smallest natural value that solves $x : {b}^{\prime } \cdot x \cdot n$ or solves $x : {b}^{\prime \prime } \cdot x \cdot n$ , i.e. $g \cdot n = {g}^{\prime }n\min {g}^{\prime \prime }n$ (ii) for $b \cdot x \cdot y \equiv {b}^{\prime } \cdot x \cdot y \land {b}^{\prime \prime } \cdot x \cdot y,g \cap$ is the smallest common solution of both

i.e. $g \cdot n \geq {g}^{!}n\max = {g}^{\prime \prime }n,$

where we have the inequality in order to cater for the case that $g!n \max {g}^{\prime }n$ solves only one of the equations. We have

$$ g. n = g ^ {\prime}. n \max g ^ {\prime \prime}. n $$

$\left( {{A}{i} : {g}^{\prime }n < i \leq n : {b}^{\prime }.i,n}\right) \land \left( {{A}{i} : {g}^{\prime \prime }n < i \leq n : {b}^{\prime \prime }.i,n}\right) ,i \in e.$ $\left( {\underline{A}X,Y;B^{\prime }\left( {XY}\right) ;B^{\prime }Y}\right) \land \left( {\underline{A}X,Y;B^{\prime \prime }\left( {XY}\right) ;B^{\prime \prime }Y}\right) ,$

i.e. if both ${B}^{\prime }$ and ${B}^{\prime \prime }$ are postfix-closed as well!

Since our $B^{\prime}$ and $B$ are postfix-closed, a legitimate implementation of

$$ n := g. (n + 1) $$

is there fore

$$ h ^ {\prime} := g ^ {\prime} (n + 1); h ^ {\prime \prime} := g ^ {\prime \prime} (n + 1); h := h ^ {\prime} \max h ^ {\prime \prime} $$

i.e. by thus merging the solutions of the primed problems, we can solve the original one. The two primed problems are so similar - the one for $f$ is the other one for $-f$ - that we shall devote the rest of this note to solving the maximum segment length for $B'$ .

From EWD942 we know that our task is to implement

$$ {h ^ {\prime} = g ^ {\prime}. n } h := g ^ {\prime} (n + 1) $$

let us elaborate ${b}^{\prime }.x.\left( {n + 1}\right)$ since ${g}^{\prime }\left( {n + 1}\right)$ is defined as the smallest natural solution of $x : {b}^{\prime }.x.\left( {n + 1}\right)$

$$ \begin{array}{l} b ^ {\prime} \cdot x. (n + 1) \ = {\mathrm {d e f i n i t i o n} o f b ^ {\prime} } \ (\overline {{A}} i, j: x \leq i < j < n + 1: f _ {i} \leq f _ {j} + w) \ = {\mathrm {i s o l a t i o n l a r g e s t} j \cdot v a l u e } \ (\underline {{A}} i, j: x \leq i < j < n: f _ {i} ^ {j} \leq f _ {j} + w) \land (\underline {{A}} i: x \leq i < n: f _ {i} ^ {j} \leq f _ {n} + w) \ = {\mathrm {d e f i n i t i o n} o f b ^ {\prime} } \ b ^ {\prime}. x. n \wedge (\overline {{A}} i: x \leq i < n: f _ {i} \leq f _ {n} + w) \ \end{array} $$

Because ${B}^{\prime }$ is postfix-closed

$$ b ^ {\prime} x. n \equiv g ^ {\prime} n ^ {\prime} \leqslant x $$

Combining the two results, we find that

$$ b ^ {\prime} x. (n + 1) \equiv g ^ {\prime} n \leq x \land (\underline {{A}} i: x \leq i < n: f. i \leq f. n + w). $$

So far, we have simplified - which is always safe- and even quite nicely so in view of the precondition

Let us now investigate whether we can optimize. As b.x.(n+1) has been given, finding the smallest solution of x: b.x.(n+1) for a single value of n requires a linear search, which would lead to a quadratic algorithm. But that smallest solution has to be determined for a whole sequence of successive values of n , and the question is whether the algorithm can collect additional information about f(i.o.s i<n) as it goes along, with the aid of which the determination of the smallest solution of x: b.x.(n+1) can be speeded up. Because that additional information is to be used over and over again, for successive values of n we would like to reduce its dependence of n , which occurs in b.x.(n+1) in no less than 3 different places. Further more, it is reasonable to ex

pect that, somewhere along the line, we should ex.

The first conjunct of $b.x.(n + 1)$ being simple to evaluate and the second conjunct being the one that would give rise to the linear search, it is the latter one on which we should focus our attention. It is of the form Qo, given by

$$ Q _ {0} = (\underline {{A}} i: x \leq i < n: f. i \leq H) $$

in which we consider $H$ as a parameter,of which it is temporarily irrelevant that it depends on $P,n$ (which does not enter b.x.(n+1) in any other way). The introduction of $H$ is nothing deep: it is a convenient abbreviation.

Because -like $b^{\prime}x.(n + 1)$ -both its conjuncts weaken with increasing $x$ , $g^{\prime}(n + 1)$ is the maximum of $g.n$ and the smallest (natural) solution of $x:Qo$ .

In view of the very special form of Qo, the smallest natural solution of $x$ : Qo is almost the largest solution of

$$ x: (f _ {1} (x - 1) > H); $$

I said "almost" because in this formulation we have to ensure that the equation has a solution, no matter how large $H$ . This we can ensure by defining for the purpose of this discussion

$$ f _ {1} (- 1) = + \infty $$

This being done, we can define the smallest natural solution of $x$ : Qo as the unique q satisfying

$0 \leq q \leq n \land f\left( {q - 1}\right) > H \land \left( {{H}_{i} : q \leq i < n : f,i \leq H}\right)$

We would like to tackle the last conjunct with the aid of collected information, which should be independent of H. Because

$$ p _ {i} (q - 1) > H \land p _ {i} < H \Rightarrow p _ {i} < p _ {i} (q - 1) $$

we can "eliminate" $H$ from the quantified expression by concluding that $q$ is a solution of $x: Q_1$ with $Q_1$ given by

$$ Q _ {1} \equiv 0 \leq x \leq n \land f. (x - 1) > H \land (\underline {{A}} i: x \leq i < n: f. i < f. (x - 1)) $$

Let ${q1}$ be an arbitrary solution of $x : {Q1}$ ; then

$$ 9 1 - 1 < n \land f. (9 1 - 1) > H $$

From the last conjunct of (0) we then conclude ${91} - 1 < q$ or,equivalently, ${91} \leq q$ ,i.e. the

And now we are in good shape. Let us write

$$ Q _ {1} \equiv f _ {\cdot} (x - 1) > H \land Q _ {2} \qquad w i t h $$

$$ Q _ {2} \equiv 0 \leq x \leq n \land (\underline {{A}} i: x \leq i < n: f. i < f. (x - 1)) $$

i.e. we have extracted the conjuncts independent of $H -$ , and suppose that we have somehow tabulated the roots of $x:Q2$ in increasing order. In order to determine $q$ one has to find the largest root $x$ such that $f(x - 1) > H$ .

Let ${x0}$ and ${x1}$ be 2 different roots of $x : {Q2}$

In other words, for $x$ in increasing order ranging over the roots of $x: Q2$ , the values $P(x - 1)$ form a decreasing sequence, and as a result $q$ can be determined in logarithmic time.

The adjustment of the set of roots of $x$ : Q2 in preparation of n=n+1 has now to be considered. From Q2 we see that

(i) roots $x$ with ${f}{1}\left( {x - 1}\right) > {f}{n}$ also solve $x : {Q2}{n + 1}^{n}$ and hence have to be maintained (ii) roots $x$ with ${f}{.}\left( {x - 1}\right) \leq f.n$ don't solve $x : {Q2}^{\prime }{}_{n + 1}^{n}$ and hence have to be discarded (iii) the only new root of $x : {Q2}^{\mathrm{n}}$ is $\mathrm{n} + 1$ ,

Hence the roofof $x:Q2$ can be stored in a stack; since (accordog to (iii) stack growth is linear in N, the unstacking involved in (i) and (ii) can be done in the most naive fashion, one element at a time, and the manipulations remain linear in N.

Note Instead of stacking individual roots, one can stack root intervals, e.g. pairs $(i,j)$ such that the pair $(i,j)$ in the stack represents the roots $x$ satisfying $i < x \leq j$ (or the subscripts $x-1$ satisfying $i \leq x-1 < j$ ). S. Doitse Swierstra draw our attention to this possibility at the ATAC session of 15 October 1985. The searching for $q$ becomes a two-stage process - two binary searches in succession, one for the interval and one for the place in the interval. It remains logarithmic. Worst case storage demands remain linear in $N$ , the average case might be better. (End of Note.)

Concluding remarks

When I raised the problem of the longest ribbon length I had the feeling that it somehow was a stinker. Yet it took me some time to admit that -at least for the time being- could not find a shorter heuristically convincing argument that leads to Q2 .

Writing the above was much harder than I expected. (Took also more time than intended.) The introduction of the x-1 was a nuisance; I considered for quite some time whether I would try to eliminate it. But with the h as introduced in EWD942 I would get +1's in other places.

The discovery that the conjunction of prefix-closed predicates is only helpful if they are postfix-closed as well was only made after I embarked on this problem. The moral of the story seems to be that a compact theory about extreme solutions of equations with various forms of monotonicity would be welcome.

I am indebted to the ATAC . to Chris Lengauer in particular.

Austin, 18 October 1985

pror. Dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 -1188 USA