[ create a new paste ] login | about

Link: http://codepad.org/svtI3f5z    [ raw code | output | fork ]

C, pasted on Dec 6:
#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;
}


Output:
4
4
5
4
4
0


3  3  3  2  2  0  3  2  2  
1  3  1  3  0  1  1  2  0  
1  2  2  3  0  3  0  1  2  
1  1  3  3  3  2  2  0  1  
3  2  0  0  1  1  0  0  0  
2  1  2  1  3  0  2  2  0  
0  1  1  0  3  0  2  3  3  
0  3  1  2  3  3  2  1  1  
0  3  0  1  1  2  1  3  2  




took 3 seconds


Create a new paste based on this one


Comments: