// When given bad input, e.g. non-contiguous blocks of the same letter,
// behaviour is unpredictable (for example the split block disappears)
// This should be checked for and an error output.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h> // sleep()
#include <ctype.h>  // isprint()
#include <error.h>
#include <errno.h>

#ifndef TRUE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif

//#define MONITOR TRUE

#define UP 0
#define LEFT 0
#define DOWN 1
#define RIGHT 1

#define NUM_ROWS 6
#define NUM_COLS 6

#ifdef DBMAIN
#define NUM_GAMES (1U)

// Still a problem with the solver: THIS "bggAHXXCbHLCkegCxxLdFLhFCFDFHlllhhaGEhhXXGX"
// takes way too many steps - there's a point where the block in the rightmost column
// could have been moved upwards and it would be done, but instead a lot of redundant
// moves are made to evacuate it downwards, ending up by taking a total of 34 moves.

// Oh - its one of those ones where a block wraps :-(  I thought I had fixed that :-(

static const char *puzzle =
  ".C.BBJ" // <-- JJ is bad
  "JCKKEE"
  "XXXH.."
  "ILLH.."
  "I.DAAG"
  "FFD..G"; // soln: " bggAHXXCbHLCkegCxxLdFLhFCFDFHlllhhaGEhhXXGX";

//"DD..EE"
//".JJ..F"
//"BGXXXF"
//"BG.KAA"
//"BIIK.."
//"HHCCC.";

#endif

/*
  A sequences of moves is recorded as so:
  * 1-space move only.  More than one space
    will be recorded as multiple 1-space moves.
  * because each block can only move in one axis,
    the move is recorded as the upper case letter
    for a positive move and a lower case letter
    for a negative move.  (Positive and negative
    being in relation to the coordinate system used)
  * A history is kept and the new position is not
    added to the queue if it has been seen before.
  * the history of how we got to this state is
    always valid and back-tracking is done simply
    by removing the last character from the 'history'
    string.
  * current state is represented by a 36-character
    string.
 */

// The most positions recorded for all the above games was 28785 ...
#define MAX_POSITIONS  65536 /* Use 32768 if that's too much RAM for you */
#define MAX_MOVES 128 /* TEMP ONLY!!! */
#define BOARD_SIZE (NUM_ROWS*NUM_COLS + MAX_MOVES + 1 + 1) // Unless we add move history to each queued board! */
static int next_free_seen_position = 0;
static char seen[MAX_POSITIONS][BOARD_SIZE];

static int queue_put = 0, queue_get = MAX_POSITIONS-1;
static char queue[MAX_POSITIONS][BOARD_SIZE];

#ifdef DBMAIN

static int screen[37][19];

static void draw_block(char *p, int ox, int oy, int horizontal, int block) {
  int i,j, x,y, w,h;
  // always at least 2, sometimes 3
  x = ox*6; y = oy*3;
  if (p[oy*6+ox] != block) {
    fprintf(stderr, "p[%d][%d] = %c, block = %c\n", ox, oy, p[oy*6+ox], block);
  }
  if (horizontal) {
    h = 3; w = 12;                                // GG
    if ((ox < 4) && (p[oy*6+ox+2] == block)) w = 18; // GGG
  } else {
    h = 6; w = 6;
    if ((oy < 4) && (p[(oy+2)*6+ox] == block)) h = 9;
  }
  for (j = y+1; j < y+h; j++) {
    for (i = x+1; i < x+w; i++) {
      screen[i][j] = (isprint(block) ? block : '?');
    }
  }
}
#endif

