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

Generated with cgit - Back to sebastiano.tronto.net