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

Generated with cgit - Back to sebastiano.tronto.net