static int One_Step(char *p, int c, int dir) {
  int i, j, success;
  success = FALSE;
  if (c != '.') for (j = 0; j < 6; j++) {   // top to bottom
    for (i = 0; i < 6; i++) { // left to right
      if (p[j*6+i] == c) { // first one it hits, topmost or leftmost
        
        if ((i < 4) && (p[j*6+i+2] == c)) {
          // left of horizontal triple
          //fprintf(stderr, "[3] left/right\n");
          if ((dir==LEFT) && (i > 0) && (p[j*6+i-1] == '.')) {
            // horizontal triple move left
            //fprintf(stderr, "[3] left\n");
            p[j*6+i-1] = c; p[j*6+i+2] = '.';
            success = TRUE;
          } else if ((dir==RIGHT) && (i < 3) && (p[j*6+i+3] == '.')) {
            // horizontal triple move right
            //fprintf(stderr, "[3] right\n");
            p[j*6+i+3] = c; p[j*6+i] = '.';
            success = TRUE;
          }
        } else if ((i < 5) && (p[j*6+i+1] == c)) {
          // left of horizontal pair
          //fprintf(stderr, "[2] left/right\n");
          if ((dir==LEFT) && (i > 0) && (p[j*6+i-1] == '.')) {
            // horizontal pair move left
            //fprintf(stderr, "[2] left\n");
            p[j*6+i-1] = c; p[j*6+i+1] = '.';
            success = TRUE;
          } else if ((dir==RIGHT) && (i < 4) && (p[j*6+i+2] == '.')) {
            // horizontal pair move right
            //fprintf(stderr, "[2] right\n");
            p[j*6+i+2] = c; p[j*6+i] = '.';
            success = TRUE;
          }
        }

        if ((j < 4) && (p[(j+2)*6+i] == c)) {
          // top of vertical triple
          //fprintf(stderr, "[3] up/down\n");
          if ((dir==UP) && (j > 0) && (p[(j-1)*6+i] == '.')) {
            // vertical triple move up
            p[(j-1)*6+i] = c; p[(j+2)*6+i] = '.';
            //fprintf(stderr, "[3] up\n");
            success = TRUE;
          } else if ((dir==DOWN) && (j < 3) && (p[(j+3)*6+i] == '.')) {
            // vertical triple down
            p[(j+3)*6+i] = c; p[j*6+i] = '.'; 
            //fprintf(stderr, "[3] down\n");
            success = TRUE;
         }
        } else if ((j < 5) && (p[(j+1)*6+i] == c)) {
          // top of vertical pair
          //fprintf(stderr, "[2] up/down\n");
          if ((dir==UP) && (j > 0) && (p[(j-1)*6+i] == '.')) {
            // vertical pair move up
            p[(j-1)*6+i] = c; p[(j+1)*6+i] = '.';
            //fprintf(stderr, "[2] up\n");
            success = TRUE;
          } else if ((dir==DOWN) && (j < 4) && (p[(j+2)*6+i] == '.')) {
            // vertical pair down
            p[(j+2)*6+i] = c; p[j*6+i] = '.';
            //fprintf(stderr, "[2] down\n");
            success = TRUE;
          }
        }

        return success;
      }
    }
  }
  return success;
}

#ifdef DBMAIN
static void draw_screen(char *p) {
  int i,j;
  char block;

  for (j = 0; j < 18+1; j++) {
    for (i = 0; i < 36+1; i++) {
      if (j%3 == 0) {
        // +-----+------
        if (i%6 == 0) {
          screen[i][j] = '+';
        } else {
          screen[i][j] = '-';
        }
      } else {
        // |     |     |
        if (i%6 == 0) {
          screen[i][j] = ((j/3 == 2) && (i == 6*6) ? ' ' : '|');
        } else {
          screen[i][j] = ' ';
        }
      }
    }
  }
  for (j = 0; j < 6; j++) {   // top to bottom
    for (i = 0; i < 6; i++) { // left to right
      block = p[j*6+i];
      if (block == '.') continue;
      if ((i > 0) && (p[j*6+i-1] == block)) {
        // horizontal block handled already
      } else if ((i < 5) && (p[j*6+i+1] == block)) {
        // horizontal block
        draw_block(p, i,j, TRUE, block);
      } else if ((j > 0) && (p[(j-1)*6+i] == block)) {
        // vertical block handled already
      } else if ((j < 5) && (p[(j+1)*6+i] == block)) {
        // vertical block
        draw_block(p, i,j, FALSE, block);
      } else {
        // error
      }
    }
  }

  //for (i = 0; i < 6*6; i++) {
  //  fputc(p[i], stdout);
  //  if (i%6 == 5) fputc('\n', stdout);
  //}

  for (j = 0; j < 18+1; j++) {
    for (i = 0; i < 36+1; i++) {
      if (isprint(screen[i][j])) {
        fputc(screen[i][j], stdout);
      } else {
        fputc('!', stdout);
      }
    }
    fputc('\n', stdout);
  }
}
#endif

static int longest_sequence = 0;
static void enqueue(char *p, char code) {
  int len;
  len = strlen(p);
  if (len > longest_sequence) longest_sequence = len;
  if (len >= NUM_ROWS*NUM_COLS + MAX_MOVES) {
    fprintf(stderr, "Too many moves to store in queued string: \"%s\" + '%c'\n\n", p, code);
    exit(EXIT_FAILURE);
  }
  strcpy(queue[queue_put], p);
  queue[queue_put][len] = code; len += 1; queue[queue_put][len] = '\0'; // Save the last move along with the updated board state
  queue_put = (queue_put+1) % MAX_POSITIONS;
  if (queue_put == queue_get) {
    fprintf(stderr, "Queue full!  put/get = %d\n", queue_put);
    exit(EXIT_FAILURE);
  }
#ifdef MONITOR
  printf("\nTrying: (put=%d get=%d) %d positions seen.\n", queue_put, queue_get, next_free_seen_position);
  draw_screen(p);
#endif
}


