/* The file you are looking at is in my working directory so
   may be in the middle of an edit.  See the -stable version for
   one sure to work */

/* (c) Graham Toal, 23May1999 */

/* I spoke too soon about this being well optimised... I forgot that
   the x=y symmetry would reduce the final run time by 50% if I can
   find a way to take advantage of it.   Still, it's only linear -
   the real optimisation here is in reducing the exponential term.

   This version fixes the bogosity that required a manual check of the
   word in the last column.

 */


#include <stdio.h>
#include <stdlib.h>

#include "splib.h"

#ifndef TRUE
#define TRUE (0==0)
#define FALSE (!TRUE)
#endif

/* The dictionary itself is global, as these variables are seldom
   referenced, and I don't want to pass them in as parameters to every
   procedure just so I can access them occassionaly */

NODE *rootdawg;
INDEX nedges;

#define MAX 11 /* Biggest we're willing to tackle will eventually be 10 */

static int sq[MAX/* row */][MAX/* col */];		/* letters */

static NODE *fork_point[MAX+1/* row */][MAX/* col */];
             /* downward word branch choices from this row */

static char check[MAX+1/* row */][MAX/* col */][256+1/* alphabet */];
                  /* string of letters which
                     are valid in each position in the row below */

/* This one is *NOT* row, col */
static char vertical_word[MAX /* col */][MAX+1 /* row/wordlen */];

/* This is probably redundant - it's just a printable horizontal word 
   also used for communication.  Can probably use sq[][] instead. */
char word[MAX /* row */][MAX+1 /* len */];


/* Doubles as producing answers and debug routine */
void print_square(int row, int col, int max, char *s)
{
  int i, j;

  printf(s);
  j = (row/2)-1;
  for (;;) {
    for (i = max-1; i >= 0; --i) putchar(sq[j][i]);
    putchar('\n');
    if (j == 0) break;
    j -= 1;
  }
  putchar('\n');
  fflush(stdout);
}

/* parameter col is the length is of the horizontal word and should
   always be invoked externally with len=0.  hnode should be dawg+1 for
   the start of every word in the full wordlist. */

/* Iterate a letter at a time across each row; recurse at the end of a
   row to go to the next row.  Backtrack when the square is blocked. */

void next_letter(NODE *hnode, int row, int max, int col)
{
  NODE *nextnode;
  int ch;
  NODE *savednode;
  char savedcheck[256];

  if (row == max || col == max) return;
  /* safety - I'd prefer this were done at the point of the recursive call  */
  /* It's because of things like that that some of the arrays have to be +1 */

  for (;;) { /* loop across horizontal letter placement */
    ch = (char)(((*hnode) >> V_LETTER) & M_LETTER);
    word[row][col] = ch;
    word[row][col+1] = '\0';
    sq[row][col] = ch;
    vertical_word[col][row] = ch;
    vertical_word[col][row+1] = '\0';

    nextnode = rootdawg+((*hnode) & M_NODE_POINTER);

    /* Test to see if this edge letter is allowed in the vertical
       crosscheck list */

    if (strchr(check[row][col], ch) != NULL) {

      int nextfree;
      int found;
      NODE *vnode;

      /* letter is placed.  Before we go any further, did this
         placement generate a solution? */

      /* letter is placed in the square, now see if it is valid.
         We place next horizontal letter recursively if this one was
           accepted OK.  It may be rejected due to vertical crosscheck
           and it may be rejected because it blocks off the vertical
           word from being expanded further downwards.  Of course
           we shouldn't care about the latter if this is the final row. */

      /* INLINE: 
         fork_point[row+1][col] = follow_edge(fork_point[row][col], ch); */

      vnode = fork_point[row][col];

      found = FALSE;
      for (;;) { /* placed a letter, look for next set of options */
        if (ch == (((*vnode) >> V_LETTER) & M_LETTER)) {
          vnode = rootdawg+(*vnode & M_NODE_POINTER);
          found = TRUE; break;
	}
        if ((*vnode & M_END_OF_NODE) != 0) break;
        vnode++;
      }
      if (found) {
        savednode = fork_point[row+1][col];
        strcpy(savedcheck, check[row+1][col]);
        fork_point[row+1][col] = vnode;
        nextfree = 0;
        for (;;) {
          if (vnode == NULL) {
            fprintf(stdout, "Don't know why vnode is NULL\n");
            exit(1);
          }
          check[row+1][col][nextfree++] = ((*vnode) >> V_LETTER) & M_LETTER;
          if ((*vnode & M_END_OF_NODE) != 0) break;
          vnode++;
        }
        check[row+1][col][nextfree++] = '\0';

        if (col+1 == max) {
          /* good placement on this row.
             recurse to next row.
             reset the dictionary to start of line */

          if (row+1 == (max/2)) {
            /* As the word would not have been placed unless it formed a
               vertical word also, we must have a solution.  Print it and return */
            print_square(max,max,max,"Lower Half Solution:\n");
            return;
          }

          /* good placement.  recurse to next row.  reset the dictionary */
          next_letter(rootdawg+1, row+1, max, 0);
        } else {
          /* place next letter horizontally */
          next_letter(
            nextnode, row, max, col+1);
	}
        /* what I worry about here is when we backtrack, do all
           the things like check[] and fork_point[] work properly?
           They *should* do, because ones we backtrack over should
           never be looked at, but I have this niggling doubt, at
           least as long as the program isn't working...
         */

        fork_point[row+1][col] = savednode;
        strcpy(check[row+1][col], savedcheck);
      } else {
        char tmp[256];
        /* Cannot make this play because it blocks of progress for
           a vertical word.  Go back up a row. */;
        /* (or maybe backtrack a letter and try another word on this row?) */
      }
    }

    /* now see if there is another letter at this position. */

    if ((*hnode & M_END_OF_NODE) != 0) break; /* end of node */
    hnode++;
  } /* end loop across horizontal letter placement */
}

int main(int argc, char **argv) {
  char fname[256];
  int row, col;
  int max;

  if (argc == 1) {
    max = 4;
  } else if (argc == 2) {
    max = *argv[1];
    if (isdigit(max)) max = max - '0'; else max = 4;
    if (max == 1 || max == 0) max = 10;
  } else {
    fprintf(stderr, "syntax: ws 4\n        (or any number 2-9)\n");
    exit(1);
  }

  sprintf(fname, "revdawg.%0d", max);
  if (!dawg_init(fname, &rootdawg, &nedges)) {
    fprintf(stdout, "Cannot open %s\n", fname);
    exit(1);
  }

  /* Have to initialise first row specially.
     *all* words are valid at this point. */

  row = 0;
  for (row = 0; row < max; row++) {
    /* wrong for all but 0th row, but we don't care as it'll be filled in
       in time anyway. */
    for (col = 0; col < max; col++) {
      sq[row][col] = '_';
      strcpy(check[row][col], "abcdefghijklmnopqrstuvwxyz");
      fork_point[row][col] = rootdawg+1;
      strcpy(vertical_word[col], "");
    }
  }
  next_letter(rootdawg+1, 0, max, 0/*len*/);

  print_square(max,max,max,"Final state (non solution):\n");

  exit(0);
}