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

Generated with cgit - Back to sebastiano.tronto.net