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

Generated with cgit - Back to sebastiano.tronto.net