/*********************************************************************
 *                                                                   *
 *    This program computes the states of the Japanese ball          *
 *    puzzle and writes them out to disk.                            *
 *                                                                   *
 *    Second version - a touch more efficient than the first.        *
 *                                                                   *
 *         Author = Mike Rosing                                      *
 *          Date  = Jan. 10, 2005                                     *
 *                                                                   *
 ********************************************************************/

#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define SPACESIZE (200*1024*1024)

unsigned int *StateSpace;

/*  I use 22 longs to represent all possible states.  The first 3 longs
    represent the balls with 3 bits for each ball.  The most signficant
    bit of the 0th long holds up/down toggle state - 0 is up, 1 is down.
    The last 9 bits of the 0th long hold row 0 if in up state and row 5
    if in down state.  The next 4 short words (2 longs) hold the rows 1
    through 4 using 15 bits, the msb is not used.  The next 19 longs hold
    3 byte pointers of which 23 bits are indexes to 22 long states, and 
    the most significant bit says if that state has been visited (set).
    19 longs = 4*19 = 76 bytes and I need 3*25 = 75 bytes.  Last byte
    is not used.
*/
/*  perform a rotation on a row of balls.  Enter with rotation
    amount (+/-2, +/-1, or 0).  Operates on a short.  Negative 
    shifts go left, positive shifts go right.
*/

void rotate( int shift, unsigned short *row)
{
    unsigned short mask1, mask2;

    if( !shift) return;
    if( shift<0)
    {
	if( shift == -1)
	{
	    mask1 = 0x7000;
	    mask2 = 0x0fff;
	    *row = (*row & mask1) >> 12 | (*row & mask2) << 3;
	}
	else
	{
	    mask1 = 0x7e00;
	    mask2 = 0x01ff;
	    *row = (*row & mask1) >> 9 | (*row & mask2) << 6;
	}
    }
    else
    {
	if( shift == 1)
	{
	    mask1 = 0x0007;
	    mask2 = 0x7ff8;
	    *row = (*row & mask1) << 12 | (*row & mask2) >> 3;
	}
	else
	{
	    mask1 = 0x003f;
	    mask2 = 0x7fc0;
	    *row = (*row & mask1) << 9 | (*row & mask2) >> 6;
	}
    }
}

/*  perform a toggle operation  
    Since state is done in place, flips toggle bit.
*/

void toggle( unsigned int *state)
{
    unsigned int mask1, mask2, mask3, mask4, mask5;

    mask1 = state[0] & 0x1ff;
    mask2 = state[1] & 0x0e380e38;
    mask3 = state[2] & 0x0e380e38;
    mask4 = state[1] & 0x71c771c7;
    mask5 = state[2] & 0x71c771c7;
    if( *state & 0x80000000) // going from down to up
    {
	state[0] = (mask4 & 0x70000000) >> 22
	    | (mask4 & 0x01c00000) >> 19
	    | (mask4 & 0x00070000) >> 16;
	state[1] = mask2 | (mask4 & 0x71c7) << 16
	    | (mask5 & 0x71c70000) >> 16;
	state[2] = mask3 | (mask5 & 0x71c7) << 16
	    | (mask1 & 0x1c0) << 6 | (mask1 & 0x38) << 3
	    | (mask1 & 0x7);
    }
    else
    {
/*  going from up to down  */
	
	state[0] = (mask5 & 0x7000) >> 6 | ( mask5 & 0x01c0) >> 3 
	    | (mask5 & 7) | 0x80000000;
	state[1] = (mask1 & 0x1c0) << 22 | (mask1 & 0x38) << 19
	    | (mask1 & 0x7) << 16 | (mask4 & 0x71c70000) >> 16
	    | mask2;
	state[2] = mask3 | (mask5 & 0x71c70000) >> 16
	    | (mask4 & 0x71c7) << 16;
    }
}

/*  compare two states.  If same returns 1, 
    if different, returns 0.
*/

int compare( unsigned int *state1, unsigned int *state2)
{
    if( state1[0] != state2[0]) return 0;
    if( state1[1] != state2[1]) return 0;
    if( state1[2] != state2[2]) return 0;
    return 1;
}

/*  convert pointer to state block from an address to an integer */

