1 // Hyperbolic Rogue -- expansion analyzer
2 // Copyright (C) 2011-2019 Zeno Rogue, see 'hyper.cpp' for details
3
4 /** \file expansion.cpp
5 * \brief exponential growth of hyperbolic geometries
6 *
7 * Calculations related to this exponential growth.
8 * Screens which display this exponential growth (e.g. 'size of the world' in geometry experiments) are also implemented here.
9 */
10
11 #include "hyper.h"
12 namespace hr {
13
subtype(cell * c)14 int subtype(cell *c) {
15 return patterns::getpatterninfo(c, patterns::PAT_NONE, 0).id;
16 }
17
canonicize(vector<int> & t)18 void canonicize(vector<int>& t) {
19 for(int i=2; i<isize(t); i++)
20 if((t[i] & 3) == 1 && (t[i-1] & 3) != 1)
21 std::rotate(t.begin()+1, t.begin()+i, t.end());
22 }
23
24 #if HDR
25 struct expansion_analyzer {
26 vector<int> gettype(cell *c);
27 int N;
28 vector<cell*> samples;
29 map<vector<int>, int> codeid;
30 vector<vector<int> > children;
31 int rootid, diskid;
32 int coefficients_known;
33 #if CAP_GMP
34 vector<mpq_class> coef;
35 #else
36 vector<int> coef;
37 #endif
38 int valid_from, tested_to;
39 ld growth;
40
41 int sample_id(cell *c);
42 void preliminary_grouping();
43 void reduce_grouping();
44 vector<vector<bignum>> descendants;
45 bignum& get_descendants(int level);
46 bignum& get_descendants(int level, int type);
47 void find_coefficients();
48 void reset();
49
expansion_analyzerhr::expansion_analyzer50 expansion_analyzer() { reset(); }
51
52 string approximate_descendants(int d, int max_length);
53 void view_distances_dialog();
54 ld get_growth();
55
56 private:
57 bool verify(int id);
58 int valid(int v, int step);
59 };
60 #endif
61
gettype(cell * c)62 vector<int> expansion_analyzer::gettype(cell *c) {
63 vector<int> res;
64 res.push_back(subtype(c) * 4 + 2);
65 int d = celldist(c);
66 for(int i=0; i<c->type; i++) {
67 cell *c1 = c->cmove(i);
68 int bonus = 0;
69 if(bt::in()) bonus += 16 * (celldistAlt(c1) - celldistAlt(c));
70 res.push_back(bonus + subtype(c1) * 4 + celldist(c1) - d);
71 }
72 canonicize(res);
73 return res;
74 }
75
sample_id(cell * c)76 int expansion_analyzer::sample_id(cell *c) {
77 auto t = gettype(c);
78 if(codeid.count(t)) return codeid[t];
79 auto &cit = codeid[t];
80 cit = isize(samples);
81 samples.push_back(c);
82 return cit;
83 }
84
get_children_codes(cell * c,const T & distfun,const U & typefun)85 template<class T, class U> vector<int> get_children_codes(cell *c, const T& distfun, const U& typefun) {
86 vector<int> res;
87 int d = distfun(c);
88 cellwalker cw(c, 0);
89 if(d > 0) {
90 forCellCM(c2, c) if(celldist(cw.peek()) < d) break; else cw++;
91 }
92 for(int k=0; k<c->type; k++) {
93 cell *c1 = cw.cpeek();
94 cw++;
95 if(distfun(c1) != d+1) continue;
96 cell *c2 = cw.cpeek();
97 if(distfun(c2) != d+1) continue;
98 res.push_back(typefun(c1));
99 }
100 return res;
101 }
102
preliminary_grouping()103 void expansion_analyzer::preliminary_grouping() {
104 samples.clear();
105 codeid.clear();
106 children.clear();
107 if(currentmap->strict_tree_rules()) {
108 N = isize(rulegen::treestates);
109 children.resize(N);
110 rootid = rulegen::rule_root;
111 for(int i=0; i<N; i++)
112 for(int v: rulegen::treestates[i].rules)
113 if(v >= 0) children[i].push_back(v);
114 }
115 else if(reg3::in_rule()) {
116 #if MAXMDIM >= 4
117 rootid = reg3::rule_get_root(0);
118 auto& chi = reg3::rule_get_children();
119 N = isize(chi) / S7;
120 children.resize(N);
121 int k = 0;
122 for(int i=0; i<N; i++) for(int j=0; j<S7; j++) {
123 int ck = chi[k];
124 if(ck < -1) ck += (1<<16);
125 if(ck >= 0)
126 children[i].push_back(ck);
127 k++;
128 }
129 #endif
130 }
131 else {
132 sample_id(currentmap->gamestart());
133 // queue for, do not change to range-based for
134 for(int i=0; i<isize(samples); i++)
135 children.push_back(get_children_codes(samples[i], celldist, [this] (cell *c) { return sample_id(c); }));
136 N = isize(samples);
137 rootid = 0;
138 }
139 diskid = N;
140 children.push_back(children[rootid]);
141 children[diskid].push_back(diskid);
142 N++;
143 }
144
reduce_grouping()145 void expansion_analyzer::reduce_grouping() {
146 if(reg3::in_rule()) return;
147 if(currentmap->strict_tree_rules()) return;
148 int old_N = N;
149 vector<int> grouping;
150 grouping.resize(N);
151 int nogroups = 1;
152 for(int i=0; i<N; i++) grouping[i] = 0;
153 while(true) {
154 vector< pair<vector<int>, int > > childgroups(N);
155 for(int i=0; i<N; i++) {
156 childgroups[i].second = i;
157 for(int j: children[i])
158 childgroups[i].first.push_back(grouping[j]);
159 // sort(childgroups[i].first.begin(), childgroups[i].first.end());
160 }
161 sort(childgroups.begin(), childgroups.end());
162 int newgroups = 0;
163 for(int i=0; i<N; i++) {
164 if(i == 0 || childgroups[i].first != childgroups[i-1].first) newgroups++;
165 grouping[childgroups[i].second] = newgroups - 1;
166 }
167 if(nogroups == newgroups) break;
168 nogroups = newgroups;
169 }
170
171 vector<int> groupsample(nogroups, -1);
172 for(int i=0; i<N; i++) {
173 int& g = groupsample[grouping[i]];
174 if(g == -1) g = i;
175 }
176
177 vector<int> reorder(nogroups);
178 for(int i=0; i<nogroups; i++) reorder[i] = i;
179 sort(reorder.begin(), reorder.end(), [&] (int i, int j) { return groupsample[i] < groupsample[j]; });
180
181 vector<int> inv_reorder(nogroups);
182 for(int i=0; i<nogroups; i++) inv_reorder[reorder[i]] = i;
183
184 for(int i=0; i<N; i++) grouping[i] = inv_reorder[grouping[i]];
185
186 for(int i=0; i<N; i++) groupsample[grouping[i]] = i;
187
188 vector<vector<int>> newchildren(nogroups);
189 for(int i=0; i<nogroups; i++)
190 for(int j: children[groupsample[i]])
191 newchildren[i].push_back(grouping[j]);
192 children = move(newchildren);
193 for(auto& p: codeid) p.second = grouping[p.second];
194 N = nogroups;
195 rootid = grouping[rootid];
196 diskid = grouping[diskid];
197 for(int g=0; g<old_N; g++) if(grouping[g] != g) descendants.clear();
198 }
199
size_upto(vector<T> & v,int s)200 template<class T> int size_upto(vector<T>& v, int s) {
201 int res = isize(v);
202 if(res < s) v.resize(s);
203 return res;
204 }
205
get_descendants(int level)206 bignum& expansion_analyzer::get_descendants(int level) {
207 if(!N) preliminary_grouping(), reduce_grouping();
208 return get_descendants(level, rootid);
209 }
210
get_descendants(int level,int type)211 bignum& expansion_analyzer::get_descendants(int level, int type) {
212 if(!N) preliminary_grouping(), reduce_grouping();
213 auto& pd = descendants;
214 size_upto(pd, level+1);
215 for(int d=0; d<=level; d++)
216 for(int i=size_upto(pd[d], N); i<N; i++)
217 if(d == 0) pd[d][i].be(1);
218 else for(int j: children[i])
219 pd[d][i] += pd[d-1][j];
220 return pd[level][type];
221 }
222
verify(int id)223 bool expansion_analyzer::verify(int id) {
224 if(id < isize(coef)) return false;
225 #if CAP_GMP
226 mpq_class res = 0;
227 for(int t=0; t<isize(coef); t++)
228 res += coef[t] * get_descendants(id-t-1).as_mpq();
229 return res == get_descendants(id).as_mpq();
230 #else
231 long long res = 0;
232 for(int t=0; t<isize(coef); t++)
233 res += coef[t] * get_descendants(id-t-1).approx_ll();
234 return res == get_descendants(id).approx_ll();
235 #endif
236 }
237
valid(int v,int step)238 int expansion_analyzer::valid(int v, int step) {
239 if(step < 0) return 0;
240 int more = reg3::in_rule() ? 1 : 5;
241 #if CAP_GMP == 0
242 if(get_descendants(step+v+v+more).approx_int() >= bignum::BASE) return 0;
243 typedef ld val;
244 const val unit = 1;
245 #else
246 typedef mpq_class val;
247 const val unit = 1;
248 #endif
249 val matrix[100][128];
250 for(int i=0; i<v; i++)
251 for(int j=0; j<v+1; j++)
252 #if CAP_GMP == 0
253 matrix[i][j] = get_descendants(step+i+j).approx_ll();
254 #else
255 matrix[i][j] = get_descendants(step+i+j).as_mpq();
256 #endif
257
258 for(int k=0; k<v; k++) {
259 int nextrow = k;
260 #if CAP_GMP == 0
261 while(nextrow < v && std::abs(matrix[nextrow][k]) < 1e-6)
262 nextrow++;
263 #else
264 while(nextrow < v && matrix[nextrow][k] == 0)
265 nextrow++;
266 #endif
267 if(nextrow == v) return 1;
268 if(nextrow != k) {
269 // printf("swap %d %d\n", k, nextrow);
270 for(int l=0; l<=v; l++) swap(matrix[k][l], matrix[nextrow][l]);
271 // display();
272 }
273 val divv = unit / matrix[k][k];
274 for(int k1=k; k1<=v; k1++) matrix[k][k1] *= divv;
275 // printf("divide %d\n", k);
276 // display();
277 for(int k1=k+1; k1<v; k1++) if(matrix[k1][k] != 0) {
278 val coef = -matrix[k1][k];
279 for(int k2=k; k2<=v; k2++) matrix[k1][k2] += matrix[k][k2] * coef;
280 }
281 // printf("zeros below %d\n", k);
282 // display();
283 }
284
285 for(int k=v-1; k>=0; k--)
286 for(int l=k-1; l>=0; l--)
287 if(matrix[l][k]) matrix[l][v] -= matrix[l][k] * matrix[k][v];
288
289 coef.resize(v);
290 #if CAP_GMP
291 for(int i=0; i<v; i++) coef[i] = matrix[v-1-i][v];
292 #else
293 for(int i=0; i<v; i++) coef[i] = int(floor(matrix[v-1-i][v] + .5));
294 #endif
295
296 for(int t=step+v; t<step+v+v+more; t++) if(!verify(t)) return 2;
297 tested_to = step+v+v+more;
298 while(tested_to < step+v+v+100) {
299 #if !CAP_GMP
300 if(get_descendants(tested_to).approx_ll() >= bignum::BASE2) break;
301 #endif
302 if(!verify(tested_to)) return 2;
303 tested_to++;
304 }
305
306 valid_from = step+v;
307 return 3;
308 }
309
find_coefficients()310 void expansion_analyzer::find_coefficients() {
311 if(coefficients_known) return;
312 if(!N) preliminary_grouping(), reduce_grouping();
313 for(int v=1; v<25; v++)
314 for(int step=0; step<3 * v; step++) {
315 int val = valid(v, step);
316 if(val == 0) break;
317 if(val == 3) { coefficients_known = 2; return; }
318 }
319 coefficients_known = 1;
320 }
321
322 ld growth;
323
get_growth()324 ld expansion_analyzer::get_growth() {
325 if(growth >= 1) return growth;
326 if(!N) preliminary_grouping(), reduce_grouping();
327 vector<ld> eigen(N, 1);
328 ld total;
329
330 for(int iter=0; iter<100000; iter++) {
331 total = 0;
332 vector<ld> neweigen(N, 0);
333 for(int i=0; i<N; i++) {
334 for(int j: children[i]) neweigen[i] += eigen[j];
335 total += neweigen[i];
336 }
337 for(int i=0; i<N; i++) eigen[i] = .1 * eigen[i] + .9 * neweigen[i] / total;
338 }
339 return growth = total;
340 }
341
reset()342 void expansion_analyzer::reset() {
343 N = 0;
344 growth = 0;
345 coefficients_known = 0;
346 samples.clear();
347 codeid.clear();
348 children.clear();
349 coef.clear();
350 descendants.clear();
351 }
352
type_in(expansion_analyzer & ea,cell * c,const cellfunction & f)353 EX int type_in(expansion_analyzer& ea, cell *c, const cellfunction& f) {
354 if(!ea.N) ea.preliminary_grouping(), ea.reduce_grouping();
355 vector<int> res;
356 res.push_back(subtype(c) * 4 + 2);
357 int d = f(c);
358 for(int i=0; i<c->type; i++) {
359 cell *c1 = c->cmove(i);
360 int bonus = 0;
361 if(bt::in()) bonus += 16 * (celldistAlt(c1) - celldistAlt(c));
362 res.push_back(bonus + subtype(c1) * 4 + f(c1) - d);
363 }
364
365 canonicize(res);
366 if(ea.codeid.count(res)) return ea.codeid[res];
367 int ret = ea.N++;
368 ea.codeid[res] = ret;
369
370 ea.children.emplace_back();
371 ea.children[ret] = get_children_codes(c, f, [&ea, &f] (cell *c1) { return type_in(ea, c1, f); });
372
373 return ret;
374 }
375
type_in_quick(expansion_analyzer & ea,cell * c,const cellfunction & f)376 int type_in_quick(expansion_analyzer& ea, cell *c, const cellfunction& f) {
377 vector<int> res;
378 res.push_back(subtype(c) * 4 + 2);
379 int d = f(c);
380 for(int i=0; i<c->type; i++) {
381 cell *c1 = c->cmove(i);
382 int dd = f(c1) - d;
383 if(dd < -1 || dd > 1) return -1;
384 res.push_back(subtype(c1) * 4 + dd);
385 }
386
387 canonicize(res);
388 if(ea.codeid.count(res)) return ea.codeid[res];
389 return -1;
390 }
391
sizes_known()392 EX bool sizes_known() {
393 if(reg3::in_rule()) return true;
394 if(bounded) return false;
395 // Castle Anthrax is infinite
396 if(bt::in()) return false;
397 // not implemented
398 if(arcm::in()) return false;
399 if(kite::in()) return false;
400 if(currentmap->strict_tree_rules()) return true;
401 if(arb::in()) return false;
402 return true;
403 }
404
trees_known()405 EX bool trees_known() {
406 return sizes_known() && !(BITRUNCATED && a4 && S7 <= 5);
407 }
408
approximate_descendants(int d,int max_length)409 string expansion_analyzer::approximate_descendants(int d, int max_length) {
410 auto t = SDL_GetTicks();
411 while(isize(descendants) <= d && SDL_GetTicks() < t + 100)
412 get_descendants(isize(descendants));
413 if(isize(descendants) > d)
414 return get_descendants(d).get_str(max_length);
415 int v = isize(descendants) - 1;
416 bignum& b = get_descendants(v);
417 if(b.digits.empty()) return "0";
418 ld log_10 = log(b.digits.back()) / log(10) + 9 * (isize(b.digits) - 1) + (d - v) * log(get_growth()) / log(10);
419 int more_digits = int(log_10);
420 return XLAT("about ") + fts(pow(10, log_10 - more_digits)) + "E" + its(more_digits);
421 }
422
423 enum eDistanceFrom { dfPlayer, dfStart, dfWorld };
424 EX string dfnames[3] = { "player", "start", "land" };
425
426 eDistanceFrom distance_from = dfPlayer;
427
428 enum eNumberCoding { ncNone, ncDistance, ncType, ncDebug, ncError };
429 EX string ncnames[5] = { "NO", "distance", "type", "debug", "error" };
430 eNumberCoding number_coding = ncDistance;
431
mod_allowed()432 bool mod_allowed() {
433 return cheater || autocheat || arcm::in() || tour::on;
434 }
435
curr_dist(cell * c)436 EX int curr_dist(cell *c) {
437 switch(distance_from) {
438 case dfPlayer:
439 return c->cpdist < INFD ? c->cpdist : celldistance(cwt.at, c);
440 case dfStart:
441 return celldist(c);
442 case dfWorld:
443 if(!mod_allowed() && !among(c->land, laOcean, laIvoryTower, laEndorian, laDungeon, laTemple, laWhirlpool, laCanvas))
444 return 0;
445 if((isCyclic(c->land) || among(c->land, laCanvas, laCaribbean, laStorms, laRlyeh))) {
446 if(eubinary || c->master->alt) return celldistAlt(c);
447 return UNKNOWN;
448 }
449 return inmirror(c) ? (c->landparam & 255) : c->landparam;
450 }
451 return 0;
452 }
453
454 int position;
455
type_in_reduced(expansion_analyzer & ea,cell * c,const cellfunction & f)456 EX int type_in_reduced(expansion_analyzer& ea, cell *c, const cellfunction& f) {
457 int a = ea.N;
458 int t = type_in(ea, c, f);
459 if(expansion.N != a) {
460 expansion.reduce_grouping();
461 t = type_in(ea, c, f);
462 }
463 return t;
464 }
465
466 // which=1 => right, which=-1 => left
467
parent_id(cell * c,int which,const cellfunction & cf)468 EX int parent_id(cell *c, int which, const cellfunction& cf) {
469 int d = cf(c)-1;
470 for(int i=0; i<c->type; i++) {
471
472 if(cf(c->cmove(i)) == d) {
473 int steps = 0;
474 again:
475 if(!which || steps == c->type) return i;
476 int i2 = c->c.fix(i+which);
477 if(cf(c->cmove(i2)) == d) {
478 i = i2; steps++; goto again;
479 }
480 else return i;
481 }
482 }
483
484 return -1;
485 }
486
487 // set which=1,bonus=1 to get right neighbor on level
488
generate_around(cell * c)489 EX void generate_around(cell *c) {
490 forCellCM(c2, c) if(c2->mpdist > BARLEV) setdist(c2, BARLEV, c);
491 }
492
493 EX namespace ts {
verified_add(cell * c,int which,int bonus,const cellfunction & cf)494 EX cell *verified_add(cell *c, int which, int bonus, const cellfunction& cf) {
495 int id = parent_id(c, which, cf);
496 if(id == -1) return NULL;
497 return c->cmodmove(id + bonus);
498 }
499
verified_add_gen(cell * c,int which,int bonus,const cellfunction & cf)500 EX cell *verified_add_gen(cell *c, int which, int bonus, const cellfunction& cf) {
501 return verified_add(c, which, bonus, cf);
502 }
503
add(cell * c,int which,int bonus,const cellfunction & cf)504 EX cell *add(cell *c, int which, int bonus, const cellfunction& cf) {
505 int pid = parent_id(c, which, cf);
506 if(pid == -1) pid = 0;
507 return c->cmodmove(pid + bonus);
508 }
509
left_of(cell * c,const cellfunction & cf)510 EX cell *left_of(cell *c, const cellfunction& cf) {
511 int pid = parent_id(c, 1, cf);
512 if(pid == -1) return c;
513 if(valence() == 3) return c->cmodmove(pid+1);
514 else return (cellwalker(c, pid) + wstep - 1).cpeek();
515 }
516
right_of(cell * c,const cellfunction & cf)517 EX cell *right_of(cell *c, const cellfunction& cf) {
518 int pid = parent_id(c, -1, cf);
519 if(pid == -1) return c;
520 if(valence() == 3) return c->cmodmove(pid-1);
521 else return (cellwalker(c, pid) + wstep + 1).cpeek();
522 }
523
child_number(cell * c,int id,const cellfunction & cf)524 EX cell *child_number(cell *c, int id, const cellfunction& cf) {
525 int pid = parent_id(c, 1, cf);
526 if(pid == -1) return c->cmove(id);
527 return c->cmodmove(pid + (valence() == 3 ? 2 : 1) + id);
528 }
529
530 #if HDR
left_parent(cell * c,const cellfunction & cf)531 inline cell *left_parent(cell *c, const cellfunction& cf) { return verified_add(c, 1, 0, cf); }
right_parent(cell * c,const cellfunction & cf)532 inline cell *right_parent(cell *c, const cellfunction& cf) { return verified_add(c, -1, 0, cf); }
533 #endif
534
535 EX }
536
537 EX bool viewdists = false;
538 EX bool use_color_codes = true;
539 EX bool use_analyzer = true;
540 EX bool show_distance_lists = true;
541
542 int first_distance = 0, scrolltime = 0;
543 bool scrolling_distances = false;
544
545 EX map<int, color_t> expcolors;
546
distribute_color(int id)547 color_t distribute_color(int id) {
548 if(expcolors.count(id)) return expcolors[id];
549 color_t v = forecolor; // 0xFFFFFF;
550 for(int z=0; z<24; z++) if(id & (1<<z)) part(v, (z%3)) ^= (1<<(7-(z/3)));
551 return v;
552 }
553
554 EX bool dist_label_colored = true;
555 EX color_t dist_label_color = 0;
556
do_viewdist()557 void celldrawer::do_viewdist() {
558 if(behindsphere(V)) return;
559
560 int cd = (use_color_codes || number_coding == ncDistance || number_coding == ncDebug) ? curr_dist(c) : 0;
561
562 if(use_color_codes) {
563 int dc = distcolors[cd];
564 wcol = gradient(wcol, dc, 0, .4, 1);
565 fcol = gradient(fcol, dc, 0, .4, 1);
566 }
567
568 string label = "";
569 int dc = 0xFFD500;
570
571 switch(number_coding) {
572 case ncDistance: {
573 label = cd == UNKNOWN ? "?" : its(cd);
574 dc = distcolors[cd];
575 break;
576 }
577 case ncType: {
578 int t = -1;
579 if(reg3::in_rule()) switch(distance_from) {
580 case dfPlayer:
581 t = -1;
582 break;
583 case dfStart:
584 t = c->master->fiftyval;
585 break;
586 case dfWorld:
587 if(c->master->alt) t = c->master->alt->fiftyval;
588 break;
589 }
590 else if(currentmap->strict_tree_rules()) switch(distance_from) {
591 case dfPlayer:
592 t = -1;
593 break;
594 case dfStart:
595 t = c->master->fieldval;
596 break;
597 case dfWorld:
598 if(c->master->alt) t = c->master->alt->fieldval;
599 break;
600 }
601 else t = type_in_reduced(expansion, c, curr_dist);
602 if(t >= 0) label = its(t), dc = distribute_color(t);
603 break;
604 }
605 case ncDebug: {
606 int d =
607 distance_from == dfStart && cwt.at == currentmap->gamestart() && c->cpdist < INFD ? c->cpdist :
608 celldistance(c, distance_from == dfPlayer ? cwt.at : currentmap->gamestart());
609 dc = (d != cd) ? 0xFF0000 : 0x00FF00;
610 label = its(d);
611 }
612 case ncError: {
613 if(pointer_indices.count(c)) label = index_pointer(c);
614 }
615 case ncNone: ;
616 }
617
618 if(!dist_label_colored) dc = dist_label_color;
619
620 // string label = its(fieldpattern::getriverdistleft(c)) + its(fieldpattern::getriverdistright(c));
621 /* queuepolyat(V, shFloor[ct6], darkena(gradient(0, distcolors[cd&7], 0, .25, 1), fd, 0xC0),
622 PPR::TEXT); */
623 if(label != "")
624 queuestr(V, (isize(label) > 1 ? .6 : 1), label, 0xFF000000 + dc, 1);
625 }
626
viewdist_configure_dialog()627 EX void viewdist_configure_dialog() {
628 dialog::init("");
629 cmode |= sm::SIDE | sm::MAYDARK | sm::EXPANSION;
630 gamescreen(0);
631
632 dialog::addSelItem(XLAT("which distance"), XLAT(dfnames[distance_from]), 'c');
633 dialog::add_action([] () { distance_from = mod_allowed() ? eDistanceFrom((distance_from + 1) % 3) : eDistanceFrom(2 - distance_from); });
634
635 dialog::addSelItem(XLAT("number codes"), XLAT(ncnames[number_coding]), 'n');
636 dialog::add_action([] () { number_coding = eNumberCoding((number_coding + 1) % (mod_allowed() ? 4 : 2)); });
637
638 dialog::addBoolItem_action(XLAT("color codes"), use_color_codes, 'u');
639
640 dialog::addSelItem(XLAT("display distances from"), its(first_distance), 'd');
641 dialog::add_action([] () {
642 scrolling_distances = false;
643 dialog::editNumber(first_distance, 0, 3000, 1, 0, XLAT("display distances from"), "");
644 dialog::bound_low(0);
645 });
646
647 dialog::addBoolItem(XLAT("strict tree maps"), currentmap->strict_tree_rules(), 's');
648 dialog::add_action_push(rulegen::show);
649
650 int id = 0;
651 using namespace linepatterns;
652 for(auto& lp: {&patTriTree, &patTriRings, &patTriOther}) {
653 dialog::addColorItem(XLAT(lp->lpname), lp->color, '1'+(id++));
654 dialog::add_action([&lp] () {
655 dialog::openColorDialog(lp->color, NULL);
656 dialog::dialogflags |= sm::MAYDARK | sm::SIDE | sm::EXPANSION;
657 });
658 }
659
660 if(!mod_allowed()) {
661 dialog::addItem(XLAT("enable the cheat mode for additional options"), 'C');
662 dialog::add_action(enable_cheat);
663 }
664 else
665 dialog::addBreak(100);
666
667 dialog::addBreak(100);
668
669 dialog::addItem(XLAT("disable"), 'x');
670 dialog::add_action([] () { viewdists = false; popScreen(); });
671
672 dialog::addItem(XLAT("move the player"), 'm');
673 dialog::add_action([] () { show_distance_lists = false; popScreenAll(); });
674
675 dialog::addItem(distance_from ? XLAT("show number of descendants by distance") : XLAT("show number of cells by distance"), 'l');
676 dialog::add_action([] () { show_distance_lists = true; popScreenAll(); });
677
678 dialog::display();
679 }
680
is_descendant(cell * c)681 bool is_descendant(cell *c) {
682 if(c == cwt.at) return true;
683 if(curr_dist(c) < curr_dist(cwt.at)) return false;
684 return is_descendant(ts::right_parent(c, curr_dist));
685 }
686
687 const int scrollspeed = 100;
688
689 bool not_only_descendants = false;
690
691 #if CAP_GMP
produce_coef_formula(vector<mpq_class> coef)692 string produce_coef_formula(vector<mpq_class> coef) {
693 #else
694 string produce_coef_formula(vector<int> coef) {
695 #endif
696 string fmt = "a(d+" + its(isize(coef)) + ") = ";
697 bool first = true;
698 for(int i=0; i<isize(coef); i++) if(coef[i]) {
699 if(first && coef[i] == 1) ;
700 else if(first) fmt += its(coef[i]);
701 else if(coef[i] == 1) fmt += " + ";
702 else if(coef[i] == -1) fmt += " - ";
703 else if(coef[i] > 1) fmt += " + " + its(coef[i]);
704 else if(coef[i] < -1) fmt += " - " + its(-coef[i]);
705 fmt += "a(d";
706 if(i != isize(coef) - 1)
707 fmt += "+" + its(isize(coef) - 1 - i);
708 fmt += ")";
709 first = false;
710 }
711 return fmt;
712 }
713
714 void expansion_analyzer::view_distances_dialog() {
715 static int lastticks;
716 if(scrolling_distances && !bounded) {
717 scrolltime += SDL_GetTicks() - lastticks;
718 first_distance += scrolltime / scrollspeed;
719 scrolltime %= scrollspeed;
720 }
721 lastticks = SDL_GetTicks();
722 if(first_distance < 0) first_distance = 0;
723
724 dynamicval<color_t> dv(distcolors[0], forecolor);
725 dialog::init("");
726 cmode |= sm::DIALOG_STRICT_X | sm::EXPANSION;
727
728 int maxlen = bounded ? 128 : 16 + first_distance;
729 vector<bignum> qty(maxlen);
730
731 bool really_use_analyzer = use_analyzer && sizes_known();
732
733 if(really_use_analyzer) {
734 int t;
735 if(reg3::in_rule() || currentmap->strict_tree_rules()) {
736 if(!N) preliminary_grouping();
737 t = rootid;
738 }
739 else
740 t = type_in_reduced(expansion, cwt.at, curr_dist);
741 for(int r=0; r<maxlen; r++)
742 qty[r] = expansion.get_descendants(r, t);
743 }
744 else {
745 if(distance_from == dfPlayer) {
746 celllister cl(cwt.at, bounded ? maxlen-1 : gamerange(), 100000, NULL);
747 for(int d: cl.dists)
748 if(d >= 0 && d < maxlen) qty[d]++;
749 }
750 else {
751 celllister cl(cwt.at, bounded ? maxlen-1 : gamerange(), 100000, NULL);
752 for(cell *c: cl.lst) if((not_only_descendants || is_descendant(c)) && curr_dist(c) < maxlen) qty[curr_dist(c)]++;
753 }
754 #if !CAP_GMP
755 if(sizes_known() && !not_only_descendants) {
756 find_coefficients();
757 if(gamerange()+1 >= valid_from && coefficients_known == 2) {
758 for(int i=gamerange()+1; i<maxlen; i++)
759 for(int j=0; j<isize(coef); j++) {
760 qty[i].addmul(qty[i-1-j], coef[j]);
761 }
762 }
763 }
764 #endif
765 }
766
767 dialog::addBreak(100 - 100 * scrolltime / scrollspeed);
768
769 for(int i=first_distance; i<maxlen; i++) if(!qty[i].digits.empty())
770 dialog::addInfo(its(i) + ": " + qty[i].get_str(100), distcolors[i]);
771
772 dialog::addBreak(100 * scrolltime / scrollspeed);
773
774 if(sizes_known() || bt::in()) {
775 if(euclid && !arb::in()) {
776 dialog::addBreak(200);
777 dialog::addInfo("a(d) = " + its(get_descendants(10).approx_int() - get_descendants(9).approx_int()) + "d", forecolor);
778 }
779 else {
780 dialog::addBreak(100);
781
782 find_coefficients();
783 if(coefficients_known == 2) {
784 string fmt = produce_coef_formula(coef);
785 fmt += " (d>" + its(valid_from-1) + ")";
786 dialog::addHelp(fmt);
787 }
788 else dialog::addBreak(100);
789
790 dialog::addInfo("Θ(" + fts(get_growth(), 8) + "...ᵈ)", forecolor);
791 }
792 }
793
794 dialog::addItem(XLAT("scroll"), 'S');
795 dialog::addItem(XLAT("configure"), 'C');
796 dialog::display();
797 }
798
799 EX void enable_viewdists() {
800 first_distance = 0;
801 scrolltime = 0;
802 viewdists = true;
803 if(!mod_allowed()) {
804 number_coding = ncDistance;
805 distance_from = dfPlayer;
806 }
807 show_distance_lists = true;
808 }
809
810 bool expansion_handleKey(int sym, int uni) {
811 if((cmode & sm::NORMAL) && viewdists) {
812 if(uni == 'S' && (cmode & sm::EXPANSION)) scrolling_distances = !scrolling_distances;
813 else if(uni == 'C') pushScreen(viewdist_configure_dialog);
814 else if(uni == 'A' && (cmode & sm::EXPANSION)) use_analyzer = !use_analyzer;
815 else if(sym == SDLK_ESCAPE) first_distance = 0, viewdists = false;
816 else return false;
817 return true;
818 }
819 return false;
820 }
821
822 int expansion_hook = addHook(hooks_handleKey, 0, expansion_handleKey);
823
824 #if !ISMINI
825 void compute_coefficients() {
826 println(hlog, gp::operation_name(), " ", ginf[geometry].tiling_name);
827 start_game();
828
829 printf(" sizes:");
830 for(int i=0; i<expansion.valid_from+10; i++) printf(" %d", expansion.get_descendants(i).approx_int());
831
832 printf(" N = %d\n", expansion.N);
833
834 expansion.find_coefficients();
835 if(expansion.coefficients_known == 2) {
836 println(hlog, " coefficients:");
837 for(auto& x: expansion.coef) println(hlog, " ", x);
838 println(hlog, " (tested on %d to %d)\n", expansion.valid_from, expansion.tested_to);
839 }
840 }
841
842 #if CAP_COMMANDLINE
843 int expansion_readArgs() {
844 using namespace arg;
845
846 if(0) ;
847 else if(argis("-vap")) {
848 PHASEFROM(2);
849 start_game();
850 shift(); int radius = argi();
851 while(true) {
852 string s = expansion.approximate_descendants(radius, 100);
853 printf("s = %s\n", s.c_str());
854 if(isize(expansion.descendants) >= radius) break;
855 }
856 }
857 else if(argis("-csizes")) {
858 PHASEFROM(2);
859 start_game();
860 expansion.get_growth();
861 shift(); for(int i=0; i<argi(); i++)
862 printf("%s / %s\n", expansion.get_descendants(i).get_str(1000).c_str(), expansion.get_descendants(i, expansion.diskid).get_str(1000).c_str());
863 }
864 else if(argis("-csolve")) {
865 PHASEFROM(2);
866 start_game();
867 printf("preliminary_grouping...\n");
868 expansion.preliminary_grouping();
869 printf("N = %d\n", expansion.N);
870 for(int i=0; i<expansion.N; i++) {
871 printf("%d:", i);
872 for(int c: expansion.children[i]) printf(" %d", c);
873 printf("\n");
874 }
875 printf("reduce_grouping...\n");
876 expansion.reduce_grouping();
877 printf("N = %d\n", expansion.N);
878 for(int i=0; i<expansion.N; i++) {
879 printf("%d:", i);
880 for(int c: expansion.children[i]) printf(" %d", c);
881 printf("\n");
882 }
883 println(hlog, "growth = ", expansion.get_growth());
884 expansion.find_coefficients();
885 if(expansion.coefficients_known == 2) {
886
887 println(hlog, " sizes:");
888 for(int i=0; i<expansion.valid_from+10; i++)
889 println(hlog, "[", i, "] = ", expansion.get_descendants(i).get_str(10000));
890
891 println(hlog, " disks:");
892 for(int i=0; i<expansion.valid_from+10; i++)
893 println(hlog, "[", i, "] = ", expansion.get_descendants(i, expansion.diskid).get_str(10000));
894
895 vector<string> disks;
896 for(int i=0; i<expansion.valid_from+10; i++)
897 disks.push_back(expansion.get_descendants(i, expansion.diskid).get_str(10000));
898 println(hlog, "disks = ", disks);
899
900 println(hlog, "coefficients: ", expansion.coef);
901 println(hlog, "i.e. ", produce_coef_formula(expansion.coef));
902 println(hlog, "coefficients tested from ", expansion.valid_from, " to ", expansion.tested_to);
903 }
904 }
905 #if CAP_GP
906 else if(argis("-csolve_tab")) {
907 for(eGeometry geo: {gNormal, gOctagon, g45, g46, g47}) {
908 set_geometry(geo);
909 set_variation(eVariation::pure);
910 compute_coefficients();
911 set_variation(eVariation::bitruncated);
912 compute_coefficients();
913 for(int x=1; x<9; x++)
914 for(int y=0; y<=x; y++) {
915 if(x == 1 && y == 0) continue;
916 if(x == 1 && y == 1 && S3 == 3) continue;
917 if(x+y > 10) continue;
918 stop_game();
919 gp::param = gp::loc(x, y);
920 set_variation(eVariation::goldberg);
921 compute_coefficients();
922 }
923 }
924 }
925 #endif
926
927 else if(argis("-expansion")) {
928 cheat(); viewdists = true;
929 shift(); distance_from = (eDistanceFrom) argi();
930 shift(); number_coding = (eNumberCoding) argi();
931 shift(); use_color_codes = argi() & 1; use_analyzer = argi() & 2; show_distance_lists = argi() & 4;
932 not_only_descendants = argi() & 8;
933 }
934
935 else if(argis("-expansion-labelcolor")) {
936 dist_label_colored = false;
937 shift(); dist_label_color = arghex();
938 }
939
940 else if(argis("-expansion-off")) {
941 viewdists = false;
942 }
943
944 else return 1;
945 return 0;
946 }
947
948 auto ea_hook = addHook(hooks_args, 100, expansion_readArgs);
949 #endif
950 #endif
951
952 EX expansion_analyzer expansion;
953
954 EX int sibling_limit = 0;
955
956 EX void set_sibling_limit() {
957 if(0) ;
958 #if CAP_IRR
959 else if(IRREGULAR) sibling_limit = 3;
960 #endif
961 #if CAP_BT
962 else if(bt::in()) sibling_limit = 3;
963 #endif
964 #if CAP_GP
965 else {
966 auto p = gp::univ_param();
967 sibling_limit = 2 * p.first + p.second;
968 }
969 #else
970 else sibling_limit = PURE ? 2 : 3;
971 #endif
972 }
973
974 int celldist0(cell *c) {
975 if(bt::in()) return celldistAlt(c);
976 else return celldist(c);
977 }
978
979 bool in_segment(cell *left, cell *mid, cell *right) {
980 while(true) {
981 if(mid == left) return true;
982 if(left == right) return false;
983 left = ts::right_of(left, celldist0);
984 }
985 }
986
987 int sibling_distance(cell *a, cell *b, int limit) {
988 int counting = 0;
989 while(true) {
990 if(a == b) return counting;
991 if(limit == 0) return INF;
992 counting++; limit--;
993 a = ts::right_of(a, celldist0);
994 }
995 }
996
997 /** An algorithm for computing distance between two cells.
998 This algorithm runs correctly in O(d) assuming that:
999 - distances from the origin are known
1000 - the set of cells in distance d from the origin forms a cycle
1001 - the map is Gromov hyperbolic (with sibling_limit computed correctly) and planar
1002 - all vertices have valence <= 4
1003 - each vertex has at most two parents
1004 */
1005 EX int hyperbolic_celldistance(cell *c1, cell *c2) {
1006 int found_distance = INF;
1007
1008 int d = 0, d1 = celldist0(c1), d2 = celldist0(c2), sl_used = 0;
1009
1010 cell *cl1=c1, *cr1=c1, *cl2=c2, *cr2=c2;
1011 while(true) {
1012
1013 if(a45 && BITRUNCATED) {
1014 // some cells in this tiling have three parents,
1015 // making the usual algorithm fail
1016 if(d2 == d1+1) {
1017 swap(d1, d2); swap(cl1, cl2); swap(c1, c2); swap(cr1, cr2);
1018 }
1019 auto short_distances = [cl1, cr1, d, &found_distance] (cell *c) {
1020 celllister cl(c, 4, 1000, cl1);
1021 if(cl.listed(cl1)) found_distance = min(found_distance, d + cl.getdist(cl1));
1022 if(cl.listed(cr1)) found_distance = min(found_distance, d + cl.getdist(cr1));
1023 };
1024
1025 if(d1 <= d2+1) {
1026 short_distances(cl2);
1027 if(cl2 != cr2) short_distances(cr2);
1028 }
1029 }
1030
1031 if(d >= found_distance) {
1032 if(sl_used == sibling_limit && IRREGULAR) {
1033 printf("sibling_limit used: %d\n", sibling_limit); sibling_limit++;
1034 }
1035 return found_distance;
1036 }
1037
1038 if(d1 == d2) {
1039 if(cl1 == c1 && in_segment(cl2, c1, cr2)) return d;
1040 if(cl2 == c2 && in_segment(cl1, c2, cr1)) return d;
1041 if(valence() == 3) {
1042 int dx = min(sibling_distance(cr1, cl2, sibling_limit), sibling_distance(cr2, cl1, sibling_limit));
1043 if(d + dx <= found_distance) {
1044 found_distance = d + dx;
1045 sl_used = dx;
1046 }
1047 }
1048 else {
1049 if(cl1 == cr2 || cr1 == cl2) found_distance = d;
1050 }
1051 }
1052
1053 if(d >= found_distance) {
1054 if(sl_used == sibling_limit && IRREGULAR) {
1055 printf("sibling_limit used: %d\n", sibling_limit); sibling_limit++;
1056 }
1057 return found_distance;
1058 }
1059
1060 if(d1 >= d2) {
1061 cl1 = ts::left_parent(cl1, celldist0);
1062 cr1 = ts::right_parent(cr1, celldist0);
1063 d++; d1--;
1064 }
1065 if(d1 < d2) {
1066 cl2 = ts::left_parent(cl2, celldist0);
1067 cr2 = ts::right_parent(cr2, celldist0);
1068 d++; d2--;
1069 }
1070 }
1071 }
1072
1073 }