//#define VERBOSE
/*
 * This program is in the public domain.
 *
 * Brute-force solving the puzzle described in curses.c; in particular,
 *  this finds a shortest (in terms of number of movse) solution.
 */

/*
 * State consists of nine bits giving the player avatar pattern, five
 *  bits giving the player avatar X location, five more giving its Y
 *  location, and nine bits giving which reduce cells still exist.
 *  (There is redundancy here.  The number of avatar bits set always
 *  equals the number of reduce bits set; and many
 *  <avatar-locations,avatar-pattern> pairs are impossible.  We do this
 *  for the sake of code convenience.)
 *
 * This means we want 9+5+5+9 = 28 bits.  This fits comfortably in an
 *  unsigned int...but leaves only four bits for depth, and solution
 *  takes well over 16 moves.  So we use a struct.
 *
 * We operate in a 29x29 grid, most of which is solid walls and thus
 *  isn't interesting.
 */

/*
 * The solid-wall pattern, as 29 values each 29 bits long.  The
 *  bitmasks after it look reversed because we store lower X
 *  coordinates in lower bits, but the usual way of writing binary puts
 *  higher bits further to the left.  This diagram also has some
 *  relevant locations marked with letters (all these are empty space
 *  in the bitmasks): p for the initial player avatar centre, e for the
 *  avatar echo centres, r for the reduce cell locations, and g for the
 *  goal cell.
 *
 *                          1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
 *  y\x 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
 *  0   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 *  1   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 *  2   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 *  3   # # # # # # # # # # . r # # # # # # # # # # # # # # # # #
 *  4   # # # # # # # # # # . . . # # # # # # # # # # # # # # # #
 *  5   # # # # # # # # # . . . . # # # # # # # # # # # # # # # #
 *  6   # # # # # . . . . . . . . . . # # # # # # # # # # # # # #
 *  7   # # # # # r . . . . . . . . . . . . . . # # # # # # # # #
 *  8   # # # # # # # # . . . r . . . # # . # . # # # # # # # # #
 *  9   # # # # # # # # . . . . . . . . . . . . # # . . . # # # #
 * 10   # # # # # # # r . . . . . . . # # . # . # # . g . # # # #
 * 11   # # # r # # # # # # . . . # # # # . # . # # . . . # # # #
 * 12   # # # . # # # # # # . p . # # # # . . . # # # # # # # # #
 * 13   # # # . # . # # # # . . . # # # # . . . # # # # # # # # #
 * 14   # # # . # . # # # # # # # # # . . . . . . . . . . . # # #
 * 15   # # # . . . . . # # # # # # # . . . . . . e . . r . # # #
 * 16   # # # . . . . . . . . . . . # . . . . . . . . . . . # # #
 * 17   # # # . . . . . . . . . . . . . . # # # . . . # # # # # #
 * 18   # # # # # # # # # # . # # # # # # # # # . . . # # # # # #
 * 19   # # # # . . . # # # . # # # # # # # # # . . . # # # # # #
 * 20   # # # # . r . # # # . # # # # # # # # # # # # # # # # # #
 * 21   # # # # . . . # # . . . . . . # . . . # # # # # # # # # #
 * 22   # # # # # . # # # . . . . . . # . r . # # . . . # # # # #
 * 23   # # # # # . . . # . . . . . . # . . . # # . r . # # # # #
 * 24   # # # # # . e . . . . . . # # # # # # . # . . . # # # # #
 * 25   # # # # # . . . . . . . # # # # # # # # # # # # # # # # #
 * 26   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 * 27   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 * 28   # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
 *
 * For code convenience, player avatar location and echo locations are
 *  stored as the upper left (lowest x and y) coordinates of the 3x3
 *  rectangle, not its centre.
 */
#include <avl.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct xy XY;

struct xy {
  char x;
  char y;
  } ;

