commit 2ed29b3e942132d9a3b732f9e5a71d5c6b7d527d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 31 May 2014 23:19:18 +0200
main
Diffstat:
| main.c | | | 377 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 377 insertions(+), 0 deletions(-)
diff --git a/main.c b/main.c
@@ -0,0 +1,377 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#define MAXN 20
+#define UBOUND 10
+
+int debug = 0;
+
+int N, K;
+// z, x, y
+// height, line, col
+unsigned char G[MAXN][MAXN][MAXN];
+// attack patterns
+unsigned char A[MAXN][MAXN][MAXN];
+// rook positions (z, x, y)
+unsigned char R[MAXN*MAXN][3];
+// rook violations
+//char V[MAXN*MAXN];
+// putative violations
+unsigned char V[MAXN][MAXN][MAXN];
+
+void print() {
+ for (int x = 0; x < N; x++) {
+ for (int y = 0; y < N; y++) {
+ int pos = -1;
+ for (int z = 0; z < N; z++) {
+ if (G[z][x][y]) {
+ pos = z;
+ break;
+ }
+ }
+ if (pos < 0)
+ printf("* ");
+ else {
+ if (pos < 9)
+ printf("%d ", pos + 1);
+ else
+ printf("%c ", 'A' + (pos - 9));
+ }
+ }
+ printf("\n");
+ }
+ if (debug) {
+ for (int i = 0; i < K; i++)
+ printf("rook %d at %d %d %d\n", i, R[i][1], R[i][2], R[i][0]);
+ }
+}
+
+void print_attacks() {
+ for (int z = 0; z < N; z++) {
+ printf("== %d ==\n", z);
+ for (int x = 0; x < N; x++) {
+ for (int y = 0; y < N; y++) {
+ int val = A[z][x][y];
+ printf("%d%d%d ", val & (1 << 0), (val & (1 << 1))>>1, (val& (1 << 2))>>2);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ }
+}
+
+void print_all_violations() {
+ for (int z = 0; z < N; z++) {
+ printf("== %d ==\n", z);
+ for (int x = 0; x < N; x++) {
+ for (int y = 0; y < N; y++) {
+ int val = V[z][x][y];
+ printf("%d ", val);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ }
+}
+
+void print_violations() {
+ int tot = 0;
+ for (int i = 0; i < K; i++) {
+ int val = V[R[i][0]][R[i][1]][R[i][2]];
+ printf("rook %d has %d violations\n", i,
+ val);
+ tot += val;
+ }
+ printf("=> %d total violations\n", tot);
+}
+
+void upd_atk_rm(int i) {
+ int z = R[i][0];
+ int x = R[i][1];
+ int y = R[i][2];
+ for (int p = 0; p < N; p++) {
+ A[p][x][y] &= ~(1 << 0);
+ A[z][p][y] &= ~(1 << 1);
+ A[z][x][p] &= ~(1 << 2);
+ }
+}
+
+void upd_atk_add(int i) {
+ int z = R[i][0];
+ int x = R[i][1];
+ int y = R[i][2];
+ for (int p = 0; p < N; p++) {
+ A[p][x][y] |= 1 << 0;
+ A[z][p][y] |= 1 << 1;
+ A[z][x][p] |= 1 << 2;
+ }
+}
+
+
+void num_attacks() {
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++)
+ A[i][j][k] = 0;
+ for (int i = 0; i < K; i++) {
+ if (R[i][0] < MAXN)
+ upd_atk_add(i);
+ }
+}
+
+
+
+void check_attacks() {
+ int backup[MAXN][MAXN][MAXN];
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++)
+ backup[i][j][k] = A[i][j][k];
+ num_attacks();
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++)
+ if (backup[i][j][k] != A[i][j][k]) {
+ print_attacks();
+ printf("ERROR at %d %d %d\n", i, j, k);
+ exit(1);
+ }
+}
+
+
+int num_violations() {
+ int tot = 0;
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++)
+ V[i][j][k] = 0;
+ for (int z = 0; z < N; z++)
+ for (int x = 0; x < N; x++)
+ for (int y = 0; y < N; y++) {
+ for (int p = 0; p < N; p++) {
+ if (p != z && (A[p][x][y] | (1 << 0)) == 7)
+ {V[z][x][y]++;}
+ if (p != x && (A[z][p][y] | (1 << 1)) == 7)
+ {V[z][x][y]++;}
+ if (p != y && (A[z][x][p] | (1 << 2)) == 7)
+ {V[z][x][y]++;}
+ }
+ if (G[z][x][y]) {
+ tot += V[z][x][y];
+ //printf("add %d to num_violations for %d %d %d\n", V[z][x][y], x, y, z);
+ }
+ }
+ return tot;
+}
+
+// int tot = 0;
+// for (int i = 0; i < K; i++) {
+// V[i] = 0;
+// int z = R[i][0];
+// int x = R[i][1];
+// int y = R[i][2];
+// for (int p = 0; p < N; p++) {
+// if (p != z && A[p][x][y] == 7)
+// {V[i]++; tot++;}
+// if (p != x && A[z][p][y] == 7)
+// {V[i]++; tot++;}
+// if (p != y && A[z][x][p] == 7)
+// {V[i]++; tot++;}
+// }
+// }
+
+void init_pos() {
+ // initial position
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++)
+ G[i][j][k] = 0;
+ int remaining = K;
+ int height = 0, pos = 0;
+ while (remaining > 0) {
+ int z = height;
+ int x = pos;
+ int y = (pos + height) % N;
+ G[z][x][y] = 1;
+ remaining--;
+ R[remaining][0] = z;
+ R[remaining][1] = x;
+ R[remaining][2] = y;
+ pos++;
+ if (pos >= N) {
+ pos = 0;
+ height++;
+ }
+ }
+}
+
+int choose_rook(int prev) {
+ int best = -1;
+ int nvs[MAXN*MAXN];
+ int nnvs = 0;
+ int nv;
+ for (int i = 0; i < K; i++) {
+ if (i == prev)
+ continue;
+ if ((nv = V[R[i][0]][R[i][1]][R[i][2]]) > best) {
+ best = nv;
+ }
+ }
+ for (int i = 0; i < K; i++) {
+ if (i == prev)
+ continue;
+ if ((nv = V[R[i][0]][R[i][1]][R[i][2]]) == best) {
+ nvs[nnvs++] = i;
+ }
+ }
+ return nvs[rand() % nnvs];
+}
+
+void random_move() {
+ int rook = (rand() % K);
+ //printf("move %d at random\n", rook);
+ int z = R[rook][0];
+ int x = R[rook][1];
+ int y = R[rook][2];
+ G[z][x][y] = 0;
+ upd_atk_rm(rook);
+ int nx, ny, nz;
+ while (1) {
+ nx = (rand() % N);
+ ny = (rand() % N);
+ nz = (rand() % N);
+ if (!A[nz][nx][ny] && !G[nz][nx][ny])
+ break;
+ }
+ G[nz][nx][ny] = 1;
+ R[rook][0] = nz;
+ R[rook][1] = nx;
+ R[rook][2] = ny;
+ num_attacks();
+ num_violations();
+}
+
+void position(int i) {
+ int best = N*N*N+1;
+ int bs[MAXN*MAXN*MAXN][3];
+ int nbs = 0;
+ for (int z = 0; z < N; z++)
+ for (int x = 0; x < N; x++)
+ for (int y = 0; y < N; y++)
+ if (!A[z][x][y] && !G[z][x][y])
+ if (V[z][x][y] < best) {
+ best = V[z][x][y];
+ }
+ for (int z = 0; z < N; z++)
+ for (int x = 0; x < N; x++)
+ for (int y = 0; y < N; y++)
+ if (!A[z][x][y] && !G[z][x][y])
+ if (V[z][x][y] == best) {
+ bs[nbs][0] = z;
+ bs[nbs][1] = x;
+ bs[nbs][2] = y;
+ nbs++;
+ if (debug) printf("%d %d %d is a fitting position\n", z, x, y);
+ }
+ int npos = rand() % nbs;
+ int bz = bs[npos][0];
+ int bx = bs[npos][1];
+ int by = bs[npos][2];
+ if(debug) printf("position %d to %d %d %d with viol %d\n", i, bx, by, bz, V[bz][by][by]);
+ G[bz][bx][by] = 1;
+ R[i][0] = bz;
+ R[i][1] = bx;
+ R[i][2] = by;
+ upd_atk_add(i);
+}
+
+void spawn_rook() {
+ position(K-1);
+}
+
+
+int main(int argc, char **argv) {
+ int oK;
+ int first = 1;
+ int seed;
+ N = atoi(argv[1]);
+ oK = atoi(argv[2]);
+ if (argc == 4)
+ seed = atoi(argv[3]);
+ else {
+ seed = time(NULL);
+ }
+ printf("using random seed %d\n", seed);
+ srand(seed);
+ int tot;
+ for (K = oK; K < N*N; K++) {
+ printf("try %d rooks\n", K);
+ if (first) {
+ init_pos();
+ first = 0;
+ } else {
+ spawn_rook();
+ }
+ num_attacks();
+ tot = num_violations();
+ print();
+ //print_attacks();
+ //print_violations();
+ int useless1 = 0, useless2 = 0;
+ int prev_raw = -1;
+ while (tot > 0) {
+ if (debug) print_violations();
+ int rook = choose_rook(prev_raw);
+ prev_raw = rook;
+ // when doing a useless step, offset the choice
+ //rook = (rook + useless1) % K;
+ if(debug) printf("chosen rook %d yields %d\n", prev_raw, rook);
+ if(debug) print();
+ if(debug) print_attacks();
+ int z = R[rook][0];
+ int x = R[rook][1];
+ int y = R[rook][2];
+ G[z][x][y] = 0;
+ upd_atk_rm(rook);
+ R[rook][0] = MAXN;
+ R[rook][1] = MAXN;
+ R[rook][2] = MAXN;
+ if(debug) print_attacks();
+ if(debug) check_attacks();
+ num_violations();
+ position(rook);
+ int otot = tot;
+ int pred = V[R[rook][0]][R[rook][1]][R[rook][2]];
+ if(debug) print();
+ if(debug) print_all_violations();
+ tot = num_violations();
+ if(debug) print_all_violations();
+ int npred = V[R[rook][0]][R[rook][1]][R[rook][2]];
+ if (npred != pred) {
+ printf("violation mispredict: thought %d and had %d!\n", pred, npred);
+ exit(1);
+ }
+ if(debug) print_violations();
+ if(debug) print_attacks();
+ if(debug) print();
+ //printf("total viol %d\n", tot);
+ if (tot >= otot) {
+ // no improvement
+ useless1++;
+ useless2++;
+ } else {
+ useless1 = useless2 = 0;
+ }
+ if (useless1 > UBOUND || useless2 > UBOUND) {
+ useless1 = useless2 = 0;
+ random_move();
+ }
+ }
+ printf("!!! DONE %d rooks\n", K);
+ print();
+ }
+ return 0;
+}
+
+
