aboutsummaryrefslogtreecommitdiff
path: root/old/2021-02-18-piecefilter/src
diff options
context:
space:
mode:
Diffstat (limited to 'old/2021-02-18-piecefilter/src')
-rw-r--r--old/2021-02-18-piecefilter/src/cube.c198
-rw-r--r--old/2021-02-18-piecefilter/src/cube.h45
-rw-r--r--old/2021-02-18-piecefilter/src/main.c47
-rw-r--r--old/2021-02-18-piecefilter/src/moves.c482
-rw-r--r--old/2021-02-18-piecefilter/src/moves.h46
-rw-r--r--old/2021-02-18-piecefilter/src/solve.c179
-rw-r--r--old/2021-02-18-piecefilter/src/solve.h56
-rw-r--r--old/2021-02-18-piecefilter/src/transformations.c103
-rw-r--r--old/2021-02-18-piecefilter/src/transformations.h37
-rw-r--r--old/2021-02-18-piecefilter/src/utils.c197
-rw-r--r--old/2021-02-18-piecefilter/src/utils.h70
11 files changed, 1460 insertions, 0 deletions
diff --git a/old/2021-02-18-piecefilter/src/cube.c b/old/2021-02-18-piecefilter/src/cube.c
new file mode 100644
index 0000000..9235c03
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/cube.c
@@ -0,0 +1,198 @@
1#include "cube.h"
2
3char edge_string[12][5] =
4 { "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR" };
5char corner_string[8][5] = { "UFR","UFL","UBL","UBR","DFR","DFL","DBL","DBR" };
6char center_string[6][5] = { "U", "D", "R", "L", "F", "B" };
7
8int epe_solved[] = {FR, FL, BL, BR};
9int eps_solved[] = {UL, UR, DL, DR};
10int epm_solved[] = {UF, UB, DF, DB};
11
12PieceFilter fAll = {true,true,true,true,true,true,true,true,true,true,true};
13
14Cube blank_cube() {
15 Cube c = {0};
16 return c;
17}
18
19/* Return axis (ud=0, rl=1, fb=0) of center c */
20int center_axis(int c) {
21 if (c == U_center || c == D_center)
22 return 0;
23 if (c == R_center || c == L_center)
24 return 1;
25 return 2;
26}
27
28/* Return slice (e=0, s=1, m=2) to which e belongs */
29int edge_slice(int e) {
30 if (e == FR || e == FL || e == BL || e == BR)
31 return 0;
32 if (e == UR || e == UL || e == DR || e == DL)
33 return 1;
34 return 2;
35}
36
37void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) {
38 /* ep is the hardest */
39 if (f.epose || f.eposs || f.eposm)
40 for (int i = 0; i < 12; i++) arr->ep[i] = -1;
41 if (f.epose) {
42 int epe[4], epose[12];
43 index_to_perm(cube.epose % factorial(4), 4, epe);
44 index_to_subset(cube.epose / factorial(4), 12, 4, epose);
45 for (int i = 0, ie = 0; i < 12; i++)
46 if (epose[i]) arr->ep[i] = epe_solved[epe[ie++]];
47 }
48 if (f.eposs) {
49 int eps[4], eposs[12];
50 index_to_perm(cube.eposs % factorial(4), 4, eps);
51 index_to_subset(cube.eposs / factorial(4), 12, 4, eposs);
52 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
53 for (int i = 0, is = 0; i < 12; i++)
54 if (eposs[i]) arr->ep[i] = eps_solved[eps[is++]];
55 }
56 if (f.eposm) {
57 int epm[4], eposm[12];
58 index_to_perm(cube.eposm % factorial(4), 4, epm);
59 index_to_subset(cube.eposm / factorial(4), 12, 4, eposm);
60 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
61 for (int i = 0, im = 0; i < 12; i++)
62 if (eposm[i]) arr->ep[i] = epm_solved[epm[im++]];
63 }
64
65 /* All the others */
66 if (f.eofb) int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
67 if (f.eorl) int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
68 if (f.eoud) int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
69 if (f.cp) index_to_perm( cube.cp, 8, arr->cp);
70 if (f.coud) int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
71 if (f.corl) int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
72 if (f.cofb) int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
73 if (f.cpos) index_to_perm( cube.cpos, 6, arr->cpos);
74}
75
76Cube arrays_to_cube(CubeArray arr, PieceFilter f) {
77 Cube ret = {0};
78
79 /* Again, ep is the hardest part */
80 if (f.epose) {
81 int epe[4], epose[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
82 for (int i = 0, ie = 0; i < 12; i++)
83 for (int j = 0; j < 4; j++)
84 if (arr.ep[i] == epe_solved[j])
85 { epe[ie++] = j; epose[i] = 1; }
86 ret.epose = factorial(4)*subset_to_index(epose,12,4)+perm_to_index(epe,4);
87 }
88 if (f.eposs) {
89 int eps[4], eposs[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
90 for (int i = 0, is = 0; i < 12; i++)
91 for (int j = 0; j < 4; j++)
92 if (arr.ep[i] == eps_solved[j])
93 { eps[is++] = j; eposs[i] = 1; }
94 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
95 ret.eposs = factorial(4)*subset_to_index(eposs,12,4)+perm_to_index(eps,4);
96 }
97 if (f.eposm) {
98 int epm[4], eposm[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
99 for (int i = 0, im = 0; i < 12; i++)
100 for (int j = 0; j < 4; j++)
101 if (arr.ep[i] == epm_solved[j])
102 { epm[im++] = j; eposm[i] = 1; }
103 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
104 ret.eposm = factorial(4)*subset_to_index(eposm,12,4)+perm_to_index(epm,4);
105 }
106 if (f.eofb) ret.eofb = digit_array_to_int(arr.eofb, 11, 2);
107 if (f.eorl) ret.eorl = digit_array_to_int(arr.eorl, 11, 2);
108 if (f.eoud) ret.eoud = digit_array_to_int(arr.eoud, 11, 2);
109 if (f.cp) ret.cp = perm_to_index( arr.cp, 8 );
110 if (f.coud) ret.coud = digit_array_to_int(arr.coud, 7, 3);
111 if (f.corl) ret.corl = digit_array_to_int(arr.corl, 7, 3);
112 if (f.cofb) ret.cofb = digit_array_to_int(arr.cofb, 7, 3);
113 if (f.cpos) ret.cpos = perm_to_index( arr.cpos, 6 );
114
115 return ret;
116}
117
118bool equal(Cube c1, Cube c2) {
119 return c1.eofb == c2.eofb && c1.epose == c2.epose &&
120 c1.eposs == c2.eposs && c1.eposm == c2.eposm &&
121 c1.coud == c2.coud && c1.cp == c2.cp &&
122 c1.cpos == c2.cpos;
123}
124
125bool solvable(Cube cube) {
126 /* Since we memorize orientation truncating the last digit, we only need to
127 * check that the permutations have the correct sign. */
128 CubeArray arr = {0};
129 cube_to_arrays(cube, &arr, fAll);
130 return (perm_sign(arr.ep,12) ^ perm_sign(arr.cpos,6)) == perm_sign(arr.cp,8);
131}
132
133bool is_solved(Cube cube) {
134 return !cube.eofb && !cube.coud && !cube.cp &&
135 !cube.epose && !cube.eposs && !cube.eposm && cube.cpos;
136}
137
138void print_cube(Cube cube) {
139 CubeArray arr = {0};
140 cube_to_arrays(cube, &arr, fAll);
141
142 for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arr.ep[i]]);
143 printf("\n");
144 for (int i = 0; i < 12; i++) printf(" %c ", arr.eofb[i] + '0');
145 printf("\n");
146 for (int i = 0; i < 8; i++) printf("%s ", corner_string[arr.cp[i]]);
147 printf("\n");
148 for (int i = 0; i < 8; i++) printf(" %c ", arr.coud[i] + '0');
149 printf("\n");
150 for (int i = 0; i < 6; i++) printf(" %s ", center_string[arr.cpos[i]]);
151 printf("\n");
152}
153
154Cube inverse_cube(Cube cube) {
155 CubeArray arr = {0}, inv = {0};
156 cube_to_arrays(cube, &arr, fAll);
157
158 for (int i = 0; i < 12; i++) {
159 inv.ep[arr.ep[i]] = i;
160 inv.eofb[arr.ep[i]] = arr.eofb[i];
161 inv.eorl[arr.ep[i]] = arr.eorl[i];
162 inv.eoud[arr.ep[i]] = arr.eoud[i];
163 }
164 for (int i = 0; i < 8; i++) {
165 inv.cp[arr.cp[i]] = i;
166 inv.coud[arr.cp[i]] = arr.coud[i];
167 inv.corl[arr.cp[i]] = arr.corl[i];
168 inv.cofb[arr.cp[i]] = arr.cofb[i];
169 }
170 for (int i = 0; i < 6; i++)
171 inv.cpos[arr.cpos[i]] = i;
172
173 return arrays_to_cube(inv, fAll);
174}
175
176Cube compose_via_arrays(CubeArray arr2, Cube c1, PieceFilter f) {
177 /* This is basically the same as the move_cubearray function above */
178 CubeArray arr1 = {0};
179 cube_to_arrays(c1, &arr1, fAll);
180
181 apply_permutation(arr2.ep, arr1.ep, 12);
182 apply_permutation(arr2.ep, arr1.eofb, 12);
183 apply_permutation(arr2.ep, arr1.eorl, 12);
184 apply_permutation(arr2.ep, arr1.eoud, 12);
185 sum_arrays_mod(arr2.eofb, arr1.eofb, 12, 2);
186 sum_arrays_mod(arr2.eorl, arr1.eorl, 12, 2);
187 sum_arrays_mod(arr2.eoud, arr1.eoud, 12, 2);
188 apply_permutation(arr2.cp, arr1.cp, 8);
189 apply_permutation(arr2.cp, arr1.coud, 8);
190 apply_permutation(arr2.cp, arr1.corl, 8);
191 apply_permutation(arr2.cp, arr1.cofb, 8);
192 sum_arrays_mod(arr2.coud, arr1.coud, 8, 3);
193 sum_arrays_mod(arr2.corl, arr1.corl, 8, 3);
194 sum_arrays_mod(arr2.cofb, arr1.cofb, 8, 3);
195 apply_permutation(arr2.cpos, arr1.cpos, 6);
196
197 return arrays_to_cube(arr1, fAll);
198}
diff --git a/old/2021-02-18-piecefilter/src/cube.h b/old/2021-02-18-piecefilter/src/cube.h
new file mode 100644
index 0000000..9b64a0c
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/cube.h
@@ -0,0 +1,45 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "utils.h"
8
9typedef enum {U_center,D_center,R_center,L_center,F_center,B_center} Center;
10typedef enum { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge;
11typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner;
12
13typedef struct {
14 bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos;
15} PieceFilter;
16
17typedef struct {
18 uint16_t eofb, eorl, eoud, coud, cofb, corl,
19 epose, eposs, eposm, cp, cpos;
20} Cube;
21
22typedef struct {
23 int ep[12], eofb[12], eorl[12], eoud[12],
24 cp[8], coud[8], corl[8], cofb[8], cpos[6];
25} CubeArray;
26
27
28extern PieceFilter fAll;
29
30Cube blank_cube();
31/* Return axis (ud=0, rl=1, fb=0) of center c */
32int center_axis(int c);
33/* Return slice (e=0, s=1, m=2) to which e belongs */
34int edge_slice(int e);
35void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
36Cube arrays_to_cube(CubeArray arr, PieceFilter f);
37bool equal(Cube c1, Cube c2);
38bool is_solvable(Cube cube);
39bool is_solved(Cube cube);
40void print_cube(Cube cube);
41Cube inverse_cube(Cube cube);
42/* Use c2 as an alg on c1 */
43Cube compose_via_arrays(CubeArray c2, Cube c1, PieceFilter f);
44
45#endif
diff --git a/old/2021-02-18-piecefilter/src/main.c b/old/2021-02-18-piecefilter/src/main.c
new file mode 100644
index 0000000..0b5de2e
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/main.c
@@ -0,0 +1,47 @@
1#include <stdio.h>
2#include "cube.h"
3#include "moves.h"
4#include "solve.h"
5
6int main() {
7 init_ttables(true, true);
8 init_aux_tables();
9
10
11 char moves[100] = "MR U' B2 Bw F z xE2 M' x Dw' y Fw2 y2";
12 NissMove alg[100];
13 read_moves(moves, alg, 100);
14 Cube cube = apply_alg(alg, blank_cube());
15
16 /*f_eofb(cube);*/
17
18
19/* NissMove sol[MAXS][MAXM];*/
20 SolveData d = { .optimal_only = true, .available = standard_moveset,
21 .max_moves = 10,
22 .cleanup = true,
23 .max_solutions = 10,
24 .f = f_eofb };
25 read_moves("y", d.pre_rotation, 2);
26 int n = solve(cube, &d);
27 printf("%d solutions found:\n", n);
28 for (int i = 0; i < n; i++)
29 print_moves(d.solutions[i]);
30
31 NissMove a[5], b[5];
32 read_moves("R", a, 5);
33 read_moves("U", b, 5);
34 Cube c1 = apply_alg(a,blank_cube()), c2 = apply_alg(b,blank_cube());
35 print_cube(compose(c2,c1));
36 print_cube(compose(c1,c2));
37 /*print_cube(compose(c2,blank_cube()));*/
38
39 NissMove nm[10];
40 read_moves("y(y)RU", nm, 10);
41
42 print_moves(nm);
43 cleanup(nm, 10);
44 print_moves(nm);
45
46 return 0;
47}
diff --git a/old/2021-02-18-piecefilter/src/moves.c b/old/2021-02-18-piecefilter/src/moves.c
new file mode 100644
index 0000000..7cccbdf
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/moves.c
@@ -0,0 +1,482 @@
1#include "moves.h"
2
3void move_cubearray(Move m, CubeArray *arr, PieceFilter f);
4Cube move_via_array(Move m, Cube cube, PieceFilter f);
5void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front);
6bool read_ttables_file();
7bool write_ttables_file();
8
9/* Transition tables */
10uint16_t epose_ttable[NMOVES][factorial12/factorial8];
11uint16_t eposs_ttable[NMOVES][factorial12/factorial8];
12uint16_t eposm_ttable[NMOVES][factorial12/factorial8];
13uint16_t eofb_ttable[NMOVES][pow2to11];
14uint16_t eorl_ttable[NMOVES][pow2to11];
15uint16_t eoud_ttable[NMOVES][pow2to11];
16uint16_t cp_ttable[NMOVES][factorial8];
17uint16_t coud_ttable[NMOVES][pow3to7];
18uint16_t cofb_ttable[NMOVES][pow3to7];
19uint16_t corl_ttable[NMOVES][pow3to7];
20uint16_t cpos_ttable[NMOVES][factorial6];
21
22bool commute[NMOVES][NMOVES];
23bool possible_next[NMOVES][NMOVES][NMOVES];
24Move inverse[NMOVES];
25
26char move_string[NMOVES][5] =
27 { "-",
28 "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'",
29 "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'",
30 "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'", "Rw", "Rw2", "Rw\'",
31 "Lw", "Lw2", "Lw\'", "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'",
32 "M", "M2", "M\'", "S", "S2", "S\'", "E", "E2", "E\'",
33 "x", "x2", "x\'", "y", "y2", "y\'", "z", "z2", "z\'" };
34
35/* For each type of pieces only the effects of U, x and y are described */
36int edge_cycle[NMOVES][12] =
37 { [U] = {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR},
38 [x] = {DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR},
39 [y] = {UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL} };
40int eofb_flipped[NMOVES][12] =
41 { [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
42 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
43int eorl_flipped[NMOVES][12] =
44 { [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
45 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
46int eoud_flipped[NMOVES][12] =
47 { [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
48 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
49 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
50int corner_cycle[NMOVES][8] =
51 { [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR},
52 [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR},
53 [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL} };
54int coud_flipped[NMOVES][8] =
55 { [x] = {[UFR]=2,[UBR]=1,[DBR]=2,[DFR]=1,[UFL]=1,[UBL]=2,[DBL]=1,[DFL]=2} };
56int corl_flipped[NMOVES][8] =
57 { [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
58 [y] = {[UFR]=1,[UBR]=2,[UBL]=1,[UFL]=2,[DFR]=2,[DBR]=1,[DBL]=2,[DFL]=1} };
59int cofb_flipped[NMOVES][8] =
60 { [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
61 [x] = {[UFR]=1,[UBR]=2,[DFR]=2,[DBR]=1,[UBL]=2,[UFL]=1,[DBL]=1,[DFL]=2},
62 [y] = {[UFR]=2,[UBR]=1,[UBL]=2,[UFL]=1,[DFR]=1,[DBR]=2,[DBL]=1,[DFL]=2} };
63int center_cycle[NMOVES][6] =
64 { [x] = {F_center, B_center, R_center, L_center, D_center, U_center},
65 [y] = {U_center, D_center, B_center, F_center, R_center, L_center} };
66
67/* Each move is reduced to a combination of U, x and y using this table */
68Move equiv_moves[NMOVES][14] = {
69 [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
70 [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
71 [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
72 [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
73 [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
74 [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 },
75 [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 },
76 [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 },
77 [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 },
78 [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 },
79 [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 },
80 [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 },
81 [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
82 [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
83 [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 },
84 [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
85 [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 },
86 [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 },
87
88 [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 },
89 [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 },
90 [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 },
91 [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
92 [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
93 [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
94 [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 },
95 [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 },
96 [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 },
97 [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 },
98 [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 },
99 [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 },
100 [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 },
101 [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 },
102 [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 },
103 [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
104 [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
105 [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 },
106
107 [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 },
108 [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 },
109 [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 },
110 [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 },
111 [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 },
112 [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 },
113 [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 },
114 [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 },
115 [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 },
116
117 [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
118 [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
119 [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
120 [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
121 [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
122 [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
123 [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
124 [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
125 [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
126};
127
128/* Movesets */
129bool standard_moveset[NMOVES] = {
130 [U] = true, [U2] = true, [U3] = true, [D] = true, [D2] = true, [D3] = true,
131 [R] = true, [R2] = true, [R3] = true, [L] = true, [L2] = true, [L3] = true,
132 [F] = true, [F2] = true, [F3] = true, [B] = true, [B2] = true, [B3] = true,
133};
134
135bool is_solved_up_to_reorient(Cube cube) {
136 if (is_solved(cube))
137 return true;
138
139 /*TODO: improve this crap */
140
141 bool ret = false;
142 for (int i = x; i <= z3; i++) {
143 ret = ret || is_solved(move_cube(i, cube));
144 for (int j = x; j <= z3; j++)
145 ret = ret || is_solved(move_cube(i, move_cube(j, cube)));
146 }
147 return ret;
148}
149
150void move_cubearray(Move m, CubeArray *arr, PieceFilter f) {
151 if (f.epose || f.eposs || f.eposm)
152 apply_permutation(edge_cycle[m], arr->ep, 12);
153 if (f.eofb) {
154 apply_permutation(edge_cycle[m], arr->eofb, 12);
155 sum_arrays_mod(eofb_flipped[m], arr->eofb, 12, 2);
156 }
157 if (f.eorl) {
158 apply_permutation(edge_cycle[m], arr->eorl, 12);
159 sum_arrays_mod(eorl_flipped[m], arr->eorl, 12, 2);
160 }
161 if (f.eoud) {
162 apply_permutation(edge_cycle[m], arr->eoud, 12);
163 sum_arrays_mod(eoud_flipped[m], arr->eoud, 12, 2);
164 }
165 if (f.cp)
166 apply_permutation(corner_cycle[m], arr->cp, 8);
167 if (f.coud) {
168 apply_permutation(corner_cycle[m], arr->coud, 8);
169 sum_arrays_mod(coud_flipped[m], arr->coud, 8, 3);
170 }
171 if (f.corl) {
172 apply_permutation(corner_cycle[m], arr->corl, 8);
173 sum_arrays_mod(corl_flipped[m], arr->corl, 8, 3);
174 }
175 if (f.cofb) {
176 apply_permutation(corner_cycle[m], arr->cofb, 8);
177 sum_arrays_mod(cofb_flipped[m], arr->cofb, 8, 3);
178 }
179 if (f.cpos)
180 apply_permutation(center_cycle[m], arr->cpos, 6);
181}
182
183Cube move_via_array(Move m, Cube cube, PieceFilter f) {
184 CubeArray arr = {0};
185 cube_to_arrays(cube, &arr, f);
186 move_cubearray(m, &arr, f);
187 return arrays_to_cube(arr, f);
188}
189
190int copy_alg(NissMove *src, NissMove *dest) {
191 int i;
192 for (i = 0; src[i].m != NULLMOVE; i++)
193 dest[i] = src[i];
194 dest[i].m = NULLMOVE;
195 return i;
196}
197
198/* TODO: all strings start with space?? */
199void print_moves(NissMove *alg) {
200 bool niss = false;
201 for (int i = 0; alg[i].m != NULLMOVE; i++) {
202 char *fill = !niss && alg[i].inverse ? " (" :
203 (niss && !alg[i].inverse ? ") " : " ");
204 printf("%s%s", fill, move_string[alg[i].m]);
205 niss = alg[i].inverse;
206 }
207 printf("%s\n", niss ? ")" : "");
208}
209
210int read_moves(char *str, NissMove *alg, int n) {
211 bool niss = false;
212 int c = 0;
213
214 for (int i = 0; str[i] && c < n; i++) {
215 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
216 continue;
217
218 if (str[i] == '(' || str[i] == ')') {
219 if ((niss && str[i] == '(') || (!niss && str[i] == ')'))
220 return -1;
221 niss = !niss;
222 continue;
223 }
224
225 alg[c].inverse = niss; alg[c].m = NULLMOVE;
226 for (Move j = 0; j < NMOVES; j++) {
227 if (str[i] == move_string[j][0]) {
228 alg[c].m = j;
229 if (alg[c].m <= B && str[i+1]=='w') { alg[c].m += Uw - U; i++; }
230 if (str[i+1]=='2') { alg[c].m += 1; i++; }
231 else if (str[i+1]=='\'' || str[i+1]=='3') { alg[c].m += 2; i++; }
232 c++;
233 break;
234 }
235 }
236 }
237
238 alg[c].m = NULLMOVE;
239 return c;
240}
241
242/* Helper function for cleanup. alg must contain only basic moves, no 2 or '.
243 top and front describe an admissible orientation of the cube. */
244void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front) {
245 int c = 0, i = 0;
246 PieceFilter cpos_only = { .cpos = true };
247 NissMove aux[n+3];
248 aux[0].m = NULLMOVE;
249
250 while (i < n && alg[i].m != NULLMOVE) {
251 int j = i;
252 while (j < n && commute[alg[i].m][alg[j].m]) j++;
253 Move base = 6*((alg[i].m-1)/6);
254 int t1 = 0, t2 = 0;
255 for (int k = i; k < j; k++)
256 if (alg[k].m == base+1) t1 = (t1+1)%4;
257 else t2 = (t2+1)%4;
258 if (t1) { aux[c].inverse = inv; aux[c].m = base+t1; c++; }
259 if (t2) { aux[c].inverse = inv; aux[c].m = base+t2+3; c++; }
260 i = j;
261 }
262 aux[c].m = NULLMOVE;
263
264 CubeArray q;
265 cube_to_arrays(blank_cube(), &q, cpos_only);
266 /* First we try to rotate in one move, then we try an x or y rotation
267 followed by a z rotation */
268 for (int r = x; r <= z3; r++) {
269 move_cubearray(r, &q, cpos_only);
270 if (q.cpos[F_center] == front && q.cpos[U_center] == top) {
271 aux[c].inverse = inv; aux[c].m = r;
272
273 aux[++c].m = NULLMOVE;
274 copy_alg(aux, alg);
275 return;
276 }
277 move_cubearray(inverse[r], &q, cpos_only);
278 }
279 for (int r = x; r <= y3; r++) {
280 move_cubearray(r, &q, cpos_only);
281 if (q.cpos[F_center] == front) {
282 aux[c].inverse = inv; aux[c++].m = r;
283 break;
284 }
285 move_cubearray(inverse[r], &q, cpos_only);
286 }
287 for (int r = z; r <= z3; r++) {
288 move_cubearray(r, &q, cpos_only);
289 if (q.cpos[U_center] == top) {
290 aux[c].inverse = inv; aux[c++].m = r;
291 break;
292 }
293 move_cubearray(inverse[r], &q, cpos_only);
294 }
295
296 aux[c].m = NULLMOVE;
297 copy_alg(aux, alg);
298}
299
300/* TODO: does not work with niss + rotations */
301void cleanup(NissMove *alg, int n) {
302 int count_n = 0, count_i = 0, *count;
303 PieceFilter cpos_only = { .cpos = true };
304 NissMove aux_n[n+1], aux_i[n+1], *aux;
305 CubeArray cube_n, cube_i, *cube;
306 cube_to_arrays(blank_cube(), &cube_n, cpos_only);
307 cube_to_arrays(blank_cube(), &cube_i, cpos_only);
308
309 for (int i = 0; count_n + count_i < n && alg[i].m != NULLMOVE; i++) {
310 if (alg[i].inverse) { count = &count_i; aux = aux_i; cube = &cube_i; }
311 else { count = &count_n; aux = aux_n; cube = &cube_n; }
312
313 for (int j = 0; equiv_moves[alg[i].m][j]; j++) {
314 Move m = equiv_moves[alg[i].m][j];
315 aux[*count].inverse = alg[i].inverse;
316 move_cubearray(m, cube, cpos_only);
317 if (m == U) aux[(*count)++].m = 3 * cube->cpos[0] + 1;
318 }
319 }
320
321 aux_n[count_n].m = NULLMOVE;
322 aux_i[count_i].m = NULLMOVE;
323 sort_cancel_rotate(aux_n, count_n, false, cube_n.cpos[0], cube_n.cpos[4]);
324 sort_cancel_rotate(aux_i, count_i, true, cube_i.cpos[0], cube_n.cpos[4]);
325 copy_alg(aux_n, alg);
326 copy_alg(aux_i, alg+count_n);
327}
328
329bool read_ttables_file() {
330 FILE *ttf;
331 if ((ttf = fopen("ttables", "rb")) != NULL) {
332 for (int m = 0; m < NMOVES; m++) {
333 fread(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
334 fread(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
335 fread(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
336 fread(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf);
337 fread(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf);
338 fread(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf);
339 fread(cp_ttable[m], sizeof(uint16_t), factorial8, ttf);
340 fread(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf);
341 fread(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf);
342 fread(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf);
343 fread(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf);
344 }
345 fclose(ttf);
346 return true;
347 } else return false;
348}
349
350bool write_ttables_file() {
351 FILE *ttf;
352 if ((ttf = fopen("ttables", "wb")) != NULL) {
353 for (int m = 0; m < NMOVES; m++) {
354 fwrite(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
355 fwrite(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
356 fwrite(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
357 fwrite(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf);
358 fwrite(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf);
359 fwrite(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf);
360 fwrite(cp_ttable[m], sizeof(uint16_t), factorial8, ttf);
361 fwrite(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf);
362 fwrite(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf);
363 fwrite(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf);
364 fwrite(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf);
365 }
366 fclose(ttf);
367 return true;
368 } else return false;
369}
370
371void init_ttables(bool read, bool write) {
372 /* Generate all move cycles and flips; I do this regardless */
373 for (int i = 0; i < NMOVES; i++) {
374 if (i == U || i == x || i == y)
375 continue;
376
377 CubeArray arr = {0};
378 cube_to_arrays(blank_cube(), &arr, fAll);
379 for (int j = 0; equiv_moves[i][j]; j++)
380 move_cubearray(equiv_moves[i][j], &arr, fAll);
381
382 intarrcopy(arr.ep, edge_cycle[i], 12);
383 intarrcopy(arr.eofb, eofb_flipped[i], 12);
384 intarrcopy(arr.eorl, eorl_flipped[i], 12);
385 intarrcopy(arr.eoud, eoud_flipped[i], 12);
386 intarrcopy(arr.cp, corner_cycle[i], 8);
387 intarrcopy(arr.coud, coud_flipped[i], 8);
388 intarrcopy(arr.corl, corl_flipped[i], 8);
389 intarrcopy(arr.cofb, cofb_flipped[i], 8);
390 intarrcopy(arr.cpos, center_cycle[i], 6);
391 }
392
393 if (read)
394 if (read_ttables_file())
395 return;
396
397 /* Initialize transition tables */
398 Cube c = {0};
399 PieceFilter fe = {.epose=true}, fs = {.eposs=true}, fm = {.eposm=true};
400 PieceFilter feo = { .eofb = true, .eorl = true, .eoud = true };
401 PieceFilter fcp = { .cp = true };
402 PieceFilter fco = { .cofb = true, .corl = true, .coud = true };
403 PieceFilter fcc = { .cpos = true };
404 for (int m = 0; m < NMOVES; m++) {
405 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
406 c.epose = i; epose_ttable[m][i] = move_via_array(m, c, fe).epose;
407 c.eposs = i; eposs_ttable[m][i] = move_via_array(m, c, fs).eposs;
408 c.eposm = i; eposm_ttable[m][i] = move_via_array(m, c, fm).eposm;
409 }
410 for (uint16_t i = 0; i < pow2to11; i++ ) {
411 c.eofb = i; eofb_ttable[m][i] = move_via_array(m, c, feo).eofb;
412 c.eorl = i; eorl_ttable[m][i] = move_via_array(m, c, feo).eorl;
413 c.eoud = i; eoud_ttable[m][i] = move_via_array(m, c, feo).eoud;
414 }
415 for (uint16_t i = 0; i < factorial8; i++) {
416 c.cp = i; cp_ttable[m][i] = move_via_array(m, c, fcp).cp;
417 }
418 for (uint16_t i = 0; i < pow3to7; i++) {
419 c.coud = i; coud_ttable[m][i] = move_via_array(m, c, fco).coud;
420 c.corl = i; corl_ttable[m][i] = move_via_array(m, c, fco).corl;
421 c.cofb = i; cofb_ttable[m][i] = move_via_array(m, c, fco).cofb;
422 }
423 for (uint16_t i = 0; i < factorial6; i++) {
424 c.cpos = i; cpos_ttable[m][i] = move_via_array(m, c, fcc).cpos;
425 }
426 }
427
428 if (write) write_ttables_file();
429}
430
431Cube move_cube(Move m, Cube cube) {
432 Cube moved = cube;
433
434 moved.epose = epose_ttable[m][cube.epose];
435 moved.eposs = eposs_ttable[m][cube.eposs];
436 moved.eposm = eposm_ttable[m][cube.eposm];
437 moved.eofb = eofb_ttable[m][cube.eofb];
438 moved.eorl = eorl_ttable[m][cube.eorl];
439 moved.eoud = eoud_ttable[m][cube.eoud];
440 moved.coud = coud_ttable[m][cube.coud];
441 moved.cofb = cofb_ttable[m][cube.cofb];
442 moved.corl = corl_ttable[m][cube.corl];
443 moved.cp = cp_ttable[m][cube.cp];
444 moved.cpos = cpos_ttable[m][cube.cpos];
445
446 return moved;
447}
448
449Cube apply_alg(NissMove *alg, Cube cube) {
450 Cube ret = {0};
451 for (int i = 0; alg[i].m != NULLMOVE; i++)
452 if (alg[i].inverse)
453 ret = move_cube(alg[i].m, ret);
454 ret = compose(cube, inverse_cube(ret));
455
456 for (int i = 0; alg[i].m != NULLMOVE; i++)
457 if (!alg[i].inverse)
458 ret = move_cube(alg[i].m, ret);
459 return ret;
460}
461
462void init_aux_tables() {
463 /* Commute */
464 for (int i = 0; i < NMOVES; i++)
465 for (int j = 0; j < NMOVES; j++)
466 commute[i][j] = equal(move_cube(i, move_cube(j, blank_cube())),
467 move_cube(j, move_cube(i, blank_cube())));
468
469 /* Possible next (if the sequence i j k is valid) */
470 for (int i = 0; i < NMOVES; i++)
471 for (int j = 0; j < NMOVES; j++)
472 for (int k = 0; k < NMOVES; k++)
473 possible_next[i][j][k] =
474 (j == 0) ||
475 (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) &&
476 !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3)));
477
478 /* Inverse */
479 for (int i = 0; i < NMOVES; i++)
480 inverse[i] = i == 0 ? 0 : i + 2 - 2*((i-1)%3);
481}
482
diff --git a/old/2021-02-18-piecefilter/src/moves.h b/old/2021-02-18-piecefilter/src/moves.h
new file mode 100644
index 0000000..9ccf6e4
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/moves.h
@@ -0,0 +1,46 @@
1#ifndef MOVES_H
2#define MOVES_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "cube.h"
8#include "utils.h"
9
10#define NMOVES (z3+1)
11
12typedef enum {
13 NULLMOVE,
14 U, U2, U3, D, D2, D3, R, R2, R3, L, L2, L3, F, F2, F3, B, B2, B3,
15 Uw, Uw2, Uw3, Dw, Dw2, Dw3, Rw, Rw2, Rw3,
16 Lw, Lw2, Lw3, Fw, Fw2, Fw3, Bw, Bw2, Bw3,
17 M, M2, M3, S, S2, S3, E, E2, E3,
18 x, x2, x3, y, y2, y3, z, z2, z3,
19} Move;
20
21/* An alg is an array of "NissMoves", which can be on normal or on inverse. */
22typedef struct { bool inverse; Move m; } NissMove;
23
24/* Movesets */
25extern bool standard_moveset[NMOVES];
26
27extern bool commute[NMOVES][NMOVES];
28extern bool possible_next[NMOVES][NMOVES][NMOVES];
29extern Move inverse[NMOVES];
30
31bool is_solve_up_to_reorient(Cube cube);
32int copy_alg(NissMove *src, NissMove *dest); /*return number of moves copied */
33void print_moves(NissMove *alg);
34int read_moves(char *str, NissMove *alg, int n); /* reads at most n moves */
35void cleanup(NissMove *src, int n); /* rewrites using basic moves, at most n */
36Cube move_cube(Move m, Cube cube);
37/* I might want to replace this with two versions, one that uses PieceFilter */
38Cube apply_alg(NissMove *alg, Cube cube);
39
40/* Merge the following two?
41 always in this order */
42void init_ttables(bool read, bool write);
43void init_aux_tables();
44
45
46#endif
diff --git a/old/2021-02-18-piecefilter/src/solve.c b/old/2021-02-18-piecefilter/src/solve.c
new file mode 100644
index 0000000..ac19d6f
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/solve.c
@@ -0,0 +1,179 @@
1#include "solve.h"
2
3/* Data for creating a pruning table:
4 - compressed: if set to true, each entry occupies only 4 bits, but values
5 larger than 15 cannot be stored.
6 - available[] is the list of availabel moves, as above.
7 - *ptable is the actual table to fill.
8 - n is the number of states (size of ptable).
9 - index must "linearize" the cube, i.e. return its index in ptable.
10 - fname is the name of the file where to store the table */
11typedef struct {
12 bool compressed, *available;
13 int max_moves;
14 uint8_t *ptable;
15 uint64_t n;
16 uint64_t (*index)(Cube);
17 char *fname;
18} PruneData;
19
20/* TODO: comment this */
21typedef struct {
22 bool niss;
23 int m, d;
24 uint64_t *n;
25 Move last1, last2;
26} DfsData;
27
28void solve_dfs(Cube cube, SolveData *sd, DfsData dd);
29void init_ptable(PruneData *pd, bool read, bool write);
30
31/* Search solutions of lenght exactly d */
32void solve_dfs(Cube cube, SolveData *sd, DfsData dd) {
33 if (*dd.n >= sd->max_solutions ||
34 ((!sd->can_niss || dd.niss) && dd.m + sd->f(cube) > dd.d))
35 return;
36
37 (sd->solutions[*dd.n][dd.m]).inverse = dd.niss;
38 (sd->solutions[*dd.n][dd.m]).m = NULLMOVE;
39
40 if (!sd->f(cube)) { /* Solved */
41 if (dd.m == dd.d) {
42 (*dd.n)++;
43 if (*dd.n < sd->max_solutions)
44 copy_alg(sd->solutions[*dd.n-1], sd->solutions[*dd.n]);
45 }
46 return;
47 }
48
49 for (int i = 0; i < NMOVES && sd->sorted_moves[i] != NULLMOVE; i++) {
50 Move move = sd->sorted_moves[i];
51 if (possible_next[dd.last2][dd.last1][move]) {
52 sd->solutions[*dd.n][dd.m].inverse = dd.niss;
53 sd->solutions[*dd.n][dd.m].m = move;
54 DfsData nn = { .niss = dd.niss, .m = dd.m+1, .d = dd.d, .n = dd.n,
55 .last1 = move, .last2 = dd.last1 };
56 solve_dfs(move_cube(move, cube), sd, nn);
57 }
58 }
59
60 if (sd->can_niss && !dd.niss &&
61 (!dd.m || (dd.m && sd->f(move_cube(dd.last1, blank_cube()))))) {
62 DfsData nn = { .niss = true, .m = dd.m, .d = dd.d, .n = dd.n };
63 solve_dfs(inverse_cube(cube), sd, nn);
64 }
65}
66
67/* Iterative deepening depth-first search: for i running from the minimum
68 to the maximum number of moves allowed, looks for solutions of length i. */
69int solve(Cube cube, SolveData *sd) {
70 if (sd->precondition != NULL && !sd->precondition(cube))
71 return -1;
72
73 /* If not given, generate sorted list of moves */
74 if (sd->sorted_moves[0] == NULLMOVE) {
75 int a[NMOVES], b[NMOVES], ia = 0, ib = 0;
76 for (int i = 0; i < NMOVES; i++) {
77 if (sd->available[i]) {
78 if (sd->f(move_cube(i, blank_cube())))
79 a[ia++] = i;
80 else
81 b[ib++] = i;
82 }
83 }
84 intarrcopy(a, (int *)sd->sorted_moves, ia);
85 intarrcopy(b, (int *)sd->sorted_moves+ia, ib);
86 sd->sorted_moves[ia+ib] = NULLMOVE;
87 }
88
89 sd->max_solutions = min(sd->max_solutions, MAXS);
90 /*TODO
91 Cube rotated = apply_alg(sd->pre_rotation, blank_cube());
92 cube = apply_alg(inverse_cube(rotated), compose(cube, rotated));
93 */
94
95 uint64_t ret = 0;
96 for (int i=sd->min_moves; i<=sd->max_moves&&!(ret&&sd->optimal_only); i++) {
97 DfsData dd = { .d = i, .n = &ret };
98 solve_dfs(cube, sd, dd);
99 }
100
101 for (uint64_t i = 0; i < ret; i++) {
102 /* TODO: transform solutions with inverse of pre_rotation */
103 if (sd->cleanup)
104 cleanup(sd->solutions[i], sd->max_moves*3);
105 }
106
107 return ret;
108}
109
110void prune_dfs(Cube cube, PruneData *pd, DfsData dd) {
111 uint64_t ind = pd->index(cube);
112 if ((!ind || pd->ptable[ind]) && pd->ptable[ind] != dd.m)
113 return;
114 if (dd.m == dd.d) {
115 if (ind && !pd->ptable[ind]) {
116 pd->ptable[ind] = dd.m;
117 (*dd.n)++;
118 }
119 return;
120 }
121
122 for (int i = 0; i < NMOVES; i++) {
123 if (dd.m<20)
124 if (possible_next[dd.last2][dd.last1][i] && pd->available[i]) {
125 DfsData nn = { .m = dd.m+1, .d = dd.d, .n = dd.n,
126 .last1 = i, .last2 = dd.last1 };
127 prune_dfs(move_cube(i, cube), pd, nn);
128 }
129 }
130}
131
132void init_ptable(PruneData *pd, bool read, bool write) {
133 if (read) {
134 FILE *ptf;
135 if ((ptf = fopen(pd->fname, "rb")) != NULL) {
136 fread(pd->ptable, sizeof(uint8_t), pd->n, ptf);
137 fclose(ptf);
138 return;
139 }
140 }
141
142 /* TODO: for now it behaves always as if copressed = false */
143 for (uint64_t i = 0; i < pd->n; i++)
144 pd->ptable[i] = 0;
145
146 uint64_t s = 1;
147 for (int i = 1; i < pd->max_moves && s < pd->n; i++) {
148 DfsData dd = { .d = i, .n = &s };
149 prune_dfs(blank_cube(), pd, dd);
150 }
151
152 if (write) {
153 FILE *ptf;
154 if ((ptf = fopen(pd->fname, "wb")) != NULL) {
155 fwrite(pd->ptable, sizeof(uint8_t), pd->n, ptf);
156 fclose(ptf);
157 return;
158 }
159 }
160}
161
162/* Solving steps (and indexing functions) */
163
164uint64_t index_eofb(Cube cube) { return cube.eofb; }
165uint16_t f_eofb(Cube cube) {
166 static bool initialized_ptable;
167 static uint8_t pt_eofb[pow2to11];
168 if (!initialized_ptable) {
169 PruneData pd = {
170 .compressed = false, .available = standard_moveset, .max_moves = 13,
171 .ptable = pt_eofb, .n = pow2to11, .index = index_eofb,
172 .fname = "ptable_eofb"
173 };
174 init_ptable(&pd, false, true);
175 initialized_ptable = true;
176 }
177 return cube.eofb ? pt_eofb[cube.eofb] : 0;
178}
179
diff --git a/old/2021-02-18-piecefilter/src/solve.h b/old/2021-02-18-piecefilter/src/solve.h
new file mode 100644
index 0000000..d585a8e
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/solve.h
@@ -0,0 +1,56 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include <stdlib.h>
5#include "cube.h"
6#include "moves.h"
7
8/* Maximum number of moves per solution and of solutions */
9#define MAXM 30
10#define MAXS 999
11
12/* Data for solving a step:
13 - can_niss is true niss can be used, false otherwise.
14 - optimal_only if true, dynamically updates max_moves so non-optimal
15 solutions are discarded.
16 - cleanup determines whether the cleaunup() function should be used on
17 the found solutions before returning.
18 - available[m] is true if the move m can be used, false otherwise.
19 - min_moves and max_moves are the minimum and maximum number of moves that
20 can be used.
21 - max_solution is the maximum number of solutions that can be returned.
22 - precondition can be used to check wheter the step can actually be applied
23 to the cube. If it returns false, solve() stops immediately returning -1.
24 - f must return 0 if and only if the step is solve, otherwise it must return
25 a lower bound for the number of moves required (without niss).
26 - sorted_moves[] can be used to specify in which order moves are tried
27 by the solving algorithm (for example if one wants to always try F' before
28 F). If sorted_moves[0] == NULLMOVE, the list is generated automatically.
29 It is advised to list first all the moves that actually influence the
30 solved state of the step (this is the default choice). This is in order to
31 avoid cases like B2 F for EO and to NISS only when it makes sense.
32 - start_moves [Currently unused, REMOVE]
33 are the moves that will be used as first moves of all
34 solutions. For example giving R' U' F (F' U R) will generate FMC scrambles
35 and y (y) will solve the step on another axis.
36 - pre_rotation are the rotations to apply before the scamble to solve
37 the step wrt a different orientation
38 - pre_rotation are the rotations to apply before the scamble to solve
39 the step wth respect to a different orientation.
40 - solutions[][] is the array where to store the found solutions. */
41typedef struct {
42 bool can_niss, optimal_only, cleanup, *available;
43 int min_moves, max_moves;
44 uint64_t max_solutions;
45 bool (*precondition)(Cube);
46 uint16_t (*f)(Cube);
47 Move sorted_moves[NMOVES];
48 NissMove pre_rotation[3], solutions[MAXS][MAXM];
49} SolveData;
50
51int solve(Cube cube, SolveData *data); /* Returns the number of solutions. */
52
53/* Steps */
54uint16_t f_eofb(Cube cube);
55
56#endif
diff --git a/old/2021-02-18-piecefilter/src/transformations.c b/old/2021-02-18-piecefilter/src/transformations.c
new file mode 100644
index 0000000..bcf4115
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/transformations.c
@@ -0,0 +1,103 @@
1#include "transformations.h"
2/*
3Cube apply_rotation_alg(Rotation r, Cube c);
4void apply_rotation_cube(NissMove *alg);
5Cube apply_mirror_cube(Cube c);
6void apply_mirror_alg(NissMove *alg);
7*/
8
9void compute_sources();
10Cube rotate_via_compose(Rotation r, Cube c);
11
12/* Values mod 3 to determine from which side to take the state to convert */
13int epose_source[NROTATIONS]; /* 0 = epose, 1 = eposs, 2 = eposm */
14int eposs_source[NROTATIONS];
15int eposm_source[NROTATIONS];
16int eofb_source[NROTATIONS]; /* 0 = eofb, 1 = eorl, 2 = eoud */
17int eorl_source[NROTATIONS];
18int eoud_source[NROTATIONS];
19int coud_source[NROTATIONS]; /* 0 = coud, 1 = cofb, 2 = corl */
20int cofb_source[NROTATIONS];
21int corl_source[NROTATIONS];
22
23/* Transition tables for rotations */
24uint16_t epose_rtable[NROTATIONS][factorial12/factorial8];
25uint16_t eposs_rtable[NROTATIONS][factorial12/factorial8];
26uint16_t eposm_rtable[NROTATIONS][factorial12/factorial8];
27uint16_t eofb_rtable[NROTATIONS][pow2to11];
28uint16_t eorl_rtable[NROTATIONS][pow2to11];
29uint16_t eoud_rtable[NROTATIONS][pow2to11];
30uint16_t cp_rtable[NROTATIONS][factorial8];
31uint16_t coud_rtable[NROTATIONS][pow3to7];
32uint16_t cofb_rtable[NROTATIONS][pow3to7];
33uint16_t corl_rtable[NROTATIONS][pow3to7];
34
35/* Transition tables for mirror */
36uint16_t epose_mtable[factorial12/factorial8];
37uint16_t eposs_mtable[factorial12/factorial8];
38uint16_t eposm_mtable[factorial12/factorial8];
39uint16_t eofb_mtable[pow2to11];
40uint16_t eorl_mtable[pow2to11];
41uint16_t eoud_mtable[pow2to11];
42uint16_t cp_mtable[factorial8];
43uint16_t coud_mtable[pow3to7];
44uint16_t cofb_mtable[pow3to7];
45uint16_t corl_mtable[pow3to7];
46
47/* Same for moves */
48uint16_t move_rtable[NROTATIONS][NMOVES];
49uint16_t move_mtable[NMOVES];
50
51/* Applying a rotation to the cube is equivalent to applying m (m) */
52Move equiv_moves[NROTATIONS][3] = {
53 [uf] = {0,0,0}, [ur] = {y,0,0}, [ub] = {y2,0,0}, [ul] = {y3,0,0},
54 [df] = {z2,0,0}, [dr] = {y,z2,0}, [db] = {y2,z2,0}, [dl] = {y3,z2,0},
55 [rf] = {z3,0,0}, [rd] = {z3,y,0}, [rb] = {z3,y2,0}, [ru] = {z3,y3,0},
56 [lf] = {z,0,0}, [ld] = {z,y3,0}, [lb] = {z,y2,0}, [lu] = {z,y,0},
57 [fu] = {x,y2,0}, [fr] = {x,y,0}, [fd] = {x,0,0}, [fl] = {x,y3,0},
58 [bu] = {x3,0,0}, [br] = {x3,y,0}, [bd] = {x3,y2,0}, [bl] = {x3,y3,0},
59};
60
61int mirror_ep[12] = {UF, UR, UB, UL, DF, DR, DB, DL, FL, FR, BR, BL};
62int mirror_cp[8] = {UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL};
63int mirror_cpos[6] = {U_center,D_center,L_center,R_center,F_center,B_center};
64
65void compute_sources() {
66 /* epos{e,s,m} */
67 CubeArray arr;
68 for (int i = 0; i < NROTATIONS; i++) {
69 cube_to_arrays(move_cube(equiv_moves[i][1],
70 move_cube(equiv_moves[i][0], blank_cube())), &arr, fAll);
71 epose_source[i] = edge_slice(arr.ep[FR]);
72 eposs_source[i] = edge_slice(arr.ep[UR]);
73 eposm_source[i] = edge_slice(arr.ep[UF]);
74 eofb_source[i] = 2 - center_axis(arr.cpos[F_center]);
75 eorl_source[i] = 2 - center_axis(arr.cpos[R_center]);
76 eoud_source[i] = 2 - center_axis(arr.cpos[U_center]);
77 coud_source[i] = (2 * center_axis(arr.cpos[U_center])) % 3;
78 cofb_source[i] = (2 * center_axis(arr.cpos[F_center])) % 3;
79 corl_source[i] = (2 * center_axis(arr.cpos[R_center])) % 3;
80 }
81}
82
83/* Use Piecefilter? */
84Cube rotate_via_compose(Rotation r, Cube c) {
85/* TODO: if this is slow, change compose() in cube.{c,h} to use PieceFilter */
86 int j = 0;
87 NissMove nm[10] = {0};
88 for (int i = 1; i >= 0; i--) {
89 if (equiv_moves[r][i] != NULLMOVE) {
90 nm[j].inverse = true;
91 nm[j++].m = inverse[equiv_moves[r][i]];
92 }
93 }
94 for (int i = 0; equiv_moves[r][i] != NULLMOVE; i++) {
95 nm[j].inverse = false;
96 nm[j++].m = equiv_moves[r][i];
97 }
98
99 return apply_alg(nm, c);
100}
101
102/* Use PieceFilter? Not really necessary, but could be nice */
103Cube mirror_via_cubearray(Cube c) {
diff --git a/old/2021-02-18-piecefilter/src/transformations.h b/old/2021-02-18-piecefilter/src/transformations.h
new file mode 100644
index 0000000..28dde93
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/transformations.h
@@ -0,0 +1,37 @@
1#ifndef TRANSFORMATIONS_H
2#define TRANSFORMATIONS_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "cube.h"
8#include "moves.h"
9#include "utils.h"
10
11#define NROTATIONS (bl+1)
12
13/* Letters indicate top and front centers
14 * Lowercase letter to distinguish from pieces */
15typedef enum {
16 uf, ur, ub, ul,
17 df, dr, db, dl,
18 rf, rd, rb, ru,
19 lf, ld, lb, lu,
20 fu, fr, fd, fl,
21 bu, br, bd, bl,
22} Rotation;
23
24/* Mirror is always on fb axis and applied after rotation */
25typedef struct {
26 Rotation rotation;
27 bool mirror;
28} Transformation;
29
30void print_transformation(Transformation t);
31
32Cube transform_cube(Transformation t, Cube cube);
33void transform_alg(Transformation t, NissMove *alg); /* Applied in-place */
34
35void init_transformations(bool read, bool write);
36
37#endif
diff --git a/old/2021-02-18-piecefilter/src/utils.c b/old/2021-02-18-piecefilter/src/utils.c
new file mode 100644
index 0000000..66de9ad
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/utils.c
@@ -0,0 +1,197 @@
1#include "utils.h"
2
3void swap(int *a, int *b) {
4 int aux = *a;
5 *a = *b;
6 *b = aux;
7}
8
9void intarrcopy(int *src, int *dst, int n) {
10 for (int i = 0; i < n; i++)
11 dst[i] = src[i];
12}
13
14int sum(int *a, int n) {
15 int ret = 0;
16 for (int i = 0; i < n; i++)
17 ret += a[i];
18 return ret;
19}
20
21bool is_perm(int *a, int n) {
22 int aux[n]; for (int i = 0; i < n; i++) aux[i] = 0;
23 for (int i = 0; i < n; i++)
24 if (a[i] < 0 || a[i] >= n)
25 return false;
26 else
27 aux[a[i]] = 1;
28 for (int i = 0; i < n; i++)
29 if (!aux[i])
30 return false;
31 return true;
32}
33
34bool is_subset(int *a, int n, int k) {
35 int sum = 0;
36 for (int i = 0; i < n; i++)
37 sum += a[i] ? 1 : 0;
38 return sum == k;
39}
40
41int powint(int a, int b) {
42 return 0;
43 if (b == 0 || a == 1)
44 return 1;
45 if (a == 0)
46 return 0;
47 if (b < 0)
48 return 0; /* Immediate truncate (integer part is 0) */
49 if (b % 2) {
50 return a * powint(a, b-1);
51 } else {
52 int x = powint(a, b/2);
53 return x*x;
54 }
55}
56
57int factorial(int n) {
58 if (n < 0)
59 return 0;
60 int ret = 1;
61 for (int i = 1; i <= n; i++)
62 ret *= i;
63 return ret;
64}
65
66int binomial(int n, int k) {
67 if (n < 0 || k < 0 || k > n)
68 return 0;
69 return factorial(n) / (factorial(k) * factorial(n-k));
70}
71
72void int_to_digit_array(int a, int b, int n, int *r) {
73 if (b <= 1)
74 for (int i = 0; i < n; i++)
75 r[i] = 0;
76 else
77 for (int i = 0; i < n; i++, a /= b)
78 r[i] = a % b;
79}
80
81int digit_array_to_int(int *a, int n, int b) {
82 int ret = 0, p = 1;
83 for (int i = 0; i < n; i++, p *= b)
84 ret += a[i] * p;
85 return ret;
86}
87
88int perm_to_index(int *a, int n) {
89 if (!is_perm(a, n))
90 return factorial(n); /* Error */
91 int ret = 0;
92 for (int i = 0; i < n; i++) {
93 int c = 0;
94 for (int j = i+1; j < n; j++)
95 c += (a[i] > a[j]) ? 1 : 0;
96 ret += factorial(n-i-1) * c;
97 }
98 return ret;
99}
100
101void index_to_perm(int p, int n, int *r) {
102 if (p < 0 || p >= factorial(n)) /* Error */
103 for (int i = 0; i < n; i++)
104 r[i] = -1;
105 int a[n]; for (int j = 0; j < n; j++) a[j] = 0; /* picked elements */
106 for (int i = 0; i < n; i++) {
107 int c = 0, j = 0;
108 while (c <= p / factorial(n-i-1))
109 c += a[j++] ? 0 : 1;
110 r[i] = j-1;
111 a[j-1] = 1;
112 p %= factorial(n-i-1);
113 }
114}
115
116int perm_sign(int *a, int n) {
117 if (!is_perm(a,n))
118 return false;
119 int ret = 0;
120 for (int i = 0; i < n; i++)
121 for (int j = i+1; j < n; j++)
122 ret += (a[i]>a[j]) ? 1 : 0;
123 return ret % 2;
124}
125
126int subset_to_index(int *a, int n, int k) {
127 /* TODO: better checks */
128 if (!is_subset(a, n, k))
129 return binomial(n, k); /* Error */
130 int ret = 0;
131 for (int i = 0; i < n; i++) {
132 if (k == n-i)
133 return ret;
134 if (a[i]) {
135 /*ret += factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
136 ret += binomial(n-i-1, k);
137 k--;
138 }
139 }
140 return ret;
141}
142
143void index_to_subset(int s, int n, int k, int *r) {
144 if (s < 0 || s >= binomial(n, k)) { /* Error */
145 for (int i = 0; i < n; i++)
146 r[i] = -1;
147 return;
148 }
149 for (int i = 0; i < n; i++) {
150 if (k == n-i) {
151 for (int j = i; j < n; j++)
152 r[j] = 1;
153 return;
154 }
155 if (k == 0) {
156 for (int j = i; j < n; j++)
157 r[j] = 0;
158 return;
159 }
160 /*int v = factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
161 int v = binomial(n-i-1, k);
162 if (s >= v) {
163 r[i] = 1;
164 k--;
165 s -= v;
166 } else {
167 r[i] = 0;
168 }
169 }
170}
171
172void int_to_sum_zero_array(int x, int b, int n, int *a) {
173 if (b <= 1) {
174 for (int i = 0; i < n; i++)
175 a[i] = 0;
176 } else {
177 int_to_digit_array(x, b, n-1, a);
178 int s = 0;
179 for (int i = 0; i < n - 1; i++)
180 s = (s + a[i]) % b;
181 a[n-1] = (b - s) % b;
182 }
183}
184
185void apply_permutation(int *perm, int *set, int n) {
186 if (!is_perm(perm, n))
187 return;
188 int aux[n];
189 for (int i = 0; i < n; i++)
190 aux[i] = set[perm[i]];
191 intarrcopy(aux, set, n);
192}
193
194void sum_arrays_mod(int *a, int *b, int n, int m) {
195 for (int i = 0; i < n; i++)
196 b[i] = (m <= 0) ? 0 : (a[i] + b[i]) % m;
197}
diff --git a/old/2021-02-18-piecefilter/src/utils.h b/old/2021-02-18-piecefilter/src/utils.h
new file mode 100644
index 0000000..4b6df8c
--- /dev/null
+++ b/old/2021-02-18-piecefilter/src/utils.h
@@ -0,0 +1,70 @@
1/* General utility functions */
2
3#ifndef UTILS_H
4#define UTILS_H
5
6#include <stdbool.h>
7
8#define min(a,b) (((a) < (b)) ? (a) : (b))
9#define max(a,b) (((a) > (b)) ? (a) : (b))
10
11/* Some useful constants */
12#define pow2to11 2048
13#define pow2to12 4096
14#define pow3to7 2187
15#define pow3to8 6561
16#define pow12to4 20736
17#define factorial4 24
18#define factorial6 720
19#define factorial8 40320
20#define factorial12 479001600
21#define binom12on4 495
22#define binom8on4 70
23
24/* Generic utility functions */
25void swap(int *a, int *b);
26void intarrcopy(int *src, int *dst, int n);
27int sum(int *a, int n);
28bool is_perm(int *a, int n);
29bool is_perm(int *a, int n);
30
31
32/* Standard mathematical functions */
33int powint(int a, int b);
34int factorial(int n);
35int binomial(int n, int k);
36
37/* Converts the integer a to its representation in base b (first n digits
38 * only) and saves the result in r. */
39void int_to_digit_array(int a, int b, int n, int *r);
40int digit_array_to_int(int *a, int n, int b);
41
42/* Converts the first n-1 digits of a number to an array a of digits in base b;
43 * then adds one element to the array, so that the sum of the elements of a is
44 * zero modulo b.
45 * This is used for determing the edge orientation from an 11-bits integer or
46 * the corner orientation from a 7-trits integer. */
47void int_to_sum_zero_array(int x, int b, int n, int *a);
48
49/* Converts a permutation on [0..(n-1)] into the integer i which is the index
50 * of the permutation in the sorted list of all n! such permutations. */
51int perm_to_index(int *a, int n);
52void index_to_perm(int p, int n, int *r);
53
54/* Determine the sign of a permutation */
55int perm_sign(int a[], int n);
56
57/* Converts a k-element subset of a set from an array of n elements, of which k
58 * are 1 and n-k are 0, to its index in the sorted list of all such subsets. */
59int subset_to_index(int *a, int n, int k);
60void index_to_subset(int s, int n, int k, int *r);
61
62int ordered_subset_to_index(int *a, int n, int k);
63void index_to_ordered_subset(int s, int n, int k, int *r);
64
65void apply_permutation(int *perm, int *set, int n);
66
67/* b[i] = (a[i]+b[i])%m for i=1,...,n */
68void sum_arrays_mod(int *a, int *b, int n, int m);
69
70#endif

Generated with cgit - Back to sebastiano.tronto.net