unsigned int state2int( unsigned int *state)
{
    unsigned int k;

    k = (unsigned int) (state - StateSpace);
    k /= 22;
    k |= 0x800000;
    return k;
}

unsigned int *int2state( unsigned int k)
{
    unsigned int p;

    p = k & 0x7fffff;
    p *= 22;
    return (unsigned int*)(StateSpace +  p);
}

/*  store 24 bit pointer into correct offset location  */

void store24( unsigned int *state, int index, unsigned int value)
{
    char *ptr;

    ptr = (char *)state;
    ptr += 12 + 3*index;
    *ptr++ = (value >> 16) & 0xff;
    *ptr++ = (value >> 8) & 0xff;
    *ptr = value & 0xff;
}

/*  get 24 bit value out of location stored in state structure  */

unsigned int get24( unsigned int *state, int index)
{
    char *ptr;
    unsigned int x;

    ptr = (char *)state;
    ptr += 12 + 3*index;
    x = ((*ptr++) << 16) & 0xff0000;
    x |= ((*ptr++) << 8) & 0xff00;
    x |= (*ptr) & 0xff;
    return x;
}

/*  convert state date back into matrix for checking.
    not to be used in full run!!  */

void unpack( unsigned int *state, int matrix[6][5])
{
    int row, col;
    unsigned int mask;

    mask = state[0];
    for( col=0; col<5; col++)
    {
	matrix[0][col] = -1;
	matrix[5][col] = -1;
    }
    if( state[0] & 0x80000000)
    {
	matrix[5][0] = (mask & 0x1c0) >> 6;
	matrix[5][2] = (mask & 0x38) >> 3;
	matrix[5][4] = mask & 7;
    }
    else
    {
	matrix[0][0] = (mask & 0x1c0) >> 6;
	matrix[0][2] = (mask & 0x38) >> 3;
	matrix[0][4] = mask & 7;
    }
    mask = 0x70000000;
    for(col=0; col<5; col++)
    {
	matrix[1][col] = (state[1] & mask) >> (28 - col*3);
	mask >>= 3;
    }
    mask >>= 1;
    for(col=0; col<5; col++)
    {
	matrix[2][col] = (state[1] & mask) >> (12 - col*3);
	mask >>= 3;
    }
    mask = 0x70000000;
    for(col=0; col<5; col++)
    {
	matrix[3][col] = (state[2] & mask) >> (28 - col*3);
	mask >>= 3;
    }
    mask >>= 1;
    for(col=0; col<5; col++)
    {
	matrix[4][col] = (state[2] & mask) >> (12 - col*3);
	mask >>= 3;
    }
}

