1 /**
2
3 Honeycomb data generator. See rulegen.sh
4
5 This algorithm works as follows:
6
7 - We use a DFS-like algorithm to identify all the required states. To tell whether two cells
8 c1 and c2 are in the same state, we compute its generate_ext_nei -- the same generate_ext_nei
9 is the same state. To compute generate_ext_nei(c), we list all cells vertex-adjacent to c,
10 and for each c' in this list, we compute FV(c')-FV(c), where FV is the distance from
11 some central tile. It is crucial to identify the directions in unique way (in 2D we can simply
12 use clockwise order, in 3D it is more difficult) -- we do this by using a regular pattern
13 (see get_id).
14
15 After all states are identified, we construct the tree of states -- every non-root state is
16 attached to the first neighbor (according to the direction order) which has smaller FV.
17 For non-tree directions, we construct a path going through nodes with smaller values of FV --
18 this guarantees termination of the algorithm in amortized time O(1).
19
20 */
21
22 #include "zlib.h"
23 #include "../hyper.h"
24
25 namespace hr {
26
27 int exh;
28
29 map<string, map<string,int> > rules;
30
31 /** \brief distance from the center */
32 #define FV master->fiftyval
33
34 /** \brief change i into a string containing a displayable character */
__anoncc9dc1bb0102(int i, char init='a') 35 auto dis = [] (int i, char init='a') { return s0 + char(init + i); };
36
37 bool optimize_344 = false;
38
39 /** \brief we use a regular pattern to make sure that the directions are identified consistently.
40 In {5,3,5} we can just use the Seifert-Weber space for this identification; otherwise,
41 we use the field pattern. */
42
get_id(cell * c)43 int get_id(cell *c) {
44 if(geometry == gSpace535) return 0;
45 if(optimize_344 && geometry == gSpace344) {
46 /* we use the 'pattern from crystal' */
47 /* but it is mod 4, mod 2 is enough for us */
48 int res = 0;
49 int fv = c->master->fieldval;
50 for(int i=0; i<4; i++) {
51 res = 2 * res + (fv&1);
52 fv >>= 2;
53 }
54 return res;
55 }
56 return c->master->fieldval;
57 }
58
59 /** \brief aux function for find_path which limits path length
60 * the rule is that we make some moves which decrease FV, then we make some moves which increase FV
61 */
62
find_path(cell * x,cell * y,int steps)63 string find_path(cell *x, cell *y, int steps) {
64 if(x->FV != y->FV) {
65 println(hlog, x, y, " steps=", steps, " d=", x->FV, " vs ", y->FV);
66 exit(3);
67 }
68 if(x == y) return "";
69 if(steps == 0) return "?";
70 for(int i=0; i<S7; i++)
71 if(x->move(i) && x->move(i)->FV < x->FV)
72 for(int j=0; j<S7; j++)
73 if(y->move(j) && y->move(j)->FV < y->FV) {
74 string ch = find_path(x->move(i), y->move(j), steps-1);
75 if(ch == "?") continue;
76 return dis(i) + ch + dis(y->c.spin(j));
77 }
78 return "?";
79 }
80
81 /** \brief aux function for find_path which limits path length
82 * the rule is that we keep to a fixed FV-level (this works better in {x,x,3})
83 */
84
find_path_side(cell * x,cell * y,int steps)85 string find_path_side(cell *x, cell *y, int steps) {
86 if(x->FV != y->FV) {
87 println(hlog, x, y, " steps=", steps, " d=", x->FV, " vs ", y->FV);
88 exit(3);
89 }
90 if(x == y) return "";
91 if(steps == 0) return "?";
92 for(int i=0; i<S7; i++)
93 if(x->move(i) && x->move(i)->FV == x->FV) {
94 string ch = find_path_side(x->move(i), y, steps-1);
95 if(ch == "?") continue;
96 return dis(i) + ch;
97 }
98 return "?";
99 }
100
101 /** \brief find the sequence of moves we need to take to get from y to x (x and y must be the same fv-level)
102 * return '?' if nothing found
103 */
104
find_path(cell * x,cell * y)105 string find_path(cell *x, cell *y) {
106 if(x == y) return "";
107
108 if(geometry == gSpace353) {
109 static int max_steps = -1;
110
111 for(int steps=0; steps<5; steps++) {
112 string f = find_path_side(x, y, steps);
113 if(f != "?") {
114 if(steps > max_steps) {
115 println(hlog, "found a sidepath with ", max_steps = steps, " steps");
116 }
117 return f;
118 }
119 }
120
121 if(max_steps < 10) {
122 max_steps = 10;
123 println(hlog, "failed to find_path_side");
124 }
125 }
126
127 for(int steps=0;; steps++) {
128 string f = find_path(x, y, steps);
129 if(f != "?") return f;
130 }
131 }
132
133 /** a map of all the cells vertex-adjacent to c */
134 struct ext_nei_rules_t {
135 vector<int> from, dir, original;
136 };
137
138 /** ext_nei_rules_t need to be created only once for each get_id */
139 map<int, ext_nei_rules_t> ext_nei_rules;
140
141 /** aux recursive function of construct_rules: the compact variant */
listnear_compact(cell * c,ext_nei_rules_t & e,const transmatrix & T,int id,set<cell * > & visi)142 void listnear_compact(cell *c, ext_nei_rules_t& e, const transmatrix& T, int id, set<cell*>& visi) {
143 visi.insert(c);
144 int a = 0, b = 0;
145 for(int i=0; i<S7; i++) {
146 bool ok = false;
147 transmatrix U = T * currentmap->adj(c, i);
148 for(auto v: cgi.vertices_only) for(auto w: cgi.vertices_only)
149 if(hdist(v, U*w) < 1e-3) ok = true;
150 if(!ok) continue;
151 cell *c1 = c->cmove(i);
152 int id1 = isize(e.from);
153 e.from.push_back(id);
154 e.dir.push_back(i);
155 a++;
156 e.original.push_back(!visi.count(c1));
157 if(e.original.back()) {
158 b++;
159 listnear_compact(c1, e, U, id1, visi);
160 }
161 }
162 }
163
164 /** aux recursive function of construct_rules: the maxdist variant */
listnear_exh(cell * c,ext_nei_rules_t & e,int maxdist)165 void listnear_exh(cell *c, ext_nei_rules_t& e, int maxdist) {
166 map<cell*, int> dist;
167 map<cell*, int> origdir;
168 vector<cell*> lst;
169
170 println(hlog, "called listnear_exh for: ", c);
171
172 auto enqueue = [&] (cell *c, int d, int od) {
173 if(dist.count(c)) return;
174 dist[c] = d;
175 origdir[c] = od;
176 lst.push_back(c);
177 };
178
179 enqueue(c, 0, -1);
180 for(int k=0; k<isize(lst); k++) {
181 cell *ca = lst[k];
182 int di = dist[ca] + 1;
183 int odi = origdir[ca];
184 for(int i=0; i<S7; i++) {
185 if(odi >= 0 && !cgi.dirs_adjacent[i][odi]) continue;
186 cell *c1 = ca->cmove(i);
187 e.from.push_back(k);
188 e.dir.push_back(i);
189 e.original.push_back(!dist.count(c1));
190 if(e.original.back() && di < maxdist)
191 enqueue(c1, di, ca->c.spin(i));
192 }
193 }
194 }
195
196 /** \brief create ext_nei_rules_t for the given c */
construct_rules(cell * c,ext_nei_rules_t & e)197 void construct_rules(cell *c, ext_nei_rules_t& e) {
198 e.from = {-1};
199 e.dir = {-1};
200 e.original = {1};
201 if(!exh) {
202 set<cell*> visi;
203 listnear_compact(c, e, Id, 0, visi);
204 }
205 else {
206 listnear_exh(c, e, exh);
207 }
208 int orgc = 0;
209 for(auto i: e.original) orgc += i;
210 println(hlog, "id ", get_id(c), " list length = ", isize(e.original), " original = ", orgc);
211 }
212
213 /** \brief we learn that a and b are connected -- make sure that their FV's match */
fix_dist(cell * a,cell * b)214 void fix_dist(cell *a, cell *b) {
215 if(a->FV > b->FV+1) {
216 a->FV = b->FV+1;
217 forCellEx(c, a) fix_dist(a, c);
218 }
219 if(b->FV > a->FV+1) {
220 b->FV = a->FV+1;
221 forCellEx(c, b) fix_dist(b, c);
222 }
223 }
224
225 /** \brief compute ext_nei_rules_t for the given cell, and make it into a string form; also do fix_dist */
226
generate_ext_nei(cell * c)227 string generate_ext_nei(cell *c) {
228 int fv = get_id(c);
229 auto& e = ext_nei_rules[fv];
230 if(e.from.empty()) construct_rules(c, e);
231 vector<cell*> ext_nei = {c};
232 for(int i=1; i<isize(e.from); i++) {
233 cell *last = ext_nei[e.from[i]];
234 cell *next = last->cmove(e.dir[i]);
235 fix_dist(last, next);
236 ext_nei.push_back(next);
237 }
238 string res;
239 for(int i=0; i<isize(e.from); i++) if(e.original[i]) res += char('L' + ext_nei[i]->FV - c->FV);
240 return its(fv) + ":" + res;
241 }
242
243 /** cells become 'candidates' before their generate_ext_nei is checked in order to let them become states */
244 set<cell*> candidates;
245 vector<cell*> candidates_list;
246
247 /** the state ID for a given string returned by generate_ext_nei */
248 map<string, int> id_of;
249
250 /** cell representing the given state ID */
251 vector<cell*> rep_of;
252
253 /** current number of states */
254 int number_states = 0;
255
256 /** \brief for state s, child_rules[s][i] is -1 if i-th neighbor not a child; otherwise, the state index of that neighbor */
257 vector<vector<int> > child_rules;
258
259 /** parent direction for every state */
260 vector<int> parent_list;
261
262 /** \brief if child_rules[s][i] is -1, the rules to get to that neighbor */
263 vector<vector<string> > side_rules;
264
add_candidate(cell * c)265 void add_candidate(cell *c) {
266 if(candidates.count(c)) return;
267 candidates.insert(c);
268 candidates_list.push_back(c);
269 }
270
271 /** the main function */
test_canonical(string fname)272 void test_canonical(string fname) {
273 stop_game();
274 reg3::reg3_rule_available = false;
275 fieldpattern::use_rule_fp = true;
276 fieldpattern::use_quotient_fp = true;
277 start_game();
278
279 int qc = reg3::quotient_count();
280
281 vector<cell*> c0;
282
283 if(optimize_344 && geometry == gSpace344) qc = 16;
284
285 /* we start from a 'center' in every get_id-type */
286 if(geometry == gSpace535) {
287 c0.resize(qc, cwt.at);
288 }
289 else {
290 for(int fv=0; fv<qc; fv++) {
291 cell *c = cwt.at;
292 /* 100 to ensure that the FV-spheres around candidates do not interact */
293 for(int i=0; i<100 || get_id(c) != fv; i++) c = c->cmove(hrand(S7));
294 c->FV = 0;
295 c0.push_back(c);
296 }
297 }
298
299 for(cell* c: c0) add_candidate(c);
300
301 vector<int> empty(S7);
302 for(auto& e: empty) e = -1;
303 println(hlog, "empty = ", empty);
304
305 /** generate candidate_list using a BFS-like algorithm, starting from c0 */
306
307 for(int i=0; i<isize(candidates_list); i++) {
308 cell *c = candidates_list[i];
309 string s = generate_ext_nei(c);
310 if(!id_of.count(s)) {
311 // println(hlog, "found candidate for: ", s);
312 id_of[s] = number_states++;
313 rep_of.push_back(c);
314 for(int i=0; i<S7; i++) add_candidate(c->cmove(i));
315 }
316 }
317
318 child_rules.resize(number_states, empty);
319
320 parent_list.resize(number_states);
321
322 println(hlog, "found ", its(number_states), " states");
323
324 /** generate child_rules */
325
326 for(int i=0; i<number_states; i++) {
327 cell *c = rep_of[i];
328
329 string st = generate_ext_nei(c);
330 if(!id_of.count(st) || id_of[st] != i) {
331 println(hlog, "error: ext_nei changed");
332 }
333
334 for(int a=0; a<S7; a++) {
335 cell *c1 = c->move(a);
336 if(c1->FV < c->FV) parent_list[i] = a;
337 if(c1->FV <= c->FV) continue;
338 for(int b=0; b<S7; b++) {
339 cell *c2 = c1->move(b);
340 if(c2->FV != c->FV) continue;
341 if(c2 == c) {
342 string st = generate_ext_nei(c1);
343 if(!id_of.count(st)) {
344 println(hlog, "error: new state generated while generating child_rules");
345 }
346 child_rules[i][a] = id_of[st];
347 }
348 break;
349 }
350 continue;
351 }
352 }
353
354 if(true) {
355
356 /* minimize the automaton */
357
358 // println(hlog, "original rules: ", child_rules);
359 fflush(stdout);
360
361 vector<int> ih(number_states, 0);
362
363 int lqids = 0;
364
365 for(int a=0; a<100; a++) {
366 set<vector<int>> found;
367 vector<vector<int>> v(number_states);
368 map<vector<int>, int> ids;
369 for(int i=0; i<number_states; i++) {
370 vector<int> res(S7+1);
371 for(int d=0; d<S7; d++) res[d] = (child_rules[i][d] != -1) ? ih[child_rules[i][d]] : -1;
372 res[S7] = parent_list[i];
373 v[i] = res;
374 found.insert(res);
375 }
376 int qids = 0;
377 for(auto hash: found) ids[hash] = qids++;
378 println(hlog, "minimization step: ", qids, " states");
379 if(qids == lqids) break;
380 lqids = qids;
381 for(int i=0; i<number_states; i++)
382 ih[i] = ids[v[i]];
383 }
384
385 println(hlog, "reduced states to = ", lqids);
386 vector<vector<int> > new_child_rules;
387 new_child_rules.resize(lqids, empty);
388 for(int i=0; i<number_states; i++) {
389 int j = ih[i];
390 for(int d=0; d<S7; d++) {
391 int cid = child_rules[i][d];
392 new_child_rules[j][d] = cid == -1 ? -1 : ih[cid];
393 }
394 }
395 child_rules = new_child_rules;
396 number_states = lqids;
397 for(auto& p: id_of) p.second = ih[p.second];
398 println(hlog, "rehashed");
399 fflush(stdout);
400 }
401
402 // for(auto& a: child_rules) for(auto i:a) print(hlog, i, ",");
403 println(hlog);
404
405 /* generate side rules */
406 side_rules.resize(number_states);
407 for(auto& s: side_rules) s.resize(S7);
408
409 for(int i=0; i<isize(candidates_list); i++) {
410 cell *c = candidates_list[i];
411 string s = generate_ext_nei(c);
412 if(!id_of.count(s)) println(hlog, "error: MISSING");
413 int id = id_of[s];
414
415 cell *cpar = nullptr;
416 int a0;
417
418 for(int a=0; a<S7; a++) {
419 cell *c1 = c->move(a);
420 if(!c1) continue;
421 if(c1->FV < c->FV && !cpar) cpar = c1, a0 = a;
422 }
423
424 for(int a=0; a<S7; a++) {
425 cell *c1 = c->move(a);
426 if(!c1) continue;
427 bool is_child = false;
428 cell* c2 = nullptr;
429 int dir = 0;
430
431 if(c1->FV >= c->FV) {
432 for(int b=0; b<S7; b++) {
433 c2 = c1->move(b);
434 if(!c2) continue;
435 if(c2->FV >= c1->FV) continue;
436 dir = c1->c.spin(b);
437 break;
438 }
439 }
440
441 is_child = (c2 == c);
442 bool was_child = child_rules[id][a] >= 0;
443
444 if(is_child ^ was_child) {
445 println(hlog, "id=", id, " a=", a);
446 println(hlog, "is_child = ", is_child);
447 println(hlog, "was_child = ", was_child);
448 println(hlog, "c fv = ", c->FV);
449 println(hlog, "c1 fv = ", c1->FV, " [", a, "]");
450 if(c2 == nullptr) { println(hlog, "c2 missing"); }
451 else
452 println(hlog, "c2 fv = ", c2->FV, " [", c2->c.spin(dir), "]");
453 println(hlog, c, "->", c1, "->", c2);
454 fflush(stdout);
455
456 cell *r = rep_of[id];
457 println(hlog, r, " at ", r->FV);
458 cell *r1 = r->move(a);
459 if(!r1) { println(hlog, "error: r1 missing"); continue; }
460 println(hlog, r1, " at ", r1->FV);
461 for(int a=0; a<S7; a++) if(r1->move(a)) println(hlog, a, ":", r1->move(a), " at ", r1->move(a)->FV);
462 fflush(stdout);
463 exit(3);
464 }
465
466 if(is_child) continue;
467
468 string solu;
469
470 if(c1->FV < c->FV)
471 solu = dis(a0, 'A') + find_path(cpar, c1);
472 else if(c1->FV == c->FV)
473 solu = dis(a0, 'A') + find_path(cpar, c2) + dis(dir);
474 else
475 solu = find_path(c, c2) + dis(dir);
476
477 auto& sr = side_rules[id][a];
478
479 if(sr != "" && sr != solu) {
480 println(hlog, "conflict: ", solu, " vs ", sr, " FV = ", c->FV, " vs ", c1->FV);
481 if(isize(sr) < isize(solu)) continue;
482 }
483
484 sr = solu;
485
486 continue;
487 }
488 }
489
490 // println(hlog, side_rules);
491
492 string side_data;
493 for(auto& a: side_rules) for(auto&b :a) if(b != "") side_data += b + ",";
494 println(hlog, side_data);
495
496 vector<short> data;
497 for(auto& a: child_rules) for(auto i:a) data.push_back(i);
498
499 shstream ss;
500
501 auto& fp = currfp;
502 hwrite_fpattern(ss, fp);
503
504 vector<int> root(qc, 0);
505 for(int i=0; i<qc; i++) root[i] = id_of[generate_ext_nei(c0[i])];
506 println(hlog, "root = ", root);
507
508 hwrite(ss, root);
509
510 println(hlog, "copy data");
511 hwrite(ss, data);
512 println(hlog, "copy side_data");
513 hwrite(ss, side_data);
514
515 println(hlog, "compress_string");
516 string s = compress_string(ss.s);
517
518 fhstream of(fname, "wb");
519 print(of, s);
520 }
521
522 auto fqhook =
__anoncc9dc1bb0302null523 addHook(hooks_args, 100, [] {
524 using namespace arg;
525
526 if(0) ;
527 else if(argis("-extra-verification")) {
528 reg3::extra_verification++;
529 }
530 else if(argis("-exh")) {
531 shift(); exh = argi();
532 }
533 else if(argis("-no-rule")) {
534 reg3::reg3_rule_available = false;
535 }
536 else if(argis("-other-rule")) {
537 reg3::reg3_rule_available = true;
538 shift(); reg3::other_rule = args();
539 }
540 else if(argis("-urf")) {
541 cheat(); fieldpattern::use_rule_fp = true;
542 }
543 else if(argis("-uqf")) {
544 cheat(); fieldpattern::use_quotient_fp = true;
545 }
546 else if(argis("-gen-rule")) {
547 shift(); test_canonical(args());
548 }
549 else return 1;
550 return 0;
551 });
552
553 }
554
555 // 1 + 12 + 30 + 20 = 55
556