#include #include #include #include int random(int n) { int r = rand(); int r2 = r + (r >> 7) + (r >> 13); return r2 % n; } #define SIZE 100 int maze[SIZE][3]; int L[SIZE*3]; int R[SIZE*3]; bool end[SIZE*3]; #define UNDEFINED -1 void generate_maze(int n) { for (int i = 0; i < n; i++) { maze[i][0] = UNDEFINED; maze[i][1] = UNDEFINED; maze[i][2] = UNDEFINED; } // make first connection { maze[0][0] = 0; int k = random(n); if (k == 0) maze[0][1] = 1; else maze[1][0] = 1; } int l = 1; for (int empty_places = n * 3 - 2; empty_places > 0;) { // find a node with a free place int i1, j1; for (i1 = 0; i1 < n; i1++) if (maze[i1][0] != UNDEFINED && maze[i1][2] == UNDEFINED) break; if (maze[i1][1] == UNDEFINED) j1 = 1; else j1 = 2; maze[i1][j1] = 2*l; //printf("maze[%d][%d] = %d ", i1, j1, l); // find another node with int i2, j2; do { i2 = random(n); //printf(" i2 = %d ", i2); } while (maze[i2][2] != UNDEFINED); while (maze[i2][0] == UNDEFINED && maze[i2-1][0] == UNDEFINED) i2--; if (maze[i2][0] == UNDEFINED) j2 = 0; else if (maze[i2][1] == UNDEFINED) j2 = 1; else j2 = 2; maze[i2][j2] = 2*l + 1; //printf(" maze[%d][%d] = %d ", i2, j2, l); //printf("e = %d ", empty_places); if (empty_places == 2) break; bool can_go_next = false; for (int i = 0; i < n; i++) if (maze[i][0] != UNDEFINED && maze[i][2] == UNDEFINED) { can_go_next = true; break; } if (!can_go_next) { //printf(" go back\n"); maze[i1][j1] = UNDEFINED; maze[i2][j2] = UNDEFINED; } else { //printf(" okay\n"); empty_places -= 2; l++; } } for (int i = 1; i < n; i++) { if (random(2) == 1) { int h = maze[i][1]; maze[i][1] = maze[i][2]; maze[i][2] = h; } } } void print_maze(int n) { for (int i = 0; i < n; i++) printf("%2d %2d %2d\n", maze[i][0]/2, maze[i][1]/2, maze[i][2]/2); printf("\n"); } int reverse(int i) { return (i & ~1) | (~i & 1); } void fill_LR(int n) { for (int i = 0; i < n; i++) { int v0 = maze[i][0]; int v1 = maze[i][1]; int v2 = maze[i][2]; int w0 = reverse(v0); int w1 = reverse(v1); int w2 = reverse(v2); L[v0] = w1; L[v1] = w2; L[v2] = w0; R[v0] = w2; R[v1] = w0; R[v2] = w1; } for (int i = 0; i < n*3; i++) end[i] = false; end[maze[0][0]] = true; end[maze[0][1]] = true; end[maze[0][2]] = true; } void check_LR(int n) { for (int i = 0; i < n; i++) { if ( reverse(L[reverse(R[i])]) != i || reverse(R[reverse(L[i])]) != i || reverse(L[reverse(L[reverse(L[i])])]) != i || reverse(R[reverse(R[reverse(R[i])])]) != i) printf("error %d\n", i); } } void print_LR(int n) { for (int i = 0; i < n; i++) { printf("%2d: %2d %2d %s\n", i, L[i], R[i], end[i] ? "end" : ""); } printf("\n"); } int min[SIZE*3]; void print_LR_min(int n) { for (int i = 0; i < n; i++) { printf("%2d (%2d): %2d (%d) %2d (%d)\n", i, min[i], L[i], min[L[i]], R[i], min[R[i]]); } printf("\n"); } void calculate_min(int n) { for (int i = 0; i < n; i++) min[i] = end[i] ? 0 : n; for (bool modified = true; modified;) { //print_LR_min(n); //printf("--\n"); modified = false; for (int j = 0; j < n; j++) { int m = min[L[j]] + 1; if (m < min[j]) { min[j] = m; modified = true; } m = min[R[j]] + 1; if (m < min[j]) { min[j] = m; modified = true; } } } } class Stat { public: Stat() : n(0), _sum(0.0), _sum2(0.0) {} void add(double v) { if (n == 0 || v < min) min = v; if (n == 0 || v > max) max = v; n++; _sum += v; _sum2 += v*v; } double average() { if (n == 0) return 0.0; return _sum / n; } double stddev() { if (n <= 1) return 0.0; return sqrt((_sum2 - _sum*_sum/(double)n) / (double)(n)); } void print() { printf("[%lf %lf %lf] %lf", min, average(), max, stddev()); } long n; double min; double max; private: double _sum; double _sum2; }; void solve_straight(int n, long &depth, long &underway) { int pos[3*SIZE]; for (int i = 0; i < n; i++) pos[i] = i; depth = 0; underway = 0; for (;depth < 300;) { // Count number at end position int at_end = 0; for (int i = 0; i < n; i++) if (end[pos[i]]) at_end++; if (at_end == n) break; // -- we are done depth++; underway += n - at_end; // Evaluate left and right int min_L = n; int nr_at_min_L = 0; int left_L = 0; double cost_L = 0.0; int min_R = n; int nr_at_min_R = 0; int left_R = 0; double cost_R = 0.0; for (int i = 0; i < n; i++) if (!end[pos[i]]) { int m = min[L[pos[i]]]; if (m < min_L) { min_L = m; nr_at_min_L = 1; } else if (m == min_L) nr_at_min_L++; left_L += m; cost_L += sqrt(sqrt(m)); m = min[R[pos[i]]]; if (m < min_R) { min_R = m; nr_at_min_R = 1; } else if (m == min_R) nr_at_min_R++; left_R += m; cost_R += sqrt(sqrt(m)); } #define SMALLER(X,Y) (X) < (Y) ? true : (X) > (Y) ? false : #define SELECT(Z) if (Z random(2) == 0) // make selection // SELECT(SMALLER(min_L, min_R)) // SELECT(SMALLER(min_L, min_R) SMALLER(left_L, left_R)) // SELECT(SMALLER(min_L, min_R) SMALLER(nr_at_min_R, nr_at_min_L)) // SELECT(SMALLER(cost_L, cost_R)) SELECT(SMALLER(min_L, min_R) SMALLER(cost_L, cost_R)) { //printf("L"); for (int i = 0; i < n; i++) { if (!end[pos[i]]) pos[i] = L[pos[i]]; //printf(" %2d", pos[i]); } } else { //printf("R"); for (int i = 0; i < n; i++) { if (!end[pos[i]]) pos[i] = R[pos[i]]; //printf(" %2d", pos[i]); } } //printf("\n"); } //printf("%ld %lf\n", depth, ((double)underway)/(double)n); } #define WORKSET_SIZE 1000 struct State { int pos[3*SIZE]; int underway; int min; int nr_at_min; int left; double cost; }; State state_workset[WORKSET_SIZE]; State* free_states[WORKSET_SIZE]; int nr_free_states = 0; State* old_states[WORKSET_SIZE]; int nr_old = 0; State* new_states[WORKSET_SIZE]; int nr_new = 0; State* alloc_state() { if (nr_free_states > 0) return free_states[--nr_free_states]; if (nr_new > nr_old) return new_states[--nr_new]; else return old_states[--nr_old]; } void dealloc_state(State* state) { free_states[nr_free_states++] = state; } void insert_in_new_states(State* state) { for (int i = 0; i < nr_new; i++) { // SELECT(SMALLER(state->min, new_states[i]->min)) // SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->left, new_states[i]->left)) // SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->nr_at_min, new_states[i]->nr_at_min)) // SELECT(SMALLER(state->cost, new_states[i]->cost)) SELECT(SMALLER(state->min, new_states[i]->min) SMALLER(state->cost, new_states[i]->cost)) { State* h = new_states[i]; new_states[i] = state; state = h; } } if (nr_new < WORKSET_SIZE) { new_states[nr_new++] = state; } else dealloc_state(state); } void solve_with_workset(int n, long &depth, long &underway) { for (int i = 0; i < WORKSET_SIZE; i++) free_states[i] = &state_workset[i]; nr_free_states = WORKSET_SIZE; // Initialize State* init_state = alloc_state(); init_state->left = 0; for (int i = 0; i < n; i++) { init_state->pos[i] = i; if (!end[i]) init_state->left++; } init_state->underway = init_state->left; old_states[0] = init_state; nr_old = 1; // Iterate for(depth = 1; ; depth++) { for(int i = 0; i < nr_old; i++) { State* old_state = old_states[i]; if (old_state->left == 0) { underway = old_state->underway; return; } State* new_state_L = alloc_state(); if (new_state_L == old_state) { dealloc_state(old_state); break; } State* new_state_R = alloc_state(); if (new_state_R == old_state) { dealloc_state(new_state_R); dealloc_state(old_state); break; } // Evaluate left and right new_state_L->underway = old_state->underway; new_state_L->min = n; new_state_L->nr_at_min = 0; new_state_L->left = 0; new_state_L->cost = 0.0; new_state_R->underway = old_state->underway; new_state_R->min = n; new_state_R->nr_at_min = 0; new_state_R->left = 0; new_state_R->cost = 0.0; for (int j = 0; j < n; j++) { int pos = old_state->pos[j]; if (!end[pos]) { new_state_L->pos[j] = L[pos]; int m = min[L[pos]]; if (m < new_state_L->min) { new_state_L->min = m; new_state_L->nr_at_min = 1; } else if (m == new_state_L->min) new_state_L->nr_at_min++; new_state_L->underway++; new_state_L->left += m; new_state_L->cost += sqrt(sqrt(m)); new_state_R->pos[j] = R[pos]; m = min[R[pos]]; if (m < new_state_R->min) { new_state_R->min = m; new_state_R->nr_at_min = 1; } else if (m == new_state_R->min) new_state_R->nr_at_min++; new_state_R->underway++; new_state_R->left += m; new_state_R->cost += sqrt(sqrt(m)); } else { new_state_L->pos[j] = pos; new_state_R->pos[j] = pos; } } new_state_L->underway = old_state->underway + new_state_L->left; new_state_R->underway = old_state->underway + new_state_R->left; insert_in_new_states(new_state_L); insert_in_new_states(new_state_R); dealloc_state(old_state); } for (int i = 0; i < nr_new; i++) old_states[i] = new_states[i]; nr_old = nr_new; nr_new = 0; } } int main(int argc, char *argv[]) { srand(time(0)); for (int n = 10; n < 100; n += 2) { Stat depth_stat; Stat underway_stat; for (int times = 0; times < 100; times++) { generate_maze(n); //print_maze(n); fill_LR(n); int n3 = n * 3; check_LR(n3); //print_LR(n3); calculate_min(n3); //print_LR_min(n3); #ifdef STRAIGHT for (int x = 0; x < 100; x++) { long depth; long underway; solve_straight(n, depth, underway); depth_stat.add(depth); underway_stat.add((double)underway/(double)n); } #else long depth; long underway; solve_with_workset(n, depth, underway); depth_stat.add(depth); underway_stat.add((double)underway/(double)n); #endif } printf("%3d: depth: ", n); depth_stat.print(); printf(" underway: "); underway_stat.print(); printf("\n"); } return 0; }