/*
 * Solve cube puzzles.
 *
 * A cube rolls on a 4x4 grid of squares.  Every time it touches down,
 *  it swaps what's in the square with what's on the cube face.  Given
 *  six marked squares on the original grid, the goal is to get all six
 *  of them on the cube faces.
 *
 * Command line specifies the marked squares and the initial cube
 *  location with either
 *
 * - seven numbers, each 0 through 15, in which case the first six give
 *    the marked squares and the last the cube location, or
 * - a sequence of 16 0s and 1s, of which exactly six must be 1s, with
 *    either one 0 replaced with a c or one 1 replaced with a C.
 *
 * In the first case, the numbers must be seven separate command-line
 *  arguments.  In the second case, the arguments may be anywhere from
 *  1 to 16 command-line arguments; they are effectively concatenated
 *  in order.
 *
 * Conceptually, our state consists of a 16-bit number with set bits
 *  indicating marked squares on the grid, a 6-bit number with set bits
 *  indicating marked squares on the cube, and a number in [0..15]
 *  indicating where the cube is.  This fits easily into a 32-bit
 *  integer - we need only 16+6+4=26 bits of it.  Most of the 2^26
 *  possible values for this state variable are invalid; the valid ones
 *  are those where exactly six of the 22 mark-location bits are set.
 *  We map between the sparse representation and the compact
 *  representation with arrays.
 *
 * In the sparse representation: The cube location is kept in bits
 *  0x000000f.  The grid mark bits are kept in bits 0x00ffff0.  The
 *  cube mark bits are kept in bits 0x3f00000.
 *
 * The grid is numbered
 *
 *	+----+----+----+----+
 *	|  0 |  1 |  2 |  3 |
 *	+----+----+----+----+
 *	|  4 |  5 |  6 |  7 |
 *	+----+----+----+----+
 *	|  8 |  9 | 10 | 11 |
 *	+----+----+----+----+
 *	| 12 | 13 | 14 | 15 |
 *	+----+----+----+----+
 *
 * The cube mark bits are top=0x01, back=0x02, right=0x04, front=0x08,
 *  left=0x10, bottom=0x20 (all relative to the cube-bits field).
 *
 *		    +--------+
 *		   /        /|
 *		  /  0x01  / | <---0x02
 *		 /        /  |
 *	0x10-->	+--------+ 0x04
 *		|        |  /
 *		|  0x08  | / <---0x20
 *		|        |/
 *		+--------+
 *
 * In the compact representation: The cube location is kept in bits
 *  0xf, with the upper bits replaced by the compact representation of
 *  the same 22 bits.
 */

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

extern const char *__progname;

typedef unsigned int STATE;

// Number of sparse and compact bitmask states
// (ie, cube location not included)
#define NSPARSE (65536*64)
#define NCOMPACT 74613

// Number of possible states
#define NSTATE (NCOMPACT*16)

// Location of cube-location bits within a state
#define CUBE_S 0
#define CUBE_M 0x0f
// Location of mark bits within a state
// Same for sparse and compact, except value < NCOMPACT for compact
#define MARK_S 4
#define MARK_M 0x03fffff
// Build a state from a cube location and mark bits
#define STATE_MAKE(cube,mark) (((cube) << CUBE_S) | ((mark) << MARK_S))
// Crack a state apart
#define STATE_CUBE(s) (((s) >> CUBE_S) & CUBE_M)
#define STATE_MARK(s) (((s) >> MARK_S) & MARK_M)
// Pieces of a sparse representation (within mark bits)
#define S_GRID_S 0
#define S_GRID_M 0x00ffff
#define S_CUBE_S 16
#define S_CUBE_M 0x3f
// The bit position on the cube which swaps with the grid
#define SWAP_BIT 0x20

// Parsed command line
static int cmdline_grid[6];
static int cmdline_cube;

// Map sparse representation to compact representation
static int stoc[NSPARSE];
// Map compact representation to sparse representation
static unsigned int ctos[NCOMPACT];

// Permute cube bits for a single roll step.
static unsigned int roll_mx[64];
static unsigned int roll_px[64];
static unsigned int roll_my[64];
static unsigned int roll_py[64];

typedef enum {
	  D_MX = 1,
	  D_PX,
	  D_MY,
	  D_PY
	  } DIR;

typedef struct sq SQ;

struct sq {
  STATE *v;
  int n;
  } ;

// Start state (sparse representation)
static STATE start;

