/* Output from p2c, the Pascal-to-C translator */
/* From input file "ladder4.p" */


#include "p2c/home/p2c/p2c.h"


#define NONE            (-1)
#define wordLength      4
#define maxSteps        99
#define maxWords        20000

#define infinite        99999L


typedef short dictIndex;

typedef Char fixedLength[wordLength];

typedef struct wordStatus {
  long dist;
  dictIndex prev;
  fixedLength word;
} wordStatus;

typedef wordStatus dictionary[maxWords + 2];


Static dictIndex lastWord;
Static dictionary dict;
Static fixedLength first, last;
Static dictIndex firstIdx, lastIdx;
Static FILE *dictfile;


Static Void InitVars()
{
  lastWord = -1;
  /*  reset(input, 'TT:'); */
  /*  rewrite(output, 'TT:'); */
  if (dictfile != NULL)
    dictfile = freopen("word4", "r", dictfile);
  else
    dictfile = fopen("word4", "r");
  if (dictfile == NULL)
    _EscIO(FileNotFound);
}


Static Void ResetVars()
{
  dictIndex each, FORLIM;
  wordStatus *WITH;

  FORLIM = lastWord + 1;
  for (each = 1; each <= FORLIM; each++) {
    WITH = &dict[each];
    WITH->prev = NONE;
    WITH->dist = infinite;
  }
}


Static Void ReadDict(dict)
wordStatus *dict;
{
  char i;
  wordStatus *WITH;

  while (!P_eof(dictfile) && lastWord < maxWords) {
    lastWord++;
    WITH = &dict[lastWord + 1];
    for (i = 0; i < wordLength; i++) {
      WITH->word[i] = getc(dictfile);
      if (WITH->word[i] == '\n')
	WITH->word[i] = ' ';
    }
    fscanf(dictfile, "%*[^\n]");
    getc(dictfile);
    /*     WriteLn('Added word ', word);*/
    WITH->prev = NONE;
    WITH->dist = infinite;
  }
  /* WriteLn('End of file - Dictionary Read OK');*/
}


Static dictIndex Idx(word_)
Char *word_;
{
  dictIndex Result;
  fixedLength word;
  dictIndex mid, l, r;

  memcpy(word, word_, sizeof(fixedLength));
  r = lastWord;
  l = 0;
  mid = l;
  Result = -1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (strncmp(word, dict[mid + 1].word, sizeof(fixedLength)) >= 0) {
      if (!strncmp(word, dict[mid + 1].word, sizeof(fixedLength))) {
	Result = mid;
	goto _L999;
      }
      l = mid + 1;
    } else
      r = mid - 1;
  }
_L999:
  return Result;
}


Local dictIndex FindPivot(low, high)
dictIndex low, high;
{
  if (low < high)
    return low;
  else
    return -1;
}

Local Void Swap(one, two)
dictIndex one, two;
{
  wordStatus temp;

  temp = dict[one + 1];
  dict[one + 1] = dict[two + 1];
  dict[two + 1] = temp;
}

Local Void Partition(last, low, high, pivot)
dictIndex *last, low, high;
Char *pivot;
{
  dictIndex dex;

  *last = low;
  for (dex = low + 1; dex <= high; dex++) {
    if (strncmp(dict[dex + 1].word, pivot, sizeof(fixedLength)) < 0) {
      (*last)++;
      Swap(*last, dex);
    }
  }
  if (low != *last)
    Swap(low, *last);
}


Static Void SortDict(low, high)
dictIndex low, high;
{
  /* This is a totally brain-damaged quicksort out of a book for
     American University students. God help them... */
  fixedLength pivot;
  dictIndex last, pivotIndex;

  pivotIndex = FindPivot(low, high);
  if (pivotIndex == -1)
    return;
  memcpy(pivot, dict[pivotIndex + 1].word, sizeof(fixedLength));
  Partition(&last, low, high, pivot);
  SortDict(low, last - 1);
  SortDict(last + 1, high);
}


Static Void ReadWord(word)
Char *word;
{
  char i;

  /* WriteLn('Reading a word...');*/
  for (i = 0; i < wordLength; i++) {
    word[i] = getchar();
    /*    WriteLn('Word[', i, '] = ', ORD(word[i]));*/
    if (word[i] == '\n')
      word[i] = ' ';
  }
  scanf("%*[^\n]");
  /*  WriteLn('Word is <', word, '>');*/
  getchar();
}


Static Void FindLadders(last, root)
dictIndex last, root;
{
  fixedLength word;
  char chpos;
  short level;
  dictIndex test, neighbour;
  Char ch, other;
  dictIndex FORLIM1;

  dict[root + 1].dist = 0;
  for (level = 1; level <= maxSteps; level++) {
    FORLIM1 = lastWord;
    for (test = 0; test <= FORLIM1; test++) {
      if (dict[test + 1].dist == level - 1) {
	memcpy(word, dict[test + 1].word, sizeof(fixedLength));
	for (chpos = 0; chpos < wordLength; chpos++) {
	  ch = word[chpos];
	  for (other = 'a'; other <= 'z'; other++) {
	    if (ch != other) {
	      word[chpos] = other;
	      neighbour = Idx(word);
	      if (neighbour != -1 && dict[neighbour + 1].dist > level) {
		dict[neighbour + 1].dist = level;
		dict[neighbour + 1].prev = test;
		/*               WriteLn(dict[test].word, ' -> ', word);*/
	      }
	    }
	  }
	  word[chpos] = ch;
	}
      }
    }
    if (dict[last + 1].dist != infinite) {
      printf("%12d step path found!\n", level);
      goto _L999;
    }
    printf("Finished level %12d\n", level);
  }
_L999: ;
}


Static Void PrintLadders(root, last)
dictIndex root, last;
{
  dictIndex prev;

  if (dict[root + 1].dist == infinite) {
    printf("No path found between %.*s and %.*s\n",
	   wordLength, dict[root + 1].word, wordLength, dict[last + 1].word);
    return;
  }
  printf("%.*s\n", wordLength, dict[root + 1].word);
  do {
    prev = dict[root + 1].prev;
    printf("%.*s\n", wordLength, dict[prev + 1].word);
    root = prev;
  } while (root != last);
}


main(argc, argv)
int argc;
Char *argv[];
{
  PASCAL_MAIN(argc, argv);
  dictfile = NULL;
  InitVars();
  ReadDict(dict);
  /*  SortDict(0, lastWord);*/
  do {
    do {
      printf("From: ");
      ReadWord(first);
      firstIdx = Idx(first);
      if (firstIdx == -1)
	printf("%.*s is not in the dictionary\n", wordLength, first);
    } while (firstIdx == -1);
    do {
      printf("To:   ");
      ReadWord(last);
      lastIdx = Idx(last);
      if (lastIdx == -1)
	printf("%.*s is not in the dictionary\n", wordLength, last);
    } while (lastIdx == -1);
    FindLadders(firstIdx, lastIdx);
    PrintLadders(firstIdx, lastIdx);
    ResetVars();
  } while (true);
_L999:
  if (dictfile != NULL)
    fclose(dictfile);
  exit(EXIT_SUCCESS);
}



/* End. */