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