/* CSE303, Fall 2005, Homework 3, Problem 2 */
/* You need to modify this file as described in the assignment */

/* A simple word-find program */
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// global variable to hold argv[0]; used in error messages.
char * progname;

// functions for printing errors and exiting.
void usage() {
  fprintf(stderr,"usage: %s grid-height grid-width grid-file\n",progname);
  exit(1);
}
void bad_grid() {
  fprintf(stderr,"%s: grid is too small\n",progname);
  exit(1);
}
void bad_word() {
  fprintf(stderr,"%s: bad word (maybe too big for grid)\n",progname);
  exit(1);
}

// Read the file to create the grid.
// Change this function to assume the file has spaces and blank lines.
// For the extra credit, change this function and its type.
char ** make_grid(int height,int width,FILE * file) {
  char ** ans = (char**)malloc(height*sizeof(char*));
  int i;
  for(i=0; i < height; ++i)
    ans[i] = (char*)malloc(width*sizeof(char));
  char * input_buffer = (char*)malloc((width+2)*sizeof(char));
  int    lines_read   = 0;
  for(; lines_read < height; ++lines_read) {
    if(!fgets(input_buffer,width+2,file))
      bad_grid();
    if(strlen(input_buffer) < width+1) // +1 because of \n
      bad_grid();
    strncpy(ans[lines_read],input_buffer,width); // do not copy the \n
  }
  free(input_buffer);
  return ans;
}

// Read one word from stdin; return a new string holding it.
// Exit on a blank line.
// No change necessary.
char * read_word(int max_size) {
  char * ans = (char*)malloc((max_size+2)*sizeof(char));
  if(!fgets(ans,max_size+2,stdin))
    bad_word();
  if(strlen(ans)==1)
    exit(0);
  if(strlen(ans)==max_size+1 && ans[max_size] != '\n')
    bad_word();
  return ans;
}

// Look for a word in the grid and print the result.
// Change this function to look for diagonals.
// Change this function to print where the word is found and the direction.
// Note: better style would be separating the I/O into another function.
// Note: could be made much faster by optimizing when first letter is wrong.
void find_word(int height, int width, char ** grid, char * word) {
  int steps[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
  int word_length = strlen(word)-1; // -1 because of \n
  int row_start, col_start, step_index, word_index;
  for(row_start=0; row_start < height; ++row_start)
    for(col_start=0; col_start < width; ++col_start)
      for(step_index=0; step_index < 4; ++step_index) {
	for(word_index=0; word_index < word_length; ++word_index) {
	  int row = row_start + word_index*steps[step_index][0];
	  int col = col_start + word_index*steps[step_index][1];
	  if(row < 0 || row >= height || col < 0 || col >= width)
	    break;
	  if(grid[row][col] != word[word_index])
	    break;
	}
	if(word_index==word_length) {
	  // success
	  fprintf(stdout,"found\n");
	  return;
	}
      }
  fprintf(stdout,"not found\n");
}

// Process command-line arguments and enter word-find loop.
// No change necessary.
int main(int argc, char ** argv) {
  progname = argv[0];
  if(argc != 4)
    usage();
  int    height = atoi(argv[1]);
  int    width  = atoi(argv[2]);
  FILE * file   = fopen(argv[3],"r");
  if(height <= 0 || width <= 0 || !file)
    usage();
  char ** grid = make_grid(height,width,file);
  while(1) {
    fprintf(stdout,"enter word to find (enter to quit):\n");
    int max_size = (height > width) ? height : width;
    char * word = read_word(max_size);
    find_word(height,width,grid,word);
    free(word);
  }
  return 0;
}