commit 91f6b1d21fef43a2cc155c34edae3cb0683ecf35
parent 9e8f1fd929ec3c8e061d82081b1a0dcd0a02c910
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 10 Jun 2014 18:14:24 +0200
Merge gitorious.org:crooks/arcaseus-crooks
Diffstat:
| extract.sh | | | 0 | |
| main.c | | | 343 | +++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------- |
| run.sh | | | 7 | +++---- |
3 files changed, 236 insertions(+), 114 deletions(-)
diff --git a/extract.sh b/extract.sh
diff --git a/main.c b/main.c
@@ -2,6 +2,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
+#include <inttypes.h>
// compilation:
// gcc -std=c99 -O2 -Wall main.c
@@ -24,9 +25,9 @@
// TODO: optimize UBOUND
// upper bound on grid size (N) for static allocation
-#define MAXN 20
+#define MAXN 64
// number of useless steps to make before doing a random move
-#define UBOUND 30
+#define UBOUND 10
// C1/C2 is the probability of going on doing an additional random move
#define C1 3
@@ -52,6 +53,46 @@ unsigned char R[MAXN*MAXN][3];
// other rooks) for each cell (no matter whether it contains a rook or not)
unsigned char V[MAXN][MAXN][MAXN];
+// proj_xy[i]&(1<<j) is true, iff there is a rook of coordinates
+// (x=i, y=j, z=anything)
+// In other words, it is the projection along the z axis giving a matrice of
+// booleans, with the booleans then grouped in bitfields along the y axis.
+// Similarily for the others.
+uint64_t proj_xy[MAXN];
+uint64_t proj_xz[MAXN];
+uint64_t proj_yx[MAXN];
+uint64_t proj_yz[MAXN];
+uint64_t proj_zx[MAXN];
+uint64_t proj_zy[MAXN];
+// v_zx[k][i] is the number of cases already attacked in both the z and the
+// x direction, in the line with coordinates (z=k, x=i).
+// Interesting invariants: v_zx[z][x] = popcount(proj_xy[x] & proj_zy[z])
+// V[z][x][y] = v_zx[z][x] + v_xy[x][y] + v_zy[z][y]
+uint8_t v_zx[MAXN][MAXN];
+uint8_t v_xy[MAXN][MAXN];
+uint8_t v_zy[MAXN][MAXN];
+
+void print();
+
+int popcount64(uint64_t bitfield) {
+ return __builtin_popcountll((unsigned long long) bitfield);
+}
+
+int getVEmpty(int z, int x, int y) {
+ int result;
+ result = (v_zx[z][x] + v_xy[x][y] + v_zy[z][y]);
+ return result;
+}
+
+// TODO: optimise in position where we know that !G[z][x][y]
+int getV(int z, int x, int y) {
+ int result;
+ result = getVEmpty(z, x, y);
+ if (G[z][x][y])
+ result -= 3; // Do not count a rook as being in violation with itself.
+ return result;
+}
+
void intHandler() {
// needed for profiling
printf("SIGINT caught, exiting\n");
@@ -128,53 +169,60 @@ void print_violations() {
printf("=> %d total violations\n", tot);
}
-int upd_vio(int z, int x, int y, int v, int d) {
- int delta = 0;
- int old = A[z][x][y];
- int val, new;
- if (v > 0)
- new = A[z][x][y] | (1 << d);
- else
- new = A[z][x][y] & ~(1 << d);
- if (old == new)
- return 0; // nothing changed
- for (int p = 0; p < N; p++) {
- if (p != z) {
- val = ((new | (1 << 0)) == 7 ? 1 : 0) - ((old | (1 << 0)) == 7 ? 1 : 0);
- V[p][x][y] += val;
- if (G[p][x][y]) delta += val;
- }
- if (p != x) {
- val = ((new | (1 << 1)) == 7 ? 1 : 0) - ((old | (1 << 1)) == 7 ? 1 : 0);
- V[z][p][y] += val;
- if (G[z][p][y]) delta += val;
- }
- if (p != y) {
- val = ((new | (1 << 2)) == 7 ? 1 : 0) - ((old | (1 << 2)) == 7 ? 1 : 0);
- V[z][x][p] += val;
- if (G[z][x][p]) delta += val;
- }
- }
- return delta;
-}
-
int upd_atk_rm(int i) {
// update A to reflect the fact that rook i is about to be removed
int z = R[i][0];
int x = R[i][1];
int y = R[i][2];
- //printf("rmv rook at %d %d %d\n", z, x, y);
- int delta = 0;
+ uint64_t mask_z = 1ull << z;
+ uint64_t mask_x = 1ull << x;
+ uint64_t mask_y = 1ull << y;
+ uint64_t old_vzx1, old_vzx2, old_vzy1, old_vzy2, old_vxy1, old_vxy2;
+ proj_xy[x] &= ~mask_y;
+ proj_xz[x] &= ~mask_z;
+ proj_yx[y] &= ~mask_x;
+ proj_yz[y] &= ~mask_z;
+ proj_zx[z] &= ~mask_x;
+ proj_zy[z] &= ~mask_y;
+
+//printf("rmv rook at %d %d %d\n", z, x, y);
+ int new_delta = 0;
for (int p = 0; p < N; p++) {
- delta += upd_vio(p, x, y, -1, 0);
A[p][x][y] &= ~(1 << 0); // p x y attacked by z x y along direction z
- delta += upd_vio(z, p, y, -1, 1);
A[z][p][y] &= ~(1 << 1); // z p y attacked by z x y along direction x
- delta += upd_vio(z, x, p, -1, 2);
A[z][x][p] &= ~(1 << 2); // z x p attacked by z x y along direction y
+
+// Interesting invariants: v_zx[z][x] = popcount(proj_xy[x] & proj_zy[z])
+// v_zy[z][y] = popcount(proj_yx[y] & proj_zx[z])
+// v_xy[x][y] = popcount(proj_yz[y] & proj_xz[x]);
+ // TODO: refactor
+ old_vzx1 = v_zx[z][p];
+ old_vzx2 = v_zx[p][x];
+ old_vzy1 = v_zy[z][p];
+ old_vzy2 = v_zy[p][y];
+ old_vxy1 = v_xy[x][p];
+ old_vxy2 = v_xy[p][y];
+ v_zx[z][p] = popcount64(proj_xy[p] & proj_zy[z]);
+ v_zx[p][x] = popcount64(proj_xy[x] & proj_zy[p]);
+ v_zy[z][p] = popcount64(proj_yx[p] & proj_zx[z]);
+ v_zy[p][y] = popcount64(proj_yx[y] & proj_zx[p]);
+ v_xy[x][p] = popcount64(proj_yz[p] & proj_xz[x]);
+ v_xy[p][y] = popcount64(proj_yz[y] & proj_xz[p]);
+ if (proj_xz[p] & mask_z)
+ new_delta += v_zx[z][p] - old_vzx1;
+ if (proj_zx[p] & mask_x)
+ new_delta += v_zx[p][x] - old_vzx2;
+ if (proj_yz[p] & mask_z)
+ new_delta += v_zy[z][p] - old_vzy1;
+ if (proj_zy[p] & mask_y)
+ new_delta += v_zy[p][y] - old_vzy2;
+ if (proj_yx[p] & mask_x)
+ new_delta += v_xy[x][p] - old_vxy1;
+ if (proj_xy[p] & mask_y)
+ new_delta += v_xy[p][y] - old_vxy2;
}
- delta -= V[z][x][y];
- return delta;
+ new_delta -= getV(z, x, y);
+ return new_delta;
}
int upd_atk_add(int i) {
@@ -182,18 +230,60 @@ int upd_atk_add(int i) {
int z = R[i][0];
int x = R[i][1];
int y = R[i][2];
+ uint64_t mask_z = 1ull << z;
+ uint64_t mask_x = 1ull << x;
+ uint64_t mask_y = 1ull << y;
+ uint64_t old_vzx1, old_vzx2, old_vzy1, old_vzy2, old_vxy1, old_vxy2;
+ proj_xy[x] |= mask_y;
+ proj_xz[x] |= mask_z;
+ proj_yx[y] |= mask_x;
+ proj_yz[y] |= mask_z;
+ proj_zx[z] |= mask_x;
+ proj_zy[z] |= mask_y;
//printf("added rook at %d %d %d\n", z, x, y);
- int delta = 0;
+ int new_delta = 0;
for (int p = 0; p < N; p++) {
- delta += upd_vio(p, x, y, 1, 0);
A[p][x][y] |= 1 << 0;
- delta += upd_vio(z, p, y, 1, 1);
A[z][p][y] |= 1 << 1;
- delta += upd_vio(z, x, p, 1, 2);
A[z][x][p] |= 1 << 2;
+
+// Interesting invariants: v_zx[z][x] = popcount(proj_xy[x] & proj_zy[z])
+// v_zy[z][y] = popcount(proj_yx[y] & proj_zx[z])
+// v_xy[x][y] = popcount(proj_yz[y] & proj_xz[x]);
+ // TODO: refactor
+ old_vzx1 = v_zx[z][p];
+ old_vzx2 = v_zx[p][x];
+ old_vzy1 = v_zy[z][p];
+ old_vzy2 = v_zy[p][y];
+ old_vxy1 = v_xy[x][p];
+ old_vxy2 = v_xy[p][y];
+ v_zx[z][p] = popcount64(proj_xy[p] & proj_zy[z]);
+ v_zx[p][x] = popcount64(proj_xy[x] & proj_zy[p]);
+ v_zy[z][p] = popcount64(proj_yx[p] & proj_zx[z]);
+ v_zy[p][y] = popcount64(proj_yx[y] & proj_zx[p]);
+ v_xy[x][p] = popcount64(proj_yz[p] & proj_xz[x]);
+ v_xy[p][y] = popcount64(proj_yz[y] & proj_xz[p]);
+ if (p != z) {
+ if (proj_zx[p] & mask_x)
+ new_delta += v_zx[p][x] - old_vzx2;
+ if (proj_zy[p] & mask_y)
+ new_delta += v_zy[p][y] - old_vzy2;
+ }
+ if (p != x) {
+ if (proj_xz[p] & mask_z)
+ new_delta += v_zx[z][p] - old_vzx1;
+ if (proj_xy[p] & mask_y)
+ new_delta += v_xy[p][y] - old_vxy2;
+ }
+ if (p != y) {
+ if (proj_yz[p] & mask_z)
+ new_delta += v_zy[z][p] - old_vzy1;
+ if (proj_yx[p] & mask_x)
+ new_delta += v_xy[x][p] - old_vxy1;
+ }
}
- delta += V[z][x][y];
- return delta;
+ new_delta += getV(z, x, y);
+ return new_delta;
}
void num_attacks() {
@@ -208,6 +298,24 @@ void num_attacks() {
}
}
+void check_attacks() {
+ // debug: regenerate A from scratch
+ // and check that the previous version was already correct
+ 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() {
// regenerate V from scratch
@@ -319,15 +427,11 @@ int choose_rook(int prev) {
for (int i = 0; i < K; i++) {
if (i == prev)
continue;
- if ((nv = V[R[i][0]][R[i][1]][R[i][2]]) > best) {
+ if ((nv = getV(R[i][0], R[i][1], R[i][2])) > best) {
best = nv;
- }
- }
- // best is now the maximal num of violations
- 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[0] = i;
+ nnvs = 1;
+ } else if (nv == best) {
nvs[nnvs++] = i;
}
}
@@ -346,15 +450,24 @@ int random_move() {
G[z][x][y] = 0;
delta += upd_atk_rm(rook);
int nx, ny, nz;
- while (1) {
+ uint64_t mask_x, mask_y;
+ do {
nx = (rand() % N);
ny = (rand() % N);
nz = (rand() % N);
- if (!A[nz][nx][ny] && !G[nz][nx][ny])
+ mask_x = 1ull << x;
+ mask_y = 1ull << y;
+ if (!A[nz][nx][ny] && !G[nz][nx][ny]) {
+#if 0
+ printf("proj_zy[nz]:%lx, mask_y: %lx:%lx -- ", proj_zy[nz], mask_y, proj_zy[nz] & mask_y);
+ printf("proj_xy[nx]:%lx, mask_y: %lx:%lx -- ", proj_xy[nx], mask_y, proj_xy[nx] & mask_y);
+ printf("proj_zx[nz]:%lx, mask_x: %lx:%lx\n", proj_zx[nz], mask_x, proj_zx[nz] & mask_x);
+#endif
break; // found a spot that's both empty and not in direct attack
+ }
// TODO: nothing tests if this loop stands a chance of terminating, it would
// be neater to exit the program then
- }
+ } while (1); // ((proj_zy[nz] & mask_y) || (proj_xy[nx] & mask_y) || (proj_zx[nz] & mask_x));
G[nz][nx][ny] = 1;
R[rook][0] = nz;
R[rook][1] = nx;
@@ -364,56 +477,70 @@ int random_move() {
}
int position(int i) {
- // position rook i that was just removed
- // TODO: more efficient (pqueue?)
- // TODO more clever (chance to select cell with non-optimal number of
- // violations)
- 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];
- nbs = 0;
- }
- 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);
- }
- }
- // choose random cell among optimal ones
- 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;
- return upd_atk_add(i);
-}
-
-void spawn_rook() {
- // add a new rook to the problem
- position(K-1);
+ // position rook i that was just removed
+ // TODO: more efficient (pqueue?)
+ // TODO more clever (chance to select cell with non-optimal number of
+ // violations)
+ int best = N*N*N+1;
+ int bs[MAXN*MAXN*MAXN][3];
+ int nbs = 0;
+ int v_zxy;
+ uint64_t mask_x, mask_y;
+ for (int z = 0; z < N; z++) {
+ for (int x = 0; x < N; x++) {
+ mask_x = 1ull << x;
+ if((proj_zx[z] & mask_x) || (v_zx[z][x] > best))
+ {continue;}
+ for (int y = 0; y < N; y++) {
+ mask_y = 1ull << y;
+ if ((proj_zy[z] | proj_xy[x]) & mask_y)
+ {continue;}
+ // getVEmpty, because we know that the cell is
+ // not attacked, thus empty.
+ v_zxy = getVEmpty(z, x, y);
+ if (v_zxy < best) {
+ best = v_zxy;
+ bs[0][0] = z;
+ bs[0][1] = x;
+ bs[0][2] = y;
+ nbs = 1;
+ if (debug)
+ printf("%d %d %d is a fitting position\n", z, x, y);
+ }
+ else if (v_zxy == 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);
+ }
+ }
+ }
+ }
+ // choose random cell among optimal ones
+ 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, getV(bz, by, bx));
+ G[bz][bx][by] = 1;
+ R[i][0] = bz;
+ R[i][1] = bx;
+ R[i][2] = by;
+ return upd_atk_add(i);
}
-
int main(int argc, char **argv) {
int oK;
+ int stopK;
int first = 1;
int seed;
N = atoi(argv[1]);
oK = atoi(argv[2]);
- if (argc == 4)
- seed = atoi(argv[3]);
+ stopK = atoi(argv[3]);
+ if (argc == 5)
+ seed = atoi(argv[4]);
else {
seed = time(NULL);
}
@@ -421,24 +548,20 @@ int main(int argc, char **argv) {
srand(seed);
signal(SIGINT, intHandler);
- int tot;
- for (K = oK; K < N*N; K++) {
+ int tot, otot;
+ for (K = oK; K < stopK; K++) {
printf("try %d rooks\n", K);
// starting position if we just started, otherwise add the rook to the
// existing position
if (first) {
init_pos();
first = 0;
+ num_attacks();
+ tot = num_violations();
} else {
- spawn_rook();
+ tot += position(K-1);
}
- // compute number of attacks and violations
- num_attacks();
- tot = num_violations();
- //check_increment();
- //print();
-
int useless = 0;
int prev_rook = -1;
@@ -462,6 +585,7 @@ int main(int argc, char **argv) {
// remove the rook
//printf("tot is %d will rm %d\n", tot, rook);
G[z][x][y] = 0;
+ otot = tot;
tot += upd_atk_rm(rook);
//printf("tot is %d after rm\n", tot);
R[rook][0] = MAXN;
@@ -470,7 +594,7 @@ int main(int argc, char **argv) {
if(debug) print_attacks();
//check_increment();
-
+
// recompute V without the rook
//num_violations();
//printf("check_incr\n");
@@ -479,7 +603,6 @@ int main(int argc, char **argv) {
// choose next position
tot += 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();
@@ -497,7 +620,7 @@ int main(int argc, char **argv) {
if(debug) print_attacks();
if(debug) print();
//printf("total viol %d\n", tot);
-
+
if (tot >= otot) {
// no improvement at this round
useless++;
diff --git a/run.sh b/run.sh
@@ -1,10 +1,9 @@
#!/bin/bash
-FILE="tmp/main_${1}.c"
+FILE="main.c"
PROG="tmp/rooks$1"
OUT="tmp/out$1"
-cat main.c | sed 's/define MAXN.*/define MAXN '$1'/' > $FILE
-gcc -std=c99 -O2 -o $PROG $FILE
-$PROG $1 1 > $OUT &
+gcc -std=c99 -O3 -march=native -o $PROG $FILE
+$PROG $1 1 9999 > $OUT &
PID="$!"
sleep $2
kill $PID
