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

Generated with cgit - Back to sebastiano.tronto.net