#include #include class RandomU32Generator { // Based on: http://my.opera.com/metrallik/blog/2013/04/19/c-class-for-random-generation-with-mersenne-twister-method public: RandomU32Generator(unsigned long seed = 10){ mt[0]=seed; for(unsigned long i=1;i>30))+i)&bitMask_32; idx = 0; } unsigned long get() { if(idx==0) gen(); unsigned long y=mt[idx]; y^= y>>11; y^=(y<< 7)&2636928640L; y^=(y<<15)&4022730752L; y^= y>>18; idx=(idx+1)%length; return y&bitMask_32; } void gen() { for(int i=0;i>1); if(y%2) mt[i]^=2567483615L; } return; } private: static const int length=624; static const unsigned long bitMask_32=0xffffffff; static const unsigned long bitPow_31=1L<<31; unsigned long mt[length]; unsigned long idx; }; class RandomBoolGenerator { public: RandomBoolGenerator() : _randomU32Generator(13), _i(0) { _r = _randomU32Generator.get(); } bool get() { if (++_i > 31) { _r = _randomU32Generator.get(); _i = 0; } return ((_r >> _i) & 1) == 0; } private: RandomU32Generator _randomU32Generator; int _i; unsigned long _r; }; RandomBoolGenerator randomBoolGenerator; class BooleanMatrix { public: BooleanMatrix(int n, int m) : _n(n), _m(m) { _len = _n * _m; _a = new bool[_len]; reset(); } ~BooleanMatrix() { delete[] _a; } bool get(int i, int j) { return _a[i + j*_n]; } void set(int i, int j) { _a[i + j*_n] = true; } void reset(int i, int j) { _a[i + j*_n] = false; } void reset() { for (int i = 0; i < _len; i++) _a[i] = false; } private: int _n; int _m; unsigned long _len; bool *_a; }; const int N = 1000; class Edge { public: Edge(int n_x, int n_y, char n_dir) : x(n_x), y(n_y), dir(n_dir), next(0), prev(0), opposing(0) {} Edge *next; Edge *prev; Edge *opposing; long x; long y; char dir; class Element { public: Element() : edge(0), index(-1), length(-1), visited(false) {} Edge *edge; int index; long long length; bool visited; }; Element elements[N]; void* operator new(size_t size) { if (_alloced == 0) return malloc(size); void *result = _alloced; _alloced = *(void**)_alloced; return result; } void operator delete(void* p, size_t size) { *(void**)p = _alloced; _alloced = p; } private: static void* _alloced; }; void* Edge::_alloced = 0; BooleanMatrix maze(N, N); BooleanMatrix visited(N, N); class Counting { public: Counting() : total(0), inf(0) { for (int i = 0; i < 100; i++) counts[i] = 0; } Counting(const Counting &other) : total(other.total), inf(other.inf) { for (int i = 0; i < 100; i++) counts[i] = other.counts[i]; } void add(long long length) { int i = 0; long long l = 2; for (; i < 99; i++, l *= 2) if (length <= l) break; counts[i] += length; total++; } void addInf(long long length) { inf += length; total++; } long long counts[100]; long long total; long long inf; void print(FILE *fout, int size) { double area = (long long)size * (long long)size * (long long)N * (long long)N; double prevdiff = 0; long long p = 1; int f = -1; int t = -1; for (int i = 0; i < 100; i++) { if (counts[i] != 0) { t = i; if (f == -1) f = i; } } double sum = 0; for (int i = f; i <= t; i++) { double diff = ((double)counts[i])/area*50; sum += diff; fprintf(fout, "%20lld: %10f", p, sum); p *= 2; if (i > 0) { fprintf(fout, " %10f", diff); if (i > 1 && prevdiff != 0.0) { double factor = diff / prevdiff; fprintf(fout, " %10f", factor); if (factor < 1.0) { double end = sum + factor * diff / (1 - factor); fprintf(fout, " %10f", end); } } } fprintf(fout, "\n"); prevdiff = diff; } if (inf > 0) fprintf(fout, "inf: %10f\n", ((double)inf)/area*50); } }; Counting loop_counting; void follow(int i, int j, char dir, Edge* start_edge, int start_index, Edge* (&edges)[4]) { Edge *end_edge; int end_index; long long length = 0; for (;;) { if (dir == 'd') { if (j >= 0) visited.set(i, j); j++; if (j == N) { end_edge = edges[2]; end_index = i; break; } dir = maze.get(i, j) ? 'l' : 'r'; } else if (dir == 'u') { j--; if (j < 0) { end_edge = edges[0]; end_index = i; break; } dir = maze.get(i, j) ? 'r' : 'l'; } else if (dir == 'r') { i++; if (i == N) { end_edge = edges[1]; end_index = j; break; } dir = maze.get(i, j) ? 'u' : 'd'; } else if (dir == 'l') { i--; if (i < 0) { end_edge = edges[3]; end_index = j; break; } dir = maze.get(i, j) ? 'd' : 'u'; } length++; } Edge::Element &start_element = start_edge->elements[start_index]; start_element.edge = end_edge; start_element.index = end_index; start_element.length = length; Edge::Element &end_element = end_edge->elements[end_index]; end_element.edge = start_edge; end_element.index = start_index; end_element.length = length; } void fill(int x, int y, Edge* (&edges)[4]) { printf("File %d,%d\n", x, y); edges[0] = new Edge(x, y, 'r'); edges[1] = new Edge(x+1, y, 'd'); edges[2] = new Edge(x, y+1, 'l'); edges[3] = new Edge(x, y, 'u'); for (int i = 0; i < 4; i++) { int j = (i+1)%4; edges[i]->next = edges[j]; edges[j]->prev = edges[i]; } maze.reset(); visited.reset(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (randomBoolGenerator.get()) maze.set(i, j); } } for (int i = 0; i < N; i += 2) follow(i, -1, 'd', edges[0], i, edges); for (int j = 1; j < N; j += 2) follow(-1, j, 'r', edges[3], j, edges); for (int i = 1; i < N; i += 2) follow(i, N, 'u', edges[2], i, edges); for (int j = 0; j < N; j += 2) follow(N, j, 'l', edges[1], j, edges); for (int s_i = 0; s_i < N-1; s_i++) for (int s_j = 0; s_j < N; s_j++) if ((s_i + s_j)%2 == 1 && !visited.get(s_i, s_j)) { int i = s_i; int j = s_j; char dir = 'd'; long long length = 0; do { if (dir == 'd') { visited.set(i, j); j++; dir = maze.get(i, j) ? 'l' : 'r'; } else if (dir == 'u') { j--; dir = maze.get(i, j) ? 'r' : 'l'; } if (dir == 'r') { i++; dir = maze.get(i, j) ? 'u' : 'd'; } else if (dir == 'l') { i--; dir = maze.get(i, j) ? 'd' : 'u'; } length += 2; } while (i != s_i || j != s_j || dir != 'd'); loop_counting.add(length); } } void glue(Edge* loop, Edge* (&edges)[4]) { for (int i = 0; i < 4; i++) { Edge* right = edges[i]; Edge* left = 0; for (Edge* edge_loop = loop;;) { if ( edge_loop->x == right->x && edge_loop->y == right->y && ( (edge_loop->dir == 'd' && right->dir == 'u') || (edge_loop->dir == 'l' && right->dir == 'r') || (edge_loop->dir == 'u' && right->dir == 'd') || (edge_loop->dir == 'r' && right->dir == 'l'))) { left = edge_loop; break; } edge_loop = edge_loop->next; if (edge_loop == loop) break; } if (left != 0) { for (int i = 0; i < N; i++) { bool okay = true; bool loop = false; long long length = 0; Edge::Element &right_element = right->elements[i]; Edge* right_edge = right_element.edge; int right_index = right_element.index; length += right_element.length; while (right_edge == right || (right_edge == left && right_index != i)) if (right_edge == right) { if (right_index > i) okay = false; Edge::Element &element = left->elements[right_index]; right_edge = element.edge; right_index = element.index; length += element.length; } else // right_edge == left { if (right_index > i) okay = false; Edge::Element &element = right->elements[right_index]; right_edge = element.edge; right_index = element.index; length += element.length; } if (!okay) continue; if (right_edge == left && right_index == i) { loop_counting.add(length); continue; } Edge::Element &left_element = left->elements[i]; Edge* left_edge = left_element.edge; int left_index = left_element.index; length += left_element.length; while (left_edge == right || left_edge == left) if (left_edge == right) { if (left_index > i) okay = false; Edge::Element &element = left->elements[left_index]; left_edge = element.edge; left_index = element.index; length += element.length; } else // left_edge == left { if (left_index > i) okay = false; Edge::Element &element = right->elements[left_index]; left_edge = element.edge; left_index = element.index; length += element.length; } if (!okay) continue; Edge::Element &right_elem = right_edge->elements[right_index]; right_elem.edge = left_edge; right_elem.index = left_index; right_elem.length = length; Edge::Element &left_elem = left_edge->elements[left_index]; left_elem.edge = right_edge; left_elem.index = right_index; left_elem.length = length; } if (left->next != right) { right->prev->next = left->next; left->next->prev = right->prev; } if (right->next != left) { right->next->prev = left->prev; left->prev->next = right->next; } delete right; delete left; } } } int main(int argc, char* argv[]) { Edge* edges[4]; fill(0, 0, edges); Edge* main_loop = edges[0]; FILE *f = fopen("diagmaze3.txt", "wt"); for (int size = 2;; size++) { for (int i = 0; i < size-1; i++) { Edge* edges[4]; fill(i, size-1, edges); glue(main_loop, edges); } for (int j = 0; j < size; j++) { Edge* edges[4]; fill(size-1, j, edges); glue(main_loop, edges); } Counting all_counting(loop_counting); double inf; Counting open_loop_counting; Edge *right = main_loop; while (right->dir != 'd') right = right->next; Edge *left = main_loop; while (left->dir != 'u') left = left->prev; for (; right->dir == 'd' && left->dir == 'u'; right = right->next, left = left->prev) { right->opposing = left; left->opposing = right; } Edge *top = main_loop; while (top->dir != 'r') top = top->next; Edge *bottom = main_loop; while (bottom->dir != 'l') bottom = bottom->prev; for (; top->dir == 'r' && bottom->dir == 'l'; top = top->next, bottom = bottom->prev) { top->opposing = bottom; bottom->opposing = top; } for (Edge* edge = main_loop;;) { if (edge->opposing == 0) printf("edge %c without opposing\n", edge->dir); for (int i = 0; i < N; i++) edge->elements[i].visited = false; edge = edge->next; if (edge == main_loop) break; } for (Edge* edge = main_loop;;) { for (int i = 0; i < N; i++) { Edge::Element &element = edge->elements[i]; if (!element.visited) { long long length = 0; Edge* next_edge = edge; int next_index = i; int x = 0; int y = 0; do { if (next_edge->dir == 'r') x++; else if (next_edge->dir == 'l') x--; else if (next_edge->dir == 'd') y++; else if (next_edge->dir == 'u') y--; Edge::Element &elem = next_edge->elements[next_index]; elem.visited = true; next_edge = elem.edge; next_index = elem.index; open_loop_counting.add(elem.length); length += elem.length; next_edge->elements[next_index].visited = true; next_edge = next_edge->opposing; } while (next_edge != edge || next_index != i); if (x == 0 && y == 0) all_counting.add(length); else all_counting.addInf(length); } } edge = edge->next; if (edge == main_loop) break; } fprintf(f, "Size = %d\n", size); fprintf(f, "loops\n"); loop_counting.print(f, size); fprintf(f, "open loops\n"); open_loop_counting.print(f, size); fprintf(f, "all\n"); all_counting.print(f, size); fprintf(f, "\n"); fflush(f); } }