aboutsummaryrefslogtreecommitdiff
path: root/old/2021-11-10-beforeremovingchecker/moves.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--old/2021-11-10-beforeremovingchecker/moves.c474
1 files changed, 474 insertions, 0 deletions
diff --git a/old/2021-11-10-beforeremovingchecker/moves.c b/old/2021-11-10-beforeremovingchecker/moves.c
new file mode 100644
index 0000000..5ba17ca
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/moves.c
@@ -0,0 +1,474 @@
1#include "moves.h"
2
3/* Local functions ***********************************************************/
4
5static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f);
6static bool read_mtables_file();
7static bool write_mtables_file();
8
9/* Tables and other data *****************************************************/
10
11/* Every move is translated to a an <U, x, y> alg before filling the
12 transition tables, see init_moves() */
13
14static int edge_cycle[NMOVES][12] =
15{
16 [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
17 [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
18 [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }
19};
20
21static int corner_cycle[NMOVES][8] =
22{
23 [U] = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR },
24 [x] = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
25 [y] = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL }
26};
27
28static int center_cycle[NMOVES][6] =
29{
30 [x] = { F_center, B_center, R_center, L_center, D_center, U_center },
31 [y] = { U_center, D_center, B_center, F_center, R_center, L_center }
32};
33
34static int eofb_flipped[NMOVES][12] = {
35 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
36 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
37};
38
39static int eorl_flipped[NMOVES][12] = {
40 [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
41 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
42};
43
44static int eoud_flipped[NMOVES][12] = {
45 [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
46 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
47 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
48};
49
50static int coud_flipped[NMOVES][8] = {
51 [x] = {
52 [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
53 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2
54 }
55};
56
57static int corl_flipped[NMOVES][8] = {
58 [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
59 [y] = {
60 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
61 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
62 }
63};
64
65static int cofb_flipped[NMOVES][8] = {
66 [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
67 [x] = {
68 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
69 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
70 },
71 [y] = {
72 [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1,
73 [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2
74 }
75};
76
77static char equiv_alg_string[100][NMOVES] = {
78 [NULLMOVE] = "",
79
80 [U] = " U ",
81 [U2] = " UU ",
82 [U3] = " UUU ",
83 [D] = " xx U xx ",
84 [D2] = " xx UU xx ",
85 [D3] = " xx UUU xx ",
86 [R] = " yx U xxxyyy ",
87 [R2] = " yx UU xxxyyy ",
88 [R3] = " yx UUU xxxyyy ",
89 [L] = " yyyx U xxxy ",
90 [L2] = " yyyx UU xxxy ",
91 [L3] = " yyyx UUU xxxy ",
92 [F] = " x U xxx ",
93 [F2] = " x UU xxx ",
94 [F3] = " x UUU xxx ",
95 [B] = " xxx U x ",
96 [B2] = " xxx UU x ",
97 [B3] = " xxx UUU x ",
98
99 [Uw] = " xx U xx y ",
100 [Uw2] = " xx UU xx yy ",
101 [Uw3] = " xx UUU xx yyy ",
102 [Dw] = " U yyy ",
103 [Dw2] = " UU yy ",
104 [Dw3] = " UUU y ",
105 [Rw] = " yyyx U xxxy x ",
106 [Rw2] = " yyyx UU xxxy xx ",
107 [Rw3] = " yyyx UUU xxxy xxx ",
108 [Lw] = " yx U xxxyyy xxx ",
109 [Lw2] = " yx UU xxxyyy xx ",
110 [Lw3] = " yx UUU xxxyyy x ",
111 [Fw] = " xxx U x yxxxyyy ",
112 [Fw2] = " xxx UU x yxxyyy ",
113 [Fw3] = " xxx UUU x yxyyy ",
114 [Bw] = " x U xxx yxyyy ",
115 [Bw2] = " x UU xxx yxxyyy ",
116 [Bw3] = " x UUU xxx yxxxyyy ",
117
118 [M] = " yx U xx UUU yxyyy ",
119 [M2] = " yx UU xx UU xxxy ",
120 [M3] = " yx UUU xx U yxxxy ",
121 [S] = " x UUU xx U yyyx ",
122 [S2] = " x UU xx UU yyx ",
123 [S3] = " x U xx UUU yx ",
124 [E] = " U xx UUU xxyyy ",
125 [E2] = " UU xx UU xxyy ",
126 [E3] = " UUU xx U xxy ",
127
128 [x] = " x ",
129 [x2] = " xx ",
130 [x3] = " xxx ",
131 [y] = " y ",
132 [y2] = " yy ",
133 [y3] = " yyy ",
134 [z] = " yyy x y ",
135 [z2] = " yy xx ",
136 [z3] = " y x yyy "
137};
138
139/* Transition tables, to be loaded up at the beginning */
140static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
141static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
142static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
143static int eofb_mtable[NMOVES][POW2TO11];
144static int eorl_mtable[NMOVES][POW2TO11];
145static int eoud_mtable[NMOVES][POW2TO11];
146static int cp_mtable[NMOVES][FACTORIAL8];
147static int coud_mtable[NMOVES][POW3TO7];
148static int cofb_mtable[NMOVES][POW3TO7];
149static int corl_mtable[NMOVES][POW3TO7];
150static int cpos_mtable[NMOVES][FACTORIAL6];
151
152
153/* Local functions implementation ********************************************/
154
155static Cube
156apply_move_cubearray(Move m, Cube cube, PieceFilter f)
157{
158 /*init_moves();*/
159
160 CubeArray m_arr = {
161 edge_cycle[m],
162 eofb_flipped[m],
163 eorl_flipped[m],
164 eoud_flipped[m],
165 corner_cycle[m],
166 coud_flipped[m],
167 corl_flipped[m],
168 cofb_flipped[m],
169 center_cycle[m]
170 };
171
172 return move_via_arrays(&m_arr, cube, f);
173}
174
175/* Public functions **********************************************************/
176
177Cube
178apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a)
179{
180 Cube ret = {0};
181 int i;
182
183 for (i = 0; i < alg->len; i++)
184 if (alg->inv[i])
185 ret = a ? apply_move(alg->move[i], ret) :
186 apply_move_cubearray(alg->move[i], ret, f);
187
188 ret = compose_filtered(c, inverse_cube(ret), f);
189
190 for (i = 0; i < alg->len; i++)
191 if (!alg->inv[i])
192 ret = a ? apply_move(alg->move[i], ret) :
193 apply_move_cubearray(alg->move[i], ret, f);
194
195 return ret;
196}
197
198Cube
199apply_alg(Alg *alg, Cube cube)
200{
201 return apply_alg_generic(alg, cube, pf_all, true);
202}
203
204Cube
205apply_move(Move m, Cube cube)
206{
207 /*init_moves();*/
208
209 return (Cube) {
210 .epose = epose_mtable[m][cube.epose],
211 .eposs = eposs_mtable[m][cube.eposs],
212 .eposm = eposm_mtable[m][cube.eposm],
213 .eofb = eofb_mtable[m][cube.eofb],
214 .eorl = eorl_mtable[m][cube.eorl],
215 .eoud = eoud_mtable[m][cube.eoud],
216 .coud = coud_mtable[m][cube.coud],
217 .cofb = cofb_mtable[m][cube.cofb],
218 .corl = corl_mtable[m][cube.corl],
219 .cp = cp_mtable[m][cube.cp],
220 .cpos = cpos_mtable[m][cube.cpos]
221 };
222}
223
224void
225init_moves() {
226 static bool initialized = false;
227 if (initialized)
228 return;
229 initialized = true;
230
231 Cube c;
232 CubeArray arrs;
233 int i;
234 unsigned int ui;
235 Move m;
236 Alg *equiv_alg[NMOVES];
237
238 for (i = 0; i < NMOVES; i++)
239 equiv_alg[i] = new_alg(equiv_alg_string[i]);
240
241 /* Generate all move cycles and flips; I do this regardless */
242 for (i = 0; i < NMOVES; i++) {
243 if (i == U || i == x || i == y)
244 continue;
245
246 c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false);
247
248 arrs = (CubeArray) {
249 edge_cycle[i],
250 eofb_flipped[i],
251 eorl_flipped[i],
252 eoud_flipped[i],
253 corner_cycle[i],
254 coud_flipped[i],
255 corl_flipped[i],
256 cofb_flipped[i],
257 center_cycle[i]
258 };
259 cube_to_arrays(c, &arrs, pf_all);
260 }
261
262 if (read_mtables_file())
263 return;
264
265 fprintf(stderr, "Cannot load %s, generating it\n", "mtables");
266
267 /* Initialize transition tables */
268 for (m = 0; m < NMOVES; m++) {
269 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
270 c = (Cube){ .epose = ui };
271 c = apply_move_cubearray(m, c, pf_e);
272 epose_mtable[m][ui] = c.epose;
273
274 c = (Cube){ .eposs = ui };
275 c = apply_move_cubearray(m, c, pf_s);
276 eposs_mtable[m][ui] = c.eposs;
277
278 c = (Cube){ .eposm = ui };
279 c = apply_move_cubearray(m, c, pf_m);
280 eposm_mtable[m][ui] = c.eposm;
281 }
282 for (ui = 0; ui < POW2TO11; ui++ ) {
283 c = (Cube){ .eofb = ui };
284 c = apply_move_cubearray(m, c, pf_eo);
285 eofb_mtable[m][ui] = c.eofb;
286
287 c = (Cube){ .eorl = ui };
288 c = apply_move_cubearray(m, c, pf_eo);
289 eorl_mtable[m][ui] = c.eorl;
290
291 c = (Cube){ .eoud = ui };
292 c = apply_move_cubearray(m, c, pf_eo);
293 eoud_mtable[m][ui] = c.eoud;
294 }
295 for (ui = 0; ui < POW3TO7; ui++) {
296 c = (Cube){ .coud = ui };
297 c = apply_move_cubearray(m, c, pf_co);
298 coud_mtable[m][ui] = c.coud;
299
300 c = (Cube){ .corl = ui };
301 c = apply_move_cubearray(m, c, pf_co);
302 corl_mtable[m][ui] = c.corl;
303
304 c = (Cube){ .cofb = ui };
305 c = apply_move_cubearray(m, c, pf_co);
306 cofb_mtable[m][ui] = c.cofb;
307 }
308 for (ui = 0; ui < FACTORIAL8; ui++) {
309 c = (Cube){ .cp = ui };
310 c = apply_move_cubearray(m, c, pf_cp);
311 cp_mtable[m][ui] = c.cp;
312 }
313 for (ui = 0; ui < FACTORIAL6; ui++) {
314 c = (Cube){ .cpos = ui };
315 c = apply_move_cubearray(m, c, pf_cpos);
316 cpos_mtable[m][ui] = c.cpos;
317 }
318 }
319
320 if (!write_mtables_file())
321 fprintf(stderr, "Error writing mtables\n");
322
323 for (i = 0; i < NMOVES; i++)
324 free_alg(equiv_alg[i]);
325}
326
327static bool
328read_mtables_file()
329{
330 init_env();
331
332 FILE *f;
333 char fname[strlen(tabledir)+20];
334 int m, b = sizeof(int);
335 bool r = true;
336
337 /* Table sizes, used for reading and writing files */
338 uint64_t me[11] = {
339 [0] = FACTORIAL12/FACTORIAL8,
340 [1] = FACTORIAL12/FACTORIAL8,
341 [2] = FACTORIAL12/FACTORIAL8,
342 [3] = POW2TO11,
343 [4] = POW2TO11,
344 [5] = POW2TO11,
345 [6] = FACTORIAL8,
346 [7] = POW3TO7,
347 [8] = POW3TO7,
348 [9] = POW3TO7,
349 [10] = FACTORIAL6
350 };
351
352 strcpy(fname, tabledir);
353 strcat(fname, "/mtables");
354
355 if ((f = fopen(fname, "rb")) == NULL)
356 return false;
357
358 for (m = 0; m < NMOVES; m++) {
359 r = r && fread(epose_mtable[m], b, me[0], f) == me[0];
360 r = r && fread(eposs_mtable[m], b, me[1], f) == me[1];
361 r = r && fread(eposm_mtable[m], b, me[2], f) == me[2];
362 r = r && fread(eofb_mtable[m], b, me[3], f) == me[3];
363 r = r && fread(eorl_mtable[m], b, me[4], f) == me[4];
364 r = r && fread(eoud_mtable[m], b, me[5], f) == me[5];
365 r = r && fread(cp_mtable[m], b, me[6], f) == me[6];
366 r = r && fread(coud_mtable[m], b, me[7], f) == me[7];
367 r = r && fread(corl_mtable[m], b, me[8], f) == me[8];
368 r = r && fread(cofb_mtable[m], b, me[9], f) == me[9];
369 r = r && fread(cpos_mtable[m], b, me[10], f) == me[10];
370 }
371
372 fclose(f);
373 return r;
374}
375
376static bool
377write_mtables_file()
378{
379 init_env();
380
381 FILE *f;
382 char fname[strlen(tabledir)+20];
383 int m, b = sizeof(int);
384 bool r = true;
385
386 /* Table sizes, used for reading and writing files */
387 uint64_t me[11] = {
388 [0] = FACTORIAL12/FACTORIAL8,
389 [1] = FACTORIAL12/FACTORIAL8,
390 [2] = FACTORIAL12/FACTORIAL8,
391 [3] = POW2TO11,
392 [4] = POW2TO11,
393 [5] = POW2TO11,
394 [6] = FACTORIAL8,
395 [7] = POW3TO7,
396 [8] = POW3TO7,
397 [9] = POW3TO7,
398 [10] = FACTORIAL6
399 };
400
401 strcpy(fname, tabledir);
402 strcat(fname, "/mtables");
403
404 if ((f = fopen(fname, "wb")) == NULL)
405 return false;
406
407 for (m = 0; m < NMOVES; m++) {
408 r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0];
409 r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1];
410 r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2];
411 r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3];
412 r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4];
413 r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5];
414 r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6];
415 r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7];
416 r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8];
417 r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9];
418 r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10];
419 }
420
421 fclose(f);
422 return r;
423}
424
425bool
426commute(Move m1, Move m2)
427{
428 static bool initialized = false;
429 static bool commute_aux[NMOVES][NMOVES];
430
431 if (!initialized) {
432 Cube c1, c2;
433 int i, j;
434
435 for (i = 0; i < NMOVES; i++) {
436 for (j = 0; j < NMOVES; j++) {
437 c1 = apply_move(i, apply_move(j, (Cube){0}));
438 c2 = apply_move(j, apply_move(i, (Cube){0}));
439 commute_aux[i][j] = equal(c1, c2) && i && j;
440 }
441 }
442
443 initialized = true;
444 }
445
446 return commute_aux[m1][m2];
447}
448
449bool
450possible_next(Move m1, Move m2, Move m3)
451{
452 static bool initialized = false;
453 static bool paux[NMOVES][NMOVES][NMOVES];
454
455 if (!initialized) {
456 int i, j, k;
457 bool p, q, c;
458
459 for (i = 0; i < NMOVES; i++) {
460 for (j = 0; j < NMOVES; j++) {
461 for (k = 0; k < NMOVES; k++) {
462 p = j && base_move(j) == base_move(k);
463 q = i && base_move(i) == base_move(k);
464 c = commute(i, j);
465 paux[i][j][k] = !(p || (c && q));
466 }
467 }
468 }
469
470 initialized = true;
471 }
472
473 return paux[m1][m2][m3];
474}

Generated with cgit - Back to sebastiano.tronto.net