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