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