aboutsummaryrefslogtreecommitdiff
path: root/old/2021-02-28-transformcube-works/src
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-02-28-transformcube-works/src
parent3568412f8f230774d0d11d7ed1c897424f95d3ef (diff)
downloadnissy-4fb67201414169a2687f41c4056b2e284b4938cb.tar.gz
nissy-4fb67201414169a2687f41c4056b2e284b4938cb.zip
Removed old files
Diffstat (limited to '')
-rw-r--r--old/2021-02-28-transformcube-works/src/cube.c271
-rw-r--r--old/2021-02-28-transformcube-works/src/cube.h55
-rw-r--r--old/2021-02-28-transformcube-works/src/main.c57
-rw-r--r--old/2021-02-28-transformcube-works/src/moves.c489
-rw-r--r--old/2021-02-28-transformcube-works/src/moves.h50
-rw-r--r--old/2021-02-28-transformcube-works/src/solve.c180
-rw-r--r--old/2021-02-28-transformcube-works/src/solve.h56
-rw-r--r--old/2021-02-28-transformcube-works/src/transformations.c224
-rw-r--r--old/2021-02-28-transformcube-works/src/transformations.h34
-rw-r--r--old/2021-02-28-transformcube-works/src/utils.c197
-rw-r--r--old/2021-02-28-transformcube-works/src/utils.h70
11 files changed, 0 insertions, 1683 deletions
diff --git a/old/2021-02-28-transformcube-works/src/cube.c b/old/2021-02-28-transformcube-works/src/cube.c
deleted file mode 100644
index 649a4de..0000000
--- a/old/2021-02-28-transformcube-works/src/cube.c
+++ /dev/null
@@ -1,271 +0,0 @@
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
118Center center_at(Cube cube, Center c) {
119 static CubeArrayAllocated all = {0};
120 CubeArray arr = {0};
121 allocate_cubearray(&arr, &all);
122 cube_to_arrays(cube, &arr, pf_cpos);
123 return arr.cpos[c];
124}
125
126Edge edge_at(Cube cube, Edge e) {
127 static CubeArrayAllocated all = {0};
128 CubeArray arr = {0};
129 allocate_cubearray(&arr, &all);
130 cube_to_arrays(cube, &arr, pf_ep);
131 return arr.ep[e];
132}
133
134Corner corner_at(Cube cube, Corner c) {
135 static CubeArrayAllocated all = {0};
136 CubeArray arr = {0};
137 allocate_cubearray(&arr, &all);
138 cube_to_arrays(cube, &arr, pf_cp);
139 return arr.cp[c];
140}
141
142bool equal(Cube c1, Cube c2) {
143 return c1.eofb == c2.eofb && c1.epose == c2.epose &&
144 c1.eposs == c2.eposs && c1.eposm == c2.eposm &&
145 c1.coud == c2.coud && c1.cp == c2.cp &&
146 c1.cpos == c2.cpos;
147}
148
149bool is_solvable(Cube cube) {
150 static CubeArrayAllocated all = {0};
151 CubeArray arrx = {0};
152 allocate_cubearray(&arrx, &all);
153 cube_to_arrays(cube, &arrx, pf_all);
154
155 /* Since we memorize orientation truncating the last digit, we only need to
156 * check that the permutations have the correct sign. */
157 /* TODO: I should also check that the different eos and cos are compatible */
158 return (perm_sign(arrx.ep,12)^perm_sign(arrx.cpos,6))==perm_sign(arrx.cp,8);
159}
160
161bool is_solved(Cube cube) {
162 /* TODO: might return true if cube is not solvable but looks solved form one
163 of the incompatible interpretations (e.g. eofb and ep solved, but
164 eorl not solve) */
165 return !cube.eofb && !cube.coud && !cube.cp &&
166 !cube.epose && !cube.eposs && !cube.eposm && cube.cpos;
167}
168
169void print_cube(Cube cube) {
170 static CubeArrayAllocated all = {0};
171 CubeArray arrx = {0};
172 allocate_cubearray(&arrx, &all);
173
174 cube_to_arrays(cube, &arrx, pf_all);
175
176/*
177 for (int i = 0; i < 12; i++) printf("%d ", arrx.ep[i]);
178 printf("\n");*/
179
180 for (int i = 0; i < 12; i++) printf(" %s ", edge_string[arrx.ep[i]]);
181 printf("\n");
182 for (int i = 0; i < 12; i++) printf(" %c ", arrx.eofb[i] + '0');
183 printf("\n");
184 for (int i = 0; i < 8; i++) printf("%s ", corner_string[arrx.cp[i]]);
185 printf("\n");
186 for (int i = 0; i < 8; i++) printf(" %c ", arrx.coud[i] + '0');
187 printf("\n");
188 for (int i = 0; i < 6; i++) printf(" %s ", center_string[arrx.cpos[i]]);
189 printf("\n");
190}
191
192Cube admissible_ep(Cube cube, PieceFilter f) {
193 static CubeArrayAllocated all = {0};
194 CubeArray arrx = {0};
195 allocate_cubearray(&arrx, &all);
196 cube_to_arrays(cube, &arrx, f);
197
198 bool used[12] = {0};
199 for (int i = 0; i < 12; i++)
200 if (arrx.ep[i] != -1)
201 used[arrx.ep[i]] = true;
202 for (int i = 0, j = 0; i < 12; i++) {
203 while (j < 11 && used[j]) j++;
204 if (arrx.ep[i] == -1)
205 arrx.ep[i] = j++;
206 }
207
208 return arrays_to_cube(arrx, pf_ep);
209}
210
211Cube inverse_cube(Cube cube) {
212 static CubeArrayAllocated all = {0}, invall = {0};
213 CubeArray arrx = {0}, invx = {0};
214 allocate_cubearray(&arrx, &all);
215 allocate_cubearray(&invx, &invall);
216
217 cube_to_arrays(cube, &arrx, pf_all);
218
219 for (int i = 0; i < 12; i++) {
220 invx.ep[arrx.ep[i]] = i;
221 invx.eofb[arrx.ep[i]] = arrx.eofb[i];
222 invx.eorl[arrx.ep[i]] = arrx.eorl[i];
223 invx.eoud[arrx.ep[i]] = arrx.eoud[i];
224 }
225 for (int i = 0; i < 8; i++) {
226 invx.cp[arrx.cp[i]] = i;
227 invx.coud[arrx.cp[i]] = (3 - arrx.coud[i])%3;
228 invx.corl[arrx.cp[i]] = (3 - arrx.corl[i])%3;
229 invx.cofb[arrx.cp[i]] = (3 - arrx.cofb[i])%3;
230 }
231 for (int i = 0; i < 6; i++)
232 invx.cpos[arrx.cpos[i]] = i;
233
234 return arrays_to_cube(invx, pf_all);
235}
236
237Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter f) {
238 static CubeArrayAllocated all = {0};
239 CubeArray arrx = {0};
240 allocate_cubearray(&arrx, &all);
241
242 cube_to_arrays(c, &arrx, f);
243
244 if (f.epose || f.eposs || f.eposm)
245 apply_permutation( arr.ep, arrx.ep, 12 );
246 if (f.eofb) { apply_permutation( arr.ep, arrx.eofb, 12 );
247 sum_arrays_mod( arr.eofb, arrx.eofb, 12, 2 ); }
248 if (f.eorl) { apply_permutation( arr.ep, arrx.eorl, 12 );
249 sum_arrays_mod( arr.eorl, arrx.eorl, 12, 2 ); }
250 if (f.eoud) { apply_permutation( arr.ep, arrx.eoud, 12 );
251 sum_arrays_mod( arr.eoud, arrx.eoud, 12, 2 ); }
252 if (f.cp) apply_permutation( arr.cp, arrx.cp, 8 );
253 if (f.coud) { apply_permutation( arr.cp, arrx.coud, 8 );
254 sum_arrays_mod( arr.coud, arrx.coud, 8, 3 ); }
255 if (f.corl) { apply_permutation( arr.cp, arrx.corl, 8 );
256 sum_arrays_mod( arr.corl, arrx.corl, 8, 3 ); }
257 if (f.cofb) { apply_permutation( arr.cp, arrx.cofb, 8 );
258 sum_arrays_mod( arr.cofb, arrx.cofb, 8, 3 ); }
259 if (f.cpos) apply_permutation( arr.cpos, arrx.cpos, 6 );
260
261 return arrays_to_cube(arrx, f);
262}
263
264Cube compose(Cube c2, Cube c1) {
265 static CubeArrayAllocated all = {0};
266 CubeArray arrx = {0};
267 allocate_cubearray(&arrx, &all);
268
269 cube_to_arrays(c2, &arrx, pf_all);
270 return move_via_arrays(arrx, c1, pf_all);
271}
diff --git a/old/2021-02-28-transformcube-works/src/cube.h b/old/2021-02-28-transformcube-works/src/cube.h
deleted file mode 100644
index 3229eae..0000000
--- a/old/2021-02-28-transformcube-works/src/cube.h
+++ /dev/null
@@ -1,55 +0,0 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "utils.h"
8
9typedef enum {U_center,D_center,R_center,L_center,F_center,B_center} Center;
10typedef enum { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge;
11typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner;
12
13typedef struct {
14 uint16_t eofb, eorl, eoud, coud, cofb, corl,
15 epose, eposs, eposm, cp, cpos;
16} Cube;
17
18typedef struct {
19 bool epose, eposs, eposm, eofb, eorl, eoud, cp, coud, cofb, corl, cpos;
20} PieceFilter;
21
22typedef struct {
23 int *ep, *eofb, *eorl, *eoud, *cp, *coud, *corl, *cofb, *cpos;
24} CubeArray;
25
26extern PieceFilter pf_all, pf_cpos, pf_ep, pf_cp,
27 pf_e, pf_s, pf_m, pf_eo, pf_co;
28
29void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
30Cube arrays_to_cube(CubeArray arr, PieceFilter f);
31
32Center center_at(Cube cube, Center c);
33Edge edge_at(Cube cube, Edge e);
34Corner corner_at(Cube cube, Corner c);
35/* Aggiungi funzioni per "queries" sul cubo: se pezzo è orientato rispetto ad
36 un certo asse, se il pezzo è risolto... */
37/* Would be nice: a funciton block_solved(Cube c, Block b), where Block is
38 something like struct {bool centers[6], edges[12], corners[8]}
39 (The advantage over checking pieces one by one is that I can convert
40 to cubearray only once and for all) */
41/* Altro TODO, ma forse non ne vale la pena: pre-calcolare tutti i possibili
42 valori per questi, e salvare i risultati in array (facile per cp e cpos,
43 mentre per ep bisogna anche cercare quale tra epose, eposs e eposm contiene
44 il valore giusto) */
45
46bool equal(Cube c1, Cube c2);
47bool is_solvable(Cube cube);
48bool is_solved(Cube cube);
49void print_cube(Cube cube);
50Cube admissible_ep(Cube cube, PieceFilter f); /* Returns admissible ep */
51Cube inverse_cube(Cube cube);
52Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */
53Cube move_via_arrays(CubeArray arr, Cube c, PieceFilter pf);
54
55#endif
diff --git a/old/2021-02-28-transformcube-works/src/main.c b/old/2021-02-28-transformcube-works/src/main.c
deleted file mode 100644
index 56f3f3b..0000000
--- a/old/2021-02-28-transformcube-works/src/main.c
+++ /dev/null
@@ -1,57 +0,0 @@
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] = "MR U' B2 Bw F z xE2 M' x Dw' y Fw2";*/
14
15 /*char moves[100] = "M'U2MU2";*/
16 char moves[100] = "R' D2 F2 U2 R F2 R D2 L' R2 D2 F D' L' U' B R' D' U R' B";
17 NissMove alg[100];
18 read_moves(moves, alg, 100);
19 Cube cube = apply_alg(alg, (Cube){0});
20 print_cube(cube);
21 cube = transform_cube(rd, cube);
22 print_cube(cube);
23
24 /*f_eofb(cube);*/
25
26
27 /*
28 SolveData d = { .optimal_only = true, .available = standard_moveset,
29 .max_moves = 10,
30 .cleanup = true,
31 .max_solutions = 10,
32 .f = f_eofb };
33 read_moves("y", d.pre_rotation, 2);
34 int n = solve(cube, &d);
35 printf("%d solutions found:\n", n);
36 for (int i = 0; i < n; i++)
37 print_moves(d.solutions[i]);
38 */
39
40/*
41 NissMove a[5], b[5];
42 read_moves("R", a, 5);
43 read_moves("U", b, 5);
44 Cube c1 = apply_alg(a,(Cube){0}), c2 = apply_alg(b,(Cube){0});
45 print_cube(compose(c2,c1));
46 print_cube(compose(c1,c2));
47
48 NissMove nm[10];
49 read_moves("y(y)RU", nm, 10);
50
51 print_moves(nm);
52 cleanup(nm, 10);
53 print_moves(nm);
54 */
55
56 return 0;
57}
diff --git a/old/2021-02-28-transformcube-works/src/moves.c b/old/2021-02-28-transformcube-works/src/moves.c
deleted file mode 100644
index 4b0eee1..0000000
--- a/old/2021-02-28-transformcube-works/src/moves.c
+++ /dev/null
@@ -1,489 +0,0 @@
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_moves(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/* Helper function for cleanup. alg must contain only basic moves, no 2 or '.
248 top and front describe an admissible orientation of the cube. *
249void sort_cancel_rotate(NissMove *alg, int n, bool inv, int top, int front) {
250 int c = 0, i = 0;
251 PieceFilter cpos_only = { .cpos = true };
252 NissMove aux[n+3];
253 aux[0].m = NULLMOVE;
254
255 while (i < n && alg[i].m != NULLMOVE) {
256 int j = i;
257 while (j < n && commute[alg[i].m][alg[j].m]) j++;
258 Move base = 6*((alg[i].m-1)/6);
259 int t1 = 0, t2 = 0;
260 for (int k = i; k < j; k++)
261 if (alg[k].m == base+1) t1 = (t1+1)%4;
262 else t2 = (t2+1)%4;
263 if (t1) { aux[c].inverse = inv; aux[c].m = base+t1; c++; }
264 if (t2) { aux[c].inverse = inv; aux[c].m = base+t2+3; c++; }
265 i = j;
266 }
267 aux[c].m = NULLMOVE;
268
269 CubeArray q;
270 cube_to_arrays((Cube){0}, &q, cpos_only);
271 * First we try to rotate in one move, then we try an x or y rotation
272 followed by a z rotation
273 TODO: change once I implement the "is_rotaton(Move) function" *
274 for (int r = x; r <= z3; r++) {
275 move_cubearray(r, &q, cpos_only);
276 if (q.cpos[F_center] == front && q.cpos[U_center] == top) {
277 aux[c].inverse = inv; aux[c].m = r;
278
279 aux[++c].m = NULLMOVE;
280 copy_alg(aux, alg);
281 return;
282 }
283 move_cubearray(inverse[r], &q, cpos_only);
284 }
285 for (int r = x; r <= y3; r++) {
286 move_cubearray(r, &q, cpos_only);
287 if (q.cpos[F_center] == front) {
288 aux[c].inverse = inv; aux[c++].m = r;
289 break;
290 }
291 move_cubearray(inverse[r], &q, cpos_only);
292 }
293 for (int r = z; r <= z3; r++) {
294 move_cubearray(r, &q, cpos_only);
295 if (q.cpos[U_center] == top) {
296 aux[c].inverse = inv; aux[c++].m = r;
297 break;
298 }
299 move_cubearray(inverse[r], &q, cpos_only);
300 }
301
302 aux[c].m = NULLMOVE;
303 copy_alg(aux, alg);
304}
305
306* TODO: does not work with niss + rotations *
307void cleanup(NissMove *alg, int n) {
308 int count_n = 0, count_i = 0, *count;
309 PieceFilter cpos_only = { .cpos = true };
310 NissMove aux_n[n+1], aux_i[n+1], *aux;
311 CubeArray cube_n, cube_i, *cube;
312 cube_to_arrays((Cube){0}, &cube_n, cpos_only);
313 cube_to_arrays((Cube){0}, &cube_i, cpos_only);
314
315 for (int i = 0; count_n + count_i < n && alg[i].m != NULLMOVE; i++) {
316 if (alg[i].inverse) { count = &count_i; aux = aux_i; cube = &cube_i; }
317 else { count = &count_n; aux = aux_n; cube = &cube_n; }
318
319 for (int j = 0; equiv_moves[alg[i].m][j]; j++) {
320 Move m = equiv_moves[alg[i].m][j];
321 aux[*count].inverse = alg[i].inverse;
322 move_cubearray(m, cube, cpos_only);
323 if (m == U) aux[(*count)++].m = 3 * cube->cpos[0] + 1;
324 }
325 }
326
327 aux_n[count_n].m = NULLMOVE;
328 aux_i[count_i].m = NULLMOVE;
329 sort_cancel_rotate(aux_n, count_n, false, cube_n.cpos[0], cube_n.cpos[4]);
330 sort_cancel_rotate(aux_i, count_i, true, cube_i.cpos[0], cube_n.cpos[4]);
331 copy_alg(aux_n, alg);
332 copy_alg(aux_i, alg+count_n);
333}
334*/
335
336bool read_ttables_file() {
337 FILE *ttf;
338 long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8,
339 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
340 factorial8, pow3to7, pow3to7, pow3to7, factorial6 };
341 if ((ttf = fopen("ttables", "rb")) != NULL) {
342 bool r = true;
343 for (int m = 0; m < NMOVES; m++) {
344 r = r && fread(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0];
345 r = r && fread(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1];
346 r = r && fread(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2];
347 r = r && fread(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3];
348 r = r && fread(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4];
349 r = r && fread(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5];
350 r = r && fread(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6];
351 r = r && fread(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7];
352 r = r && fread(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8];
353 r = r && fread(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9];
354 r = r && fread(cpos_ttable[m], sizeof(uint16_t), me[10], ttf) == me[10];
355 }
356 fclose(ttf);
357 return r;
358 } else return false;
359}
360
361bool write_ttables_file() {
362 FILE *ttf;
363 long unsigned int me[11] = { factorial12/factorial8, factorial12/factorial8,
364 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
365 factorial8, pow3to7, pow3to7, pow3to7, factorial6 };
366 if ((ttf = fopen("ttables", "wb")) != NULL) {
367 bool r = true;
368 for (int m = 0; m < NMOVES; m++) {
369 r = r && fwrite(epose_ttable[m], sizeof(uint16_t), me[0], ttf) == me[0];
370 r = r && fwrite(eposs_ttable[m], sizeof(uint16_t), me[1], ttf) == me[1];
371 r = r && fwrite(eposm_ttable[m], sizeof(uint16_t), me[2], ttf) == me[2];
372 r = r && fwrite(eofb_ttable[m], sizeof(uint16_t), me[3], ttf) == me[3];
373 r = r && fwrite(eorl_ttable[m], sizeof(uint16_t), me[4], ttf) == me[4];
374 r = r && fwrite(eoud_ttable[m], sizeof(uint16_t), me[5], ttf) == me[5];
375 r = r && fwrite(cp_ttable[m], sizeof(uint16_t), me[6], ttf) == me[6];
376 r = r && fwrite(coud_ttable[m], sizeof(uint16_t), me[7], ttf) == me[7];
377 r = r && fwrite(corl_ttable[m], sizeof(uint16_t), me[8], ttf) == me[8];
378 r = r && fwrite(cofb_ttable[m], sizeof(uint16_t), me[9], ttf) == me[9];
379 r = r && fwrite(cpos_ttable[m], sizeof(uint16_t), me[10],ttf) == me[10];
380 }
381 fclose(ttf);
382 return r;
383 } else return false;
384}
385
386void init_ttables(bool read, bool write) {
387 /* Generate all move cycles and flips; I do this regardless */
388 for (int i = 0; i < NMOVES; i++) {
389 if (i == U || i == x || i == y)
390 continue;
391
392 Cube c = {0};
393 for (int j = 0; equiv_moves[i][j]; j++)
394 c = apply_move_cubearray(equiv_moves[i][j], c, pf_all);
395
396 CubeArray arrs = {
397 edge_cycle[i], eofb_flipped[i], eorl_flipped[i], eoud_flipped[i],
398 corner_cycle[i], coud_flipped[i], corl_flipped[i], cofb_flipped[i],
399 center_cycle[i]
400 };
401 cube_to_arrays(c, &arrs, pf_all);
402 }
403
404 if (read)
405 if (read_ttables_file())
406 return;
407
408 /* Initialize transition tables */
409 for (int m = 0; m < NMOVES; m++) {
410 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
411 epose_ttable[m][i] = apply_move_cubearray(m,(Cube){.epose=i},pf_e).epose;
412 eposs_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposs=i},pf_s).eposs;
413 eposm_ttable[m][i] = apply_move_cubearray(m,(Cube){.eposm=i},pf_m).eposm;
414 }
415 for (uint16_t i = 0; i < pow2to11; i++ ) {
416 eofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.eofb=i},pf_eo).eofb;
417 eorl_ttable[m][i] = apply_move_cubearray(m,(Cube){.eorl=i},pf_eo).eorl;
418 eoud_ttable[m][i] = apply_move_cubearray(m,(Cube){.eoud=i},pf_eo).eoud;
419 }
420 for (uint16_t i = 0; i < pow3to7; i++) {
421 coud_ttable[m][i] = apply_move_cubearray(m,(Cube){.coud=i},pf_co).coud;
422 corl_ttable[m][i] = apply_move_cubearray(m,(Cube){.corl=i},pf_co).corl;
423 cofb_ttable[m][i] = apply_move_cubearray(m,(Cube){.cofb=i},pf_co).cofb;
424 }
425 for (uint16_t i = 0; i < factorial8; i++)
426 cp_ttable[m][i] = apply_move_cubearray(m,(Cube){.cp=i},pf_cp).cp;
427 for (uint16_t i = 0; i < factorial6; i++)
428 cpos_ttable[m][i] = apply_move_cubearray(m,(Cube){.cpos=i},pf_cpos).cpos;
429 }
430
431 if (write)
432 if (!write_ttables_file())
433 printf("Error in writing ttables: file not writable\n");
434}
435
436Cube move_cube(Move m, Cube cube) {
437 Cube moved = {0};
438
439 moved.epose = epose_ttable[m][cube.epose];
440 moved.eposs = eposs_ttable[m][cube.eposs];
441 moved.eposm = eposm_ttable[m][cube.eposm];
442 moved.eofb = eofb_ttable[m][cube.eofb];
443 moved.eorl = eorl_ttable[m][cube.eorl];
444 moved.eoud = eoud_ttable[m][cube.eoud];
445 moved.coud = coud_ttable[m][cube.coud];
446 moved.cofb = cofb_ttable[m][cube.cofb];
447 moved.corl = corl_ttable[m][cube.corl];
448 moved.cp = cp_ttable[m][cube.cp];
449 moved.cpos = cpos_ttable[m][cube.cpos];
450
451 return moved;
452}
453
454Cube apply_alg(NissMove *alg, Cube cube) {
455 Cube ret = {0};
456 for (int i = 0; alg[i].m != NULLMOVE; i++)
457 if (alg[i].inverse)
458 ret = move_cube(alg[i].m, ret);
459
460 ret = compose(cube, inverse_cube(ret));
461
462 for (int i = 0; alg[i].m != NULLMOVE; i++)
463 if (!alg[i].inverse)
464 ret = move_cube(alg[i].m, ret);
465 return ret;
466}
467
468void init_aux_tables() {
469 /* Commute */
470 for (int i = 0; i < NMOVES; i++)
471 for (int j = 0; j < NMOVES; j++)
472 commute[i][j] = equal(move_cube(i, move_cube(j, (Cube){0})),
473 move_cube(j, move_cube(i, (Cube){0})));
474
475 /* Possible next (if the sequence i j k is valid) */
476 for (int i = 0; i < NMOVES; i++)
477 for (int j = 0; j < NMOVES; j++)
478 for (int k = 0; k < NMOVES; k++)
479 possible_next[i][j][k] =
480 (j == 0) ||
481 (j != 0 && (j-(j-1)%3) != (k-(k-1)%3) &&
482 !(i != 0 && commute[i][j] && (i-(i-1)%3) == (k-(k-1)%3)));
483
484 /* Inverse */
485 for (int i = 0; i < NMOVES; i++)
486 inverse[i] = i == NULLMOVE ? NULLMOVE : i + 2 - 2*((i-1)%3);
487
488}
489
diff --git a/old/2021-02-28-transformcube-works/src/moves.h b/old/2021-02-28-transformcube-works/src/moves.h
deleted file mode 100644
index c1489a1..0000000
--- a/old/2021-02-28-transformcube-works/src/moves.h
+++ /dev/null
@@ -1,50 +0,0 @@
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_moves(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);
43
44/* Merge the following two?
45 always in this order */
46void init_ttables(bool read, bool write);
47void init_aux_tables();
48
49
50#endif
diff --git a/old/2021-02-28-transformcube-works/src/solve.c b/old/2021-02-28-transformcube-works/src/solve.c
deleted file mode 100644
index 07c9075..0000000
--- a/old/2021-02-28-transformcube-works/src/solve.c
+++ /dev/null
@@ -1,180 +0,0 @@
1#include "solve.h"
2
3/* Data for creating a pruning table:
4 - compressed: if set to true, each entry occupies only 4 bits, but values
5 larger than 15 cannot be stored.
6 - available[] is the list of availabel moves, as above.
7 - *ptable is the actual table to fill.
8 - n is the number of states (size of ptable).
9 - index must "linearize" the cube, i.e. return its index in ptable.
10 - fname is the name of the file where to store the table */
11typedef struct {
12 bool compressed, *available;
13 int max_moves;
14 uint8_t *ptable;
15 uint64_t n;
16 uint64_t (*index)(Cube);
17 char *fname;
18} PruneData;
19
20/* TODO: comment this */
21typedef struct {
22 bool niss;
23 int m, d;
24 uint64_t *n;
25 Move last1, last2;
26} DfsData;
27
28void solve_dfs(Cube cube, SolveData *sd, DfsData dd);
29void init_ptable(PruneData *pd, bool read, bool write);
30
31/* Search solutions of lenght exactly d */
32void solve_dfs(Cube cube, SolveData *sd, DfsData dd) {
33 if (*dd.n >= sd->max_solutions ||
34 ((!sd->can_niss || dd.niss) && dd.m + sd->f(cube) > dd.d))
35 return;
36
37 (sd->solutions[*dd.n][dd.m]).inverse = dd.niss;
38 (sd->solutions[*dd.n][dd.m]).m = NULLMOVE;
39
40 if (!sd->f(cube)) { /* Solved */
41 if (dd.m == dd.d) {
42 (*dd.n)++;
43 if (*dd.n < sd->max_solutions)
44 copy_alg(sd->solutions[*dd.n-1], sd->solutions[*dd.n]);
45 }
46 return;
47 }
48
49 for (int i = 0; i < NMOVES && sd->sorted_moves[i] != NULLMOVE; i++) {
50 Move move = sd->sorted_moves[i];
51 if (possible_next[dd.last2][dd.last1][move]) {
52 sd->solutions[*dd.n][dd.m].inverse = dd.niss;
53 sd->solutions[*dd.n][dd.m].m = move;
54 DfsData nn = { .niss = dd.niss, .m = dd.m+1, .d = dd.d, .n = dd.n,
55 .last1 = move, .last2 = dd.last1 };
56 solve_dfs(move_cube(move, cube), sd, nn);
57 }
58 }
59
60 if (sd->can_niss && !dd.niss &&
61 (!dd.m || (dd.m && sd->f(move_cube(dd.last1, (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; }
166uint16_t 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-02-28-transformcube-works/src/solve.h b/old/2021-02-28-transformcube-works/src/solve.h
deleted file mode 100644
index d585a8e..0000000
--- a/old/2021-02-28-transformcube-works/src/solve.h
+++ /dev/null
@@ -1,56 +0,0 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include <stdlib.h>
5#include "cube.h"
6#include "moves.h"
7
8/* Maximum number of moves per solution and of solutions */
9#define MAXM 30
10#define MAXS 999
11
12/* Data for solving a step:
13 - can_niss is true niss can be used, false otherwise.
14 - optimal_only if true, dynamically updates max_moves so non-optimal
15 solutions are discarded.
16 - cleanup determines whether the cleaunup() function should be used on
17 the found solutions before returning.
18 - available[m] is true if the move m can be used, false otherwise.
19 - min_moves and max_moves are the minimum and maximum number of moves that
20 can be used.
21 - max_solution is the maximum number of solutions that can be returned.
22 - precondition can be used to check wheter the step can actually be applied
23 to the cube. If it returns false, solve() stops immediately returning -1.
24 - f must return 0 if and only if the step is solve, otherwise it must return
25 a lower bound for the number of moves required (without niss).
26 - sorted_moves[] can be used to specify in which order moves are tried
27 by the solving algorithm (for example if one wants to always try F' before
28 F). If sorted_moves[0] == NULLMOVE, the list is generated automatically.
29 It is advised to list first all the moves that actually influence the
30 solved state of the step (this is the default choice). This is in order to
31 avoid cases like B2 F for EO and to NISS only when it makes sense.
32 - start_moves [Currently unused, REMOVE]
33 are the moves that will be used as first moves of all
34 solutions. For example giving R' U' F (F' U R) will generate FMC scrambles
35 and y (y) will solve the step on another axis.
36 - pre_rotation are the rotations to apply before the scamble to solve
37 the step wrt a different orientation
38 - pre_rotation are the rotations to apply before the scamble to solve
39 the step wth respect to a different orientation.
40 - solutions[][] is the array where to store the found solutions. */
41typedef struct {
42 bool can_niss, optimal_only, cleanup, *available;
43 int min_moves, max_moves;
44 uint64_t max_solutions;
45 bool (*precondition)(Cube);
46 uint16_t (*f)(Cube);
47 Move sorted_moves[NMOVES];
48 NissMove pre_rotation[3], solutions[MAXS][MAXM];
49} SolveData;
50
51int solve(Cube cube, SolveData *data); /* Returns the number of solutions. */
52
53/* Steps */
54uint16_t f_eofb(Cube cube);
55
56#endif
diff --git a/old/2021-02-28-transformcube-works/src/transformations.c b/old/2021-02-28-transformcube-works/src/transformations.c
deleted file mode 100644
index 9ae10e9..0000000
--- a/old/2021-02-28-transformcube-works/src/transformations.c
+++ /dev/null
@@ -1,224 +0,0 @@
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);
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[NROTATIONS]; /* 0 = epose, 1 = eposs, 2 = eposm */
10int eposs_source[NROTATIONS];
11int eposm_source[NROTATIONS];
12int eofb_source[NROTATIONS]; /* 0 = eoud, 1 = eorl, 2 = eofb */
13int eorl_source[NROTATIONS];
14int eoud_source[NROTATIONS];
15int coud_source[NROTATIONS]; /* 0 = coud, 1 = corl, 2 = cofb */
16int cofb_source[NROTATIONS];
17int corl_source[NROTATIONS];
18
19/* Transition tables for rotations (n+1 is mirror) */
20uint16_t epose_rtable[NROTATIONS][factorial12/factorial8];
21uint16_t eposs_rtable[NROTATIONS][factorial12/factorial8];
22uint16_t eposm_rtable[NROTATIONS][factorial12/factorial8];
23uint16_t eo_rtable[NROTATIONS][pow2to11];
24/*uint16_t eofb_rtable[NROTATIONS][pow2to11];
25uint16_t eorl_rtable[NROTATIONS][pow2to11];
26uint16_t eoud_rtable[NROTATIONS][pow2to11];*/
27uint16_t cp_rtable[NROTATIONS][factorial8];
28uint16_t co_rtable[NROTATIONS][pow3to7];
29/*uint16_t coud_rtable[NROTATIONS][pow3to7];
30uint16_t cofb_rtable[NROTATIONS][pow3to7];
31uint16_t corl_rtable[NROTATIONS][pow3to7];*/
32uint16_t cpos_rtable[NROTATIONS][factorial6];
33
34/* Same for moves */
35uint16_t move_rtable[NROTATIONS][NMOVES];
36
37NissMove rotation_niss[NROTATIONS][6];
38
39int edge_slice(int e) {
40 if (e == FR || e == FL || e == BL || e == BR)
41 return 0;
42 if (e == UR || e == UL || e == DR || e == DL)
43 return 1;
44 return 2;
45}
46
47Cube rotate_via_compose(Transformation r, Cube c) {
48 if (r != mirror) {
49 return apply_alg(rotation_niss[r], c);
50 } else {
51 static int zero12[12] = {0,0,0,0,0,0,0,0,0,0,0,0},
52 zero8[12] = {0,0,0,0,0,0,0,0},
53 mirror_ep[12] = {UF,UR,UB,UL,DF,DR,DB,DL,FL,FR,BR,BL},
54 mirror_cp[8] = {UFL, UFR, UBR, UBL, DFL, DFR, DBR, DBL},
55 mirror_cpos[6] =
56 {U_center,D_center,L_center,R_center,F_center,B_center};
57 return move_via_arrays((CubeArray){
58 .ep = mirror_ep, .eofb = zero12, .eorl = zero12, .eoud = zero12,
59 .cp = mirror_cp, .coud = zero8, .corl = zero8, .cofb = zero8,
60 .cpos = mirror_cpos}, c, pf_all);
61 }
62}
63
64bool read_rtables_file() {
65 FILE *ttf;
66 long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8,
67 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
68 factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES };
69 if ((ttf = fopen("rtables", "rb")) != NULL) {
70 bool r = true;
71 for (int m = 0; m < NROTATIONS; m++) {
72 r = r && fread(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0];
73 r = r && fread(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1];
74 r = r && fread(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2];
75 r = r && fread(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
76 /*r = r && fread(eofb_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
77 r = r && fread(eorl_rtable[m], sizeof(uint16_t), me[4], ttf) == me[4];
78 r = r && fread(eoud_rtable[m], sizeof(uint16_t), me[5], ttf) == me[5];*/
79 r = r && fread(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6];
80 r = r && fread(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
81 /*r = r && fread(coud_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
82 r = r && fread(corl_rtable[m], sizeof(uint16_t), me[8], ttf) == me[8];
83 r = r && fread(cofb_rtable[m], sizeof(uint16_t), me[9], ttf) == me[9];*/
84 r = r && fread(cpos_rtable[m], sizeof(uint16_t), me[10], ttf) == me[10];
85 r = r && fread(move_rtable[m], sizeof(uint16_t), me[11], ttf) == me[11];
86 }
87 fclose(ttf);
88 return r;
89 } else return false;
90}
91
92bool write_rtables_file() {
93 FILE *ttf;
94 long unsigned int me[12] = { factorial12/factorial8, factorial12/factorial8,
95 factorial12/factorial8, pow2to11, pow2to11, pow2to11,
96 factorial8, pow3to7, pow3to7, pow3to7, factorial6, NMOVES };
97 if ((ttf = fopen("rtables", "wb")) != NULL) {
98 bool r = true;
99 for (int m = 0; m < NROTATIONS; m++) {
100 r = r && fwrite(epose_rtable[m], sizeof(uint16_t), me[0], ttf) == me[0];
101 r = r && fwrite(eposs_rtable[m], sizeof(uint16_t), me[1], ttf) == me[1];
102 r = r && fwrite(eposm_rtable[m], sizeof(uint16_t), me[2], ttf) == me[2];
103 r = r && fwrite(eo_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
104 /*r = r && fwrite(eofb_rtable[m], sizeof(uint16_t), me[3], ttf) == me[3];
105 r = r && fwrite(eorl_rtable[m], sizeof(uint16_t), me[4], ttf) == me[4];
106 r = r && fwrite(eoud_rtable[m], sizeof(uint16_t), me[5], ttf) == me[5];*/
107 r = r && fwrite(cp_rtable[m], sizeof(uint16_t), me[6], ttf) == me[6];
108 r = r && fwrite(co_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
109 /*r = r && fwrite(coud_rtable[m], sizeof(uint16_t), me[7], ttf) == me[7];
110 r = r && fwrite(corl_rtable[m], sizeof(uint16_t), me[8], ttf) == me[8];
111 r = r && fwrite(cofb_rtable[m], sizeof(uint16_t), me[9], ttf) == me[9];*/
112 r = r && fwrite(cpos_rtable[m], sizeof(uint16_t), me[10],ttf) == me[10];
113 r = r && fwrite(move_rtable[m], sizeof(uint16_t), me[11],ttf) == me[11];
114 }
115 fclose(ttf);
116 return r;
117 } else return false;
118}
119
120void init_transformations(bool read, bool write) {
121 /* Compute sources */
122 for (int i = 0; i < NROTATIONS; i++) {
123 Cube cube = {0};
124 if (i != mirror)
125 cube = apply_alg(rotation_algs[i], (Cube){0});
126 epose_source[i] = edge_slice(edge_at(cube, FR));
127 eposs_source[i] = edge_slice(edge_at(cube, UR));
128 eposm_source[i] = edge_slice(edge_at(cube, UF));
129 eofb_source[i] = center_at(cube, F_center)/2;
130 eorl_source[i] = center_at(cube, R_center)/2;
131 eoud_source[i] = center_at(cube, U_center)/2;
132 coud_source[i] = center_at(cube, U_center)/2;
133 cofb_source[i] = center_at(cube, F_center)/2;
134 corl_source[i] = center_at(cube, R_center)/2;
135 }
136
137 /*TODO: maybe move down*/
138 /* Compute rotation_niss array, necessary for rotate_via_compose */
139 for (int r = 0; r != mirror; r++) {
140 concat(rotation_algs[r], rotation_algs[r], rotation_niss[r]);
141 for (int i = len(rotation_algs[r]); rotation_niss[r][i].m != NULLMOVE; i++)
142 rotation_niss[r][i].inverse = true;
143 }
144
145 /* If I can read tables from file, I stop here */
146 if (read)
147 if (read_rtables_file())
148 return;
149
150 /* Initialize tables */
151 for (int m = 0; m < NROTATIONS; m++) {
152 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};
153 CubeArray epcp = { .ep = eparr, .cp = cparr };
154 cube_to_arrays(apply_alg(rotation_algs[m], (Cube){0}), &epcp,
155 (PieceFilter){.epose=true,.eposs=true,.eposm=true,.cp=true});
156 for (uint16_t i = 0; i < factorial12/factorial8; i++) {
157 Cube c[3] = { admissible_ep((Cube){ .epose = i}, pf_e),
158 admissible_ep((Cube){ .eposs = i}, pf_s),
159 admissible_ep((Cube){ .eposm = i}, pf_m) };
160 epose_rtable[m][i] = rotate_via_compose(m, c[epose_source[m]]).epose;
161 eposs_rtable[m][i] = rotate_via_compose(m, c[eposs_source[m]]).eposs;
162 eposm_rtable[m][i] = rotate_via_compose(m, c[eposm_source[m]]).eposm;
163 }
164 for (uint16_t i = 0; i < pow2to11; i++ ) {
165 int eoarr[12];
166 int_to_sum_zero_array(i, 2, 12, eoarr);
167 apply_permutation(eparr, eoarr, 12);
168 eo_rtable[m][i] = digit_array_to_int(eoarr, 11, 2);
169 /*Cube c[3] = {(Cube){.eoud=i}, (Cube){.eorl=i}, (Cube){.eofb=i}};
170 eofb_rtable[m][i] = apply_alg(rotation_algs[m], (Cube){.eofb=i}).eofb;
171 eorl_rtable[m][i] = rotate_via_compose(m, c[eorl_source[m]]).eorl;
172 eoud_rtable[m][i] = rotate_via_compose(m, c[eoud_source[m]]).eoud;*/
173 }
174 for (uint16_t i = 0; i < pow3to7; i++) {
175 int coarr[12];
176 int_to_sum_zero_array(i, 3, 8, coarr);
177 apply_permutation(cparr, coarr, 8);
178 co_rtable[m][i] = digit_array_to_int(coarr, 8, 3);
179 /*Cube c[3] = {(Cube){.coud=i}, (Cube){.corl=i}, (Cube){.cofb=i}};
180 coud_rtable[m][i] = rotate_via_compose(m, c[coud_source[m]]).coud;
181 corl_rtable[m][i] = rotate_via_compose(m, c[corl_source[m]]).corl;
182 cofb_rtable[m][i] = rotate_via_compose(m, c[cofb_source[m]]).cofb;*/
183 }
184 for (uint16_t i = 0; i < factorial8; i++)
185 cp_rtable[m][i] = rotate_via_compose(m, (Cube){.cp=i}).cp;
186 for (uint16_t i = 0; i < factorial6; i++)
187 cpos_rtable[m][i] = rotate_via_compose(m, (Cube){.cpos=i}).cpos;
188 }
189
190 if (write)
191 if (!write_rtables_file())
192 printf("Error in writing rtables: file not writable\n");
193}
194
195Cube transform_cube(Transformation t, Cube cube) {
196 Cube transformed = {0};
197
198 uint16_t aux_epos[3] = { cube.epose, cube.eposs, cube.eposm },
199 aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb },
200 aux_co[3] = { cube.coud, cube.corl, cube.cofb };
201
202 transformed.epose = epose_rtable[t][aux_epos[epose_source[t]]];
203 transformed.eposs = eposs_rtable[t][aux_epos[eposs_source[t]]];
204 transformed.eposm = eposm_rtable[t][aux_epos[eposm_source[t]]];
205 transformed.eofb = eo_rtable[t][aux_eo[eofb_source[t]]];
206 transformed.eorl = eo_rtable[t][aux_eo[eorl_source[t]]];
207 transformed.eoud = eo_rtable[t][aux_eo[eoud_source[t]]];
208 transformed.coud = co_rtable[t][aux_co[coud_source[t]]];
209 transformed.corl = co_rtable[t][aux_co[corl_source[t]]];
210 transformed.cofb = co_rtable[t][aux_co[cofb_source[t]]];
211 transformed.cp = cp_rtable[t][cube.cp];
212 transformed.cpos = cpos_rtable[t][cube.cpos];
213
214/*
215 printf("%d\n", coud_source[t]);
216 int ccc[8];
217 int_to_sum_zero_array(cube.cofb, 3, 8, ccc);
218 for (int i = 0; i < 8; i++)
219 printf("%d ", ccc[i]);
220 printf("\n");
221 */
222
223 return transformed;
224}
diff --git a/old/2021-02-28-transformcube-works/src/transformations.h b/old/2021-02-28-transformcube-works/src/transformations.h
deleted file mode 100644
index c42cc34..0000000
--- a/old/2021-02-28-transformcube-works/src/transformations.h
+++ /dev/null
@@ -1,34 +0,0 @@
1#ifndef TRANSFORMATIONS_H
2#define TRANSFORMATIONS_H
3
4#include <stdio.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include "cube.h"
8#include "moves.h"
9#include "utils.h"
10
11#define NROTATIONS (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-02-28-transformcube-works/src/utils.c b/old/2021-02-28-transformcube-works/src/utils.c
deleted file mode 100644
index 66de9ad..0000000
--- a/old/2021-02-28-transformcube-works/src/utils.c
+++ /dev/null
@@ -1,197 +0,0 @@
1#include "utils.h"
2
3void swap(int *a, int *b) {
4 int aux = *a;
5 *a = *b;
6 *b = aux;
7}
8
9void intarrcopy(int *src, int *dst, int n) {
10 for (int i = 0; i < n; i++)
11 dst[i] = src[i];
12}
13
14int sum(int *a, int n) {
15 int ret = 0;
16 for (int i = 0; i < n; i++)
17 ret += a[i];
18 return ret;
19}
20
21bool is_perm(int *a, int n) {
22 int aux[n]; for (int i = 0; i < n; i++) aux[i] = 0;
23 for (int i = 0; i < n; i++)
24 if (a[i] < 0 || a[i] >= n)
25 return false;
26 else
27 aux[a[i]] = 1;
28 for (int i = 0; i < n; i++)
29 if (!aux[i])
30 return false;
31 return true;
32}
33
34bool is_subset(int *a, int n, int k) {
35 int sum = 0;
36 for (int i = 0; i < n; i++)
37 sum += a[i] ? 1 : 0;
38 return sum == k;
39}
40
41int powint(int a, int b) {
42 return 0;
43 if (b == 0 || a == 1)
44 return 1;
45 if (a == 0)
46 return 0;
47 if (b < 0)
48 return 0; /* Immediate truncate (integer part is 0) */
49 if (b % 2) {
50 return a * powint(a, b-1);
51 } else {
52 int x = powint(a, b/2);
53 return x*x;
54 }
55}
56
57int factorial(int n) {
58 if (n < 0)
59 return 0;
60 int ret = 1;
61 for (int i = 1; i <= n; i++)
62 ret *= i;
63 return ret;
64}
65
66int binomial(int n, int k) {
67 if (n < 0 || k < 0 || k > n)
68 return 0;
69 return factorial(n) / (factorial(k) * factorial(n-k));
70}
71
72void int_to_digit_array(int a, int b, int n, int *r) {
73 if (b <= 1)
74 for (int i = 0; i < n; i++)
75 r[i] = 0;
76 else
77 for (int i = 0; i < n; i++, a /= b)
78 r[i] = a % b;
79}
80
81int digit_array_to_int(int *a, int n, int b) {
82 int ret = 0, p = 1;
83 for (int i = 0; i < n; i++, p *= b)
84 ret += a[i] * p;
85 return ret;
86}
87
88int perm_to_index(int *a, int n) {
89 if (!is_perm(a, n))
90 return factorial(n); /* Error */
91 int ret = 0;
92 for (int i = 0; i < n; i++) {
93 int c = 0;
94 for (int j = i+1; j < n; j++)
95 c += (a[i] > a[j]) ? 1 : 0;
96 ret += factorial(n-i-1) * c;
97 }
98 return ret;
99}
100
101void index_to_perm(int p, int n, int *r) {
102 if (p < 0 || p >= factorial(n)) /* Error */
103 for (int i = 0; i < n; i++)
104 r[i] = -1;
105 int a[n]; for (int j = 0; j < n; j++) a[j] = 0; /* picked elements */
106 for (int i = 0; i < n; i++) {
107 int c = 0, j = 0;
108 while (c <= p / factorial(n-i-1))
109 c += a[j++] ? 0 : 1;
110 r[i] = j-1;
111 a[j-1] = 1;
112 p %= factorial(n-i-1);
113 }
114}
115
116int perm_sign(int *a, int n) {
117 if (!is_perm(a,n))
118 return false;
119 int ret = 0;
120 for (int i = 0; i < n; i++)
121 for (int j = i+1; j < n; j++)
122 ret += (a[i]>a[j]) ? 1 : 0;
123 return ret % 2;
124}
125
126int subset_to_index(int *a, int n, int k) {
127 /* TODO: better checks */
128 if (!is_subset(a, n, k))
129 return binomial(n, k); /* Error */
130 int ret = 0;
131 for (int i = 0; i < n; i++) {
132 if (k == n-i)
133 return ret;
134 if (a[i]) {
135 /*ret += factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
136 ret += binomial(n-i-1, k);
137 k--;
138 }
139 }
140 return ret;
141}
142
143void index_to_subset(int s, int n, int k, int *r) {
144 if (s < 0 || s >= binomial(n, k)) { /* Error */
145 for (int i = 0; i < n; i++)
146 r[i] = -1;
147 return;
148 }
149 for (int i = 0; i < n; i++) {
150 if (k == n-i) {
151 for (int j = i; j < n; j++)
152 r[j] = 1;
153 return;
154 }
155 if (k == 0) {
156 for (int j = i; j < n; j++)
157 r[j] = 0;
158 return;
159 }
160 /*int v = factorial(n-i-1) / (factorial(k) * factorial(n-i-1-k));*/
161 int v = binomial(n-i-1, k);
162 if (s >= v) {
163 r[i] = 1;
164 k--;
165 s -= v;
166 } else {
167 r[i] = 0;
168 }
169 }
170}
171
172void int_to_sum_zero_array(int x, int b, int n, int *a) {
173 if (b <= 1) {
174 for (int i = 0; i < n; i++)
175 a[i] = 0;
176 } else {
177 int_to_digit_array(x, b, n-1, a);
178 int s = 0;
179 for (int i = 0; i < n - 1; i++)
180 s = (s + a[i]) % b;
181 a[n-1] = (b - s) % b;
182 }
183}
184
185void apply_permutation(int *perm, int *set, int n) {
186 if (!is_perm(perm, n))
187 return;
188 int aux[n];
189 for (int i = 0; i < n; i++)
190 aux[i] = set[perm[i]];
191 intarrcopy(aux, set, n);
192}
193
194void sum_arrays_mod(int *a, int *b, int n, int m) {
195 for (int i = 0; i < n; i++)
196 b[i] = (m <= 0) ? 0 : (a[i] + b[i]) % m;
197}
diff --git a/old/2021-02-28-transformcube-works/src/utils.h b/old/2021-02-28-transformcube-works/src/utils.h
deleted file mode 100644
index 4b6df8c..0000000
--- a/old/2021-02-28-transformcube-works/src/utils.h
+++ /dev/null
@@ -1,70 +0,0 @@
1/* General utility functions */
2
3#ifndef UTILS_H
4#define UTILS_H
5
6#include <stdbool.h>
7
8#define min(a,b) (((a) < (b)) ? (a) : (b))
9#define max(a,b) (((a) > (b)) ? (a) : (b))
10
11/* Some useful constants */
12#define pow2to11 2048
13#define pow2to12 4096
14#define pow3to7 2187
15#define pow3to8 6561
16#define pow12to4 20736
17#define factorial4 24
18#define factorial6 720
19#define factorial8 40320
20#define factorial12 479001600
21#define binom12on4 495
22#define binom8on4 70
23
24/* Generic utility functions */
25void swap(int *a, int *b);
26void intarrcopy(int *src, int *dst, int n);
27int sum(int *a, int n);
28bool is_perm(int *a, int n);
29bool is_perm(int *a, int n);
30
31
32/* Standard mathematical functions */
33int powint(int a, int b);
34int factorial(int n);
35int binomial(int n, int k);
36
37/* Converts the integer a to its representation in base b (first n digits
38 * only) and saves the result in r. */
39void int_to_digit_array(int a, int b, int n, int *r);
40int digit_array_to_int(int *a, int n, int b);
41
42/* Converts the first n-1 digits of a number to an array a of digits in base b;
43 * then adds one element to the array, so that the sum of the elements of a is
44 * zero modulo b.
45 * This is used for determing the edge orientation from an 11-bits integer or
46 * the corner orientation from a 7-trits integer. */
47void int_to_sum_zero_array(int x, int b, int n, int *a);
48
49/* Converts a permutation on [0..(n-1)] into the integer i which is the index
50 * of the permutation in the sorted list of all n! such permutations. */
51int perm_to_index(int *a, int n);
52void index_to_perm(int p, int n, int *r);
53
54/* Determine the sign of a permutation */
55int perm_sign(int a[], int n);
56
57/* Converts a k-element subset of a set from an array of n elements, of which k
58 * are 1 and n-k are 0, to its index in the sorted list of all such subsets. */
59int subset_to_index(int *a, int n, int k);
60void index_to_subset(int s, int n, int k, int *r);
61
62int ordered_subset_to_index(int *a, int n, int k);
63void index_to_ordered_subset(int s, int n, int k, int *r);
64
65void apply_permutation(int *perm, int *set, int n);
66
67/* b[i] = (a[i]+b[i])%m for i=1,...,n */
68void sum_arrays_mod(int *a, int *b, int n, int m);
69
70#endif

Generated with cgit - Back to sebastiano.tronto.net