aboutsummaryrefslogtreecommitdiff
path: root/old/2021-06-02-cleanedup
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano.tronto@gmail.com>2021-11-11 22:05:00 +0100
committerSebastiano Tronto <sebastiano.tronto@gmail.com>2021-11-11 22:05:00 +0100
commit4fb67201414169a2687f41c4056b2e284b4938cb (patch)
treea68246e3e21435229541f83f485ab41cfb2ba08a /old/2021-06-02-cleanedup
parent3568412f8f230774d0d11d7ed1c897424f95d3ef (diff)
downloadnissy-4fb67201414169a2687f41c4056b2e284b4938cb.tar.gz
nissy-4fb67201414169a2687f41c4056b2e284b4938cb.zip
Removed old files
Diffstat (limited to '')
-rw-r--r--old/2021-06-02-cleanedup/cube.c2010
-rw-r--r--old/2021-06-02-cleanedup/cube.h179
-rw-r--r--old/2021-06-02-cleanedup/main.c35
-rw-r--r--old/2021-06-02-cleanedup/steps.h22
4 files changed, 0 insertions, 2246 deletions
diff --git a/old/2021-06-02-cleanedup/cube.c b/old/2021-06-02-cleanedup/cube.c
deleted file mode 100644
index bb86143..0000000
--- a/old/2021-06-02-cleanedup/cube.c
+++ /dev/null
@@ -1,2010 +0,0 @@
1#include "cube.h"
2
3/* Constants and macros *****************************************************/
4
5#define pow2to11 2048
6#define pow2to12 4096
7#define pow3to7 2187
8#define pow3to8 6561
9#define pow12to4 20736
10#define factorial4 24
11#define factorial6 720
12#define factorial8 40320
13#define factorial12 479001600
14#define binom12on4 495
15#define binom8on4 70
16
17#define BASEALGLEN 50
18#define NMOVES (z3+1)
19#define NTRANS (mirror+1)
20#define NROTATIONS (NTRANS-1)
21
22#define min(a,b) (((a) < (b)) ? (a) : (b))
23#define max(a,b) (((a) > (b)) ? (a) : (b))
24
25/* Local types ***************************************************************/
26
27typedef struct cubearray CubeArray;
28typedef struct dfsdata DfsData;
29typedef struct piecefilter PieceFilter;
30
31struct
32cubearray
33{
34 int *ep;
35 int *eofb;
36 int *eorl;
37 int *eoud;
38 int *cp;
39 int *coud;
40 int *corl;
41 int *cofb;
42 int *cpos;
43};
44
45struct
46dfsdata
47{
48 int d;
49 int m;
50 bool niss;
51 Move last1;
52 Move last2;
53 AlgList *sols;
54 Alg current_alg;
55};
56
57struct
58piecefilter
59{
60 bool epose;
61 bool eposs;
62 bool eposm;
63 bool eofb;
64 bool eorl;
65 bool eoud;
66 bool cp;
67 bool coud;
68 bool cofb;
69 bool corl;
70 bool cpos;
71};
72
73/* Local functions **********************************************************/
74
75static Cube admissible_ep(Cube cube, PieceFilter f);
76static CubeArray * alloc_cubearray(CubeArray *arr, PieceFilter f);
77static void append_alg(AlgList *l, Alg alg);
78static void append_move(Alg alg, NissMove m);
79static Cube apply_alg_filtered(Alg alg, Cube cube, PieceFilter f);
80static void apply_permutation(int *perm, int *set, int n);
81static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f);
82static Cube arrays_to_cube(CubeArray arr, PieceFilter f);
83static int binomial(int n, int k);
84static Cube compose_filtered(Cube c2, Cube c1, PieceFilter f);
85static void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
86static int digit_array_to_int(int *a, int n, int b);
87static int edge_slice(Edge e); /* E=0, S=1, M=2 */
88static uint16_t epos_from_arrays(int *epos, int *ep);
89static int factorial(int n);
90static void free_alglist(AlgList *l);
91static void free_cubearray(CubeArray *arr, PieceFilter f);
92static void index_to_perm(int p, int n, int *r);
93static void index_to_subset(int s, int n, int k, int *r);
94static void init_auxtables();
95static void init_moves();
96static void init_trans();
97static void int_to_digit_array(int a, int b, int n, int *r);
98static void int_to_sum_zero_array(int x, int b, int n, int *a);
99static void intarrcopy(int *src, int *dst, int n);
100static int invert_digits(int a, int b, int n);
101static bool is_perm(int *a, int n);
102static bool is_subset(int *a, int n, int k);
103static Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter pf);
104static Move * moveset_to_movelist(bool *moveset, Step step);
105static AlgList * new_alglist();
106static int perm_sign(int a[], int n);
107static int perm_to_index(int *a, int n);
108static int powint(int a, int b);
109static bool read_rtables_file();
110static bool read_ttables_file();
111static bool realloc_alg(Alg alg, int n);
112static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f);
113static void solve_dfs(Cube c, Step s, SolveOptions opts, DfsData dd);
114static int subset_to_index(int *a, int n, int k);
115static void sum_arrays_mod(int *src, int *dst, int n, int m);
116static void swap(int *a, int *b);
117static bool write_rtables_file();
118static bool write_ttables_file();
119
120/* Aux tables ****************************************************************/
121
122bool commute[NMOVES][NMOVES];
123bool possible_next[NMOVES][NMOVES][NMOVES];
124Move inverse_move_aux[NMOVES];
125Trans inverse_trans_aux[NTRANS];
126
127/* Some utility constants ****************************************************/
128
129static int zero12[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
130static int zero8[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
131
132static int epe_solved[4] = { FR, FL, BL, BR };
133static int eps_solved[4] = { UL, UR, DL, DR };
134static int epm_solved[4] = { UF, UB, DF, DB };
135
136static int ep_mirror[12] = { UF, UR, UB, UL, DF, DR, DB, DL, FL, FR, BR, BL };
137static int cp_mirror[8] = { UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL };
138static int cpos_mirror[6] = {
139 U_center, D_center,
140 L_center, R_center,
141 F_center, B_center
142};
143
144static long unsigned int me[12] = {
145 factorial12/factorial8,
146 factorial12/factorial8,
147 factorial12/factorial8,
148 pow2to11,
149 pow2to11,
150 pow2to11,
151 factorial8,
152 pow3to7,
153 pow3to7,
154 pow3to7,
155 factorial6,
156 NMOVES
157};
158
159static PieceFilter pf_all = {
160 true, true, true, true, true, true, true, true, true, true, true
161};
162static PieceFilter pf_epcp = {
163 .epose = true, .eposs = true, .eposm = true, .cp = true
164};
165static PieceFilter pf_cpos = { .cpos = true };
166static PieceFilter pf_cp = { .cp = true };
167static PieceFilter pf_ep = { .epose = true, .eposs = true, .eposm = true };
168static PieceFilter pf_e = { .epose = true };
169static PieceFilter pf_s = { .eposs = true };
170static PieceFilter pf_m = { .eposm = true };
171static PieceFilter pf_eo = { .eofb = true, .eorl = true, .eoud = true };
172static PieceFilter pf_co = { .coud = true, .cofb = true, .corl = true };
173
174/* Strings for moves and pieces **********************************************/
175
176char move_string[NMOVES][5] = {
177 "-",
178 "U", "U2", "U\'", "D", "D2", "D\'",
179 "R", "R2", "R\'", "L", "L2", "L\'",
180 "F", "F2", "F\'", "B", "B2", "B\'",
181 "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'",
182 "Rw", "Rw2", "Rw\'", "Lw", "Lw2", "Lw\'",
183 "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'",
184 "M", "M2", "M\'",
185 "S", "S2", "S\'",
186 "E", "E2", "E\'",
187 "x", "x2", "x\'",
188 "y", "y2", "y\'",
189 "z", "z2", "z\'"
190};
191char edge_string[12][5] = {
192 "UF", "UL", "UB", "UR",
193 "DF", "DL", "DB", "DR",
194 "FR", "FL", "BL", "BR"
195};
196char corner_string[8][5] = {
197 "UFR", "UFL", "UBL", "UBR",
198 "DFR", "DFL", "DBL", "DBR"
199};
200char center_string[6][5] = {
201 "U", "D",
202 "R", "L",
203 "F", "B"
204};
205
206/* Transition tables for transformations and moves ***************************/
207
208uint16_t epose_rtable[NTRANS][factorial12/factorial8];
209uint16_t eposs_rtable[NTRANS][factorial12/factorial8];
210uint16_t eposm_rtable[NTRANS][factorial12/factorial8];
211uint16_t eo_rtable[NTRANS][pow2to11];
212uint16_t cp_rtable[NTRANS][factorial8];
213uint16_t co_rtable[NTRANS][pow3to7];
214uint16_t cpos_rtable[NTRANS][factorial6];
215Move moves_rtable[NTRANS][NMOVES];
216
217uint16_t epose_ttable[NMOVES][factorial12/factorial8];
218uint16_t eposs_ttable[NMOVES][factorial12/factorial8];
219uint16_t eposm_ttable[NMOVES][factorial12/factorial8];
220uint16_t eofb_ttable[NMOVES][pow2to11];
221uint16_t eorl_ttable[NMOVES][pow2to11];
222uint16_t eoud_ttable[NMOVES][pow2to11];
223uint16_t cp_ttable[NMOVES][factorial8];
224uint16_t coud_ttable[NMOVES][pow3to7];
225uint16_t cofb_ttable[NMOVES][pow3to7];
226uint16_t corl_ttable[NMOVES][pow3to7];
227uint16_t cpos_ttable[NMOVES][factorial6];
228
229/* Used to compute the full transition tables for moves and transformations **/
230
231int epose_source[NTRANS]; /* 0 = epose, 1 = eposs, 2 = eposm */
232int eposs_source[NTRANS];
233int eposm_source[NTRANS];
234int eofb_source[NTRANS]; /* 0 = eoud, 1 = eorl, 2 = eofb */
235int eorl_source[NTRANS];
236int eoud_source[NTRANS];
237int coud_source[NTRANS]; /* 0 = coud, 1 = corl, 2 = cofb */
238int cofb_source[NTRANS];
239int corl_source[NTRANS];
240
241NissMove rotation_niss[NTRANS][6];
242NissMove rotation_algs[NROTATIONS][3] = {
243 { { .m = NULLMOVE }, { .m = NULLMOVE }, { .m = NULLMOVE } },
244 { { .m = y }, { .m = NULLMOVE }, { .m = NULLMOVE } },
245 { { .m = y2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
246 { { .m = y3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
247 { { .m = z2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
248 { { .m = y }, { .m = z2 }, { .m = NULLMOVE } },
249 { { .m = x2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
250 { { .m = y3 }, { .m = z2 }, { .m = NULLMOVE } },
251 { { .m = z3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
252 { { .m = z3 }, { .m = y }, { .m = NULLMOVE } },
253 { { .m = z3 }, { .m = y2 }, { .m = NULLMOVE } },
254 { { .m = z3 }, { .m = y3 }, { .m = NULLMOVE } },
255 { { .m = z }, { .m = NULLMOVE }, { .m = NULLMOVE } },
256 { { .m = z }, { .m = y3 }, { .m = NULLMOVE } },
257 { { .m = z }, { .m = y2 }, { .m = NULLMOVE } },
258 { { .m = z }, { .m = y }, { .m = NULLMOVE } },
259 { { .m = x }, { .m = y2 }, { .m = NULLMOVE } },
260 { { .m = x }, { .m = y }, { .m = NULLMOVE } },
261 { { .m = x }, { .m = NULLMOVE }, { .m = NULLMOVE } },
262 { { .m = x }, { .m = y3 }, { .m = NULLMOVE } },
263 { { .m = x3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
264 { { .m = x3 }, { .m = y }, { .m = NULLMOVE } },
265 { { .m = x3 }, { .m = y2 }, { .m = NULLMOVE } },
266 { { .m = x3 }, { .m = y3 }, { .m = NULLMOVE } },
267};
268
269/* For each type of pieces only the effects of U, x and y are described */
270int edge_cycle[NMOVES][12] = {
271 [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
272 [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
273 [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }
274};
275int eofb_flipped[NMOVES][12] = {
276 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
277 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
278};
279int eorl_flipped[NMOVES][12] = {
280 [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
281 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
282};
283int eoud_flipped[NMOVES][12] = {
284 [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
285 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
286 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
287};
288int corner_cycle[NMOVES][8] = {
289 [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR},
290 [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR},
291 [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL}
292};
293int coud_flipped[NMOVES][8] = {
294 [x] = {
295 [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
296 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2
297 }
298};
299int corl_flipped[NMOVES][8] = {
300 [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
301 [y] = {
302 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
303 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
304 }
305};
306int cofb_flipped[NMOVES][8] = {
307 [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
308 [x] = {
309 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
310 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
311 },
312 [y] = {
313 [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1,
314 [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2
315 }
316};
317int center_cycle[NMOVES][6] = {
318 [x] = { F_center, B_center, R_center, L_center, D_center, U_center },
319 [y] = { U_center, D_center, B_center, F_center, R_center, L_center }
320};
321
322/* Each move is reduced to a combination of U, x and y using this table */
323Move equiv_moves[NMOVES][14] = {
324 [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
325 [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
326 [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
327 [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
328 [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
329 [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 },
330 [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 },
331 [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 },
332 [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 },
333 [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 },
334 [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 },
335 [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 },
336 [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
337 [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
338 [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 },
339 [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
340 [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 },
341 [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 },
342
343 [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 },
344 [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 },
345 [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 },
346 [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
347 [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
348 [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
349 [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 },
350 [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 },
351 [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 },
352 [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 },
353 [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 },
354 [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 },
355 [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 },
356 [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 },
357 [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 },
358 [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
359 [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
360 [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 },
361
362 [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 },
363 [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 },
364 [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 },
365 [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 },
366 [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 },
367 [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 },
368 [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 },
369 [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 },
370 [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 },
371
372 [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
373 [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
374 [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
375 [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
376 [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
377 [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
378 [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
379 [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
380 [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
381};
382
383/* Local functions implementation ********************************************/
384
385static Cube
386admissible_ep(Cube cube, PieceFilter f)
387{
388 CubeArray arr;
389 Cube ret;
390 bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
391 int i, j;
392
393 alloc_cubearray(&arr, f);
394 cube_to_arrays(cube, &arr, f);
395
396 for (i = 0; i < 12; i++)
397 if (arr.ep[i] != -1)
398 used[arr.ep[i]] = true;
399
400 for (i = 0, j = 0; i < 12; i++) {
401 for ( ; j < 11 && used[j]; j++);
402 if (arr.ep[i] == -1)
403 arr.ep[i] = j++;
404 }
405
406 ret = arrays_to_cube(arr, pf_ep);
407 free_cubearray(&arr, f);
408
409 return ret;
410}
411
412static CubeArray *
413alloc_cubearray(CubeArray *arr, PieceFilter f)
414{
415 if (f.epose || f.eposs || f.eposm)
416 arr->ep = malloc(12 * sizeof(int));
417 if (f.eofb)
418 arr->eofb = malloc(12 * sizeof(int));
419 if (f.eorl)
420 arr->eorl = malloc(12 * sizeof(int));
421 if (f.eoud)
422 arr->eoud = malloc(12 * sizeof(int));
423 if (f.cp)
424 arr->cp = malloc(8 * sizeof(int));
425 if (f.coud)
426 arr->coud = malloc(8 * sizeof(int));
427 if (f.corl)
428 arr->corl = malloc(8 * sizeof(int));
429 if (f.cofb)
430 arr->cofb = malloc(8 * sizeof(int));
431 if (f.cpos)
432 arr->cpos = malloc(6 * sizeof(int));
433
434 return arr;
435}
436
437static void
438append_alg(AlgList *l, Alg alg)
439{
440 AlgListNode *node = malloc(sizeof(AlgListNode));
441
442 node->alg = new_alg("");
443 copy_alg(alg, node->alg);
444 node->next = NULL;
445
446 if (++l->len == 1)
447 l->first = node;
448 else
449 l->last->next = node;
450 l->last = node;
451}
452
453static void
454append_move(Alg alg, NissMove m)
455{
456 int n = len(alg);
457
458 if (!realloc_alg(alg, n))
459 return;
460
461 alg[n] = m;
462 alg[n+1] = (NissMove) { .m = NULLMOVE };
463}
464
465static Cube
466apply_alg_filtered(Alg alg, Cube cube, PieceFilter f)
467{
468 Cube ret = {0};
469 int i;
470
471 for (i = 0; alg[i].m != NULLMOVE; i++)
472 if (alg[i].inverse)
473 ret = apply_move(alg[i].m, ret);
474
475 ret = compose_filtered(cube, inverse_cube(ret), f);
476
477 for (i = 0; alg[i].m != NULLMOVE; i++)
478 if (!alg[i].inverse)
479 ret = apply_move(alg[i].m, ret);
480
481 return ret;
482}
483
484static void
485apply_permutation(int *perm, int *set, int n)
486{
487 int *aux = malloc(n * sizeof(int));
488 int i;
489
490 if (!is_perm(perm, n))
491 return;
492
493 for (i = 0; i < n; i++)
494 aux[i] = set[perm[i]];
495
496 intarrcopy(aux, set, n);
497 free(aux);
498}
499
500static Cube
501apply_move_cubearray(Move m, Cube cube, PieceFilter f)
502{
503 CubeArray m_arr = {
504 edge_cycle[m],
505 eofb_flipped[m],
506 eorl_flipped[m],
507 eoud_flipped[m],
508 corner_cycle[m],
509 coud_flipped[m],
510 corl_flipped[m],
511 cofb_flipped[m],
512 center_cycle[m]
513 };
514
515 return move_via_arrays(m_arr, cube, f);
516}
517
518static Cube
519arrays_to_cube(CubeArray arr, PieceFilter f)
520{
521 Cube ret = {0};
522 int epose[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
523 int eposs[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
524 int eposm[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
525 int epe[4], eps[4], epm[4];
526 int i, ie, is, im, j;
527
528 /* Again, ep is the hardest part */
529 if (f.epose) {
530 for (i = 0, ie = 0; i < 12; i++) {
531 for (j = 0; j < 4; j++) {
532 if (arr.ep[i] == epe_solved[j]) {
533 epe[ie++] = j;
534 epose[i] = 1;
535 }
536 }
537 }
538 ret.epose = epos_from_arrays(epose, epe);
539 }
540
541 if (f.eposs) {
542 for (i = 0, is = 0; i < 12; i++) {
543 for (j = 0; j < 4; j++) {
544 if (arr.ep[i] == eps_solved[j]) {
545 eps[is++] = j;
546 eposs[i] = 1;
547 }
548 }
549 }
550 for (i = 0; i < 4; i++)
551 swap(&eposs[eps_solved[i]], &eposs[i+8]);
552 ret.eposs = epos_from_arrays(eposs, eps);
553 }
554
555 if (f.eposm) {
556 for (i = 0, im = 0; i < 12; i++) {
557 for (j = 0; j < 4; j++) {
558 if (arr.ep[i] == epm_solved[j]) {
559 epm[im++] = j;
560 eposm[i] = 1;
561 }
562 }
563 }
564 for (i = 0; i < 4; i++)
565 swap(&eposm[epm_solved[i]], &eposm[i+8]);
566 ret.eposm = epos_from_arrays(eposm, epm);
567 }
568
569 if (f.eofb)
570 ret.eofb = digit_array_to_int(arr.eofb, 11, 2);
571 if (f.eorl)
572 ret.eorl = digit_array_to_int(arr.eorl, 11, 2);
573 if (f.eoud)
574 ret.eoud = digit_array_to_int(arr.eoud, 11, 2);
575 if (f.cp)
576 ret.cp = perm_to_index(arr.cp, 8);
577 if (f.coud)
578 ret.coud = digit_array_to_int(arr.coud, 7, 3);
579 if (f.corl)
580 ret.corl = digit_array_to_int(arr.corl, 7, 3);
581 if (f.cofb)
582 ret.cofb = digit_array_to_int(arr.cofb, 7, 3);
583 if (f.cpos)
584 ret.cpos = perm_to_index(arr.cpos, 6);
585
586 return ret;
587}
588
589static int
590binomial(int n, int k)
591{
592 if (n < 0 || k < 0 || k > n)
593 return 0;
594
595 return factorial(n) / (factorial(k) * factorial(n-k));
596}
597
598static Cube
599compose_filtered(Cube c2, Cube c1, PieceFilter f)
600{
601 CubeArray arr;
602 Cube ret;
603
604 alloc_cubearray(&arr, f);
605 cube_to_arrays(c2, &arr, f);
606 ret = move_via_arrays(arr, c1, f);
607 free_cubearray(&arr, f);
608
609 return ret;
610}
611
612static void
613cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f)
614{
615 int epose[12], eposs[12], eposm[12];
616 int epe[4], eps[4], epm[4];
617 int i, ie, is, im;
618
619 /* ep is the hardest */
620 if (f.epose || f.eposs || f.eposm)
621 for (i = 0; i < 12; i++)
622 arr->ep[i] = -1;
623
624 if (f.epose) {
625 index_to_perm(cube.epose % factorial(4), 4, epe);
626 index_to_subset(cube.epose / factorial(4), 12, 4, epose);
627 for (i = 0, ie = 0; i < 12; i++)
628 if (epose[i])
629 arr->ep[i] = epe_solved[epe[ie++]];
630 }
631
632 if (f.eposs) {
633 index_to_perm(cube.eposs % factorial(4), 4, eps);
634 index_to_subset(cube.eposs / factorial(4), 12, 4, eposs);
635 for (i = 0; i < 4; i++)
636 swap(&eposs[eps_solved[i]], &eposs[i+8]);
637 for (i = 0, is = 0; i < 12; i++)
638 if (eposs[i])
639 arr->ep[i] = eps_solved[eps[is++]];
640 }
641
642 if (f.eposm) {
643 index_to_perm(cube.eposm % factorial(4), 4, epm);
644 index_to_subset(cube.eposm / factorial(4), 12, 4, eposm);
645 for (i = 0; i < 4; i++)
646 swap(&eposm[epm_solved[i]], &eposm[i+8]);
647 for (i = 0, im = 0; i < 12; i++)
648 if (eposm[i])
649 arr->ep[i] = epm_solved[epm[im++]];
650 }
651
652 /* All the others */
653 if (f.eofb)
654 int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
655 if (f.eorl)
656 int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
657 if (f.eoud)
658 int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
659 if (f.cp)
660 index_to_perm(cube.cp, 8, arr->cp);
661 if (f.coud)
662 int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
663 if (f.corl)
664 int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
665 if (f.cofb)
666 int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
667 if (f.cpos)
668 index_to_perm(cube.cpos, 6, arr->cpos);
669}
670
671static int
672digit_array_to_int(int *a, int n, int b)
673{
674 int i, ret = 0, p = 1;
675
676 for (i = 0; i < n; i++, p *= b)
677 ret += a[i] * p;
678
679 return ret;
680}
681
682static int
683edge_slice(Edge e) {
684 if (e == FR || e == FL || e == BL || e == BR)
685 return 0;
686 if (e == UR || e == UL || e == DR || e == DL)
687 return 1;
688
689 return 2;
690}
691
692static uint16_t
693epos_from_arrays(int *epos, int *ep)
694{
695 return factorial4 * subset_to_index(epos,12,4) + perm_to_index(ep,4);
696}
697
698static int
699factorial(int n)
700{
701 int i, ret = 1;
702
703 if (n < 0)
704 return 0;
705
706 for (i = 1; i <= n; i++)
707 ret *= i;
708
709 return ret;
710}
711
712static void
713free_alglist(AlgList *l)
714{
715 AlgListNode *aux, *i = l->first;
716
717 while (i != NULL) {
718 aux = i->next;
719 free(i);
720 i = aux;
721 }
722 free(l);
723
724 return;
725}
726
727static void
728free_cubearray(CubeArray *arr, PieceFilter f)
729{
730 if (f.epose || f.eposs || f.eposm)
731 free(arr->ep);
732 if (f.eofb)
733 free(arr->eofb);
734 if (f.eorl)
735 free(arr->eorl);
736 if (f.eoud)
737 free(arr->eoud);
738 if (f.cp)
739 free(arr->cp);
740 if (f.coud)
741 free(arr->coud);
742 if (f.corl)
743 free(arr->corl);
744 if (f.cofb)
745 free(arr->cofb);
746 if (f.cpos)
747 free(arr->cpos);
748}
749
750static void
751index_to_perm(int p, int n, int *r)
752{
753 int *a = malloc(n * sizeof(int));
754 int i, j, c;
755
756 for (i = 0; i < n; i++)
757 a[i] = 0;
758
759 if (p < 0 || p >= factorial(n))
760 for (i = 0; i < n; i++)
761 r[i] = -1;
762
763 for (i = 0; i < n; i++) {
764 c = 0;
765 j = 0;
766 while (c <= p / factorial(n-i-1))
767 c += a[j++] ? 0 : 1;
768 r[i] = j-1;
769 a[j-1] = 1;
770 p %= factorial(n-i-1);
771 }
772
773 free(a);
774}
775
776static void
777index_to_subset(int s, int n, int k, int *r)
778{
779 int i, j, v;
780
781 if (s < 0 || s >= binomial(n, k)) {
782 for (i = 0; i < n; i++)
783 r[i] = -1;
784 return;
785 }
786
787 for (i = 0; i < n; i++) {
788 if (k == n-i) {
789 for (j = i; j < n; j++)
790 r[j] = 1;
791 return;
792 }
793
794 if (k == 0) {
795 for (j = i; j < n; j++)
796 r[j] = 0;
797 return;
798 }
799
800 v = binomial(n-i-1, k);
801 if (s >= v) {
802 r[i] = 1;
803 k--;
804 s -= v;
805 } else {
806 r[i] = 0;
807 }
808 }
809}
810
811static void
812init_auxtables()
813{
814 Cube c1, c2;
815 int i, j, k;
816 bool cij, p1, p2;
817
818 for (i = 0; i < NMOVES; i++) {
819 for (j = 0; j < NMOVES; j++) {
820 c1 = apply_move(i, apply_move(j, (Cube){0}));
821 c2 = apply_move(j, apply_move(i, (Cube){0}));
822 commute[i][j] = equal(c1, c2);
823 }
824 }
825
826 for (i = 0; i < NMOVES; i++) {
827 for (j = 0; j < NMOVES; j++) {
828 for (k = 0; k < NMOVES; k++) {
829 p1 = j && (j-(j-1)%3) == (k-(k-1)%3);
830 p2 = i && (i-(i-1)%3) == (k-(k-1)%3);
831 cij = commute[i][j];
832 possible_next[i][j][k] = !(p1 || (cij && p2));
833 }
834 }
835 }
836
837 for (i = 0; i < NMOVES; i++)
838 inverse_move_aux[i] =
839 i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3);
840
841 /* Is there a more elegant way? */
842 inverse_trans_aux[uf] = uf;
843 inverse_trans_aux[ur] = ul;
844 inverse_trans_aux[ul] = ur;
845 inverse_trans_aux[ub] = ub;
846
847 inverse_trans_aux[df] = df;
848 inverse_trans_aux[dr] = dr;
849 inverse_trans_aux[dl] = dl;
850 inverse_trans_aux[db] = db;
851
852 inverse_trans_aux[rf] = lf;
853 inverse_trans_aux[rd] = bl;
854 inverse_trans_aux[rb] = rb;
855 inverse_trans_aux[ru] = fr;
856
857 inverse_trans_aux[lf] = rf;
858 inverse_trans_aux[ld] = br;
859 inverse_trans_aux[lb] = lb;
860 inverse_trans_aux[lu] = fl;
861
862 inverse_trans_aux[fu] = fu;
863 inverse_trans_aux[fr] = ru;
864 inverse_trans_aux[fd] = bu;
865 inverse_trans_aux[fl] = lu;
866
867 inverse_trans_aux[bu] = fd;
868 inverse_trans_aux[br] = ld;
869 inverse_trans_aux[bd] = bd;
870 inverse_trans_aux[bl] = rd;
871
872 inverse_trans_aux[mirror] = mirror;
873}
874
875static void
876init_moves() {
877 Cube c;
878 CubeArray arrs;
879 int i, j;
880 uint16_t ui;
881 Move m;
882
883 /* Generate all move cycles and flips; I do this regardless */
884 for (i = 0; i < NMOVES; i++) {
885 if (i == U || i == x || i == y)
886 continue;
887
888 c = (Cube){0};
889 for (j = 0; equiv_moves[i][j]; j++)
890 c = apply_move_cubearray(equiv_moves[i][j], c, pf_all);
891
892 arrs = (CubeArray){
893 edge_cycle[i],
894 eofb_flipped[i],
895 eorl_flipped[i],
896 eoud_flipped[i],
897 corner_cycle[i],
898 coud_flipped[i],
899 corl_flipped[i],
900 cofb_flipped[i],
901 center_cycle[i]
902 };
903 cube_to_arrays(c, &arrs, pf_all);
904 }
905
906 if (read_ttables_file())
907 return;
908
909 fprintf(stderr, "ttables not found, generating them.\n");
910
911 /* Initialize transition tables */
912 for (m = 0; m < NMOVES; m++) {
913 for (ui = 0; ui < factorial12/factorial8; ui++) {
914 c = (Cube){ .epose = ui };
915 c = apply_move_cubearray(m, c, pf_e);
916 epose_ttable[m][ui] = c.epose;
917
918 c = (Cube){ .eposs = ui };
919 c = apply_move_cubearray(m, c, pf_s);
920 eposs_ttable[m][ui] = c.eposs;
921
922 c = (Cube){ .eposm = ui };
923 c = apply_move_cubearray(m, c, pf_m);
924 eposm_ttable[m][ui] = c.eposm;
925 }
926 for (ui = 0; ui < pow2to11; ui++ ) {
927 c = (Cube){ .eofb = ui };
928 c = apply_move_cubearray(m, c, pf_eo);
929 eofb_ttable[m][ui] = c.eofb;
930
931 c = (Cube){ .eorl = ui };
932 c = apply_move_cubearray(m, c, pf_eo);
933 eorl_ttable[m][ui] = c.eorl;
934
935 c = (Cube){ .eoud = ui };
936 c = apply_move_cubearray(m, c, pf_eo);
937 eoud_ttable[m][ui] = c.eoud;
938 }
939 for (ui = 0; ui < pow3to7; ui++) {
940 c = (Cube){ .coud = ui };
941 c = apply_move_cubearray(m, c, pf_co);
942 coud_ttable[m][ui] = c.coud;
943
944 c = (Cube){ .corl = ui };
945 c = apply_move_cubearray(m, c, pf_co);
946 corl_ttable[m][ui] = c.corl;
947
948 c = (Cube){ .cofb = ui };
949 c = apply_move_cubearray(m, c, pf_co);
950 cofb_ttable[m][ui] = c.cofb;
951 }
952 for (ui = 0; ui < factorial8; ui++) {
953 c = (Cube){ .cp = ui };
954 c = apply_move_cubearray(m, c, pf_cp);
955 cp_ttable[m][ui] = c.cp;
956 }
957 for (ui = 0; ui < factorial6; ui++) {
958 c = (Cube){ .cpos = ui };
959 c = apply_move_cubearray(m, c, pf_cpos);
960 cpos_ttable[m][ui] = c.cpos;
961 }
962 }
963
964 if (!write_ttables_file())
965 fprintf(stderr, "Error writing ttables\n");
966}
967
968static void
969init_trans() {
970 Cube aux, cube, c[3];
971 CubeArray epcp;
972 int eparr[12], eoarr[12];
973 int cparr[8], coarr[8];
974 int i;
975 bool b1, b2, b3;
976 uint16_t ui;
977 Move mi, move;
978 Trans r, m;
979
980 /* Compute sources */
981 for (i = 0; i < NTRANS; i++) {
982 if (i == mirror)
983 cube = (Cube){0};
984 else
985 cube = apply_alg(rotation_algs[i], (Cube){0});
986
987 epose_source[i] = edge_slice(edge_at(cube, FR));
988 eposs_source[i] = edge_slice(edge_at(cube, UR));
989 eposm_source[i] = edge_slice(edge_at(cube, UF));
990 eofb_source[i] = center_at(cube, F_center)/2;
991 eorl_source[i] = center_at(cube, R_center)/2;
992 eoud_source[i] = center_at(cube, U_center)/2;
993 coud_source[i] = center_at(cube, U_center)/2;
994 cofb_source[i] = center_at(cube, F_center)/2;
995 corl_source[i] = center_at(cube, R_center)/2;
996 }
997
998 /* Compute rotation_niss array, necessary for rotate_via_compose */
999 for (r = 0; r != mirror; r++) {
1000 concat(rotation_algs[r], rotation_algs[r], rotation_niss[r]);
1001 for (i = len(rotation_algs[r]); rotation_niss[r][i].m; i++)
1002 rotation_niss[r][i].inverse = true;
1003 }
1004
1005 if (read_rtables_file())
1006 return;
1007
1008 fprintf(stderr, "rtables not found, generating them.\n");
1009
1010 /* Initialize tables */
1011 for (m = 0; m < NTRANS; m++) {
1012 if (m == mirror) {
1013 intarrcopy(ep_mirror, eparr, 12);
1014 intarrcopy(cp_mirror, cparr, 8);
1015 } else {
1016 epcp = (CubeArray){ .ep = eparr, .cp = cparr };
1017 cube = apply_alg(rotation_algs[m], (Cube){0});
1018 cube_to_arrays(cube, &epcp, pf_epcp);
1019 }
1020
1021 for (ui = 0; ui < factorial12/factorial8; ui++) {
1022 c[0] = admissible_ep((Cube){ .epose = ui }, pf_e);
1023 c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s);
1024 c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m);
1025
1026 cube = rotate_via_compose(m,c[epose_source[m]],pf_ep);
1027 epose_rtable[m][ui] = cube.epose;
1028
1029 cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep);
1030 eposs_rtable[m][ui] = cube.eposs;
1031
1032 cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep);
1033 eposm_rtable[m][ui] = cube.eposm;
1034 }
1035 for (ui = 0; ui < pow2to11; ui++ ) {
1036 int_to_sum_zero_array(ui, 2, 12, eoarr);
1037 apply_permutation(eparr, eoarr, 12);
1038 eo_rtable[m][ui] = digit_array_to_int(eoarr, 11, 2);
1039 }
1040 for (ui = 0; ui < pow3to7; ui++) {
1041 int_to_sum_zero_array(ui, 3, 8, coarr);
1042 apply_permutation(cparr, coarr, 8);
1043 co_rtable[m][ui] = digit_array_to_int(coarr, 7, 3);
1044 if (m == mirror)
1045 co_rtable[m][ui] =
1046 invert_digits(co_rtable[m][ui], 3, 7);
1047 }
1048 for (ui = 0; ui < factorial8; ui++) {
1049 cube = (Cube){ .cp = ui };
1050 cube = rotate_via_compose(m, cube, pf_cp);
1051 cp_rtable[m][ui] = cube.cp;
1052 }
1053 for (ui = 0; ui < factorial6; ui++) {
1054 cube = (Cube){ .cpos = ui };
1055 cube = rotate_via_compose(m, cube, pf_cpos);
1056 cpos_rtable[m][ui] = cube.cpos;
1057 }
1058 for (mi = 0; mi < NMOVES; mi++) {
1059 if (m == mirror) {
1060 b1 = (mi >= U && mi <= Bw3);
1061 b2 = (mi >= S && mi <= E3);
1062 b3 = (mi >= x && mi <= z3);
1063 if (b1 || b2 || b3)
1064 moves_rtable[m][mi] =
1065 inverse_move_aux[mi];
1066 else
1067 moves_rtable[m][mi] = mi;
1068
1069 if ((mi-1)/3==(R-1)/3 || (mi-1)/3==(Rw-1)/3)
1070 moves_rtable[m][mi] += 3;
1071 if ((mi-1)/3==(L-1)/3 || (mi-1)/3==(L2-1)/3)
1072 moves_rtable[m][mi] -= 3;
1073 } else {
1074 aux = apply_trans(m, apply_move(mi,(Cube){0}));
1075 for (move = 0; move < NMOVES; move++) {
1076 cube = apply_move(
1077 inverse_move_aux[move], aux);
1078 if (is_solved(cube, false))
1079 moves_rtable[m][mi] = move;
1080 }
1081 }
1082 }
1083 }
1084
1085 if (!write_rtables_file())
1086 fprintf(stderr, "Error writing rtables\n");
1087}
1088
1089static void
1090int_to_digit_array(int a, int b, int n, int *r)
1091{
1092 int i;
1093
1094 if (b <= 1)
1095 for (i = 0; i < n; i++)
1096 r[i] = 0;
1097 else
1098 for (i = 0; i < n; i++, a /= b)
1099 r[i] = a % b;
1100}
1101
1102static void
1103int_to_sum_zero_array(int x, int b, int n, int *a)
1104{
1105 int i, s = 0;
1106
1107 if (b <= 1) {
1108 for (i = 0; i < n; i++)
1109 a[i] = 0;
1110 } else {
1111 int_to_digit_array(x, b, n-1, a);
1112 for (i = 0; i < n - 1; i++)
1113 s = (s + a[i]) % b;
1114 a[n-1] = (b - s) % b;
1115 }
1116}
1117
1118static void
1119intarrcopy(int *src, int *dst, int n)
1120{
1121 int i;
1122
1123 for (i = 0; i < n; i++)
1124 dst[i] = src[i];
1125}
1126
1127static int
1128invert_digits(int a, int b, int n)
1129{
1130 int i, *r = malloc(n * sizeof(int));
1131
1132 int_to_digit_array(a, b, n, r);
1133 for (i = 0; i < n; i++)
1134 r[i] = (b-r[i]) % b;
1135
1136 return digit_array_to_int(r, n, b);
1137}
1138
1139static bool
1140is_perm(int *a, int n)
1141{
1142 int *aux = malloc(n * sizeof(int));
1143 int i;
1144
1145 for (i = 0; i < n; i++)
1146 if (a[i] < 0 || a[i] >= n)
1147 return false;
1148 else
1149 aux[a[i]] = 1;
1150
1151 for (i = 0; i < n; i++)
1152 if (!aux[i])
1153 return false;
1154
1155 free(aux);
1156
1157 return true;
1158}
1159
1160static bool
1161is_subset(int *a, int n, int k)
1162{
1163 int i, sum = 0;
1164
1165 for (i = 0; i < n; i++)
1166 sum += a[i] ? 1 : 0;
1167
1168 return sum == k;
1169}
1170
1171static Cube
1172move_via_arrays(CubeArray arr, Cube c, PieceFilter f)
1173{
1174 CubeArray arrc;
1175 Cube ret;
1176
1177 alloc_cubearray(&arrc, f);
1178 cube_to_arrays(c, &arrc, f);
1179
1180 if (f.epose || f.eposs || f.eposm)
1181 apply_permutation(arr.ep, arrc.ep, 12);
1182
1183 if (f.eofb) {
1184 apply_permutation(arr.ep, arrc.eofb, 12);
1185 sum_arrays_mod(arr.eofb, arrc.eofb, 12, 2);
1186 }
1187
1188 if (f.eorl) {
1189 apply_permutation(arr.ep, arrc.eorl, 12);
1190 sum_arrays_mod(arr.eorl, arrc.eorl, 12, 2);
1191 }
1192
1193 if (f.eoud) {
1194 apply_permutation(arr.ep, arrc.eoud, 12);
1195 sum_arrays_mod(arr.eoud, arrc.eoud, 12, 2);
1196 }
1197
1198 if (f.cp)
1199 apply_permutation(arr.cp, arrc.cp, 8);
1200
1201 if (f.coud) {
1202 apply_permutation(arr.cp, arrc.coud, 8);
1203 sum_arrays_mod(arr.coud, arrc.coud, 8, 3);
1204 }
1205
1206 if (f.corl) {
1207 apply_permutation(arr.cp, arrc.corl, 8);
1208 sum_arrays_mod(arr.corl, arrc.corl, 8, 3);
1209 }
1210
1211 if (f.cofb) {
1212 apply_permutation(arr.cp, arrc.cofb, 8);
1213 sum_arrays_mod(arr.cofb, arrc.cofb, 8, 3);
1214 }
1215
1216 if (f.cpos)
1217 apply_permutation(arr.cpos, arrc.cpos, 6);
1218
1219 ret = arrays_to_cube(arrc, f);
1220 free_cubearray(&arrc, f);
1221
1222 return ret;
1223}
1224
1225static Move *
1226moveset_to_movelist(bool *moveset, Step step)
1227{
1228 Cube c;
1229 int *a = malloc(NMOVES * sizeof(int)), b[NMOVES];
1230 int na = 0, nb = 0;
1231 Move i;
1232
1233 if (moveset != NULL) {
1234 for (i = NULLMOVE+1; i < NMOVES; i++) {
1235 if (moveset[i]) {
1236 c = apply_move(i, (Cube){0});
1237 if (step.f != NULL && step.f(c)) {
1238 a[na++] = i;
1239 } else {
1240 b[nb++] = i;
1241 }
1242 }
1243 }
1244 }
1245
1246 intarrcopy(b, a+na, nb);
1247 a[na+nb] = NULLMOVE;
1248
1249 return (Move *)a;
1250}
1251
1252static AlgList *
1253new_alglist()
1254{
1255 AlgList *ret = malloc(sizeof(AlgList));
1256
1257 ret->len = 0;
1258 ret->first = NULL;
1259 ret->last = NULL;
1260
1261 return ret;
1262}
1263
1264static int
1265perm_sign(int *a, int n)
1266{
1267 int i, j, ret = 0;
1268
1269 if (!is_perm(a,n))
1270 return -1;
1271
1272 for (i = 0; i < n; i++)
1273 for (j = i+1; j < n; j++)
1274 ret += (a[i] > a[j]) ? 1 : 0;
1275
1276 return ret % 2;
1277}
1278
1279static int
1280perm_to_index(int *a, int n)
1281{
1282 int i, j, c, ret = 0;
1283
1284 if (!is_perm(a, n))
1285 return -1;
1286
1287 for (i = 0; i < n; i++) {
1288 c = 0;
1289 for (j = i+1; j < n; j++)
1290 c += (a[i] > a[j]) ? 1 : 0;
1291 ret += factorial(n-i-1) * c;
1292 }
1293
1294 return ret;
1295}
1296
1297static int
1298powint(int a, int b)
1299{
1300 if (b < 0)
1301 return 0; /* Truncate */
1302 if (b == 0)
1303 return 1;
1304
1305 if (b % 2)
1306 return a * powint(a, b-1);
1307 else
1308 return powint(a*a, b/2);
1309}
1310
1311static bool
1312read_rtables_file()
1313{
1314 FILE *ttf;
1315 int b = sizeof(uint16_t);
1316 bool r = true;
1317 Move m;
1318
1319 if ((ttf = fopen("rtables", "rb")) != NULL) {
1320 for (m = 0; m < NTRANS; m++) {
1321 r = r && fread(epose_rtable[m],b,me[0],ttf) == me[0];
1322 r = r && fread(eposs_rtable[m],b,me[1],ttf) == me[1];
1323 r = r && fread(eposm_rtable[m],b,me[2],ttf) == me[2];
1324 r = r && fread(eo_rtable[m],b,me[3],ttf) == me[3];
1325 r = r && fread(cp_rtable[m],b,me[6],ttf) == me[6];
1326 r = r && fread(co_rtable[m],b,me[7],ttf) == me[7];
1327 r = r && fread(cpos_rtable[m],b,me[10],ttf) == me[10];
1328 r = r && fread(moves_rtable[m],b,me[11],ttf) == me[11];
1329 }
1330 fclose(ttf);
1331 return r;
1332 } else {
1333 return false;
1334 }
1335}
1336
1337static bool
1338read_ttables_file()
1339{
1340 FILE *ttf;
1341 int m, b = sizeof(uint16_t);
1342 bool r = true;
1343
1344 if ((ttf = fopen("ttables", "rb")) != NULL) {
1345 for (m = 0; m < NMOVES; m++) {
1346 r = r && fread(epose_ttable[m],b,me[0],ttf) == me[0];
1347 r = r && fread(eposs_ttable[m],b,me[1],ttf) == me[1];
1348 r = r && fread(eposm_ttable[m],b,me[2],ttf) == me[2];
1349 r = r && fread(eofb_ttable[m],b,me[3],ttf) == me[3];
1350 r = r && fread(eorl_ttable[m],b,me[4],ttf) == me[4];
1351 r = r && fread(eoud_ttable[m],b,me[5],ttf) == me[5];
1352 r = r && fread(cp_ttable[m],b,me[6],ttf) == me[6];
1353 r = r && fread(coud_ttable[m],b,me[7],ttf) == me[7];
1354 r = r && fread(corl_ttable[m],b,me[8],ttf) == me[8];
1355 r = r && fread(cofb_ttable[m],b,me[9],ttf) == me[9];
1356 r = r && fread(cpos_ttable[m],b,me[10],ttf) == me[10];
1357 }
1358 fclose(ttf);
1359 return r;
1360 } else {
1361 return false;
1362 }
1363}
1364
1365static bool
1366realloc_alg(Alg alg, int n)
1367{
1368 if (n+1 >= BASEALGLEN) {
1369 if (reallocarray(alg, n+2, sizeof(NissMove)) == NULL) {
1370 fprintf(stderr, "Error reallocating alg\n");
1371 return false;
1372 }
1373 }
1374
1375 return true;
1376}
1377
1378static Cube
1379rotate_via_compose(Trans r, Cube c, PieceFilter f)
1380{
1381 Cube ret;
1382 CubeArray ma = {
1383 .ep = ep_mirror,
1384 .eofb = zero12,
1385 .eorl = zero12,
1386 .eoud = zero12,
1387 .cp = cp_mirror,
1388 .coud = zero8,
1389 .corl = zero8,
1390 .cofb = zero8,
1391 .cpos = cpos_mirror
1392 };
1393
1394 if (r != mirror) {
1395 ret = apply_alg_filtered(rotation_niss[r], c, f);
1396 } else {
1397 ret = move_via_arrays(ma, (Cube){0}, f);
1398 ret = compose_filtered(c, ret, f);
1399 ret = move_via_arrays(ma, ret, f);
1400 }
1401
1402 return ret;
1403}
1404
1405static void
1406solve_dfs(Cube c, Step s, SolveOptions opts, DfsData dd)
1407{
1408 DfsData newdd;
1409 Move move;
1410 NissMove nm;
1411 int i;
1412 bool found_many, prune, niss_makes_sense;
1413
1414 found_many = dd.sols->len >= opts.max_solutions;
1415 prune = (!opts.can_niss || dd.niss) && dd.m + s.f(c) > dd.d;
1416 if (found_many || prune)
1417 return;
1418
1419 if (!s.f(c)) {
1420 if (dd.m == dd.d)
1421 append_alg(dd.sols, dd.current_alg);
1422 return;
1423 }
1424
1425 for (i = 0; opts.sorted_moves[i] != NULLMOVE; i++) {
1426 move = opts.sorted_moves[i];
1427 if (possible_next[dd.last2][dd.last1][move]) {
1428 nm = (NissMove){ .m = move, .inverse = dd.niss };
1429 newdd = (DfsData) {
1430 .d = dd.d,
1431 .m = dd.m + 1,
1432 .niss = dd.niss,
1433 .last1 = move,
1434 .last2 = dd.last1,
1435 .sols = dd.sols,
1436 .current_alg = dd.current_alg,
1437 };
1438
1439 append_move(dd.current_alg, nm);
1440 solve_dfs(apply_move(move, c), s, opts, newdd);
1441 remove_last_moves(dd.current_alg, 1);
1442 }
1443 }
1444
1445 niss_makes_sense = !dd.m || (s.f(apply_move(dd.last1, (Cube){0})));
1446 if (opts.can_niss && !dd.niss && niss_makes_sense) {
1447 newdd = (DfsData) {
1448 .d = dd.d,
1449 .m = dd.m,
1450 .niss = true,
1451 .last1 = NULLMOVE,
1452 .last2 = NULLMOVE,
1453 .sols = dd.sols,
1454 .current_alg = dd.current_alg,
1455 };
1456 solve_dfs(inverse_cube(c), s, opts, newdd);
1457 }
1458}
1459
1460static int
1461subset_to_index(int *a, int n, int k)
1462{
1463 int i, ret = 0;
1464
1465 if (!is_subset(a, n, k))
1466 return binomial(n, k);
1467
1468 for (i = 0; i < n; i++) {
1469 if (k == n-i)
1470 return ret;
1471 if (a[i]) {
1472 ret += binomial(n-i-1, k);
1473 k--;
1474 }
1475 }
1476
1477 return ret;
1478}
1479
1480static void
1481sum_arrays_mod(int *src, int *dst, int n, int m)
1482{
1483 int i;
1484
1485 for (i = 0; i < n; i++)
1486 dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m;
1487}
1488
1489static void
1490swap(int *a, int *b)
1491{
1492 int aux;
1493
1494 aux = *a;
1495 *a = *b;
1496 *b = aux;
1497}
1498
1499static bool
1500write_rtables_file()
1501{
1502 FILE *ttf;
1503 bool r = true;
1504 int b = sizeof(uint16_t);
1505 Move m;
1506
1507 if ((ttf = fopen("rtables", "wb")) != NULL) {
1508 for (m = 0; m < NTRANS; m++) {
1509 r = r && fwrite(epose_rtable[m],b,me[0], ttf) == me[0];
1510 r = r && fwrite(eposs_rtable[m],b,me[1], ttf) == me[1];
1511 r = r && fwrite(eposm_rtable[m],b,me[2], ttf) == me[2];
1512 r = r && fwrite(eo_rtable[m],b,me[3], ttf) == me[3];
1513 r = r && fwrite(cp_rtable[m],b,me[6], ttf) == me[6];
1514 r = r && fwrite(co_rtable[m],b,me[7], ttf) == me[7];
1515 r = r && fwrite(cpos_rtable[m],b,me[10],ttf) == me[10];
1516 r = r && fwrite(moves_rtable[m],b,me[11],ttf)== me[11];
1517 }
1518 fclose(ttf);
1519 return r;
1520 } else {
1521 return false;
1522 }
1523}
1524
1525static bool
1526write_ttables_file()
1527{
1528 FILE *ttf;
1529 int m, b = sizeof(uint16_t);;
1530 bool r = true;
1531
1532 if ((ttf = fopen("ttables", "wb")) != NULL) {
1533 for (m = 0; m < NMOVES; m++) {
1534 r = r && fwrite(epose_ttable[m],b,me[0],ttf) == me[0];
1535 r = r && fwrite(eposs_ttable[m],b,me[1],ttf) == me[1];
1536 r = r && fwrite(eposm_ttable[m],b,me[2],ttf) == me[2];
1537 r = r && fwrite(eofb_ttable[m],b,me[3],ttf) == me[3];
1538 r = r && fwrite(eorl_ttable[m],b,me[4],ttf) == me[4];
1539 r = r && fwrite(eoud_ttable[m],b,me[5],ttf) == me[5];
1540 r = r && fwrite(cp_ttable[m],b,me[6],ttf) == me[6];
1541 r = r && fwrite(coud_ttable[m],b,me[7],ttf) == me[7];
1542 r = r && fwrite(corl_ttable[m],b,me[8],ttf) == me[8];
1543 r = r && fwrite(cofb_ttable[m],b,me[9],ttf) == me[9];
1544 r = r && fwrite(cpos_ttable[m],b,me[10],ttf) == me[10];
1545 }
1546 fclose(ttf);
1547 return r;
1548 } else {
1549 return false;
1550 }
1551}
1552
1553/* Public functions implementation *******************************************/
1554
1555Cube
1556apply_alg(Alg alg, Cube cube)
1557{
1558 return apply_alg_filtered(alg, cube, pf_all);
1559}
1560
1561Cube
1562apply_move(Move m, Cube cube)
1563{
1564 Cube moved = {0};
1565
1566 moved.epose = epose_ttable[m][cube.epose];
1567 moved.eposs = eposs_ttable[m][cube.eposs];
1568 moved.eposm = eposm_ttable[m][cube.eposm];
1569 moved.eofb = eofb_ttable[m][cube.eofb];
1570 moved.eorl = eorl_ttable[m][cube.eorl];
1571 moved.eoud = eoud_ttable[m][cube.eoud];
1572 moved.coud = coud_ttable[m][cube.coud];
1573 moved.cofb = cofb_ttable[m][cube.cofb];
1574 moved.corl = corl_ttable[m][cube.corl];
1575 moved.cp = cp_ttable[m][cube.cp];
1576 moved.cpos = cpos_ttable[m][cube.cpos];
1577
1578 return moved;
1579}
1580
1581Cube
1582apply_trans(Trans t, Cube cube)
1583{
1584 Cube transformed = {0};
1585 uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm };
1586 uint16_t aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb };
1587 uint16_t aux_co[3] = { cube.coud, cube.corl, cube.cofb };
1588
1589 transformed.epose = epose_rtable[t][aux_epos[epose_source[t]]];
1590 transformed.eposs = eposs_rtable[t][aux_epos[eposs_source[t]]];
1591 transformed.eposm = eposm_rtable[t][aux_epos[eposm_source[t]]];
1592 transformed.eofb = eo_rtable[t][aux_eo[eofb_source[t]]];
1593 transformed.eorl = eo_rtable[t][aux_eo[eorl_source[t]]];
1594 transformed.eoud = eo_rtable[t][aux_eo[eoud_source[t]]];
1595 transformed.coud = co_rtable[t][aux_co[coud_source[t]]];
1596 transformed.corl = co_rtable[t][aux_co[corl_source[t]]];
1597 transformed.cofb = co_rtable[t][aux_co[cofb_source[t]]];
1598 transformed.cp = cp_rtable[t][cube.cp];
1599 transformed.cpos = cpos_rtable[t][cube.cpos];
1600
1601 return transformed;
1602}
1603
1604/* TODO: this has to be changed using pre-computations */
1605bool
1606block_solved(Cube cube, Block block)
1607{
1608 CubeArray arr;
1609 int i;
1610 bool ret = true;
1611
1612 alloc_cubearray(&arr, pf_all);
1613 cube_to_arrays(cube, &arr, pf_all);
1614
1615 for (i = 0; i < 12; i++)
1616 ret = ret && !(block.edge[i] && (arr.ep[i] != i || arr.eofb[i]));
1617 for (i = 0; i < 8; i++)
1618 ret = ret && !(block.corner[i] && (arr.cp[i] != i || arr.coud[i]));
1619 for (i = 0; i < 6; i++)
1620 ret = ret && !(block.center[i] && arr.cpos[i] != i);
1621
1622 free_cubearray(&arr, pf_all);
1623
1624 return ret;
1625}
1626
1627Center
1628center_at(Cube cube, Center c)
1629{
1630 int ret;
1631 CubeArray arr;
1632
1633 alloc_cubearray(&arr, pf_cpos);
1634 cube_to_arrays(cube, &arr, pf_cpos);
1635 ret = arr.cpos[c];
1636 free_cubearray(&arr, pf_cpos);
1637
1638 return ret;
1639}
1640
1641Cube
1642compose(Cube c2, Cube c1)
1643{
1644 return compose_filtered(c2, c1, pf_all);
1645}
1646
1647Corner
1648corner_at(Cube cube, Corner c)
1649{
1650 int ret;
1651 CubeArray arr;
1652
1653 alloc_cubearray(&arr, pf_cp);
1654 cube_to_arrays(cube, &arr, pf_cp);
1655 ret = arr.cp[c];
1656 free_cubearray(&arr, pf_cp);
1657
1658 return ret;
1659}
1660
1661Edge
1662edge_at(Cube cube, Edge e)
1663{
1664 int ret;
1665 CubeArray arr;
1666
1667 alloc_cubearray(&arr, pf_ep);
1668 cube_to_arrays(cube, &arr, pf_ep);
1669 ret = arr.ep[e];
1670 free_cubearray(&arr, pf_ep);
1671
1672 return ret;
1673}
1674
1675bool
1676equal(Cube c1, Cube c2)
1677{
1678 return c1.eofb == c2.eofb &&
1679 c1.epose == c2.epose &&
1680 c1.eposs == c2.eposs &&
1681 c1.eposm == c2.eposm &&
1682 c1.coud == c2.coud &&
1683 c1.cp == c2.cp &&
1684 c1.cpos == c2.cpos;
1685}
1686
1687Cube
1688inverse_cube(Cube cube)
1689{
1690 CubeArray arr, inv;
1691 Cube ret;
1692 int i;
1693
1694 alloc_cubearray(&arr, pf_all);
1695 alloc_cubearray(&inv, pf_all);
1696
1697 cube_to_arrays(cube, &arr, pf_all);
1698
1699 for (i = 0; i < 12; i++) {
1700 inv.ep[arr.ep[i]] = i;
1701 inv.eofb[arr.ep[i]] = arr.eofb[i];
1702 inv.eorl[arr.ep[i]] = arr.eorl[i];
1703 inv.eoud[arr.ep[i]] = arr.eoud[i];
1704 }
1705
1706 for (i = 0; i < 8; i++) {
1707 inv.cp[arr.cp[i]] = i;
1708 inv.coud[arr.cp[i]] = (3 - arr.coud[i]) % 3;
1709 inv.corl[arr.cp[i]] = (3 - arr.corl[i]) % 3;
1710 inv.cofb[arr.cp[i]] = (3 - arr.cofb[i]) % 3;
1711 }
1712
1713 for (int i = 0; i < 6; i++)
1714 inv.cpos[arr.cpos[i]] = i;
1715
1716 ret = arrays_to_cube(inv, pf_all);
1717 free_cubearray(&arr, pf_all);
1718 free_cubearray(&inv, pf_all);
1719
1720 return ret;
1721}
1722
1723Move
1724inverse_move(Move m)
1725{
1726 return inverse_move_aux[m];
1727}
1728
1729Trans
1730inverse_trans(Trans t)
1731{
1732 return inverse_trans_aux[t];
1733}
1734
1735bool
1736is_solved(Cube cube, bool reorient)
1737{
1738 int i;
1739
1740 if (reorient)
1741 for (i = 0; i < NROTATIONS; i++)
1742 if (is_solved(apply_alg(rotation_algs[i], cube), false))
1743 return true;
1744
1745 return equal(cube, (Cube){0});
1746}
1747
1748int
1749piece_orientation(Cube cube, int piece, char *orientation)
1750{
1751 int arr[12], n, b;
1752 uint16_t x;
1753
1754 if (!strcmp(orientation, "eofb")) {
1755 x = cube.eofb;
1756 n = 12;
1757 b = 2;
1758 } else if (!strcmp(orientation, "eorl")) {
1759 x = cube.eorl;
1760 n = 12;
1761 b = 2;
1762 } else if (!strcmp(orientation, "eoud")) {
1763 x = cube.eoud;
1764 n = 12;
1765 b = 2;
1766 } else if (!strcmp(orientation, "coud")) {
1767 x = cube.coud;
1768 n = 8;
1769 b = 3;
1770 } else if (!strcmp(orientation, "corl")) {
1771 x = cube.corl;
1772 n = 8;
1773 b = 3;
1774 } else if (!strcmp(orientation, "cofb")) {
1775 x = cube.cofb;
1776 n = 8;
1777 b = 3;
1778 } else {
1779 return -1;
1780 }
1781
1782 int_to_sum_zero_array(x, b, n, arr);
1783 if (piece < n)
1784 return arr[piece];
1785
1786 return -1;
1787}
1788
1789void
1790print_cube(Cube cube)
1791{
1792 CubeArray arr;
1793
1794 alloc_cubearray(&arr, pf_all);
1795 cube_to_arrays(cube, &arr, pf_all);
1796
1797 for (int i = 0; i < 12; i++)
1798 printf(" %s ", edge_string[arr.ep[i]]);
1799 printf("\n");
1800
1801 for (int i = 0; i < 12; i++)
1802 printf(" %c ", arr.eofb[i] + '0');
1803 printf("\n");
1804
1805 for (int i = 0; i < 8; i++)
1806 printf("%s ", corner_string[arr.cp[i]]);
1807 printf("\n");
1808
1809 for (int i = 0; i < 8; i++)
1810 printf(" %c ", arr.coud[i] + '0');
1811 printf("\n");
1812
1813 for (int i = 0; i < 6; i++)
1814 printf(" %s ", center_string[arr.cpos[i]]);
1815 printf("\n");
1816
1817 free_cubearray(&arr, pf_all);
1818}
1819
1820void
1821concat(Alg src1, Alg src2, Alg dest)
1822{
1823 int n1 = len(src1), n2 = len(src2);
1824
1825 if (!realloc_alg(dest, n1+n2))
1826 return;
1827
1828 copy_alg(src1, dest);
1829 copy_alg(src2, dest + n1);
1830}
1831
1832void
1833copy_alg(Alg src, Alg dest)
1834{
1835 int i, n = len(src);
1836
1837 if (!realloc_alg(dest, n))
1838 return;
1839
1840 for (i = 0; src[i].m != NULLMOVE; i++)
1841 dest[i] = src[i];
1842 dest[i].m = NULLMOVE;
1843}
1844
1845void
1846invert_alg(Alg src, Alg dest)
1847{
1848 Move m;
1849 int i, n = len(src);
1850
1851 if (!realloc_alg(dest, n))
1852 return;
1853
1854 for (i = 0; i < n; i++) {
1855 m = inverse_move_aux[src[i].m];
1856 dest[n-i-1] = (NissMove) { .m = m, .inverse = src[i].inverse };
1857 }
1858 dest[n].m = NULLMOVE;
1859}
1860
1861int
1862len(Alg alg)
1863{
1864 int i;
1865
1866 for (i = 0; alg[i].m != NULLMOVE; i++);
1867
1868 return i;
1869}
1870
1871Alg
1872new_alg(char *str)
1873{
1874 Alg alg = malloc(BASEALGLEN * sizeof(NissMove));
1875 int i;
1876 bool niss = false;
1877 Move j, m;
1878 NissMove nm;
1879
1880 alg[0] = (NissMove){ .m = NULLMOVE };
1881 for (i = 0; str[i]; i++) {
1882 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
1883 continue;
1884
1885 if (str[i] == '(' && niss) {
1886 fprintf(stderr, "Error reading moves: nested ( )\n");
1887 return alg;
1888 }
1889
1890 if (str[i] == ')' && !niss) {
1891 fprintf(stderr, "Error reading moves: unmatched )\n");
1892 return alg;
1893 }
1894
1895 if (str[i] == '(' || str[i] == ')') {
1896 niss = !niss;
1897 continue;
1898 }
1899
1900 for (j = 0; j < NMOVES; j++) {
1901 if (str[i] == move_string[j][0]) {
1902 m = j;
1903 if (m <= B && str[i+1]=='w') {
1904 m += Uw - U;
1905 i++;
1906 }
1907 if (str[i+1]=='2') {
1908 m += 1;
1909 i++;
1910 } else if (str[i+1]=='\'' || str[i+1]=='3') {
1911 m += 2;
1912 i++;
1913 }
1914 nm = (NissMove){ .m = m, .inverse = niss };
1915 append_move(alg, nm);
1916 break;
1917 }
1918 }
1919 }
1920 append_move(alg, (NissMove){ .m = NULLMOVE });
1921
1922 return alg;
1923}
1924
1925void
1926print_alg(Alg alg)
1927{
1928 char fill[4];
1929 int i;
1930 bool niss = false;
1931
1932 for (i = 0; alg[i].m != NULLMOVE; i++) {
1933 if (!niss && alg[i].inverse)
1934 strcpy(fill, i == 0 ? "(" : " (");
1935 if (niss && !alg[i].inverse)
1936 strcpy(fill, ") ");
1937 if (niss == alg[i].inverse)
1938 strcpy(fill, i == 0 ? "" : " ");
1939
1940 printf("%s%s", fill, move_string[alg[i].m]);
1941 niss = alg[i].inverse;
1942 }
1943 printf("%s\n", niss ? ")" : "");
1944}
1945
1946void
1947remove_last_moves(Alg alg, int k)
1948{
1949 int n = len(alg);
1950 int i = max(0, n-k);
1951
1952 alg[i].m = NULLMOVE;
1953}
1954
1955AlgList *
1956solve(Cube cube, Step step, SolveOptions opts)
1957{
1958 AlgList *sols = new_alglist();
1959 AlgListNode *node;
1960 Cube c;
1961 DfsData dd;
1962 int i;
1963
1964 if (step.ready != NULL && !step.ready(cube))
1965 return sols;
1966
1967 if (opts.sorted_moves == NULL)
1968 opts.sorted_moves = moveset_to_movelist(opts.moveset, step);
1969
1970 for (i = opts.min_moves; i <= opts.max_moves; i++) {
1971 if (sols->len && opts.optimal_only)
1972 break;
1973
1974 c = apply_trans(opts.pre_trans, cube);
1975 dd = (DfsData) {
1976 .d = i,
1977 .m = 0,
1978 .niss = false,
1979 .last1 = NULLMOVE,
1980 .last2 = NULLMOVE,
1981 .sols = sols,
1982 .current_alg = new_alg("")
1983 };
1984
1985 solve_dfs(c, step, opts, dd);
1986 }
1987
1988 for (node = sols->first; node != NULL; node = node->next)
1989 transform_alg(inverse_trans_aux[opts.pre_trans], node->alg);
1990
1991 return sols;
1992}
1993
1994void
1995transform_alg(Trans t, Alg alg)
1996{
1997 int i;
1998
1999 for (i = 0; alg[i].m != NULLMOVE; i++)
2000 alg[i].m = moves_rtable[t][alg[i].m];
2001}
2002
2003
2004void
2005init()
2006{
2007 init_moves();
2008 init_auxtables();
2009 init_trans();
2010}
diff --git a/old/2021-06-02-cleanedup/cube.h b/old/2021-06-02-cleanedup/cube.h
deleted file mode 100644
index f1559a4..0000000
--- a/old/2021-06-02-cleanedup/cube.h
+++ /dev/null
@@ -1,179 +0,0 @@
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdint.h>
4#include <stdlib.h>
5#include <string.h>
6
7/* Constants ****************************************************************/
8
9#define NMOVES (z3+1)
10#define NTRANS (mirror+1)
11#define NROTATIONS (NTRANS-1)
12
13/* Typedefs *****************************************************************/
14
15typedef enum center Center;
16typedef enum corner Corner;
17typedef enum edge Edge;
18typedef enum move Move;
19typedef enum trans Trans;
20
21typedef struct nissmove * Alg;
22typedef struct alglist AlgList;
23typedef struct alglistnode AlgListNode;
24typedef struct block Block;
25typedef struct cube Cube;
26typedef struct nissmove NissMove;
27typedef struct solveoptions SolveOptions;
28typedef struct step Step;
29
30/* Type specifications *******************************************************/
31
32enum
33center
34{
35 U_center, D_center,
36 R_center, L_center,
37 F_center, B_center
38};
39
40enum
41corner
42{
43 UFR, UFL, UBL, UBR,
44 DFR, DFL, DBL, DBR
45};
46
47enum
48edge
49{
50 UF, UL, UB, UR,
51 DF, DL, DB, DR,
52 FR, FL, BL, BR
53};
54
55enum
56move
57{
58 NULLMOVE,
59 U, U2, U3, D, D2, D3,
60 R, R2, R3, L, L2, L3,
61 F, F2, F3, B, B2, B3,
62 Uw, Uw2, Uw3, Dw, Dw2, Dw3,
63 Rw, Rw2, Rw3, Lw, Lw2, Lw3,
64 Fw, Fw2, Fw3, Bw, Bw2, Bw3,
65 M, M2, M3,
66 S, S2, S3,
67 E, E2, E3,
68 x, x2, x3,
69 y, y2, y3,
70 z, z2, z3,
71};
72
73enum
74trans
75{
76 uf, ur, ub, ul,
77 df, dr, db, dl,
78 rf, rd, rb, ru,
79 lf, ld, lb, lu,
80 fu, fr, fd, fl,
81 bu, br, bd, bl,
82 mirror, /* R|L */
83};
84
85struct
86alglist
87{
88 AlgListNode *first;
89 AlgListNode *last;
90 int len;
91};
92
93struct
94alglistnode
95{
96 Alg alg;
97 AlgListNode *next;
98};
99
100struct
101block
102{
103 bool edge[12];
104 bool corner[8];
105 bool center[6];
106};
107
108struct
109cube
110{
111 uint16_t epose;
112 uint16_t eposs;
113 uint16_t eposm;
114 uint16_t eofb;
115 uint16_t eorl;
116 uint16_t eoud;
117 uint16_t cp;
118 uint16_t coud;
119 uint16_t cofb;
120 uint16_t corl;
121 uint16_t cpos;
122};
123
124struct
125nissmove
126{
127 Move m;
128 bool inverse;
129};
130
131struct
132solveoptions
133{
134 int min_moves;
135 int max_moves;
136 int max_solutions;
137 bool optimal_only;
138 bool can_niss;
139 bool *moveset;
140 Move *sorted_moves;
141 Trans pre_trans;
142};
143
144struct
145step
146{
147 int (*f)(Cube);
148 bool (*ready)(Cube);
149};
150
151/* Public functions **********************************************************/
152
153Cube apply_alg(Alg alg, Cube cube);
154Cube apply_move(Move m, Cube cube);
155Cube apply_trans(Trans t, Cube cube);
156bool block_solved(Cube cube, Block);
157Center center_at(Cube cube, Center c);
158Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */
159Corner corner_at(Cube cube, Corner c);
160Edge edge_at(Cube cube, Edge e);
161bool equal(Cube c1, Cube c2);
162Cube inverse_cube(Cube cube);
163Move inverse_move(Move m);
164Trans inverse_trans(Trans t);
165bool is_solved(Cube cube, bool reorient);
166int piece_orientation(Cube cube, int piece, char *orientation);
167void print_cube(Cube cube);
168AlgList * solve(Cube cube, Step step, SolveOptions opts);
169
170void concat(Alg src1, Alg src2, Alg dest);
171void copy_alg(Alg src, Alg dest);
172void invert_alg(Alg src, Alg dest);
173int len(Alg alg);
174Alg new_alg(char *str);
175void print_alg(Alg alg);
176void remove_last_moves(Alg alg, int k);
177void transform_alg(Trans t, Alg alg);
178
179void init();
diff --git a/old/2021-06-02-cleanedup/main.c b/old/2021-06-02-cleanedup/main.c
deleted file mode 100644
index fca5e3c..0000000
--- a/old/2021-06-02-cleanedup/main.c
+++ /dev/null
@@ -1,35 +0,0 @@
1#include <stdio.h>
2#include "cube.h"
3#include "steps.h"
4
5int main() {
6 Alg algo;
7 AlgList *sols;
8 Cube cube;
9 SolveOptions opts;
10
11 init();
12
13 algo = new_alg("R U R' F");
14 cube = apply_alg(algo, (Cube){0});
15
16 print_cube(apply_trans(rd, cube));
17
18 opts = (SolveOptions) {
19 .min_moves = 0,
20 .max_moves = 5,
21 .optimal_only = true,
22 .max_solutions = 3,
23 .can_niss = false,
24 .moveset = standard_moveset,
25 .pre_trans = fu
26 };
27 sols = solve(cube, step_eofb, opts);
28 if (sols->len == 0)
29 fprintf(stderr, "No solution found\n");
30 else
31 print_alg(sols->first->alg);
32
33
34 return 0;
35}
diff --git a/old/2021-06-02-cleanedup/steps.h b/old/2021-06-02-cleanedup/steps.h
deleted file mode 100644
index 452b71c..0000000
--- a/old/2021-06-02-cleanedup/steps.h
+++ /dev/null
@@ -1,22 +0,0 @@
1/* Pre-conditions, i.e. "ready(cube)" functions ******************************/
2
3bool always_ready(Cube cube) { return true; }
4
5/* Main functions, i.e. "f(cube)" ********************************************/
6
7int f_eofb(Cube cube) { return (cube.eofb != 0) ? 1 : 0; }
8
9/* Steps *********************************************************************/
10
11Step step_eofb = { .f = f_eofb, .ready = always_ready };
12
13/* Movesets ******************************************************************/
14
15bool standard_moveset[NMOVES] = {
16 [U] = true, [U2] = true, [U3] = true,
17 [D] = true, [D2] = true, [D3] = true,
18 [R] = true, [R2] = true, [R3] = true,
19 [L] = true, [L2] = true, [L3] = true,
20 [F] = true, [F2] = true, [F3] = true,
21 [B] = true, [B2] = true, [B3] = true,
22};

Generated with cgit - Back to sebastiano.tronto.net