/****************************************************
 * Title: Solving Puzzle 2
 * Author: Osami Yamamoto (osami@meijo-u.ac.jp)
 * Date: Sat Jan 25 08:25:41 JST 2014
 ****************************************************/

/*
 * Suppose that there is a board on which five balls are
 * initially located randomly, where three of them are
 * labeled 'R' and other two balls are labeled 'B'.
 * For instance, the configuration is like
 *  +---+
 *  |BRB|
 *  |RR |
 *  +---+
 * You can move a ball to the empty place in one step, and, 
 * only a ball which faces to the empty place or a ball which
 * can reach the empty place by flying across one ball which
 * is labeled differently can move to the empty place.  Find
 * a sequence of moves from the initial configuration to the
 * following goal configuration with the minimal number of steps:
 *  +---+
 *  |B R|
 *  |BRR|
 *  +---+
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRIVATE static
#define PUBLIC 

struct config{
  char a[7];
  struct config *parent;
  int action_from;
  int action_to;
};
typedef struct config config;
enum {MAX_QUEUE_LEN = 500};
enum {MAX_TT_LEN = 500};

PRIVATE config **queue;
PRIVATE int head, tail, ttsize; 
PRIVATE void newline(){putchar('\n');}
PRIVATE config **t_table;
PRIVATE int n_mk_config;

/*----------------------------------------*
 config *mk_config(char *c, config *parent)
 *----------------------------------------*/
PRIVATE config *mk_config(const char *c, config *parent){
  int i;
  config *pt = (config *)malloc(sizeof(config));
  for (i = 0; i < 6; i++) pt->a[i] = c[i];
  pt->a[6] = '\0';
  pt->parent = parent;
  n_mk_config += 1;
  return pt;
} /* mk_config */

/*----------------------------------------*
 void print_config(config *pt)
 *----------------------------------------*/
PRIVATE void print_config(config *pt){
  int i;
  printf("+---+\n");
  for (i = 0; i < 6; i++){
    if (i % 3 == 0) putchar('|'); 
    putchar(pt->a[i]);
    if ((i + 1) % 3 == 0){
      putchar('|');
      newline();
    } /* if */
  } /* for */
  printf("+---+\n");
} /* print_config */

/*----------------------------------------*
 int eq_config(config *pt1, config *pt2)
 *----------------------------------------*/
PRIVATE int eq_config(config *pt1, config *pt2){
  int i;
  for (i = 0; i < 6; i++)
    if (pt1->a[i] != pt2->a[i]) return 0;
  return 1;
} /* eq_config */

/*----------------------------------------*
 int blank_pos(config *pt)
 *----------------------------------------*/
PRIVATE int blank_pos(config *pt){
  int i;
  for (i = 0; i < 6; i++){
    if (pt->a[i] == ' ') return i;
  } /* for */
  return -1;
} /* blank_pos */

/*----------------------------------------*
 void init_queue(void)
 *----------------------------------------*/
PRIVATE void init_queue(void){
  queue = (config **)malloc(sizeof(config *) * MAX_QUEUE_LEN);
  t_table = (config **)malloc(sizeof(config *) * MAX_TT_LEN);
  head = tail = 0;
  ttsize = 0;
  n_mk_config = 0;
} /* init_queue */

/*----------------------------------------*
 void enqueue(config *a)
 *----------------------------------------*/
PRIVATE void enqueue(config *a){
  queue[tail] = a;
  tail = (tail + 1) % MAX_QUEUE_LEN;
} /* enqueue */

/*----------------------------------------*
 config * dequeue(void)
 *----------------------------------------*/
PRIVATE config * dequeue(void){
  config *m = queue[head];
  head = (head + 1) % MAX_QUEUE_LEN;
  return m;
} /* dequeue */

/*----------------------------------------*
 void push_ttt(config *pt){
 *----------------------------------------*/
PRIVATE void push_TT(config *pt){
  t_table[ttsize] = pt;
  ttsize += 1;
} /* push_TT */

/*----------------------------------------*
 int search_TT(config *pt)
 *----------------------------------------*/
PRIVATE int search_TT(config *pt){
  int i;
  for (i = 0; i < ttsize; i++){
    if (eq_config(pt, t_table[i])) return 1;
  } /* for */
  return 0;
} /* search_TT */

/*----------------------------------------*
 void print_action(int n, config **result)
 *----------------------------------------*/