static int dequeue(char *p) {
  queue_get = (queue_get+1) % MAX_POSITIONS;
  if (queue_get == queue_put) {
    return FALSE;
  }
  strcpy(p, queue[queue_get]);
  return TRUE;
}

static int Seen(char *p) {
  int i;
  strcpy(seen[next_free_seen_position], p);
  for (i = 0; i <= next_free_seen_position; i++) {
    if (strncmp(seen[i], p, NUM_ROWS*NUM_COLS)==0) break; // compare layout but not how we got here.
  }
  if (i == next_free_seen_position) {
    next_free_seen_position++;
    return FALSE; // not previously seen, so add it...
  } else {
    return TRUE;
  }
}

static inline int solved(char *p) {
  return ((p[2*6+4] == 'X') && (p[2*6+5] == 'X'));
}

static int solve(char *p) {
  int block, code, dir;
  char saved[BOARD_SIZE];
  strcpy(saved, p);
  
  if (One_Step(p, 'X', 0)) {
    if (solved(p)) {
      int len = strlen(p);
      p[len] = 'x'; len += 1; p[len] = '\0'; // Save the final move along with the updated board state
      return TRUE;
    } else if (!Seen(p)) {
      enqueue(p, 'x');
    }
  }

  strcpy(p, saved);
  if (One_Step(p, 'X', 1)) {
    if (solved(p)) {
      int len = strlen(p);
      p[len] = 'X'; len += 1; p[len] = '\0'; // Save the final move along with the updated board state
      return TRUE;
    } else if (!Seen(p)) {
      enqueue(p, 'X');
    }
  }

  for (dir = 0; dir <= 1; dir++) { // 0: UP,LEFT  1: DOWN,RIGHT
    for (block = 'A'; block <= 'X'; block++) {
      strcpy(p, saved);
      code = block; if (dir == 0) code = tolower(code);
      if (One_Step(p, block, dir)) {
        if (solved(p)) {
          int len = strlen(p);
          p[len] = code; len += 1; p[len] = '\0'; // Save the final move along with the updated board state
          return TRUE;
        } else if (!Seen(p)) {
          enqueue(p, code);
        }
      }
    }
  }
  return FALSE;
}

#ifdef DBMAIN
static void show_results(char *orig, char *moves) {
  int block, dir;
  for (;;) {
    if (*moves == '\0') {
      printf("\nSolution:\n");
      draw_screen(orig);
      return;
    }
    printf("\nBefore applying %c:\n", *moves);
    draw_screen(orig); sleep(1);
    block = *moves++;
    if (block == '\0') break;
    dir = 1;
    if (islower(block)) {
      dir = 0;
      block = toupper(block);
    }
    One_Step(orig, block, dir);
  }
#ifdef MONITOR
  sleep(10);
#endif
}
#endif

int reduce_steps(char *s) {
  int steps = 0, last = 0;
  while (*s != '\0') {
    if (*s != last) steps++;
    last = *s++;
  }
  return steps-1; // subtract X's at end of string.
}

int solvable(char *p, int *steps) {  // If p is solved, it should be updated with the final solution and the path to get there.

  next_free_seen_position = 0;
  queue_put = 0;
  queue_get = MAX_POSITIONS-1;
  longest_sequence = 0;
  
  enqueue(p, ' ');
  while (dequeue(p)) {
    if (solve(p)) {
      *steps = reduce_steps(&p[NUM_ROWS*NUM_COLS+1]);
      return TRUE;
    }
  }
  return FALSE;
}

#ifdef DBMAIN
int main(int argc, char **argv) {
  int steps;
  char p[BOARD_SIZE];

  next_free_seen_position = 0;
  queue_put = 0;
  queue_get = MAX_POSITIONS-1;


  printf("\n\nGame: %s\n\n\n", puzzle);
  strcpy(p, puzzle);
  draw_screen(p);
  if (solvable(p, &steps)) {
    char orig[BOARD_SIZE];
    printf("Solution found!   %d positions evaluated.\n", next_free_seen_position);
    printf("                  Moves: %s\n", &p[NUM_ROWS*NUM_COLS+1]);
    strcpy(orig, puzzle); // ram copy modified by show_results
    show_results(p, &p[NUM_ROWS*NUM_COLS+1]);
  }

  return 0;
}
#endif