main()
{
    unsigned int *genstate, *available, *oldstate;
    int matrix[6][5],  numgood;
    int row, col, state, i;
    unsigned short *rowptr;
    unsigned int pckd;
    char inchr[2], filename[64];
    int statefile, ballerror, balls[6];
    int coltrix[5][5][5][5];  // color a, color b, row a, row b
    int colora, colma;

    StateSpace = malloc(sizeof(int)*SPACESIZE);
    if (StateSpace == NULL) 
    {
	printf("sorry, can't get that much space\n");
	exit(0);
    }

/*  initialize system from real puzzle  */

    for(i=0; i<SPACESIZE; i++) StateSpace[i] = 0;
    printf("Starting in up state \n");
    printf("Do each column from right most double plunger\n");
    printf("continuing to each next right column. \n");
    printf("0 = black,\n");
    printf("1 = red,\n");
    printf("2 = green\n");
    printf("3 = orange\n");
    printf("4 = blue\n");
    printf("5 = yellow\n");
/*  fake initial state while debugging
    for( col=0; col<5; col++)
    {
	for( row=0; row<5; row++)
	{
	    if( (col & 1) && (!row)) continue;
	    printf("column %d, row %d, input color: ", col, row);
	    scanf("%s", inchr);
	    while( inchr[0]>'5' && inchr[0]<'0')
	    {
		printf("0 = black,\n");
		printf("1 = red,\n");
		printf("2 = green\n");
		printf("3 = orange\n");
		printf("4 = blue\n");
		printf("5 = yellow\n");
		printf("column %d, row %d, input color: ");
		scanf("%s", inchr);
	    }
	    matrix[row][col] = inchr[0] & 7;
	}
	matrix[5][col] = -1;
    }
*/
/*****************begin fake input*****************/
    matrix[ 0][ 0] = 3;
    matrix[ 1][ 0] = 2;
    matrix[ 2][ 0] = 3;
    matrix[ 3][ 0] = 4;
    matrix[ 4][ 0] = 3;
    matrix[0][1] = -1;
    matrix[ 1][ 1] = 5;
    matrix[ 2][ 1] = 5;
    matrix[ 3][ 1] = 2;
    matrix[ 4][ 1] = 4;
    matrix[ 0][ 2] = 0;
    matrix[ 1][ 2] = 1;
    matrix[ 2][ 2] = 1;
    matrix[ 3][ 2] = 1;
    matrix[ 4][ 2] = 1;
    matrix[0][3] = -1;
    matrix[ 1][ 3] = 4;
    matrix[ 2][ 3] = 5;
    matrix[ 3][ 3] = 4;
    matrix[ 4][ 3] = 2;
    matrix[ 0][ 4] = 5;
    matrix[ 1][ 4] = 2;
    matrix[ 2][ 4] = 3;
    matrix[ 3][ 4] = 0;
    matrix[ 4][ 4] = 0;
    matrix[5][0] = -1;
    matrix[5][1] = -1;
    matrix[5][2] = -1;
    matrix[5][3] = -1;
    matrix[5][4] = -1;
/*******************end fake input****************/
/*  verify that input data is ok  */

	for( i=0; i<6; i++) balls[i] = 0;
	for( row=0; row<6; row++)
	    for( col=0; col<5; col++)
		if( matrix[row][col] >= 0)
		    balls[matrix[row][col]]++;
	ballerror = 0;
	if( balls[0] != 3)
	{
	  printf("wrong black # - %d\n", balls[0]);
	  ballerror = 1;
	}
	for( i=1; i<6; i++)
	{
	    if( balls[i] != 4)
	    {
		printf(" wrong color %d - #= %d\n", i, balls[i]);
		ballerror = 1;
	    }
	}
	if (ballerror)
	{
	  for(row=0; row<6; row++)
	  {
	    for(col=0; col<5; col++)
	      printf("%d  ", matrix[row][col]);
	    printf("\n");
	  }
	  exit(0);
	}

    genstate = StateSpace;
    available = genstate+22;

/*  convert input matrix to initial stored state  */

    genstate[0] = (matrix[0][0] & 7)  << 6 | (matrix[0][2] & 7) << 3
	| (matrix[0][4] & 7);
    for(i=0; i<5; i++)
	genstate[1] |= (matrix[1][i] & 7) << 28 - 3*i;
    for(i=0; i<5; i++)
	genstate[1] |= (matrix[2][i] & 7) << 12 - 3*i;
    for(i=0; i<5; i++)
	genstate[2] |= (matrix[3][i] & 7) << 28 - 3*i;
    for(i=0; i<5; i++)
	genstate[2] |= (matrix[4][i] & 7) << 12 - 3*i;

    printf("genstate[0] = %x;\n", genstate[0]);
    printf("genstate[1] = %x;\n", genstate[1]);
    printf("genstate[2] = %x;\n", genstate[2]);
    exit(0);

/*	unpack( genstate, matrix);
	for(row=0; row<6; row++)
	{
	    for(col=0; col<5; col++)
		printf("%d  ", matrix[row][col]);
	    printf("\n");
	}
 
/*  generate first 25 states off of initial state.  */

    for( state=0; state<25; state++)
    {
	for(i=0; i<3; i++) available[i] = genstate[i];
	i = state/5 - 2;
	rowptr = (unsigned short *) (&available[1]);
	rotate( i, rowptr);
 	rowptr++;
	rotate( i, rowptr);
	i = state%5 - 2;
	rowptr = (unsigned short *) (&available[2]);
	rotate( i, rowptr);
	rowptr++;
	rotate( i, rowptr);
	toggle( available);

/*  mark initial state with pointer to this one and vice versa  */

	pckd = state2int( genstate);
	store24( available, 24 - state, pckd);
	pckd = state2int( available);
	store24( genstate, state, pckd);
	available += 22;
    }
    genstate += 22;

/* now generate as many new verticies as possible.   */

    while( available < StateSpace + SPACESIZE-22)
    {
	for( state=0; state<25; state++)
	{

  /*  skip state 0,0 when going from down to up  */

	  if( (genstate[0] & 0x80000000) && (state == 12)) continue;
	    pckd = get24( genstate, state);
	    if (pckd & 0x800000) continue;  // been here already !
	    for( i=0; i<3; i++) available[i] = genstate[i];
	    i = state/5 - 2;
	    rowptr = (unsigned short *) (&available[1]);
	    rotate( i, rowptr);
	    rowptr++;
	    rotate( i, rowptr);
	    i = state%5 - 2;
	    rowptr = (unsigned short *) (&available[2]);
	    rotate( i, rowptr);
	    rowptr++;
	    rotate( i, rowptr);
	    toggle( available);

/*	    oldstate = genstate + 22;  // start search and next state
	    while( oldstate < available)
	    {
		if( compare(available, oldstate))
		{
		    pckd = state2int( oldstate);
		    store24( genstate, state, pckd);
		    pckd = state2int( genstate);
		    store24( oldstate, 24 - state, pckd);
		    break;
		}
		oldstate += 22;
	    }
	    if( oldstate == available)
*/
	    {
		pckd = state2int( available);
		store24( genstate, state, pckd);
		pckd = state2int( genstate);
		store24( available, 24 - state, pckd);
		available += 22;
	    }
	    if(available > StateSpace + SPACESIZE-22) break;
	}

/*  next step is to pick a direction to fill previous generated states.
    for now, use plain old brute force.
*/
	genstate += 22;
	pckd = state2int( genstate) & 0x7fffff;
	if( (pckd % 100000) == 0) printf("working on state %d\n", pckd);
	if(genstate > available) break;
    }

    printf("last state examined was %d\n", pckd-1);

/*  scan data file and look for good states  */

    for(col=0; col<5; col++)
    {
      for(i=0; i<5; i++)
      {
	for( row=0; row<5; row++)
	{ 
	  for(state=0; state<5; state++)
	    coltrix[col][i][row][state] = 0;
	}
      }
    }

    printf("Save data to what file: ");
    scanf("%s", filename);
    statefile = open(filename, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR | 
		     S_IRGRP |S_IWGRP | S_IROTH );
    if(statefile < 0) printf("failed to create file %s\n", filename);

/*  first check that every state makes sense */

    oldstate = StateSpace;
    while( oldstate < StateSpace + SPACESIZE - 22)
    {
	unpack( oldstate, matrix);
/*	for( i=0; i<6; i++) balls[i] = 0;
	for( row=0; row<6; row++)
	    for( col=0; col<5; col++)
		if( matrix[row][col] >= 0)
		    balls[matrix[row][col]]++;
	ballerror = 0;
	if( balls[0] != 3)
	{
	  printf("in state %d wrong black # - %d\n", 
		 state2int(oldstate) & 0x7fffff, balls[0]);
	  ballerror = 1;
	}
	for( i=1; i<6; i++)
	{
	    if( balls[i] != 4)
	    {
		printf("in state %d, wrong color %d - #= %d\n", 
		       state2int(oldstate) & 0x7fffff, i, balls[i]);
		ballerror = 1;
	    }
	}
	if (ballerror)
	{
	  for(row=0; row<6; row++)
	  {
	    for(col=0; col<5; col++)
	      printf("%d  ", matrix[row][col]);
	    printf("\n");
	  }
	  exit(0);
	}
       
/*  is this state "interesting"?  */

	numgood = 0;
	ballerror = 0;
	for( col=0; col<5; col++)
	{
	  if( matrix[0][col] < 0)
	  {
	    if( matrix[5][col] == matrix[4][col])
	    {
	      if( (matrix[4][col] == matrix[3][col]) &&
		  (matrix[3][col] == matrix[2][col]))
	      {
		numgood++;
		i = matrix[2][col];
	      }
	    }
	    else if ( matrix[4][col] == matrix[3][col])
	    {
	      if( (matrix[2][col] == matrix[3][col]) &&
		  (matrix[1][col] == matrix[2][col]))
	      {
		numgood++;
		i = matrix[2][col];
	      }
	    }
	  }
	  else
	  {
	    if( matrix[0][col] == matrix[1][col])
	    {
	      if( (matrix[1][col] == matrix[2][col]) &&
		  (matrix[3][col] == matrix[2][col]))
	      {
		numgood++;
		i = matrix[2][col];
	      }
	    }
	    else if ( matrix[1][col] == matrix[2][col])
	    {
	      if( (matrix[2][col] == matrix[3][col]) &&
		  (matrix[3][col] == matrix[4][col]))
	      {
		numgood++;
		i = matrix[2][col];
	      }
	    }
	  }
	  switch (numgood)
	  {
	    case 0:
		ballerror = 0;
		break;
	    case 1: 
		if( ballerror) break;
		colma = col;
		colora = i-1;
		ballerror++;
		break;
	    case 2:
		if( ballerror >= 2) break;
		coltrix[colora][i-1][colma][col]++;
		ballerror++;
		break;
	    case 3:
	        if ( ballerror >= 3) break;
		printf("%d columns in state %d\n", numgood, 
		       state2int(oldstate) & 0x7fffff);

/*  we have more than 2 states.  Follow path back to
    state 0 and write each step out to disk.  */

		available = oldstate;
		while (available != StateSpace)
		{
		  for (state=0; state<3; state++)
		    write( statefile, &available[state], 4);
		  for( state=0; state<25; state++)
		  {
		    pckd = get24( available, state);
		    if (! (pckd & 0x800000)) continue;
		    if (pckd < state2int( available)) 
		    {
		      write( statefile, &state, 4);
		      available = int2state(pckd);
		      break;
		    }
		  }
		}
		for (state=0; state<3; state++)
		  write( statefile, &available[state], 4);
		pckd = 0xffffffff;
		write( statefile, &pckd, 4);
		ballerror++;
		break;
	    case 4:
	        if ( ballerror >= 4) break;
		printf("%d columns in state %d\n", numgood, 
		       state2int(oldstate) & 0x7fffff);

/*  we have more than 2 states.  Follow path back to
    state 0 and write each step out to disk.  */

		available = oldstate;
		while (available != StateSpace)
		{
		  for (state=0; state<3; state++)
		    write( statefile, &available[state], 4);
		  for( state=0; state<25; state++)
		  {
		    pckd = get24( available, state);
		    if (! (pckd & 0x800000)) continue;
		    if (pckd < state2int( available)) 
		    {
		      write( statefile, &state, 4);
		      available = int2state(pckd);
		      break;
		    }
		  }
		}
		for (state=0; state<3; state++)
		  write( statefile, &available[state], 4);
		pckd = 0xffffffff;
		write( statefile, &pckd, 4);
		ballerror++;
		break;
	    default:
	        if ( ballerror >= 5) 
		{
		  printf("More than 5 columns - you are fucked!!!\n");
		  exit(0);
		}
		printf("SOLUTION FOUND: %d columns in state %d\n", numgood, 
		       state2int(oldstate) & 0x7fffff);

/*  we have more than 2 states.  Follow path back to
    state 0 and write each step out to disk.  */

		available = oldstate;
		while (available != StateSpace)
		{
		  for (state=0; state<3; state++)
		    write( statefile, &available[state], 4);
		  for( state=0; state<25; state++)
		  {
		    pckd = get24( available, state);
		    if (! (pckd & 0x800000)) continue;
		    if (pckd < state2int( available)) 
		    {
		      write( statefile, &state, 4);
		      available = int2state(pckd);
		      break;
		    }
		  }
		}
		for (state=0; state<3; state++)
		  write( statefile, &available[state], 4);
		pckd = 0xffffffff;
		write( statefile, &pckd, 4);
		ballerror++;
	  }
	}
	if( numgood == 1) coltrix[colora][colora][colma][colma]++;
	oldstate += 22;
    }

    for(col=0; col<5; col++)
    {
      printf("column b = %d\n\n", col);
      for(colora=0; colora<5; colora++)
      {
	for(i=0; i<5; i++) 
	{
	  for(colma=0; colma<5; colma++)
	  {
	    if( ((colma != col) && (colora == i)) ||
		((colma == col) && (colora != i)))
	      printf("   X ");
	    else
	      printf("%4d ", coltrix[colora][i][colma][col]);
	  }
	  printf("  ");
	}
	printf("\n");
      }
      printf("\n");
    }

/*  all of ram filled.  save data to disk  */

    close(statefile);
    printf("all done\n");

}