commit 8729df936060e870fdda89e0242179fc5ef6707d
parent 1cd7bbf5aba3a968c6ffbac5e4d1cbe65f538d90
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 7 Jun 2014 19:21:27 +0200
update violations incrementally
Diffstat:
| main.c | | | 131 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- |
1 file changed, 100 insertions(+), 31 deletions(-)
diff --git a/main.c b/main.c
@@ -117,31 +117,72 @@ void print_violations() {
printf("=> %d total violations\n", tot);
}
-void upd_atk_rm(int i) {
+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);
+ 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;
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
}
+ delta -= V[z][x][y];
+ return delta;
}
-void upd_atk_add(int i) {
+int upd_atk_add(int i) {
// update A to reflect the fact that rook i was just added
int z = R[i][0];
int x = R[i][1];
int y = R[i][2];
+ //printf("added rook at %d %d %d\n", z, x, y);
+ int 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;
}
+ delta += V[z][x][y];
+ return delta;
}
-
void num_attacks() {
// generate A from scratch
for (int i = 0; i < N; i++)
@@ -155,26 +196,6 @@ 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
// returns total number of violations
@@ -205,6 +226,48 @@ int num_violations() {
return tot;
}
+void check_increment(int ntot) {
+ //printf("CHECK: before\n");
+ //print_all_violations();
+ // debug: regenerate A, V from scratch
+ // and check that the previous version was already correct
+ int backupA[MAXN][MAXN][MAXN];
+ int backupV[MAXN][MAXN][MAXN];
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++) {
+ backupA[i][j][k] = A[i][j][k];
+ backupV[i][j][k] = V[i][j][k];
+ }
+ num_attacks();
+ int rntot = num_violations();
+ //printf("CHECK: after\n");
+ //print_all_violations();
+ for (int i = 0; i < N; i++)
+ for (int j = 0; j < N; j++)
+ for (int k = 0; k < N; k++) {
+ if (backupA[i][j][k] != A[i][j][k]) {
+ print_attacks();
+ printf("ERROR attacks at %d %d %d\n", i, j, k);
+ exit(1);
+ }
+ if (backupV[i][j][k] != V[i][j][k]) {
+ print();
+ print_attacks();
+ print_all_violations();
+ printf("ERROR violations at z=%d x=%d y=%d, had %d computed %d\n", i, j, k, backupV[i][j][k], V[i][j][k]);
+ exit(1);
+ }
+ }
+ if (ntot != rntot) {
+ print_all_violations();
+ print_violations();
+ printf("total violation miscount, had %d computed %d\n", ntot, rntot);
+ exit(1);
+ }
+}
+
+
void init_pos() {
// create initial position
for (int i = 0; i < N; i++)
@@ -283,11 +346,12 @@ int random_move() {
R[rook][1] = nx;
R[rook][2] = ny;
// recompute everything
+ // TODO: don't do this
upd_atk_add(rook);
return num_violations();
}
-void position(int i) {
+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
@@ -324,7 +388,7 @@ void position(int i) {
R[i][0] = bz;
R[i][1] = bx;
R[i][2] = by;
- upd_atk_add(i);
+ return upd_atk_add(i);
}
void spawn_rook() {
@@ -362,6 +426,7 @@ int main(int argc, char **argv) {
// compute number of attacks and violations
num_attacks();
tot = num_violations();
+ //check_increment();
//print();
int useless = 0;
@@ -385,20 +450,24 @@ int main(int argc, char **argv) {
int y = R[rook][2];
// remove the rook
+ //printf("tot is %d will rm %d\n", tot, rook);
G[z][x][y] = 0;
- upd_atk_rm(rook);
+ tot += upd_atk_rm(rook);
+ //printf("tot is %d after rm\n", tot);
R[rook][0] = MAXN;
R[rook][1] = MAXN;
R[rook][2] = MAXN;
if(debug) print_attacks();
- //check_attacks();
+ //check_increment();
// recompute V without the rook
- num_violations();
+ //num_violations();
+ //printf("check_incr\n");
+ //check_increment(tot);
// choose next position
- position(rook);
+ tot += position(rook);
int otot = tot;
int pred = V[R[rook][0]][R[rook][1]][R[rook][2]];
@@ -406,11 +475,11 @@ int main(int argc, char **argv) {
if(debug) print_all_violations();
// recompute number of violations
- tot = num_violations();
+ //tot = num_violations();
if(debug) print_all_violations();
int npred = V[R[rook][0]][R[rook][1]][R[rook][2]];
- if (debug && npred != pred) {
+ if (npred != pred) {
printf("violation mispredict: thought %d and had %d!\n", pred, npred);
exit(1);
}
