aboutsummaryrefslogtreecommitdiff
path: root/old/2021-06-23-realizing-bad-tables
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--old/2021-06-23-realizing-bad-tables/HERE1
-rw-r--r--old/2021-06-23-realizing-bad-tables/cube.c2844
-rw-r--r--old/2021-06-23-realizing-bad-tables/cube.h88
-rw-r--r--old/2021-06-23-realizing-bad-tables/cubetypes.h224
-rw-r--r--old/2021-06-23-realizing-bad-tables/main.c70
-rw-r--r--old/2021-06-23-realizing-bad-tables/steps.c486
-rw-r--r--old/2021-06-23-realizing-bad-tables/steps.h42
7 files changed, 3755 insertions, 0 deletions
diff --git a/old/2021-06-23-realizing-bad-tables/HERE b/old/2021-06-23-realizing-bad-tables/HERE
new file mode 100644
index 0000000..487e305
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/HERE
@@ -0,0 +1 @@
Here you can also find some tables data that I have removed, like ep and tripleeo
diff --git a/old/2021-06-23-realizing-bad-tables/cube.c b/old/2021-06-23-realizing-bad-tables/cube.c
new file mode 100644
index 0000000..4e60bb2
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/cube.c
@@ -0,0 +1,2844 @@
1#include "cube.h"
2
3/* Local functions **********************************************************/
4
5static Cube admissible_ep(Cube cube, PieceFilter f);
6static bool allowed_next(Move move, DfsData *dd);
7static void append_alg(AlgList *l, Alg *alg);
8static void append_move(Alg *alg, Move m, bool inverse);
9static Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a);
10static void apply_permutation(int *perm, int *set, int n);
11static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f);
12static int array_ep_to_epos(int *ep, int *eps_solved);
13static Cube arrays_to_cube(CubeArray *arr, PieceFilter f);
14static int binomial(int n, int k);
15static Cube compose_filtered(Cube c2, Cube c1, PieceFilter f);
16static void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
17static void dfs(Cube c, Step s, SolveOptions *opts, DfsData *dd);
18static void dfs_branch(Cube c, Step s, SolveOptions *opts, DfsData *dd);
19static bool dfs_check_solved(SolveOptions *opts, DfsData *dd);
20static void dfs_niss(Cube c, Step s, SolveOptions *opts, DfsData *dd);
21static bool dfs_stop(Cube c, Step s, SolveOptions *opts, DfsData *dd);
22static int digit_array_to_int(int *a, int n, int b);
23static int edge_slice(Edge e); /* E=0, S=1, M=2 */
24static int epos_dependent_pos(int pos1, int pos2);
25static int epos_from_arrays(int *epos, int *ep);
26static void epos_to_partial_ep(int epos, int *ep, int *ss);
27static int factorial(int n);
28static void free_alglistnode(AlgListNode *aln);
29static void free_cubearray(CubeArray *arr, PieceFilter f);
30static void genptable_dfs(Cube c, PruneData *pd, DfsData *dd);
31static void genptable_dfs_branch(Cube c, PruneData *pd, DfsData *dd);
32static void index_to_perm(int p, int n, int *r);
33static void index_to_subset(int s, int n, int k, int *r);
34static void int_to_digit_array(int a, int b, int n, int *r);
35static void int_to_sum_zero_array(int x, int b, int n, int *a);
36static int invert_digits(int a, int b, int n);
37static bool is_perm(int *a, int n);
38static bool is_subset(int *a, int n, int k);
39static Cube move_via_arrays(CubeArray *arr, Cube c, PieceFilter pf);
40static void movelist_to_position(Move *movelist, int *position);
41static void moveset_to_list(Moveset ms, Checker f, Move *r);
42static AlgList * new_alglist();
43static CubeArray * new_cubearray(Cube cube, PieceFilter f);
44static int perm_sign(int *a, int n);
45static int perm_to_index(int *a, int n);
46static int powint(int a, int b);
47static bool ptable_has_reached(PruneData *pd, uint64_t ind);
48static void ptable_set_reached(PruneData *pd, uint64_t ind);
49static void ptable_update(PruneData *pd, uint64_t ind, int m);
50static void realloc_alg(Alg *alg, int n);
51static bool read_algset_file(AlgSet *as);
52static bool read_mtables_file();
53static bool read_ptable_file(PruneData *pd);
54static bool read_ttables_file();
55static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f);
56static int subset_to_index(int *a, int n, int k);
57static void sum_arrays_mod(int *src, int *dst, int n, int m);
58static void swap(int *a, int *b);
59static bool write_algset_file(AlgSet *as);
60static bool write_mtables_file();
61static bool write_ptable_file(PruneData *pd);
62static bool write_ttables_file();
63
64static void init_auxtables();
65static void init_cphtr_cosets();
66static void init_cphtr_cosets_bfs(int i, int c);
67static void init_environment();
68static void init_moves();
69static void init_moves_aux();
70static void init_strings();
71static void init_trans();
72static void init_trans_aux();
73
74/* All sorts of useful costants and tables **********************************/
75
76static char * tabledir;
77
78static PieceFilter pf_all;
79static PieceFilter pf_4val;
80static PieceFilter pf_epcp;
81static PieceFilter pf_cpos;
82static PieceFilter pf_cp;
83static PieceFilter pf_ep;
84static PieceFilter pf_e;
85static PieceFilter pf_s;
86static PieceFilter pf_m;
87static PieceFilter pf_eo;
88static PieceFilter pf_co;
89
90static int epe_solved[4];
91static int eps_solved[4];
92static int epm_solved[4];
93
94static char move_string[NMOVES][7];
95static char edge_string[12][7];
96static char corner_string[8][7];
97static char center_string[6][7];
98
99static bool commute[NMOVES][NMOVES];
100static bool possible_next[NMOVES][NMOVES][NMOVES];
101static Move inverse_move_aux[NMOVES];
102static Trans inverse_trans_aux[NTRANS];
103static int epos_dependent_aux[BINOM12ON4][BINOM12ON4];
104static int cphtr_cosets[FACTORIAL8];
105static Center what_center_at_aux[FACTORIAL6][6];
106static Corner what_corner_at_aux[FACTORIAL8][8];
107static int what_orientation_last_corner_aux[POW3TO7];
108static int what_orientation_last_edge_aux[POW2TO11];
109static Center where_is_center_aux[FACTORIAL6][6];
110static Corner where_is_corner_aux[FACTORIAL8][8];
111static Edge where_is_edge_aux[3][FACTORIAL12/FACTORIAL8][12];
112
113static int epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
114static int eposs_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
115static int eposm_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
116static int eo_ttable[NTRANS][POW2TO11];
117static int cp_ttable[NTRANS][FACTORIAL8];
118static int co_ttable[NTRANS][POW3TO7];
119static int cpos_ttable[NTRANS][FACTORIAL6];
120static Move moves_ttable[NTRANS][NMOVES];
121
122static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
123static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
124static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
125static int eofb_mtable[NMOVES][POW2TO11];
126static int eorl_mtable[NMOVES][POW2TO11];
127static int eoud_mtable[NMOVES][POW2TO11];
128static int cp_mtable[NMOVES][FACTORIAL8];
129static int coud_mtable[NMOVES][POW3TO7];
130static int cofb_mtable[NMOVES][POW3TO7];
131static int corl_mtable[NMOVES][POW3TO7];
132static int cpos_mtable[NMOVES][FACTORIAL6];
133
134static uint64_t me[12];
135
136static int edge_cycle[NMOVES][12];
137static int corner_cycle[NMOVES][8];
138static int center_cycle[NMOVES][6];
139static int eofb_flipped[NMOVES][12];
140static int eorl_flipped[NMOVES][12];
141static int eoud_flipped[NMOVES][12];
142static int coud_flipped[NMOVES][8];
143static int corl_flipped[NMOVES][8];
144static int cofb_flipped[NMOVES][8];
145static Alg * equiv_alg[NMOVES];
146
147static int epose_source[NTRANS]; /* 0=epose, 1=eposs, 2=eposm */
148static int eposs_source[NTRANS];
149static int eposm_source[NTRANS];
150static int eofb_source[NTRANS]; /* 0=eoud, 1=eorl, 2=eofb */
151static int eorl_source[NTRANS];
152static int eoud_source[NTRANS];
153static int coud_source[NTRANS]; /* 0=coud, 1=corl, 2=cofb */
154static int cofb_source[NTRANS];
155static int corl_source[NTRANS];
156static int ep_mirror[12];
157static int cp_mirror[8];
158static int cpos_mirror[6];
159static Alg * trans_algs[NROTATIONS];
160
161
162/* Local functions implementation ********************************************/
163
164static Cube
165admissible_ep(Cube cube, PieceFilter f)
166{
167 CubeArray *arr = new_cubearray(cube, f);
168 Cube ret;
169 bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
170 int i, j;
171
172 for (i = 0; i < 12; i++)
173 if (arr->ep[i] != -1)
174 used[arr->ep[i]] = true;
175
176 for (i = 0, j = 0; i < 12; i++) {
177 for ( ; j < 11 && used[j]; j++);
178 if (arr->ep[i] == -1)
179 arr->ep[i] = j++;
180 }
181
182 ret = arrays_to_cube(arr, pf_ep);
183 free_cubearray(arr, f);
184
185 return ret;
186}
187
188static bool
189allowed_next(Move move, DfsData *dd)
190{
191 if (!possible_next[dd->last2][dd->last1][move])
192 return false;
193
194 if (commute[dd->last1][move])
195 return dd->move_position[dd->last1] < dd->move_position[move];
196
197 return true;
198}
199
200static void
201append_alg(AlgList *l, Alg *alg)
202{
203 AlgListNode *node = malloc(sizeof(AlgListNode));
204 int i;
205
206 node->alg = new_alg("");
207 for (i = 0; i < alg->len; i++)
208 append_move(node->alg, alg->move[i], alg->inv[i]);
209 node->next = NULL;
210
211 if (++l->len == 1)
212 l->first = node;
213 else
214 l->last->next = node;
215 l->last = node;
216}
217
218static void
219append_move(Alg *alg, Move m, bool inverse)
220{
221 if (alg->len == alg->allocated)
222 realloc_alg(alg, 2*alg->len);
223
224 alg->move[alg->len] = m;
225 alg->inv [alg->len] = inverse;
226 alg->len++;
227}
228
229static Cube
230apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a)
231{
232 Cube ret = {0};
233 int i;
234
235 for (i = 0; i < alg->len; i++)
236 if (alg->inv[i])
237 ret = a ? apply_move(alg->move[i], ret) :
238 apply_move_cubearray(alg->move[i], ret, f);
239
240 ret = compose_filtered(c, inverse_cube(ret), f);
241
242 for (i = 0; i < alg->len; i++)
243 if (!alg->inv[i])
244 ret = a ? apply_move(alg->move[i], ret) :
245 apply_move_cubearray(alg->move[i], ret, f);
246
247 return ret;
248}
249
250static void
251apply_permutation(int *perm, int *set, int n)
252{
253 int *aux = malloc(n * sizeof(int));
254 int i;
255
256 if (!is_perm(perm, n))
257 return;
258
259 for (i = 0; i < n; i++)
260 aux[i] = set[perm[i]];
261
262 memcpy(set, aux, n * sizeof(int));
263 free(aux);
264}
265
266static Cube
267apply_move_cubearray(Move m, Cube cube, PieceFilter f)
268{
269 CubeArray m_arr = {
270 edge_cycle[m],
271 eofb_flipped[m],
272 eorl_flipped[m],
273 eoud_flipped[m],
274 corner_cycle[m],
275 coud_flipped[m],
276 corl_flipped[m],
277 cofb_flipped[m],
278 center_cycle[m]
279 };
280
281 return move_via_arrays(&m_arr, cube, f);
282}
283
284static int
285array_ep_to_epos(int *ep, int *ss)
286{
287 int epos[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
288 int eps[4];
289 int i, j, is;
290
291 for (i = 0, is = 0; i < 12; i++) {
292 for (j = 0; j < 4; j++) {
293 if (ep[i] == ss[j]) {
294 eps[is++] = j;
295 epos[i] = 1;
296 }
297 }
298 }
299
300 for (i = 0; i < 4; i++)
301 swap(&epos[ss[i]], &epos[i+8]);
302
303 return epos_from_arrays(epos, eps);
304}
305
306static Cube
307arrays_to_cube(CubeArray *arr, PieceFilter f)
308{
309 Cube ret = {0};
310
311 if (f.epose)
312 ret.epose = array_ep_to_epos(arr->ep, epe_solved);
313 if (f.eposs)
314 ret.eposs = array_ep_to_epos(arr->ep, eps_solved);
315 if (f.eposm)
316 ret.eposm = array_ep_to_epos(arr->ep, epm_solved);
317 if (f.eofb)
318 ret.eofb = digit_array_to_int(arr->eofb, 11, 2);
319 if (f.eorl)
320 ret.eorl = digit_array_to_int(arr->eorl, 11, 2);
321 if (f.eoud)
322 ret.eoud = digit_array_to_int(arr->eoud, 11, 2);
323 if (f.cp)
324 ret.cp = perm_to_index(arr->cp, 8);
325 if (f.coud)
326 ret.coud = digit_array_to_int(arr->coud, 7, 3);
327 if (f.corl)
328 ret.corl = digit_array_to_int(arr->corl, 7, 3);
329 if (f.cofb)
330 ret.cofb = digit_array_to_int(arr->cofb, 7, 3);
331 if (f.cpos)
332 ret.cpos = perm_to_index(arr->cpos, 6);
333
334 return ret;
335}
336
337static int
338binomial(int n, int k)
339{
340 if (n < 0 || k < 0 || k > n)
341 return 0;
342
343 return factorial(n) / (factorial(k) * factorial(n-k));
344}
345
346static Cube
347compose_filtered(Cube c2, Cube c1, PieceFilter f)
348{
349 CubeArray *arr = new_cubearray(c2, f);
350 Cube ret;
351
352 ret = move_via_arrays(arr, c1, f);
353 free_cubearray(arr, f);
354
355 return ret;
356}
357
358static void
359cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f)
360{
361 int i;
362
363 if (f.epose || f.eposs || f.eposm)
364 for (i = 0; i < 12; i++)
365 arr->ep[i] = -1;
366
367 if (f.epose)
368 epos_to_partial_ep(cube.epose, arr->ep, epe_solved);
369 if (f.eposs)
370 epos_to_partial_ep(cube.eposs, arr->ep, eps_solved);
371 if (f.eposm)
372 epos_to_partial_ep(cube.eposm, arr->ep, epm_solved);
373 if (f.eofb)
374 int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
375 if (f.eorl)
376 int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
377 if (f.eoud)
378 int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
379 if (f.cp)
380 index_to_perm(cube.cp, 8, arr->cp);
381 if (f.coud)
382 int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
383 if (f.corl)
384 int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
385 if (f.cofb)
386 int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
387 if (f.cpos)
388 index_to_perm(cube.cpos, 6, arr->cpos);
389}
390
391/*
392static int
393cphtr_cp(int cp)
394{
395 int i, a[8];
396
397 index_to_perm(cp, 8, a);
398
399 for (i = 0; i < 8; i++)
400 if (a[i] == UFR || a[i] == UBL || a[i] == DFL || a[i] == DBR)
401 a[i] = 0;
402 else
403 a[i] = 1;
404
405 swap(&a[1], &a[5]);
406 swap(&a[3], &a[7]);
407
408 return subset_to_index(a, 8, 4);
409}
410*/
411
412static void
413dfs(Cube c, Step s, SolveOptions *opts, DfsData *dd)
414{
415 if (dfs_stop(c, s, opts, dd))
416 return;
417
418 if (dfs_check_solved(opts, dd))
419 return;
420
421 dfs_branch(c, s, opts, dd);
422
423 if (opts->can_niss && !dd->niss)
424 dfs_niss(c, s, opts, dd);
425}
426
427static void
428dfs_branch(Cube c, Step s, SolveOptions *opts, DfsData *dd)
429{
430 Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
431
432 int i, maxnsol = opts->max_solutions;
433
434 for (i = 0; (m=moves[i]) != NULLMOVE && dd->sols->len < maxnsol; i++) {
435 if (allowed_next(m, dd)) {
436 dd->last2 = dd->last1;
437 dd->last1 = m;
438 append_move(dd->current_alg, m, dd->niss);
439
440 dfs(apply_move(m, c), s, opts, dd);
441
442 dd->current_alg->len--;
443 dd->last2 = l2;
444 dd->last1 = l1;
445 }
446 }
447}
448
449static bool
450dfs_check_solved(SolveOptions *opts, DfsData *dd)
451{
452 if (dd->lb != 0)
453 return false;
454
455 if (dd->current_alg->len == dd->d) {
456 append_alg(dd->sols, dd->current_alg);
457
458 if (opts->feedback)
459 print_alg(dd->current_alg, false);
460 }
461
462 return true;
463}
464
465static void
466dfs_niss(Cube c, Step s, SolveOptions *opts, DfsData *dd)
467{
468 Move l1 = dd->last1, l2 = dd->last2;
469
470 if (dd->current_alg->len == 0 ||
471 (s.check(apply_move(inverse_move(l1), (Cube){0}), 1))) {
472 dd->niss = true;
473 dd->last1 = NULLMOVE;
474 dd->last2 = NULLMOVE;
475
476 dfs(inverse_cube(c), s, opts, dd);
477
478 dd->last1 = l1;
479 dd->last2 = l2;
480 dd->niss = false;
481 }
482}
483
484static bool
485dfs_stop(Cube c, Step s, SolveOptions *opts, DfsData *dd)
486{
487 if (dd->sols->len >= opts->max_solutions)
488 return true;
489
490 dd->lb = s.check(c, dd->d - dd->current_alg->len);
491 if (opts->can_niss && !dd->niss)
492 dd->lb = MIN(1, dd->lb);
493
494 if (dd->current_alg->len + dd->lb > dd->d)
495 return true;
496
497 return false;
498}
499
500static int
501digit_array_to_int(int *a, int n, int b)
502{
503 int i, ret = 0, p = 1;
504
505 for (i = 0; i < n; i++, p *= b)
506 ret += a[i] * p;
507
508 return ret;
509}
510
511static int
512edge_slice(Edge e) {
513 if (e < 0 || e > 11)
514 return -1;
515
516 if (e == FR || e == FL || e == BL || e == BR)
517 return 0;
518 if (e == UR || e == UL || e == DR || e == DL)
519 return 1;
520
521 return 2;
522}
523
524static int
525epos_dependent_pos(int poss, int pose)
526{
527 int ep[12] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
528 int ep8[8] = {0, 0, 0, 0, 0, 0, 0, 0};
529 int i, j;
530
531 epos_to_partial_ep(poss*FACTORIAL4, ep, eps_solved);
532 epos_to_partial_ep(pose*FACTORIAL4, ep, epe_solved);
533
534 for (i = 0, j = 0; i < 12; i++)
535 if (edge_slice(ep[i]) != 0)
536 ep8[j++] = (edge_slice(ep[i]) == 1) ? 1 : 0;
537
538 swap(&ep8[1], &ep8[4]);
539 swap(&ep8[3], &ep8[6]);
540
541 return subset_to_index(ep8, 8, 4);
542}
543
544static int
545epos_from_arrays(int *epos, int *ep)
546{
547 return FACTORIAL4 * subset_to_index(epos,12,4) + perm_to_index(ep,4);
548}
549
550static void
551epos_to_partial_ep(int epos, int *ep, int *ss)
552{
553 int i, is, eposs[12], eps[4];
554
555 index_to_perm(epos % FACTORIAL4, 4, eps);
556 index_to_subset(epos / FACTORIAL4, 12, 4, eposs);
557
558 for (i = 0; i < 4; i++)
559 swap(&eposs[ss[i]], &eposs[i+8]);
560
561 for (i = 0, is = 0; i < 12; i++)
562 if (eposs[i])
563 ep[i] = ss[eps[is++]];
564}
565
566static int
567factorial(int n)
568{
569 int i, ret = 1;
570
571 if (n < 0)
572 return 0;
573
574 for (i = 1; i <= n; i++)
575 ret *= i;
576
577 return ret;
578}
579
580void
581free_alg(Alg *alg)
582{
583 free(alg->move);
584 free(alg->inv);
585 free(alg);
586}
587
588void
589free_alglist(AlgList *l)
590{
591 AlgListNode *aux, *i = l->first;
592
593 while (i != NULL) {
594 aux = i->next;
595 free_alglistnode(i);
596 i = aux;
597 }
598 free(l);
599}
600
601void
602free_alglistnode(AlgListNode *aln)
603{
604 free_alg(aln->alg);
605 free(aln);
606}
607
608static void
609free_cubearray(CubeArray *arr, PieceFilter f)
610{
611 if (f.epose || f.eposs || f.eposm)
612 free(arr->ep);
613 if (f.eofb)
614 free(arr->eofb);
615 if (f.eorl)
616 free(arr->eorl);
617 if (f.eoud)
618 free(arr->eoud);
619 if (f.cp)
620 free(arr->cp);
621 if (f.coud)
622 free(arr->coud);
623 if (f.corl)
624 free(arr->corl);
625 if (f.cofb)
626 free(arr->cofb);
627 if (f.cpos)
628 free(arr->cpos);
629
630 free(arr);
631}
632
633static void
634genptable_dfs(Cube c, PruneData *pd, DfsData *dd)
635{
636 uint64_t ind = pd->index(c);
637 int oldval = ptableval(pd, ind);
638
639 if (oldval < dd->m || ptable_has_reached(pd, ind) || pd->n == pd->size)
640 return;
641
642 ptable_set_reached(pd, ind);
643
644 if (dd->m == dd->d) {
645 if (dd->m < oldval)
646 ptable_update(pd, ind, dd->m);
647 return;
648 }
649
650 genptable_dfs_branch(c, pd, dd);
651}
652
653static void
654genptable_dfs_branch(Cube c, PruneData *pd, DfsData *dd)
655{
656 Move i, move, l1 = dd->last1, l2 = dd->last2;
657
658 dd->m++;
659
660 for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) {
661 move = dd->sorted_moves[i];
662 if (allowed_next(move, dd)) {
663 dd->last2 = dd->last1;
664 dd->last1 = move;
665
666 genptable_dfs(apply_move(move, c), pd, dd);
667
668 dd->last2 = l2;
669 dd->last1 = l1;
670 }
671 }
672
673 dd->m--;
674}
675
676static void
677index_to_perm(int p, int n, int *r)
678{
679 int *a = malloc(n * sizeof(int));
680 int i, j, c;
681
682 for (i = 0; i < n; i++)
683 a[i] = 0;
684
685 if (p < 0 || p >= factorial(n))
686 for (i = 0; i < n; i++)
687 r[i] = -1;
688
689 for (i = 0; i < n; i++) {
690 c = 0;
691 j = 0;
692 while (c <= p / factorial(n-i-1))
693 c += a[j++] ? 0 : 1;
694 r[i] = j-1;
695 a[j-1] = 1;
696 p %= factorial(n-i-1);
697 }
698
699 free(a);
700}
701
702static void
703index_to_subset(int s, int n, int k, int *r)
704{
705 int i, j, v;
706
707 if (s < 0 || s >= binomial(n, k)) {
708 for (i = 0; i < n; i++)
709 r[i] = -1;
710 return;
711 }
712
713 for (i = 0; i < n; i++) {
714 if (k == n-i) {
715 for (j = i; j < n; j++)
716 r[j] = 1;
717 return;
718 }
719
720 if (k == 0) {
721 for (j = i; j < n; j++)
722 r[j] = 0;
723 return;
724 }
725
726 v = binomial(n-i-1, k);
727 if (s >= v) {
728 r[i] = 1;
729 k--;
730 s -= v;
731 } else {
732 r[i] = 0;
733 }
734 }
735}
736
737static void
738int_to_digit_array(int a, int b, int n, int *r)
739{
740 int i;
741
742 if (b <= 1)
743 for (i = 0; i < n; i++)
744 r[i] = 0;
745 else
746 for (i = 0; i < n; i++, a /= b)
747 r[i] = a % b;
748}
749
750static void
751int_to_sum_zero_array(int x, int b, int n, int *a)
752{
753 int i, s = 0;
754
755 if (b <= 1) {
756 for (i = 0; i < n; i++)
757 a[i] = 0;
758 } else {
759 int_to_digit_array(x, b, n-1, a);
760 for (i = 0; i < n - 1; i++)
761 s = (s + a[i]) % b;
762 a[n-1] = (b - s) % b;
763 }
764}
765
766static int
767invert_digits(int a, int b, int n)
768{
769 int i, ret, *r = malloc(n * sizeof(int));
770
771 int_to_digit_array(a, b, n, r);
772 for (i = 0; i < n; i++)
773 r[i] = (b-r[i]) % b;
774
775 ret = digit_array_to_int(r, n, b);
776 free(r);
777 return ret;
778}
779
780static bool
781is_perm(int *a, int n)
782{
783 int *aux = malloc(n * sizeof(int));
784 int i;
785
786 for (i = 0; i < n; i++)
787 if (a[i] < 0 || a[i] >= n)
788 return false;
789 else
790 aux[a[i]] = 1;
791
792 for (i = 0; i < n; i++)
793 if (!aux[i])
794 return false;
795
796 free(aux);
797
798 return true;
799}
800
801static bool
802is_subset(int *a, int n, int k)
803{
804 int i, sum = 0;
805
806 for (i = 0; i < n; i++)
807 sum += a[i] ? 1 : 0;
808
809 return sum == k;
810}
811
812static Cube
813move_via_arrays(CubeArray *arr, Cube c, PieceFilter f)
814{
815 CubeArray *arrc = new_cubearray(c, f);
816 Cube ret;
817
818 if (f.epose || f.eposs || f.eposm)
819 apply_permutation(arr->ep, arrc->ep, 12);
820
821 if (f.eofb) {
822 apply_permutation(arr->ep, arrc->eofb, 12);
823 sum_arrays_mod(arr->eofb, arrc->eofb, 12, 2);
824 }
825
826 if (f.eorl) {
827 apply_permutation(arr->ep, arrc->eorl, 12);
828 sum_arrays_mod(arr->eorl, arrc->eorl, 12, 2);
829 }
830
831 if (f.eoud) {
832 apply_permutation(arr->ep, arrc->eoud, 12);
833 sum_arrays_mod(arr->eoud, arrc->eoud, 12, 2);
834 }
835
836 if (f.cp)
837 apply_permutation(arr->cp, arrc->cp, 8);
838
839 if (f.coud) {
840 apply_permutation(arr->cp, arrc->coud, 8);
841 sum_arrays_mod(arr->coud, arrc->coud, 8, 3);
842 }
843
844 if (f.corl) {
845 apply_permutation(arr->cp, arrc->corl, 8);
846 sum_arrays_mod(arr->corl, arrc->corl, 8, 3);
847 }
848
849 if (f.cofb) {
850 apply_permutation(arr->cp, arrc->cofb, 8);
851 sum_arrays_mod(arr->cofb, arrc->cofb, 8, 3);
852 }
853
854 if (f.cpos)
855 apply_permutation(arr->cpos, arrc->cpos, 6);
856
857 ret = arrays_to_cube(arrc, f);
858 free_cubearray(arrc, f);
859
860 return ret;
861}
862
863static void
864movelist_to_position(Move *movelist, int *position)
865{
866 Move m;
867
868 for (m = 0; m < NMOVES && movelist[m] != NULLMOVE; m++)
869 position[movelist[m]] = m;
870}
871
872static void
873moveset_to_list(Moveset ms, Checker f, Move *r)
874{
875 Cube c;
876 int b[NMOVES];
877 int na = 0, nb = 0;
878 Move i;
879
880 if (ms == NULL) {
881 fprintf(stderr, "Error: no moveset given\n");
882 return;
883 }
884
885 for (i = U; i < NMOVES; i++) {
886 if (ms(i)) {
887 c = apply_move(i, (Cube){0});
888 if (f != NULL && f(c, 1))
889 r[na++] = i;
890 else
891 b[nb++] = i;
892 }
893 }
894
895 memcpy(r + na, b, nb * sizeof(Move));
896 r[na+nb] = NULLMOVE;
897}
898
899static AlgList *
900new_alglist()
901{
902 AlgList *ret = malloc(sizeof(AlgList));
903
904 ret->len = 0;
905 ret->first = NULL;
906 ret->last = NULL;
907
908 return ret;
909}
910
911static CubeArray *
912new_cubearray(Cube cube, PieceFilter f)
913{
914 CubeArray *arr = malloc(sizeof(CubeArray));
915
916 if (f.epose || f.eposs || f.eposm)
917 arr->ep = malloc(12 * sizeof(int));
918 if (f.eofb)
919 arr->eofb = malloc(12 * sizeof(int));
920 if (f.eorl)
921 arr->eorl = malloc(12 * sizeof(int));
922 if (f.eoud)
923 arr->eoud = malloc(12 * sizeof(int));
924 if (f.cp)
925 arr->cp = malloc(8 * sizeof(int));
926 if (f.coud)
927 arr->coud = malloc(8 * sizeof(int));
928 if (f.corl)
929 arr->corl = malloc(8 * sizeof(int));
930 if (f.cofb)
931 arr->cofb = malloc(8 * sizeof(int));
932 if (f.cpos)
933 arr->cpos = malloc(6 * sizeof(int));
934
935 cube_to_arrays(cube, arr, f);
936
937 return arr;
938}
939
940static int
941perm_sign(int *a, int n)
942{
943 int i, j, ret = 0;
944
945 if (!is_perm(a,n))
946 return -1;
947
948 for (i = 0; i < n; i++)
949 for (j = i+1; j < n; j++)
950 ret += (a[i] > a[j]) ? 1 : 0;
951
952 return ret % 2;
953}
954
955static int
956perm_to_index(int *a, int n)
957{
958 int i, j, c, ret = 0;
959
960 if (!is_perm(a, n))
961 return -1;
962
963 for (i = 0; i < n; i++) {
964 c = 0;
965 for (j = i+1; j < n; j++)
966 c += (a[i] > a[j]) ? 1 : 0;
967 ret += factorial(n-i-1) * c;
968 }
969
970 return ret;
971}
972
973static int
974powint(int a, int b)
975{
976 if (b < 0)
977 return 0;
978 if (b == 0)
979 return 1;
980
981 if (b % 2)
982 return a * powint(a, b-1);
983 else
984 return powint(a*a, b/2);
985}
986
987static bool
988ptable_has_reached(PruneData *pd, uint64_t ind)
989{
990 return (ind % 2) ? pd->reached[ind/2] / 16 : pd->reached[ind/2] % 16;
991}
992
993static void
994ptable_set_reached(PruneData *pd, uint64_t ind)
995{
996 uint8_t oldval2 = pd->reached[ind/2];
997 int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
998
999 pd->reached[ind/2] = (ind % 2) ? 16 + other : 16*other + 1;
1000}
1001
1002static void
1003ptable_update(PruneData *pd, uint64_t ind, int n)
1004{
1005 uint8_t oldval2 = pd->ptable[ind/2];
1006 int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
1007
1008 pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n;
1009 pd->n++;
1010}
1011
1012static void
1013realloc_alg(Alg *alg, int n)
1014{
1015 if (alg == NULL) {
1016 fprintf(stderr, "Error: trying to reallocate NULL alg.\n");
1017 return;
1018 }
1019
1020 if (n < alg->len) {
1021 fprintf(stderr, "Error: alg too long for reallocation ");
1022 fprintf(stderr, "(%d vs %d)\n", alg->len, n);
1023 return;
1024 }
1025
1026 if (n > 1000000) {
1027 fprintf(stderr, "Warning: very long alg,");
1028 fprintf(stderr, "something might go wrong.\n");
1029 }
1030
1031 alg->move = realloc(alg->move, n * sizeof(int));
1032 alg->inv = realloc(alg->inv, n * sizeof(int));
1033 alg->allocated = n;
1034}
1035
1036static bool
1037read_algset_file(AlgSet *as)
1038{
1039 return false;
1040}
1041
1042static bool
1043read_mtables_file()
1044{
1045 FILE *f;
1046 char fname[strlen(tabledir)+20];
1047 int m, b = sizeof(int);
1048 bool r = true;
1049
1050 strcpy(fname, tabledir);
1051 strcat(fname, "/mtables");
1052
1053 if ((f = fopen(fname, "rb")) == NULL)
1054 return false;
1055
1056 for (m = 0; m < NMOVES; m++) {
1057 r = r && fread(epose_mtable[m], b, me[0], f) == me[0];
1058 r = r && fread(eposs_mtable[m], b, me[1], f) == me[1];
1059 r = r && fread(eposm_mtable[m], b, me[2], f) == me[2];
1060 r = r && fread(eofb_mtable[m], b, me[3], f) == me[3];
1061 r = r && fread(eorl_mtable[m], b, me[4], f) == me[4];
1062 r = r && fread(eoud_mtable[m], b, me[5], f) == me[5];
1063 r = r && fread(cp_mtable[m], b, me[6], f) == me[6];
1064 r = r && fread(coud_mtable[m], b, me[7], f) == me[7];
1065 r = r && fread(corl_mtable[m], b, me[8], f) == me[8];
1066 r = r && fread(cofb_mtable[m], b, me[9], f) == me[9];
1067 r = r && fread(cpos_mtable[m], b, me[10], f) == me[10];
1068 }
1069
1070 fclose(f);
1071 return r;
1072}
1073
1074static bool
1075read_ptable_file(PruneData *pd)
1076{
1077 FILE *f;
1078 char fname[strlen(tabledir)+100];
1079 uint64_t r;
1080
1081 strcpy(fname, tabledir);
1082 strcat(fname, "/");
1083 strcat(fname, pd->filename);
1084
1085 if ((f = fopen(fname, "rb")) == NULL)
1086 return false;
1087
1088 r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
1089 fclose(f);
1090
1091 return r == ptablesize(pd);
1092}
1093
1094static bool
1095read_ttables_file()
1096{
1097 FILE *f;
1098 char fname[strlen(tabledir)+20];
1099 int b = sizeof(int);
1100 bool r = true;
1101 Move m;
1102
1103 strcpy(fname, tabledir);
1104 strcat(fname, "/");
1105 strcat(fname, "ttables");
1106
1107 if ((f = fopen(fname, "rb")) == NULL)
1108 return false;
1109
1110 for (m = 0; m < NTRANS; m++) {
1111 r = r && fread(epose_ttable[m], b, me[0], f) == me[0];
1112 r = r && fread(eposs_ttable[m], b, me[1], f) == me[1];
1113 r = r && fread(eposm_ttable[m], b, me[2], f) == me[2];
1114 r = r && fread(eo_ttable[m], b, me[3], f) == me[3];
1115 r = r && fread(cp_ttable[m], b, me[6], f) == me[6];
1116 r = r && fread(co_ttable[m], b, me[7], f) == me[7];
1117 r = r && fread(cpos_ttable[m], b, me[10], f) == me[10];
1118 r = r && fread(moves_ttable[m], b, me[11], f) == me[11];
1119 }
1120
1121 fclose(f);
1122 return r;
1123}
1124
1125static Cube
1126rotate_via_compose(Trans r, Cube c, PieceFilter f)
1127{
1128 Alg *inv;
1129 static int zero12[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
1130 static int zero8[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
1131 static CubeArray ma = {
1132 .ep = ep_mirror,
1133 .eofb = zero12,
1134 .eorl = zero12,
1135 .eoud = zero12,
1136 .cp = cp_mirror,
1137 .coud = zero8,
1138 .corl = zero8,
1139 .cofb = zero8,
1140 .cpos = cpos_mirror
1141 };
1142
1143 Cube ret;
1144
1145 if (r != mirror) {
1146 ret = apply_alg_generic(trans_algs[r], c, f, true);
1147 inv = on_inverse(trans_algs[r]);
1148 ret = apply_alg_generic(inv, ret, f, true);
1149 free_alg(inv);
1150 } else {
1151 ret = move_via_arrays(&ma, (Cube){0}, f);
1152 ret = compose_filtered(c, ret, f);
1153 ret = move_via_arrays(&ma, ret, f);
1154 }
1155
1156 return ret;
1157}
1158
1159static int
1160subset_to_index(int *a, int n, int k)
1161{
1162 int i, ret = 0;
1163
1164 if (!is_subset(a, n, k))
1165 return binomial(n, k);
1166
1167 for (i = 0; i < n; i++) {
1168 if (k == n-i)
1169 return ret;
1170 if (a[i]) {
1171 ret += binomial(n-i-1, k);
1172 k--;
1173 }
1174 }
1175
1176 return ret;
1177}
1178
1179static void
1180sum_arrays_mod(int *src, int *dst, int n, int m)
1181{
1182 int i;
1183
1184 for (i = 0; i < n; i++)
1185 dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m;
1186}
1187
1188static void
1189swap(int *a, int *b)
1190{
1191 int aux;
1192
1193 aux = *a;
1194 *a = *b;
1195 *b = aux;
1196}
1197
1198static bool
1199write_algset_file(AlgSet *as)
1200{
1201 return false;
1202}
1203
1204static bool
1205write_mtables_file()
1206{
1207 FILE *f;
1208 char fname[strlen(tabledir)+20];
1209 int m, b = sizeof(int);
1210 bool r = true;
1211
1212 strcpy(fname, tabledir);
1213 strcat(fname, "/mtables");
1214
1215 if ((f = fopen(fname, "wb")) == NULL)
1216 return false;
1217
1218 for (m = 0; m < NMOVES; m++) {
1219 r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0];
1220 r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1];
1221 r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2];
1222 r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3];
1223 r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4];
1224 r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5];
1225 r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6];
1226 r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7];
1227 r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8];
1228 r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9];
1229 r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10];
1230 }
1231
1232 fclose(f);
1233 return r;
1234}
1235
1236static bool
1237write_ptable_file(PruneData *pd)
1238{
1239 FILE *f;
1240 char fname[strlen(tabledir)+100];
1241 uint64_t written;
1242
1243 strcpy(fname, tabledir);
1244 strcat(fname, "/");
1245 strcat(fname, pd->filename);
1246
1247 if ((f = fopen(fname, "wb")) == NULL)
1248 return false;
1249
1250 written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
1251 fclose(f);
1252
1253 return written == ptablesize(pd);
1254}
1255
1256static bool
1257write_ttables_file()
1258{
1259 FILE *f;
1260 char fname[strlen(tabledir)+20];
1261 bool r = true;
1262 int b = sizeof(int);
1263 Move m;
1264
1265 strcpy(fname, tabledir);
1266 strcat(fname, "/ttables");
1267
1268 if ((f = fopen(fname, "wb")) == NULL)
1269 return false;
1270
1271 for (m = 0; m < NTRANS; m++) {
1272 r = r && fwrite(epose_ttable[m], b, me[0], f) == me[0];
1273 r = r && fwrite(eposs_ttable[m], b, me[1], f) == me[1];
1274 r = r && fwrite(eposm_ttable[m], b, me[2], f) == me[2];
1275 r = r && fwrite(eo_ttable[m], b, me[3], f) == me[3];
1276 r = r && fwrite(cp_ttable[m], b, me[6], f) == me[6];
1277 r = r && fwrite(co_ttable[m], b, me[7], f) == me[7];
1278 r = r && fwrite(cpos_ttable[m], b, me[10], f) == me[10];
1279 r = r && fwrite(moves_ttable[m], b, me[11], f) == me[11];
1280 }
1281
1282 fclose(f);
1283 return r;
1284}
1285
1286/* Init functions implementation *********************************************/
1287
1288static void
1289init_auxtables()
1290{
1291 Cube c1, c2;
1292 CubeArray *arr;
1293 uint64_t ui, uj;
1294 int i, j, k, auxarr[12];
1295 bool cij, p1, p2;
1296
1297 for (ui = 0; ui < FACTORIAL6; ui++) {
1298 arr = new_cubearray((Cube){.cpos = ui}, pf_cpos);
1299 for (i = 0; i < 6; i++) {
1300 what_center_at_aux[ui][i] = arr->cpos[i];
1301 where_is_center_aux[ui][arr->cpos[i]] = i;
1302 }
1303 free_cubearray(arr, pf_cpos);
1304 }
1305
1306 for (ui = 0; ui < FACTORIAL8; ui++) {
1307 arr = new_cubearray((Cube){.cp = ui}, pf_cp);
1308 for (i = 0; i < 8; i++) {
1309 what_corner_at_aux[ui][i] = arr->cp[i];
1310 where_is_corner_aux[ui][arr->cp[i]] = i;
1311 }
1312 free_cubearray(arr, pf_cp);
1313 }
1314
1315 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
1316 arr = new_cubearray((Cube){.epose = ui}, pf_e);
1317 for (i = 0; i < 12; i++)
1318 if (edge_slice(arr->ep[i]) == 0)
1319 where_is_edge_aux[0][ui][arr->ep[i]] = i;
1320 free_cubearray(arr, pf_e);
1321
1322 arr = new_cubearray((Cube){.eposs = ui}, pf_s);
1323 for (i = 0; i < 12; i++)
1324 if (edge_slice(arr->ep[i]) == 1)
1325 where_is_edge_aux[1][ui][arr->ep[i]] = i;
1326 free_cubearray(arr, pf_s);
1327
1328 arr = new_cubearray((Cube){.eposm = ui}, pf_m);
1329 for (i = 0; i < 12; i++)
1330 if (edge_slice(arr->ep[i]) == 2)
1331 where_is_edge_aux[2][ui][arr->ep[i]] = i;
1332 free_cubearray(arr, pf_m);
1333 }
1334
1335 for (ui = 0; ui < POW3TO7; ui++) {
1336 int_to_sum_zero_array(ui, 3, 8, auxarr);
1337 what_orientation_last_corner_aux[ui] = auxarr[7];
1338 }
1339
1340 for (ui = 0; ui < POW2TO11; ui++) {
1341 int_to_sum_zero_array(ui, 2, 12, auxarr);
1342 what_orientation_last_edge_aux[ui] = auxarr[11];
1343 }
1344
1345 for (ui = 0; ui < BINOM12ON4; ui++)
1346 for (uj = 0; uj < BINOM12ON4; uj++)
1347 epos_dependent_aux[ui][uj]=epos_dependent_pos(ui, uj);
1348
1349 for (i = 0; i < NMOVES; i++) {
1350 for (j = 0; j < NMOVES; j++) {
1351 c1 = apply_move(i, apply_move(j, (Cube){0}));
1352 c2 = apply_move(j, apply_move(i, (Cube){0}));
1353 commute[i][j] = equal(c1, c2) && i && j;
1354 }
1355 }
1356
1357 for (i = 0; i < NMOVES; i++) {
1358 for (j = 0; j < NMOVES; j++) {
1359 for (k = 0; k < NMOVES; k++) {
1360 p1 = j && base_move(j) == base_move(k);
1361 p2 = i && base_move(i) == base_move(k);
1362 cij = commute[i][j];
1363 possible_next[i][j][k] = !(p1 || (cij && p2));
1364 }
1365 }
1366 }
1367
1368 for (i = 0; i < NMOVES; i++)
1369 inverse_move_aux[i] = i ? i + 2 - 2*((i-1)%3) : NULLMOVE;
1370
1371 /* Is there a more elegant way? */
1372 inverse_trans_aux[uf] = uf;
1373 inverse_trans_aux[ur] = ul;
1374 inverse_trans_aux[ul] = ur;
1375 inverse_trans_aux[ub] = ub;
1376
1377 inverse_trans_aux[df] = df;
1378 inverse_trans_aux[dr] = dr;
1379 inverse_trans_aux[dl] = dl;
1380 inverse_trans_aux[db] = db;
1381
1382 inverse_trans_aux[rf] = lf;
1383 inverse_trans_aux[rd] = bl;
1384 inverse_trans_aux[rb] = rb;
1385 inverse_trans_aux[ru] = fr;
1386
1387 inverse_trans_aux[lf] = rf;
1388 inverse_trans_aux[ld] = br;
1389 inverse_trans_aux[lb] = lb;
1390 inverse_trans_aux[lu] = fl;
1391
1392 inverse_trans_aux[fu] = fu;
1393 inverse_trans_aux[fr] = ru;
1394 inverse_trans_aux[fd] = bu;
1395 inverse_trans_aux[fl] = lu;
1396
1397 inverse_trans_aux[bu] = fd;
1398 inverse_trans_aux[br] = ld;
1399 inverse_trans_aux[bd] = bd;
1400 inverse_trans_aux[bl] = rd;
1401
1402 inverse_trans_aux[mirror] = mirror;
1403}
1404
1405/*
1406 * There is certainly a bette way to do this, but for now I just use
1407 * a "graph coloring" algorithm to compute the cosets for cphtr.
1408 *
1409 * For doing it better "Mathematically", we need 3 things:
1410 * - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other
1411 * This is easy and it is done in the commented function cphtr_cp().
1412 * - Check that there is no ep/cp parity
1413 * - Check that we are not in the "3c" case; this is the part I don't
1414 * know how to do.
1415 */
1416static void
1417init_cphtr_cosets()
1418{
1419 unsigned int i;
1420 int c = 0;
1421
1422 for (i = 0; i < FACTORIAL8; i++)
1423 cphtr_cosets[i] = -1;
1424
1425 for (i = 0; i < FACTORIAL8; i++)
1426 if (cphtr_cosets[i] == -1)
1427 init_cphtr_cosets_bfs(i, c++);
1428}
1429
1430static void
1431init_cphtr_cosets_bfs(int i, int c)
1432{
1433 int j, jj, k, next[FACTORIAL8], next2[FACTORIAL8], n, n2;
1434 Move moves[6] = {U2, D2, R2, L2, F2, B2};
1435
1436 n = 1;
1437 next[0] = i;
1438 cphtr_cosets[i] = c;
1439
1440 while (n != 0) {
1441 for (j = 0, n2 = 0; j < n; j++) {
1442 for (k = 0; k < 6; k++) {
1443 jj = cp_mtable[moves[k]][next[j]];
1444 if (cphtr_cosets[jj] == -1) {
1445 cphtr_cosets[jj] = c;
1446 next2[n2++] = jj;
1447 }
1448 }
1449 }
1450
1451 for (j = 0; j < n2; j++)
1452 next[j] = next2[j];
1453 n = n2;
1454 }
1455}
1456
1457static void
1458init_environment()
1459{
1460 char *nissydata = getenv("NISSYDATA");
1461 char *localdata = getenv("XDG_DATA_HOME");
1462 char *home = getenv("HOME");
1463 bool read, write;
1464
1465 if (nissydata != NULL) {
1466 tabledir = malloc(strlen(nissydata) * sizeof(char) + 20);
1467 strcpy(tabledir, nissydata);
1468 } else if (localdata != NULL) {
1469 tabledir = malloc(strlen(localdata) * sizeof(char) + 20);
1470 strcpy(tabledir, localdata);
1471 strcat(tabledir, "/nissy");
1472 } else if (home != NULL) {
1473 tabledir = malloc(strlen(home) * sizeof(char) + 20);
1474 strcpy(tabledir, home);
1475 strcat(tabledir, "/.nissy");
1476 }
1477
1478 mkdir(tabledir, 0777);
1479 strcat(tabledir, "/tables");
1480 mkdir(tabledir, 0777);
1481
1482 read = !access(tabledir, R_OK);
1483 write = !access(tabledir, W_OK);
1484
1485 if (!read) {
1486 fprintf(stderr, "Table files cannot be read.\n");
1487 } else if (!write) {
1488 fprintf(stderr, "Data directory not writable: ");
1489 fprintf(stderr, "tables can be loaded, but not saved.\n");
1490 }
1491}
1492
1493static void
1494init_moves() {
1495 Cube c;
1496 CubeArray arrs;
1497 int i;
1498 unsigned int ui;
1499 Move m;
1500
1501 /* Generate all move cycles and flips; I do this regardless */
1502 for (i = 0; i < NMOVES; i++) {
1503 if (i == U || i == x || i == y)
1504 continue;
1505
1506 c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false);
1507
1508 arrs = (CubeArray) {
1509 edge_cycle[i],
1510 eofb_flipped[i],
1511 eorl_flipped[i],
1512 eoud_flipped[i],
1513 corner_cycle[i],
1514 coud_flipped[i],
1515 corl_flipped[i],
1516 cofb_flipped[i],
1517 center_cycle[i]
1518 };
1519 cube_to_arrays(c, &arrs, pf_all);
1520 }
1521
1522 if (read_mtables_file())
1523 return;
1524
1525 fprintf(stderr, "Cannot load %s, generating it\n", "mtables");
1526
1527 /* Initialize transition tables */
1528 for (m = 0; m < NMOVES; m++) {
1529 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
1530 c = (Cube){ .epose = ui };
1531 c = apply_move_cubearray(m, c, pf_e);
1532 epose_mtable[m][ui] = c.epose;
1533
1534 c = (Cube){ .eposs = ui };
1535 c = apply_move_cubearray(m, c, pf_s);
1536 eposs_mtable[m][ui] = c.eposs;
1537
1538 c = (Cube){ .eposm = ui };
1539 c = apply_move_cubearray(m, c, pf_m);
1540 eposm_mtable[m][ui] = c.eposm;
1541 }
1542 for (ui = 0; ui < POW2TO11; ui++ ) {
1543 c = (Cube){ .eofb = ui };
1544 c = apply_move_cubearray(m, c, pf_eo);
1545 eofb_mtable[m][ui] = c.eofb;
1546
1547 c = (Cube){ .eorl = ui };
1548 c = apply_move_cubearray(m, c, pf_eo);
1549 eorl_mtable[m][ui] = c.eorl;
1550
1551 c = (Cube){ .eoud = ui };
1552 c = apply_move_cubearray(m, c, pf_eo);
1553 eoud_mtable[m][ui] = c.eoud;
1554 }
1555 for (ui = 0; ui < POW3TO7; ui++) {
1556 c = (Cube){ .coud = ui };
1557 c = apply_move_cubearray(m, c, pf_co);
1558 coud_mtable[m][ui] = c.coud;
1559
1560 c = (Cube){ .corl = ui };
1561 c = apply_move_cubearray(m, c, pf_co);
1562 corl_mtable[m][ui] = c.corl;
1563
1564 c = (Cube){ .cofb = ui };
1565 c = apply_move_cubearray(m, c, pf_co);
1566 cofb_mtable[m][ui] = c.cofb;
1567 }
1568 for (ui = 0; ui < FACTORIAL8; ui++) {
1569 c = (Cube){ .cp = ui };
1570 c = apply_move_cubearray(m, c, pf_cp);
1571 cp_mtable[m][ui] = c.cp;
1572 }
1573 for (ui = 0; ui < FACTORIAL6; ui++) {
1574 c = (Cube){ .cpos = ui };
1575 c = apply_move_cubearray(m, c, pf_cpos);
1576 cpos_mtable[m][ui] = c.cpos;
1577 }
1578 }
1579
1580 if (!write_mtables_file())
1581 fprintf(stderr, "Error writing mtables\n");
1582}
1583
1584static void
1585init_moves_aux()
1586{
1587 /* Some standard PieceFilters */
1588 pf_all.epose = true;
1589 pf_all.eposs = true;
1590 pf_all.eposm = true;
1591 pf_all.eofb = true;
1592 pf_all.eorl = true;
1593 pf_all.eoud = true;
1594 pf_all.cp = true;
1595 pf_all.cofb = true;
1596 pf_all.corl = true;
1597 pf_all.coud = true;
1598 pf_all.cpos = true;
1599
1600 pf_4val.epose = true;
1601 pf_4val.eposs = true;
1602 pf_4val.eposm = true;
1603 pf_4val.eofb = true;
1604 pf_4val.coud = true;
1605 pf_4val.cp = true;
1606
1607 pf_epcp.epose = true;
1608 pf_epcp.eposs = true;
1609 pf_epcp.eposm = true;
1610 pf_epcp.cp = true;
1611
1612 pf_cpos.cpos = true;
1613
1614 pf_cp.cp = true;
1615
1616 pf_ep.epose = true;
1617 pf_ep.eposs = true;
1618 pf_ep.eposm = true;
1619
1620 pf_e.epose = true;
1621 pf_s.eposs = true;
1622 pf_m.eposm = true;
1623
1624 pf_eo.eofb = true;
1625 pf_eo.eorl = true;
1626 pf_eo.eoud = true;
1627
1628 pf_co.cofb = true;
1629 pf_co.corl = true;
1630 pf_co.coud = true;
1631
1632 /* Used to convert to and from CubeArray */
1633 epe_solved[0] = FR;
1634 epe_solved[1] = FL;
1635 epe_solved[2] = BL;
1636 epe_solved[3] = BR;
1637
1638 eps_solved[0] = UL;
1639 eps_solved[1] = UR;
1640 eps_solved[2] = DL;
1641 eps_solved[3] = DR;
1642
1643 epm_solved[0] = UF;
1644 epm_solved[1] = UB;
1645 epm_solved[2] = DF;
1646 epm_solved[3] = DB;
1647
1648 /* Table sizes, used for reading and writing files */
1649 me[0] = FACTORIAL12/FACTORIAL8;
1650 me[1] = FACTORIAL12/FACTORIAL8;
1651 me[2] = FACTORIAL12/FACTORIAL8;
1652 me[3] = POW2TO11;
1653 me[4] = POW2TO11;
1654 me[5] = POW2TO11;
1655 me[6] = FACTORIAL8;
1656 me[7] = POW3TO7;
1657 me[8] = POW3TO7;
1658 me[9] = POW3TO7;
1659 me[10] = FACTORIAL6;
1660 me[11] = NMOVES;
1661
1662 /* Cycles *********************/
1663 edge_cycle[U][UF] = UR;
1664 edge_cycle[U][UL] = UF;
1665 edge_cycle[U][UB] = UL;
1666 edge_cycle[U][UR] = UB;
1667 edge_cycle[U][DF] = DF;
1668 edge_cycle[U][DL] = DL;
1669 edge_cycle[U][DB] = DB;
1670 edge_cycle[U][DR] = DR;
1671 edge_cycle[U][FR] = FR;
1672 edge_cycle[U][FL] = FL;
1673 edge_cycle[U][BL] = BL;
1674 edge_cycle[U][BR] = BR;
1675
1676 edge_cycle[x][UF] = DF;
1677 edge_cycle[x][UL] = FL;
1678 edge_cycle[x][UB] = UF;
1679 edge_cycle[x][UR] = FR;
1680 edge_cycle[x][DF] = DB;
1681 edge_cycle[x][DL] = BL;
1682 edge_cycle[x][DB] = UB;
1683 edge_cycle[x][DR] = BR;
1684 edge_cycle[x][FR] = DR;
1685 edge_cycle[x][FL] = DL;
1686 edge_cycle[x][BL] = UL;
1687 edge_cycle[x][BR] = UR;
1688
1689 edge_cycle[y][UF] = UR;
1690 edge_cycle[y][UL] = UF;
1691 edge_cycle[y][UB] = UL;
1692 edge_cycle[y][UR] = UB;
1693 edge_cycle[y][DF] = DR;
1694 edge_cycle[y][DL] = DF;
1695 edge_cycle[y][DB] = DL;
1696 edge_cycle[y][DR] = DB;
1697 edge_cycle[y][FR] = BR;
1698 edge_cycle[y][FL] = FR;
1699 edge_cycle[y][BL] = FL;
1700 edge_cycle[y][BR] = BL;
1701
1702 corner_cycle[U][UFR] = UBR;
1703 corner_cycle[U][UFL] = UFR;
1704 corner_cycle[U][UBL] = UFL;
1705 corner_cycle[U][UBR] = UBL;
1706 corner_cycle[U][DFR] = DFR;
1707 corner_cycle[U][DFL] = DFL;
1708 corner_cycle[U][DBL] = DBL;
1709 corner_cycle[U][DBR] = DBR;
1710
1711 corner_cycle[x][UFR] = DFR;
1712 corner_cycle[x][UFL] = DFL;
1713 corner_cycle[x][UBL] = UFL;
1714 corner_cycle[x][UBR] = UFR;
1715 corner_cycle[x][DFR] = DBR;
1716 corner_cycle[x][DFL] = DBL;
1717 corner_cycle[x][DBL] = UBL;
1718 corner_cycle[x][DBR] = UBR;
1719
1720 corner_cycle[y][UFR] = UBR;
1721 corner_cycle[y][UFL] = UFR;
1722 corner_cycle[y][UBL] = UFL;
1723 corner_cycle[y][UBR] = UBL;
1724 corner_cycle[y][DFR] = DBR;
1725 corner_cycle[y][DFL] = DFR;
1726 corner_cycle[y][DBL] = DFL;
1727 corner_cycle[y][DBR] = DBL;
1728
1729 center_cycle[U][U_center] = U_center;
1730 center_cycle[U][D_center] = D_center;
1731 center_cycle[U][R_center] = R_center;
1732 center_cycle[U][L_center] = L_center;
1733 center_cycle[U][F_center] = F_center;
1734 center_cycle[U][B_center] = B_center;
1735
1736 center_cycle[x][U_center] = F_center;
1737 center_cycle[x][D_center] = B_center;
1738 center_cycle[x][R_center] = R_center;
1739 center_cycle[x][L_center] = L_center;
1740 center_cycle[x][F_center] = D_center;
1741 center_cycle[x][B_center] = U_center;
1742
1743 center_cycle[y][U_center] = U_center;
1744 center_cycle[y][D_center] = D_center;
1745 center_cycle[y][R_center] = B_center;
1746 center_cycle[y][L_center] = F_center;
1747 center_cycle[y][F_center] = R_center;
1748 center_cycle[y][B_center] = L_center;
1749
1750 /* Flipped pieces *************/
1751 eofb_flipped[x][UF] = 1;
1752 eofb_flipped[x][UB] = 1;
1753 eofb_flipped[x][DF] = 1;
1754 eofb_flipped[x][DB] = 1;
1755
1756 eofb_flipped[y][FR] = 1;
1757 eofb_flipped[y][FL] = 1;
1758 eofb_flipped[y][BL] = 1;
1759 eofb_flipped[y][BR] = 1;
1760
1761 eorl_flipped[x][UF] = 1;
1762 eorl_flipped[x][UL] = 1;
1763 eorl_flipped[x][UB] = 1;
1764 eorl_flipped[x][UR] = 1;
1765 eorl_flipped[x][DF] = 1;
1766 eorl_flipped[x][DL] = 1;
1767 eorl_flipped[x][DB] = 1;
1768 eorl_flipped[x][DR] = 1;
1769 eorl_flipped[x][FR] = 1;
1770 eorl_flipped[x][FL] = 1;
1771 eorl_flipped[x][BL] = 1;
1772 eorl_flipped[x][BR] = 1;
1773
1774 eorl_flipped[y][FR] = 1;
1775 eorl_flipped[y][FL] = 1;
1776 eorl_flipped[y][BL] = 1;
1777 eorl_flipped[y][BR] = 1;
1778
1779 eoud_flipped[U][UF] = 1;
1780 eoud_flipped[U][UL] = 1;
1781 eoud_flipped[U][UB] = 1;
1782 eoud_flipped[U][UR] = 1;
1783
1784 eoud_flipped[x][UF] = 1;
1785 eoud_flipped[x][UB] = 1;
1786 eoud_flipped[x][DF] = 1;
1787 eoud_flipped[x][DB] = 1;
1788
1789 eoud_flipped[y][UF] = 1;
1790 eoud_flipped[y][UL] = 1;
1791 eoud_flipped[y][UB] = 1;
1792 eoud_flipped[y][UR] = 1;
1793 eoud_flipped[y][DF] = 1;
1794 eoud_flipped[y][DL] = 1;
1795 eoud_flipped[y][DB] = 1;
1796 eoud_flipped[y][DR] = 1;
1797 eoud_flipped[y][FR] = 1;
1798 eoud_flipped[y][FL] = 1;
1799 eoud_flipped[y][BL] = 1;
1800 eoud_flipped[y][BR] = 1;
1801
1802 coud_flipped[x][UFR] = 2;
1803 coud_flipped[x][UFL] = 1;
1804 coud_flipped[x][UBR] = 1;
1805 coud_flipped[x][UBL] = 2;
1806 coud_flipped[x][DFR] = 1;
1807 coud_flipped[x][DFL] = 2;
1808 coud_flipped[x][DBR] = 2;
1809 coud_flipped[x][DBL] = 1;
1810
1811 corl_flipped[U][UFR] = 1;
1812 corl_flipped[U][UFL] = 2;
1813 corl_flipped[U][UBL] = 1;
1814 corl_flipped[U][UBR] = 2;
1815
1816 corl_flipped[y][UFR] = 1;
1817 corl_flipped[y][UFL] = 2;
1818 corl_flipped[y][UBL] = 1;
1819 corl_flipped[y][UBR] = 2;
1820 corl_flipped[y][DFR] = 2;
1821 corl_flipped[y][DFL] = 1;
1822 corl_flipped[y][DBL] = 2;
1823 corl_flipped[y][DBR] = 1;
1824
1825 cofb_flipped[U][UFR] = 2;
1826 cofb_flipped[U][UFL] = 1;
1827 cofb_flipped[U][UBL] = 2;
1828 cofb_flipped[U][UBR] = 1;
1829
1830 cofb_flipped[x][UFR] = 1;
1831 cofb_flipped[x][UFL] = 2;
1832 cofb_flipped[x][UBL] = 1;
1833 cofb_flipped[x][UBR] = 2;
1834 cofb_flipped[x][DFR] = 2;
1835 cofb_flipped[x][DFL] = 1;
1836 cofb_flipped[x][DBL] = 2;
1837 cofb_flipped[x][DBR] = 1;
1838
1839 cofb_flipped[y][UFR] = 2;
1840 cofb_flipped[y][UFL] = 1;
1841 cofb_flipped[y][UBL] = 2;
1842 cofb_flipped[y][UBR] = 1;
1843 cofb_flipped[y][DFR] = 1;
1844 cofb_flipped[y][DFL] = 2;
1845 cofb_flipped[y][DBL] = 1;
1846 cofb_flipped[y][DBR] = 2;
1847
1848 /* Equivalent moves ***********/
1849 equiv_alg[NULLMOVE] = new_alg("");
1850
1851 equiv_alg[U] = new_alg(" U ");
1852 equiv_alg[U2] = new_alg(" UU ");
1853 equiv_alg[U3] = new_alg(" UUU ");
1854 equiv_alg[D] = new_alg(" xx U xx ");
1855 equiv_alg[D2] = new_alg(" xx UU xx ");
1856 equiv_alg[D3] = new_alg(" xx UUU xx ");
1857 equiv_alg[R] = new_alg(" yx U xxxyyy ");
1858 equiv_alg[R2] = new_alg(" yx UU xxxyyy ");
1859 equiv_alg[R3] = new_alg(" yx UUU xxxyyy ");
1860 equiv_alg[L] = new_alg(" yyyx U xxxy ");
1861 equiv_alg[L2] = new_alg(" yyyx UU xxxy ");
1862 equiv_alg[L3] = new_alg(" yyyx UUU xxxy ");
1863 equiv_alg[F] = new_alg(" x U xxx ");
1864 equiv_alg[F2] = new_alg(" x UU xxx ");
1865 equiv_alg[F3] = new_alg(" x UUU xxx ");
1866 equiv_alg[B] = new_alg(" xxx U x ");
1867 equiv_alg[B2] = new_alg(" xxx UU x ");
1868 equiv_alg[B3] = new_alg(" xxx UUU x ");
1869
1870 equiv_alg[Uw] = new_alg(" xx U xx y ");
1871 equiv_alg[Uw2] = new_alg(" xx UU xx yy ");
1872 equiv_alg[Uw3] = new_alg(" xx UUU xx yyy ");
1873 equiv_alg[Dw] = new_alg(" U yyy ");
1874 equiv_alg[Dw2] = new_alg(" UU yy ");
1875 equiv_alg[Dw3] = new_alg(" UUU y ");
1876 equiv_alg[Rw] = new_alg(" yyyx U xxxy x ");
1877 equiv_alg[Rw2] = new_alg(" yyyx UU xxxy xx ");
1878 equiv_alg[Rw3] = new_alg(" yyyx UUU xxxy xxx ");
1879 equiv_alg[Lw] = new_alg(" yx U xxxyyy xxx ");
1880 equiv_alg[Lw2] = new_alg(" yx UU xxxyyy xx ");
1881 equiv_alg[Lw3] = new_alg(" yx UUU xxxyyy x ");
1882 equiv_alg[Fw] = new_alg(" xxx U x yxxxyyy ");
1883 equiv_alg[Fw2] = new_alg(" xxx UU x yxxyyy ");
1884 equiv_alg[Fw3] = new_alg(" xxx UUU x yxyyy ");
1885 equiv_alg[Bw] = new_alg(" x U xxx yxyyy ");
1886 equiv_alg[Bw2] = new_alg(" x UU xxx yxxyyy ");
1887 equiv_alg[Bw3] = new_alg(" x UUU xxx yxxxyyy ");
1888
1889 equiv_alg[M] = new_alg(" yx U xx UUU yxyyy ");
1890 equiv_alg[M2] = new_alg(" yx UU xx UU xxxy ");
1891 equiv_alg[M3] = new_alg(" yx UUU xx U yxxxy ");
1892 equiv_alg[S] = new_alg(" x UUU xx U yyyx ");
1893 equiv_alg[S2] = new_alg(" x UU xx UU yyx ");
1894 equiv_alg[S3] = new_alg(" x U xx UUU yx ");
1895 equiv_alg[E] = new_alg(" U xx UUU xxyyy ");
1896 equiv_alg[E2] = new_alg(" UU xx UU xxyy ");
1897 equiv_alg[E3] = new_alg(" UUU xx U xxy ");
1898
1899 equiv_alg[x] = new_alg(" x ");
1900 equiv_alg[x2] = new_alg(" xx ");
1901 equiv_alg[x3] = new_alg(" xxx ");
1902 equiv_alg[y] = new_alg(" y ");
1903 equiv_alg[y2] = new_alg(" yy ");
1904 equiv_alg[y3] = new_alg(" yyy ");
1905 equiv_alg[z] = new_alg(" yyy x y ");
1906 equiv_alg[z2] = new_alg(" yy xx ");
1907 equiv_alg[z3] = new_alg(" y x yyy ");
1908}
1909
1910static void
1911init_strings()
1912{
1913 strcpy(move_string [NULLMOVE], "-" );
1914 strcpy(move_string [U], "U" );
1915 strcpy(move_string [U2], "U2" );
1916 strcpy(move_string [U3], "U\'" );
1917 strcpy(move_string [D], "D" );
1918 strcpy(move_string [D2], "D2" );
1919 strcpy(move_string [D3], "D\'" );
1920 strcpy(move_string [R], "R" );
1921 strcpy(move_string [R2], "R2" );
1922 strcpy(move_string [R3], "R\'" );
1923 strcpy(move_string [L], "L" );
1924 strcpy(move_string [L2], "L2" );
1925 strcpy(move_string [L3], "L\'" );
1926 strcpy(move_string [F], "F" );
1927 strcpy(move_string [F2], "F2" );
1928 strcpy(move_string [F3], "F\'" );
1929 strcpy(move_string [B], "B" );
1930 strcpy(move_string [B2], "B2" );
1931 strcpy(move_string [B3], "B\'" );
1932 strcpy(move_string [Uw], "Uw" );
1933 strcpy(move_string [Uw2], "Uw2" );
1934 strcpy(move_string [Uw3], "Uw\'" );
1935 strcpy(move_string [Dw], "Dw" );
1936 strcpy(move_string [Dw2], "Dw2" );
1937 strcpy(move_string [Dw3], "Dw\'" );
1938 strcpy(move_string [Rw], "Rw" );
1939 strcpy(move_string [Rw2], "Rw2" );
1940 strcpy(move_string [Rw3], "Rw\'" );
1941 strcpy(move_string [Lw], "Lw" );
1942 strcpy(move_string [Lw2], "Lw2" );
1943 strcpy(move_string [Lw3], "Lw\'" );
1944 strcpy(move_string [Fw], "Fw" );
1945 strcpy(move_string [Fw2], "Fw2" );
1946 strcpy(move_string [Fw3], "Fw\'" );
1947 strcpy(move_string [Bw], "Bw" );
1948 strcpy(move_string [Bw2], "Bw2" );
1949 strcpy(move_string [Bw3], "Bw\'" );
1950 strcpy(move_string [M], "M" );
1951 strcpy(move_string [M2], "M2" );
1952 strcpy(move_string [M3], "M\'" );
1953 strcpy(move_string [S], "S" );
1954 strcpy(move_string [S2], "S2" );
1955 strcpy(move_string [S3], "S\'" );
1956 strcpy(move_string [E], "E" );
1957 strcpy(move_string [E2], "E2" );
1958 strcpy(move_string [E3], "E\'" );
1959 strcpy(move_string [x], "x" );
1960 strcpy(move_string [x2], "x2" );
1961 strcpy(move_string [x3], "x\'" );
1962 strcpy(move_string [y], "y" );
1963 strcpy(move_string [y2], "y2" );
1964 strcpy(move_string [y3], "y\'" );
1965 strcpy(move_string [z], "z" );
1966 strcpy(move_string [z2], "z2" );
1967 strcpy(move_string [z3], "z\'" );
1968
1969 strcpy(edge_string [UF], "UF" );
1970 strcpy(edge_string [UL], "UL" );
1971 strcpy(edge_string [UB], "UB" );
1972 strcpy(edge_string [UR], "UR" );
1973 strcpy(edge_string [DF], "DF" );
1974 strcpy(edge_string [DL], "DL" );
1975 strcpy(edge_string [DB], "DB" );
1976 strcpy(edge_string [DR], "DR" );
1977 strcpy(edge_string [FR], "FR" );
1978 strcpy(edge_string [FL], "FL" );
1979 strcpy(edge_string [BL], "BL" );
1980 strcpy(edge_string [BR], "BR" );
1981
1982 strcpy(corner_string [UFR], "UFR" );
1983 strcpy(corner_string [UFL], "UFL" );
1984 strcpy(corner_string [UBL], "UBL" );
1985 strcpy(corner_string [UBR], "UBR" );
1986 strcpy(corner_string [DFR], "DFR" );
1987 strcpy(corner_string [DFL], "DFL" );
1988 strcpy(corner_string [DBL], "DBL" );
1989 strcpy(corner_string [DBR], "DBR" );
1990
1991 strcpy(center_string [U_center], "U" );
1992 strcpy(center_string [D_center], "D" );
1993 strcpy(center_string [R_center], "R" );
1994 strcpy(center_string [L_center], "L" );
1995 strcpy(center_string [F_center], "F" );
1996 strcpy(center_string [B_center], "B" );
1997}
1998
1999static void
2000init_trans() {
2001 Cube aux, cube, c[3];
2002 CubeArray epcp;
2003 int eparr[12], eoarr[12];
2004 int cparr[8], coarr[8];
2005 int i;
2006 unsigned int ui;
2007 bool b1, b2, b3;
2008 Move mi, move;
2009 Trans m;
2010
2011 /* Compute sources */
2012 for (i = 0; i < NTRANS; i++) {
2013 if (i == mirror)
2014 cube = (Cube){0};
2015 else
2016 cube = apply_alg(trans_algs[i], (Cube){0});
2017
2018 epose_source[i] = edge_slice(what_edge_at(cube, FR));
2019 eposs_source[i] = edge_slice(what_edge_at(cube, UR));
2020 eposm_source[i] = edge_slice(what_edge_at(cube, UF));
2021 eofb_source[i] = what_center_at(cube, F_center)/2;
2022 eorl_source[i] = what_center_at(cube, R_center)/2;
2023 eoud_source[i] = what_center_at(cube, U_center)/2;
2024 coud_source[i] = what_center_at(cube, U_center)/2;
2025 cofb_source[i] = what_center_at(cube, F_center)/2;
2026 corl_source[i] = what_center_at(cube, R_center)/2;
2027 }
2028
2029 if (read_ttables_file())
2030 return;
2031
2032 fprintf(stderr, "Cannot load %s, generating it\n", "ttables");
2033
2034 /* Initialize tables */
2035 for (m = 0; m < NTRANS; m++) {
2036 if (m == mirror) {
2037 memcpy(eparr, ep_mirror, 12 * sizeof(int));
2038 memcpy(cparr, cp_mirror, 8 * sizeof(int));
2039 } else {
2040 epcp = (CubeArray){ .ep = eparr, .cp = cparr };
2041 cube = apply_alg(trans_algs[m], (Cube){0});
2042 cube_to_arrays(cube, &epcp, pf_epcp);
2043 }
2044
2045 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
2046 c[0] = admissible_ep((Cube){ .epose = ui }, pf_e);
2047 c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s);
2048 c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m);
2049
2050 cube = rotate_via_compose(m,c[epose_source[m]],pf_ep);
2051 epose_ttable[m][ui] = cube.epose;
2052
2053 cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep);
2054 eposs_ttable[m][ui] = cube.eposs;
2055
2056 cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep);
2057 eposm_ttable[m][ui] = cube.eposm;
2058 }
2059 for (ui = 0; ui < POW2TO11; ui++ ) {
2060 int_to_sum_zero_array(ui, 2, 12, eoarr);
2061 apply_permutation(eparr, eoarr, 12);
2062 eo_ttable[m][ui] = digit_array_to_int(eoarr, 11, 2);
2063 }
2064 for (ui = 0; ui < POW3TO7; ui++) {
2065 int_to_sum_zero_array(ui, 3, 8, coarr);
2066 apply_permutation(cparr, coarr, 8);
2067 co_ttable[m][ui] = digit_array_to_int(coarr, 7, 3);
2068 if (m == mirror)
2069 co_ttable[m][ui] =
2070 invert_digits(co_ttable[m][ui], 3, 7);
2071 }
2072 for (ui = 0; ui < FACTORIAL8; ui++) {
2073 cube = (Cube){ .cp = ui };
2074 cube = rotate_via_compose(m, cube, pf_cp);
2075 cp_ttable[m][ui] = cube.cp;
2076 }
2077 for (ui = 0; ui < FACTORIAL6; ui++) {
2078 cube = (Cube){ .cpos = ui };
2079 cube = rotate_via_compose(m, cube, pf_cpos);
2080 cpos_ttable[m][ui] = cube.cpos;
2081 }
2082 for (mi = 0; mi < NMOVES; mi++) {
2083 if (m == mirror) {
2084 b1 = (mi >= U && mi <= Bw3);
2085 b2 = (mi >= S && mi <= E3);
2086 b3 = (mi >= x && mi <= z3);
2087 if (b1 || b2 || b3)
2088 moves_ttable[m][mi] =
2089 inverse_move_aux[mi];
2090 else
2091 moves_ttable[m][mi] = mi;
2092
2093 if ((mi-1)/3==(R-1)/3 || (mi-1)/3==(Rw-1)/3)
2094 moves_ttable[m][mi] += 3;
2095 if ((mi-1)/3==(L-1)/3 || (mi-1)/3==(L2-1)/3)
2096 moves_ttable[m][mi] -= 3;
2097 } else {
2098 aux = apply_trans(m, apply_move(mi,(Cube){0}));
2099 for (move = 0; move < NMOVES; move++) {
2100 cube = apply_move(
2101 inverse_move_aux[move], aux);
2102 if (is_solved(cube, false))
2103 moves_ttable[m][mi] = move;
2104 }
2105 }
2106 }
2107 }
2108
2109 if (!write_ttables_file())
2110 fprintf(stderr, "Error writing ttables\n");
2111}
2112
2113static void
2114init_trans_aux()
2115{
2116 ep_mirror[UF] = UF;
2117 ep_mirror[UL] = UR;
2118 ep_mirror[UB] = UB;
2119 ep_mirror[UR] = UL;
2120 ep_mirror[DF] = DF;
2121 ep_mirror[DL] = DR;
2122 ep_mirror[DB] = DB;
2123 ep_mirror[DR] = DL;
2124 ep_mirror[FR] = FL;
2125 ep_mirror[FL] = FR;
2126 ep_mirror[BR] = BL;
2127 ep_mirror[BL] = BR;
2128
2129 cp_mirror[UFR] = UFL;
2130 cp_mirror[UFL] = UFR;
2131 cp_mirror[UBL] = UBR;
2132 cp_mirror[UBR] = UBL;
2133 cp_mirror[DFR] = DFL;
2134 cp_mirror[DFL] = DFR;
2135 cp_mirror[DBL] = DBR;
2136 cp_mirror[DBR] = DBL;
2137
2138 cpos_mirror[U_center] = U_center;
2139 cpos_mirror[D_center] = D_center;
2140 cpos_mirror[R_center] = L_center;
2141 cpos_mirror[L_center] = R_center;
2142 cpos_mirror[F_center] = F_center;
2143 cpos_mirror[B_center] = B_center;
2144
2145 /* Is there a more elegant way? */
2146 trans_algs[uf] = new_alg("");
2147 trans_algs[ur] = new_alg("y");
2148 trans_algs[ub] = new_alg("y2");
2149 trans_algs[ul] = new_alg("y3");
2150
2151 trans_algs[df] = new_alg("z2");
2152 trans_algs[dr] = new_alg("y z2");
2153 trans_algs[db] = new_alg("x2");
2154 trans_algs[dl] = new_alg("y3 z2");
2155
2156 trans_algs[rf] = new_alg("z3");
2157 trans_algs[rd] = new_alg("z3 y");
2158 trans_algs[rb] = new_alg("z3 y2");
2159 trans_algs[ru] = new_alg("z3 y3");
2160
2161 trans_algs[lf] = new_alg("z");
2162 trans_algs[ld] = new_alg("z y3");
2163 trans_algs[lb] = new_alg("z y2");
2164 trans_algs[lu] = new_alg("z y");
2165
2166 trans_algs[fu] = new_alg("x y2");
2167 trans_algs[fr] = new_alg("x y");
2168 trans_algs[fd] = new_alg("x");
2169 trans_algs[fl] = new_alg("x y3");
2170
2171 trans_algs[bu] = new_alg("x3");
2172 trans_algs[br] = new_alg("x3 y");
2173 trans_algs[bd] = new_alg("x3 y2");
2174 trans_algs[bl] = new_alg("x3 y3");
2175}
2176
2177
2178/* Public functions implementation *******************************************/
2179
2180Cube
2181apply_alg(Alg *alg, Cube cube)
2182{
2183 return apply_alg_generic(alg, cube, pf_all, true);
2184}
2185
2186Cube
2187apply_move(Move m, Cube cube)
2188{
2189 return (Cube) {
2190 .epose = epose_mtable[m][cube.epose],
2191 .eposs = eposs_mtable[m][cube.eposs],
2192 .eposm = eposm_mtable[m][cube.eposm],
2193 .eofb = eofb_mtable[m][cube.eofb],
2194 .eorl = eorl_mtable[m][cube.eorl],
2195 .eoud = eoud_mtable[m][cube.eoud],
2196 .coud = coud_mtable[m][cube.coud],
2197 .cofb = cofb_mtable[m][cube.cofb],
2198 .corl = corl_mtable[m][cube.corl],
2199 .cp = cp_mtable[m][cube.cp],
2200 .cpos = cpos_mtable[m][cube.cpos]
2201 };
2202}
2203
2204Cube
2205apply_trans(Trans t, Cube cube)
2206{
2207 int aux_epos[3] = { cube.epose, cube.eposs, cube.eposm };
2208 int aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb };
2209 int aux_co[3] = { cube.coud, cube.corl, cube.cofb };
2210
2211 return (Cube) {
2212 .epose = epose_ttable[t][aux_epos[epose_source[t]]],
2213 .eposs = eposs_ttable[t][aux_epos[eposs_source[t]]],
2214 .eposm = eposm_ttable[t][aux_epos[eposm_source[t]]],
2215 .eofb = eo_ttable[t][aux_eo[eofb_source[t]]],
2216 .eorl = eo_ttable[t][aux_eo[eorl_source[t]]],
2217 .eoud = eo_ttable[t][aux_eo[eoud_source[t]]],
2218 .coud = co_ttable[t][aux_co[coud_source[t]]],
2219 .corl = co_ttable[t][aux_co[corl_source[t]]],
2220 .cofb = co_ttable[t][aux_co[cofb_source[t]]],
2221 .cp = cp_ttable[t][cube.cp],
2222 .cpos = cpos_ttable[t][cube.cpos]
2223 };
2224}
2225
2226Move
2227base_move(Move m)
2228{
2229 if (m == NULLMOVE)
2230 return NULLMOVE;
2231 else
2232 return m - (m-1)%3;
2233}
2234
2235Cube
2236compose(Cube c2, Cube c1)
2237{
2238 return compose_filtered(c2, c1, pf_all);
2239}
2240
2241uint64_t
2242cphtr(Cube cube)
2243{
2244 return cphtr_cosets[cube.cp];
2245}
2246
2247uint64_t
2248epos_dependent(Cube c)
2249{
2250 return epos_dependent_aux[c.eposs/FACTORIAL4][c.epose/FACTORIAL4];
2251}
2252
2253bool
2254equal(Cube c1, Cube c2)
2255{
2256 return c1.eofb == c2.eofb &&
2257 c1.epose == c2.epose &&
2258 c1.eposs == c2.eposs &&
2259 c1.eposm == c2.eposm &&
2260 c1.coud == c2.coud &&
2261 c1.cp == c2.cp &&
2262 c1.cpos == c2.cpos;
2263}
2264
2265void
2266genalgset(AlgSet *as)
2267{
2268 uint64_t i;
2269
2270 if (as->generated)
2271 return;
2272
2273 /* TODO: check if memory is enough, otherwise maybe crash gracefully? */
2274 as->table = malloc(as->size * sizeof(AlgList *));
2275
2276 if (read_algset_file(as)) {
2277 as->generated = true;
2278 return;
2279 }
2280
2281 fprintf(stderr, "Cannot load %s, generating it\n", as->filename);
2282
2283 for (i = 0; i < as->size; i++) {
2284 as->table[i] = solve(as->antindex(i), as->step, &as->opts);
2285 fprintf(stderr, "Generated %lu / %lu cases\n", i, as->size);
2286 }
2287
2288 if (!write_algset_file(as))
2289 fprintf(stderr, "Error writing algset file\n");
2290
2291 as->generated = true;
2292}
2293
2294void
2295genptable(PruneData *pd)
2296{
2297 uint64_t j;
2298 DfsData dd = {
2299 .m = 0,
2300 .last1 = NULLMOVE,
2301 .last2 = NULLMOVE
2302 };
2303
2304 if (pd->generated)
2305 return;
2306
2307 /* TODO: check if memory is enough, otherwise maybe crash gracefully? */
2308 pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
2309
2310 if (read_ptable_file(pd)) {
2311 pd->generated = true;
2312 return;
2313 }
2314
2315 fprintf(stderr, "Cannot load %s, generating it\n", pd->filename);
2316
2317 /* We use 4 bits per value, so any distance >= 15 is set to 15 */
2318 for (j = 0; j < pd->size; j++)
2319 ptable_update(pd, j, 15);
2320
2321 moveset_to_list(pd->moveset, NULL, dd.sorted_moves);
2322 movelist_to_position(dd.sorted_moves, dd.move_position);
2323
2324 pd->reached = malloc(ptablesize(pd) * sizeof(uint8_t));
2325 for (dd.d = 0, pd->n = 0; dd.d < 15 && pd->n < pd->size; dd.d++) {
2326 memset(pd->reached, 0, ptablesize(pd)*sizeof(uint8_t));
2327 genptable_dfs((Cube){0}, pd, &dd);
2328 fprintf(stderr, "Depth %d completed, generated %lu/%lu\n",
2329 dd.d, pd->n, pd->size);
2330 }
2331
2332 if (!write_ptable_file(pd))
2333 fprintf(stderr, "Error writing ptable file\n");
2334
2335 pd->generated = true;
2336 free(pd->reached);
2337}
2338
2339Cube
2340inverse_cube(Cube cube)
2341{
2342 CubeArray *arr = new_cubearray(cube, pf_all);
2343 CubeArray *inv = new_cubearray((Cube){0}, pf_all);
2344 Cube ret;
2345 int i;
2346
2347 for (i = 0; i < 12; i++) {
2348 inv->ep[arr->ep[i]] = i;
2349 inv->eofb[arr->ep[i]] = arr->eofb[i];
2350 inv->eorl[arr->ep[i]] = arr->eorl[i];
2351 inv->eoud[arr->ep[i]] = arr->eoud[i];
2352 }
2353
2354 for (i = 0; i < 8; i++) {
2355 inv->cp[arr->cp[i]] = i;
2356 inv->coud[arr->cp[i]] = (3 - arr->coud[i]) % 3;
2357 inv->corl[arr->cp[i]] = (3 - arr->corl[i]) % 3;
2358 inv->cofb[arr->cp[i]] = (3 - arr->cofb[i]) % 3;
2359 }
2360
2361 for (int i = 0; i < 6; i++)
2362 inv->cpos[arr->cpos[i]] = i;
2363
2364 ret = arrays_to_cube(inv, pf_all);
2365 free_cubearray(arr, pf_all);
2366 free_cubearray(inv, pf_all);
2367
2368 return ret;
2369}
2370
2371Move
2372inverse_move(Move m)
2373{
2374 return inverse_move_aux[m];
2375}
2376
2377Trans
2378inverse_trans(Trans t)
2379{
2380 return inverse_trans_aux[t];
2381}
2382
2383bool
2384is_admissible(Cube cube)
2385{
2386 /* TODO: this should check consistency of different orientations */
2387 /* TODO: check that centers are opposite and admissible */
2388
2389 CubeArray *a = new_cubearray(cube, pf_all);
2390 int parity;
2391 bool perm;
2392
2393 perm = is_perm(a->ep, 12) &&
2394 is_perm(a->cp, 8) &&
2395 is_perm(a->cpos, 6);
2396 parity = perm_sign(a->ep, 12) +
2397 perm_sign(a->cp, 8) +
2398 perm_sign(a->cpos, 6);
2399
2400 return perm && parity % 2 == 0;
2401}
2402
2403bool
2404is_solved(Cube cube, bool reorient)
2405{
2406 Trans i;
2407
2408 if (reorient)
2409 for (i = 0; i < NROTATIONS; i++)
2410 if (is_solved(apply_alg(trans_algs[i],cube), false))
2411 return true;
2412
2413 return equal(cube, (Cube){0});
2414}
2415
2416bool
2417is_solved_block(Cube cube, Block block)
2418{
2419 int i;
2420
2421 for (i = 0; i < 12; i++)
2422 if (block.edge[i] && !is_solved_edge(cube, i))
2423 return false;
2424 for (i = 0; i < 8; i++)
2425 if (block.corner[i] && !is_solved_corner(cube, i))
2426 return false;
2427 for (i = 0; i < 6; i++)
2428 if (block.center[i] && !is_solved_center(cube, i))
2429 return false;
2430
2431 return true;
2432}
2433
2434bool
2435is_solved_center(Cube cube, Center c)
2436{
2437 return what_center_at(cube, c) == c;
2438}
2439
2440bool
2441is_solved_corner(Cube cube, Corner c)
2442{
2443 return what_corner_at(cube, c) == c &&
2444 what_orientation_corner(cube.coud, c);
2445}
2446
2447bool
2448is_solved_edge(Cube cube, Edge e)
2449{
2450 return what_edge_at(cube, e) == e &&
2451 what_orientation_edge(cube.eofb, e);
2452}
2453
2454int
2455piece_orientation(Cube cube, int piece, char *orientation)
2456{
2457 int arr[12], n, b, x;
2458
2459 if (!strcmp(orientation, "eofb")) {
2460 x = cube.eofb;
2461 n = 12;
2462 b = 2;
2463 } else if (!strcmp(orientation, "eorl")) {
2464 x = cube.eorl;
2465 n = 12;
2466 b = 2;
2467 } else if (!strcmp(orientation, "eoud")) {
2468 x = cube.eoud;
2469 n = 12;
2470 b = 2;
2471 } else if (!strcmp(orientation, "coud")) {
2472 x = cube.coud;
2473 n = 8;
2474 b = 3;
2475 } else if (!strcmp(orientation, "corl")) {
2476 x = cube.corl;
2477 n = 8;
2478 b = 3;
2479 } else if (!strcmp(orientation, "cofb")) {
2480 x = cube.cofb;
2481 n = 8;
2482 b = 3;
2483 } else {
2484 return -1;
2485 }
2486
2487 int_to_sum_zero_array(x, b, n, arr);
2488 if (piece < n)
2489 return arr[piece];
2490
2491 return -1;
2492}
2493
2494void
2495print_cube(Cube cube)
2496{
2497/*
2498 CubeArray *arr = new_cubearray(cube, pf_all);
2499
2500 for (int i = 0; i < 12; i++)
2501 printf(" %s ", edge_string[arr->ep[i]]);
2502 printf("\n");
2503
2504 for (int i = 0; i < 12; i++)
2505 printf(" %c ", arr->eofb[i] + '0');
2506 printf("\n");
2507
2508 for (int i = 0; i < 8; i++)
2509 printf("%s ", corner_string[arr->cp[i]]);
2510 printf("\n");
2511
2512 for (int i = 0; i < 8; i++)
2513 printf(" %c ", arr->coud[i] + '0');
2514 printf("\n");
2515
2516 for (int i = 0; i < 6; i++)
2517 printf(" %s ", center_string[arr->cpos[i]]);
2518 printf("\n");
2519
2520 free_cubearray(arr, pf_all);
2521*/
2522
2523 for (int i = 0; i < 12; i++)
2524 printf(" %s ", edge_string[what_edge_at(cube, i)]);
2525 printf("\n");
2526
2527 for (int i = 0; i < 12; i++)
2528 printf(" %d ", what_orientation_edge(cube.eofb, i));
2529 printf("\n");
2530
2531 for (int i = 0; i < 8; i++)
2532 printf("%s ", corner_string[what_corner_at(cube, i)]);
2533 printf("\n");
2534
2535 for (int i = 0; i < 8; i++)
2536 printf(" %d ", what_orientation_corner(cube.coud, i));
2537 printf("\n");
2538
2539 for (int i = 0; i < 6; i++)
2540 printf(" %s ", center_string[what_center_at(cube, i)]);
2541 printf("\n");
2542
2543}
2544
2545Cube
2546random_cube()
2547{
2548 CubeArray *arr = new_cubearray((Cube){0}, pf_4val);
2549 Cube ret;
2550 int ep, cp, eo, co;
2551
2552 ep = rand() % FACTORIAL12;
2553 cp = rand() % FACTORIAL8;
2554 eo = rand() % POW2TO11;
2555 co = rand() % POW3TO7;
2556
2557 index_to_perm(ep, 12, arr->ep);
2558 index_to_perm(cp, 8, arr->cp);
2559 int_to_sum_zero_array(eo, 2, 12, arr->eofb);
2560 int_to_sum_zero_array(co, 3, 8, arr->coud);
2561
2562 if (perm_sign(arr->ep, 12) != perm_sign(arr->cp, 8))
2563 swap(&(arr->ep[0]), &(arr->ep[1]));
2564
2565 ret = arrays_to_cube(arr, pf_4val);
2566 free_cubearray(arr, pf_4val);
2567
2568 return ret;
2569}
2570
2571AlgList *
2572solve(Cube cube, Step step, SolveOptions *opts)
2573{
2574 AlgListNode *node;
2575 AlgList *sols = new_alglist();
2576 Cube c = apply_trans(opts->pre_trans, cube);
2577 DfsData dd = {
2578 .m = 0,
2579 .niss = false,
2580 .lb = -1,
2581 .last1 = NULLMOVE,
2582 .last2 = NULLMOVE,
2583 .sols = sols,
2584 .current_alg = new_alg("")
2585 };
2586
2587 if (step.ready != NULL && step.ready(c, 1) != 0) {
2588 fprintf(stderr, "Cube not ready for solving step\n");
2589 return sols;
2590 }
2591
2592 moveset_to_list(step.moveset, step.check, dd.sorted_moves);
2593 movelist_to_position(dd.sorted_moves, dd.move_position);
2594
2595 for (dd.d = opts->min_moves;
2596 dd.d <= opts->max_moves && !(sols->len && opts->optimal_only);
2597 dd.d++) {
2598 if (opts->feedback)
2599 fprintf(stderr,
2600 "Found %d solutions, searching depth %d...\n",
2601 sols->len, dd.d);
2602 dfs(c, step, opts, &dd);
2603 }
2604
2605 for (node = sols->first; node != NULL; node = node->next)
2606 transform_alg(inverse_trans_aux[opts->pre_trans], node->alg);
2607
2608 free_alg(dd.current_alg);
2609 return sols;
2610}
2611
2612Alg *
2613inverse_alg(Alg *alg)
2614{
2615 Alg *ret = new_alg("");
2616 int i;
2617
2618 for (i = alg->len-1; i >= 0; i--)
2619 append_move(ret, alg->move[i], alg->inv[i]);
2620
2621 return ret;
2622}
2623
2624Alg *
2625new_alg(char *str)
2626{
2627 Alg *alg = malloc(sizeof(Alg));
2628 int i;
2629 bool niss = false;
2630 Move j, m;
2631
2632 alg->move = malloc(30 * sizeof(Move));
2633 alg->inv = malloc(30 * sizeof(bool));
2634 alg->allocated = 30;
2635 alg->len = 0;
2636
2637 for (i = 0; str[i]; i++) {
2638 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
2639 continue;
2640
2641 if (str[i] == '(' && niss) {
2642 fprintf(stderr, "Error reading moves: nested ( )\n");
2643 return alg;
2644 }
2645
2646 if (str[i] == ')' && !niss) {
2647 fprintf(stderr, "Error reading moves: unmatched )\n");
2648 return alg;
2649 }
2650
2651 if (str[i] == '(' || str[i] == ')') {
2652 niss = !niss;
2653 continue;
2654 }
2655
2656 for (j = 0; j < NMOVES; j++) {
2657 if (str[i] == move_string[j][0]) {
2658 m = j;
2659 if (m <= B && str[i+1]=='w') {
2660 m += Uw - U;
2661 i++;
2662 }
2663 if (str[i+1]=='2') {
2664 m += 1;
2665 i++;
2666 } else if (str[i+1]=='\'' || str[i+1]=='3') {
2667 m += 2;
2668 i++;
2669 }
2670 append_move(alg, m, niss);
2671 break;
2672 }
2673 }
2674 }
2675
2676 return alg;
2677}
2678
2679Alg *
2680on_inverse(Alg *alg)
2681{
2682 Alg *ret = new_alg("");
2683 int i;
2684
2685 for (i = 0; i < alg->len; i++)
2686 append_move(ret, alg->move[i], !alg->inv[i]);
2687
2688 return ret;
2689}
2690
2691void
2692print_alg(Alg *alg, bool l)
2693{
2694 /* TODO: make it possible to print to stdout or to string */
2695 /* Maybe just return a string */
2696 char fill[4];
2697 int i;
2698 bool niss = false;
2699
2700 for (i = 0; i < alg->len; i++) {
2701 if (!niss && alg->inv[i])
2702 strcpy(fill, i == 0 ? "(" : " (");
2703 if (niss && !alg->inv[i])
2704 strcpy(fill, ") ");
2705 if (niss == alg->inv[i])
2706 strcpy(fill, i == 0 ? "" : " ");
2707
2708 printf("%s%s", fill, move_string[alg->move[i]]);
2709 niss = alg->inv[i];
2710 }
2711
2712 if (niss)
2713 printf(")");
2714 if (l)
2715 printf(" (%d)", alg->len);
2716
2717 printf("\n");
2718}
2719
2720void
2721print_alglist(AlgList *al, bool l)
2722{
2723 AlgListNode *i;
2724
2725 for (i = al->first; i != NULL; i = i->next)
2726 print_alg(i->alg, l);
2727}
2728
2729void
2730print_ptable(PruneData *pd)
2731{
2732 uint64_t i, a[16];
2733
2734 for (i = 0; i < 16; i++)
2735 a[i] = 0;
2736
2737 if (!pd->generated)
2738 genptable(pd);
2739
2740 for (i = 0; i < pd->size; i++)
2741 a[ptableval(pd, i)]++;
2742
2743 fprintf(stderr, "Values for table %s\n", pd->filename);
2744 for (i = 0; i < 16; i++)
2745 printf("%2lu\t%10lu\n", i, a[i]);
2746}
2747
2748uint64_t
2749ptablesize(PruneData *pd)
2750{
2751 return (pd->size + 1) / 2;
2752}
2753
2754int
2755ptableval(PruneData *pd, uint64_t ind)
2756{
2757 return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16;
2758}
2759
2760
2761Alg *
2762trans_alg(Trans i)
2763{
2764 return trans_algs[i];
2765}
2766
2767void
2768transform_alg(Trans t, Alg *alg)
2769{
2770 int i;
2771
2772 for (i = 0; i < alg->len; i++)
2773 alg->move[i] = moves_ttable[t][alg->move[i]];
2774}
2775
2776Center
2777what_center_at(Cube cube, Center c)
2778{
2779 return what_center_at_aux[cube.cpos][c];
2780}
2781
2782Corner
2783what_corner_at(Cube cube, Corner c)
2784{
2785 return what_corner_at_aux[cube.cp][c];
2786}
2787
2788Edge
2789what_edge_at(Cube cube, Edge e)
2790{
2791 Edge ret;
2792 CubeArray *arr = new_cubearray(cube, pf_ep);
2793
2794 ret = arr->ep[e];
2795
2796 free_cubearray(arr, pf_ep);
2797 return ret;
2798}
2799
2800int
2801what_orientation_corner(int co, Corner c)
2802{
2803 if (c < 7)
2804 return (co / powint(3, c)) % 3;
2805 else
2806 return what_orientation_last_corner_aux[co];
2807}
2808
2809int
2810what_orientation_edge(int eo, Edge e)
2811{
2812 if (e < 11)
2813 return (eo & (1 << e)) ? 1 : 0;
2814 else
2815 return what_orientation_last_edge_aux[eo];
2816}
2817
2818Center
2819where_is_center(Cube cube, Center c)
2820{
2821 return where_is_center_aux[cube.cpos][c];
2822}
2823
2824Corner
2825where_is_corner(Cube cube, Corner c)
2826{
2827 return where_is_corner_aux[cube.cp][c];
2828}
2829
2830
2831void
2832init()
2833{
2834 /* Order is important! */
2835 init_environment();
2836 init_strings();
2837 init_moves_aux();
2838 init_moves();
2839 init_auxtables();
2840 init_cphtr_cosets();
2841 init_trans_aux();
2842 init_trans();
2843}
2844
diff --git a/old/2021-06-23-realizing-bad-tables/cube.h b/old/2021-06-23-realizing-bad-tables/cube.h
new file mode 100644
index 0000000..dcad047
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/cube.h
@@ -0,0 +1,88 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include <stdlib.h>
8#include <string.h>
9#include <time.h>
10#include <unistd.h>
11#include <sys/stat.h>
12
13/* Constants and macros *****************************************************/
14
15#define POW2TO6 64ULL
16#define POW2TO11 2048ULL
17#define POW2TO12 4096ULL
18#define POW3TO7 2187ULL
19#define POW3TO8 6561ULL
20#define FACTORIAL4 24ULL
21#define FACTORIAL6 720ULL
22#define FACTORIAL7 5040ULL
23#define FACTORIAL8 40320ULL
24#define FACTORIAL12 479001600ULL
25#define BINOM12ON4 495ULL
26#define BINOM8ON4 70ULL
27#define MIN(a,b) (((a) < (b)) ? (a) : (b))
28#define MAX(a,b) (((a) > (b)) ? (a) : (b))
29
30#define NMOVES (z3+1)
31#define NTRANS (mirror+1)
32#define NROTATIONS (NTRANS-1)
33
34/* Type definitions **********************************************************/
35
36#include "cubetypes.h"
37
38/* Public functions **********************************************************/
39
40Cube apply_alg(Alg *alg, Cube cube);
41Cube apply_move(Move m, Cube cube);
42Cube apply_trans(Trans t, Cube cube);
43bool block_solved(Cube cube, Block);
44Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */
45uint64_t cphtr(Cube cube);
46uint64_t epos_dependent(Cube cube);
47bool equal(Cube c1, Cube c2);
48Cube inverse_cube(Cube cube);
49Move inverse_move(Move m);
50Trans inverse_trans(Trans t);
51bool is_admissible(Cube cube);
52bool is_solved(Cube cube, bool reorient);
53bool is_solved_center(Cube cube, Center c);
54bool is_solved_corner(Cube cube, Corner c);
55bool is_solved_edge(Cube cube, Edge e);
56void print_cube(Cube cube);
57Cube random_cube();
58AlgList * solve(Cube cube, Step step, SolveOptions *opts);
59Center what_center_at(Cube cube, Center c);
60Corner what_corner_at(Cube cube, Corner c);
61Edge what_edge_at(Cube cube, Edge e);
62int what_orientation_corner(int co, Corner c);
63int what_orientation_edge(int eo, Edge e);
64Center where_is_center(Cube cube, Center c);
65Corner where_is_corner(Cube cube, Corner c);
66Edge where_is_edge(Cube cube, Edge e);
67
68Move base_move(Move m);
69void free_alg(Alg *alg);
70void free_alglist(AlgList *l);
71Alg * inverse_alg(Alg *alg);
72Alg * new_alg(char *str);
73Alg * on_inverse(Alg *alg);
74void print_alg(Alg *alg, bool l);
75void print_alglist(AlgList *al, bool l);
76Alg * trans_alg(Trans i);
77void transform_alg(Trans t, Alg *alg);
78
79void genalgset(AlgSet *as);
80void genptable(PruneData *pd);
81void print_ptable(PruneData *pd);
82uint64_t ptablesize(PruneData *pd);
83int ptableval(PruneData *pd, uint64_t ind);
84
85void init();
86
87#endif
88
diff --git a/old/2021-06-23-realizing-bad-tables/cubetypes.h b/old/2021-06-23-realizing-bad-tables/cubetypes.h
new file mode 100644
index 0000000..886295c
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/cubetypes.h
@@ -0,0 +1,224 @@
1/* Typedefs ******************************************************************/
2
3typedef enum center Center;
4typedef enum corner Corner;
5typedef enum edge Edge;
6typedef enum move Move;
7typedef enum trans Trans;
8
9typedef struct alg Alg;
10typedef struct alglist AlgList;
11typedef struct alglistnode AlgListNode;
12typedef struct algset AlgSet;
13typedef struct block Block;
14typedef struct cube Cube;
15typedef struct cubearray CubeArray;
16typedef struct dfsdata DfsData;
17typedef struct piecefilter PieceFilter;
18typedef struct prunedata PruneData;
19typedef struct solveoptions SolveOptions;
20typedef struct step Step;
21
22typedef Cube (*AntiIndexer) (uint64_t);
23typedef int (*Checker) (Cube, int);
24typedef uint64_t (*Indexer) (Cube);
25typedef bool (*Moveset) (Move);
26
27
28/* Enums *********************************************************************/
29
30enum
31center
32{
33 U_center, D_center,
34 R_center, L_center,
35 F_center, B_center
36};
37
38enum
39corner
40{
41 UFR, UFL, UBL, UBR,
42 DFR, DFL, DBL, DBR
43};
44
45enum
46edge
47{
48 UF, UL, UB, UR,
49 DF, DL, DB, DR,
50 FR, FL, BL, BR
51};
52
53enum
54move
55{
56 NULLMOVE,
57 U, U2, U3, D, D2, D3,
58 R, R2, R3, L, L2, L3,
59 F, F2, F3, B, B2, B3,
60 Uw, Uw2, Uw3, Dw, Dw2, Dw3,
61 Rw, Rw2, Rw3, Lw, Lw2, Lw3,
62 Fw, Fw2, Fw3, Bw, Bw2, Bw3,
63 M, M2, M3,
64 S, S2, S3,
65 E, E2, E3,
66 x, x2, x3,
67 y, y2, y3,
68 z, z2, z3,
69};
70
71enum
72trans
73{
74 uf, ur, ub, ul,
75 df, dr, db, dl,
76 rf, rd, rb, ru,
77 lf, ld, lb, lu,
78 fu, fr, fd, fl,
79 bu, br, bd, bl,
80 mirror, /* R|L */
81};
82
83
84/* Structs *******************************************************************/
85
86struct
87alg
88{
89 Move * move;
90 bool * inv;
91 int len;
92 int allocated;
93};
94
95struct
96alglist
97{
98 AlgListNode * first;
99 AlgListNode * last;
100 int len;
101};
102
103struct
104alglistnode
105{
106 Alg * alg;
107 AlgListNode * next;
108};
109
110struct
111block
112{
113 bool edge[12];
114 bool corner[8];
115 bool center[6];
116};
117
118struct
119cube
120{
121 int epose;
122 int eposs;
123 int eposm;
124 int eofb;
125 int eorl;
126 int eoud;
127 int cp;
128 int coud;
129 int cofb;
130 int corl;
131 int cpos;
132};
133
134struct
135cubearray
136{
137 int * ep;
138 int * eofb;
139 int * eorl;
140 int * eoud;
141 int * cp;
142 int * coud;
143 int * corl;
144 int * cofb;
145 int * cpos;
146};
147
148struct
149dfsdata
150{
151 int d;
152 int m;
153 int lb;
154 bool niss;
155 Move last1;
156 Move last2;
157 AlgList * sols;
158 Alg * current_alg;
159 Move sorted_moves[NMOVES];
160 int move_position[NMOVES];
161};
162
163struct
164piecefilter
165{
166 bool epose;
167 bool eposs;
168 bool eposm;
169 bool eofb;
170 bool eorl;
171 bool eoud;
172 bool cp;
173 bool coud;
174 bool cofb;
175 bool corl;
176 bool cpos;
177};
178
179struct
180prunedata
181{
182 char * filename;
183 uint8_t * ptable;
184 uint8_t * reached;
185 bool generated;
186 uint64_t n;
187 uint64_t size;
188 Indexer index;
189 Moveset moveset;
190};
191
192struct
193solveoptions
194{
195 int min_moves;
196 int max_moves;
197 int max_solutions;
198 bool optimal_only;
199 bool can_niss;
200 bool feedback;
201 Trans pre_trans;
202};
203
204struct
205step
206{
207 Checker check;
208 Checker ready;
209 Moveset moveset;
210};
211
212/* TODO: I put it here because it needs the definition of Step, sort it out */
213struct
214algset
215{
216 char * filename;
217 AlgList ** table;
218 bool generated;
219 uint64_t size;
220 Indexer index;
221 AntiIndexer antindex;
222 Step step;
223 SolveOptions opts;
224};
diff --git a/old/2021-06-23-realizing-bad-tables/main.c b/old/2021-06-23-realizing-bad-tables/main.c
new file mode 100644
index 0000000..e0e049a
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/main.c
@@ -0,0 +1,70 @@
1#include <stdio.h>
2#include "cube.h"
3#include "steps.h"
4
5int main() {
6 Alg *algo;
7 AlgList *sols;
8 Cube cube;
9 SolveOptions opts;
10 char line[1000];
11 int i, ns = 3;
12/* int nrand = 10000, sum1, sum2, sum3;*/
13
14 Step *stps[20] = {&corners_HTM, &eofb_HTM, &optimal_HTM};
15 char sss[30][30] = {"Corners", "EO on F/B", "Optimal solution"};
16
17 opts = (SolveOptions) {
18 .min_moves = 0,
19 .max_moves = 20,
20 .optimal_only = true,
21 .max_solutions = 1,
22 .can_niss = false,
23 .feedback = true,
24 .pre_trans = uf
25 };
26
27 init();
28
29 print_ptable(&pd_corners_HTM);
30
31/*
32 srand(time(NULL));
33 sum1 = 0;
34 sum2 = 0;
35 sum3 = 0;
36 for (i = 0; i < nrand; i++) {
37 cube = random_cube();
38 sum1 += corners_HTM.check(cube, 20);
39 sum2 += cornershtr_HTM.check(cube, 20);
40 sum3 += optimal_HTM.check(cube, 20);
41 }
42 printf("Average corners pruning: %lf\n", ((double)sum1) / ((double) nrand));
43 printf("Average corners htr pruning: %lf\n", ((double)sum2) / ((double) nrand));
44 printf("Average optimal pruning: %lf\n", ((double)sum3) / ((double) nrand));
45*/
46
47 printf("Welcome to nissy 2.0! Insert a scramble:\n");
48
49 if (fgets(line, 1000, stdin) != NULL) {
50 algo = new_alg(line);
51 cube = apply_alg(algo, (Cube){0});
52
53 print_cube(cube);
54 printf("Index: %lu\n", pd_cornershtr_HTM.index(cube));
55
56 for (i = 0; i < ns; i++) {
57 if (stps[i]->check == NULL)
58 fprintf(stderr, "Check function for step %d is null\n", i);
59 printf("Check: %d\n", stps[i]->check(cube, 20));
60 sols = solve(cube, *stps[i], &opts);
61 printf("%s: %d solutions found:\n", sss[i], sols->len);
62 print_alglist(sols, true);
63 free_alglist(sols);
64 }
65 free_alg(algo);
66 }
67
68 return 0;
69}
70
diff --git a/old/2021-06-23-realizing-bad-tables/steps.c b/old/2021-06-23-realizing-bad-tables/steps.c
new file mode 100644
index 0000000..2b029b8
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/steps.c
@@ -0,0 +1,486 @@
1#include "steps.h"
2
3/* Check functions ***********************************************************/
4
5static int check_nothing(Cube cube, int target);
6static int check_centers(Cube cube, int target);
7static int check_eofb_HTM(Cube cube, int target);
8static int check_coud_HTM(Cube cube, int target);
9static int check_coud_URF(Cube cube, int target);
10static int check_corners_HTM(Cube cube, int target);
11static int check_cornershtr_HTM(Cube cube, int target);
12static int check_corners_URF(Cube cube, int target);
13static int check_cornershtr_URF(Cube cube, int target);
14static int check_ep_HTM(Cube cube, int target);
15static int check_edges_HTM(Cube cube, int target);
16static int check_drud_HTM(Cube cube, int target);
17static int check_optimal_HTM(Cube cube, int target);
18static int check_corners6eo_HTM(Cube cube, int target);
19static int check_tripleeo_HTM(Cube cube, int target);
20
21
22/* Index functions ***********************************************************/
23
24static uint64_t index_eofb(Cube cube);
25static uint64_t index_coud(Cube cube);
26static uint64_t index_corners(Cube cube);
27static uint64_t index_cornershtr(Cube cube);
28static uint64_t index_ep(Cube cube);
29static uint64_t index_drud(Cube cube);
30static uint64_t index_corners6eo(Cube cube);
31static uint64_t index_tripleeo(Cube cube);
32
33
34/* Steps *********************************************************************/
35
36Step
37eofb_HTM = {
38 .check = check_eofb_HTM,
39 .ready = check_centers,
40 .moveset = moveset_HTM
41};
42
43Step
44coud_HTM = {
45 .check = check_coud_HTM,
46 .ready = check_centers,
47 .moveset = moveset_HTM
48};
49
50Step
51coud_URF = {
52 .check = check_coud_URF,
53 .ready = check_nothing,
54 .moveset = moveset_URF
55};
56
57Step
58corners_HTM = {
59 .check = check_corners_HTM,
60 .ready = check_centers,
61 .moveset = moveset_HTM
62};
63
64Step
65cornershtr_HTM = {
66 .check = check_cornershtr_HTM,
67 .ready = check_centers,
68 .moveset = moveset_HTM
69};
70
71Step
72cornershtr_URF = {
73 .check = check_cornershtr_URF,
74 .ready = check_nothing,
75 .moveset = moveset_URF
76};
77
78Step
79corners_URF = {
80 .check = check_corners_URF,
81 .ready = check_nothing,
82 .moveset = moveset_URF
83};
84
85Step
86edges_HTM = {
87 .check = check_edges_HTM,
88 .ready = check_centers,
89 .moveset = moveset_HTM
90};
91
92Step
93drud_HTM = {
94 .check = check_drud_HTM,
95 .ready = check_centers,
96 .moveset = moveset_HTM
97};
98
99Step
100optimal_HTM = {
101 .check = check_optimal_HTM,
102 .ready = check_centers,
103 .moveset = moveset_HTM
104};
105
106Step
107tripleeo_HTM = {
108 .check = check_tripleeo_HTM,
109 .ready = check_centers,
110 .moveset = moveset_HTM
111};
112
113
114/* Blocks ********************************************************************/
115
116Block
117block_223dl = {
118 .edge = { [DF] = 1, [DL] = 1, [DB] = 1, [FL] = 1, [BL] = 1 },
119 .corner = { [DFL] = 1, [DBL] = 1 },
120 .center = { [D_center] = 1, [L_center] = 1 }
121};
122
123
124/* Pruning tables ************************************************************/
125
126PruneData
127pd_eofb_HTM = {
128 .filename = "ptable_eofb_HTM",
129 .size = POW2TO11,
130 .index = index_eofb,
131 .moveset = moveset_HTM
132};
133
134PruneData
135pd_coud_HTM = {
136 .filename = "ptable_coud_HTM",
137 .size = POW3TO7,
138 .index = index_coud,
139 .moveset = moveset_HTM
140};
141
142PruneData
143pd_cornershtr_HTM = {
144 .filename = "ptable_cornershtr_HTM",
145 .size = POW3TO7 * BINOM8ON4 * 6, /*TODO: check */
146 .index = index_cornershtr,
147 .moveset = moveset_HTM
148};
149
150PruneData
151pd_corners_HTM = {
152 .filename = "ptable_corners_HTM",
153 .size = POW3TO7 * FACTORIAL8,
154 .index = index_corners,
155 .moveset = moveset_HTM
156};
157
158PruneData
159pd_ep_HTM = {
160 .filename = "ptable_ep_HTM",
161 .size = FACTORIAL12,
162 .index = index_ep,
163 .moveset = moveset_HTM
164};
165
166PruneData
167pd_drud_HTM = {
168 .filename = "ptable_drud_HTM",
169 .size = POW2TO11 * POW3TO7 * BINOM12ON4,
170 .index = index_drud,
171 .moveset = moveset_HTM
172};
173
174PruneData
175pd_corners6eo_HTM = {
176 .filename = "ptable_corners6eo_HTM",
177 .size = POW2TO6 * POW3TO7 * FACTORIAL8,
178 .index = index_corners6eo,
179 .moveset = moveset_HTM
180};
181
182PruneData
183pd_tripleeo_HTM = {
184 .filename = "ptable_tripleeo_HTM",
185 .size = BINOM12ON4 * BINOM8ON4 * POW2TO11,
186 .index = index_tripleeo,
187 .moveset = moveset_HTM
188};
189
190
191/* Alg sets ******************************************************************/
192
193/* TODO: remove this (I am only keeping it as an example for future algesets)
194AlgSet
195as_ephtr_HTM = {
196 .filename = "algset_ephtr_HTM",
197 .size = FACTORIAL4 * FACTORIAL4 * FACTORIAL4,
198 .index = index_ephtr,
199 .antindex = index_to_cube_ephtr,
200 .step = (Step) {
201 .check = check_optimal_HTM,
202 .ready = check_htr_solved_corners_HTM,
203 .moveset = moveset_HTM
204 },
205 .opts = (SolveOptions) {
206 .min_moves = 0,
207 .max_moves = 20,
208 .max_solutions = 1,
209 .optimal_only = true,
210 .can_niss = false,
211 .feedback = true,
212 .pre_trans = uf
213 }
214};
215*/
216
217
218/* Check functions implementation ********************************************/
219
220static int
221check_nothing(Cube cube, int target)
222{
223 return 0;
224}
225
226static int
227check_centers(Cube cube, int target)
228{
229 return (cube.cpos == 0) ? 0 : 1;
230}
231
232static int
233check_eofb_HTM(Cube cube, int target)
234{
235 if (!pd_eofb_HTM.generated)
236 genptable(&pd_eofb_HTM);
237
238 return ptableval(&pd_eofb_HTM, cube.eofb);
239}
240
241static int
242check_coud_HTM(Cube cube, int target)
243{
244 if (!pd_coud_HTM.generated)
245 genptable(&pd_coud_HTM);
246
247 return ptableval(&pd_coud_HTM, cube.coud);
248}
249
250static int
251check_coud_URF(Cube cube, int target)
252{
253 /* TODO: I can improve this by checking first the orientation of
254 * the corner in DBL and use that as a reference */
255
256 int ud = check_coud_HTM(cube, target);
257 int rl = check_coud_HTM(apply_move(z, cube), target);
258 int fb = check_coud_HTM(apply_move(x, cube), target);
259
260 return MIN(ud, MIN(rl, fb));
261}
262
263static int
264check_corners_HTM(Cube cube, int target)
265{
266 if (!pd_corners_HTM.generated)
267 genptable(&pd_corners_HTM);
268
269 return ptableval(&pd_corners_HTM, index_corners(cube));
270}
271
272static int
273check_cornershtr_HTM(Cube cube, int target)
274{
275 if (!pd_cornershtr_HTM.generated)
276 genptable(&pd_cornershtr_HTM);
277
278 return ptableval(&pd_cornershtr_HTM, index_cornershtr(cube));
279}
280
281static int
282check_cornershtr_URF(Cube cube, int target)
283{
284 /* TODO: I can improve this by checking first the corner in DBL
285 * and use that as a reference */
286
287 int c, ret = 15;
288 Trans i;
289
290 for (i = 0; i < NROTATIONS; i++) {
291 c = check_cornershtr_HTM(apply_alg(trans_alg(i),cube), target);
292 ret = MIN(ret, c);
293 }
294
295 return ret;
296}
297
298static int
299check_corners_URF(Cube cube, int target)
300{
301 /* TODO: I can improve this by checking first the corner in DBL
302 * and use that as a reference */
303
304 int ret = 15;
305 Trans i;
306
307 for (i = 0; i < NROTATIONS; i++)
308 ret = MIN(ret, check_corners_HTM(
309 apply_alg(trans_alg(i), cube), target));
310
311 return ret;
312}
313
314static int
315check_ep_HTM(Cube cube, int target)
316{
317 if (!pd_ep_HTM.generated)
318 genptable(&pd_ep_HTM);
319
320 return ptableval(&pd_ep_HTM, index_ep(cube));
321}
322
323static int
324check_edges_HTM(Cube cube, int target)
325{
326 return MAX(check_ep_HTM(cube, target),
327 check_tripleeo_HTM(cube, target));
328}
329
330static int
331check_drud_HTM(Cube cube, int target)
332{
333 if (!pd_drud_HTM.generated)
334 genptable(&pd_drud_HTM);
335
336 return ptableval(&pd_drud_HTM, index_drud(cube));
337}
338
339static int
340check_optimal_HTM(Cube cube, int target)
341{
342 int dr1, dr2, dr3, cor, ret;
343 Cube cube2, cube3;
344
345 dr1 = check_drud_HTM(cube, target);
346 /*cor = check_corners6eo_HTM(cube, target);*/
347 cor = check_corners_HTM(cube, target);
348 ret = MAX(dr1, cor);
349
350 if (ret > target)
351 return ret;
352
353 cube2 = apply_trans(rf, cube);
354 dr2 = check_drud_HTM(cube2, target);
355 /*cor = check_corners6eo_HTM(cube2, target);
356 ret = MAX(ret, MAX(dr2, cor));*/
357 ret = MAX(ret, dr2);
358
359 if (ret > target)
360 return ret;
361
362 cube3 = apply_trans(bd, cube);
363 dr3 = check_drud_HTM(cube3, target);
364 /*cor = check_corners6eo_HTM(cube3, target);*/
365
366 if (dr1 == dr2 && dr2 == dr3 && dr1 != 0)
367 dr3++;
368
369 /*ret = MAX(ret, MAX(dr3, cor));*/
370 ret = MAX(ret, dr3);
371
372 if (ret == 0)
373 return (!cube.epose && !cube.eposs && !cube.eposm) ? 0 : 6;
374
375 return ret;
376}
377
378static int
379check_corners6eo_HTM(Cube cube, int target)
380{
381 if (!pd_corners6eo_HTM.generated)
382 genptable(&pd_corners6eo_HTM);
383
384 return ptableval(&pd_corners6eo_HTM, index_corners6eo(cube));
385}
386
387static int
388check_tripleeo_HTM(Cube cube, int target)
389{
390 if (!pd_tripleeo_HTM.generated)
391 genptable(&pd_tripleeo_HTM);
392
393 return ptableval(&pd_tripleeo_HTM, index_tripleeo(cube));
394}
395
396
397/* Index functions implementation ********************************************/
398
399static uint64_t
400index_eofb(Cube cube)
401{
402 return cube.eofb;
403}
404
405static uint64_t
406index_coud(Cube cube)
407{
408 return cube.coud;
409}
410
411static uint64_t
412index_cornershtr(Cube cube)
413{
414 return cube.coud * BINOM8ON4 * 6 + cphtr(cube);
415}
416
417static uint64_t
418index_corners(Cube cube)
419{
420 return cube.coud * FACTORIAL8 + cube.cp;
421}
422
423static uint64_t
424index_ep(Cube cube)
425{
426 uint64_t a, b, c;
427
428 a = cube.epose;
429 b = (cube.eposs % FACTORIAL4) + epos_dependent(cube)*FACTORIAL4;
430 c = cube.eposm % FACTORIAL4;
431
432 b *= FACTORIAL4 * BINOM12ON4;
433 c *= FACTORIAL4 * BINOM12ON4 * FACTORIAL4 * BINOM8ON4;
434
435 return a + b + c;
436}
437
438static uint64_t
439index_drud(Cube cube)
440{
441 uint64_t a, b, c;
442
443 a = cube.eofb;
444 b = cube.coud;
445 c = cube.epose / FACTORIAL4;
446
447 b *= POW2TO11;
448 c *= POW2TO11 * POW3TO7;
449
450 return a + b + c;
451}
452
453static uint64_t
454index_corners6eo(Cube cube)
455{
456 return (cube.coud*FACTORIAL8 + cube.cp)*POW2TO6 + (cube.eofb%POW2TO6);
457}
458
459static uint64_t
460index_tripleeo(Cube cube)
461{
462 uint64_t ee, es;
463
464 ee = cube.epose / FACTORIAL4;
465 es = epos_dependent(cube);
466
467 return (ee * BINOM8ON4 + es) * POW2TO11 + cube.eofb;
468}
469
470
471/* Movesets ******************************************************************/
472
473bool
474moveset_HTM(Move m)
475{
476 return m >= U && m <= B3;
477}
478
479bool
480moveset_URF(Move m)
481{
482 Move b = base_move(m);
483
484 return b == U || b == R || b == F;
485}
486
diff --git a/old/2021-06-23-realizing-bad-tables/steps.h b/old/2021-06-23-realizing-bad-tables/steps.h
new file mode 100644
index 0000000..9d8bf6a
--- /dev/null
+++ b/old/2021-06-23-realizing-bad-tables/steps.h
@@ -0,0 +1,42 @@
1#ifndef STEPS_H
2#define STEPS_H
3
4#include "cube.h"
5
6/* Steps *********************************************************************/
7
8extern Step eofb_HTM;
9extern Step coud_HTM;
10extern Step coud_URF;
11extern Step corners_HTM;
12extern Step cornershtr_HTM;
13extern Step corners_URF;
14extern Step cornershtr_URF;
15extern Step edges_HTM;
16extern Step drud_HTM;
17extern Step optimal_HTM;
18extern Step tripleeo_HTM;
19
20/* Blocks ********************************************************************/
21
22extern Block block_223dl;
23
24/* Pruning tables ************************************************************/
25
26extern PruneData pd_eofb_HTM;
27extern PruneData pd_coud_HTM;
28extern PruneData pd_corners_HTM;
29extern PruneData pd_cornershtr_HTM;
30extern PruneData pd_ep_HTM;
31extern PruneData pd_drud_HTM;
32extern PruneData pd_tripleeo_HTM;
33
34/* Alg sets ******************************************************************/
35
36
37/* Movesets ******************************************************************/
38
39bool moveset_HTM(Move m);
40bool moveset_URF(Move m);
41
42#endif

Generated with cgit - Back to sebastiano.tronto.net