// Distance from start position (~0 if not seen)
static unsigned int dist[NSTATE];

// List of states to investigate
static SQ nextq;

// List of states being investigated
static SQ curq;

// Vectors of STATEs for nextq and curq
#define QVSIZE (NSTATE*4) // deliberate overestimate
static STATE qv[2][QVSIZE];

// Depth of states on curq
static int curdepth;

// Have we printed a solution yet?
static int gotsoln;

static int try_parse_16(int ac, char **av)
{
 int ax;
 int cwa;
 int i;
 int j;

 for (i=6-1;i>=0;i--) cmdline_grid[i] = -1;
 cmdline_cube = -1;
 ax = 1;
 cwa = 0;
 for (i=0;i<16;i++)
  { if (ax >= ac) return(0);
    while (av[ax][cwa] == '\0')
     { ax ++;
       cwa = 0;
       if (ax >= ac) return(0);
     }
    switch (av[ax][cwa])
     { case '0':
	  break;
       case 'c':
	  if (cmdline_cube >= 0) return(0);
	  cmdline_cube = i;
	  break;
       case 'C':
	  if (cmdline_cube >= 0) return(0);
	  cmdline_cube = i;
	  // fall through
       case '1':
	  do <"set">
	   { for (j=6-1;j>=0;j--)
	      { if (cmdline_grid[j] < 0)
		 { cmdline_grid[j] = i;
		   break <"set">;
		 }
	      }
	     return(0);
	   } while (0);
	  break;
       case ' ':
	  break;
       default:
	  return(0);
	  break;
     }
    cwa ++;
  }
 if (cmdline_cube < 0) return(0);
 return(1);
}

static int try_parse_7(int ac, char **av)
{
 int i;
 int j;

 if (ac != 8) return(0);
 for (i=6-1;i>=0;i--)
  { cmdline_grid[i] = atoi(av[i+1]);
    if ((cmdline_grid[i] < 0) || (cmdline_grid[i] > 15)) return(0);
  }
 for (i=6-1;i>0;i--) for (j=i-1;j>=0;j--) if (cmdline_grid[i] == cmdline_grid[j]) return(0);
 cmdline_cube = atoi(av[7]);
 if ((cmdline_cube < 0) || (cmdline_cube > 15)) return(0);
 return(1);
}

static void parse_cmdline(int ac, char **av)
{
 if (try_parse_16(ac,av)) return;
 if (try_parse_7(ac,av)) return;
 fprintf(stderr,"%s: can't parse puzzle from command line\n",__progname);
 exit(1);
}

static unsigned int popcount(unsigned int v)
{
 v = ((v >> 1) & 0x55555555) + (v & 0x55555555);
 v = ((v >> 2) & 0x33333333) + (v & 0x33333333);
 v = ((v >> 4) & 0x0f0f0f0f) + (v & 0x0f0f0f0f);
 v = ((v >> 8) & 0x00ff00ff) + (v & 0x00ff00ff);
 return( ((v >> 16) & 0x0000ffff) + (v & 0x0000ffff) );
}

static void build_tables(void)
{
 int cx;
 int i;

 cx = 0;
 for (i=NSPARSE-1;i>=0;i--)
  { if (popcount(i) == 6)
     { if (cx >= NCOMPACT) abort();
       stoc[i] = cx;
       ctos[cx] = i;
       cx ++;
     }
    else
     { stoc[i] = -1;
     }
  }
 if (cx != NCOMPACT) abort();
 for (i=64-1;i>=0;i--)
  { roll_mx[i] = (i & 0x0a) | ((i & 0x01) ? 0x10 : 0) | ((i & 0x04) ? 0x01 : 0) | ((i & 0x20) ? 0x04 : 0) | ((i & 0x10) ? 0x20 : 0);
    roll_px[i] = (i & 0x0a) | ((i & 0x01) ? 0x04 : 0) | ((i & 0x04) ? 0x20 : 0) | ((i & 0x20) ? 0x10 : 0) | ((i & 0x10) ? 0x01 : 0);
    roll_my[i] = (i & 0x14) | ((i & 0x01) ? 0x02 : 0) | ((i & 0x02) ? 0x20 : 0) | ((i & 0x20) ? 0x08 : 0) | ((i & 0x08) ? 0x01 : 0);
    roll_py[i] = (i & 0x14) | ((i & 0x01) ? 0x08 : 0) | ((i & 0x02) ? 0x01 : 0) | ((i & 0x20) ? 0x02 : 0) | ((i & 0x08) ? 0x20 : 0);
  }
}

