% (c) 2005 D E Knuth; use and enjoy, but please don't blame me for mistakes...
\datethis
\def\title{VIENNOT}
\input epsf
@*Introduction. This short program implements a Viennot-inspired
bijection between Kepler towers with $w$~walls
and nested strings with height~$h$, where $2^w-1\le h<2^{w+1}-1$.
What is a Kepler tower? Good question. It is a new kind of combinatorial
object, invented by Xavier Viennot in February 2005. For example,
$$\epsfbox{kepler.2}$$
depicts a Kepler tower with 3 walls conaining 22 bricks.
This illustration is two-dimensional, but of course a tower has three
dimensions; we are viewing the tower from above. Every wall of a Kepler
tower consists of one or more rings, where
each ring of the $k$th wall is divided into $2^k$ segments of
equal length. Each brick is slightly longer than
the length of one segment.
Viennot gave the name Kepler tower to such a configuration because it
somehow suggests Kepler's model of the solar system, with the sun
in the center and the planets surrounding it in circumscribed shells.
Brick positions in the rings of the $k$th wall are identified by a sequence
of segment numbers $p_1$, \dots, $p_t$, where $1\le p_1<\cdots
int d[nn+1]; /* the path, a sequence of $\pm1$s */
int x[nn+1]; /* partial sums of the $d$'s */
char ring[n][n+3], ringcount[n]; /* occupied segments */
int wall[n]; /* wall boundaries in the |ring| array */
int serial; /* total number of cases checked */
int count[10]; /* individual counts by number of walls */
@#
main()
{
register int i,j,k,m,p,w,ww,y,mode;
printf("Checking Kepler towers with %d bricks...\n",n);
@;
while (1) {
@;
@;
@;
@;
}
done: for (w=1;count[w];w++)
printf("Altogether %d cases with %d wall%s.\n",
count[w],w,w>1? "s": "");
}
@t}\par\break{@>
@ Nested strings are conveniently generated by
Algorithm 7.2.1.6P of {\sl The Art of Computer Programming}.
@=
for (k=0;k=
d[i]=-1;
if (d[i-1]<0) d[i-1]=1, i--;
else {
for (j=i-1,k=nn-2;d[j]>0;j--,k-=2) {
d[j]=-1, d[k]=+1;
if (j==0) goto done;
}
d[j]=+1,i=nn-2;
}
@ @=
for (m=j=k=1;k=((1<0$.)
The main idea is to associate every
$r$-segment wall with a sequence of $\pm1$s whose partial sums
remain strictly less than $r$ in absolute value, except that the total
sum is $-r$. Let's call this an $r$-path.
For example, a one-wall Kepler tower corresponds to
a sequence $d_0$, $d_1$, \dots, $d_{2n}$ whose partial sums
remain nonnegative until the last step, and never exceed~2. Removing
the first element, $d_0$, leaves a 2-path,
because its partial sums are always 0, 1,
or $-1$, until finally reaching $d_1+\cdots+d_{2n}=-2$.
The $k$th wall of a larger tower
will correspond to a $2^k$-path in a similar fashion.
For example, the outer wall of a 3-wall tower comes from a
sequence $d_{p+1}$, \dots, $d_{2n}$ whose partial sums lie between
$-7$ and $+7$, except that the total sum is~$-8$; here $p$ denotes
the smallest subscript such that $d_0+\cdots+d_p=7$.
There's a slight problem, however, because the inner walls don't behave
in the same way; they give a ``dual'' $r$-path (the negative of
a true $r$-path), in which the total sum is $+r$ instead of $-r$.
Furthermore, our rule that associates $r$-paths with $r$-segment
walls doesn't obey rule (i) of Keplerian walls: Our rule
describes only the bricks {\it above\/} the bottom ring;
it produces one brick for each $+1$ in the $r$-path, so it
might not produce any bricks at all.
The solution is to associate both an ordinary wall and a dual
wall with any $r$-path or dual $r$-path, where the
ordinary wall has a brick for each $+1$ and the dual wall
has a brick for each $-1$. These walls won't satisfy
rule~(i), the bottom-ring constraint; but when we combine
them properly, everything fits together nicely so that
perfect Keplerian walls are indeed produced.
The reason this plan succeeds can best be understood by considering
what happens when a nested string $(d_0,d_1,\ldots,d_{2n})$ corresponds to,
say, a 3-wall Kepler tower. Such a path begins with $d_0=+1$; then
comes a dual 2-path, ending at $d_{p_1}$,
containing say $n_1$ positive elements and $n_1-2$ negative elements,
so that $p_1=2n_1-2$. A dual 4-path begins at $d_{p_1+1}$ and ends at
$d_{p_2}$, containing $n_2$ occurrences of $+1$ and $n_2-4$
occurrences of $-1$, so that $p_2=p_1+2n_2-4$. Finally there is
an ordinary 8-path containing $n_3$ positives and $n_3+8$ negatives,
so that $2n=p_2+2n_3+8=2n_1+2n_2+2n_3+2$. We obtain the desired
Kepler tower by putting one brick on the bottom ring and placing
$n_1-2$ bricks above them, using the dual wall from the dual 2-path.
We also put two bricks on the bottom ring of the second wall
and place $n_2-4$ bricks above them, using the dual wall from
the dual 4-path. And finally we put four bricks on the bottom ring
of the outer wall, surmounted by the $n_3$ bricks that represent the
ordinary wall of the ordinary 8-path. The total number of bricks is
$1+n_1+n_2+n_3=n$, as desired.
In summary, the problem is solved if we can find a good way to produce
$r$-segment walls from $r$-paths. And indeed, there is a simple
bijection: When the partial sum changes from 0 to~1, go into ``downward
mode'' in which a brick drops into segment~$s$ when the partial
sum decreases from $s$ to~$s-1$. When the partial sum changes from
0 to~$-1$, go into ``upward mode'' in which a brick drops into segment~$s$
when the partial sum increases from $s-r-1$ to $s-r$. In either case,
bricks drop into the uppermost ring for which they currently
have support from below.
For example, let's consider the case $r=3$. (Kepler towers use only
cases where $r$ is a power of~2, but the bijection in the previous
paragraph works fine for any value of~$r\ge2$.) The 3-path
$$\thinmuskip=6mu
+1,+1,-1,+1,-1,-1,-1,+1,-1,+1,+1,-1,-1,-1,+1,-1,-1$$
with partial sums
$$\thinmuskip=6mu \def~{\phantom{{+}}}
+1,+2,+1,+2,+1,~0,-1,~0,-1,~0,+1,~0,-1,-2,-1,-2,-3$$
goes into downward mode, drops bricks in segments 2, 2, 1, then goes
into upward mode, drops a brick in segment 3, enters upward mode
again and drops another~3, then resumes downward mode
and drops a brick into 1, and finishes with upward mode and a brick
into~2. (When $r=3$ each brick begins a new ring when it is dropped,
because at most $\lfloor r/2\rfloor$ bricks fit on a single ring.)
We can reverse the process and reconstruct the original sequence
by removing bricks from top to bottom, as described below.
@ This program represents an $r$-segment ring as an array of $r+2$
bytes, numbered 0 to $r+1$, with byte $k$ equal to 1 or 0
according as a brick occupies segment~$k$ or not.
Byte~0 is a duplicate of byte $r$, and byte~$r+1$
is a duplicate of byte~1, so that we can easily test whether a
brick will fit in a given segment of a given ring.
The current state of the tower appears in |ring[0]|, |ring[1]|, \dots,
|ring[m]|, where each |ring[j]| is an array of bytes as just mentioned.
The number of bricks in |ring[j]| is maintained in |ringcount[j]|.
Variable~|w| is the current number of walls; and
the $k$th wall consists of |ring[j]| for $|wall|[k-1]\le j<|wall|[k]$,
for $1\le k\le w$.
If we have most recently looked at |d[p]|, variable~|y| is the partial
sum $d[p'+1]+\cdots+d[p]$ of the current $2^w$-path, where $p'$ denotes
the position where the $2^{w-1}$-path ended.
We shall assume that all elements of |ring| are identically zero
when this algorithm begins.
@=
w=1,ww=2,m=0; /* $|ww|=2^w$ */
ring[0][1]=ring[0][3]=1;
for (y=p=0; y!=-ww; ) {
if (y==0) mode=-d[++p],y-=mode;
else if (y==ww) @@;
else {
y+=d[++p];
if (d[p]==mode) @;
}
}
wall[w]=m+1;
@ @=
{
wall[w++]=++m;
ww+=ww;
for (k=0;k<=ww;k+=2) ring[m][k+1]=1;
y=0;
}
@ @=
{
k=y+(mode<0? 1: ww); /* we'll drop a brick into segment |k| */
for (j=m;ring[j][k-1]==0 && ring[j][k]==0 && ring[j][k+1]==0;j--);
if (j==m) m++; /* enter a new ring, initially empty */
ring[j+1][k]=1;
if (k==1) ring[j+1][ww+1]=1;
else if (k==ww) ring[j+1][0]=1;
ringcount[j+1]++;
}
@*The inverse algorithm. Going backward is a matter of removing
bricks in the reverse order, reconstructing the nested string that
must have produced them. At the end of this process, the |ring|
array will once again be identically zero.
@d check(s) {@+y-=d[--p];
if (d[p]!=s)
fprintf(stderr,"Rejection at position %d, case %d!\n",p,serial);@+}
@=
m=wall[w]-1, mode=+1;
for (y=-ww+1,p=nn;p;) {
if (y==1-ww||y==ww-1) check(-mode)@;
else @;
}
@ @=
{
look: k=y+(mode<0? 1: ww); /* we'll look for a brick in segment |k| */
for (j=m;ring[j][k]==0;j--)
if (ring[j][k-1] || ring[j][k+1]) goto notfound;
if (j==wall[w-1]) goto notfound;
ring[j][k]=0; /* we found it! out it goes */
if (k==1) ring[j][ww+1]=0;
else if (k==ww) ring[j][0]=0;
ringcount[j]--;
if (ringcount[j]==0) m--;
check(mode);@+ continue;
notfound:@+ if (y==0) {
if (m==wall[w-1]) @@;
else @;
}
check(-mode);
}
@ @=
{
for (k=0;k<=ww;k+=2) ring[m][k+1]=0;
m--, ww>>=1, w--;
y=ww, mode=-1;
}
@ If |y=0| and |mode>0|, we looked for a brick in segment |ww|
and didn't find it. But at least one brick remains in the current
wall. Therefore, by the nature of the algorithm, a brick must
be free in segment~1. Similarly, if |y=0| and |mode<0|, there
must be a free brick in segment~|ww| at this time. (Think about it.)
@=
{
mode=-mode;@+ goto look;
}
@*Index.