/*********************************************************************
 *                                                                   *
 *    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  (1024*1024*64)

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;
}

main()
{
    unsigned int *genstate, *available, *oldstate, *endstate;
    unsigned int *stateptr, *endptr, *pathptr, *pathblk, *lastpath, *fixptr;
    int matrix[6][5];
    int row, col, state, i, k;
    unsigned int pckd, initialstate[4], *ptrptr;
    char inchr[2], filename[64], basename[50];
    int statefile, ptrfile, ptrdex, lastptr, lastptrptr;

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

    StateSpace = (unsigned int*)malloc(sizeof(int)*SPACESIZE);
    if (StateSpace == NULL) 
    {
	printf("sorry, can't get that much space\n");
	exit(0);
    }
    stateptr = (unsigned int*)malloc( sizeof(int)*1024*1024);
    if( stateptr == NULL)
    {
      printf("can't allocate state pointer ram\n");
      exit(0);
    }
    ptrptr = (unsigned int*)malloc( sizeof(int)*1024*1024);
    if( ptrptr == NULL)
    {
      printf("can't allocate pointer pointer ram\n");
      exit(0);
    }
    pathblk = (unsigned int*)malloc( sizeof(int)*1024*1024*16);
    if( pathblk == NULL)
    {
      printf("can't allocate path block ram\n");
      exit(0);
    }


/*  recover previously computed data from disk  */
    lastptr = 0;
    genstate = StateSpace;
    for(k=0x6; k>=0; k--)
    {
      sprintf(filename, "solpath%02x.dat", k);
      printf("doing file %s\n", filename);
      statefile = open(filename, O_RDWR );
      if(statefile < 0)
      {
	printf("failed to open file %s\n", filename);
	exit(0);
      }
      sprintf(filename, "solpath%02x.ptr", k);
      ptrfile = open(filename, O_RDWR );
      if(ptrfile < 0)
      {
	printf("failed to open file %s\n", filename);
	exit(0);
      }
      state = read( ptrfile, &ptrptr[0], 4);
      lastptrptr = 0;
      while (state && (lastptr < 16*1024))
      {
	  lastptrptr++;
	  state = read( ptrfile, &ptrptr[lastptrptr], 4);
      }
      printf("found %d pointers\n", lastptrptr);
//      state = read( ptrfile, &ptrdex, 4);
//      while(state)
      for(ptrdex=0; ptrdex<lastptrptr; ptrdex++)
      {
	lseek( statefile, 16*ptrptr[ptrdex], SEEK_SET);
	state = read( statefile, genstate, 16);
	stateptr[lastptr] = (unsigned int)(genstate - StateSpace);
	while( (genstate[3] != 0xffffffff) && state)
	{
	  genstate += 4;
	  state = read( statefile, genstate, 16);
	}
	oldstate = (unsigned int*) (stateptr[lastptr] + StateSpace);
	if( !compare( oldstate, genstate))
	  lastptr++;
	genstate += 4;
      }
      stateptr[lastptr] = (unsigned int) (genstate - StateSpace);
      printf("k= %d lastptr = %d\n", k, lastptr);
      if( lastptr > 1024*1024)
      {
	printf("out of room in state file!\n");
	exit(0);
      }
      close(statefile);
      close(ptrfile);
    }

/*  follow states from end back to beginning  */

    row = 0;
    pathptr = pathblk;
    endstate = initialstate;
    for( i=0; i<lastptr; i++)
    {
      genstate = (unsigned int*)(stateptr[i] + StateSpace);
      if( compare( genstate, endstate)) continue;
      endptr = (unsigned int*)(stateptr[i+1] + StateSpace);
      endptr -= 4;
      oldstate = endptr;
      pathptr[0] = 1;
      pathptr[1] = i;  // set end state
      ptrdex = 2;
      for(k=i+1; k<lastptr; k++)
      {
	available = (unsigned int*)(stateptr[k] + StateSpace);
	if( compare( oldstate, available))
	{
	  pathptr[ptrdex] = k;
	  ptrdex++;
	  endptr = (unsigned int*)(stateptr[k+1] + StateSpace);
	  endptr -= 4;
	  oldstate =  endptr;
	  pathptr[0]++;
	  if( compare( oldstate, endstate)) break;
	}
      }
      pathptr += pathptr[0]+1;
      if(pathptr > pathblk + 16*1024*1024)
      {
	printf("you're fucked!!\n");
	exit(0);
      }
      row++;
      if( !(row % 100)) printf("row = %d\n", row);
    }
    printf("there are %d paths\n", row);
/*  scan thru all states and remove any duplicates  */

    lastpath = pathptr;
    pathptr = pathblk;
    while( pathptr < lastpath)
    {
      if( pathptr[1] == 0xDEADBEEF)
      {
	pathptr += pathptr[0]+1;
	continue;
      }
      genstate = (unsigned int*)(stateptr[pathptr[1]] + StateSpace);
      state = pathptr[pathptr[0]];
      endptr = (unsigned int*) (stateptr[state+1] + StateSpace);
      endptr -= 4;
      available =  endptr;
      if( compare( available, genstate))
      {
	for( k=1; k<=pathptr[0]; k++) pathptr[k] = 0xDEADBEEF;
	pathptr += pathptr[0]+1;
	continue;
      }
      fixptr = pathptr + pathptr[0] + 1;
      if( fixptr[1] == 0xDEADBEEF)
      {
	pathptr += pathptr[0]+1;
	continue;
      }
      oldstate = (unsigned int*)(stateptr[fixptr[1]] + StateSpace);
      if( compare( genstate, oldstate))
      {
	for( k=1; k<=fixptr[0]; k++) fixptr[k] = 0xDEADBEEF;
      }
      pathptr += pathptr[0]+1;
    }

/*  save all unique states back to disk.  Remember it's in
    backwards order. */

    printf("Save data and pointers 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);
    sprintf( filename, "%s.ptr", basename);
    ptrfile = open(filename, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR | 
		     S_IRGRP |S_IWGRP | S_IROTH );
    if(ptrfile < 0) printf("failed to create file %s\n", filename);
    k =0;
    ptrdex = 0;
    pathptr = pathblk;
    while( pathptr < lastpath)
    {
      if( pathptr[1] != 0xDEADBEEF)
      {
	write( ptrfile, &ptrdex, 4);
	for( i=1; i<=pathptr[0]; i++)
	{
	  genstate = (unsigned int*)(stateptr[pathptr[i]] + StateSpace);
	  endptr = (unsigned int*)(stateptr[pathptr[i]+1] + StateSpace);
	  endptr -= 4;
	  oldstate = endptr;
	  while( genstate<oldstate)
	  {
	    write( statefile, genstate, 16);
	    genstate += 4;
	    ptrdex++;
	  }
	}
	oldstate[3] = 0xffffffff;
	write( statefile, oldstate, 16);
	ptrdex++;
	k++;
      }
      pathptr += pathptr[0]+1;
    }
    close( statefile);
    close( ptrfile);
    printf("There are %d non duplicated states\n", k);
}