ladders.w

模拟器提供了一个简单易用的平台

  del_min=del_128;
  enqueue=enq_128;
  requeue=req_128;
}

@ The frequency has been computed with the default weights explained in the
documentation of |words|; it is usually less than $2^{16}$.
A word whose frequency is 0 costs~16; a word whose frequency is 1 costs~15;
a word whose frequency is 2 or 3 costs~14; and the costs keep decreasing
by~1 as the frequency doubles, until we reach a cost of~0.

@<Sub...@>=
long freq_cost(v)
  Vertex *v;
{@+register long acc=v->weight; /* the frequency, to be shifted right */
  register long k=16;
  while (acc) k--, acc>>=1;
  return (k<0? 0: k);
}

@* Minimal ladders. The guts of this program is a routine to compute shortest
paths between two given words, |start| and |goal|.

The |dijkstra| procedure does this, in any graph with nonnegative arc lengths.
The only complication we need to deal with here is that |start| and |goal|
might not themselves be present in the graph. In that case we want to insert
them, albeit temporarily.

The conventions of {\sc GB\_\,GRAPH} allow us to do the desired augmentation
by creating a new graph |gg| whose vertices are borrowed from~|g|. The
graph~|g| has space for two more vertices (actually for four), and any
new memory blocks allocated for the additional arcs present in~|gg| will
be freed later by the operation |gb_recycle(gg)| without confusion.

@<Glob...@>=
Graph *gg; /* clone of |g| with possible additional words */
char start[6], goal[6];
   /* \.{words} dear to the user's \.{heart}, plus |'\0'| */
Vertex *uu, *vv; /* start and goal vertices in |gg| */

@ @<Find a minimal ladder from |start| to |goal|...@>=
@<Build the amplified graph |gg|@>;
@<Let |dijkstra| do the hard work@>;
@<Print the answer@>;
@<Remove all traces of |gg|@>;

@ @<Build the amplified graph |gg|@>=
gg=gb_new_graph(0L);
quit_if(gg==NULL,no_room+5);  /* out of memory */
gg->vertices = g->vertices;
gg->n = g->n;
@<Put the |start| word into |gg|, and let |uu| point to it@>;
@<Put the |goal| word into |gg|, and let |vv| point to it@>;
if (gg->n==g->n+2) @<Check if |start| is adjacent to |goal|@>;
quit_if(gb_trouble_code,no_room+6); /* out of memory */

@ The |find_word| procedure returns |NULL| if it can't find the given word
in the graph just constructed by |words|. In that case it has applied its
second argument to every adjacent word. Hence the program logic here
does everything needed to add a new vertex to~|gg| when necessary.

@<Put the |start| word into |gg|, and let |uu| point to it@>=
(gg->vertices+gg->n)->name = start; /* a tentative new vertex */
uu=find_word(start,plant_new_edge);
if (!uu)
  uu = gg->vertices + gg->n++; /* recognize the new vertex and refer to it */

@ @<Put the |goal|...@>=
if (strncmp(start,goal,5)==0) vv=uu; /* avoid inserting a word twice */
else {
  (gg->vertices+gg->n)->name = goal; /* a tentative new vertex */
  vv=find_word(goal,plant_new_edge);
  if (!vv)
    vv = gg->vertices + gg->n++; /* recognize the new vertex and refer to it */
}

@ The |alph_dist| subroutine calculates the alphabetic distance between
arbitrary five-letter words, whether they are adjacent or not.

@<Sub...@>=
long alph_dist(p,q)
  register char *p, *q;
{
  return a_dist(0)+a_dist(1)+a_dist(2)+a_dist(3)+a_dist(4);
}

@ @<Sub...@>=
void plant_new_edge(v)
  Vertex *v;
{@+Vertex *u=gg->vertices+gg->n; /* the new edge runs from |u| to |v| */
  gb_new_edge(u,v,1L); /* we have $u>v$, hence |v->arcs=u->arcs-1| */
  if (alph)
    u->arcs->len=(u->arcs-1)->len=alph_dist(u->name,v->name);
  else if (freq) {
    u->arcs->len=freq_cost(v); /* adjust the arc length from |u| to |v| */
    (u->arcs-1)->len=20; /* adjust the arc length from |v| to |u| */
  }
}

