#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tables.h"

int lookup(char *target) {
  // Return index of the word.  Binary chop for now.
  int low = 1, high = MAX_WORDS; // inclusive at each end
  while (low <= high) {
    int middle = (low+high)/2;
    int comparison = strcmp(word[middle].string, target);
    if (comparison < 0) {
      low = middle+1;
    } else if (comparison > 0) {
      high = middle-1;
    } else return middle;
  }
  return 0; // not found
}

/* look at best score for target_word.  if score+this_score is lower
   than anything previously found, set up a backlink to this_word and
   update the recorded score with new lower score.  We can then walk
   back from the target word to the root when we finally reach it.
*/

//#define INFINITY 99999 // very safe limit
#define INFINITY 999 // safe for all practical purposes, failure would be pathological

int level[MAX_WORDS+1]; // = INFINITY(*);
int best_score[MAX_WORDS+1]; // = INFINITY(*);
int backlink[MAX_WORDS+1]; // = 0(*);

// level: depth of node in breadth-first search
// score: cumulative score to here by best route
// this_word: index of 'from'
// target_word: index of 'to'
// this_score: value of this play (1 for letterswap, 3 for letterbank)
void push_link(int nextlevel, int score, int this_word, int target_word, int this_score) {
  int target_score = score + this_score;
  if (target_score < best_score[target_word]) {
    backlink[target_word] = this_word;
    best_score[target_word] = target_score;
    level[target_word] = nextlevel;
  }
}

void sweep(int this_level)
{
  int each;
  int to_word;
  int lbptr, lsptr;

  for (each = 1; each <= MAX_WORDS; each++) {
    if (level[each] == this_level) {
      if ((lsptr = word[each].ls) != 0) {
        while ((to_word = ls[lsptr++]) != 0) {
          push_link(this_level+1, best_score[each], each, to_word, 1);
        }
      }
      if ((lbptr = word[each].lb) != 0) {
        while ((to_word = lb[lbptr++]) != 0) {
          push_link(this_level+1, best_score[each], each, to_word, 3);
         }
      }
    }
  }
}

int main(int argc, char **argv) {
  char *startword, *endword;
  int from_word, to_word, target_word;
  int lbptr, lsptr;
  int next_level;
  int i;

  if ((argc != 2) && (argc != 3)) {
    fprintf(stderr, "syntax: lb from_word [to_word]?\n\n");
    exit(EXIT_FAILURE);
  }
  startword = argv[1];
  if (argc == 3) endword = argv[2]; else endword = "";

  for (i = 0; i <= MAX_WORDS; i++) {
    best_score[i] = INFINITY;
    backlink[i] = 0;
    level[i] = INFINITY;
  }

  from_word = lookup(startword);
  if (from_word == 0) {
    fprintf(stderr, "Start word \"%s\" not found in our allowed wordlist.\n", startword);
    exit(EXIT_FAILURE);
  }

  if (argc == 2) target_word = 0; else {
    target_word = lookup(endword);
    if (target_word == 0) {
      fprintf(stderr, "Target word \"%s\" not found in our allowed wordlist.\n", endword);
      exit(EXIT_FAILURE);
    }

    // This section is only for better error reporting, it can be deleted.
    lsptr = word[target_word].ls;
    lbptr = word[target_word].lb;
    if ((lsptr != 0) && (ls[lsptr] != 0) || (lbptr != 0) && (lb[lbptr] != 0)) {
      // found a link
    } else {
      // no links at all
      fprintf(stderr, "There is no word at all that can be linked to the target \"%s\"\n", endword);
      exit(EXIT_FAILURE);
    }
  }

  // initialise
  backlink[from_word] = 0;
  best_score[from_word] = 0;
  level[from_word] = 0;

  // another optional error report:
  lsptr = word[from_word].ls;
  lbptr = word[from_word].lb;
  if ((lsptr != 0) && (ls[lsptr] != 0) || (lbptr != 0) && (lb[lbptr] != 0)) {
    // found a link
  } else {
    // no links at all
    fprintf(stderr, "There is no word at all that the start word \"%s\" can link to\n", startword);
    exit(EXIT_FAILURE);
  }

  for (next_level = 0; next_level < INFINITY; next_level++) {
    sweep(next_level);
    // stop searching when we're at a level where it's just not possible
    // to generate a lower score than the best so far, eg if the score
    // is 14, there is no possible 15-step solution that could score 14
    // or less, even if all moves are 1-point letterswaps.
    if (next_level > best_score[target_word]) break;
  }

  // check for a valid result:
  if (backlink[target_word] != 0) {
    int link = target_word;
    // walk backlinks and scores
    for (;;) {
      fprintf(stdout, "%s %d\n", word[link].string, best_score[link]);
      if (link == from_word) break;
      link = backlink[link];
    }
    exit(EXIT_SUCCESS);
  } else {
    int i, best = 0, link;
    if (target_word != 0) fprintf(stderr, "Sorry, no path found from \"%s\" to \"%s\" in less than %d steps.\n",
                    startword, endword, INFINITY);
    for (i = 1; i <= MAX_WORDS; i++) {
      if ((best_score[i] >= best) && (best_score[i] != INFINITY)) {
        best = best_score[i]; link = i;
      }
    }
    // walk backlinks and scores
    if (best != INFINITY) {
      fprintf(stderr, "Longest path seen was:\n");
      for (;;) {
        fprintf(stdout, "%s %d\n", word[link].string, best_score[link]);
        if (link == from_word) break;
        link = backlink[link];
      }
    }
    exit(EXIT_FAILURE);
  }
  return 0;
}