static void sq_init(SQ *sq, unsigned int *v)
{
 sq->v = v;
 sq->n = 0;
}

static void add_next_state(STATE s)
{
 if (nextq.n >= QVSIZE) abort();
 nextq.v[nextq.n++] = s;
}

static void init(void)
{
 int i;
 unsigned int s;

 build_tables();
 for (i=NSTATE-1;i>=0;i--) dist[i] = ~0U;
 s = 0;
 for (i=6-1;i>=0;i--) s |= 1U << cmdline_grid[i];
 start = STATE_MAKE(cmdline_cube,s);
 sq_init(&curq,&qv[0][0]);
 sq_init(&nextq,&qv[1][0]);
 add_next_state(start);
 curdepth = -1;
 gotsoln = 0;
}

static void explore_move(STATE s, DIR dir)
{
 int cl;
 unsigned int sb;
 unsigned int cb;
 unsigned int gb;

 cl = STATE_CUBE(s);
 sb = STATE_MARK(s);
 cb = (sb >> S_CUBE_S) & S_CUBE_M;
 gb = (sb >> S_GRID_S) & S_GRID_M;
 switch (dir)
  { case D_MX:
       cl --;
       cb = roll_mx[cb];
       break;
    case D_PX:
       cl ++;
       cb = roll_px[cb];
       break;
    case D_MY:
       cl -= 4;
       cb = roll_my[cb];
       break;
    case D_PY:
       cl += 4;
       cb = roll_py[cb];
       break;
    default:
       abort();
       break;
  }
 if (cb & SWAP_BIT)
  { if (! ((gb >> cl) & 1))
     { gb |= 1U << cl;
       cb &= ~SWAP_BIT;
     }
  }
 else
  { if ((gb >> cl) & 1)
     { gb &= ~(1U << cl);
       cb |= SWAP_BIT;
     }
  }
 add_next_state(STATE_MAKE(cl,(gb<<S_GRID_S)|(cb<<S_CUBE_S)));
}

static void printsoln(STATE s)
{
 
}

static void explore(STATE s)
{
 unsigned int cl;
 unsigned int sb;
 int cb;
 int cs;

 cl = STATE_CUBE(s);
 sb = STATE_MARK(s);
 if (((sb >> S_CUBE_S) & S_CUBE_M) == 0x3f)
  { if (! gotsoln)
     { printsoln(s);
     }
  }
  { int cb;
    int gb;
    cb = (sb >> S_CUBE_S) & S_CUBE_M;
    gb = (sb >> S_GRID_S) & S_GRID_M;
    printf("explore: cl %d cb %d%d%d%d%d%d sb %d%d%d%d %d%d%d%d %d%d%d%d %d%d%d%d\n",cl,
	cb&1,(cb>>1)&1,(cb>>2)&1,(cb>>3)&1,(cb>>4)&1,(cb>>5)&1,
	sb&1,(sb>>1)&1,(sb>>2)&1,(sb>>3)&1,
	(sb>>4)&1,(sb>>5)&1,(sb>>6)&1,(sb>>7)&1,
	(sb>>8)&1,(sb>>9)&1,(sb>>10)&1,(sb>>11)&1,
	(sb>>12)&1,(sb>>13)&1,(sb>>14)&1,(sb>>15)&1);
  }
 cb = stoc[sb];
 if (cb < 0) abort();
 cs = STATE_MAKE(cl,cb);
 if (dist[cs] <= curdepth) return;
 dist[cs] = curdepth;
 if (cl & 3) explore_move(s,D_MX);
 if ((cl & 3) != 3) explore_move(s,D_PX);
 if (cl & 12) explore_move(s,D_MY);
 if ((cl & 12) != 12) explore_move(s,D_PY);
}

static void crunch(void)
{
 STATE s;

 while (1)
  { if (curq.n < 1)
     { unsigned int *t;
       if (nextq.n < 1) return;
       t = curq.v;
       curq.v = nextq.v;
       nextq.v = t;
       curq.n = nextq.n;
       nextq.n = 0;
       curdepth ++;
       printf("depth %d count %d\n",curdepth,curq.n);
       continue;
     }
    s = curq.v[--curq.n];
    explore(s);
  }
}

int main(int, char **);
int main(int ac, char **av)
{
 parse_cmdline(ac,av);
 init();
 crunch();
 return(0);
}