@ There's a bug in the above logic that could be embarrassing,
although it will come up only when a user is trying to be clever: The
|find_word| routine knows only the words of~|g|, so it will fail to
make any direct connection between |start| and |goal| if they happen
to be adjacent to each other yet not in the original graph. We had
better fix this, otherwise the computer will look stupid.

@<Check if |start|...@>=
if (hamm_dist(start,goal)==1) {
  gg->n--; /* temporarily pretend |vv| hasn't been added yet */
  plant_new_edge(uu); /* make |vv| adjacent to |uu| */
  gg->n++; /* and recognize it again */
}

@ The Hamming distance between words is the number of character positions
@^Hamming, Richard Wesley, distance@>
in which they differ.

@d h_dist(k) (*(p+k)==*(q+k)? 0: 1)

@<Sub...@>=
long hamm_dist(p,q)
  register char *p, *q;
{
  return h_dist(0)+h_dist(1)+h_dist(2)+h_dist(3)+h_dist(4);
}

@ OK, now we've got a graph in which |dijkstra| can operate.

@<Let |dijkstra| do the hard work@>=
if (!heur) min_dist=dijkstra(uu,vv,gg,NULL);
else if (alph) min_dist=dijkstra(uu,vv,gg,alph_heur);
else min_dist=dijkstra(uu,vv,gg,hamm_heur);

@ @<Sub...@>=
long alph_heur(v)
  Vertex *v;
{@+return alph_dist(v->name,goal);@+}
@#
long hamm_heur(v)
  Vertex *v;
{@+return hamm_dist(v->name,goal);@+}

@ @<Glob...@>=
long min_dist; /* length of the shortest ladder */

@ @<Print the answer@>=
if (min_dist<0) printf("Sorry, there's no ladder from %s to %s.\n",start,goal);
else print_dijkstra_result(vv);

@ Finally, we have to clean up our tracks. It's easy to remove all arcs
from the new vertices of~|gg| to the old vertices of~|g|; it's a bit
trickier to remove the arcs from old to new. The loop here will also
remove arcs properly between start and goal vertices, if they both
belong to |gg| not~|g|.

@<Remove all traces of |gg|@>=
for (uu=g->vertices+gg->n-1; uu>=g->vertices+g->n; uu--) {@+register Arc *a;
  for (a=uu->arcs; a; a=a->next) {
    vv=a->tip; /* now |vv->arcs==a-1|, since arcs for edges come in pairs */
    vv->arcs=vv->arcs->next;
  }
  uu->arcs=NULL; /* we needn't clear |uu->name| */
}
gb_recycle(gg); /* the |gg->data| blocks disappear, but |g->data| remains */

@* Terminal interaction. We've finished doing all the interesting things.
Only one minor part of the program still remains to be written.

@<Prompt for...@>=
putchar('\n'); /* make a blank line for visual punctuation */
restart: /* if we try to avoid this label,
              the |break| command will be broken */
if (prompt_for_five("Starting",start)!=0) break;
if (prompt_for_five("    Goal",goal)!=0) goto restart;

@ @<Sub...@>=
long prompt_for_five(s,p)
  char *s; /* string used in prompt message */
  register char *p; /* where to put a string typed by the user */
{@+register char *q; /* current position to store characters */
  register long c; /* current character of input */
  while (1) {
    printf("%s word: ",s);
    fflush(stdout); /* make sure the user sees the prompt */
    q=p;
    while (1) {
      c=getchar();
      if (c==EOF) return -1; /* end-of-file */
      if (echo) putchar(c);
      if (c=='\n') break;
      if (!islower(c)) q=p+5;
      else if (q<p+5) *q=c;
      q++;
    }
    if (q==p+5) return 0; /* got a good five-letter word */
    if (q==p) return 1; /* got just \<return> */
    printf("(Please type five lowercase letters and RETURN.)\n");
  }
}

@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.