/********************************************************************* * * * 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 #include #include #include #include #include #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=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); }