codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <time.h> #include <stdio.h> #include <stdlib.h> #define DIM 9 #define BIT(b) (1 << b) #define checkBit(x,b) ((x & BIT(b))) == BIT(b)) #define setBit(x,b) x |= BIT(b) #define clearBit(x,b) x &= ~BIT(b) #define clearBits(i,j) clearBit(q[i][0], j);\ clearBit(q[i][1], j);\ clearBit(q[i][2], j);\ clearBit(q[i][3], j) int estimative=DIM*DIM/4; int lastci, lastcj, oldvalue; void displayq(unsigned int q[DIM][4]) { int i, j, c; for(i=0; i<DIM; i++) { for(j=0; j<DIM; j++) { for(c=0; c<4; c++) { if ((q[i][c] & (1 << j)) == (1 << j)) { printf("%d ", c); break; } } } printf("\n"); } printf("\n\n"); } unsigned int rectCount(unsigned int q[DIM][4]) { int rects = 0; int ci=-1, cj=-1; int i, j; int c, cc, p; unsigned int r; int newvalue; static int coll[DIM]; int colp; for(i=0; i<DIM-1; i++) { for(j=i+1; j<DIM; j++) { colp=0; for(c=0; c<4; c++) { cc = 0; r = q[i][c] & q[j][c]; p = 0; while (r) { if (r & 0x1u) { cc++; coll[colp++]=p; } r = (r >> 1); p++; } if (cc >= 2) { rects += cc*(cc - 1)/2; int row = ((rand()%2 == 0) ? i : j); int col = coll[rand()%colp]; if (ci < 0) { if (rand() % estimative == 0) { ci = row; cj = col; } } lastci = row; lastcj = col; } } } } // if at least one rect was found, try changing one of it's vertex value if (rects > 0) { if (ci >= 0) { lastci = ci; lastcj = cj; } for(c=0; c<4; c++) { if ((q[lastci][c] & (1 << lastcj)) == (1 << lastcj)) { break; } } oldvalue = c; do { newvalue=rand()%4; } while (newvalue == oldvalue); clearBits(lastci, lastcj); setBit(q[lastci][newvalue], lastcj); } estimative = rects; return rects; } int main(int argc, char *argv[]) { unsigned int q[DIM][4]; int i, j; int count, oldCount; int notbetter; int run; int r1, r2; time_t start = time(NULL); srand(start); for(i=0; i<DIM; i++) { q[i][0] = 0; q[i][1] = 0; q[i][2] = 0; q[i][3] = 0; } do { notbetter=0; run=0; for(i=0; i<DIM; i++) { for(j=0; j<DIM; j++) { r1 = rand() % 4; clearBits(i, j); setBit(q[i][r1], j); } } oldCount=rectCount(q); do { count=rectCount(q); // printf("%6d\t%4d\t%d\n", run, notbetter, oldCount, count); if (count >= oldCount) { if (count > oldCount) { // it got worst, restore as it was before clearBits(lastci, lastcj); setBit(q[lastci][oldvalue], lastcj); count = oldCount; } if (notbetter++ > 15) { // it's not improving, do some random changes (AKA mutation) for(i=0; i<run/10000; i++) { r1=rand()%DIM; r2=rand()%DIM; clearBits(r1, r2); setBit(q[r1][rand()%4], r2); r1=rand()%DIM; r2=rand()%DIM; clearBits(r1, r2); setBit(q[r1][rand()%4], r2); } notbetter = 0; } } else { notbetter = 0; } oldCount = count; } while((count > 0) && (run++ < 50000)); printf("%d\n", count); fflush(stdin); if (count == 0) { printf("\n\n"); displayq(q); } } while(count != 0); printf("\n\ntook %d seconds\n", time(NULL) - start); return 0; }
Private
[
?
]
Run code
Submit