aboutsummaryrefslogtreecommitdiff
path: root/old/2021-05-26-before-restyle
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--old/2021-05-26-before-restyle/cube.c293
-rw-r--r--old/2021-05-26-before-restyle/cube.h65
-rw-r--r--old/2021-05-26-before-restyle/main.c24
-rw-r--r--old/2021-05-26-before-restyle/moves.c412
-rw-r--r--old/2021-05-26-before-restyle/moves.h51
-rw-r--r--old/2021-05-26-before-restyle/solve.c180
-rw-r--r--old/2021-05-26-before-restyle/solve.h59
-rw-r--r--old/2021-05-26-before-restyle/transformations.c200
-rw-r--r--old/2021-05-26-before-restyle/transformations.h34
-rw-r--r--old/2021-05-26-before-restyle/utils.c197
-rw-r--r--old/2021-05-26-before-restyle/utils.h70
11 files changed, 1585 insertions, 0 deletions
diff --git a/old/2021-05-26-before-restyle/cube.c b/old/2021-05-26-before-restyle/cube.c
new file mode 100644
index 0000000..603c66a
--- /dev/null
+++ b/old/2021-05-26-before-restyle/cube.c
@@ -0,0 +1,293 @@
1#include "cube.h"
2
3typedef struct {
4 int ep[12],eofb[12],eorl[12],eoud[12],cp[8],coud[8],corl[8],cofb[8],cpos[6];
5} CubeArrayAllocated;
6
7void allocate_cubearray(CubeArray *arr, CubeArrayAllocated *all);
8
9char edge_string[12][5] =
10 { "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR" };
11char corner_string[8][5] = { "UFR","UFL","UBL","UBR","DFR","DFL","DBL","DBR" };
12char center_string[6][5] = { "U", "D", "R", "L", "F", "B" };
13
14int epe_solved[4] = {FR, FL, BL, BR};
15int eps_solved[4] = {UL, UR, DL, DR};
16int epm_solved[4] = {UF, UB, DF, DB};
17
18PieceFilter pf_all = {true,true,true,true,true,true,true,true,true,true,true},
19 pf_cpos = { .cpos = true }, pf_cp = { .cp = true },
20 pf_ep = { .epose = true, .eposs = true, .eposm = true },
21 pf_e = {.epose=true}, pf_s={.eposs=true}, pf_m={.eposm=true},
22 pf_eo = { .eofb = true, .eorl = true, .eoud = true },
23 pf_co = { .coud = true, .cofb = true, .corl = true };
24
25void allocate_cubearray(CubeArray *arr, CubeArrayAllocated *all) {
26 arr->ep = all->ep;
27 arr->eofb = all->eofb;
28 arr->eorl = all->eorl;
29 arr->eoud = all->eoud;
30 arr->cp = all->cp;
31 arr->coud = all->coud;
32 arr->corl = all->corl;
33 arr->cofb = all->cofb;
34 arr->cpos = all->cpos;
35}
36
37void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) {
38 /* ep is the hardest */
39 if (f.epose || f.eposs || f.eposm)
40 for (int i = 0; i < 12; i++) arr->ep[i] = -1;
41 if (f.epose) {
42 int epe[4], epose[12];
43 index_to_perm(cube.epose % factorial(4), 4, epe);
44 index_to_subset(cube.epose / factorial(4), 12, 4, epose);
45 for (int i = 0, ie = 0; i < 12; i++)
46 if (epose[i]) arr->ep[i] = epe_solved[epe[ie++]];
47 }
48 if (f.eposs) {
49 int eps[4], eposs[12];
50 index_to_perm(cube.eposs % factorial(4), 4, eps);
51 index_to_subset(cube.eposs / factorial(4), 12, 4, eposs);
52 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
53 for (int i = 0, is = 0; i < 12; i++)
54 if (eposs[i]) arr->ep[i] = eps_solved[eps[is++]];
55 }
56 if (f.eposm) {
57 int epm[4], eposm[12];
58 index_to_perm(cube.eposm % factorial(4), 4, epm);
59 index_to_subset(cube.eposm / factorial(4), 12, 4, eposm);
60 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
61 for (int i = 0, im = 0; i < 12; i++)
62 if (eposm[i]) arr->ep[i] = epm_solved[epm[im++]];
63 }
64
65 /* All the others */
66 if (f.eofb) int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
67 if (f.eorl) int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
68 if (f.eoud) int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
69 if (f.cp) index_to_perm( cube.cp, 8, arr->cp);
70 if (f.coud) int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
71 if (f.corl) int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
72 if (f.cofb) int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
73 if (f.cpos) index_to_perm( cube.cpos, 6, arr->cpos);
74}
75
76Cube arrays_to_cube(CubeArray arr, PieceFilter f) {
77 Cube ret = {0};
78
79 /* Again, ep is the hardest part */
80 if (f.epose) {
81 int epe[4], epose[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
82 for (int i = 0, ie = 0; i < 12; i++)
83 for (int j = 0; j < 4; j++)
84 if (arr.ep[i] == epe_solved[j])
85 { epe[ie++] = j; epose[i] = 1; }
86 ret.epose = factorial(4)*subset_to_index(epose,12,4)+perm_to_index(epe,4);
87 }
88 if (f.eposs) {
89 int eps[4], eposs[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
90 for (int i = 0, is = 0; i < 12; i++)
91 for (int j = 0; j < 4; j++)
92 if (arr.ep[i] == eps_solved[j])
93 { eps[is++] = j; eposs[i] = 1; }
94 for (int i = 0; i < 4; i++) swap(&eposs[eps_solved[i]], &eposs[i+8]);
95 ret.eposs = factorial(4)*subset_to_index(eposs,12,4)+perm_to_index(eps,4);
96 }
97 if (f.eposm) {
98 int epm[4], eposm[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
99 for (int i = 0, im = 0; i < 12; i++)
100 for (int j = 0; j < 4; j++)
101 if (arr.ep[i] == epm_solved[j])
102 { epm[im++] = j; eposm[i] = 1; }
103 for (int i = 0; i < 4; i++) swap(&eposm[epm_solved[i]], &eposm[i+8]);
104 ret.eposm = factorial(4)*subset_to_index(eposm,12,4)+perm_to_index(epm,4);
105 }
106 if (f.eofb) ret.eofb = digit_array_to_int(arr.eofb, 11, 2);
107 if (f.eorl) ret.eorl = digit_array_to_int(arr.eorl, 11, 2);
108 if (f.eoud) ret.eoud = digit_array_to_int(arr.eoud, 11, 2);
109 if (f.cp) ret.cp = perm_to_index( arr.cp, 8 );
110 if (f.coud) ret.coud = digit_array_to_int(arr.coud, 7, 3);
111 if (f.corl) ret.corl = digit_array_to_int(arr.corl, 7, 3);
112 if (f.cofb) ret.cofb = digit_array_to_int(arr.cofb, 7, 3);
113 if (f.cpos) ret.cpos = perm_to_index( arr.cpos, 6 );
114
115 return ret;
116}
117
118int piece_orientation(Cube cube, int piece, char *orientation) {
119 int arr[12], n, b;
120 uint16_t x;
121 if (!strcmp(orientation, "eofb")) { x = cube.eofb; n = 12; b = 2; } else
122 if (!strcmp(orientation, "eorl")) { x = cube.eorl; n = 12; b = 2; } else
123 if (!strcmp(orientation, "eoud")) { x = cube.eoud; n = 12; b = 2; } else
124 if (!strcmp(orientation, "coud")) { x = cube.coud; n = 8; b = 3; } else
125 if (!strcmp(orientation, "corl")) { x = cube.corl; n = 8; b = 3; } else
126 if (!strcmp(orientation, "cofb")) { x = cube.cofb; n = 8; b = 3; }
127 else return -1;
128
129 int_to_sum_zero_array(x, b, n, arr);
130 if (piece < n)
131 return arr[piece];
132 return -1;
133}
134
135Center center_at(Cube cube, Center c) {
136 static CubeArrayAllocated all = {0};
137 CubeArray arr = {0};
138 allocate_cubearray(&arr, &all);
139 cube_to_arrays(cube, &arr, pf_cpos);
140 return arr.cpos[c];
141}
142
143Edge edge_at(Cube cube, Edge e) {
144 static CubeArrayAllocated all = {0};
145 CubeArray arr = {0};
146 allocate_cubearray(&arr, &all);
147 cube_to_arrays(cube, &arr, pf_ep);
148 return arr.ep[e];
149}
150
151Corner corner_at(Cube cube, Corner c) {
152 static CubeArrayAllocated all = {0};
153 CubeArray arr = {0};
154 allocate_cubearray(&arr, &all);
155 cube_to_arrays(cube, &arr, pf_cp);
156 return arr.cp[c];
157}
158
159bool block_solved(Cube cube, Block block) {
160 static CubeArrayAllocated all = {0};
161 CubeArray arr = {0};
162 allocate_cubearray(&arr, &all);
163 cube_to_arrays(cube, &arr, pf_all);
164
165 bool ret = true;
166
167 for (int i = 0; i < 12; i++)
168 ret = ret && !(block.edge[i] && (arr.ep[i] != i || arr.eofb[i]));
169 for (int i = 0; i < 8; i++)
170 ret = ret && !(block.corner[i] && (arr.cp[i] != i || arr.coud[i]));
171 for (int i = 0; i < 6; i++)
172 ret = ret && !(block.center[i] && arr.cpos[i] != i);
173
174 return ret;
175}
176
177bool equal(Cube c1, Cube c2) {
178 return c1.eofb == c2.eofb && c1.epose == c2.epose &&
179 c1.eposs == c2.eposs && c1.eposm == c2.eposm &&
180 c1.coud == c2.coud && c1.cp == c2.cp &&
181 c1.cpos == c2.cpos;
182}
183
184bool is_solved(Cube cube) {
185 /* TODO: might return true if cube is not solvable but looks solved form one
186 of the incompatible interpretations (e.g. eofb and ep solved, but
187 eorl not solve) */
188 return !cube.eofb && !cube.coud && !cube.cp &&
189 !cube.epose && !cube.eposs && !cube.eposm && !cube.cpos;
190}
191
192void print_cube(Cube cube) {
193 static CubeArrayAllocated all = {0};
194 CubeArray arrx = {0};
195 allocate_cubearray(&arrx, &all);
196 cube_to_arrays(cube, &arrx, pf_all);
197
198 for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arrx.ep[i]]);
199 printf("\n");
200 for (int i = 0; i < 12; i++) printf(" %c ", arrx.eofb[i] + '0');
201 printf("\n");
202 for (int i = 0; i < 8; i++) printf("%s ", corner_string[arrx.cp[i]]);
203 printf("\n");
204 for (int i = 0; i < 8; i++) printf(" %c ", arrx.coud[i] + '0');
205 printf("\n");
206 for (int i = 0; i < 6; i++) printf(" %s ", center_string[arrx.cpos[i]]);
207 printf("\n");
208}
209
210Cube admissible_ep(Cube cube, PieceFilter f) {
211 static CubeArrayAllocated all = {0};
212 CubeArray arrx = {0};
213 allocate_cubearray(&arrx, &all);
214 cube_to_arrays(cube, &arrx, f);
215
216 bool used[12] = {0};
217 for (int i = 0; i < 12; i++)
218 if (arrx.ep[i] != -1)
219 used[arrx.ep[i]] = true;
220 for (int i = 0, j = 0; i < 12; i++) {
221 while (j < 11 && used[j]) j++;
222 if (arrx.ep[i] == -1)
223 arrx.ep[i] = j++;
224 }
225
226 return arrays_to_cube(arrx, pf_ep);
227}
228
229Cube inverse_cube(Cube cube) {
230 static CubeArrayAllocated all = {0}, invall = {0};
231 CubeArray arrx = {0}, invx = {0};
232 allocate_cubearray(&arrx, &all);
233 allocate_cubearray(&invx, &invall);
234
235 cube_to_arrays(cube, &arrx, pf_all);
236
237 for (int i = 0; i < 12; i++) {
238 invx.ep[arrx.ep[i]] = i;
239 invx.eofb[arrx.ep[i]] = arrx.eofb[i];
240 invx.eorl[arrx.ep[i]] = arrx.eorl[i];
241 invx.eoud[arrx.ep[i]] = arrx.eoud[i];
242 }
243 for (int i = 0; i < 8; i++) {
244 invx.cp[arrx.cp[i]] = i;
245 invx.coud[arrx.cp[i]] = (3 - arrx.coud[i])%3;
246 invx.corl[arrx.cp[i]] = (3 - arrx.corl[i])%3;
247 invx.cofb[arrx.cp[i]] = (3 - arrx.cofb[i])%3;
248 }
249 for (int i = 0; i < 6; i++)
250 invx.cpos[arrx.cpos[i]] = i;
251
252 return arrays_to_cube(invx, pf_all);
253}
254
255Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter f) {
256 static CubeArrayAllocated all = {0};
257 CubeArray arrx = {0};
258 allocate_cubearray(&arrx, &all);
259
260 cube_to_arrays(c, &arrx, f);
261
262 if (f.epose || f.eposs || f.eposm)
263 apply_permutation( arr.ep, arrx.ep, 12 );
264 if (f.eofb) { apply_permutation( arr.ep, arrx.eofb, 12 );
265 sum_arrays_mod( arr.eofb, arrx.eofb, 12, 2 ); }
266 if (f.eorl) { apply_permutation( arr.ep, arrx.eorl, 12 );
267 sum_arrays_mod( arr.eorl, arrx.eorl, 12, 2 ); }
268 if (f.eoud) { apply_permutation( arr.ep, arrx.eoud, 12 );
269 sum_arrays_mod( arr.eoud, arrx.eoud, 12, 2 ); }
270 if (f.cp) apply_permutation( arr.cp, arrx.cp, 8 );
271 if (f.coud) { apply_permutation( arr.cp, arrx.coud, 8 );
272 sum_arrays_mod( arr.coud, arrx.coud, 8, 3 ); }
273 if (f.corl) { apply_permutation( arr.cp, arrx.corl, 8 );
274 sum_arrays_mod( arr.corl, arrx.corl, 8, 3 ); }
275 if (f.cofb) { apply_permutation( arr.cp, arrx.cofb, 8 );
276 sum_arrays_mod( arr.cofb, arrx.cofb, 8, 3 ); }
277 if (f.cpos) apply_permutation( arr.cpos, arrx.cpos, 6 );
278
279 return arrays_to_cube(arrx, f);
280}
281
282Cube compose_filtered(Cube c2, Cube c1, PieceFilter f) {
283 static CubeArrayAllocated all = {0};
284 CubeArray arrx = {0};
285 allocate_cubearray(&arrx, &all);
286
287 cube_to_arrays(c2, &arrx, f);
288 return move_via_arrays(arrx, c1, f);
289}
290
291Cube compose(Cube c2, Cube c1) {
292 return compose_filtered(c2, c1, pf_all);
293}
diff --git a/old/2021-05-26-before-restyle/cube.h b/old/2021-05-26-before-restyle/cube.h
new file mode 100644
index 0000000..0c9fc7b
--- /dev/null
+++ b/old/2021-05-26-before-restyle/cube.h
@@ -0,0 +1,65 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include <string.h>
8#include "utils.h"
9
10typedef enum {U_center,D_center,R_center,L_center,F_center,B_center} Center;
11typedef enum { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge;
12typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner;
13
14typedef struct {
15 uint16_t eofb, eorl, eoud, coud, cofb, corl,
16 epose, eposs, eposm, cp, cpos;
17} Cube;
18
19typedef struct {
20 bool edge[12], corner[8], center[6];
21} Block;
22
23typedef struct {
24 bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos;
25} PieceFilter;
26
27typedef struct {
28 int *ep, *eofb, *eorl, *eoud, *cp, *coud, *corl, *cofb, *cpos;
29} CubeArray;
30
31extern PieceFilter pf_all, pf_cpos, pf_ep, pf_cp,
32 pf_e, pf_s, pf_m, pf_eo, pf_co;
33
34void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
35Cube arrays_to_cube(CubeArray arr, PieceFilter f);
36
37/* piece can be edge or corner and orientation is any of the following:
38 "eofb", "eorl", "eoud", "coud", "corl", "cofb"
39 Return either 0 (oriented) or 1 for edges and 0, 1 or 2 for corners */
40int piece_orientation(Cube cube, int piece, char *orientation);
41Center center_at(Cube cube, Center c);
42Edge edge_at(Cube cube, Edge e);
43Corner corner_at(Cube cube, Corner c);
44bool block_solved(Cube cube, Block);
45/* Aggiungi funzioni per "queries" sul cubo: se pezzo è orientato rispetto ad
46 un certo asse, se il pezzo è risolto... */
47/* Would be nice: a funciton block_solved(Cube c, Block b), where Block is
48 something like struct {bool centers[6], edges[12], corners[8]}
49 (The advantage over checking pieces one by one is that I can convert
50 to cubearray only once and for all) */
51/* Altro TODO, ma forse non ne vale la pena: pre-calcolare tutti i possibili
52 valori per questi, e salvare i risultati in array (facile per cp e cpos,
53 mentre per ep bisogna anche cercare quale tra epose, eposs e eposm contiene
54 il valore giusto) */
55
56bool equal(Cube c1, Cube c2);
57bool is_solved(Cube cube);
58void print_cube(Cube cube);
59Cube admissible_ep(Cube cube, PieceFilter f); /* Returns admissible ep */
60Cube inverse_cube(Cube cube);
61Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */
62Cube compose_filtered(Cube c2, Cube c1, PieceFilter f);
63Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter pf);
64
65#endif
diff --git a/old/2021-05-26-before-restyle/main.c b/old/2021-05-26-before-restyle/main.c
new file mode 100644
index 0000000..cb61526
--- /dev/null
+++ b/old/2021-05-26-before-restyle/main.c
@@ -0,0 +1,24 @@
1#include <stdio.h>
2#include "cube.h"
3#include "moves.h"
4#include "solve.h"
5#include "transformations.h"
6
7int main() {
8 init_ttables(true, true);
9 init_aux_tables();
10 init_transformations(true, true);
11
12
13 char moves[100] = "R' D2 F2 U2 R F2 R D2 L' R2 D2 F D' L' U' B R' D' U R' B";
14 NissMove alg[100];
15 read_moves(moves, alg, 100);
16 Cube cube = apply_alg(alg, (Cube){0});
17 print_cube(transform_cube(rd, cube));
18
19 transform_alg(rd, alg);
20 print_alg(alg);
21
22
23 return 0;
24}
diff --git a/old/2021-05-26-before-restyle/moves.c b/old/2021-05-26-before-restyle/moves.c
new file mode 100644
index 0000000..15f0238
--- /dev/null
+++ b/old/2021-05-26-before-restyle/moves.c
@@ -0,0 +1,412 @@
1#include "moves.h"
2
3Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f);
4/* void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front); */
5bool read_ttables_file();
6bool write_ttables_file();
7
8/* Transition tables */
9uint16_t epose_ttable[NMOVES][factorial12/factorial8];
10uint16_t eposs_ttable[NMOVES][factorial12/factorial8];
11uint16_t eposm_ttable[NMOVES][factorial12/factorial8];
12uint16_t eofb_ttable[NMOVES][pow2to11];
13uint16_t eorl_ttable[NMOVES][pow2to11];
14uint16_t eoud_ttable[NMOVES][pow2to11];
15uint16_t cp_ttable[NMOVES][factorial8];
16uint16_t coud_ttable[NMOVES][pow3to7];
17uint16_t cofb_ttable[NMOVES][pow3to7];
18uint16_t corl_ttable[NMOVES][pow3to7];
19uint16_t cpos_ttable[NMOVES][factorial6];
20
21bool commute[NMOVES][NMOVES];
22bool possible_next[NMOVES][NMOVES][NMOVES];
23Move inverse[NMOVES];
24NissMove rotation_algs[24][3] = {
25 { { .m = NULLMOVE }, { .m = NULLMOVE }, { .m = NULLMOVE } },
26 { { .m = y }, { .m = NULLMOVE }, { .m = NULLMOVE } },
27 { { .m = y2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
28 { { .m = y3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
29 { { .m = z2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
30 { { .m = y }, { .m = z2 }, { .m = NULLMOVE } },
31 { { .m = x2 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
32 { { .m = y3 }, { .m = z2 }, { .m = NULLMOVE } },
33 { { .m = z3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
34 { { .m = z3 }, { .m = y }, { .m = NULLMOVE } },
35 { { .m = z3 }, { .m = y2 }, { .m = NULLMOVE } },
36 { { .m = z3 }, { .m = y3 }, { .m = NULLMOVE } },
37 { { .m = z }, { .m = NULLMOVE }, { .m = NULLMOVE } },
38 { { .m = z }, { .m = y3 }, { .m = NULLMOVE } },
39 { { .m = z }, { .m = y2 }, { .m = NULLMOVE } },
40 { { .m = z }, { .m = y }, { .m = NULLMOVE } },
41 { { .m = x }, { .m = y2 }, { .m = NULLMOVE } },
42 { { .m = x }, { .m = y }, { .m = NULLMOVE } },
43 { { .m = x }, { .m = NULLMOVE }, { .m = NULLMOVE } },
44 { { .m = x }, { .m = y3 }, { .m = NULLMOVE } },
45 { { .m = x3 }, { .m = NULLMOVE }, { .m = NULLMOVE } },
46 { { .m = x3 }, { .m = y }, { .m = NULLMOVE } },
47 { { .m = x3 }, { .m = y2 }, { .m = NULLMOVE } },
48 { { .m = x3 }, { .m = y3 }, { .m = NULLMOVE } },
49};
50
51char move_string[NMOVES][5] =
52 { "-",
53 "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'",
54 "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'",
55 "Uw", "Uw2", "Uw\'", "Dw", "Dw2", "Dw\'", "Rw", "Rw2", "Rw\'",
56 "Lw", "Lw2", "Lw\'", "Fw", "Fw2", "Fw\'", "Bw", "Bw2", "Bw\'",
57 "M", "M2", "M\'", "S", "S2", "S\'", "E", "E2", "E\'",
58 "x", "x2", "x\'", "y", "y2", "y\'", "z", "z2", "z\'" };
59
60/* For each type of pieces only the effects of U, x and y are described */
61int edge_cycle[NMOVES][12] =
62 { [U] = {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR},
63 [x] = {DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR},
64 [y] = {UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL} };
65int eofb_flipped[NMOVES][12] =
66 { [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
67 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
68int eorl_flipped[NMOVES][12] =
69 { [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
70 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } };
71int eoud_flipped[NMOVES][12] =
72 { [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
73 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
74 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
75int corner_cycle[NMOVES][8] =
76 { [U] = {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR},
77 [x] = {DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR},
78 [y] = {UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL} };
79int coud_flipped[NMOVES][8] =
80 { [x] = {[UFR]=2,[UBR]=1,[DBR]=2,[DFR]=1,[UFL]=1,[UBL]=2,[DBL]=1,[DFL]=2} };
81int corl_flipped[NMOVES][8] =
82 { [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
83 [y] = {[UFR]=1,[UBR]=2,[UBL]=1,[UFL]=2,[DFR]=2,[DBR]=1,[DBL]=2,[DFL]=1} };
84int cofb_flipped[NMOVES][8] =
85 { [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
86 [x] = {[UFR]=1,[UBR]=2,[DFR]=2,[DBR]=1,[UBL]=1,[UFL]=2,[DBL]=2,[DFL]=1},
87 [y] = {[UFR]=2,[UBR]=1,[UBL]=2,[UFL]=1,[DFR]=1,[DBR]=2,[DBL]=1,[DFL]=2} };
88int center_cycle[NMOVES][6] =
89 { [x] = {F_center, B_center, R_center, L_center, D_center, U_center},
90 [y] = {U_center, D_center, B_center, F_center, R_center, L_center} };
91
92/* Each move is reduced to a combination of U, x and y using this table */
93Move equiv_moves[NMOVES][14] = {
94 [U] = { U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
95 [U2] = { U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
96 [U3] = { U, U, U, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
97 [D] = { x, x, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
98 [D2] = { x, x, U, U, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
99 [D3] = { x, x, U, U, U, x, x, 0, 0, 0, 0, 0, 0, 0 },
100 [R] = { y, x, U, x, x, x, y, y, y, 0, 0, 0, 0, 0 },
101 [R2] = { y, x, U, U, x, x, x, y, y, y, 0, 0, 0, 0 },
102 [R3] = { y, x, U, U, U, x, x, x, y, y, y, 0, 0, 0 },
103 [L] = { y, y, y, x, U, x, x, x, y, 0, 0, 0, 0, 0 },
104 [L2] = { y, y, y, x, U, U, x, x, x, y, 0, 0, 0, 0 },
105 [L3] = { y, y, y, x, U, U, U, x, x, x, y, 0, 0, 0 },
106 [F] = { x, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
107 [F2] = { x, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0, 0 },
108 [F3] = { x, U, U, U, x, x, x, 0, 0, 0, 0, 0, 0, 0 },
109 [B] = { x, x, x, U, x, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
110 [B2] = { x, x, x, U, U, x, 0, 0, 0, 0, 0, 0, 0, 0 },
111 [B3] = { x, x, x, U, U, U, x, 0, 0, 0, 0, 0, 0, 0 },
112
113 [Uw] = { x, x, U, x, x, y, 0, 0, 0, 0, 0, 0, 0, 0 },
114 [Uw2] = { x, x, U, U, x, x, y, y, 0, 0, 0, 0, 0, 0 },
115 [Uw3] = { x, x, U, U, U, x, x, y, y, y, 0, 0, 0, 0 },
116 [Dw] = { U, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
117 [Dw2] = { U, U, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
118 [Dw3] = { U, U, U, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
119 [Rw] = { y, y, y, x, U, x, x, x, y, x, 0, 0, 0, 0 },
120 [Rw2] = { y, y, y, x, U, U, x, x, x, y, x, x, 0, 0 },
121 [Rw3] = { y, y, y, x, U, U, U, y, x, x, x, y, 0, 0 },
122 [Lw] = { y, x, U, x, x, x, y, y, y, x, x, x, 0, 0 },
123 [Lw2] = { y, x, U, U, x, x, x, y, y, y, x, x, 0, 0 },
124 [Lw3] = { y, x, U, U, U, x, x, x, y, y, y, x, 0, 0 },
125 [Fw] = { x, x, x, U, y, y, y, x, 0, 0, 0, 0, 0, 0 },
126 [Fw2] = { x, x, x, U, U, y, y, x, 0, 0, 0, 0, 0, 0 },
127 [Fw3] = { x, x, x, U, U, U, y, x, 0, 0, 0, 0, 0, 0 },
128 [Bw] = { x, U, y, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
129 [Bw2] = { x, U, U, y, y, x, x, x, 0, 0, 0, 0, 0, 0 },
130 [Bw3] = { x, U, U, U, y, x, x, x, 0, 0, 0, 0, 0, 0 },
131
132 [M] = { y, x, U, x, x, U, U, U, y, x, y, y, y, 0 },
133 [M2] = { y, x, U, U, x, x, U, U, x, x, x, y, 0, 0 },
134 [M3] = { y, x, U, U, U, x, x, U, y, x, x, x, y, 0 },
135 [S] = { x, U, U, U, x, x, U, y, y, y, x, 0, 0, 0 },
136 [S2] = { x, U, U, x, x, U, U, y, y, x, 0, 0, 0, 0 },
137 [S3] = { x, U, x, x, U, U, U, y, x, 0, 0, 0, 0, 0 },
138 [E] = { U, x, x, U, U, U, x, x, y, y, y, 0, 0, 0 },
139 [E2] = { U, U, x, x, U, U, x, x, y, y, 0, 0, 0, 0 },
140 [E3] = { U, U, U, x, x, U, x, x, y, 0, 0, 0, 0, 0 },
141
142 [x] = { x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
143 [x2] = { x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
144 [x3] = { x, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
145 [y] = { y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
146 [y2] = { y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
147 [y3] = { y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
148 [z] = { y, y, y, x, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
149 [z2] = { y, y, x, x, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
150 [z3] = { y, x, y, y, y, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
151};
152
153/* Movesets */
154bool standard_moveset[NMOVES] = {
155 [U] = true, [U2] = true, [U3] = true, [D] = true, [D2] = true, [D3] = true,
156 [R] = true, [R2] = true, [R3] = true, [L] = true, [L2] = true, [L3] = true,
157 [F] = true, [F2] = true, [F3] = true, [B] = true, [B2] = true, [B3] = true,
158};
159
160bool is_solved_up_to_reorient(Cube cube) {
161 for (int i = 0; i < 25; i++)
162 if (is_solved(apply_alg(rotation_algs[i], cube)))
163 return true;
164 return false;
165}
166
167Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f) {
168 return move_via_arrays((CubeArray)
169 { edge_cycle[m], eofb_flipped[m], eorl_flipped[m], eoud_flipped[m],
170 corner_cycle[m], coud_flipped[m], corl_flipped[m], cofb_flipped[m],
171 center_cycle[m] }, cube, f);
172}
173
174int len(NissMove *alg) {
175 int i;
176 for (i = 0; alg[i].m != NULLMOVE; i++);
177 return i;
178}
179
180int copy_alg(NissMove *src, NissMove *dest) {
181 int i;
182 for (i = 0; src[i].m != NULLMOVE; i++)
183 dest[i] = src[i];
184 dest[i].m = NULLMOVE;
185 return i;
186}
187
188int invert_alg(NissMove *src, NissMove *dest) {
189 int n = len(src);
190 for (int i = 0; i < n; i++)
191 dest[n-i-1] = (NissMove){.m=inverse[src[i].m], .inverse=src[i].inverse};
192 dest[n].m = NULLMOVE;
193 return n;
194}
195
196int concat(NissMove *src1, NissMove *src2, NissMove *dest) {
197 int n1 = len(src1), n2 = len(src2);
198 copy_alg(src1, dest);
199 copy_alg(src2, dest+n1);
200 return n1+n2;
201}
202
203/* TODO: all strings start with space?? */
204void print_alg(NissMove *alg) {
205 bool niss = false;
206 for (int i = 0; alg[i].m != NULLMOVE; i++) {
207 char *fill = !niss && alg[i].inverse ? " (" :
208 (niss && !alg[i].inverse ? ") " : " ");
209 printf("%s%s", fill, move_string[alg[i].m]);
210 niss = alg[i].inverse;
211 }
212 printf("%s\n", niss ? ")" : "");
213}
214
215int read_moves(char *str, NissMove *alg, int n) {
216 bool niss = false;
217 int c = 0;
218
219 for (int i = 0; str[i] && c < n; i++) {
220 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
221 continue;
222
223 if (str[i] == '(' || str[i] == ')') {
224 if ((niss && str[i] == '(') || (!niss && str[i] == ')'))
225 return -1;
226 niss = !niss;
227 continue;
228 }
229
230 alg[c].inverse = niss; alg[c].m = NULLMOVE;
231 for (Move j = 0; j < NMOVES; j++) {
232 if (str[i] == move_string[j][0]) {
233 alg[c].m = j;
234 if (alg[c].m <= B && str[i+1]=='w') { alg[c].m += Uw - U; i++; }
235 if (str[i+1]=='2') { alg[c].m += 1; i++; }
236 else if (str[i+1]=='\'' || str[i+1]=='3') { alg[c].m += 2; i++; }
237 c++;
238 break;
239 }
240 }
241 }
242
243 alg[c].m = NULLMOVE;
244 return c;
245}
246
247/* TODO: rewrite cleanup(). Idea:
248 1. split alg in normal + inverse part, rewriting each with equiv_moves
249 2. shift rotations to the end while transforming all moves in between
250 ARGH! this uses transformation! One more reason to merge everything in
251 one file.
252 3. cancellations
253*/
254
255bool read_ttables_file() {
256 FILE *ttf;
257 long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8,
258 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
259 factorial8, pow3to7, pow3to7, pow3to7, factorial6 };
260 if ((ttf = fopen("ttables", "rb")) != NULL) {
261 bool r = true;
262 for (int m = 0; m < NMOVES; m++) {
263 r = r && fread(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0];
264 r = r && fread(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1];
265 r = r && fread(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2];
266 r = r && fread(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3];
267 r = r && fread(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4];
268 r = r && fread(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5];
269 r = r && fread(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6];
270 r = r && fread(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7];
271 r = r && fread(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8];
272 r = r && fread(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9];
273 r = r && fread(cpos_ttable[m], sizeof(uint16_t), me[10], ttf) == me[10];
274 }
275 fclose(ttf);
276 return r;
277 } else return false;
278}
279
280bool write_ttables_file() {
281 FILE *ttf;
282 long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8,
283 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
284 factorial8, pow3to7, pow3to7, pow3to7, factorial6 };
285 if ((ttf = fopen("ttables", "wb")) != NULL) {
286 bool r = true;
287 for (int m = 0; m < NMOVES; m++) {
288 r = r && fwrite(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0];
289 r = r && fwrite(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1];
290 r = r && fwrite(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2];
291 r = r && fwrite(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3];
292 r = r && fwrite(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4];
293 r = r && fwrite(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5];
294 r = r && fwrite(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6];
295 r = r && fwrite(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7];
296 r = r && fwrite(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8];
297 r = r && fwrite(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9];
298 r = r && fwrite(cpos_ttable[m], sizeof(uint16_t), me[10],ttf) == me[10];
299 }
300 fclose(ttf);
301 return r;
302 } else return false;
303}
304
305void init_ttables(bool read, bool write) {
306 /* Generate all move cycles and flips; I do this regardless */
307 for (int i = 0; i < NMOVES; i++) {
308 if (i == U || i == x || i == y)
309 continue;
310
311 Cube c = {0};
312 for (int j = 0; equiv_moves[i][j]; j++)
313 c = apply_move_cubearray(equiv_moves[i][j], c, pf_all);
314
315 CubeArray arrs = {
316 edge_cycle[i], eofb_flipped[i], eorl_flipped[i], eoud_flipped[i],
317 corner_cycle[i], coud_flipped[i], corl_flipped[i], cofb_flipped[i],
318 center_cycle[i]
319 };
320 cube_to_arrays(c, &arrs, pf_all);
321 }
322
323 if (read)
324 if (read_ttables_file())
325 return;
326
327 /* Initialize transition tables */
328 for (int m = 0; m < NMOVES; m++) {
329 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
330 epose_ttable[m][i] = apply_move_cubearray(m,(Cube){.epose=i},pf_e).epose;
331 eposs_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposs=i},pf_s).eposs;
332 eposm_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposm=i},pf_m).eposm;
333 }
334 for (uint16_t i = 0; i < pow2to11; i++ ) {
335 eofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.eofb=i},pf_eo).eofb;
336 eorl_ttable[m][i] = apply_move_cubearray(m,(Cube){.eorl=i},pf_eo).eorl;
337 eoud_ttable[m][i] = apply_move_cubearray(m,(Cube){.eoud=i},pf_eo).eoud;
338 }
339 for (uint16_t i = 0; i < pow3to7; i++) {
340 coud_ttable[m][i] = apply_move_cubearray(m,(Cube){.coud=i},pf_co).coud;
341 corl_ttable[m][i] = apply_move_cubearray(m,(Cube){.corl=i},pf_co).corl;
342 cofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.cofb=i},pf_co).cofb;
343 }
344 for (uint16_t i = 0; i < factorial8; i++)
345 cp_ttable[m][i] = apply_move_cubearray(m,(Cube){.cp=i},pf_cp).cp;
346 for (uint16_t i = 0; i < factorial6; i++)
347 cpos_ttable[m][i] = apply_move_cubearray(m,(Cube){.cpos=i},pf_cpos).cpos;
348 }
349
350 if (write)
351 if (!write_ttables_file())
352 printf("Error in writing ttables: file not writable\n");
353}
354
355Cube move_cube(Move m, Cube cube) {
356 Cube moved = {0};
357
358 moved.epose = epose_ttable[m][cube.epose];
359 moved.eposs = eposs_ttable[m][cube.eposs];
360 moved.eposm = eposm_ttable[m][cube.eposm];
361 moved.eofb = eofb_ttable[m][cube.eofb];
362 moved.eorl = eorl_ttable[m][cube.eorl];
363 moved.eoud = eoud_ttable[m][cube.eoud];
364 moved.coud = coud_ttable[m][cube.coud];
365 moved.cofb = cofb_ttable[m][cube.cofb];
366 moved.corl = corl_ttable[m][cube.corl];
367 moved.cp = cp_ttable[m][cube.cp];
368 moved.cpos = cpos_ttable[m][cube.cpos];
369
370 return moved;
371}
372
373Cube apply_alg_filtered(NissMove *alg, Cube cube, PieceFilter f) {
374 Cube ret = {0};
375 for (int i = 0; alg[i].m != NULLMOVE; i++)
376 if (alg[i].inverse)
377 ret = move_cube(alg[i].m, ret);
378
379 ret = compose_filtered(cube, inverse_cube(ret), f);
380
381 for (int i = 0; alg[i].m != NULLMOVE; i++)
382 if (!alg[i].inverse)
383 ret = move_cube(alg[i].m, ret);
384 return ret;
385}
386
387Cube apply_alg(NissMove *alg, Cube cube) {
388 return apply_alg_filtered(alg, cube, pf_all);
389}
390
391void init_aux_tables() {
392 /* Commute */
393 for (int i = 0; i < NMOVES; i++)
394 for (int j = 0; j < NMOVES; j++)
395 commute[i][j] = equal(move_cube(i, move_cube(j, (Cube){0})),
396 move_cube(j, move_cube(i, (Cube){0})));
397
398 /* Possible next (if the sequence i j k is valid) */
399 for (int i = 0; i < NMOVES; i++)
400 for (int j = 0; j < NMOVES; j++)
401 for (int k = 0; k < NMOVES; k++)
402 possible_next[i][j][k] =
403 (j == 0) ||
404 (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) &&
405 !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3)));
406
407 /* Inverse */
408 for (int i = 0; i < NMOVES; i++)
409 inverse[i] = i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3);
410
411}
412
diff --git a/old/2021-05-26-before-restyle/moves.h b/old/2021-05-26-before-restyle/moves.h
new file mode 100644
index 0000000..0608e1b
--- /dev/null
+++ b/old/2021-05-26-before-restyle/moves.h
@@ -0,0 +1,51 @@
1#ifndef MOVES_H
2#define MOVES_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "cube.h"
8#include "utils.h"
9
10#define NMOVES (z3+1)
11
12typedef enum {
13 NULLMOVE,
14 U, U2, U3, D, D2, D3, R, R2, R3, L, L2, L3, F, F2, F3, B, B2, B3,
15 Uw, Uw2, Uw3, Dw, Dw2, Dw3, Rw, Rw2, Rw3,
16 Lw, Lw2, Lw3, Fw, Fw2, Fw3, Bw, Bw2, Bw3,
17 M, M2, M3, S, S2, S3, E, E2, E3,
18 x, x2, x3, y, y2, y3, z, z2, z3,
19} Move;
20
21/* An alg is an array of "NissMoves", which can be on normal or on inverse. */
22typedef struct { bool inverse; Move m; } NissMove;
23
24/* Movesets */
25extern bool standard_moveset[NMOVES];
26
27extern bool commute[NMOVES][NMOVES];
28extern bool possible_next[NMOVES][NMOVES][NMOVES];
29extern Move inverse[NMOVES];
30extern NissMove rotation_algs[24][3]; /* Same order as transformations */
31
32int len(NissMove *alg);
33int copy_alg(NissMove *src, NissMove *dest); /*return number of moves copied */
34int invert_alg(NissMove *src, NissMove *dest);
35int concat(NissMove *src1, NissMove *src2, NissMove *dest);
36void print_alg(NissMove *alg);
37int read_moves(char *str, NissMove *alg, int n); /* reads at most n moves */
38void cleanup(NissMove *src, int n); /* rewrites using basic moves, at most n */
39
40bool is_solved_up_to_reorient(Cube cube);
41Cube move_cube(Move m, Cube cube);
42Cube apply_alg(NissMove *alg, Cube cube);
43Cube apply_alg_filtered(NissMove *alg, Cube cube, PieceFilter f);
44
45/* Merge the following two?
46 always in this order */
47void init_ttables(bool read, bool write);
48void init_aux_tables();
49
50
51#endif
diff --git a/old/2021-05-26-before-restyle/solve.c b/old/2021-05-26-before-restyle/solve.c
new file mode 100644
index 0000000..31bd779
--- /dev/null
+++ b/old/2021-05-26-before-restyle/solve.c
@@ -0,0 +1,180 @@
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, (Cube){0}))))) {
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, (Cube){0})))
79 a[ia++] = i;
80 else
81 b[ib++] = i;
82 }
83 }
84 intarrcopy(a, (int *)sd->sorted_moves, ia);
85 intarrcopy(b, (int *)sd->sorted_moves+ia, ib);
86 sd->sorted_moves[ia+ib] = NULLMOVE;
87 }
88
89 sd->max_solutions = min(sd->max_solutions, MAXS);
90 /*TODO
91 Cube rotated = apply_alg(sd->pre_rotation, (Cube){0});
92 cube = apply_alg(inverse_cube(rotated), compose(cube, rotated));
93 */
94
95 uint64_t ret = 0;
96 for (int i=sd->min_moves; i<=sd->max_moves&&!(ret&&sd->optimal_only); i++) {
97 DfsData dd = { .d = i, .n = &ret };
98 solve_dfs(cube, sd, dd);
99 }
100
101 /* TODO: transform solutions with inverse of pre_rotation */
102 /*
103 for (uint64_t i = 0; i < ret; i++) {
104 if (sd->cleanup)
105 cleanup(sd->solutions[i], sd->max_moves*3);
106 }*/
107
108 return ret;
109}
110
111void prune_dfs(Cube cube, PruneData *pd, DfsData dd) {
112 uint64_t ind = pd->index(cube);
113 if ((!ind || pd->ptable[ind]) && pd->ptable[ind] != dd.m)
114 return;
115 if (dd.m == dd.d) {
116 if (ind && !pd->ptable[ind]) {
117 pd->ptable[ind] = dd.m;
118 (*dd.n)++;
119 }
120 return;
121 }
122
123 for (int i = 0; i < NMOVES; i++) {
124 if (dd.m<20)
125 if (possible_next[dd.last2][dd.last1][i] && pd->available[i]) {
126 DfsData nn = { .m = dd.m+1, .d = dd.d, .n = dd.n,
127 .last1 = i, .last2 = dd.last1 };
128 prune_dfs(move_cube(i, cube), pd, nn);
129 }
130 }
131}
132
133void init_ptable(PruneData *pd, bool read, bool write) {
134 if (read) {
135 FILE *ptf;
136 if ((ptf = fopen(pd->fname, "rb")) != NULL) {
137 uint64_t r = fread(pd->ptable, sizeof(uint8_t), pd->n, ptf);
138 fclose(ptf);
139 if (r == pd->n) return;
140 }
141 }
142
143 /* TODO: for now it behaves always as if copressed = false */
144 for (uint64_t i = 0; i < pd->n; i++)
145 pd->ptable[i] = 0;
146
147 uint64_t s = 1;
148 for (int i = 1; i < pd->max_moves && s < pd->n; i++) {
149 DfsData dd = { .d = i, .n = &s };
150 prune_dfs((Cube){0}, pd, dd);
151 }
152
153 if (write) {
154 FILE *ptf;
155 if ((ptf = fopen(pd->fname, "wb")) != NULL) {
156 fwrite(pd->ptable, sizeof(uint8_t), pd->n, ptf);
157 fclose(ptf);
158 return;
159 }
160 }
161}
162
163/* Solving steps (and indexing functions) */
164
165uint64_t index_eofb(Cube cube) { return cube.eofb; }
166int f_eofb(Cube cube) {
167 static bool initialized_ptable;
168 static uint8_t pt_eofb[pow2to11];
169 if (!initialized_ptable) {
170 PruneData pd = {
171 .compressed = false, .available = standard_moveset, .max_moves = 13,
172 .ptable = pt_eofb, .n = pow2to11, .index = index_eofb,
173 .fname = "ptable_eofb"
174 };
175 init_ptable(&pd, false, true);
176 initialized_ptable = true;
177 }
178 return cube.eofb ? pt_eofb[cube.eofb] : 0;
179}
180
diff --git a/old/2021-05-26-before-restyle/solve.h b/old/2021-05-26-before-restyle/solve.h
new file mode 100644
index 0000000..0b59cc2
--- /dev/null
+++ b/old/2021-05-26-before-restyle/solve.h
@@ -0,0 +1,59 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include <stdlib.h>
5#include "cube.h"
6#include "moves.h"
7#include "transformations.h"
8
9/* Maximum number of moves per solution and of solutions */
10#define MAXM 30
11#define MAXS 999
12
13/* Data for solving a step:
14 - can_niss is true niss can be used, false otherwise.
15 - optimal_only if true, dynamically updates max_moves so non-optimal
16 solutions are discarded.
17 - cleanup determines whether the cleaunup() function should be used on
18 the found solutions before returning.
19 - available[m] is true if the move m can be used, false otherwise.
20 (Rename to moveset[]?)
21 - min_moves and max_moves are the minimum and maximum number of moves that
22 can be used.
23 - max_solution is the maximum number of solutions that can be returned.
24 - precondition can be used to check wheter the step can actually be applied
25 to the cube. If it returns false, solve() stops immediately returning -1.
26 - f must return 0 if and only if the step is solve, otherwise it must return
27 a lower bound for the number of moves required (without niss).
28 - sorted_moves[] can be used to specify in which order moves are tried
29 by the solving algorithm (for example if one wants to always try F' before
30 F). If sorted_moves[0] == NULLMOVE, the list is generated automatically.
31 It is advised to list first all the moves that actually influence the
32 solved state of the step (this is the default choice). This is in order to
33 avoid cases like B2 F for EO and to NISS only when it makes sense.
34 - start_moves [Currently unused, REMOVE]
35 are the moves that will be used as first moves of all
36 solutions. For example giving R' U' F (F' U R) will generate FMC scrambles
37 and y (y) will solve the step on another axis.
38 - pre_rotation are the rotations to apply before the scamble to solve
39 the step wrt a different orientation
40 - pre_rotation are the rotations to apply before the scamble to solve
41 the step wth respect to a different orientation.
42 TODO: cange name
43 - solutions[][] is the array where to store the found solutions. */
44typedef struct {
45 bool can_niss, optimal_only, cleanup, *available;
46 int min_moves, max_moves, max_solutions;
47 int (*f)(Cube);
48 bool (*precondition)(Cube);
49 Move sorted_moves[NMOVES];
50 Transformation pre_rotation;
51 NissMove solutions[MAXS][MAXM];
52} SolveData;
53
54int solve(Cube cube, SolveData *data); /* Returns the number of solutions. */
55
56/* Steps */
57int f_eofb(Cube cube);
58
59#endif
diff --git a/old/2021-05-26-before-restyle/transformations.c b/old/2021-05-26-before-restyle/transformations.c
new file mode 100644
index 0000000..c457f0c
--- /dev/null
+++ b/old/2021-05-26-before-restyle/transformations.c
@@ -0,0 +1,200 @@
1#include "transformations.h"
2
3int edge_slice(int e); /* Return slice (e=0, s=1, m=2) to which e belongs */
4Cube rotate_via_compose(Transformation r, Cube c, PieceFilter f);
5bool read_rtables_file();
6bool write_rtables_file();
7
8/* Values mod 3 to determine from which side to take the state to convert */
9int epose_source[NTRANS]; /* 0 = epose, 1 = eposs, 2 = eposm */
10int eposs_source[NTRANS];
11int eposm_source[NTRANS];
12int eofb_source[NTRANS]; /* 0 = eoud, 1 = eorl, 2 = eofb */
13int eorl_source[NTRANS];
14int eoud_source[NTRANS];
15int coud_source[NTRANS]; /* 0 = coud, 1 = corl, 2 = cofb */
16int cofb_source[NTRANS];
17int corl_source[NTRANS];
18
19/* Transition tables for rotations (n+1 is mirror) */
20uint16_t epose_rtable[NTRANS][factorial12/factorial8];
21uint16_t eposs_rtable[NTRANS][factorial12/factorial8];
22uint16_t eposm_rtable[NTRANS][factorial12/factorial8];
23uint16_t eo_rtable[NTRANS][pow2to11];
24uint16_t cp_rtable[NTRANS][factorial8];
25uint16_t co_rtable[NTRANS][pow3to7];
26uint16_t cpos_rtable[NTRANS][factorial6];
27
28/* Same for moves */
29uint16_t moves_rtable[NTRANS][NMOVES];
30
31NissMove rotation_niss[NTRANS][6];
32
33int edge_slice(int e) {
34 if (e == FR || e == FL || e == BL || e == BR)
35 return 0;
36 if (e == UR || e == UL || e == DR || e == DL)
37 return 1;
38 return 2;
39}
40
41Cube rotate_via_compose(Transformation r, Cube c, PieceFilter f) {
42 if (r != mirror) {
43 return apply_alg_filtered(rotation_niss[r], c, f);
44 } else {
45 static int zero12[12] = {0,0,0,0,0,0,0,0,0,0,0,0},
46 zero8[12] = {0,0,0,0,0,0,0,0},
47 mirror_ep[12] = {UF,UR,UB,UL,DF,DR,DB,DL,FL,FR,BR,BL},
48 mirror_cp[8] = {UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL},
49 mirror_cpos[6] =
50 {U_center,D_center,L_center,R_center,F_center,B_center};
51 return move_via_arrays((CubeArray){
52 .ep = mirror_ep, .eofb = zero12, .eorl = zero12, .eoud = zero12,
53 .cp = mirror_cp, .coud = zero8, .corl = zero8, .cofb = zero8,
54 .cpos = mirror_cpos}, c, f);
55 }
56}
57
58bool read_rtables_file() {
59 FILE *ttf;
60 long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8,
61 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
62 factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES };
63 if ((ttf = fopen("rtables", "rb")) != NULL) {
64 bool r = true;
65 for (int m = 0; m < NTRANS; m++) {
66 r = r && fread(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0];
67 r = r && fread(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1];
68 r = r && fread(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2];
69 r = r && fread(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
70 r = r && fread(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6];
71 r = r && fread(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
72 r = r && fread(cpos_rtable[m], sizeof(uint16_t), me[10], ttf) == me[10];
73 r = r && fread(moves_rtable[m], sizeof(uint16_t), me[11], ttf) == me[11];
74 }
75 fclose(ttf);
76 return r;
77 } else return false;
78}
79
80bool write_rtables_file() {
81 FILE *ttf;
82 long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8,
83 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
84 factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES };
85 if ((ttf = fopen("rtables", "wb")) != NULL) {
86 bool r = true;
87 for (int m = 0; m < NTRANS; m++) {
88 r = r && fwrite(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0];
89 r = r && fwrite(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1];
90 r = r && fwrite(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2];
91 r = r && fwrite(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
92 r = r && fwrite(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6];
93 r = r && fwrite(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
94 r = r && fwrite(cpos_rtable[m], sizeof(uint16_t), me[10],ttf) == me[10];
95 r = r && fwrite(moves_rtable[m], sizeof(uint16_t), me[11],ttf) == me[11];
96 }
97 fclose(ttf);
98 return r;
99 } else return false;
100}
101
102void init_transformations(bool read, bool write) {
103 /* Compute sources */
104 for (int i = 0; i < NTRANS; i++) {
105 Cube cube = {0};
106 if (i != mirror)
107 cube = apply_alg(rotation_algs[i], (Cube){0});
108 epose_source[i] = edge_slice(edge_at(cube, FR));
109 eposs_source[i] = edge_slice(edge_at(cube, UR));
110 eposm_source[i] = edge_slice(edge_at(cube, UF));
111 eofb_source[i] = center_at(cube, F_center)/2;
112 eorl_source[i] = center_at(cube, R_center)/2;
113 eoud_source[i] = center_at(cube, U_center)/2;
114 coud_source[i] = center_at(cube, U_center)/2;
115 cofb_source[i] = center_at(cube, F_center)/2;
116 corl_source[i] = center_at(cube, R_center)/2;
117 }
118
119 /*TODO: maybe move down*/
120 /* Compute rotation_niss array, necessary for rotate_via_compose */
121 for (int r = 0; r != mirror; r++) {
122 concat(rotation_algs[r], rotation_algs[r], rotation_niss[r]);
123 for (int i = len(rotation_algs[r]); rotation_niss[r][i].m != NULLMOVE; i++)
124 rotation_niss[r][i].inverse = true;
125 }
126
127 /* If I can read tables from file, I stop here */
128 if (read)
129 if (read_rtables_file())
130 return;
131
132 /* Initialize tables */
133 for (int m = 0; m < NTRANS; m++) {
134 int eparr[12] = {0,0,0,0,0,0,0,0,0,0,0,0}, cparr[8] = {0,0,0,0,0,0,0,0};
135 CubeArray epcp = { .ep = eparr, .cp = cparr };
136 cube_to_arrays(apply_alg(rotation_algs[m], (Cube){0}), &epcp,
137 (PieceFilter){.epose=true,.eposs=true,.eposm=true,.cp=true});
138 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
139 Cube c[3] = { admissible_ep((Cube){ .epose = i}, pf_e),
140 admissible_ep((Cube){ .eposs = i}, pf_s),
141 admissible_ep((Cube){ .eposm = i}, pf_m) };
142 epose_rtable[m][i]=rotate_via_compose(m,c[epose_source[m]],pf_ep).epose;
143 eposs_rtable[m][i]=rotate_via_compose(m,c[eposs_source[m]],pf_ep).eposs;
144 eposm_rtable[m][i]=rotate_via_compose(m,c[eposm_source[m]],pf_ep).eposm;
145 }
146 for (uint16_t i = 0; i < pow2to11; i++ ) {
147 int eoarr[12];
148 int_to_sum_zero_array(i, 2, 12, eoarr);
149 apply_permutation(eparr, eoarr, 12);
150 eo_rtable[m][i] = digit_array_to_int(eoarr, 11, 2);
151 }
152 for (uint16_t i = 0; i < pow3to7; i++) {
153 int coarr[12];
154 int_to_sum_zero_array(i, 3, 8, coarr);
155 apply_permutation(cparr, coarr, 8);
156 co_rtable[m][i] = digit_array_to_int(coarr, 7, 3);
157 }
158 for (uint16_t i = 0; i < factorial8; i++)
159 cp_rtable[m][i] = rotate_via_compose(m, (Cube){.cp=i}, pf_cp).cp;
160 for (uint16_t i = 0; i < factorial6; i++)
161 cpos_rtable[m][i] = rotate_via_compose(m, (Cube){.cpos=i}, pf_cpos).cpos;
162 for (Move i = 0; i < NMOVES; i++) {
163 Cube aux = transform_cube(m, move_cube(i, (Cube){0}));
164 for (Move move = 0; move < NMOVES; move++)
165 if (is_solved(move_cube(inverse[move], aux)))
166 moves_rtable[m][i] = move;
167 }
168 }
169
170 if (write)
171 if (!write_rtables_file())
172 printf("Error in writing rtables: file not writable\n");
173}
174
175Cube transform_cube(Transformation t, Cube cube) {
176 Cube transformed = {0};
177
178 uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm },
179 aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb },
180 aux_co[3] = { cube.coud, cube.corl, cube.cofb };
181
182 transformed.epose = epose_rtable[t][aux_epos[epose_source[t]]];
183 transformed.eposs = eposs_rtable[t][aux_epos[eposs_source[t]]];
184 transformed.eposm = eposm_rtable[t][aux_epos[eposm_source[t]]];
185 transformed.eofb = eo_rtable[t][aux_eo[eofb_source[t]]];
186 transformed.eorl = eo_rtable[t][aux_eo[eorl_source[t]]];
187 transformed.eoud = eo_rtable[t][aux_eo[eoud_source[t]]];
188 transformed.coud = co_rtable[t][aux_co[coud_source[t]]];
189 transformed.corl = co_rtable[t][aux_co[corl_source[t]]];
190 transformed.cofb = co_rtable[t][aux_co[cofb_source[t]]];
191 transformed.cp = cp_rtable[t][cube.cp];
192 transformed.cpos = cpos_rtable[t][cube.cpos];
193
194 return transformed;
195}
196
197void transform_alg(Transformation t, NissMove *alg) {
198 for (int i = 0; alg[i].m; i++)
199 alg[i].m = moves_rtable[t][alg[i].m];
200}
diff --git a/old/2021-05-26-before-restyle/transformations.h b/old/2021-05-26-before-restyle/transformations.h
new file mode 100644
index 0000000..c673257
--- /dev/null
+++ b/old/2021-05-26-before-restyle/transformations.h
@@ -0,0 +1,34 @@
1#ifndef TRANSFORMATIONS_H
2#define TRANSFORMATIONS_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "cube.h"
8#include "moves.h"
9#include "utils.h"
10
11#define NTRANS (mirror+1)
12
13/* Letters indicate top and front centers
14 * Mirror is wrt rl
15 * Lowercase letter to distinguish from pieces */
16
17typedef enum {
18 uf, ur, ub, ul,
19 df, dr, db, dl,
20 rf, rd, rb, ru,
21 lf, ld, lb, lu,
22 fu, fr, fd, fl,
23 bu, br, bd, bl,
24 mirror,
25} Transformation;
26
27void print_transformation(Transformation t);
28
29Cube transform_cube(Transformation t, Cube cube);
30void transform_alg(Transformation t, NissMove *alg); /* Applied in-place */
31
32void init_transformations(bool read, bool write);
33
34#endif
diff --git a/old/2021-05-26-before-restyle/utils.c b/old/2021-05-26-before-restyle/utils.c
new file mode 100644
index 0000000..66de9ad
--- /dev/null
+++ b/old/2021-05-26-before-restyle/utils.c
@@ -0,0 +1,197 @@
1#include "utils.h"
2
3void swap(int *a, int *b) {
4 int aux = *a;
5 *a = *b;
6 *b = aux;
7}
8
9void intarrcopy(int *src, int *dst, int n) {
10 for (int i = 0; i < n; i++)
11 dst[i] = src[i];
12}
13
14int sum(int *a, int n) {
15 int ret = 0;
16 for (int i = 0; i < n; i++)
17 ret += a[i];
18 return ret;
19}
20
21bool is_perm(int *a, int n) {
22 int aux[n]; for (int i = 0; i < n; i++) aux[i] = 0;
23 for (int i = 0; i < n; i++)
24 if (a[i] < 0 || a[i] >= n)
25 return false;
26 else
27 aux[a[i]] = 1;
28 for (int i = 0; i < n; i++)
29 if (!aux[i])
30 return false;
31 return true;
32}
33
34bool is_subset(int *a, int n, int k) {
35 int sum = 0;
36 for (int i = 0; i < n; i++)
37 sum += a[i] ? 1 : 0;
38 return sum == k;
39}
40
41int powint(int a, int b) {
42 return 0;
43 if (b == 0 || a == 1)
44 return 1;
45 if (a == 0)
46 return 0;
47 if (b < 0)
48 return 0; /* Immediate truncate (integer part is 0) */
49 if (b % 2) {
50 return a * powint(a, b-1);
51 } else {
52 int x = powint(a, b/2);
53 return x*x;
54 }
55}
56
57int factorial(int n) {
58 if (n < 0)
59 return 0;
60 int ret = 1;
61 for (int i = 1; i <= n; i++)
62 ret *= i;
63 return ret;
64}
65
66int binomial(int n, int k) {
67 if (n < 0 || k < 0 || k > n)
68 return 0;
69 return factorial(n) / (factorial(k) * factorial(n-k));
70}
71
72void int_to_digit_array(int a, int b, int n, int *r) {
73 if (b <= 1)
74 for (int i = 0; i < n; i++)
75 r[i] = 0;
76 else
77 for (int i = 0; i < n; i++, a /= b)
78 r[i] = a % b;
79}
80
81int digit_array_to_int(int *a, int n, int b) {
82 int ret = 0, p = 1;
83 for (int i = 0; i < n; i++, p *= b)
84 ret += a[i] * p;
85 return ret;
86}
87
88int perm_to_index(int *a, int n) {
89 if (!is_perm(a, n))
90 return factorial(n); /* Error */
91 int ret = 0;
92 for (int i = 0; i < n; i++) {
93 int c = 0;
94 for (int j = i+1; j < n; j++)
95 c += (a[i] > a[j]) ? 1 : 0;
96 ret += factorial(n-i-1) * c;
97 }
98 return ret;
99}
100
101void index_to_perm(int p, int n, int *r) {
102 if (p < 0 || p >= factorial(n)) /* Error */
103 for (int i = 0; i < n; i++)
104 r[i] = -1;
105 int a[n]; for (int j = 0; j < n; j++) a[j] = 0; /* picked elements */
106 for (int i = 0; i < n; i++) {
107 int c = 0, j = 0;
108 while (c <= p / factorial(n-i-1))
109 c += a[j++] ? 0 : 1;
110 r[i] = j-1;
111 a[j-1] = 1;
112 p %= factorial(n-i-1);
113 }
114}
115
116int perm_sign(int *a, int n) {
117 if (!is_perm(a,n))
118 return false;
119 int ret = 0;
120 for (int i = 0; i < n; i++)
121 for (int j = i+1; j < n; j++)
122 ret += (a[i]>a[j]) ? 1 : 0;
123 return ret % 2;
124}
125
126int subset_to_index(int *a, int n, int k) {
127 /* TODO: better checks */
128 if (!is_subset(a, n, k))
129 return binomial(n, k); /* Error */
130 int ret = 0;
131 for (int i = 0; i < n; i++) {
132 if (k == n-i)
133 return ret;
134 if (a[i]) {
135 /*ret += factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
136 ret += binomial(n-i-1, k);
137 k--;
138 }
139 }
140 return ret;
141}
142
143void index_to_subset(int s, int n, int k, int *r) {
144 if (s < 0 || s >= binomial(n, k)) { /* Error */
145 for (int i = 0; i < n; i++)
146 r[i] = -1;
147 return;
148 }
149 for (int i = 0; i < n; i++) {
150 if (k == n-i) {
151 for (int j = i; j < n; j++)
152 r[j] = 1;
153 return;
154 }
155 if (k == 0) {
156 for (int j = i; j < n; j++)
157 r[j] = 0;
158 return;
159 }
160 /*int v = factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
161 int v = binomial(n-i-1, k);
162 if (s >= v) {
163 r[i] = 1;
164 k--;
165 s -= v;
166 } else {
167 r[i] = 0;
168 }
169 }
170}
171
172void int_to_sum_zero_array(int x, int b, int n, int *a) {
173 if (b <= 1) {
174 for (int i = 0; i < n; i++)
175 a[i] = 0;
176 } else {
177 int_to_digit_array(x, b, n-1, a);
178 int s = 0;
179 for (int i = 0; i < n - 1; i++)
180 s = (s + a[i]) % b;
181 a[n-1] = (b - s) % b;
182 }
183}
184
185void apply_permutation(int *perm, int *set, int n) {
186 if (!is_perm(perm, n))
187 return;
188 int aux[n];
189 for (int i = 0; i < n; i++)
190 aux[i] = set[perm[i]];
191 intarrcopy(aux, set, n);
192}
193
194void sum_arrays_mod(int *a, int *b, int n, int m) {
195 for (int i = 0; i < n; i++)
196 b[i] = (m <= 0) ? 0 : (a[i] + b[i]) % m;
197}
diff --git a/old/2021-05-26-before-restyle/utils.h b/old/2021-05-26-before-restyle/utils.h
new file mode 100644
index 0000000..4b6df8c
--- /dev/null
+++ b/old/2021-05-26-before-restyle/utils.h
@@ -0,0 +1,70 @@
1/* General utility functions */
2
3#ifndef UTILS_H
4#define UTILS_H
5
6#include <stdbool.h>
7
8#define min(a,b) (((a) < (b)) ? (a) : (b))
9#define max(a,b) (((a) > (b)) ? (a) : (b))
10
11/* Some useful constants */
12#define pow2to11 2048
13#define pow2to12 4096
14#define pow3to7 2187
15#define pow3to8 6561
16#define pow12to4 20736
17#define factorial4 24
18#define factorial6 720
19#define factorial8 40320
20#define factorial12 479001600
21#define binom12on4 495
22#define binom8on4 70
23
24/* Generic utility functions */
25void swap(int *a, int *b);
26void intarrcopy(int *src, int *dst, int n);
27int sum(int *a, int n);
28bool is_perm(int *a, int n);
29bool is_perm(int *a, int n);
30
31
32/* Standard mathematical functions */
33int powint(int a, int b);
34int factorial(int n);
35int binomial(int n, int k);
36
37/* Converts the integer a to its representation in base b (first n digits
38 * only) and saves the result in r. */
39void int_to_digit_array(int a, int b, int n, int *r);
40int digit_array_to_int(int *a, int n, int b);
41
42/* Converts the first n-1 digits of a number to an array a of digits in base b;
43 * then adds one element to the array, so that the sum of the elements of a is
44 * zero modulo b.
45 * This is used for determing the edge orientation from an 11-bits integer or
46 * the corner orientation from a 7-trits integer. */
47void int_to_sum_zero_array(int x, int b, int n, int *a);
48
49/* Converts a permutation on [0..(n-1)] into the integer i which is the index
50 * of the permutation in the sorted list of all n! such permutations. */
51int perm_to_index(int *a, int n);
52void index_to_perm(int p, int n, int *r);
53
54/* Determine the sign of a permutation */
55int perm_sign(int a[], int n);
56
57/* Converts a k-element subset of a set from an array of n elements, of which k
58 * are 1 and n-k are 0, to its index in the sorted list of all such subsets. */
59int subset_to_index(int *a, int n, int k);
60void index_to_subset(int s, int n, int k, int *r);
61
62int ordered_subset_to_index(int *a, int n, int k);
63void index_to_ordered_subset(int s, int n, int k, int *r);
64
65void apply_permutation(int *perm, int *set, int n);
66
67/* b[i] = (a[i]+b[i])%m for i=1,...,n */
68void sum_arrays_mod(int *a, int *b, int n, int m);
69
70#endif

Generated with cgit - Back to sebastiano.tronto.net