/* program:      findword.c
   author:       Werner Hoch <werner.ho@gmx.de>
   description:  search words in a field of characters
   licence:      public domain without any warranty
   |
  -+-----------> col
   | wordrow         (col, line)
   | ordrdro
   | rdrordr
   | droword
   |
   V line
*/

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

/*#define DEBUG*/

char * m_array;  /* linearised matrix of letters size maxline*maxcol */
int maxline=1, maxcol=0;

int
file_load(char * name) {
  FILE *f;
  int line=0, col=0;
  int c,i;

  if ((f = fopen(name,"rt")) == NULL)  {
    fprintf(stderr, "Error: Cannot open file: %s \n", name);
    return (0);
  }

  while ( (c=fgetc(f)) != EOF) {  /* get the size of the file */
    switch (c) {
    case '\n':
      maxline++;
      col=0;
      break;
    default:
      col++;
      if (col > maxcol)
	maxcol = col;
    }
  }
#ifdef DEBUG
  printf("maxline: %d, maxcol: %d\n", maxline, maxcol);
#endif

  m_array = malloc(maxline*maxcol*sizeof(char));
  if (m_array == NULL)
    return 0;
  for (i=0; i<maxcol*maxline; i++)
    m_array[i]=' ';
  rewind(f);
  col=0; line=0;
  while ( (c=fgetc(f)) != EOF) {
    switch (c) {
    case ' ':
      col++;
      break;
    case '\n':
      line++;
      col=0;
      break;
    default:
      m_array[line*maxcol+col]=c;
      col++;
    }
  }
#ifdef DEBUG
  for (i=0; i<maxcol*maxline; i++)
    printf("%c",m_array[i]);
#endif
  return 1;
}

int
main (int argc, char *argv[]) {
  int solutions=0;
  int flag,i,nr=0;
  int steps[100];
  int cursors[100];
  int possible_steps[6];
  char * dirs[] = {"", "up   ", "right", "down ", "left "};
  char * word;

  if (argc < 2) {
    printf("Count the words in a character matrix\n");
    printf("  usage: %s word matrixfile\n",argv[0]);
    return -1;
  }
  if (! file_load(argv[2])) {
    printf("ERROR: file_load\n");
    return -1;
  }
  possible_steps[0] = 0;
  possible_steps[1] = -maxcol;  /* up */
  possible_steps[2] = 1;        /* right */
  possible_steps[3] = maxcol;   /* down */
  possible_steps[4] = -1;       /* left */
  word= argv[1];
  for (i=0; i<10; i++)
    steps[i]=0;

  for (cursors[0]=0; cursors[0]<maxline*maxcol; cursors[0]++) {
    if (word[0] != m_array[cursors[0]]) /* check the first letter */
      continue;
#ifdef DEBUG
    printf("  cursors[%d] = %d\n", nr, cursors[0]);
#endif
    nr = 1;
    while (nr) {
      if (++steps[nr]>4) {
	if (nr==strlen(word)) {
	  solutions++;
	  printf("solution%d: start(%d,%d) steps:  ",
		 solutions, cursors[0]%maxcol+1, cursors[0]/maxcol+1);
	  for (i=1; i<strlen(word); i++) 
	    printf("%s ", dirs[steps[i]]);
	  printf("\n");
	}
	steps[nr]=0;  /* step back */
	nr--;
      } else { /* Check the turn and execute it if it is o.k.  */
	cursors[nr]=cursors[nr-1]+possible_steps[steps[nr]];
#ifdef DEBUG
	printf("  cursors[%d] = %d\n", nr, cursors[nr]);
#endif
	while (1) {   /* dummy while, needed for breaking */
	  /* rule: new cursor have to be inside m_array */
	  if ((cursors[nr] >= maxline*maxcol) && (cursors[nr] < 0))
	    break;
	  /* rule: letter must match */
	  if (m_array[cursors[nr]] != word[nr])
	    break;
	  /* rule: disallow wrap arounds of lines
	     walking left to columnr 0 would be an error */
	  if (cursors[nr]%maxcol==0 && steps[nr]==2) 
	    break;
	  /* rule: disallow wrap arounds of lines
	     walking right to end of previous line would be an error */
	  if (cursors[nr]%maxcol==maxcol-1 && steps[nr]==4) 
	    break;
	  /* rule: each letter can only be used once.
	     disallow dublicate use */
	  flag=0;   
	  for (i=nr-1; i>=0; i--)
	    if (cursors[nr] == cursors[i])
	      flag=1;
	  if (flag)
	    break;
	  nr++;  /* walk forward */
	  break;
	}
      }
    }
  }
  return 0;
}