#define XSIZE 29
#define YSIZE 29
#define NREDUCE 9
#define NECHO 2
static const unsigned int walls[YSIZE]
 = { 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1ffff3ff, 0x1fffe3ff,
     0x1fffe1ff, 0x1fff801f, 0x1ff0001f, 0x1ff580ff, 0x1e3000ff,
     0x1e35807f, 0x1e35e3f7, 0x1ff1e3f7, 0x1ff1e3d7, 0x1c007fd7,
     0x1c007f07, 0x1c004007, 0x1f8e0007, 0x1f8ffbff, 0x1f8ffb8f,
     0x1ffffb8f, 0x1ff8818f, 0x1f1881df, 0x1f18811f, 0x1f17e01f,
     0x1ffff01f, 0x1fffffff, 0x1fffffff, 0x1fffffff };
#define WALLS(x,y) ((walls[(y)] >> (x)) & 1)
// The code assumes reduce[] is sorted by Y value
// The code assumes there is at most one reduce per Y value
// The code assumes a move hits at most one reduce cell
static const XY reduce[NREDUCE+1]
 = { { 11, 3 },
     { 5, 7 },
     { 11, 8 },
     { 7, 10 },
     { 3, 11 },
     { 24, 15 },
     { 5, 20 },
     { 17, 22 },
     { 22, 23 },
     { 99, 99 } };
static signed char reduce_inx[XSIZE][YSIZE];
static const XY echo[NECHO] = { { 20, 14 }, { 5, 23 } };
static const XY goal = { 23, 10 };
#define DIR_L 0
#define DIR_R 1
#define DIR_U 2
#define DIR_D 3
static const int ddx[4] = { [DIR_L] = -1, [DIR_R] = 1, [DIR_U] = 0, [DIR_D] = 0 };
static const int ddy[4] = { [DIR_L] = 0, [DIR_R] = 0, [DIR_U] = -1, [DIR_D] = 1 };
static const char dchr[4] = { [DIR_L] = 'L', [DIR_R] = 'R', [DIR_U] = 'U', [DIR_D] = 'D' };
static unsigned short int rot[512];
// Subscripted [movedir][oldavatar][wallmask]
// -1 -> move not possible
// other outside 0..511 -> abort
static signed short int new_avatar[4][512][512];
#define INX(x,y) (((y)*3)+(x))

typedef struct state STATE;

struct state {
  const STATE *parent;
  unsigned short int depth;
  unsigned short int avatar;
#define AVATAR(a,x,y) (((a) >> (((y)*3)+(x))) & 1)
  unsigned short int reduce;
  unsigned char x;
  unsigned char y;
  char via;
  } ;

static STATE start;

static AVL *seen;
static AVL *pending;
static int curdepth;
static int depthcount;
static STATE *new = 0;

static void precompute(void)
{
 int i;
 int j;
 int x;
 int y;
 int d;
 short int a;
 short int m;
 int dx;
 int dy;
 int n;
 int xx;
 int yy;

 for (i=(1<<9)-1;i>=0;i--)
  { j = 0;
    for (x=3-1;x>=0;x--)
     { for (y=3-1;y>=0;y--)
	{ if (AVATAR(i,x,y)) j |= 1 << INX(3-1-y,x);
	}
     }
    rot[i] = j;
  }
 for (x=XSIZE-1;x>=0;x--) for (y=YSIZE-1;y>=0;y--) reduce_inx[x][y] = -1;
 for (i=NREDUCE-1;i>=0;i--) reduce_inx[(int)reduce[i].x][(int)reduce[i].y] = i;
 for (d=4-1;d>=0;d--)
  { dx = ddx[d];
    dy = ddy[d];
    for (a=512-1;a>=0;a--) for (m=512-1;m>=0;m--)
     { do <"n">
	{ n = a;
	  if (! (a & m)) break <"n">;
	  for (x=3-1;x>=0;x--) for (y=3-1;y>=0;y--)
	   { if (n & m & (1 << INX(x,y)))
	      { xx = x;
		yy = y;
		while (1)
		 { xx -= dx;
		   yy -= dy;
		   if ((xx < 0) || (xx >= 3) || (yy < 0) || (yy >= 3))
		    { n = -1;
		      break <"n">;
		    }
		   if ((m >> INX(xx,yy)) & 1)
		    { n = -2;
		      break <"n">;
		    }
		   if (! ((n >> INX(xx,yy)) & 1)) break;
		 }
		n = (n & ~(1 << INX(x,y))) | (1 << INX(xx,yy));
	      }
	   }
	} while (0);
       new_avatar[d][a][m] = n;
     }
  }
}

