aboutsummaryrefslogtreecommitdiff
path: root/old/2021-02-06
diff options
context:
space:
mode:
Diffstat (limited to 'old/2021-02-06')
-rw-r--r--old/2021-02-06/cube.c664
-rw-r--r--old/2021-02-06/cube.h60
-rw-r--r--old/2021-02-06/main.c46
-rw-r--r--old/2021-02-06/solve.c177
-rw-r--r--old/2021-02-06/solve.h55
-rw-r--r--old/2021-02-06/utils.c197
-rw-r--r--old/2021-02-06/utils.h70
7 files changed, 0 insertions, 1269 deletions
diff --git a/old/2021-02-06/cube.c b/old/2021-02-06/cube.c
deleted file mode 100644
index 9185281..0000000
--- a/old/2021-02-06/cube.c
+++ /dev/null
@@ -1,664 +0,0 @@
1#include "cube.h"
2
3typedef struct {
4 int ep[12], eofb[12], eorl[12], eoud[12],
5 cp[8], coud[8], corl[8], cofb[8], cpos[6];
6} CubeArray;
7
8typedef struct {
9 bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos;
10} PieceFilter;
11
12PieceFilter fAll = {true,true,true,true,true,true,true,true,true,true,true};
13PieceFilter cpos_only = { .cpos = true };
14
15void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
16Cube arrays_to_cube(CubeArray arr, PieceFilter f);
17void move_cubearray(Move m, CubeArray *arr, PieceFilter f);
18Cube move_via_array(Move m, Cube cube, PieceFilter f);
19void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front);
20bool read_ttables_file();
21bool write_ttables_file();
22
23/* Transition tables */
24uint16_t epose_ttable[NMOVES][factorial12/factorial8];
25uint16_t eposs_ttable[NMOVES][factorial12/factorial8];
26uint16_t eposm_ttable[NMOVES][factorial12/factorial8];
27uint16_t eofb_ttable[NMOVES][pow2to11];
28uint16_t eorl_ttable[NMOVES][pow2to11];
29uint16_t eoud_ttable[NMOVES][pow2to11];
30uint16_t cp_ttable[NMOVES][factorial8];
31uint16_t coud_ttable[NMOVES][pow3to7];
32uint16_t cofb_ttable[NMOVES][pow3to7];
33uint16_t corl_ttable[NMOVES][pow3to7];
34uint16_t cpos_ttable[NMOVES][factorial6];
35
36bool commute[NMOVES][NMOVES];
37bool possible_next[NMOVES][NMOVES][NMOVES];
38Move inverse[NMOVES];
39
40char edge_string[12][5] =
41 { "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR" };
42char corner_string[8][5] = { "UFR","UFL","UBL","UBR","DFR","DFL","DBL","DBR" };
43char center_string[6][5] = { "U", "D", "R", "L", "F", "B" };
44char move_string[NMOVES][5] =
45 { "-",
46 "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'",
47 "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'",
48 "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'", "Rw", "Rw2", "Rw\'",
49 "Lw", "Lw2", "Lw\'", "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'",
50 "M", "M2", "M\'", "S", "S2", "S\'", "E", "E2", "E\'",
51 "x", "x2", "x\'", "y", "y2", "y\'", "z", "z2", "z\'" };
52
53/* For each type of pieces only the effects of U, x and y are described */
54int edge_cycle[NMOVES][12] =
55 { [U] = {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR},
56 [x] = {DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR},
57 [y] = {UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL} };
58int eofb_flipped[NMOVES][12] =
59 { [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
60 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
61int eorl_flipped[NMOVES][12] =
62 { [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
63 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
64int eoud_flipped[NMOVES][12] =
65 { [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
66 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
67 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
68int corner_cycle[NMOVES][8] =
69 { [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR},
70 [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR},
71 [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL} };
72int coud_flipped[NMOVES][8] =
73 { [x] = {[UFR]=2,[UBR]=1,[DBR]=2,[DFR]=1,[UFL]=1,[UBL]=2,[DBL]=1,[DFL]=2} };
74int corl_flipped[NMOVES][8] =
75 { [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
76 [y] = {[UFR]=1,[UBR]=2,[UBL]=1,[UFL]=2,[DFR]=2,[DBR]=1,[DBL]=2,[DFL]=1} };
77int cofb_flipped[NMOVES][8] =
78 { [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
79 [x] = {[UFR]=1,[UBR]=2,[DFR]=2,[DBR]=1,[UBL]=2,[UFL]=1,[DBL]=1,[DFL]=2},
80 [y] = {[UFR]=2,[UBR]=1,[UBL]=2,[UFL]=1,[DFR]=1,[DBR]=2,[DBL]=1,[DFL]=2} };
81int center_cycle[NMOVES][6] =
82 { [x] = {F_center, B_center, R_center, L_center, D_center, U_center},
83 [y] = {U_center, D_center, B_center, F_center, R_center, L_center} };
84
85/* Each move is reduced to a combination of U, x and y using this table */
86Move equiv_moves[NMOVES][14] = {
87 [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
88 [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
89 [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
90 [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
91 [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
92 [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 },
93 [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 },
94 [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 },
95 [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 },
96 [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 },
97 [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 },
98 [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 },
99 [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
100 [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
101 [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 },
102 [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
103 [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 },
104 [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 },
105
106 [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 },
107 [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 },
108 [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 },
109 [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
110 [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
111 [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
112 [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 },
113 [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 },
114 [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 },
115 [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 },
116 [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 },
117 [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 },
118 [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 },
119 [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 },
120 [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 },
121 [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
122 [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
123 [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 },
124
125 [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 },
126 [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 },
127 [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 },
128 [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 },
129 [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 },
130 [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 },
131 [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 },
132 [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 },
133 [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 },
134
135 [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
136 [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
137 [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
138 [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
139 [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
140 [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
141 [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
142 [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
143 [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
144};
145
146/* Movesets */
147bool standard_moveset[NMOVES] = {
148 [U] = true, [U2] = true, [U3] = true, [D] = true, [D2] = true, [D3] = true,
149 [R] = true, [R2] = true, [R3] = true, [L] = true, [L2] = true, [L3] = true,
150 [F] = true, [F2] = true, [F3] = true, [B] = true, [B2] = true, [B3] = true,
151};
152
153int epe_solved[] = {FR, FL, BL, BR};
154int eps_solved[] = {UL, UR, DL, DR};
155int epm_solved[] = {UF, UB, DF, DB};
156
157Cube blank_cube() {
158 Cube c = {0};
159 return c;
160}
161
162void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) {
163 /* ep is the hardest */
164 if (f.epose || f.eposs || f.eposm)
165 for (int i = 0; i < 12; i++) arr->ep[i] = -1;
166 if (f.epose) {
167 int epe[4], epose[12];
168 index_to_perm(cube.epose % factorial(4), 4, epe);
169 index_to_subset(cube.epose / factorial(4), 12, 4, epose);
170 for (int i = 0, ie = 0; i < 12; i++)
171 if (epose[i]) arr->ep[i] = epe_solved[epe[ie++]];
172 }
173 if (f.eposs) {
174 int eps[4], eposs[12];
175 index_to_perm(cube.eposs % factorial(4), 4, eps);
176 index_to_subset(cube.eposs / factorial(4), 12, 4, eposs);
177 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
178 for (int i = 0, is = 0; i < 12; i++)
179 if (eposs[i]) arr->ep[i] = eps_solved[eps[is++]];
180 }
181 if (f.eposm) {
182 int epm[4], eposm[12];
183 index_to_perm(cube.eposm % factorial(4), 4, epm);
184 index_to_subset(cube.eposm / factorial(4), 12, 4, eposm);
185 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
186 for (int i = 0, im = 0; i < 12; i++)
187 if (eposm[i]) arr->ep[i] = epm_solved[epm[im++]];
188 }
189
190 /* All the others */
191 if (f.eofb) int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
192 if (f.eorl) int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
193 if (f.eoud) int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
194 if (f.cp) index_to_perm( cube.cp, 8, arr->cp);
195 if (f.coud) int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
196 if (f.corl) int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
197 if (f.cofb) int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
198 if (f.cpos) index_to_perm( cube.cpos, 6, arr->cpos);
199}
200
201Cube arrays_to_cube(CubeArray arr, PieceFilter f) {
202 Cube ret = {0};
203
204 /* Again, ep is the hardest part */
205 if (f.epose) {
206 int epe[4], epose[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
207 for (int i = 0, ie = 0; i < 12; i++)
208 for (int j = 0; j < 4; j++)
209 if (arr.ep[i] == epe_solved[j])
210 { epe[ie++] = j; epose[i] = 1; }
211 ret.epose = factorial(4)*subset_to_index(epose,12,4)+perm_to_index(epe,4);
212 }
213 if (f.eposs) {
214 int eps[4], eposs[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
215 for (int i = 0, is = 0; i < 12; i++)
216 for (int j = 0; j < 4; j++)
217 if (arr.ep[i] == eps_solved[j])
218 { eps[is++] = j; eposs[i] = 1; }
219 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
220 ret.eposs = factorial(4)*subset_to_index(eposs,12,4)+perm_to_index(eps,4);
221 }
222 if (f.eposm) {
223 int epm[4], eposm[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
224 for (int i = 0, im = 0; i < 12; i++)
225 for (int j = 0; j < 4; j++)
226 if (arr.ep[i] == epm_solved[j])
227 { epm[im++] = j; eposm[i] = 1; }
228 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
229 ret.eposm = factorial(4)*subset_to_index(eposm,12,4)+perm_to_index(epm,4);
230 }
231 if (f.eofb) ret.eofb = digit_array_to_int(arr.eofb, 11, 2);
232 if (f.eorl) ret.eorl = digit_array_to_int(arr.eorl, 11, 2);
233 if (f.eoud) ret.eoud = digit_array_to_int(arr.eoud, 11, 2);
234 if (f.cp) ret.cp = perm_to_index( arr.cp, 8 );
235 if (f.coud) ret.coud = digit_array_to_int(arr.coud, 7, 3);
236 if (f.corl) ret.corl = digit_array_to_int(arr.corl, 7, 3);
237 if (f.cofb) ret.cofb = digit_array_to_int(arr.cofb, 7, 3);
238 if (f.cpos) ret.cpos = perm_to_index( arr.cpos, 6 );
239
240 return ret;
241}
242
243void move_cubearray(Move m, CubeArray *arr, PieceFilter f) {
244 if (f.epose || f.eposs || f.eposm)
245 apply_permutation(edge_cycle[m], arr->ep, 12);
246 if (f.eofb) {
247 apply_permutation(edge_cycle[m], arr->eofb, 12);
248 sum_arrays_mod(eofb_flipped[m], arr->eofb, 12, 2);
249 }
250 if (f.eofb) {
251 apply_permutation(edge_cycle[m], arr->eorl, 12);
252 sum_arrays_mod(eorl_flipped[m], arr->eorl, 12, 2);
253 }
254 if (f.eofb) {
255 apply_permutation(edge_cycle[m], arr->eoud, 12);
256 sum_arrays_mod(eoud_flipped[m], arr->eoud, 12, 2);
257 }
258 if (f.cp)
259 apply_permutation(corner_cycle[m], arr->cp, 8);
260 if (f.coud) {
261 apply_permutation(corner_cycle[m], arr->coud, 8);
262 sum_arrays_mod(coud_flipped[m], arr->coud, 8, 3);
263 }
264 if (f.corl) {
265 apply_permutation(corner_cycle[m], arr->corl, 8);
266 sum_arrays_mod(corl_flipped[m], arr->corl, 8, 3);
267 }
268 if (f.cofb) {
269 apply_permutation(corner_cycle[m], arr->cofb, 8);
270 sum_arrays_mod(cofb_flipped[m], arr->cofb, 8, 3);
271 }
272 if (f.cpos)
273 apply_permutation(center_cycle[m], arr->cpos, 6);
274}
275
276Cube move_via_array(Move m, Cube cube, PieceFilter f) {
277 CubeArray arr = {0};
278 cube_to_arrays(cube, &arr, f);
279 move_cubearray(m, &arr, f);
280 return arrays_to_cube(arr, f);
281}
282
283int copy_alg(NissMove *src, NissMove *dest) {
284 int i;
285 for (i = 0; src[i].m != NULLMOVE; i++)
286 dest[i] = src[i];
287 dest[i].m = NULLMOVE;
288 return i;
289}
290
291bool equal(Cube c1, Cube c2) {
292 return c1.eofb == c2.eofb && c1.epose == c2.epose &&
293 c1.eposs == c2.eposs && c1.eposm == c2.eposm &&
294 c1.coud == c2.coud && c1.cp == c2.cp &&
295 c1.cpos == c2.cpos;
296}
297
298bool solvable(Cube cube) {
299 /* Since we memorize orientation truncating the last digit, we only need to
300 * check that the permutations have the correct sign. */
301 CubeArray arr = {0};
302 cube_to_arrays(cube, &arr, fAll);
303 return (perm_sign(arr.ep,12) ^ perm_sign(arr.cpos,6)) == perm_sign(arr.cp,8);
304}
305
306bool is_solved(Cube cube, bool reorient) {
307 if (!reorient || !cube.cpos)
308 return !cube.eofb && !cube.coud && !cube.cp &&
309 !cube.epose && !cube.eposs && !cube.eposm;
310
311 bool ret = false;
312 for (int i = x; i <= z3; i++) {
313 ret = ret || is_solved(move_cube(i, cube), false);
314 for (int j = x; j <= z3; j++)
315 ret = ret || is_solved(move_cube(i, move_cube(j, cube)), false);
316 }
317 return ret;
318}
319
320void print_cube(Cube cube) {
321 CubeArray arr = {0};
322 cube_to_arrays(cube, &arr, fAll);
323
324 for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arr.ep[i]]);
325 printf("\n");
326 for (int i = 0; i < 12; i++) printf(" %c ", arr.eofb[i] + '0');
327 printf("\n");
328 for (int i = 0; i < 8; i++) printf("%s ", corner_string[arr.cp[i]]);
329 printf("\n");
330 for (int i = 0; i < 8; i++) printf(" %c ", arr.coud[i] + '0');
331 printf("\n");
332 for (int i = 0; i < 6; i++) printf(" %s ", center_string[arr.cpos[i]]);
333 printf("\n");
334}
335
336/* TODO: all strings start with space?? */
337void print_moves(NissMove *alg) {
338 bool niss = false;
339 for (int i = 0; alg[i].m != NULLMOVE; i++) {
340 char *fill = !niss && alg[i].inverse ? " (" :
341 (niss && !alg[i].inverse ? ") " : " ");
342 printf("%s%s", fill, move_string[alg[i].m]);
343 niss = alg[i].inverse;
344 }
345 printf("%s\n", niss ? ")" : "");
346}
347
348int read_moves(char *str, NissMove *alg, int n) {
349 bool niss = false;
350 int c = 0;
351
352 for (int i = 0; str[i] && c < n; i++) {
353 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
354 continue;
355
356 if (str[i] == '(' || str[i] == ')') {
357 if ((niss && str[i] == '(') || (!niss && str[i] == ')'))
358 return -1;
359 niss = !niss;
360 continue;
361 }
362
363 alg[c].inverse = niss; alg[c].m = NULLMOVE;
364 for (Move j = 0; j < NMOVES; j++) {
365 if (str[i] == move_string[j][0]) {
366 alg[c].m = j;
367 if (alg[c].m <= B && str[i+1]=='w') { alg[c].m += Uw - U; i++; }
368 if (str[i+1]=='2') { alg[c].m += 1; i++; }
369 else if (str[i+1]=='\'' || str[i+1]=='3') { alg[c].m += 2; i++; }
370 c++;
371 break;
372 }
373 }
374 }
375
376 alg[c].m = NULLMOVE;
377 return c;
378}
379
380/* Helper function for cleanup. alg must contain only basic moves, no 2 or '.
381 top and front describe an admissible orientation of the cube. */
382void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front) {
383 int c = 0, i = 0;
384 NissMove aux[n+3];
385 aux[0].m = NULLMOVE;
386
387 while (i < n && alg[i].m != NULLMOVE) {
388 int j = i;
389 while (j < n && commute[alg[i].m][alg[j].m]) j++;
390 Move base = 6*((alg[i].m-1)/6);
391 int t1 = 0, t2 = 0;
392 for (int k = i; k < j; k++)
393 if (alg[k].m == base+1) t1 = (t1+1)%4;
394 else t2 = (t2+1)%4;
395 if (t1) { aux[c].inverse = inv; aux[c].m = base+t1; c++; }
396 if (t2) { aux[c].inverse = inv; aux[c].m = base+t2+3; c++; }
397 i = j;
398 }
399 aux[c].m = NULLMOVE;
400
401 CubeArray q;
402 cube_to_arrays(blank_cube(), &q, cpos_only);
403 /* First we try to rotate in one move, then we try an x or y rotation
404 followed by a z rotation */
405 for (int r = x; r <= z3; r++) {
406 move_cubearray(r, &q, cpos_only);
407 if (q.cpos[F_center] == front && q.cpos[U_center] == top) {
408 aux[c].inverse = inv; aux[c].m = r;
409
410 aux[++c].m = NULLMOVE;
411 copy_alg(aux, alg);
412 return;
413 }
414 move_cubearray(inverse[r], &q, cpos_only);
415 }
416 for (int r = x; r <= y3; r++) {
417 move_cubearray(r, &q, cpos_only);
418 if (q.cpos[F_center] == front) {
419 aux[c].inverse = inv; aux[c++].m = r;
420 break;
421 }
422 move_cubearray(inverse[r], &q, cpos_only);
423 }
424 for (int r = z; r <= z3; r++) {
425 move_cubearray(r, &q, cpos_only);
426 if (q.cpos[U_center] == top) {
427 aux[c].inverse = inv; aux[c++].m = r;
428 break;
429 }
430 move_cubearray(inverse[r], &q, cpos_only);
431 }
432
433 aux[c].m = NULLMOVE;
434 copy_alg(aux, alg);
435}
436
437void cleanup(NissMove *alg, int n) {
438 int count_n = 0, count_i = 0, *count;
439 NissMove aux_n[n+1], aux_i[n+1], *aux;
440 CubeArray cube_n, cube_i, *cube;
441 cube_to_arrays(blank_cube(), &cube_n, cpos_only);
442 cube_to_arrays(blank_cube(), &cube_i, cpos_only);
443
444 for (int i = 0; count_n + count_i < n && alg[i].m != NULLMOVE; i++) {
445 if (alg[i].inverse) { count = &count_i; aux = aux_i; cube = &cube_i; }
446 else { count = &count_n; aux = aux_n; cube = &cube_n; }
447
448 for (int j = 0; equiv_moves[alg[i].m][j]; j++) {
449 Move m = equiv_moves[alg[i].m][j];
450 aux[*count].inverse = alg[i].inverse;
451 move_cubearray(m, cube, cpos_only);
452 if (m == U) aux[(*count)++].m = 3 * cube->cpos[0] + 1;
453 }
454 }
455
456 aux_n[count_n].m = NULLMOVE;
457 aux_i[count_i].m = NULLMOVE;
458 sort_cancel_rotate(aux_n, count_n, false, cube_n.cpos[0], cube_n.cpos[4]);
459 sort_cancel_rotate(aux_i, count_i, true, cube_i.cpos[0], cube_n.cpos[4]);
460 copy_alg(aux_n, alg);
461 copy_alg(aux_i, alg+count_n);
462}
463
464Cube inverse_cube(Cube cube) {
465 CubeArray arr = {0}, inv = {0};
466 cube_to_arrays(cube, &arr, fAll);
467
468 for (int i = 0; i < 12; i++) {
469 inv.ep[arr.ep[i]] = i;
470 inv.eofb[arr.ep[i]] = arr.eofb[i];
471 inv.eorl[arr.ep[i]] = arr.eorl[i];
472 inv.eoud[arr.ep[i]] = arr.eoud[i];
473 }
474 for (int i = 0; i < 8; i++) {
475 inv.cp[arr.cp[i]] = i;
476 inv.coud[arr.cp[i]] = arr.coud[i];
477 inv.corl[arr.cp[i]] = arr.corl[i];
478 inv.cofb[arr.cp[i]] = arr.cofb[i];
479 }
480 for (int i = 0; i < 6; i++)
481 inv.cpos[arr.cpos[i]] = i;
482
483 return arrays_to_cube(inv, fAll);
484}
485
486bool read_ttables_file() {
487 FILE *ttf;
488 if ((ttf = fopen("ttables", "rb")) != NULL) {
489 for (int m = 0; m < NMOVES; m++) {
490 fread(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
491 fread(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
492 fread(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
493 fread(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf);
494 fread(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf);
495 fread(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf);
496 fread(cp_ttable[m], sizeof(uint16_t), factorial8, ttf);
497 fread(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf);
498 fread(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf);
499 fread(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf);
500 fread(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf);
501 }
502 fclose(ttf);
503 return true;
504 } else return false;
505}
506
507bool write_ttables_file() {
508 FILE *ttf;
509 if ((ttf = fopen("ttables", "wb")) != NULL) {
510 for (int m = 0; m < NMOVES; m++) {
511 fwrite(epose_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
512 fwrite(eposs_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
513 fwrite(eposm_ttable[m], sizeof(uint16_t), factorial12/factorial8, ttf);
514 fwrite(eofb_ttable[m], sizeof(uint16_t), pow2to11, ttf);
515 fwrite(eorl_ttable[m], sizeof(uint16_t), pow2to11, ttf);
516 fwrite(eoud_ttable[m], sizeof(uint16_t), pow2to11, ttf);
517 fwrite(cp_ttable[m], sizeof(uint16_t), factorial8, ttf);
518 fwrite(coud_ttable[m], sizeof(uint16_t), pow3to7, ttf);
519 fwrite(corl_ttable[m], sizeof(uint16_t), pow3to7, ttf);
520 fwrite(cofb_ttable[m], sizeof(uint16_t), pow3to7, ttf);
521 fwrite(cpos_ttable[m], sizeof(uint16_t), factorial6, ttf);
522 }
523 fclose(ttf);
524 return true;
525 } else return false;
526}
527
528void init_ttables(bool read, bool write) {
529 /* Generate all move cycles and flips; I do this regardless */
530 for (int i = 0; i < NMOVES; i++) {
531 if (i == U || i == x || i == y)
532 continue;
533
534 CubeArray arr = {0};
535 cube_to_arrays(blank_cube(), &arr, fAll);
536 for (int j = 0; equiv_moves[i][j]; j++)
537 move_cubearray(equiv_moves[i][j], &arr, fAll);
538
539 intarrcopy(arr.ep, edge_cycle[i], 12);
540 intarrcopy(arr.eofb, eofb_flipped[i], 12);
541 intarrcopy(arr.eorl, eorl_flipped[i], 12);
542 intarrcopy(arr.eoud, eoud_flipped[i], 12);
543 intarrcopy(arr.cp, corner_cycle[i], 8);
544 intarrcopy(arr.coud, coud_flipped[i], 8);
545 intarrcopy(arr.corl, corl_flipped[i], 8);
546 intarrcopy(arr.cofb, cofb_flipped[i], 8);
547 intarrcopy(arr.cpos, center_cycle[i], 6);
548 }
549
550 if (read)
551 if (read_ttables_file())
552 return;
553
554 /* Initialize transition tables */
555 Cube c = {0};
556 PieceFilter fe = {.epose=true}, fs = {.eposs=true}, fm = {.eposm=true};
557 PieceFilter feo = { .eofb = true, .eorl = true, .eoud = true };
558 PieceFilter fcp = { .cp = true };
559 PieceFilter fco = { .cofb = true, .corl = true, .coud = true };
560 PieceFilter fcc = { .cpos = true };
561 for (int m = 0; m < NMOVES; m++) {
562 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
563 c.epose = i; epose_ttable[m][i] = move_via_array(m, c, fe).epose;
564 c.eposs = i; eposs_ttable[m][i] = move_via_array(m, c, fs).eposs;
565 c.eposm = i; eposm_ttable[m][i] = move_via_array(m, c, fm).eposm;
566 }
567 for (uint16_t i = 0; i < pow2to11; i++ ) {
568 c.eofb = i; eofb_ttable[m][i] = move_via_array(m, c, feo).eofb;
569 c.eorl = i; eorl_ttable[m][i] = move_via_array(m, c, feo).eorl;
570 c.eoud = i; eoud_ttable[m][i] = move_via_array(m, c, feo).eoud;
571 }
572 for (uint16_t i = 0; i < factorial8; i++) {
573 c.cp = i; cp_ttable[m][i] = move_via_array(m, c, fcp).cp;
574 }
575 for (uint16_t i = 0; i < pow3to7; i++) {
576 c.coud = i; coud_ttable[m][i] = move_via_array(m, c, fco).coud;
577 c.corl = i; corl_ttable[m][i] = move_via_array(m, c, fco).corl;
578 c.cofb = i; cofb_ttable[m][i] = move_via_array(m, c, fco).cofb;
579 }
580 for (uint16_t i = 0; i < factorial6; i++) {
581 c.cpos = i; cpos_ttable[m][i] = move_via_array(m, c, fcc).cpos;
582 }
583 }
584
585 if (write) write_ttables_file();
586}
587
588Cube move_cube(Move m, Cube cube) {
589 Cube moved = cube;
590
591 moved.epose = epose_ttable[m][cube.epose];
592 moved.eposs = eposs_ttable[m][cube.eposs];
593 moved.eposm = eposm_ttable[m][cube.eposm];
594 moved.eofb = eofb_ttable[m][cube.eofb];
595 moved.eorl = eorl_ttable[m][cube.eorl];
596 moved.eoud = eoud_ttable[m][cube.eoud];
597 moved.coud = coud_ttable[m][cube.coud];
598 moved.cofb = cofb_ttable[m][cube.cofb];
599 moved.corl = corl_ttable[m][cube.corl];
600 moved.cp = cp_ttable[m][cube.cp];
601 moved.cpos = cpos_ttable[m][cube.cpos];
602
603 return moved;
604}
605
606Cube compose(Cube c2, Cube c1) {
607 /* This is basically the same as the move_cubearray function above */
608 CubeArray arr2 = {0}, arr1 = {0};
609 cube_to_arrays(c2, &arr2, fAll);
610 cube_to_arrays(c1, &arr1, fAll);
611
612 apply_permutation(arr2.ep, arr1.ep, 12);
613 apply_permutation(arr2.ep, arr1.eofb, 12);
614 apply_permutation(arr2.ep, arr1.eorl, 12);
615 apply_permutation(arr2.ep, arr1.eoud, 12);
616 sum_arrays_mod(arr2.eofb, arr1.eofb, 12, 2);
617 sum_arrays_mod(arr2.eorl, arr1.eorl, 12, 2);
618 sum_arrays_mod(arr2.eoud, arr1.eoud, 12, 2);
619 apply_permutation(arr2.cp, arr1.cp, 8);
620 apply_permutation(arr2.cp, arr1.coud, 8);
621 apply_permutation(arr2.cp, arr1.corl, 8);
622 apply_permutation(arr2.cp, arr1.cofb, 8);
623 sum_arrays_mod(arr2.coud, arr1.coud, 8, 3);
624 sum_arrays_mod(arr2.corl, arr1.corl, 8, 3);
625 sum_arrays_mod(arr2.cofb, arr1.cofb, 8, 3);
626 apply_permutation(arr2.cpos, arr1.cpos, 6);
627
628 return arrays_to_cube(arr1, fAll);
629}
630
631Cube apply_alg(NissMove *alg, Cube cube) {
632 Cube ret = {0};
633 for (int i = 0; alg[i].m != NULLMOVE; i++)
634 if (alg[i].inverse)
635 ret = move_cube(alg[i].m, ret);
636 ret = compose(cube, inverse_cube(ret));
637
638 for (int i = 0; alg[i].m != NULLMOVE; i++)
639 if (!alg[i].inverse)
640 ret = move_cube(alg[i].m, ret);
641 return ret;
642}
643
644void init_aux_tables() {
645 /* Commute */
646 for (int i = 0; i < NMOVES; i++)
647 for (int j = 0; j < NMOVES; j++)
648 commute[i][j] = equal(move_cube(i, move_cube(j, blank_cube())),
649 move_cube(j, move_cube(i, blank_cube())));
650
651 /* Possible next (if the sequence i j k is valid) */
652 for (int i = 0; i < NMOVES; i++)
653 for (int j = 0; j < NMOVES; j++)
654 for (int k = 0; k < NMOVES; k++)
655 possible_next[i][j][k] =
656 (j == 0) ||
657 (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) &&
658 !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3)));
659
660 /* Inverse */
661 for (int i = 0; i < NMOVES; i++)
662 inverse[i] = i == 0 ? 0 : i + 2 - 2*((i-1)%3);
663}
664
diff --git a/old/2021-02-06/cube.h b/old/2021-02-06/cube.h
deleted file mode 100644
index bc4f14b..0000000
--- a/old/2021-02-06/cube.h
+++ /dev/null
@@ -1,60 +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 "utils.h"
8
9#define NMOVES (z3+1)
10
11/* Constants for moves and pieces */
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;
20typedef enum {U_center,D_center,R_center,L_center,F_center,B_center} Center;
21typedef enum { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge;
22typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner;
23
24/* An alg is an array of "NissMoves", which can be on normal or on inverse. */
25typedef struct { bool inverse; Move m; } NissMove;
26
27/* Representation of the cube */
28typedef struct {
29 uint16_t eofb, eorl, eoud, coud, cofb, corl,
30 epose, eposs, eposm, cp, cpos;
31} Cube;
32
33extern bool commute[NMOVES][NMOVES];
34extern bool possible_next[NMOVES][NMOVES][NMOVES];
35extern Move inverse[NMOVES];
36/* Movesets */
37extern bool standard_moveset[NMOVES];
38
39int copy_alg(NissMove *src, NissMove *dest); /*return number of moves copied */
40
41bool equal(Cube c1, Cube c2);
42bool is_solvable(Cube cube);
43/* reorient=true allows solved in wrong orientation */
44bool is_solved(Cube cube, bool reorient);
45void print_cube(Cube cube);
46void print_moves(NissMove *alg);
47int read_moves(char *str, NissMove *alg, int n); /* reads at most n moves */
48void cleanup(NissMove *src, int n); /* rewrites using basic moves, at most n */
49Cube blank_cube();
50Cube inverse_cube(Cube cube);
51Cube move_cube(Move m, Cube cube);
52Cube compose(Cube c2, Cube c1); /* Use c2 as an alg */
53Cube apply_alg(NissMove *alg, Cube cube);
54
55void init_ttables(bool read, bool write);
56void init_aux_tables();
57
58void init_dbg();
59
60#endif
diff --git a/old/2021-02-06/main.c b/old/2021-02-06/main.c
deleted file mode 100644
index c7be782..0000000
--- a/old/2021-02-06/main.c
+++ /dev/null
@@ -1,46 +0,0 @@
1#include <stdio.h>
2#include "cube.h"
3#include "solve.h"
4
5int main() {
6 init_ttables(true, true);
7 init_aux_tables();
8
9
10 char moves[100] = "MR U' B2 Bw F z xE2 M' x Dw' y Fw2 y2";
11 NissMove alg[100];
12 read_moves(moves, alg, 100);
13 Cube cube = apply_alg(alg, blank_cube());
14
15 /*f_eofb(cube);*/
16
17
18/* NissMove sol[MAXS][MAXM];*/
19 SolveData d = { .optimal_only = true, .available = standard_moveset,
20 .max_moves = 10,
21 .cleanup = true,
22 .max_solutions = 10,
23 .f = f_eofb };
24 read_moves("y", d.pre_rotation, 2);
25 int n = solve(cube, &d);
26 printf("%d solutions found:\n", n);
27 for (int i = 0; i < n; i++)
28 print_moves(d.solutions[i]);
29
30 NissMove a[5], b[5];
31 read_moves("R", a, 5);
32 read_moves("U", b, 5);
33 Cube c1 = apply_alg(a,blank_cube()), c2 = apply_alg(b,blank_cube());
34 print_cube(compose(c2,c1));
35 print_cube(compose(c1,c2));
36 /*print_cube(compose(c2,blank_cube()));*/
37
38 NissMove nm[10];
39 read_moves("y(y)RU", nm, 10);
40
41 print_moves(nm);
42 cleanup(nm, 10);
43 print_moves(nm);
44
45 return 0;
46}
diff --git a/old/2021-02-06/solve.c b/old/2021-02-06/solve.c
deleted file mode 100644
index f6274e9..0000000
--- a/old/2021-02-06/solve.c
+++ /dev/null
@@ -1,177 +0,0 @@
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 Cube rotated = apply_alg(sd->pre_rotation, blank_cube());
91 cube = apply_alg(inverse_cube(rotated), compose(cube, rotated));
92
93 uint64_t ret = 0;
94 for (int i=sd->min_moves; i<=sd->max_moves&&!(ret&&sd->optimal_only); i++) {
95 DfsData dd = { .d = i, .n = &ret };
96 solve_dfs(cube, sd, dd);
97 }
98
99 for (uint64_t i = 0; i < ret; i++) {
100 /* TODO: transform solutions with inverse of pre_rotation */
101 if (sd->cleanup)
102 cleanup(sd->solutions[i], sd->max_moves*3);
103 }
104
105 return ret;
106}
107
108void prune_dfs(Cube cube, PruneData *pd, DfsData dd) {
109 uint64_t ind = pd->index(cube);
110 if ((!ind || pd->ptable[ind]) && pd->ptable[ind] != dd.m)
111 return;
112 if (dd.m == dd.d) {
113 if (ind && !pd->ptable[ind]) {
114 pd->ptable[ind] = dd.m;
115 (*dd.n)++;
116 }
117 return;
118 }
119
120 for (int i = 0; i < NMOVES; i++) {
121 if (dd.m<20)
122 if (possible_next[dd.last2][dd.last1][i] && pd->available[i]) {
123 DfsData nn = { .m = dd.m+1, .d = dd.d, .n = dd.n,
124 .last1 = i, .last2 = dd.last1 };
125 prune_dfs(move_cube(i, cube), pd, nn);
126 }
127 }
128}
129
130void init_ptable(PruneData *pd, bool read, bool write) {
131 if (read) {
132 FILE *ptf;
133 if ((ptf = fopen(pd->fname, "rb")) != NULL) {
134 fread(pd->ptable, sizeof(uint8_t), pd->n, ptf);
135 fclose(ptf);
136 return;
137 }
138 }
139
140 /* TODO: for now it behaves always as if copressed = false */
141 for (uint64_t i = 0; i < pd->n; i++)
142 pd->ptable[i] = 0;
143
144 uint64_t s = 1;
145 for (int i = 1; i < pd->max_moves && s < pd->n; i++) {
146 DfsData dd = { .d = i, .n = &s };
147 prune_dfs(blank_cube(), pd, dd);
148 }
149
150 if (write) {
151 FILE *ptf;
152 if ((ptf = fopen(pd->fname, "wb")) != NULL) {
153 fwrite(pd->ptable, sizeof(uint8_t), pd->n, ptf);
154 fclose(ptf);
155 return;
156 }
157 }
158}
159
160/* Solving steps (and indexing functions) */
161
162uint64_t index_eofb(Cube cube) { return cube.eofb; }
163uint16_t f_eofb(Cube cube) {
164 static bool initialized_ptable;
165 static uint8_t pt_eofb[pow2to11];
166 if (!initialized_ptable) {
167 PruneData pd = {
168 .compressed = false, .available = standard_moveset, .max_moves = 13,
169 .ptable = pt_eofb, .n = pow2to11, .index = index_eofb,
170 .fname = "ptable_eofb"
171 };
172 init_ptable(&pd, false, true);
173 initialized_ptable = true;
174 }
175 return cube.eofb ? pt_eofb[cube.eofb] : 0;
176}
177
diff --git a/old/2021-02-06/solve.h b/old/2021-02-06/solve.h
deleted file mode 100644
index 6479e14..0000000
--- a/old/2021-02-06/solve.h
+++ /dev/null
@@ -1,55 +0,0 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include <stdlib.h>
5#include "cube.h"
6
7/* Maximum number of moves per solution and of solutions */
8#define MAXM 30
9#define MAXS 999
10
11/* Data for solving a step:
12 - can_niss is true niss can be used, false otherwise.
13 - optimal_only if true, dynamically updates max_moves so non-optimal
14 solutions are discarded.
15 - cleanup determines whether the cleaunup() function should be used on
16 the found solutions before returning.
17 - available[m] is true if the move m can be used, false otherwise.
18 - min_moves and max_moves are the minimum and maximum number of moves that
19 can be used.
20 - max_solution is the maximum number of solutions that can be returned.
21 - precondition can be used to check wheter the step can actually be applied
22 to the cube. If it returns false, solve() stops immediately returning -1.
23 - f must return 0 if and only if the step is solve, otherwise it must return
24 a lower bound for the number of moves required (without niss).
25 - sorted_moves[] can be used to specify in which order moves are tried
26 by the solving algorithm (for example if one wants to always try F' before
27 F). If sorted_moves[0] == NULLMOVE, the list is generated automatically.
28 It is advised to list first all the moves that actually influence the
29 solved state of the step (this is the default choice). This is in order to
30 avoid cases like B2 F for EO and to NISS only when it makes sense.
31 - start_moves [Currently unused, REMOVE]
32 are the moves that will be used as first moves of all
33 solutions. For example giving R' U' F (F' U R) will generate FMC scrambles
34 and y (y) will solve the step on another axis.
35 - pre_rotation are the rotations to apply before the scamble to solve
36 the step wrt a different orientation
37 - pre_rotation are the rotations to apply before the scamble to solve
38 the step wth respect to a different orientation.
39 - solutions[][] is the array where to store the found solutions. */
40typedef struct {
41 bool can_niss, optimal_only, cleanup, *available;
42 int min_moves, max_moves;
43 uint64_t max_solutions;
44 bool (*precondition)(Cube);
45 uint16_t (*f)(Cube);
46 Move sorted_moves[NMOVES];
47 NissMove pre_rotation[3], solutions[MAXS][MAXM];
48} SolveData;
49
50int solve(Cube cube, SolveData *data); /* Returns the number of solutions. */
51
52/* Steps */
53uint16_t f_eofb(Cube cube);
54
55#endif
diff --git a/old/2021-02-06/utils.c b/old/2021-02-06/utils.c
deleted file mode 100644
index 66de9ad..0000000
--- a/old/2021-02-06/utils.c
+++ /dev/null
@@ -1,197 +0,0 @@
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-06/utils.h b/old/2021-02-06/utils.h
deleted file mode 100644
index 4b6df8c..0000000
--- a/old/2021-02-06/utils.h
+++ /dev/null
@@ -1,70 +0,0 @@
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