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

#include "inc/kakuro.h"
#include "inc/solver.h"
#include "inc/puzzle.h"
#include "inc/floodfill.h"

/* Note: this is a pretty biased PRNG; I don't care for puzzle
   generation but there's some issue with distribution in the
   case that RAND_MAX is not an even multiple of 10, I think. 
   So don't use this for important stuff, please! */
#define RAND_NUM_3  ((int) (rand() / (RAND_MAX / 3.0)) + 1)
#define RAND_NUM_10 ((int) (rand() / (RAND_MAX / 9.0)) + 1)
#define RAND_PCNT() ((int) (rand() / (RAND_MAX / 100.0)))

#define RAND_NUM()  (RAND_PCNT() > 60 ? RAND_NUM_3 : (RAND_PCNT() > 90 ? 10 - RAND_NUM_3 : RAND_NUM_10))

/* Allocate and return a puzzle struct */
Puzzle *create_puzzle(unsigned short width, unsigned short height) {
  Puzzle *rv = malloc(sizeof *rv);
  if(rv == NULL)
    return NULL;

  rv->width  = width;
  rv->height = height;
 /* Allocate space for a width-by-height character array in rv->data */
  rv->data = malloc(height * sizeof *rv->data);
  if(rv->data == NULL) {
    free(rv);
    rv = NULL;
  } else {
    int i;
    for(i = 0; i < height; ++i) {
      rv->data[i] = malloc(width * sizeof *rv->data[i]);
     /* Backtrack and free memory in case of calloc failure */
      if(rv->data[i] == NULL) {
        int j;
        for(j = 0; j < i; ++j)
          free(rv->data[j]);
        free(rv->data);
        free(rv);
        rv = NULL;
        break;
      }
    }
  }

  return rv;
}

void destroy_puzzle(Puzzle *puzzle) {
  unsigned short i;
  for(i = 0; i < puzzle->height; ++i)
    free(puzzle->data[i]);
  free(puzzle->data);
  free(puzzle);
}

int generate_puzzle(Puzzle *puzzle) {
  unsigned short i = 0, j = 0, count = 0;
  unsigned short okay = 0;

  while(puzzle->height && !okay) {
    ++count;
    okay = 1;
   /* Randomize */
    for(i = 0; i < puzzle->height; ++i) {
      puzzle->data[i][0] = 0;
      for(j = 1; j < puzzle->width; ++j) {
       /* Try to set black tiles appropriately */
        if(i == 0) {
          puzzle->data[i][j] = 0;
        } else {
          int blacklist = 0, t;
          int y_len = 1, x_len = 1;
          int black = (RAND_PCNT() < 53);  /* testing shows 53 works fast */

          while(puzzle->data[i - y_len][j])
            ++y_len;
          while(puzzle->data[i][j - x_len])
            ++x_len;
         /* Check lengths */
          if(y_len == 2 || x_len == 2)
            black = 0;
          if(y_len == 10 || x_len == 10)
            black = 1;
          if((y_len == 10 || x_len == 10) &&
             (x_len == 2 || y_len == 2))
            okay = 0;
         /* Check right/bottom wall boundaries */
          if(j == puzzle->width - 2 &&
             i > 2 &&
             puzzle->data[i - 2][j + 1] == 0)
            black = 0;
          if(i == puzzle->height - 1 &&
             j < puzzle->width - 2 &&
             puzzle->data[i - 1][j + 2] == 0)
            black = 0;
          if(j == puzzle->width - 1 && puzzle->data[i][j - 1] == 0)
            black = 1;
          if(i == puzzle->height - 1 && puzzle->data[i - 1][j] == 0)
            black = 1;

          blacklist = 0;
          for(t = i - 1; puzzle->data[t][j]; --t)
            blacklist |= (1 << puzzle->data[t][j]);
          for(t = j - 1; puzzle->data[i][t]; --t)
            blacklist |= (1 << puzzle->data[i][t]);
          if((blacklist & 0x03FE) == 0x03FE) {
            puzzle->data[i][j] = 0;
            okay = 0;
          } else {
            do {
              puzzle->data[i][j] = black ? 0 : RAND_NUM();
            } while(blacklist & (1 << puzzle->data[i][j]));
          }
        }
      }
    }
   /* Check for islands using floodfill with -10 */
   /* Find first white square to start floodfill */
    for(i = 1; i < puzzle->height; ++i) {
      for(j = 1; j < puzzle->width; ++j) {
        if(puzzle->data[i][j] > 0)
          goto cont1;
      }
    }
cont1:
    if(i == puzzle->height && j == puzzle->width) {
      /* Puzzle is all black */
      okay = 0;
    } else {
      floodfill(j, i, puzzle->width, puzzle->height, puzzle->data);
    }
   /* Scan puzzle, removing -10's and confirming puzzle integrity */
    for(i = 1; okay && i < puzzle->height; ++i) {
      for(j = 1; okay && j < puzzle->width; ++j) {
        if(puzzle->data[i][j] > 0)
          okay = 0;
        else if(puzzle->data[i][j] < 0)
          puzzle->data[i][j] += 10;
      }
    }
    if(okay && solve_puzzle(puzzle) != 1) {
      okay = 0;
    }
  }

  printf("<h3>Done generation; did %d regens.</h3>\n", count);
  return 1;
}

/* Render a puzzle all HTML-like */
int draw_puzzle(Puzzle *puzzle) {
  int i, j;
  puts("<table class=\"kakuro\">");
  for(i = 0; i < puzzle->height; ++i) {
    puts("  <tr>");
    for(j = 0; j < puzzle->width; ++j) {
      if(puzzle->data[i][j]) {
        puts("    <td> </td>");
      } else {
       /* Or, calculate horz/vert sums and display those */
        int h_sum = 0, v_sum = 0, x, y;
        for(x = j + 1; x < puzzle->width && puzzle->data[i][x]; ++x)
          h_sum += puzzle->data[i][x];
        for(y = i + 1; y < puzzle->height && puzzle->data[y][j]; ++y)
          v_sum += puzzle->data[y][j];
       /* Don't display zeroes */
        if(v_sum)
          printf("    <th><h4>%d</h4>\n", v_sum);
        else
          printf("    <th><h4></h4>\n");
        if(h_sum)
          printf("<h5>%d</h5></th>\n", h_sum);
        else
          puts("<h5></h5></th>");
      }
    }
    puts("  </tr>");
  }
  puts("</table>");

  return 1;
}