/*********************************************************************
 *                                                                   *
 *    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.        *
 *    Third version - use previous outputs to continue search        *
 *       in what may be more fruitful spaces                         *
 *                                                                   *
 *         Author = Mike Rosing                                      *
 *          Date  = Jan. 13, 2005                                    *
 *                                                                   *
 ********************************************************************/

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

#define SPACESIZE (175*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], basename[64];
    int statefile, ballerror, balls[6];
    int infile, ptrfile, ptrdex, lastptr;
    unsigned int stateptr[1024*100];

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

/*  initialize system from other data files  */

    printf("Read data from what file basename: ");
    scanf("%s", basename);
    sprintf(filename, "%s.dat", basename);
    infile = open(filename, O_RDWR );
    if(infile < 0) 
    {
      printf("failed to open file %s\n", filename);
      exit(0);
    }
    sprintf(filename, "%s.ptr", basename);
    ptrfile = open(filename, O_RDWR );
    if(ptrfile < 0) 
    {
      printf("failed to open file %s\n", filename);
      exit(0);
    }
    numgood = read( ptrfile, &stateptr[0], 4);
    lastptr = 1;
    while (numgood>0)
    {
      numgood = read( ptrfile, &stateptr[lastptr], 4);
      lastptr++;
    }
    printf("lastptr = %d\n", lastptr);
    printf("Save data to what basename: ");
    scanf("%s", basename);
    sprintf( filename, "%s.dat", basename);
    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);
      exit(0);
    }

    for(ptrdex = 0; ptrdex<lastptr; ptrdex++)
    {
      for(i=0; i<SPACESIZE; i++) StateSpace[i] = 0;
      printf("starting on new state #%d\n", ptrdex);
      lseek( infile, 16*stateptr[ptrdex], SEEK_SET);  // 4 bytes per long, 4 longs per state
      genstate = StateSpace;
      read( infile, genstate, 12);  // get the initial state from the file
      available = genstate+22;

/*  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=24; state>=0; 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);

	    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 % 10000) == 0) printf("working on state %d\n", pckd);
*/
	if(genstate > available) break;
      }
      pckd = state2int( genstate) & 0x7fffff;
      printf("last state examined was %d\n", pckd-1);

/*  scan resulting space for next places to search  */

      oldstate = StateSpace;
      while( oldstate < StateSpace + SPACESIZE - 22)
      {
	unpack( oldstate, matrix);
       
/*  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;
		ballerror++;
		break;
	    case 2:
		if( ballerror >= 2) break;
		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++;
	  }
	}
	oldstate += 22;
      }
      printf("all done\n");
    }
    close(statefile);
}