#define quit_if(x,c)  \
if(x) { \
fprintf(stderr, \
"Sorry, I couldn't build a dictionary (trouble code %d)!\n",c) ; \
return c; \
} \

#define a_dist(k) (*(p+k) <*(q+k) ?*(q+k) -*(p+k) :*(p+k) -*(q+k) )  \

#define h_dist(k) (*(p+k) ==*(q+k) ?0:1)  \

/*4:*/
#line 86 "ladders.w"

#include <ctype.h> 
#include "gb_graph.h" 
#include "gb_words.h" 
#include "gb_dijk.h" 

/*5:*/
#line 113 "ladders.w"

char alph= 0;
char freq= 0;
char heur= 0;
char echo= 0;
unsigned n= 0;
char rand= 0;
long seed= 0;

/*:5*//*8:*/
#line 158 "ladders.w"

Graph*g;
int zero_vector[9];

/*:8*//*13:*/
#line 238 "ladders.w"

Graph*gg;
char start[6],goal[6];

Vertex*uu,*vv;

/*:13*//*24:*/
#line 345 "ladders.w"

long min_dist;

/*:24*/
#line 92 "ladders.w"

/*12:*/
#line 215 "ladders.w"

int freq_cost(v)
Vertex*v;
{register long acc= v->weight;
register k= 16;
while(acc)k--,acc>>= 1;
return(k<0?0:k);
}

/*:12*//*18:*/
#line 280 "ladders.w"

void plant_new_edge(v)
Vertex*v;
{Vertex*u= gg->vertices+gg->n;
gb_new_edge(u,v,1);
if(alph)
u->arcs->len= (u->arcs-1)->len= alph_dist(u->name,v->name);
else if(freq){
u->arcs->len= 20;
(u->arcs-1)->len= freq_cost(v);
}
}

/*:18*//*19:*/
#line 296 "ladders.w"

int alph_dist(p,q)
register char*p,*q;
{
return a_dist(0)+a_dist(1)+a_dist(2)+a_dist(3)+a_dist(4);
}

/*:19*//*21:*/
#line 322 "ladders.w"

int hamm_dist(p,q)
register char*p,*q;
{
return h_dist(0)+h_dist(1)+h_dist(2)+h_dist(3)+h_dist(4);
}

/*:21*//*23:*/
#line 336 "ladders.w"

long alph_heur(v)
Vertex*v;
{return alph_dist(v->name,goal);}

long hamm_heur(v)
Vertex*v;
{return hamm_dist(v->name,goal);}

/*:23*//*28:*/
#line 378 "ladders.w"

int prompt_for_five(s,p)
char*s;
register char*p;
{register char*q;
register int c;
while(1){
printf("%s word: ",s);
fflush(stdout);
q= p;
while(1){
c= getchar();
if(c==EOF)return-1;
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;
if(q==p)return 1;
printf("(Please type five lowercase letters and RETURN.)\n");
}
}

/*:28*/
#line 93 "ladders.w"

main(argc,argv)
int argc;
char*argv[];
{
/*6:*/
#line 122 "ladders.w"

while(--argc){

if(strcmp(argv[argc],"-v")==0)verbose= 1;
else if(strcmp(argv[argc],"-a")==0)alph= 1;
else if(strcmp(argv[argc],"-f")==0)freq= 1;
else if(strcmp(argv[argc],"-h")==0)heur= 1;
else if(strcmp(argv[argc],"-e")==0)echo= 1;
else if(sscanf(argv[argc],"-n%u",&n)==1)rand= 0;
else if(sscanf(argv[argc],"-r%u",&n)==1)rand= 1;
else if(sscanf(argv[argc],"-s%ld",&seed)==1);
else{
fprintf(stderr,"Usage: %s [-v][-a][-f][-h][-e][-nN][-rN][-sN]\n",argv[0]);
return-2;
}
}
if(alph||rand)freq= 0;
if(freq)heur= 0;

/*:6*/
#line 98 "ladders.w"
;
/*7:*/
#line 151 "ladders.w"

g= words(n,(rand?zero_vector:NULL),0,seed);
quit_if(g==NULL,panic_code);
/*9:*/
#line 166 "ladders.w"

if(verbose){
if(alph)printf("(alphabetic distance selected)\n");
if(freq)printf("(frequency-based distances selected)\n");
if(heur)printf("(lowerbound heuristic will be used to focus the search)\n");
if(rand)printf("(random selection of %d words with seed %d)\n",g->n,seed);
else printf("(the graph has %d words)\n",g->n);
}

/*:9*/
#line 154 "ladders.w"
;
/*10:*/
#line 182 "ladders.w"

if(alph){register Vertex*u;
for(u= g->vertices+g->n-1;u>=g->vertices;u--){register Arc*a;
register char*p= u->name;
for(a= u->arcs;a;a= a->next){register char*q= a->tip->name;
a->len= a_dist(a->loc);
}
}
}else if(freq){register Vertex*u;
for(u= g->vertices+g->n-1;u>=g->vertices;u--){register Arc*a;
for(a= u->arcs;a;a= a->next)
a->len= freq_cost(a->tip);
}
}

/*:10*/
#line 155 "ladders.w"
;
/*11:*/
#line 201 "ladders.w"

if(alph||freq||heur){
init_queue= init_128;
delete_min= delete_from_128;
enqueue= enqueue_128;
requeue= requeue_128;
}

/*:11*/
#line 156 "ladders.w"
;

/*:7*/
#line 99 "ladders.w"
;
while(1){
/*27:*/
#line 371 "ladders.w"

putchar('\n');
restart:

if(prompt_for_five("Starting",start)!=0)break;
if(prompt_for_five("    Goal",goal)!=0)goto restart;

/*:27*/
#line 101 "ladders.w"
;
/*14:*/
#line 244 "ladders.w"

/*15:*/
#line 250 "ladders.w"

gg= gb_new_graph(0);
quit_if(gg==NULL,20);
gg->vertices= g->vertices;
gg->n= g->n;
/*16:*/
#line 265 "ladders.w"

(gg->vertices+gg->n)->name= start;
uu= find_word(start,plant_new_edge);
if(!uu)
uu= gg->vertices+gg->n++;

/*:16*/
#line 255 "ladders.w"
;
/*17:*/
#line 271 "ladders.w"

if(strncmp(start,goal,5)==0)vv= uu;
else{
(gg->vertices+gg->n)->name= goal;
vv= find_word(goal,plant_new_edge);
if(!vv)
vv= gg->vertices+gg->n++;
}

/*:17*/
#line 256 "ladders.w"
;
if(gg->n==g->n+2)/*20:*/
#line 310 "ladders.w"

if(hamm_dist(start,goal)==1){
gg->n--;
plant_new_edge(uu);
gg->n++;
}

/*:20*/
#line 257 "ladders.w"
;
quit_if(gb_alloc_trouble,21);

/*:15*/
#line 245 "ladders.w"
;
/*22:*/
#line 331 "ladders.w"

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);

/*:22*/
#line 246 "ladders.w"
;
/*25:*/
#line 348 "ladders.w"

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

/*:25*/
#line 247 "ladders.w"
;
/*26:*/
#line 358 "ladders.w"

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;
vv->arcs= vv->arcs->next;
}
uu->arcs= NULL;
}
gb_recycle(gg);

/*:26*/
#line 248 "ladders.w"
;

/*:14*/
#line 103 "ladders.w"
;
}
}

/*:4*/