=
if (p==q || p>q+8) {
fprintf(stderr,"Piece name is nonexistent or too long: %s",
buf);
exit(-7);
}
for (j=q;j=0 && y>=0 && occupied[0][x][y]) {
fprintf(stderr,"Piece name conflicts with board position: %s",
buf);
exit(-333);
}
}
@ It's a good idea to ``normalize'' the typical cells of a piece,
by making the |xmin| and |ymin| fields of |newbox| both zero.
@=
xy0=(newbox.xmin<<8)+newbox.ymin;
if (xy0) {
for (p=newbox.list;p;p=elt[p].link) elt[p].xy-=xy0;
newbox.xmax-=newbox.xmin,newbox.ymax-=newbox.ymin;
newbox.xmin=newbox.ymin=0;
}
@*Transformations. Now we get to the interesting part of this program,
as we try to find all of the base placements that are obtainable from
a given set of typical cells.
The method is a simple application of breadth-first search:
Starting at the newly created base, we make sure that
every elementary transformation of every known placement is also known.
This procedure requires a simple subroutine to check whether or not
two placements are equal. We can assume that both placements are normalized,
and that both have the same size. Equality testing is easy because
the lists have been sorted.
@=
int equality(int b) { /* return 1 if |base[b]| matches |newbox| */
register int p,q;
for (p=base[b].list,q=newbox.list; p; p=elt[p].link,q=elt[q].link)
if (elt[p].xy!=elt[q].xy || elt[p].suf!=elt[q].suf) return 0;
return 1;
}
@ Just two elementary transformations suffice to generate them all.
These transformations depend (in a somewhat subtle-but-nice way) on
whether or not there's a suffix that begins with `\.''.
@=
j=basecount,k=basecount+1; /* bases |j| thru |k-1| have been checked */
while (j;
for (i=basecount;i;
for (i=basecount;imaxbases) {
fprintf(stderr,"Overflow! Recompile me by making maxbases bigger than %d.\n",
basecount+23);
exit(-669);
}
@ The first elementary transformation replaces
$(x,y)$ by $(x+y-1,1-x)'$ and
$(x,y)'$ by $(x+y,1-x)$.
It corresponds to 60-degree rotation about the
``origin'' (the point between $(0,0)'$ and $(1,1)$)
in our coordinates).
Actually I add a constant, then normalize afterwards, so that the
coordinates don't go negative.
@=
newbox.size=newbox.list=0;
t=newbox.ymax=base[j].xmax;@+newbox.xmax=0;
newbox.xmin=newbox.ymin=64;
for (p=base[j].list;p;p=elt[p].link) {
x=elt[p].xy>>8, y=elt[p].xy&0xff;
if (elt[p].suf&1) { /* suffix starts with prime */
insert(x+y+1,t-x,elt[p].suf-1);
}@+else {
insert(x+y,t-x,elt[p].suf+1);
}
}
@;
@ The other elementary transformation replaces $(x,y)$ by $(y,x)$ and
$(x,y)'$ by $(y,x)'$. It corresponds to reflection about the line at slope
$30^\circ$ through the origin---a nice reflection that doesn't
interchange $\Delta$ with $\nabla$.
[I like to think of the barycentric coordinates $(x,y,z)$ such that
$x+y+z=1$ or~2, with $(x,y)\leftrightarrow(x,y,2-x,y)$ and
$(x,y)'\leftrightarrow(x,y,1-x-y)$.
With such coordinates the simplest transformations take $(x,y,z)$ to
$(y,x,z)$, $(y,z,x)$, and $(1-x,1-y,1-z)$.]
@=
newbox.size=newbox.list=0;
newbox.xmax=base[j].ymax, newbox.ymax=base[j].xmax;
for (p=base[j].list;p;p=elt[p].link) {
x=elt[p].xy>>8, y=elt[p].xy&0xff;
insert(y,x,elt[p].suf);
}
@*Finishing up. In previous parts of this program, I've terminated
abruptly when finding malformed input.
But when everything on |stdin| passes muster,
I'm ready to publish all the information that has been gathered.
@