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

Generated with cgit - Back to sebastiano.tronto.net