// much of this will look familiar from homework 3, but we do not
// output anything and grid-making is different

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <time.h>
#include "letter_probabilities.h"

#include "grid_utilities.h"

// p is a probability, a number in the range [0,1)
static char get_weighted_letter(double p) {
  // CHANGE THIS DEFINITION (this is clearly not right)
  // hint: 'a'+i with get you the i+1'th letter of the alphabet
  return 'a';
}

// DO NOT CHANGE ANYTHING BELOW HERE

char ** make_grid(int gridsize) {
  char ** ans = (char**)malloc(gridsize*sizeof(char*));
  int i,j;
  static int first_grid = 1;
  if(first_grid) {
    srand48(time(NULL)); // seed random-number-generator based on seconds
    first_grid=0;
  }
  for(i=0; i < gridsize; ++i) {
    ans[i] = (char*)malloc(gridsize*sizeof(char));
    for(j=0; j < gridsize; ++j)
      ans[i][j] = get_weighted_letter(drand48());
  }
  return ans;
}

// helper for find_whole_word
static int find_word (int grid_size, char ** grid, char * word, 
	       int * seen_row, int * seen_col,
	       int word_index, int curr_row, int curr_col) {
  int i;

  if(!word[word_index]) // hit nul-terminator of string: success
    return 1;
 
  if(curr_row < 0 || curr_row >= grid_size // fell off the grid
     || curr_col < 0 || curr_col >= grid_size)
    return 0;

  for(i=0; i < word_index; ++i)  // already been here
    if(seen_row[i]==curr_row && seen_col[i]==curr_col)
      return 0;
   
  if(grid[curr_row][curr_col] != word[word_index]) // no match
    return 0;

  int steps[8][2] = {{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}};
  int step_index = 0;
  
  seen_row[word_index]=curr_row;
  seen_col[word_index]=curr_col;
  for(; step_index < 8; ++step_index) {
    if(find_word(grid_size,grid,word,seen_row,seen_col,
		 word_index+1,
		 curr_row+steps[step_index][0],
		 curr_col+steps[step_index][1]))
      return 1;
  }

  return 0;
}

// return whether the word is in the grid
int find_whole_word(int grid_size, char ** grid, char * word) {
  int start_row;
  int start_col;
  int * seen_row = (int*)malloc(grid_size*grid_size*sizeof(int));
  int * seen_col = (int*)malloc(grid_size*grid_size*sizeof(int));
  for(start_row=0; start_row < grid_size; ++start_row)
    for(start_col=0; start_col < grid_size; ++start_col)
      if(find_word(grid_size,grid,word,seen_row,seen_col,
		   0,start_row,start_col)) {
	free(seen_row);
	free(seen_col);
	return 1;
      }
  free(seen_row);
  free(seen_col);
  return 0;
}

void print_grid(int grid_size, char ** grid) {
  int i,j;
  for(i=0; i<grid_size; ++i) {
    for(j=0; j<grid_size; ++j)
      fputc(grid[i][j],stdout);
    fputc('\n',stdout);
  }
}

void free_grid(int grid_size, char ** grid) {
  int i;
  for(i=0; i < grid_size; ++i)
    free(grid[i]);
  free(grid);
}