static STATE *newstate(void)
{
 if (! new) new = malloc(sizeof(STATE));
 return(new);
}

static void usenew(void)
{
 new = 0;
}

static int wall_cell(unsigned short int a, int x, int y)
{
 int i;
 XY e;

 if (WALLS(x,y)) return(1);
 for (i=NECHO-1;i>=0;i--)
  { e = echo[i];
    if ((x >= e.x) && (x < e.x+3) && (y >= e.y) && (y < e.y+3))
     { return(AVATAR(a,x-e.x,y-e.y));
     }
  }
 return(0);
}

/*
 * Characters used:
 *
 *	In avatar?	avatar	empty	wall	reduce	goal
 *		Y	o	-	#	R	G
 *		N	n/a	.	*	r	g
 */
static void dumpstate(const STATE *s, const char *pref)
{
 int x;
 int y;
 int nextr;
 int rx;
 int gx;
 char c;

 nextr = 0;
 for (y=0;y<YSIZE;y++)
  { if (y == reduce[nextr].y)
     { rx = ((s->reduce >> nextr) & 1) ? reduce[nextr].x : 99;
       nextr ++;
     }
    else
     { rx = 99;
     }
    gx = (y == goal.y) ? goal.x : 99;
    printf("%s",pref);
    for (x=0;x<XSIZE;x++)
     { if ((x >= s->x) && (x < s->x+3) && (y >= s->y) && (y < s->y+3))
	{ if (AVATAR(s->avatar,x-s->x,y-s->y))
	   { if (wall_cell(s->avatar,x,y) || (x == rx) || (x == gx)) abort();
	     c = 'o';
	   }
	  else
	   { c = wall_cell(s->avatar,x,y) ? '#' : (x == rx) ? 'R' : (x == gx) ? 'G' : '-';
	   }
	}
       else
	{ c = wall_cell(s->avatar,x,y) ? '*' : (x == rx) ? 'r' : (x == gx) ? 'g' : '.';
	}
       printf(" %c",c);
     }
    switch (y)
     { case 0:
	  printf("  d%d a%d r%d x%d y%d",s->depth,s->avatar,s->reduce,s->x,s->y);
	  break;
#ifdef VERBOSE
       case 1:
	  printf("  %p parent %p",(const void *)s,(const void *)s->parent);
	  break;
#endif
     }
    printf("\n");
  }
}

static int find_reduce(int x, int y)
{
 return(reduce_inx[x][y]);
}

static void print_soln_chain(const STATE *s)
{
 if (s->parent) print_soln_chain(s->parent);
 dumpstate(s,"");
 printf("----\n");
}

static void printsoln(const STATE *s)
{
 printf("Solved\n");
 print_soln_chain(s);
}

static void try_new(STATE *n, const STATE *p, char via)
{
 if (avl_insert(seen,n))
  {
#ifdef VERBOSE
    printf("Already seen\n");
#endif
    return;
  }
 n->depth = p->depth + 1;
 n->parent = p;
 n->via = via;
#ifdef VERBOSE
 printf("New\n");
 dumpstate(n,"\t");
#endif
 if ((n->x == goal.x-1) && (n->y == goal.y-1))
  { printf("depth %d count %d (partial)\n",curdepth,depthcount);
    printsoln(n);
    exit(0);
  }
 if (avl_insert(pending,n)) abort();
 usenew();
}

