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

Generated with cgit - Back to sebastiano.tronto.net