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

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

enum directions { VERT = 1, HORZ = 2 };

/* Generated by Andrew's partition.c file
 * Is a bitmap of all allowable digits
 * Usage whitelist[length][sum - 1]
 */
int whitelist[10][45] = {
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 3, 5, 15, 27, 63, 119, 255, 495, 510, 476, 504, 432, 480, 320, 384, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 7, 11, 31, 63, 127, 255, 511, 511, 511, 511, 511, 511, 511, 510, 508, 504, 496, 416, 448, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 23, 63, 127, 255, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 510, 508, 504, 464, 480, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 47, 127, 255, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 510, 508, 488, 496, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 63, 95, 255, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 510, 500, 504, 0, 0, 0, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 191, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 511, 506, 508, 0, 0, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 383, 447, 479, 495, 503, 507, 509, 510, 0,   },
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 511,   },
};

/* Solve puzzle, returns 1 on success, 0 on failure, -1 on multi-solutions*/
int solve_puzzle(Puzzle *puzzle) {
  int i, j;
  int found = 0;
  struct cell *list = calloc(puzzle->width * puzzle->height, sizeof *list);
  struct cell *new = NULL;
  if(list == NULL)
    return 0;

 /* Step one: convert puzzle format */
  for(i = 0; i < puzzle->height; ++i) {
    for(j = 0; j < puzzle->width; ++j) {
      new = &list[i * puzzle->width + j];
      new->whitelist = 511;
      if(i > 0) {
        new->up = -puzzle->width;
        (new - puzzle->width)->down = puzzle->width;
      }
      if(j > 0) {
        new->left = -1;
        (new - 1)->right = 1;
      }
      if(puzzle->data[i][j] == 0) {
        int x = 1, y = 1;
        new->b_black = 1;
        new->whitelist = 0;
        while(j + x < puzzle->width && puzzle->data[i][j + x]) {
          new->right_sum += puzzle->data[i][j + x];
          ++new->right_len;
          ++x;
        }
        while(i + y < puzzle->height && puzzle->data[i + y][j]) {
          new->down_sum += puzzle->data[i + y][j];
          ++new->down_len;
          ++y;
        }
      }
    }
  }
 /* Step two: whitelist every cell */
  for(i = 0; i < puzzle->height * puzzle->width; ++i) {
    struct cell *current;
    if(list[i].b_black) {
      current = &list[i];
      while(current->right && !(current + current->right)->b_black) {
        current += current->right;
        current->whitelist &= whitelist[list[i].right_len][list[i].right_sum - 1];
      }
      current = &list[i];
      while(current->down && !(current + current->down)->b_black) {
        current += current->down;
        current->whitelist &= whitelist[list[i].down_len][list[i].down_sum - 1];
      }
    }
  }
 /* Step three: set determinate values */
  for(i = 0; i < puzzle->height * puzzle->width; ++i) {
    if(IS_PWR_TWO(list[i].whitelist)) {
      list[i].value = 1;
      while(list[i].whitelist >>= 1)
        ++list[i].value;

      found += block_value(&list[i], HORZ | VERT);
    }
  }

 /* Step four: drop to recursive stage */
  if(found > (puzzle->height * puzzle->width / 8)) {
    found = recursive_solve(list, puzzle->height * puzzle->width, puzzle->width);
  } else
    found = 0;

 /* Free memory */
  free(list);
  return found;
}

int recursive_solve(struct cell list[], int length, int start) {
  static int depth = 0;
  static unsigned long n_calls = 0;
  static int num_solutions = 0;
  static time_t start_time;
  struct cell *new_list = NULL;
  int i, j;

  assert(list != NULL);
  assert(length > 0);

  if(depth == 0)
    num_solutions = 0;
  else if(num_solutions > 1) 
    return 2;

 /* Check puzzle validity */
  for(i = 1; i < length; ++i) {
    if(list[i].b_black) {
      if(list[i].down_len && list[i].right &&
         list[i].down_len == list[i + 1].down_len &&
         list[i].down_sum == list[i + 1].down_sum) {
        num_solutions = 2;
        return 2;
      }
      if(list[i].right_len && list[i].down &&
         list[i].right_len == list[i + list[i].down].right_len &&
         list[i].right_sum == list[i + list[i].down].right_sum) {
        num_solutions = 2;
        return 2;
      }
    } else {
      if(list[i].whitelist == 0 && list[i].value == 0)
        return 0;
    }
  }

  ++depth;
  if(n_calls == 0)
    start_time = time(NULL);
  ++n_calls;
 /* Recurse on all possiblities for next non-determinate value */
  for(i = start; i < length && !list[i].whitelist; ++i)
    ;
  if(i < length) {
    new_list = malloc(length * sizeof *list);
    if(new_list == NULL) {
      fputs("WARN: Falling down the rabbit hole!\n", stderr);
      return 0;
    }
    for(j = 0; list[i].whitelist >= (1 << j); ++j) {
      if(list[i].whitelist & (1 << j)) {
        memcpy(new_list, list, length * sizeof *list);
        new_list[i].whitelist = 0;
        new_list[i].value = j + 1;
        if(block_value(&new_list[i], HORZ | VERT) && recursive_solve(new_list, length, i + 1))
          ++num_solutions;
        else
          list[i].whitelist &= ~(1 << j);
      }
    }
    free(new_list);
  }

  --depth;
  /* Check for success */
  if(depth == 0) {
    if(num_solutions == 1)
      printf("%lu calls.\n", n_calls);
    return num_solutions;
  }
  else {
    for(i = 0; i < length; ++i)
      if(list[i].b_black && (list[i].right_sum || list[i].down_sum))
        return 0;
    return 1;
  }
}


/* Update whitelist of all cells in same row and col as current cell,
 * recursively setting any that work out to be a determinate value.
 */
int block_value(struct cell *cell, int direction) {
  static int n_calls;
  struct cell *current, *horz_heading, *vert_heading;
  int count = 1;

  assert(cell != NULL);
  assert(!cell->b_black);
  assert(cell->value < 10);
  assert(cell->value > 0);

  horz_heading = vert_heading = cell;

  ++n_calls;

  while(!horz_heading->b_black)
    horz_heading += horz_heading->left;
  while(!vert_heading->b_black)
    vert_heading += vert_heading->up;
  horz_heading->right_sum -= cell->value;
  vert_heading->down_sum  -= cell->value;
  --(horz_heading->right_len);
  --(vert_heading->down_len);

  if(direction & HORZ) {
    current = horz_heading;
    while(current->right && !(current + current->right)->b_black) {
      current += current->right;
      current->whitelist &= whitelist[horz_heading->right_len][horz_heading->right_sum - 1] & ~(1 << (cell->value - 1));
      if(!current->value && current->whitelist == 0)
        return 0;
      if(IS_PWR_TWO(current->whitelist)) {
        current->value = 1;
        while(current->whitelist >>= 1)
          ++(current->value);
        count += block_value(current, VERT);
      }
    }
  }
  if(direction & VERT) {
    current = vert_heading;
    while(current->down && !(current + current->down)->b_black) {
      current += current->down;
      current->whitelist &= whitelist[vert_heading->down_len][vert_heading->down_sum - 1] & ~(1 << (cell->value - 1));
      if(!current->value && current->whitelist == 0)
        return 0;
      if(IS_PWR_TWO(current->whitelist)) {
        current->value = 1;
        while(current->whitelist >>= 1)
          ++(current->value);
        count += block_value(current, HORZ);
      }
    }
  }
  return count;
}