static void trymove(const STATE *s, int dir)
{
 STATE *n;
 int x;
 int y;
 unsigned int wm;
 int r;
 int na;
 int ri;
 int ex;
 XY e;

#ifdef VERBOSE
 printf("Trying moving %c\n",dchr[dir]);
#endif
 x = (int)s->x + ddx[dir];
 y = (int)s->y + ddy[dir];
 if ((x < 0) || (x > XSIZE-2) || (y < 0) || (y > YSIZE-2)) return;
 n = newstate();
 *n = *s;
 n->x = x;
 n->y = y;
 wm = 0;
 r = -1;
 for (y=3-1;y>=0;y--)
  { for (x=3-1;x>=0;x--)
     { if (wall_cell(n->avatar,n->x+x,n->y+y)) wm |= 1 << ((3*y)+x);
       if (r < 0) r = find_reduce(n->x+x,n->y+y);
     }
  }
 na = new_avatar[dir][n->avatar][wm];
 do <"echodone">
  { do <"doecho">
     { for (ex=NECHO-1;ex>=0;ex--)
	{ e = echo[ex];
	  if ((n->x+2 >= e.x) && (n->x <= e.x+2) && (n->y+2 >= e.y) && (n->y <= e.y+2)) break <"doecho">;
	}
       break <"echodone">;
     } while (0);
    wm = 0;
    for (y=3-1;y>=0;y--)
     { for (x=3-1;x>=0;x--)
	{ if (wall_cell(na,n->x+x,n->y+y)) wm |= 1 << ((3*y)+x);
	}
     }
    if (na & wm) return;
  } while (0);
 if ((na < 0) || (na > 511))
  { if (na == -1) return;
    abort();
  }
 if ((r >= 0) && ((n->reduce >> r) & 1))
  { ri = INX(reduce[r].x-n->x,reduce[r].y-n->y);
    if ((na >> ri) & 1)
     { na &= ~(1 << ri);
       n->reduce &= ~(1 << r);
     }
  }
 n->avatar = na;
 try_new(n,s,dchr[dir]);
}

static void tryrotate(const STATE *s)
{
 STATE *n;
 int x;
 int y;
 int r;
 int b;

#ifdef VERBOSE
 printf("Trying rotation\n");
#endif
 n = newstate();
 *n = *s;
 n->avatar = rot[s->avatar];
 for (x=3-1;x>=0;x--)
  { for (y=3-1;y>=0;y--)
     { b = INX(x,y);
       if ((n->avatar >> b) & 1)
	{ if (wall_cell(n->avatar,n->x+x,n->y+y)) return;
	  r = find_reduce(n->x+x,n->y+2);
	  if ((r >= 0) && ((n->reduce >> r) & 1))
	   { n->avatar &= ~(1 << b);
	     n->reduce &= ~(1 << r);
	   }
	}
     }
  }
 try_new(n,s,'T');
}

static int cmp_seen(void *av, void *bv)
{
 STATE *a;
 STATE *b;

 a = av;
 b = bv;
 if (a->x != b->x) return((int)a->x-(int)b->x);
 if (a->y != b->y) return((int)a->y-(int)b->y);
 if (a->avatar != b->avatar) return((int)a->avatar-(int)b->avatar);
 if (a->reduce != b->reduce) return((int)a->reduce-(int)b->reduce);
 return(0);
}

static const AVL_OPS ao_seen = { .compare = &cmp_seen, .flags = AVL_F_NODUPS };

static int cmp_pending(void *av, void *bv)
{
 return((int)((STATE *)av)->depth-(int)((STATE *)bv)->depth);
}

static const AVL_OPS ao_pending = { .compare = &cmp_pending, .flags = 0 };

int main(void);
int main(void)
{
 STATE *s;

 seen = avl_new(&ao_seen);
 pending = avl_new(&ao_pending);
 start.x = 10;
 start.y = 11;
 start.avatar = 511;
 start.reduce = 511;
 start.parent = 0;
 start.depth = 0;
 precompute();
 curdepth = 0;
 depthcount = 0;
 if (avl_insert(seen,&start) || avl_insert(pending,&start)) abort();
 while (1)
  { s = avl_delete_first(pending);
    if (! s) break;
    if (s->depth == curdepth)
     { depthcount ++;
     }
    else
     { printf("depth %d count %d\n",curdepth,depthcount);
       fflush(0);
       curdepth = s->depth;
       depthcount = 1;
     }
#ifdef VERBOSE
    printf("Considering\n");
    dumpstate(s,"    ");
#endif
    trymove(s,0);
    trymove(s,1);
    trymove(s,2);
    trymove(s,3);
    tryrotate(s);
  }
 printf("Not found\n");
 return(0);
}