/*********************************************************************
 *                                                                   *
 *    This program reads in the states of the Japanese ball          *
 *    puzzle from disk and does some analysis.                       *
 *                                                                   *
 *         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  (128*1024*10)
#define SPACESIZE (96*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.
*/
/*  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 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, *endstate;
    unsigned int stateptr[16*1024], *endptr;
    int matrix[6][5];
    int row, col, state, i, k, numgood;
    unsigned int pckd, initialstate[4];
    char inchr[2], filename[64], basename[64];
    int statefile, ptrfile, lastptr, numsol;
    int shortsol[64], shortest;

    initialstate[0] = 0x000000c5;
    initialstate[1] = 0x2a623a6b;
    initialstate[2] = 0x44603850;
    initialstate[3] = 0x00000000;

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

/*  recover previously computed data from disk  */

    printf("Read data from what file basename: ");
    scanf("%s", basename);
    sprintf(filename, "%s.dat", basename);
    statefile = open(filename, O_RDWR );
    if(statefile < 0) 
    {
      printf("failed to open file %s\n", filename);
      exit(0);
    }
    for( i=0; i<SPACESIZE; i++)
    {
	state = read( statefile, &StateSpace[i], 4);
	if (!state) break;
    }
    if(i>=SPACESIZE)
    {
      printf("ERROR: can't read in whole datafile!!\n");
      exit(0);
    }
    close(statefile);
    endptr = &StateSpace[i];
    sprintf(filename, "%s.ptr", basename);
    ptrfile = open(filename, O_RDWR );
    if(ptrfile < 0)
    {
      printf("failed to open file %s\n", filename);
      exit(0);
    }
    state = read( ptrfile, &stateptr[0], 4);
    lastptr = 0;
    while (state && (lastptr < 16*1024))
    {
      lastptr++;
      state = read( ptrfile, &stateptr[lastptr], 4);
    }
    
    if( lastptr>= 16*1024)
      printf("WARNING: can't reach all pointers in file!!\n");

/*  find all positions that have a terminous state  */

    oldstate = StateSpace;
    i = 0;
    k = 0;
    while (oldstate < endptr)
    {
      if(compare( oldstate, initialstate) && (oldstate[3] == 0xffffffff))
	k++;
      oldstate += 4;
      i++;
    }
    printf("number of states is %d number of terminous states is %d\n", i, k);

/*  print out all states from start to finish  */
    numsol = 0;
    endstate = StateSpace;
    genstate = initialstate;
//    while( endstate < endptr)
    for( k=0; k<lastptr; k++)
    {
      endstate = (unsigned int*)( stateptr[k]*4  + StateSpace);
      unpack( endstate, matrix);
       
/*  is this state "interesting"?  */

      numgood = 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];
	    }
	  }
	}
      }
      if(numgood < 5) 
      {
	  endstate += 4;
	  continue;
      }
      oldstate = endstate + 4;
      while( (oldstate < endptr) && (!compare(oldstate, genstate)) 
	     && (oldstate[3] != 0xffffffff))
      {
	oldstate += 4;
      }
//      genstate = oldstate;
      shortsol[numsol] = 0;
      while( oldstate >= endstate)
      {
	  shortsol[numsol]++;
	state = 24 - oldstate[3];
//	printf("state = %d\n", state);
	if( state < 25)
	  printf("\nstate transition =  %d, %d rotation\n", 
		 (state/5)-2, (state%5)-2);
	else
	  printf("\ninitial state: \n");
	unpack(oldstate, matrix);
	for(row=0; row<6; row++)
	{
	  for(col=0; col<5; col++)
	    printf("%d  ", matrix[row][col]);
	  printf("\n");
	}
	oldstate -= 4;
      }
//      endstate = genstate;
      printf("------------------------------  %d\n", shortsol[numsol]);
      numsol++;
    }
    printf("total number of solutions found is %d\n", numsol);
    shortest = 400000000;
    for(i=0; i<numsol; i++)
    {
	if( shortsol[i] < shortest)
	{
	    shortest = shortsol[i];
	    k = i;
	}
    }
    printf("shortest solution is %d at path %d\n", shortest, k);
	
}