PRIVATE void print_action(int n, config **result){
  int i;
  for (i = n - 1; i >= 1; i--){
    int p0 = result[i - 1]->action_from;
    int p1 = result[i - 1]->action_to;
    int x0 = p0 % 3;
    int y0 = p0 / 3;
    int x1 = p1 % 3;
    int y1 = p1 / 3;
    const char *opt = ".";
    if (abs(p0 - p1) == 2) opt = " jumping over." ;
    printf("%d. Move the ball at (%d, %d) to (%d, %d)%s\n",
	   n - i, x0, y0, x1, y1, opt);
  } /* for */
} /* print_action */

/*----------------------------------------*
 void print_solution(config *pt)
 *----------------------------------------*/
PRIVATE void print_solution(config *pt){
  config *result[30];
  int i, n = 0;
  printf("\n----------------------\nResult::\n");
  while (pt != NULL) {
    result[n] = pt;
    pt = pt->parent;
    n += 1;
  } /* while */
  for (i = n - 1; i >= 0; i--){
    printf("  ");
    printf("+---+");
  } /* for */
  newline();
  for (i = n - 1; i >= 0; i--){
    printf("  ");
    putchar('|');
    putchar(result[i]->a[0]);
    putchar(result[i]->a[1]);
    putchar(result[i]->a[2]);
    putchar('|');
  } /* for */
  newline();
  for (i = n - 1; i >= 0; i--){
    if (i == n - 1) printf("  ");
    else printf("=>");
    putchar('|');
    putchar(result[i]->a[3]);
    putchar(result[i]->a[4]);
    putchar(result[i]->a[5]);
    putchar('|');
  } /* for */
  newline();
  for (i = n - 1; i >= 0; i--){
    printf("  ");
    printf("+---+");
  } /* for */
  newline();
  for (i = n - 1; i >= 0; i--){
    printf("  ");
    printf("%3d  ", n - i - 1);
  } /* for */
  newline();
  print_action(n, &result[0]);
  printf("Transfered in %d step(s).\n", n - 1);
} /* print_solution */


/*----------------------------------------*
 void do_loop(config *final)
 *----------------------------------------*/
PRIVATE void do_loop(config *final){
  while (1){
    config *m;
    int x, y, p;
    if (head == tail) break;
    m = dequeue();
    if (eq_config(m, final)){
      print_solution(m);
      break;
    }
    if (search_TT(m)) continue;
    push_TT(m);
    p = blank_pos(m);
    x = p % 3;
    y = p / 3;
    if (x < 2){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p + 1];
      pt->a[p + 1] = ' ';
      pt->action_from = p + 1;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
    if (x > 0){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p - 1];
      pt->a[p - 1] = ' ';
      pt->action_from = p - 1;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
    if (y > 0){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p - 3];
      pt->a[p - 3] = ' ';
      pt->action_from = p - 3;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
    if (y < 1){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p + 3];
      pt->a[p + 3] = ' ';
      pt->action_from = p + 3;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
    if (x == 0 && m->a[p + 2] != m->a[p + 1]){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p + 2];
      pt->a[p + 2] = ' ';
      pt->action_from = p + 2;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
    if (x == 2 && m->a[p - 2] != m->a[p - 1]){
      config *pt = mk_config(&m->a[0], m);
      pt->a[p] = pt->a[p - 2];
      pt->a[p - 2] = ' ';
      pt->action_from = p - 2;
      pt->action_to = p;
      enqueue(pt);
    } /* if */
  } /* while */
} /* do_loop */

/*----------------------------------------*
 void work(char *init_conf)
 *----------------------------------------*/
PRIVATE void work(char *init_conf){
  config *start = mk_config(init_conf, NULL);
  config *final = mk_config("B RBRR", NULL);
  init_queue();
  enqueue(start);
  do_loop(final);
  printf("number of mk_config = %d\n", n_mk_config);
  printf("length of t_table = %d\n", ttsize);
} /* work */

/*----------------------------------------*
 int main(int ac, char *av[])
 *----------------------------------------*/
/* PUBLIC int main(int ac, char *av[]){ */
int main(){
  char *probs[] = {"BRBRR ", "BRB RR", "RB RRB", "BR RRB", "BB RRR"};
  int i;
  for (i = 0; i < sizeof(probs) / sizeof(char *); i++)
    work(probs[i]);
  return 0;
} /* main */