aboutsummaryrefslogtreecommitdiff
path: root/old/2021-11-10-beforeremovingchecker
diff options
context:
space:
mode:
Diffstat (limited to 'old/2021-11-10-beforeremovingchecker')
-rw-r--r--old/2021-11-10-beforeremovingchecker/alg.c366
-rw-r--r--old/2021-11-10-beforeremovingchecker/alg.h35
-rw-r--r--old/2021-11-10-beforeremovingchecker/commands.c329
-rw-r--r--old/2021-11-10-beforeremovingchecker/commands.h13
-rw-r--r--old/2021-11-10-beforeremovingchecker/coord.c629
-rw-r--r--old/2021-11-10-beforeremovingchecker/coord.h40
-rw-r--r--old/2021-11-10-beforeremovingchecker/cube.c716
-rw-r--r--old/2021-11-10-beforeremovingchecker/cube.h40
-rw-r--r--old/2021-11-10-beforeremovingchecker/cubetypes.h298
-rw-r--r--old/2021-11-10-beforeremovingchecker/env.c45
-rw-r--r--old/2021-11-10-beforeremovingchecker/env.h15
-rw-r--r--old/2021-11-10-beforeremovingchecker/moves.c474
-rw-r--r--old/2021-11-10-beforeremovingchecker/moves.h16
-rw-r--r--old/2021-11-10-beforeremovingchecker/pf.c80
-rw-r--r--old/2021-11-10-beforeremovingchecker/pf.h18
-rw-r--r--old/2021-11-10-beforeremovingchecker/pruning.c272
-rw-r--r--old/2021-11-10-beforeremovingchecker/pruning.h23
-rw-r--r--old/2021-11-10-beforeremovingchecker/shell.c99
-rw-r--r--old/2021-11-10-beforeremovingchecker/shell.h13
-rw-r--r--old/2021-11-10-beforeremovingchecker/solve.c209
-rw-r--r--old/2021-11-10-beforeremovingchecker/solve.h9
-rw-r--r--old/2021-11-10-beforeremovingchecker/steps.c916
-rw-r--r--old/2021-11-10-beforeremovingchecker/steps.h10
-rw-r--r--old/2021-11-10-beforeremovingchecker/symcoord.c359
-rw-r--r--old/2021-11-10-beforeremovingchecker/symcoord.h15
-rw-r--r--old/2021-11-10-beforeremovingchecker/trans.c372
-rw-r--r--old/2021-11-10-beforeremovingchecker/trans.h13
-rw-r--r--old/2021-11-10-beforeremovingchecker/utils.c274
-rw-r--r--old/2021-11-10-beforeremovingchecker/utils.h41
29 files changed, 5739 insertions, 0 deletions
diff --git a/old/2021-11-10-beforeremovingchecker/alg.c b/old/2021-11-10-beforeremovingchecker/alg.c
new file mode 100644
index 0000000..06c2d7b
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/alg.c
@@ -0,0 +1,366 @@
1#include "alg.h"
2
3/* Local functions ***********************************************************/
4
5static void free_alglistnode(AlgListNode *aln);
6static void realloc_alg(Alg *alg, int n);
7
8/* Movesets ******************************************************************/
9
10bool
11moveset_HTM(Move m)
12{
13 return m >= U && m <= B3;
14}
15
16bool
17moveset_URF(Move m)
18{
19 Move b = base_move(m);
20
21 return b == U || b == R || b == F;
22}
23
24bool
25moveset_eofb(Move m)
26{
27 Move b = base_move(m);
28
29 return b == U || b == D || b == R || b == L ||
30 ((b == F || b == B) && m == b+1);
31}
32
33bool
34moveset_drud(Move m)
35{
36 Move b = base_move(m);
37
38 return b == U || b == D ||
39 ((b == R || b == L || b == F || b == B) && m == b + 1);
40}
41
42bool
43moveset_htr(Move m)
44{
45 Move b = base_move(m);
46
47 return moveset_HTM(m) && m == b + 1;
48}
49
50
51/* Functions *****************************************************************/
52
53void
54append_alg(AlgList *l, Alg *alg)
55{
56 AlgListNode *node = malloc(sizeof(AlgListNode));
57 int i;
58
59 node->alg = new_alg("");
60 for (i = 0; i < alg->len; i++)
61 append_move(node->alg, alg->move[i], alg->inv[i]);
62 node->next = NULL;
63
64 if (++l->len == 1)
65 l->first = node;
66 else
67 l->last->next = node;
68 l->last = node;
69}
70
71void
72append_move(Alg *alg, Move m, bool inverse)
73{
74 if (alg->len == alg->allocated)
75 realloc_alg(alg, 2*alg->len);
76
77 alg->move[alg->len] = m;
78 alg->inv [alg->len] = inverse;
79 alg->len++;
80}
81
82Move
83base_move(Move m)
84{
85 if (m == NULLMOVE)
86 return NULLMOVE;
87 else
88 return m - (m-1)%3;
89}
90
91void
92compose_alg(Alg *alg1, Alg *alg2)
93{
94 int i;
95
96 for (i = 0; i < alg2->len; i++)
97 append_move(alg1, alg2->move[i], alg2->inv[i]);
98}
99
100void
101free_alg(Alg *alg)
102{
103 free(alg->move);
104 free(alg->inv);
105 free(alg);
106}
107
108void
109free_alglist(AlgList *l)
110{
111 AlgListNode *aux, *i = l->first;
112
113 while (i != NULL) {
114 aux = i->next;
115 free_alglistnode(i);
116 i = aux;
117 }
118 free(l);
119}
120
121static void
122free_alglistnode(AlgListNode *aln)
123{
124 free_alg(aln->alg);
125 free(aln);
126}
127
128Alg *
129inverse_alg(Alg *alg)
130{
131 Alg *ret = new_alg("");
132 int i;
133
134 for (i = alg->len-1; i >= 0; i--)
135 append_move(ret, inverse_move(alg->move[i]), alg->inv[i]);
136
137 return ret;
138}
139
140Move
141inverse_move(Move m)
142{
143 return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
144}
145
146char *
147move_string(Move m)
148{
149 static char move_string_aux[NMOVES][7] = {
150 [NULLMOVE] = "-",
151 [U] = "U", [U2] = "U2", [U3] = "U\'",
152 [D] = "D", [D2] = "D2", [D3] = "D\'",
153 [R] = "R", [R2] = "R2", [R3] = "R\'",
154 [L] = "L", [L2] = "L2", [L3] = "L\'",
155 [F] = "F", [F2] = "F2", [F3] = "F\'",
156 [B] = "B", [B2] = "B2", [B3] = "B\'",
157 [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'",
158 [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'",
159 [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'",
160 [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'",
161 [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'",
162 [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'",
163 [M] = "M", [M2] = "M2", [M3] = "M\'",
164 [E] = "E", [E2] = "E2", [E3] = "E\'",
165 [S] = "S", [S2] = "S2", [S3] = "S\'",
166 [x] = "x", [x2] = "x2", [x3] = "x\'",
167 [y] = "y", [y2] = "y2", [y3] = "y\'",
168 [z] = "z", [z2] = "z2", [z3] = "z\'",
169 };
170
171 return move_string_aux[m];
172}
173
174void
175movelist_to_position(Move *movelist, int *position)
176{
177 Move m;
178
179 for (m = 0; m < NMOVES && movelist[m] != NULLMOVE; m++)
180 position[movelist[m]] = m;
181}
182
183void
184moveset_to_list(Moveset ms, Move *r)
185{
186 int n = 0;
187 Move i;
188
189 if (ms == NULL) {
190 fprintf(stderr, "Error: no moveset given\n");
191 return;
192 }
193
194 for (i = U; i < NMOVES; i++)
195 if (ms(i))
196 r[n++] = i;
197
198 r[n] = NULLMOVE;
199}
200
201Alg *
202new_alg(char *str)
203{
204 Alg *alg = malloc(sizeof(Alg));
205 int i;
206 bool niss = false, move_read;
207 Move j, m;
208
209 alg->move = malloc(30 * sizeof(Move));
210 alg->inv = malloc(30 * sizeof(bool));
211 alg->allocated = 30;
212 alg->len = 0;
213
214 for (i = 0; str[i]; i++) {
215 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
216 continue;
217
218 if (str[i] == '(' && niss) {
219 fprintf(stderr, "Error reading moves: nested ( )\n");
220 return alg;
221 }
222
223 if (str[i] == ')' && !niss) {
224 fprintf(stderr, "Error reading moves: unmatched )\n");
225 return alg;
226 }
227
228 if (str[i] == '(' || str[i] == ')') {
229 niss = !niss;
230 continue;
231 }
232
233 move_read = false;
234 for (j = 0; j < NMOVES; j++) {
235 if (str[i] == move_string(j)[0] ||
236 (str[i] >= 'a' && str[i] <= 'z' &&
237 str[i] == move_string(j)[0]-('A'-'a') && j<=B)) {
238 m = j;
239 if (str[i] >= 'a' && str[i] <= 'z' && j<=B) {
240 m += Uw - U;
241 }
242 if (m <= B && str[i+1]=='w') {
243 m += Uw - U;
244 i++;
245 }
246 if (str[i+1]=='2') {
247 m += 1;
248 i++;
249 } else if (str[i+1] == '\'' ||
250 str[i+1] == '3' ||
251 str[i+1] == '`' ) {
252 m += 2;
253 i++;
254 } else if ((int)str[i+1] == -62 &&
255 (int)str[i+2] == -76) {
256 /* Weird apostrophe */
257 m += 2;
258 i += 2;
259 } else if ((int)str[i+1] == -30 &&
260 (int)str[i+2] == -128 &&
261 (int)str[i+3] == -103) {
262 /* MacOS apostrophe */
263 m += 2;
264 i += 3;
265 }
266 append_move(alg, m, niss);
267 move_read = true;
268 break;
269 }
270 }
271
272 if (!move_read) {
273 alg = new_alg("");
274 return alg;
275 }
276 }
277
278 return alg;
279}
280
281AlgList *
282new_alglist()
283{
284 AlgList *ret = malloc(sizeof(AlgList));
285
286 ret->len = 0;
287 ret->first = NULL;
288 ret->last = NULL;
289
290 return ret;
291}
292
293Alg *
294on_inverse(Alg *alg)
295{
296 Alg *ret = new_alg("");
297 int i;
298
299 for (i = 0; i < alg->len; i++)
300 append_move(ret, alg->move[i], !alg->inv[i]);
301
302 return ret;
303}
304
305void
306print_alg(Alg *alg, bool l)
307{
308 /* TODO: make it possible to print to stdout or to string */
309 /* Maybe just return a string */
310 char fill[4];
311 int i;
312 bool niss = false;
313
314 for (i = 0; i < alg->len; i++) {
315 if (!niss && alg->inv[i])
316 strcpy(fill, i == 0 ? "(" : " (");
317 if (niss && !alg->inv[i])
318 strcpy(fill, ") ");
319 if (niss == alg->inv[i])
320 strcpy(fill, i == 0 ? "" : " ");
321
322 printf("%s%s", fill, move_string(alg->move[i]));
323 niss = alg->inv[i];
324 }
325
326 if (niss)
327 printf(")");
328 if (l)
329 printf(" (%d)", alg->len);
330
331 printf("\n");
332}
333
334void
335print_alglist(AlgList *al, bool l)
336{
337 AlgListNode *i;
338
339 for (i = al->first; i != NULL; i = i->next)
340 print_alg(i->alg, l);
341}
342
343static void
344realloc_alg(Alg *alg, int n)
345{
346 if (alg == NULL) {
347 fprintf(stderr, "Error: trying to reallocate NULL alg.\n");
348 return;
349 }
350
351 if (n < alg->len) {
352 fprintf(stderr, "Error: alg too long for reallocation ");
353 fprintf(stderr, "(%d vs %d)\n", alg->len, n);
354 return;
355 }
356
357 if (n > 1000000) {
358 fprintf(stderr, "Warning: very long alg,");
359 fprintf(stderr, "something might go wrong.\n");
360 }
361
362 alg->move = realloc(alg->move, n * sizeof(int));
363 alg->inv = realloc(alg->inv, n * sizeof(int));
364 alg->allocated = n;
365}
366
diff --git a/old/2021-11-10-beforeremovingchecker/alg.h b/old/2021-11-10-beforeremovingchecker/alg.h
new file mode 100644
index 0000000..98900b4
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/alg.h
@@ -0,0 +1,35 @@
1#ifndef ALG_H
2#define ALG_H
3
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7
8#include "cubetypes.h"
9#include "utils.h"
10
11bool moveset_HTM(Move m);
12bool moveset_URF(Move m);
13bool moveset_eofb(Move m);
14bool moveset_drud(Move m);
15bool moveset_htr(Move m);
16
17void append_alg(AlgList *l, Alg *alg);
18void append_move(Alg *alg, Move m, bool inverse);
19void compose_alg(Alg *alg1, Alg *alg2);
20Move base_move(Move m);
21void free_alg(Alg *alg);
22void free_alglist(AlgList *l);
23Alg * inverse_alg(Alg *alg);
24Move inverse_move(Move m);
25char * move_string(Move m);
26void movelist_to_position(Move *ml, int *pos);
27void moveset_to_list(Moveset ms, Move *lst);
28Alg * new_alg(char *str);
29AlgList * new_alglist();
30Alg * on_inverse(Alg *alg);
31void print_alg(Alg *alg, bool l);
32void print_alglist(AlgList *al, bool l);
33
34#endif
35
diff --git a/old/2021-11-10-beforeremovingchecker/commands.c b/old/2021-11-10-beforeremovingchecker/commands.c
new file mode 100644
index 0000000..b141229
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/commands.c
@@ -0,0 +1,329 @@
1#include "commands.h"
2
3/* Arg parsing functions *****************************************************/
4
5CommandArgs * solvestep_parse_args(int c, char **v);
6CommandArgs * help_parse_args(int c, char **v);
7CommandArgs * print_parse_args(int c, char **v);
8CommandArgs * parse_no_arg(int c, char **v);
9
10/* Exec functions ************************************************************/
11
12static void solvestep_exec(CommandArgs *args);
13static void steps_exec(CommandArgs *args);
14static void commands_exec(CommandArgs *args);
15static void print_exec(CommandArgs *args);
16static void help_exec(CommandArgs *args);
17static void quit_exec(CommandArgs *args);
18
19/* Local functions ***********************************************************/
20
21static bool read_step(CommandArgs *args, char *str);
22static bool read_scramble(int c, char **v, CommandArgs *args);
23
24/* Commands ******************************************************************/
25
26Command
27solvestep_cmd = {
28 .name = "solve",
29 .usage = "solve STEP [OPTIONS] SCRAMBLE",
30 .description = "Solve a step",
31 .parse_args = solvestep_parse_args,
32 .exec = solvestep_exec
33};
34
35Command
36steps_cmd = {
37 .name = "steps",
38 .usage = "steps",
39 .description = "List available steps",
40 .parse_args = parse_no_arg,
41 .exec = steps_exec
42};
43
44Command
45commands_cmd = {
46 .name = "commands",
47 .usage = "commands",
48 .description = "List available commands",
49 .parse_args = parse_no_arg,
50 .exec = commands_exec
51};
52
53Command
54print_cmd = {
55 .name = "print",
56 .usage = "print SCRAMBLE",
57 .description = "Print written description of the cube",
58 .parse_args = print_parse_args,
59 .exec = print_exec,
60};
61
62Command
63help_cmd = {
64 .name = "help",
65 .usage = "help [COMMAND]",
66 .description = "Display nissy manual page or help on specific command",
67 .parse_args = help_parse_args,
68 .exec = help_exec,
69};
70
71Command
72quit_cmd = {
73 .name = "quit",
74 .usage = "quit",
75 .description = "Quit nissy",
76 .parse_args = parse_no_arg,
77 .exec = quit_exec,
78};
79
80Command *commands[NCOMMANDS] = {
81 &solvestep_cmd,
82 &steps_cmd,
83 &commands_cmd,
84 &help_cmd,
85 &print_cmd,
86 &quit_cmd
87};
88
89/* Arg parsing functions implementation **************************************/
90
91CommandArgs *
92solvestep_parse_args(int c, char **v)
93{
94 int i;
95 long val;
96
97 CommandArgs *a = malloc(sizeof(CommandArgs));
98
99 a->success = false;
100 a->opts = malloc(sizeof(SolveOptions));
101 a->step = steps[0];
102 a->command = NULL;
103 a->scramble = NULL;
104
105 a->opts->min_moves = 0;
106 a->opts->max_moves = 20;
107 a->opts->max_solutions = 1;
108 a->opts->optimal_only = false;
109 a->opts->can_niss = false;
110 a->opts->feedback = false;
111 a->opts->all = false;
112 a->opts->print_number = true;
113
114 for (i = 0; i < c; i++) {
115 if (!strcmp(v[i], "-m")) {
116 val = strtol(v[++i], NULL, 10);
117 if (val < 0 || val > 100) {
118 fprintf(stderr,
119 "Invalid min number of moves.\n");
120 return a;
121 }
122 a->opts->min_moves = val;
123 } else if (!strcmp(v[i], "-M")) {
124 val = strtol(v[++i], NULL, 10);
125 if (val < 0 || val > 100) {
126 fprintf(stderr,
127 "Invalid max number of moves.\n");
128 return a;
129 }
130 a->opts->max_moves = val;
131 } else if (!strcmp(v[i], "-s")) {
132 val = strtol(v[++i], NULL, 10);
133 if (val < 1 || val > 1000000) {
134 fprintf(stderr,
135 "Invalid number of solutions.\n");
136 return a;
137 }
138 a->opts->max_solutions = val;
139 } else if (!strcmp(v[i], "-o")) {
140 a->opts->optimal_only = true;
141 } else if (!strcmp(v[i], "-n")) {
142 a->opts->can_niss = true;
143 } else if (!strcmp(v[i], "-v")) {
144 a->opts->feedback = true;
145 } else if (!strcmp(v[i], "-a")) {
146 a->opts->all = true;
147 } else if (!strcmp(v[i], "-p")) {
148 a->opts->print_number = false;
149 } else if (!read_step(a, v[i])) {
150 break;
151 }
152 }
153
154 a->success = read_scramble(c-i, &v[i], a);
155 return a;
156}
157
158CommandArgs *
159help_parse_args(int c, char **v)
160{
161 int i;
162 CommandArgs *a = malloc(sizeof(CommandArgs));
163
164 a->scramble = NULL;
165 a->opts = NULL;
166 a->step = NULL;
167 a->command = NULL;
168
169 if (c == 1) {
170 for (i = 0; i < NCOMMANDS; i++)
171 if (commands[i] != NULL &&
172 !strcmp(v[0], commands[i]->name))
173 a->command = commands[i];
174 if (a->command == NULL)
175 fprintf(stderr, "%s: command not found\n", v[0]);
176 }
177
178 a->success = c == 0 || (c == 1 && a->command != NULL);
179 return a;
180}
181
182CommandArgs *
183parse_no_arg(int c, char **v)
184{
185 CommandArgs *a = malloc(sizeof(CommandArgs));
186
187 a->scramble = NULL;
188 a->opts = NULL;
189 a->step = NULL;
190 a->command = NULL;
191
192 return a;
193}
194
195CommandArgs *
196print_parse_args(int c, char **v)
197{
198 CommandArgs *a = malloc(sizeof(CommandArgs));
199
200 a->opts = NULL;
201 a->step = NULL;
202 a->command = NULL;
203
204 a->success = read_scramble(c-1, &v[1], a);
205 return a;
206}
207
208/* Exec functions implementation *********************************************/
209
210static void
211solvestep_exec(CommandArgs *args)
212{
213 Cube c = apply_alg(args->scramble, (Cube){0});
214 AlgList *sols = solve(c, args->step, args->opts);
215 print_alglist(sols, args->opts->print_number);
216 free_alglist(sols);
217}
218
219static void
220steps_exec(CommandArgs *args)
221{
222 int i;
223
224 for (i = 0; i < NSTEPS && steps[i] != NULL; i++)
225 printf("%-15s %s\n", steps[i]->shortname, steps[i]->name);
226}
227
228static void
229commands_exec(CommandArgs *args)
230{
231 int i;
232
233 for (i = 0; i < NCOMMANDS && commands[i] != NULL; i++)
234 printf("%s\n", commands[i]->usage);
235
236}
237
238static void
239print_exec(CommandArgs *args)
240{
241 print_cube(apply_alg(args->scramble, (Cube){0}));
242}
243
244static void
245help_exec(CommandArgs *args)
246{
247 /* TODO: print full nissy manpage */
248 if (args->command == NULL) {
249 printf("Type help COMMAND for information on a ");
250 printf("specific command.\n");
251 printf("A more complete manual page is work in progress.\n");
252 } else {
253 printf("Command %s: %s\nusage: %s\n", args->command->name,
254 args->command->description, args->command->usage);
255 }
256}
257
258static void
259quit_exec(CommandArgs *args)
260{
261 exit(0);
262}
263
264/* Local functions implementation ********************************************/
265
266static bool
267read_step(CommandArgs *args, char *str)
268{
269 int i;
270
271 for (i = 0; i < NSTEPS; i++) {
272 if (steps[i] != NULL && !strcmp(steps[i]->shortname, str)) {
273 args->step = steps[i];
274 return true;
275 }
276 }
277
278 return false;
279}
280
281static bool
282read_scramble(int c, char **v, CommandArgs *args)
283{
284 int i, k, n;
285 unsigned int j;
286 char *algstr;
287
288 if (new_alg(v[0])->len == 0) {
289 fprintf(stderr, "%s: moves or option unrecognized\n", v[0]);
290 return false;
291 }
292
293 n = 0;
294 for(i = 0; i < c; i++)
295 n += strlen(v[i]);
296
297 algstr = malloc((n + 1) * sizeof(char));
298 k = 0;
299 for (i = 0; i < c; i++)
300 for (j = 0; j < strlen(v[i]); j++)
301 algstr[k++] = v[i][j];
302 algstr[k] = 0;
303
304 args->scramble = new_alg(algstr);
305 free(algstr);
306
307 if (args->scramble->len == 0)
308 fprintf(stderr, "Error reading scramble\n");
309
310 return args->scramble->len > 0;
311}
312
313/* Public functions implementation *******************************************/
314
315void
316free_args(CommandArgs *args)
317{
318 if (args == NULL)
319 return;
320
321 if (args->scramble != NULL)
322 free_alg(args->scramble);
323 if (args->opts != NULL)
324 free(args->opts);
325
326 /* step and command must not be freed, they are static! */
327
328 free(args);
329}
diff --git a/old/2021-11-10-beforeremovingchecker/commands.h b/old/2021-11-10-beforeremovingchecker/commands.h
new file mode 100644
index 0000000..f2703fa
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/commands.h
@@ -0,0 +1,13 @@
1#ifndef COMMANDS_H
2#define COMMANDS_H
3
4#include "solve.h"
5#include "steps.h"
6
7#define NCOMMANDS 10
8
9void free_args(CommandArgs *args);
10
11extern Command * commands[NCOMMANDS];
12
13#endif
diff --git a/old/2021-11-10-beforeremovingchecker/coord.c b/old/2021-11-10-beforeremovingchecker/coord.c
new file mode 100644
index 0000000..343dfb3
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/coord.c
@@ -0,0 +1,629 @@
1#include "coord.h"
2
3static Cube antindex_eofb(uint64_t ind);
4static Cube antindex_eofbepos(uint64_t ind);
5static Cube antindex_epud(uint64_t ind);
6static Cube antindex_coud(uint64_t ind);
7static Cube antindex_corners(uint64_t ind);
8static Cube antindex_cp(uint64_t ind);
9static Cube antindex_cphtr(uint64_t);
10static Cube antindex_cornershtr(uint64_t ind);
11static Cube antindex_cornershtrfin(uint64_t ind);
12static Cube antindex_drud(uint64_t ind);
13static Cube antindex_drud_eofb(uint64_t ind);
14static Cube antindex_htr_drud(uint64_t ind);
15static Cube antindex_htrfin(uint64_t ind);
16
17static uint64_t index_eofb(Cube cube);
18static uint64_t index_eofbepos(Cube cube);
19static uint64_t index_epud(Cube cube);
20static uint64_t index_coud(Cube cube);
21static uint64_t index_corners(Cube cube);
22static uint64_t index_cp(Cube cube);
23static uint64_t index_cphtr(Cube cube);
24static uint64_t index_cornershtr(Cube cube);
25static uint64_t index_cornershtrfin(Cube cube);
26static uint64_t index_drud(Cube cube);
27static uint64_t index_drud_eofb(Cube cube);
28static uint64_t index_htr_drud(Cube cube);
29static uint64_t index_htrfin(Cube cube);
30
31static void init_cphtr_cosets();
32static void init_cphtr_left_cosets_bfs(int i, int c);
33static void init_cphtr_right_cosets_color(int i, int c);
34static void init_cornershtrfin();
35
36
37/* All sorts of useful costants and tables **********************************/
38
39static int cphtr_left_cosets[FACTORIAL8];
40static int cphtr_right_cosets[FACTORIAL8];
41static int cphtr_right_rep[BINOM8ON4*6];
42static int cornershtrfin_ind[FACTORIAL8];
43static int cornershtrfin_ant[24*24/6];
44
45/* Coordinates and their implementation **************************************/
46
47Coordinate
48coord_eofb = {
49 .index = index_eofb,
50 .cube = antindex_eofb,
51 .check = check_eofb,
52 .max = POW2TO11,
53 .ntrans = 1,
54};
55
56Coordinate
57coord_eofbepos = {
58 .index = index_eofbepos,
59 .cube = antindex_eofbepos,
60 .check = check_eofbepos,
61 .max = POW2TO11 * BINOM12ON4,
62 .ntrans = 1,
63};
64
65Coordinate
66coord_coud = {
67 .index = index_coud,
68 .cube = antindex_coud,
69 .check = check_coud,
70 .max = POW3TO7,
71 .ntrans = 1,
72};
73
74Coordinate
75coord_corners = {
76 .index = index_corners,
77 .cube = antindex_corners,
78 .check = check_corners,
79 .max = POW3TO7 * FACTORIAL8,
80 .ntrans = 1,
81};
82
83Coordinate
84coord_cp = {
85 .index = index_cp,
86 .cube = antindex_cp,
87 .check = check_cp,
88 .max = FACTORIAL8,
89 .ntrans = 1,
90};
91
92Coordinate
93coord_cphtr = {
94 .index = index_cphtr,
95 .cube = antindex_cphtr,
96 .check = check_cphtr,
97 .max = BINOM8ON4 * 6,
98 .ntrans = 1,
99};
100
101Coordinate
102coord_cornershtr = {
103 .index = index_cornershtr,
104 .cube = antindex_cornershtr,
105 .check = check_cornershtr,
106 .max = POW3TO7 * BINOM8ON4 * 6,
107 .ntrans = 1,
108};
109
110Coordinate
111coord_cornershtrfin = {
112 .index = index_cornershtrfin,
113 .cube = antindex_cornershtrfin,
114 .check = check_cp,
115 .max = 24*24/6,
116 .ntrans = 1,
117};
118
119Coordinate
120coord_epud = {
121 .index = index_epud,
122 .cube = antindex_epud,
123 .check = check_epud,
124 .max = FACTORIAL8,
125 .ntrans = 1,
126};
127
128Coordinate
129coord_drud = {
130 .index = index_drud,
131 .cube = antindex_drud,
132 .check = check_drud,
133 .max = POW2TO11 * POW3TO7 * BINOM12ON4,
134 .ntrans = 1,
135};
136
137Coordinate
138coord_htr_drud = {
139 .index = index_htr_drud,
140 .cube = antindex_htr_drud,
141 .check = check_drud,
142 .max = BINOM8ON4 * 6 * BINOM8ON4,
143 .ntrans = 1,
144};
145
146Coordinate
147coord_htrfin = {
148 .index = index_htrfin,
149 .cube = antindex_htrfin,
150 .check = check_htr,
151 .max = 24 * 24 * 24 *24 * 24 / 6, /* should be /12 but it's ok */
152 .ntrans = 1,
153};
154
155Coordinate
156coord_drud_eofb = {
157 .index = index_drud_eofb,
158 .cube = antindex_drud_eofb,
159 .check = check_drud,
160 .max = POW3TO7 * BINOM12ON4,
161 .ntrans = 1,
162};
163
164/* Functions *****************************************************************/
165
166static Cube
167antindex_eofb(uint64_t ind)
168{
169 return (Cube){ .eofb = ind, .eorl = ind, .eoud = ind };
170}
171
172static Cube
173antindex_eofbepos(uint64_t ind)
174{
175 Cube ret = {0};
176
177 ret.eofb = ind % POW2TO11;
178 ret.epose = (ind / POW2TO11) * 24;
179
180 return ret;
181}
182
183static Cube
184antindex_epud(uint64_t ind)
185{
186 static bool initialized = false;
187 static Cube epud_aux[FACTORIAL8];
188 int a[12];
189 uint64_t ui;
190 CubeArray arr;
191
192 if (!initialized) {
193 a[FR] = FR;
194 a[FL] = FL;
195 a[BL] = BL;
196 a[BR] = BR;
197 for (ui = 0; ui < FACTORIAL8; ui++) {
198 index_to_perm(ui, 8, a);
199 arr.ep = a;
200 epud_aux[ui] = arrays_to_cube(&arr, pf_ep);
201 }
202
203 initialized = true;
204 }
205
206 return epud_aux[ind];
207}
208
209static Cube
210antindex_coud(uint64_t ind)
211{
212 return (Cube){ .coud = ind, .corl = ind, .cofb = ind };
213}
214
215static Cube
216antindex_corners(uint64_t ind)
217{
218 Cube c = {0};
219
220 c.coud = ind / FACTORIAL8;
221 c.cp = ind % FACTORIAL8;
222
223 return c;
224}
225
226static Cube
227antindex_cp(uint64_t ind)
228{
229 Cube c = {0};
230
231 c.cp = ind;
232
233 return c;
234}
235
236static Cube
237antindex_cphtr(uint64_t ind)
238{
239 return (Cube) { .cp = cphtr_right_rep[ind] };
240}
241
242static Cube
243antindex_cornershtr(uint64_t ind)
244{
245 Cube c = antindex_cphtr(ind % (BINOM8ON4 * 6));
246
247 c.coud = ind / (BINOM8ON4 * 6);
248
249 return c;
250}
251
252static Cube
253antindex_cornershtrfin(uint64_t ind)
254{
255 return (Cube){ .cp = cornershtrfin_ant[ind] };
256}
257
258static Cube
259antindex_drud(uint64_t ind)
260{
261 uint64_t epos, eofb;
262 Cube c;
263
264 eofb = ind % POW2TO11;
265 epos = ind / (POW2TO11 * POW3TO7);
266 c = antindex_eofbepos(eofb + POW2TO11 * epos);
267
268 c.coud = (ind / POW2TO11) % POW3TO7;
269
270 return c;
271}
272
273static Cube
274antindex_drud_eofb(uint64_t ind)
275{
276 return antindex_drud(ind * POW2TO11);
277}
278
279static Cube
280antindex_htr_drud(uint64_t ind)
281{
282 Cube ret;
283
284 ret = antindex_cphtr(ind / BINOM8ON4);
285 ret.eposs = (ind % BINOM8ON4) * FACTORIAL4;
286
287 return ret;
288}
289
290static Cube
291antindex_htrfin(uint64_t ind)
292{
293 Cube ret;
294
295 ret = antindex_cornershtrfin(ind/(24*24*24));
296
297 ret.eposm = ind % 24;
298 ind /= 24;
299 ret.eposs = ind % 24;
300 ind /= 24;
301 ret.epose = ind % 24;
302
303 return ret;
304}
305
306bool
307check_centers(Cube cube)
308{
309 return cube.cpos == 0;
310}
311
312bool
313check_corners(Cube cube)
314{
315 return cube.cp == 0 && cube.coud == 0;
316}
317
318bool
319check_cp(Cube cube)
320{
321 return cube.cp == 0;
322}
323
324bool
325check_cphtr(Cube cube)
326{
327 return index_cphtr(cube) == 0;
328}
329
330bool
331check_cornershtr(Cube cube)
332{
333 return cube.coud == 0 && index_cphtr(cube) == 0;
334}
335
336bool
337check_coud(Cube cube)
338{
339 return cube.coud == 0;
340}
341
342bool
343check_drud(Cube cube)
344{
345 return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0;
346}
347
348bool
349check_htr(Cube cube)
350{
351 return check_cornershtr(cube) &&
352 cube.eofb == 0 && cube.eorl == 0 && cube.eoud == 0;
353}
354
355bool
356check_drudfin_noE(Cube cube)
357{
358 return cube.eposs == 0 && cube.eposm == 0 && cube.cp == 0;
359}
360
361bool
362check_eofb(Cube cube)
363{
364 return cube.eofb == 0;
365}
366
367bool
368check_eofbepos(Cube cube)
369{
370 return cube.eofb == 0 && cube.epose / 24 == 0;
371}
372
373bool
374check_epose(Cube cube)
375{
376 return cube.epose == 0;
377}
378
379bool
380check_epud(Cube cube)
381{
382 return cube.eposs == 0 && cube.eposm == 0;
383}
384
385bool
386check_ep(Cube cube)
387{
388 return cube.epose == 0 && cube.eposs == 0 && cube.eposm == 0;
389}
390
391bool
392check_khuge(Cube cube)
393{
394 return check_drud(cube) && cube.epose % 24 == 0;
395}
396
397bool
398check_nothing(Cube cube)
399{
400 return is_admissible(cube); /*TODO: maybe change?*/
401}
402
403static uint64_t
404index_eofb(Cube cube)
405{
406 return cube.eofb;
407}
408
409static uint64_t
410index_eofbepos(Cube cube)
411{
412 return (cube.epose / FACTORIAL4) * POW2TO11 + cube.eofb;
413}
414
415static uint64_t
416index_epud(Cube cube)
417{
418 uint64_t ret;
419 CubeArray *arr = new_cubearray(cube, pf_ep);
420
421 ret = perm_to_index(arr->ep, 8);
422 free_cubearray(arr, pf_ep);
423
424 return ret;
425}
426
427static uint64_t
428index_coud(Cube cube)
429{
430 return cube.coud;
431}
432
433static uint64_t
434index_corners(Cube cube)
435{
436 return cube.coud * FACTORIAL8 + cube.cp;
437}
438
439static uint64_t
440index_cp(Cube cube)
441{
442 return cube.cp;
443}
444
445static uint64_t
446index_cphtr(Cube cube)
447{
448 return cphtr_right_cosets[cube.cp];
449}
450
451static uint64_t
452index_cornershtr(Cube cube)
453{
454 return cube.coud * BINOM8ON4 * 6 + index_cphtr(cube);
455}
456
457static uint64_t
458index_cornershtrfin(Cube cube)
459{
460 return cornershtrfin_ind[cube.cp];
461}
462
463static uint64_t
464index_drud(Cube cube)
465{
466 uint64_t a, b, c;
467
468 a = cube.eofb;
469 b = cube.coud;
470 c = cube.epose / FACTORIAL4;
471
472 b *= POW2TO11;
473 c *= POW2TO11 * POW3TO7;
474
475 return a + b + c;
476}
477
478static uint64_t
479index_drud_eofb(Cube cube)
480{
481 return index_drud(cube) / POW2TO11;
482}
483
484static uint64_t
485index_htr_drud(Cube cube)
486{
487 return index_cphtr(cube) * BINOM8ON4 +
488 (cube.eposs / FACTORIAL4) % BINOM8ON4;
489}
490
491static uint64_t
492index_htrfin(Cube cube)
493{
494 uint64_t epe, eps, epm, cp, ep;
495
496 epe = cube.epose % 24;
497 eps = cube.eposs % 24;
498 epm = cube.eposm % 24;
499 ep = (epe * 24 + eps) *24 + epm;
500 cp = index_cornershtrfin(cube);
501
502 return cp * 24 * 24 * 24 + ep;
503}
504
505/* Init functions implementation *********************************************/
506
507/*
508 * There is certainly a better way to do this, but for now I just use
509 * a "graph coloring" algorithm to compute the left cosets, and I compose
510 * with every possible cp to get the right cosets (it is possible that I am
511 * mixing up left and right).
512 *
513 * For doing it better "Mathematically", we need 3 things:
514 * - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other
515 * This is easy and it is done in the commented function cphtr_cp().
516 * - Check that there is no ep/cp parity
517 * - Check that we are not in the "3c" case; this is the part I don't
518 * know how to do.
519 */
520static void
521init_cphtr_cosets()
522{
523 unsigned int i;
524 int c = 0, d = 0;
525
526 for (i = 0; i < FACTORIAL8; i++) {
527 cphtr_left_cosets[i] = -1;
528 cphtr_right_cosets[i] = -1;
529 }
530
531 /* First we compute left cosets with a bfs */
532 for (i = 0; i < FACTORIAL8; i++)
533 if (cphtr_left_cosets[i] == -1)
534 init_cphtr_left_cosets_bfs(i, c++);
535
536 /* Then we compute right cosets using compose() */
537 for (i = 0; i < FACTORIAL8; i++)
538 if (cphtr_right_cosets[i] == -1)
539 init_cphtr_right_cosets_color(i, d++);
540}
541
542static void
543init_cphtr_left_cosets_bfs(int i, int c)
544{
545 int j, jj, k, next[FACTORIAL8], next2[FACTORIAL8], n, n2;
546 Move moves[6] = {U2, D2, R2, L2, F2, B2};
547
548 n = 1;
549 next[0] = i;
550 cphtr_left_cosets[i] = c;
551
552 while (n != 0) {
553 for (j = 0, n2 = 0; j < n; j++) {
554 for (k = 0; k < 6; k++) {
555 /*jj = cp_mtable[moves[k]][next[j]];*/
556 /* TODO fix formatting */
557 jj = apply_move(moves[k], (Cube){.cp=next[j]}).cp;
558 if (cphtr_left_cosets[jj] == -1) {
559 cphtr_left_cosets[jj] = c;
560 next2[n2++] = jj;
561 }
562 }
563 }
564
565 for (j = 0; j < n2; j++)
566 next[j] = next2[j];
567 n = n2;
568 }
569}
570
571static void
572init_cphtr_right_cosets_color(int i, int d)
573{
574 int cp;
575 unsigned int j;
576
577 cphtr_right_rep[d] = i;
578 for (j = 0; j < FACTORIAL8; j++) {
579 if (cphtr_left_cosets[j] == 0) {
580 /* TODO: use antindexer, it's nicer */
581 cp = compose((Cube){.cp = i}, (Cube){.cp = j}).cp;
582 cphtr_right_cosets[cp] = d;
583 }
584 }
585}
586
587static void
588init_cornershtrfin()
589{
590 unsigned int i, j;
591 int n, c;
592 Move m;
593
594 for (i = 0; i < FACTORIAL8; i++)
595 cornershtrfin_ind[i] = -1;
596 cornershtrfin_ind[0] = 0;
597
598 /* 10-pass, I think 5 is enough, but just in case */
599 n = 1;
600 for (i = 0; i < 10; i++) {
601 for (j = 0; j < FACTORIAL8; j++) {
602 if (cornershtrfin_ind[j] == -1)
603 continue;
604 for (m = U; m < NMOVES; m++) {
605 if (moveset_htr(m)) {
606 c = apply_move(m, (Cube){.cp = j}).cp;
607 if (cornershtrfin_ind[c] == -1) {
608 cornershtrfin_ind[c] = n;
609 cornershtrfin_ant[n] = c;
610 n++;
611 }
612 }
613 }
614 }
615 }
616}
617
618void
619init_coord()
620{
621 static bool initialized = false;
622 if (initialized)
623 return;
624 initialized = true;
625
626 init_cphtr_cosets();
627 init_cornershtrfin();
628}
629
diff --git a/old/2021-11-10-beforeremovingchecker/coord.h b/old/2021-11-10-beforeremovingchecker/coord.h
new file mode 100644
index 0000000..81c1e9c
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/coord.h
@@ -0,0 +1,40 @@
1#ifndef COORD_H
2#define COORD_H
3
4#include "trans.h"
5
6extern Coordinate coord_eofb;
7extern Coordinate coord_eofbepos;
8extern Coordinate coord_coud;
9extern Coordinate coord_cp;
10extern Coordinate coord_cphtr;
11extern Coordinate coord_corners;
12extern Coordinate coord_cornershtr;
13extern Coordinate coord_cornershtrfin;
14extern Coordinate coord_epud;
15extern Coordinate coord_drud;
16extern Coordinate coord_drud_eofb;
17extern Coordinate coord_htr_drud;
18extern Coordinate coord_htrfin;
19
20bool check_centers(Cube cube);
21bool check_corners(Cube cube);
22bool check_cp(Cube cube);
23bool check_cphtr(Cube cube);
24bool check_cornershtr(Cube cube);
25bool check_coud(Cube cube);
26bool check_drud(Cube cube);
27bool check_htr(Cube cube);
28bool check_drudfin_noE(Cube cube);
29bool check_eofb(Cube cube);
30bool check_eofbepos(Cube cube);
31bool check_epose(Cube cube);
32bool check_ep(Cube cube);
33bool check_epud(Cube cube);
34bool check_khuge(Cube cube);
35bool check_nothing(Cube cube);
36
37void init_coord();
38
39#endif
40
diff --git a/old/2021-11-10-beforeremovingchecker/cube.c b/old/2021-11-10-beforeremovingchecker/cube.c
new file mode 100644
index 0000000..b621d7b
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/cube.c
@@ -0,0 +1,716 @@
1#include "cube.h"
2
3/* Local functions **********************************************************/
4
5static int array_ep_to_epos(int *ep, int *eps_solved);
6static int epos_from_arrays(int *epos, int *ep);
7
8/* Local functions implementation ********************************************/
9
10static int
11array_ep_to_epos(int *ep, int *ss)
12{
13 int epos[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
14 int eps[4];
15 int i, j, is;
16
17 for (i = 0, is = 0; i < 12; i++) {
18 for (j = 0; j < 4; j++) {
19 if (ep[i] == ss[j]) {
20 eps[is++] = j;
21 epos[i] = 1;
22 }
23 }
24 }
25
26 for (i = 0; i < 4; i++)
27 swap(&epos[ss[i]], &epos[i+8]);
28
29 return epos_from_arrays(epos, eps);
30}
31
32static int
33epos_from_arrays(int *epos, int *ep)
34{
35 return FACTORIAL4 * subset_to_index(epos,12,4) + perm_to_index(ep,4);
36}
37
38/* Public functions implementation *******************************************/
39
40Cube
41arrays_to_cube(CubeArray *arr, PieceFilter f)
42{
43 Cube ret = {0};
44
45 static int epe_solved[4] = {FR, FL, BL, BR};
46 static int eps_solved[4] = {UL, UR, DL, DR};
47 static int epm_solved[4] = {UF, UB, DF, DB};
48
49 if (f.epose)
50 ret.epose = array_ep_to_epos(arr->ep, epe_solved);
51 if (f.eposs)
52 ret.eposs = array_ep_to_epos(arr->ep, eps_solved);
53 if (f.eposm)
54 ret.eposm = array_ep_to_epos(arr->ep, epm_solved);
55 if (f.eofb)
56 ret.eofb = digit_array_to_int(arr->eofb, 11, 2);
57 if (f.eorl)
58 ret.eorl = digit_array_to_int(arr->eorl, 11, 2);
59 if (f.eoud)
60 ret.eoud = digit_array_to_int(arr->eoud, 11, 2);
61 if (f.cp)
62 ret.cp = perm_to_index(arr->cp, 8);
63 if (f.coud)
64 ret.coud = digit_array_to_int(arr->coud, 7, 3);
65 if (f.corl)
66 ret.corl = digit_array_to_int(arr->corl, 7, 3);
67 if (f.cofb)
68 ret.cofb = digit_array_to_int(arr->cofb, 7, 3);
69 if (f.cpos)
70 ret.cpos = perm_to_index(arr->cpos, 6);
71
72 return ret;
73}
74
75Cube
76compose_filtered(Cube c2, Cube c1, PieceFilter f)
77{
78 CubeArray *arr = new_cubearray(c2, f);
79 Cube ret;
80
81 ret = move_via_arrays(arr, c1, f);
82 free_cubearray(arr, f);
83
84 return ret;
85}
86
87void
88cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f)
89{
90 int i;
91
92 static int epe_solved[4] = {FR, FL, BL, BR};
93 static int eps_solved[4] = {UL, UR, DL, DR};
94 static int epm_solved[4] = {UF, UB, DF, DB};
95
96 if (f.epose || f.eposs || f.eposm)
97 for (i = 0; i < 12; i++)
98 arr->ep[i] = -1;
99
100 if (f.epose)
101 epos_to_partial_ep(cube.epose, arr->ep, epe_solved);
102 if (f.eposs)
103 epos_to_partial_ep(cube.eposs, arr->ep, eps_solved);
104 if (f.eposm)
105 epos_to_partial_ep(cube.eposm, arr->ep, epm_solved);
106 if (f.eofb)
107 int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb);
108 if (f.eorl)
109 int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl);
110 if (f.eoud)
111 int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud);
112 if (f.cp)
113 index_to_perm(cube.cp, 8, arr->cp);
114 if (f.coud)
115 int_to_sum_zero_array(cube.coud, 3, 8, arr->coud);
116 if (f.corl)
117 int_to_sum_zero_array(cube.corl, 3, 8, arr->corl);
118 if (f.cofb)
119 int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb);
120 if (f.cpos)
121 index_to_perm(cube.cpos, 6, arr->cpos);
122}
123
124void
125epos_to_partial_ep(int epos, int *ep, int *ss)
126{
127 int i, is, eposs[12], eps[4];
128
129 index_to_perm(epos % FACTORIAL4, 4, eps);
130 index_to_subset(epos / FACTORIAL4, 12, 4, eposs);
131
132 for (i = 0; i < 4; i++)
133 swap(&eposs[ss[i]], &eposs[i+8]);
134
135 for (i = 0, is = 0; i < 12; i++)
136 if (eposs[i])
137 ep[i] = ss[eps[is++]];
138}
139
140void
141free_cubearray(CubeArray *arr, PieceFilter f)
142{
143 if (f.epose || f.eposs || f.eposm)
144 free(arr->ep);
145 if (f.eofb)
146 free(arr->eofb);
147 if (f.eorl)
148 free(arr->eorl);
149 if (f.eoud)
150 free(arr->eoud);
151 if (f.cp)
152 free(arr->cp);
153 if (f.coud)
154 free(arr->coud);
155 if (f.corl)
156 free(arr->corl);
157 if (f.cofb)
158 free(arr->cofb);
159 if (f.cpos)
160 free(arr->cpos);
161
162 free(arr);
163}
164
165Cube
166move_via_arrays(CubeArray *arr, Cube c, PieceFilter f)
167{
168 CubeArray *arrc = new_cubearray(c, f);
169 Cube ret;
170
171 if (f.epose || f.eposs || f.eposm)
172 apply_permutation(arr->ep, arrc->ep, 12);
173
174 if (f.eofb) {
175 apply_permutation(arr->ep, arrc->eofb, 12);
176 sum_arrays_mod(arr->eofb, arrc->eofb, 12, 2);
177 }
178
179 if (f.eorl) {
180 apply_permutation(arr->ep, arrc->eorl, 12);
181 sum_arrays_mod(arr->eorl, arrc->eorl, 12, 2);
182 }
183
184 if (f.eoud) {
185 apply_permutation(arr->ep, arrc->eoud, 12);
186 sum_arrays_mod(arr->eoud, arrc->eoud, 12, 2);
187 }
188
189 if (f.cp)
190 apply_permutation(arr->cp, arrc->cp, 8);
191
192 if (f.coud) {
193 apply_permutation(arr->cp, arrc->coud, 8);
194 sum_arrays_mod(arr->coud, arrc->coud, 8, 3);
195 }
196
197 if (f.corl) {
198 apply_permutation(arr->cp, arrc->corl, 8);
199 sum_arrays_mod(arr->corl, arrc->corl, 8, 3);
200 }
201
202 if (f.cofb) {
203 apply_permutation(arr->cp, arrc->cofb, 8);
204 sum_arrays_mod(arr->cofb, arrc->cofb, 8, 3);
205 }
206
207 if (f.cpos)
208 apply_permutation(arr->cpos, arrc->cpos, 6);
209
210 ret = arrays_to_cube(arrc, f);
211 free_cubearray(arrc, f);
212
213 return ret;
214}
215
216CubeArray *
217new_cubearray(Cube cube, PieceFilter f)
218{
219 CubeArray *arr = malloc(sizeof(CubeArray));
220
221 if (f.epose || f.eposs || f.eposm)
222 arr->ep = malloc(12 * sizeof(int));
223 if (f.eofb)
224 arr->eofb = malloc(12 * sizeof(int));
225 if (f.eorl)
226 arr->eorl = malloc(12 * sizeof(int));
227 if (f.eoud)
228 arr->eoud = malloc(12 * sizeof(int));
229 if (f.cp)
230 arr->cp = malloc(8 * sizeof(int));
231 if (f.coud)
232 arr->coud = malloc(8 * sizeof(int));
233 if (f.corl)
234 arr->corl = malloc(8 * sizeof(int));
235 if (f.cofb)
236 arr->cofb = malloc(8 * sizeof(int));
237 if (f.cpos)
238 arr->cpos = malloc(6 * sizeof(int));
239
240 cube_to_arrays(cube, arr, f);
241
242 return arr;
243}
244
245
246/* TODO: consider if this is good here or better in coord.c
247 in any case it is used in transformation init at the moment */
248Cube
249admissible_ep(Cube cube, PieceFilter f)
250{
251 CubeArray *arr = new_cubearray(cube, f);
252 Cube ret;
253 bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
254 int i, j;
255
256 for (i = 0; i < 12; i++)
257 if (arr->ep[i] != -1)
258 used[arr->ep[i]] = true;
259
260 for (i = 0, j = 0; i < 12; i++) {
261 for ( ; j < 11 && used[j]; j++);
262 if (arr->ep[i] == -1)
263 arr->ep[i] = j++;
264 }
265
266 ret = arrays_to_cube(arr, pf_ep);
267 free_cubearray(arr, f);
268
269 return ret;
270}
271
272Cube
273compose(Cube c2, Cube c1)
274{
275 return compose_filtered(c2, c1, pf_all);
276}
277
278int
279edge_slice(Edge e) {
280 if (e < 0 || e > 11)
281 return -1;
282
283 if (e == FR || e == FL || e == BL || e == BR)
284 return 0;
285 if (e == UR || e == UL || e == DR || e == DL)
286 return 1;
287
288 return 2;
289}
290
291bool
292equal(Cube c1, Cube c2)
293{
294 return c1.eofb == c2.eofb &&
295 c1.epose == c2.epose &&
296 c1.eposs == c2.eposs &&
297 c1.eposm == c2.eposm &&
298 c1.coud == c2.coud &&
299 c1.cp == c2.cp &&
300 c1.cpos == c2.cpos;
301}
302
303Cube
304inverse_cube(Cube cube)
305{
306 CubeArray *arr = new_cubearray(cube, pf_all);
307 CubeArray *inv = new_cubearray((Cube){0}, pf_all);
308 Cube ret;
309 int i;
310
311 for (i = 0; i < 12; i++) {
312 inv->ep[arr->ep[i]] = i;
313 inv->eofb[arr->ep[i]] = arr->eofb[i];
314 inv->eorl[arr->ep[i]] = arr->eorl[i];
315 inv->eoud[arr->ep[i]] = arr->eoud[i];
316 }
317
318 for (i = 0; i < 8; i++) {
319 inv->cp[arr->cp[i]] = i;
320 inv->coud[arr->cp[i]] = (3 - arr->coud[i]) % 3;
321 inv->corl[arr->cp[i]] = (3 - arr->corl[i]) % 3;
322 inv->cofb[arr->cp[i]] = (3 - arr->cofb[i]) % 3;
323 }
324
325 for (int i = 0; i < 6; i++)
326 inv->cpos[arr->cpos[i]] = i;
327
328 ret = arrays_to_cube(inv, pf_all);
329 free_cubearray(arr, pf_all);
330 free_cubearray(inv, pf_all);
331
332 return ret;
333}
334
335bool
336is_admissible(Cube cube)
337{
338 /* TODO: this should check consistency of different orientations */
339 /* TODO: check that centers are opposite and admissible */
340
341 CubeArray *a = new_cubearray(cube, pf_all);
342 int parity;
343 bool perm;
344
345 perm = is_perm(a->ep, 12) &&
346 is_perm(a->cp, 8) &&
347 is_perm(a->cpos, 6);
348 parity = perm_sign(a->ep, 12) +
349 perm_sign(a->cp, 8) +
350 perm_sign(a->cpos, 6);
351
352 return perm && parity % 2 == 0;
353}
354
355bool
356is_solved(Cube cube)
357{
358 /* TODO: move somewhere else, like in solve.c
359 int i;
360 if (reorient) {
361 for (i = 0; i < NROTATIONS; i++)
362 if (is_solved(apply_alg(rotation_algs[i], cube),false))
363 return true;
364 return false;
365 } else {
366 return equal(cube, (Cube){0});
367 }
368 */
369
370 return equal(cube, (Cube){0});
371}
372
373bool
374is_solved_block(Cube cube, Block block)
375{
376 int i;
377
378 for (i = 0; i < 12; i++)
379 if (block.edge[i] && !is_solved_edge(cube, i))
380 return false;
381 for (i = 0; i < 8; i++)
382 if (block.corner[i] && !is_solved_corner(cube, i))
383 return false;
384 for (i = 0; i < 6; i++)
385 if (block.center[i] && !is_solved_center(cube, i))
386 return false;
387
388 return true;
389}
390
391bool
392is_solved_center(Cube cube, Center c)
393{
394 return what_center_at(cube, c) == c;
395}
396
397bool
398is_solved_corner(Cube cube, Corner c)
399{
400 return what_corner_at(cube, c) == c &&
401 what_orientation_corner(cube.coud, c);
402}
403
404bool
405is_solved_edge(Cube cube, Edge e)
406{
407 return what_edge_at(cube, e) == e &&
408 what_orientation_edge(cube.eofb, e);
409}
410
411int
412piece_orientation(Cube cube, int piece, char *orientation)
413{
414 int arr[12], n, b, x;
415
416 if (!strcmp(orientation, "eofb")) {
417 x = cube.eofb;
418 n = 12;
419 b = 2;
420 } else if (!strcmp(orientation, "eorl")) {
421 x = cube.eorl;
422 n = 12;
423 b = 2;
424 } else if (!strcmp(orientation, "eoud")) {
425 x = cube.eoud;
426 n = 12;
427 b = 2;
428 } else if (!strcmp(orientation, "coud")) {
429 x = cube.coud;
430 n = 8;
431 b = 3;
432 } else if (!strcmp(orientation, "corl")) {
433 x = cube.corl;
434 n = 8;
435 b = 3;
436 } else if (!strcmp(orientation, "cofb")) {
437 x = cube.cofb;
438 n = 8;
439 b = 3;
440 } else {
441 return -1;
442 }
443
444 int_to_sum_zero_array(x, b, n, arr);
445 if (piece < n)
446 return arr[piece];
447
448 return -1;
449}
450
451void
452print_cube(Cube cube)
453{
454 static char edge_string[12][7] = {
455 [UF] = "UF", [UL] = "UL", [UB] = "UB", [UR] = "UR",
456 [DF] = "DF", [DL] = "DL", [DB] = "DB", [DR] = "DR",
457 [FR] = "FR", [FL] = "FL", [BL] = "BL", [BR] = "BR"
458 };
459
460 static char corner_string[8][7] = {
461 [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR",
462 [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR"
463 };
464
465 static char center_string[6][7] = {
466 [U_center] = "U", [D_center] = "D",
467 [R_center] = "R", [L_center] = "L",
468 [F_center] = "F", [B_center] = "B"
469 };
470
471 for (int i = 0; i < 12; i++)
472 printf(" %s ", edge_string[what_edge_at(cube, i)]);
473 printf("\n");
474
475 for (int i = 0; i < 12; i++)
476 printf(" %d ", what_orientation_edge(cube.eofb, i));
477 printf("\n");
478
479 for (int i = 0; i < 8; i++)
480 printf("%s ", corner_string[what_corner_at(cube, i)]);
481 printf("\n");
482
483 for (int i = 0; i < 8; i++)
484 printf(" %d ", what_orientation_corner(cube.coud, i));
485 printf("\n");
486
487 for (int i = 0; i < 6; i++)
488 printf(" %s ", center_string[what_center_at(cube, i)]);
489 printf("\n");
490}
491
492Cube
493random_cube()
494{
495 CubeArray *arr = new_cubearray((Cube){0}, pf_4val);
496 Cube ret;
497 int ep, cp, eo, co;
498
499 ep = rand() % FACTORIAL12;
500 cp = rand() % FACTORIAL8;
501 eo = rand() % POW2TO11;
502 co = rand() % POW3TO7;
503
504 index_to_perm(ep, 12, arr->ep);
505 index_to_perm(cp, 8, arr->cp);
506 int_to_sum_zero_array(eo, 2, 12, arr->eofb);
507 int_to_sum_zero_array(co, 3, 8, arr->coud);
508
509 if (perm_sign(arr->ep, 12) != perm_sign(arr->cp, 8))
510 swap(&(arr->ep[0]), &(arr->ep[1]));
511
512 ret = arrays_to_cube(arr, pf_4val);
513 free_cubearray(arr, pf_4val);
514
515 return ret;
516}
517
518Center
519what_center_at(Cube cube, Center c)
520{
521 static bool initialized = false;
522 static Center aux[FACTORIAL6][6];
523 static int i;
524 static unsigned int ui;
525 static CubeArray *arr;
526
527 if (!initialized) {
528 for (ui = 0; ui < FACTORIAL6; ui++) {
529 arr = new_cubearray((Cube){.cpos = ui}, pf_cpos);
530 for (i = 0; i < 6; i++)
531 aux[ui][i] = arr->cpos[i];
532 free_cubearray(arr, pf_cpos);
533 }
534
535 initialized = true;
536 }
537
538 return aux[cube.cpos][c];
539}
540
541Corner
542what_corner_at(Cube cube, Corner c)
543{
544 static bool initialized = false;
545 static Corner aux[FACTORIAL8][8];
546 static int i;
547 static unsigned int ui;
548 static CubeArray *arr;
549
550 if (!initialized) {
551 for (ui = 0; ui < FACTORIAL8; ui++) {
552 arr = new_cubearray((Cube){.cp = ui}, pf_cp);
553 for (i = 0; i < 8; i++)
554 aux[ui][i] = arr->cp[i];
555 free_cubearray(arr, pf_cp);
556 }
557
558 initialized = true;
559 }
560
561 return aux[cube.cp][c];
562}
563
564Edge
565what_edge_at(Cube cube, Edge e)
566{
567 Edge ret;
568 CubeArray *arr = new_cubearray(cube, pf_ep);
569
570 ret = arr->ep[e];
571
572 free_cubearray(arr, pf_ep);
573 return ret;
574}
575
576int
577what_orientation_corner(int co, Corner c)
578{
579 static bool initialized = false;
580 static int auxlast[POW3TO7];
581 static int auxarr[8];
582 static unsigned int ui;
583
584 if (!initialized) {
585 for (ui = 0; ui < POW3TO7; ui++) {
586 int_to_sum_zero_array(ui, 3, 8, auxarr);
587 auxlast[ui] = auxarr[7];
588 }
589
590 initialized = true;
591 }
592
593 if (c < 7)
594 return (co / powint(3, c)) % 3;
595 else
596 return auxlast[co];
597}
598
599int
600what_orientation_edge(int eo, Edge e)
601{
602 static bool initialized = false;
603 static int auxlast[POW2TO11];
604 static int auxarr[12];
605 static unsigned int ui;
606
607 if (!initialized) {
608 for (ui = 0; ui < POW2TO11; ui++) {
609 int_to_sum_zero_array(ui, 2, 12, auxarr);
610 auxlast[ui] = auxarr[11];
611 }
612
613 initialized = true;
614 }
615
616 if (e < 11)
617 return (eo & (1 << e)) ? 1 : 0;
618 else
619 return auxlast[eo];
620}
621
622Center
623where_is_center(Cube cube, Center c)
624{
625 static bool initialized = false;
626 static Center aux[FACTORIAL6][6];
627 static int i;
628 static unsigned int ui;
629 static CubeArray *arr;
630
631 if (!initialized) {
632 for (ui = 0; ui < FACTORIAL6; ui++) {
633 arr = new_cubearray((Cube){.cpos = ui}, pf_cpos);
634 for (i = 0; i < 6; i++)
635 aux[ui][arr->cpos[i]] = i;
636 free_cubearray(arr, pf_cpos);
637 }
638
639 initialized = true;
640 }
641
642 return aux[cube.cpos][c];
643}
644
645Corner
646where_is_corner(Cube cube, Corner c)
647{
648 static bool initialized = false;
649 static Corner aux[FACTORIAL8][8];
650 static int i;
651 static unsigned int ui;
652 static CubeArray *arr;
653
654 if (!initialized) {
655 for (ui = 0; ui < FACTORIAL8; ui++) {
656 arr = new_cubearray((Cube){.cp = ui}, pf_cp);
657 for (i = 0; i < 8; i++)
658 aux[ui][arr->cp[i]] = i;
659 free_cubearray(arr, pf_cp);
660 }
661
662 initialized = true;
663 }
664 return aux[cube.cp][c];
665}
666
667Edge
668where_is_edge(Cube cube, Edge e)
669{
670 /* TODO: when I wrote this code I forgot to add the final
671 part, and now I can't remember how it was supposed to
672 work (i.e. how to recover the location of the edge
673 from these tables. I think it is either very easy or
674 wrong, in any case it is not a priority now.
675 Future Seba can deal with it.
676
677 static bool initialized = false;
678 static Edge aux[3][FACTORIAL12/FACTORIAL8][12];
679 static int i;
680 static unsigned int ui;
681 static CubeArray *arr;
682
683 if (!initialized) {
684 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
685 arr = new_cubearray((Cube){.epose = ui}, pf_e);
686 for (i = 0; i < 12; i++)
687 if (edge_slice(arr->ep[i]) == 0)
688 aux[0][ui][arr->ep[i]] = i;
689 free_cubearray(arr, pf_e);
690
691 arr = new_cubearray((Cube){.eposs = ui}, pf_s);
692 for (i = 0; i < 12; i++)
693 if (edge_slice(arr->ep[i]) == 1)
694 aux[1][ui][arr->ep[i]] = i;
695 free_cubearray(arr, pf_s);
696
697 arr = new_cubearray((Cube){.eposm = ui}, pf_m);
698 for (i = 0; i < 12; i++)
699 if (edge_slice(arr->ep[i]) == 2)
700 aux[2][ui][arr->ep[i]] = i;
701 free_cubearray(arr, pf_m);
702 }
703
704 initialized = true;
705 }
706 */
707
708 int i;
709 CubeArray *arr = new_cubearray(cube, pf_ep);
710
711 for (i = 0; i < 12; i++)
712 if ((Edge)arr->ep[i] == e)
713 return i;
714
715 return -1;
716}
diff --git a/old/2021-11-10-beforeremovingchecker/cube.h b/old/2021-11-10-beforeremovingchecker/cube.h
new file mode 100644
index 0000000..98657ab
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/cube.h
@@ -0,0 +1,40 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5#include <time.h>
6
7#include "pf.h"
8#include "utils.h"
9
10Cube admissible_ep(Cube cube, PieceFilter f); /* TODO: move? */
11Cube arrays_to_cube(CubeArray *arr, PieceFilter f); /* TODO: remove */
12Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */
13Cube compose_filtered(Cube c2, Cube c1, PieceFilter f);
14void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f);
15int edge_slice(Edge e); /* E=0, S=1, M=2 */
16bool equal(Cube c1, Cube c2);
17Cube inverse_cube(Cube cube);
18bool is_admissible(Cube cube);
19bool is_solved(Cube cube);
20bool block_solved(Cube cube, Block); /*TODO: rename to is_solved_block()*/
21bool is_solved_center(Cube cube, Center c);
22bool is_solved_corner(Cube cube, Corner c);
23bool is_solved_edge(Cube cube, Edge e);
24void epos_to_partial_ep(int epos, int *ep, int *ss);
25void free_cubearray(CubeArray *arr, PieceFilter f); /* TODO: remove */
26Cube move_via_arrays(CubeArray *arr, Cube c, PieceFilter pf);
27CubeArray * new_cubearray(Cube cube, PieceFilter f); /* TODO: remove */
28void print_cube(Cube cube);
29Cube random_cube();
30Center what_center_at(Cube cube, Center c);
31Corner what_corner_at(Cube cube, Corner c);
32Edge what_edge_at(Cube cube, Edge e);
33int what_orientation_corner(int co, Corner c);
34int what_orientation_edge(int eo, Edge e);
35Center where_is_center(Cube cube, Center c);
36Corner where_is_corner(Cube cube, Corner c);
37Edge where_is_edge(Cube cube, Edge e);
38
39#endif
40
diff --git a/old/2021-11-10-beforeremovingchecker/cubetypes.h b/old/2021-11-10-beforeremovingchecker/cubetypes.h
new file mode 100644
index 0000000..38a6f8d
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/cubetypes.h
@@ -0,0 +1,298 @@
1#ifndef CUBETYPES_H
2#define CUBETYPES_H
3
4#include <stdbool.h>
5#include <stdint.h>
6
7#define NMOVES 55 /* Actually 55, but one is NULLMOVE */
8#define NTRANS 48
9#define NROTATIONS 24
10
11
12/* Typedefs ******************************************************************/
13
14typedef enum center Center;
15typedef enum corner Corner;
16typedef enum edge Edge;
17typedef enum move Move;
18typedef enum trans Trans;
19
20typedef struct alg Alg;
21typedef struct alglist AlgList;
22typedef struct alglistnode AlgListNode;
23typedef struct block Block;
24typedef struct command Command;
25typedef struct commandargs CommandArgs;
26typedef struct coordinate Coordinate;
27typedef struct cube Cube;
28typedef struct cubearray CubeArray;
29typedef struct cubetarget CubeTarget;
30typedef struct dfsdata DfsData;
31typedef struct piecefilter PieceFilter;
32typedef struct prunedata PruneData;
33typedef struct solveoptions SolveOptions;
34typedef struct step Step;
35typedef struct symdata SymData;
36
37typedef Cube (*AntiIndexer) (uint64_t);
38typedef bool (*Checker) (Cube);
39typedef int (*Estimator) (CubeTarget);
40typedef bool (*Validator) (Alg *);
41typedef void (*Exec) (CommandArgs *);
42typedef uint64_t (*Indexer) (Cube);
43typedef bool (*Moveset) (Move);
44typedef CommandArgs * (*ArgParser) (int, char **);
45typedef Trans (*TransDetector) (Cube);
46
47
48/* Enums *********************************************************************/
49
50enum
51center
52{
53 U_center, D_center,
54 R_center, L_center,
55 F_center, B_center
56};
57
58enum
59corner
60{
61 UFR, UFL, UBL, UBR,
62 DFR, DFL, DBL, DBR
63};
64
65enum
66edge
67{
68 UF, UL, UB, UR,
69 DF, DL, DB, DR,
70 FR, FL, BL, BR
71};
72
73enum
74move
75{
76 NULLMOVE,
77 U, U2, U3, D, D2, D3,
78 R, R2, R3, L, L2, L3,
79 F, F2, F3, B, B2, B3,
80 Uw, Uw2, Uw3, Dw, Dw2, Dw3,
81 Rw, Rw2, Rw3, Lw, Lw2, Lw3,
82 Fw, Fw2, Fw3, Bw, Bw2, Bw3,
83 M, M2, M3,
84 S, S2, S3,
85 E, E2, E3,
86 x, x2, x3,
87 y, y2, y3,
88 z, z2, z3,
89};
90
91enum
92trans
93{
94 uf, ur, ub, ul,
95 df, dr, db, dl,
96 rf, rd, rb, ru,
97 lf, ld, lb, lu,
98 fu, fr, fd, fl,
99 bu, br, bd, bl,
100 uf_mirror, ur_mirror, ub_mirror, ul_mirror,
101 df_mirror, dr_mirror, db_mirror, dl_mirror,
102 rf_mirror, rd_mirror, rb_mirror, ru_mirror,
103 lf_mirror, ld_mirror, lb_mirror, lu_mirror,
104 fu_mirror, fr_mirror, fd_mirror, fl_mirror,
105 bu_mirror, br_mirror, bd_mirror, bl_mirror,
106};
107
108
109/* Structs *******************************************************************/
110
111struct
112alg
113{
114 Move * move;
115 bool * inv;
116 int len;
117 int allocated;
118};
119
120struct
121alglist
122{
123 AlgListNode * first;
124 AlgListNode * last;
125 int len;
126};
127
128struct
129alglistnode
130{
131 Alg * alg;
132 AlgListNode * next;
133};
134
135struct
136block
137{
138 bool edge[12];
139 bool corner[8];
140 bool center[6];
141};
142
143struct
144command
145{
146 /* TODO: more stuff to add? maybe complete help? */
147 /* Maybe add list of options */
148 char * name;
149 char * usage;
150 char * description;
151 ArgParser parse_args;
152 Exec exec;
153};
154
155struct
156commandargs
157{
158 bool success;
159 Alg * scramble;
160 SolveOptions * opts;
161 Step * step;
162 Command * command; /* For help */
163};
164
165struct
166coordinate
167{
168 Indexer index;
169 AntiIndexer cube;
170 Checker check;
171 uint64_t max;
172 int ntrans;
173 Trans * trans;
174};
175
176struct
177cube
178{
179 int epose;
180 int eposs;
181 int eposm;
182 int eofb;
183 int eorl;
184 int eoud;
185 int cp;
186 int coud;
187 int cofb;
188 int corl;
189 int cpos;
190};
191
192struct
193cubearray
194{
195 int * ep;
196 int * eofb;
197 int * eorl;
198 int * eoud;
199 int * cp;
200 int * coud;
201 int * corl;
202 int * cofb;
203 int * cpos;
204};
205
206struct
207cubetarget
208{
209 Cube cube;
210 int target;
211};
212
213struct
214dfsdata
215{
216 int d;
217 int m;
218 int lb;
219 bool niss;
220 Move last1;
221 Move last2;
222 AlgList * sols;
223 Alg * current_alg;
224 Move sorted_moves[NMOVES];
225 int move_position[NMOVES];
226};
227
228struct
229piecefilter
230{
231 bool epose;
232 bool eposs;
233 bool eposm;
234 bool eofb;
235 bool eorl;
236 bool eoud;
237 bool cp;
238 bool coud;
239 bool cofb;
240 bool corl;
241 bool cpos;
242};
243
244struct
245prunedata
246{
247 char * filename;
248 uint8_t * ptable;
249 bool generated;
250 uint64_t n;
251 Coordinate * coord;
252 Moveset moveset;
253};
254
255struct
256solveoptions
257{
258 /* TODO: add option to list *all* solutions satisfying other
259 constraints (min/max moves and optimality) */
260 int min_moves;
261 int max_moves;
262 int max_solutions;
263 bool optimal_only;
264 bool can_niss;
265 bool feedback; /* TODO: rename with "verbose" */
266 bool all;
267 bool print_number;
268};
269
270struct
271step
272{
273 char * shortname;
274 char * name;
275 Estimator estimate;
276 Checker ready;
277 char * ready_msg;
278 Validator is_valid;
279 Moveset moveset;
280 Trans pre_trans;
281 TransDetector detect;
282};
283
284struct
285symdata
286{
287 char * filename;
288 bool generated;
289 Coordinate * coord;
290 Coordinate * sym_coord;
291 int ntrans;
292 Trans * trans;
293 uint64_t * class;
294 Cube * rep;
295 Trans * transtorep;
296};
297
298#endif
diff --git a/old/2021-11-10-beforeremovingchecker/env.c b/old/2021-11-10-beforeremovingchecker/env.c
new file mode 100644
index 0000000..d13642f
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/env.c
@@ -0,0 +1,45 @@
1#include "env.h"
2
3bool initialized_env = false;
4char *tabledir;
5
6void
7init_env()
8{
9 char *nissydata = getenv("NISSYDATA");
10 char *localdata = getenv("XDG_DATA_HOME");
11 char *home = getenv("HOME");
12 bool read, write;
13
14 if (initialized_env)
15 return;
16
17 if (nissydata != NULL) {
18 tabledir = malloc(strlen(nissydata) * sizeof(char) + 20);
19 strcpy(tabledir, nissydata);
20 } else if (localdata != NULL) {
21 tabledir = malloc(strlen(localdata) * sizeof(char) + 20);
22 strcpy(tabledir, localdata);
23 strcat(tabledir, "/nissy");
24 } else if (home != NULL) {
25 tabledir = malloc(strlen(home) * sizeof(char) + 20);
26 strcpy(tabledir, home);
27 strcat(tabledir, "/.nissy");
28 }
29
30 mkdir(tabledir, 0777);
31 strcat(tabledir, "/tables");
32 mkdir(tabledir, 0777);
33
34 read = !access(tabledir, R_OK);
35 write = !access(tabledir, W_OK);
36
37 if (!read) {
38 fprintf(stderr, "Table files cannot be read.\n");
39 } else if (!write) {
40 fprintf(stderr, "Data directory not writable: ");
41 fprintf(stderr, "tables can be loaded, but not saved.\n");
42 }
43
44 initialized_env = true;
45}
diff --git a/old/2021-11-10-beforeremovingchecker/env.h b/old/2021-11-10-beforeremovingchecker/env.h
new file mode 100644
index 0000000..871a9c1
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/env.h
@@ -0,0 +1,15 @@
1#ifndef ENV_H
2#define ENV_H
3
4#include <stdbool.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8#include <unistd.h>
9#include <sys/stat.h>
10
11extern char *tabledir;
12
13void init_env();
14
15#endif
diff --git a/old/2021-11-10-beforeremovingchecker/moves.c b/old/2021-11-10-beforeremovingchecker/moves.c
new file mode 100644
index 0000000..5ba17ca
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/moves.c
@@ -0,0 +1,474 @@
1#include "moves.h"
2
3/* Local functions ***********************************************************/
4
5static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f);
6static bool read_mtables_file();
7static bool write_mtables_file();
8
9/* Tables and other data *****************************************************/
10
11/* Every move is translated to a an <U, x, y> alg before filling the
12 transition tables, see init_moves() */
13
14static int edge_cycle[NMOVES][12] =
15{
16 [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
17 [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
18 [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }
19};
20
21static int corner_cycle[NMOVES][8] =
22{
23 [U] = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR },
24 [x] = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
25 [y] = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL }
26};
27
28static int center_cycle[NMOVES][6] =
29{
30 [x] = { F_center, B_center, R_center, L_center, D_center, U_center },
31 [y] = { U_center, D_center, B_center, F_center, R_center, L_center }
32};
33
34static int eofb_flipped[NMOVES][12] = {
35 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
36 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
37};
38
39static int eorl_flipped[NMOVES][12] = {
40 [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
41 [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }
42};
43
44static int eoud_flipped[NMOVES][12] = {
45 [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 },
46 [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
47 [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
48};
49
50static int coud_flipped[NMOVES][8] = {
51 [x] = {
52 [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
53 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2
54 }
55};
56
57static int corl_flipped[NMOVES][8] = {
58 [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 },
59 [y] = {
60 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
61 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
62 }
63};
64
65static int cofb_flipped[NMOVES][8] = {
66 [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 },
67 [x] = {
68 [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2,
69 [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1
70 },
71 [y] = {
72 [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1,
73 [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2
74 }
75};
76
77static char equiv_alg_string[100][NMOVES] = {
78 [NULLMOVE] = "",
79
80 [U] = " U ",
81 [U2] = " UU ",
82 [U3] = " UUU ",
83 [D] = " xx U xx ",
84 [D2] = " xx UU xx ",
85 [D3] = " xx UUU xx ",
86 [R] = " yx U xxxyyy ",
87 [R2] = " yx UU xxxyyy ",
88 [R3] = " yx UUU xxxyyy ",
89 [L] = " yyyx U xxxy ",
90 [L2] = " yyyx UU xxxy ",
91 [L3] = " yyyx UUU xxxy ",
92 [F] = " x U xxx ",
93 [F2] = " x UU xxx ",
94 [F3] = " x UUU xxx ",
95 [B] = " xxx U x ",
96 [B2] = " xxx UU x ",
97 [B3] = " xxx UUU x ",
98
99 [Uw] = " xx U xx y ",
100 [Uw2] = " xx UU xx yy ",
101 [Uw3] = " xx UUU xx yyy ",
102 [Dw] = " U yyy ",
103 [Dw2] = " UU yy ",
104 [Dw3] = " UUU y ",
105 [Rw] = " yyyx U xxxy x ",
106 [Rw2] = " yyyx UU xxxy xx ",
107 [Rw3] = " yyyx UUU xxxy xxx ",
108 [Lw] = " yx U xxxyyy xxx ",
109 [Lw2] = " yx UU xxxyyy xx ",
110 [Lw3] = " yx UUU xxxyyy x ",
111 [Fw] = " xxx U x yxxxyyy ",
112 [Fw2] = " xxx UU x yxxyyy ",
113 [Fw3] = " xxx UUU x yxyyy ",
114 [Bw] = " x U xxx yxyyy ",
115 [Bw2] = " x UU xxx yxxyyy ",
116 [Bw3] = " x UUU xxx yxxxyyy ",
117
118 [M] = " yx U xx UUU yxyyy ",
119 [M2] = " yx UU xx UU xxxy ",
120 [M3] = " yx UUU xx U yxxxy ",
121 [S] = " x UUU xx U yyyx ",
122 [S2] = " x UU xx UU yyx ",
123 [S3] = " x U xx UUU yx ",
124 [E] = " U xx UUU xxyyy ",
125 [E2] = " UU xx UU xxyy ",
126 [E3] = " UUU xx U xxy ",
127
128 [x] = " x ",
129 [x2] = " xx ",
130 [x3] = " xxx ",
131 [y] = " y ",
132 [y2] = " yy ",
133 [y3] = " yyy ",
134 [z] = " yyy x y ",
135 [z2] = " yy xx ",
136 [z3] = " y x yyy "
137};
138
139/* Transition tables, to be loaded up at the beginning */
140static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
141static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
142static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8];
143static int eofb_mtable[NMOVES][POW2TO11];
144static int eorl_mtable[NMOVES][POW2TO11];
145static int eoud_mtable[NMOVES][POW2TO11];
146static int cp_mtable[NMOVES][FACTORIAL8];
147static int coud_mtable[NMOVES][POW3TO7];
148static int cofb_mtable[NMOVES][POW3TO7];
149static int corl_mtable[NMOVES][POW3TO7];
150static int cpos_mtable[NMOVES][FACTORIAL6];
151
152
153/* Local functions implementation ********************************************/
154
155static Cube
156apply_move_cubearray(Move m, Cube cube, PieceFilter f)
157{
158 /*init_moves();*/
159
160 CubeArray m_arr = {
161 edge_cycle[m],
162 eofb_flipped[m],
163 eorl_flipped[m],
164 eoud_flipped[m],
165 corner_cycle[m],
166 coud_flipped[m],
167 corl_flipped[m],
168 cofb_flipped[m],
169 center_cycle[m]
170 };
171
172 return move_via_arrays(&m_arr, cube, f);
173}
174
175/* Public functions **********************************************************/
176
177Cube
178apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a)
179{
180 Cube ret = {0};
181 int i;
182
183 for (i = 0; i < alg->len; i++)
184 if (alg->inv[i])
185 ret = a ? apply_move(alg->move[i], ret) :
186 apply_move_cubearray(alg->move[i], ret, f);
187
188 ret = compose_filtered(c, inverse_cube(ret), f);
189
190 for (i = 0; i < alg->len; i++)
191 if (!alg->inv[i])
192 ret = a ? apply_move(alg->move[i], ret) :
193 apply_move_cubearray(alg->move[i], ret, f);
194
195 return ret;
196}
197
198Cube
199apply_alg(Alg *alg, Cube cube)
200{
201 return apply_alg_generic(alg, cube, pf_all, true);
202}
203
204Cube
205apply_move(Move m, Cube cube)
206{
207 /*init_moves();*/
208
209 return (Cube) {
210 .epose = epose_mtable[m][cube.epose],
211 .eposs = eposs_mtable[m][cube.eposs],
212 .eposm = eposm_mtable[m][cube.eposm],
213 .eofb = eofb_mtable[m][cube.eofb],
214 .eorl = eorl_mtable[m][cube.eorl],
215 .eoud = eoud_mtable[m][cube.eoud],
216 .coud = coud_mtable[m][cube.coud],
217 .cofb = cofb_mtable[m][cube.cofb],
218 .corl = corl_mtable[m][cube.corl],
219 .cp = cp_mtable[m][cube.cp],
220 .cpos = cpos_mtable[m][cube.cpos]
221 };
222}
223
224void
225init_moves() {
226 static bool initialized = false;
227 if (initialized)
228 return;
229 initialized = true;
230
231 Cube c;
232 CubeArray arrs;
233 int i;
234 unsigned int ui;
235 Move m;
236 Alg *equiv_alg[NMOVES];
237
238 for (i = 0; i < NMOVES; i++)
239 equiv_alg[i] = new_alg(equiv_alg_string[i]);
240
241 /* Generate all move cycles and flips; I do this regardless */
242 for (i = 0; i < NMOVES; i++) {
243 if (i == U || i == x || i == y)
244 continue;
245
246 c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false);
247
248 arrs = (CubeArray) {
249 edge_cycle[i],
250 eofb_flipped[i],
251 eorl_flipped[i],
252 eoud_flipped[i],
253 corner_cycle[i],
254 coud_flipped[i],
255 corl_flipped[i],
256 cofb_flipped[i],
257 center_cycle[i]
258 };
259 cube_to_arrays(c, &arrs, pf_all);
260 }
261
262 if (read_mtables_file())
263 return;
264
265 fprintf(stderr, "Cannot load %s, generating it\n", "mtables");
266
267 /* Initialize transition tables */
268 for (m = 0; m < NMOVES; m++) {
269 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
270 c = (Cube){ .epose = ui };
271 c = apply_move_cubearray(m, c, pf_e);
272 epose_mtable[m][ui] = c.epose;
273
274 c = (Cube){ .eposs = ui };
275 c = apply_move_cubearray(m, c, pf_s);
276 eposs_mtable[m][ui] = c.eposs;
277
278 c = (Cube){ .eposm = ui };
279 c = apply_move_cubearray(m, c, pf_m);
280 eposm_mtable[m][ui] = c.eposm;
281 }
282 for (ui = 0; ui < POW2TO11; ui++ ) {
283 c = (Cube){ .eofb = ui };
284 c = apply_move_cubearray(m, c, pf_eo);
285 eofb_mtable[m][ui] = c.eofb;
286
287 c = (Cube){ .eorl = ui };
288 c = apply_move_cubearray(m, c, pf_eo);
289 eorl_mtable[m][ui] = c.eorl;
290
291 c = (Cube){ .eoud = ui };
292 c = apply_move_cubearray(m, c, pf_eo);
293 eoud_mtable[m][ui] = c.eoud;
294 }
295 for (ui = 0; ui < POW3TO7; ui++) {
296 c = (Cube){ .coud = ui };
297 c = apply_move_cubearray(m, c, pf_co);
298 coud_mtable[m][ui] = c.coud;
299
300 c = (Cube){ .corl = ui };
301 c = apply_move_cubearray(m, c, pf_co);
302 corl_mtable[m][ui] = c.corl;
303
304 c = (Cube){ .cofb = ui };
305 c = apply_move_cubearray(m, c, pf_co);
306 cofb_mtable[m][ui] = c.cofb;
307 }
308 for (ui = 0; ui < FACTORIAL8; ui++) {
309 c = (Cube){ .cp = ui };
310 c = apply_move_cubearray(m, c, pf_cp);
311 cp_mtable[m][ui] = c.cp;
312 }
313 for (ui = 0; ui < FACTORIAL6; ui++) {
314 c = (Cube){ .cpos = ui };
315 c = apply_move_cubearray(m, c, pf_cpos);
316 cpos_mtable[m][ui] = c.cpos;
317 }
318 }
319
320 if (!write_mtables_file())
321 fprintf(stderr, "Error writing mtables\n");
322
323 for (i = 0; i < NMOVES; i++)
324 free_alg(equiv_alg[i]);
325}
326
327static bool
328read_mtables_file()
329{
330 init_env();
331
332 FILE *f;
333 char fname[strlen(tabledir)+20];
334 int m, b = sizeof(int);
335 bool r = true;
336
337 /* Table sizes, used for reading and writing files */
338 uint64_t me[11] = {
339 [0] = FACTORIAL12/FACTORIAL8,
340 [1] = FACTORIAL12/FACTORIAL8,
341 [2] = FACTORIAL12/FACTORIAL8,
342 [3] = POW2TO11,
343 [4] = POW2TO11,
344 [5] = POW2TO11,
345 [6] = FACTORIAL8,
346 [7] = POW3TO7,
347 [8] = POW3TO7,
348 [9] = POW3TO7,
349 [10] = FACTORIAL6
350 };
351
352 strcpy(fname, tabledir);
353 strcat(fname, "/mtables");
354
355 if ((f = fopen(fname, "rb")) == NULL)
356 return false;
357
358 for (m = 0; m < NMOVES; m++) {
359 r = r && fread(epose_mtable[m], b, me[0], f) == me[0];
360 r = r && fread(eposs_mtable[m], b, me[1], f) == me[1];
361 r = r && fread(eposm_mtable[m], b, me[2], f) == me[2];
362 r = r && fread(eofb_mtable[m], b, me[3], f) == me[3];
363 r = r && fread(eorl_mtable[m], b, me[4], f) == me[4];
364 r = r && fread(eoud_mtable[m], b, me[5], f) == me[5];
365 r = r && fread(cp_mtable[m], b, me[6], f) == me[6];
366 r = r && fread(coud_mtable[m], b, me[7], f) == me[7];
367 r = r && fread(corl_mtable[m], b, me[8], f) == me[8];
368 r = r && fread(cofb_mtable[m], b, me[9], f) == me[9];
369 r = r && fread(cpos_mtable[m], b, me[10], f) == me[10];
370 }
371
372 fclose(f);
373 return r;
374}
375
376static bool
377write_mtables_file()
378{
379 init_env();
380
381 FILE *f;
382 char fname[strlen(tabledir)+20];
383 int m, b = sizeof(int);
384 bool r = true;
385
386 /* Table sizes, used for reading and writing files */
387 uint64_t me[11] = {
388 [0] = FACTORIAL12/FACTORIAL8,
389 [1] = FACTORIAL12/FACTORIAL8,
390 [2] = FACTORIAL12/FACTORIAL8,
391 [3] = POW2TO11,
392 [4] = POW2TO11,
393 [5] = POW2TO11,
394 [6] = FACTORIAL8,
395 [7] = POW3TO7,
396 [8] = POW3TO7,
397 [9] = POW3TO7,
398 [10] = FACTORIAL6
399 };
400
401 strcpy(fname, tabledir);
402 strcat(fname, "/mtables");
403
404 if ((f = fopen(fname, "wb")) == NULL)
405 return false;
406
407 for (m = 0; m < NMOVES; m++) {
408 r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0];
409 r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1];
410 r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2];
411 r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3];
412 r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4];
413 r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5];
414 r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6];
415 r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7];
416 r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8];
417 r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9];
418 r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10];
419 }
420
421 fclose(f);
422 return r;
423}
424
425bool
426commute(Move m1, Move m2)
427{
428 static bool initialized = false;
429 static bool commute_aux[NMOVES][NMOVES];
430
431 if (!initialized) {
432 Cube c1, c2;
433 int i, j;
434
435 for (i = 0; i < NMOVES; i++) {
436 for (j = 0; j < NMOVES; j++) {
437 c1 = apply_move(i, apply_move(j, (Cube){0}));
438 c2 = apply_move(j, apply_move(i, (Cube){0}));
439 commute_aux[i][j] = equal(c1, c2) && i && j;
440 }
441 }
442
443 initialized = true;
444 }
445
446 return commute_aux[m1][m2];
447}
448
449bool
450possible_next(Move m1, Move m2, Move m3)
451{
452 static bool initialized = false;
453 static bool paux[NMOVES][NMOVES][NMOVES];
454
455 if (!initialized) {
456 int i, j, k;
457 bool p, q, c;
458
459 for (i = 0; i < NMOVES; i++) {
460 for (j = 0; j < NMOVES; j++) {
461 for (k = 0; k < NMOVES; k++) {
462 p = j && base_move(j) == base_move(k);
463 q = i && base_move(i) == base_move(k);
464 c = commute(i, j);
465 paux[i][j][k] = !(p || (c && q));
466 }
467 }
468 }
469
470 initialized = true;
471 }
472
473 return paux[m1][m2][m3];
474}
diff --git a/old/2021-11-10-beforeremovingchecker/moves.h b/old/2021-11-10-beforeremovingchecker/moves.h
new file mode 100644
index 0000000..082a080
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/moves.h
@@ -0,0 +1,16 @@
1#ifndef MOVES_H
2#define MOVES_H
3
4#include "alg.h"
5#include "cube.h"
6#include "env.h"
7
8Cube apply_alg(Alg *alg, Cube cube);
9Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a);
10Cube apply_move(Move m, Cube cube);
11bool commute(Move m1, Move m2);
12bool possible_next(Move m1, Move m2, Move m3);
13
14void init_moves();
15
16#endif
diff --git a/old/2021-11-10-beforeremovingchecker/pf.c b/old/2021-11-10-beforeremovingchecker/pf.c
new file mode 100644
index 0000000..34be4fd
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/pf.c
@@ -0,0 +1,80 @@
1#include "pf.h"
2
3PieceFilter
4pf_all = {
5 .epose = true,
6 .eposs = true,
7 .eposm = true,
8 .eofb = true,
9 .eorl = true,
10 .eoud = true,
11 .cp = true,
12 .cofb = true,
13 .corl = true,
14 .coud = true,
15 .cpos = true
16};
17
18PieceFilter
19pf_4val = {
20 .epose = true,
21 .eposs = true,
22 .eposm = true,
23 .eofb = true,
24 .coud = true,
25 .cp = true
26};
27
28PieceFilter
29pf_epcp = {
30 .epose = true,
31 .eposs = true,
32 .eposm = true,
33 .cp = true
34};
35
36PieceFilter
37pf_cpos = {
38 .cpos = true
39};
40
41PieceFilter
42pf_cp = {
43 .cp = true
44};
45
46PieceFilter
47pf_ep = {
48 .epose = true,
49 .eposs = true,
50 .eposm = true
51};
52
53PieceFilter
54pf_e = {
55 .epose = true
56};
57
58PieceFilter
59pf_s = {
60 .eposs = true
61};
62
63PieceFilter
64pf_m = {
65 .eposm = true
66};
67
68PieceFilter
69pf_eo = {
70 .eofb = true,
71 .eorl = true,
72 .eoud = true
73};
74
75PieceFilter
76pf_co = {
77 .cofb = true,
78 .corl = true,
79 .coud = true
80};
diff --git a/old/2021-11-10-beforeremovingchecker/pf.h b/old/2021-11-10-beforeremovingchecker/pf.h
new file mode 100644
index 0000000..85ee1eb
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/pf.h
@@ -0,0 +1,18 @@
1#ifndef PF_H
2#define PF_H
3
4#include "cubetypes.h"
5
6extern PieceFilter pf_all;
7extern PieceFilter pf_4val;
8extern PieceFilter pf_epcp;
9extern PieceFilter pf_cpos;
10extern PieceFilter pf_cp;
11extern PieceFilter pf_ep;
12extern PieceFilter pf_e;
13extern PieceFilter pf_s;
14extern PieceFilter pf_m;
15extern PieceFilter pf_eo;
16extern PieceFilter pf_co;
17
18#endif
diff --git a/old/2021-11-10-beforeremovingchecker/pruning.c b/old/2021-11-10-beforeremovingchecker/pruning.c
new file mode 100644
index 0000000..86363f4
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/pruning.c
@@ -0,0 +1,272 @@
1#include "pruning.h"
2
3static void genptable_bfs(PruneData *pd, int d, Move *ms);
4static void genptable_branch(PruneData *pd, uint64_t i, int d, Move *m);
5static void ptable_update(PruneData *pd, Cube cube, int m);
6static void ptable_update_index(PruneData *pd, uint64_t ind, int m);
7static int ptableval_index(PruneData *pd, uint64_t ind);
8static bool read_ptable_file(PruneData *pd);
9static bool write_ptable_file(PruneData *pd);
10
11PruneData
12pd_eofb_HTM = {
13 .filename = "pt_eofb_HTM",
14 .coord = &coord_eofb,
15 .moveset = moveset_HTM,
16};
17
18PruneData
19pd_coud_HTM = {
20 .filename = "pt_coud_HTM",
21 .coord = &coord_coud,
22 .moveset = moveset_HTM,
23};
24
25PruneData
26pd_cornershtr_HTM = {
27 .filename = "pt_cornershtr_withcosets_HTM",
28 .coord = &coord_cornershtr,
29 .moveset = moveset_HTM,
30};
31
32PruneData
33pd_corners_HTM = {
34 .filename = "pt_corners_HTM",
35 .coord = &coord_corners,
36 .moveset = moveset_HTM,
37};
38
39PruneData
40pd_drud_sym16_HTM = {
41 .filename = "pt_drud_sym16_HTM",
42 .coord = &coord_drud_sym16,
43 .moveset = moveset_HTM,
44};
45
46PruneData
47pd_drud_eofb = {
48 .filename = "pt_drud_eofb",
49 .coord = &coord_drud_eofb,
50 .moveset = moveset_eofb,
51};
52
53PruneData
54pd_drudfin_noE_sym16_drud = {
55 .filename = "pt_drudfin_noE_sym16_drud",
56 .coord = &coord_drudfin_noE_sym16,
57 .moveset = moveset_drud,
58};
59
60PruneData
61pd_htr_drud = {
62 .filename = "pt_htr_drud",
63 .coord = &coord_htr_drud,
64 .moveset = moveset_drud,
65};
66
67PruneData
68pd_htrfin_htr = {
69 .filename = "pt_htrfin_htr",
70 .coord = &coord_htrfin,
71 .moveset = moveset_htr,
72};
73
74PruneData
75pd_khuge_HTM = {
76 .filename = "pt_khuge_HTM",
77 .coord = &coord_khuge,
78 .moveset = moveset_HTM,
79};
80
81void
82genptable(PruneData *pd)
83{
84 Move ms[NMOVES];
85 int d;
86 uint64_t j, oldn;
87
88 if (pd->generated)
89 return;
90
91 /* TODO: check if memory is enough, otherwise maybe exit gracefully? */
92 pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
93
94 if (read_ptable_file(pd)) {
95 pd->generated = true;
96 return;
97 }
98 pd->generated = true;
99
100 fprintf(stderr, "Cannot load %s, generating it\n", pd->filename);
101
102 moveset_to_list(pd->moveset, ms);
103
104 /* We use 4 bits per value, so any distance >= 15 is set to 15 */
105 for (j = 0; j < pd->coord->max; j++)
106 ptable_update_index(pd, j, 15);
107
108 for (j = 0; j < pd->coord->max; j++)
109 if (ptableval_index(pd, j) != 15) {
110 printf("Error, non-max value at index %lu!\n", j);
111 break;
112 }
113 printf("Table set, ready to start\n");
114
115 /*TODO: change, set to 0 for every solved state (might be more than 1)*/
116 ptable_update(pd, (Cube){0}, 0);
117 pd->n = 1;
118 oldn = 0;
119 fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n",
120 0, pd->n - oldn, pd->n, pd->coord->max);
121 oldn = 1;
122 for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
123 genptable_bfs(pd, d, ms);
124 fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n",
125 d+1, pd->n - oldn, pd->n, pd->coord->max);
126 oldn = pd->n;
127 }
128
129 if (!write_ptable_file(pd))
130 fprintf(stderr, "Error writing ptable file\n");
131}
132
133static void
134genptable_bfs(PruneData *pd, int d, Move *ms)
135{
136 uint64_t i;
137
138 for (i = 0; i < pd->coord->max; i++)
139 if (ptableval_index(pd, i) == d)
140 genptable_branch(pd, i, d, ms);
141}
142
143static void
144genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
145{
146 int i, j;
147 Cube ci, cc, c;
148
149 /*
150 * This is the only line of the whole program where we REALLY need an
151 * anti-indexer function. We could get rid of it if only we could save
152 * a cube object for each index value as we go, but then we would need
153 * an incredible amount of memory to generate each ptable: assuming
154 * fields in struct cube are 32 bit ints that would take 88 times the
155 * memory of the table to be generated, more than 120Gb for
156 * ptable_khuge for example!
157 */
158 ci = pd->coord->cube(ind);
159
160 for (i = 0; i < pd->coord->ntrans; i++) {
161 /* For simplicity trans[] is NULL when ntrans = 1 */
162 c = i == 0 ? ci :
163 apply_trans(pd->coord->trans[i], ci);
164 for (j = 0; ms[j] != NULLMOVE; j++) {
165 cc = apply_move(ms[j], c);
166 if (ptableval(pd, cc) > d+1)
167 ptable_update(pd, cc, d+1);
168 }
169 }
170}
171
172void
173print_ptable(PruneData *pd)
174{
175 uint64_t i, a[16];
176
177 for (i = 0; i < 16; i++)
178 a[i] = 0;
179
180 if (!pd->generated)
181 genptable(pd);
182
183 for (i = 0; i < pd->coord->max; i++)
184 a[ptableval_index(pd, i)]++;
185
186 fprintf(stderr, "Values for table %s\n", pd->filename);
187 for (i = 0; i < 16; i++)
188 printf("%2lu\t%10lu\n", i, a[i]);
189}
190
191uint64_t
192ptablesize(PruneData *pd)
193{
194 return (pd->coord->max + 1) / 2;
195}
196
197static void
198ptable_update(PruneData *pd, Cube cube, int n)
199{
200 uint64_t ind = pd->coord->index(cube);
201 ptable_update_index(pd, ind, n);
202}
203
204static void
205ptable_update_index(PruneData *pd, uint64_t ind, int n)
206{
207 uint8_t oldval2 = pd->ptable[ind/2];
208 int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
209
210 pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n;
211 pd->n++;
212}
213
214int
215ptableval(PruneData *pd, Cube cube)
216{
217 return ptableval_index(pd, pd->coord->index(cube));
218}
219
220static int
221ptableval_index(PruneData *pd, uint64_t ind)
222{
223 if (!pd->generated)
224 genptable(pd);
225
226 return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16;
227}
228
229static bool
230read_ptable_file(PruneData *pd)
231{
232 init_env();
233
234 FILE *f;
235 char fname[strlen(tabledir)+100];
236 uint64_t r;
237
238 strcpy(fname, tabledir);
239 strcat(fname, "/");
240 strcat(fname, pd->filename);
241
242 if ((f = fopen(fname, "rb")) == NULL)
243 return false;
244
245 r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
246 fclose(f);
247
248 return r == ptablesize(pd);
249}
250
251static bool
252write_ptable_file(PruneData *pd)
253{
254 init_env();
255
256 FILE *f;
257 char fname[strlen(tabledir)+100];
258 uint64_t written;
259
260 strcpy(fname, tabledir);
261 strcat(fname, "/");
262 strcat(fname, pd->filename);
263
264 if ((f = fopen(fname, "wb")) == NULL)
265 return false;
266
267 written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
268 fclose(f);
269
270 return written == ptablesize(pd);
271}
272
diff --git a/old/2021-11-10-beforeremovingchecker/pruning.h b/old/2021-11-10-beforeremovingchecker/pruning.h
new file mode 100644
index 0000000..631ee3a
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/pruning.h
@@ -0,0 +1,23 @@
1#ifndef PRUNING_H
2#define PRUNING_H
3
4#include "symcoord.h"
5
6extern PruneData pd_eofb_HTM;
7extern PruneData pd_coud_HTM;
8extern PruneData pd_corners_HTM;
9extern PruneData pd_cornershtr_HTM;
10extern PruneData pd_drud_sym16_HTM;
11extern PruneData pd_drud_eofb;
12extern PruneData pd_drudfin_noE_sym16_drud;
13extern PruneData pd_htr_drud;
14extern PruneData pd_htrfin_htr;
15extern PruneData pd_khuge_HTM;
16
17void genptable(PruneData *pd);
18void print_ptable(PruneData *pd);
19uint64_t ptablesize(PruneData *pd);
20int ptableval(PruneData *pd, Cube cube);
21
22#endif
23
diff --git a/old/2021-11-10-beforeremovingchecker/shell.c b/old/2021-11-10-beforeremovingchecker/shell.c
new file mode 100644
index 0000000..e591faa
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/shell.c
@@ -0,0 +1,99 @@
1#include "shell.h"
2
3static void cleanwhitespaces(char *line);
4static int parseline(char *line, char **v);
5
6static void
7cleanwhitespaces(char *line)
8{
9 char *i;
10
11 for (i = line; *i != 0; i++)
12 if (*i == '\t' || *i == '\n')
13 *i = ' ';
14}
15
16/* This function assumes that **v is large enough */
17static int
18parseline(char *line, char **v)
19{
20 char *t;
21 int n = 0;
22
23 cleanwhitespaces(line);
24
25 for (t = strtok(line, " "); t != NULL; t = strtok(NULL, " "))
26 strcpy(v[n++], t);
27
28 return n;
29}
30
31void
32exec_args(int c, char **v)
33{
34 int i;
35 Command *cmd = NULL;
36 CommandArgs *args;
37
38 for (i = 0; i < NCOMMANDS; i++)
39 if (commands[i] != NULL && !strcmp(v[0], commands[i]->name))
40 cmd = commands[i];
41
42 if (cmd == NULL) {
43 fprintf(stderr, "%s: command not found\n", v[0]);
44 return;
45 }
46
47 args = cmd->parse_args(c-1, &v[1]);
48 if (!args->success) {
49 fprintf(stderr, "usage: %s\n", cmd->usage);
50 return;
51 }
52
53 cmd->exec(args);
54 free_args(args);
55}
56
57void
58launch()
59{
60 int i, shell_argc;
61 char line[MAXLINELEN], **shell_argv;
62
63 shell_argv = malloc(MAXNTOKENS * sizeof(char *));
64 for (i = 0; i < MAXNTOKENS; i++)
65 shell_argv[i] = malloc((MAXTOKENLEN+1) * sizeof(char));
66
67 fprintf(stderr, "Welcome to Nissy 2.0 (demo version).\n");
68 fprintf(stderr, "Limited commands available. ");
69 fprintf(stderr, "Type 'help' for a list.\n");
70
71 while (true) {
72 fprintf(stderr, "nissy-# ");
73 if (fgets(line, MAXLINELEN, stdin) == NULL)
74 break;
75 shell_argc = parseline(line, shell_argv);
76 exec_args(shell_argc, shell_argv);
77 }
78
79 for (i = 0; i < MAXNTOKENS; i++)
80 free(shell_argv[i]);
81 free(shell_argv);
82}
83
84/* We will have our main() here, for now */
85int
86main(int argc, char *argv[])
87{
88 init_moves();
89 init_trans();
90 init_coord();
91 init_symcoord();
92
93 if (argc > 1)
94 exec_args(argc-1, &argv[1]);
95 else
96 launch();
97
98 return 0;
99}
diff --git a/old/2021-11-10-beforeremovingchecker/shell.h b/old/2021-11-10-beforeremovingchecker/shell.h
new file mode 100644
index 0000000..a72d136
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/shell.h
@@ -0,0 +1,13 @@
1#ifndef SHELL_H
2#define SHELL_H
3
4#include "commands.h"
5
6#define MAXLINELEN 10000
7#define MAXTOKENLEN 255
8#define MAXNTOKENS 255
9
10void exec_args(int c, char **v);
11void launch();
12
13#endif
diff --git a/old/2021-11-10-beforeremovingchecker/solve.c b/old/2021-11-10-beforeremovingchecker/solve.c
new file mode 100644
index 0000000..af685ec
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/solve.c
@@ -0,0 +1,209 @@
1#include "solve.h"
2
3/* Local functions ***********************************************************/
4
5static bool allowed_next(Move move, DfsData *dd);
6static void dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
7static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd);
8static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd);
9static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
10static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
11
12/* Local functions ***********************************************************/
13
14static bool
15allowed_next(Move move, DfsData *dd)
16{
17
18/* TODO: remove the commented part, was added to moves.c
19 static bool initialized = false;
20 static bool commute[NMOVES][NMOVES], pnext[NMOVES][NMOVES][NMOVES];
21
22 if (!initialized) {
23 Cube c1, c2;
24 int i, j, k;
25 bool p1, p2, cij;
26
27 for (i = 0; i < NMOVES; i++) {
28 for (j = 0; j < NMOVES; j++) {
29 c1 = apply_move(i, apply_move(j, (Cube){0}));
30 c2 = apply_move(j, apply_move(i, (Cube){0}));
31 commute[i][j] = equal(c1, c2) && i && j;
32 for (k = 0; k < NMOVES; k++) {
33 p1 = j && base_move(j) == base_move(k);
34 p2 = i && base_move(i) == base_move(k);
35 cij = commute[i][j];
36 pnext[i][j][k] = !(p1 || (cij && p2));
37 }
38 }
39 }
40
41 initialized = true;
42 }
43
44 if (!pnext[dd->last2][dd->last1][move])
45 return false;
46
47 if (commute[dd->last1][move])
48 return dd->move_position[dd->last1] < dd->move_position[move];
49
50 return true;
51*/
52
53 if (!possible_next(dd->last2, dd->last1, move))
54 return false;
55
56 if (commute(dd->last1, move))
57 return dd->move_position[dd->last1] < dd->move_position[move];
58
59 return true;
60}
61
62static void
63dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
64{
65 if (dfs_stop(c, s, opts, dd))
66 return;
67
68 if (dfs_check_solved(s, opts, dd))
69 return;
70
71 dfs_branch(c, s, opts, dd);
72
73 if (opts->can_niss && !dd->niss)
74 dfs_niss(c, s, opts, dd);
75}
76
77static void
78dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
79{
80 Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
81
82 int i, maxnsol = opts->max_solutions;
83
84 for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) {
85 m = moves[i];
86 if (allowed_next(m, dd)) {
87 dd->last2 = dd->last1;
88 dd->last1 = m;
89 append_move(dd->current_alg, m, dd->niss);
90
91 dfs(apply_move(m, c), s, opts, dd);
92
93 dd->current_alg->len--;
94 dd->last2 = l2;
95 dd->last1 = l1;
96 }
97 }
98}
99
100static bool
101dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
102{
103 if (dd->lb != 0)
104 return false;
105
106 if (dd->current_alg->len == dd->d) {
107 if (s->is_valid(dd->current_alg) || opts->all)
108 append_alg(dd->sols, dd->current_alg);
109
110 if (opts->feedback)
111 print_alg(dd->current_alg, false);
112 }
113
114 return true;
115}
116
117static void
118dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
119{
120 Move l1 = dd->last1, l2 = dd->last2;
121 CubeTarget ct;
122
123 ct.cube = apply_move(inverse_move(l1), (Cube){0});
124 ct.target = 1;
125
126 if (dd->current_alg->len == 0 || s->estimate(ct)) {
127 dd->niss = true;
128 dd->last1 = NULLMOVE;
129 dd->last2 = NULLMOVE;
130
131 dfs(inverse_cube(c), s, opts, dd);
132
133 dd->last1 = l1;
134 dd->last2 = l2;
135 dd->niss = false;
136 }
137}
138
139static bool
140dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
141{
142 CubeTarget ct = {
143 .cube = c,
144 .target = dd->d - dd->current_alg->len
145 };
146
147 if (dd->sols->len >= opts->max_solutions)
148 return true;
149
150 dd->lb = s->estimate(ct);
151 if (opts->can_niss && !dd->niss)
152 dd->lb = MIN(1, dd->lb);
153
154 if (dd->current_alg->len + dd->lb > dd->d)
155 return true;
156
157 return false;
158}
159
160/* Public functions **********************************************************/
161
162AlgList *
163solve(Cube cube, Step *step, SolveOptions *opts)
164{
165 AlgListNode *node;
166 AlgList *sols = new_alglist();
167 Cube c;
168
169 if (step->detect != NULL)
170 step->pre_trans = step->detect(cube);
171 c = apply_trans(step->pre_trans, cube);
172
173 DfsData dd = {
174 .m = 0,
175 .niss = false,
176 .lb = -1,
177 .last1 = NULLMOVE,
178 .last2 = NULLMOVE,
179 .sols = sols,
180 .current_alg = new_alg("")
181 };
182
183 if (step->ready != NULL && !step->ready(c)) {
184 fprintf(stderr, "Cube not ready for solving step: ");
185 fprintf(stderr, "%s\n", step->ready_msg);
186 return sols;
187 }
188
189 moveset_to_list(step->moveset, dd.sorted_moves);
190 movelist_to_position(dd.sorted_moves, dd.move_position);
191
192 for (dd.d = opts->min_moves;
193 dd.d <= opts->max_moves &&
194 !(sols->len && opts->optimal_only) &&
195 sols->len < opts->max_solutions;
196 dd.d++) {
197 if (opts->feedback)
198 fprintf(stderr,
199 "Found %d solutions, searching depth %d...\n",
200 sols->len, dd.d);
201 dfs(c, step, opts, &dd);
202 }
203
204 for (node = sols->first; node != NULL; node = node->next)
205 transform_alg(inverse_trans(step->pre_trans), node->alg);
206
207 free_alg(dd.current_alg);
208 return sols;
209}
diff --git a/old/2021-11-10-beforeremovingchecker/solve.h b/old/2021-11-10-beforeremovingchecker/solve.h
new file mode 100644
index 0000000..ff84e7e
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/solve.h
@@ -0,0 +1,9 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include "moves.h"
5#include "trans.h"
6
7AlgList * solve(Cube cube, Step *step, SolveOptions *opts);
8
9#endif
diff --git a/old/2021-11-10-beforeremovingchecker/steps.c b/old/2021-11-10-beforeremovingchecker/steps.c
new file mode 100644
index 0000000..7213766
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/steps.c
@@ -0,0 +1,916 @@
1#include "steps.h"
2
3/* Standard checkers (return lower bound) ************************************/
4
5static int estimate_eoany_HTM(CubeTarget ct);
6static int estimate_eofb_HTM(CubeTarget ct);
7static int estimate_coany_HTM(CubeTarget ct);
8static int estimate_coud_HTM(CubeTarget ct);
9static int estimate_coany_URF(CubeTarget ct);
10static int estimate_coud_URF(CubeTarget ct);
11static int estimate_corners_HTM(CubeTarget ct);
12static int estimate_cornershtr_HTM(CubeTarget ct);
13static int estimate_corners_URF(CubeTarget ct);
14static int estimate_cornershtr_URF(CubeTarget ct);
15static int estimate_drany_HTM(CubeTarget ct);
16static int estimate_drud_HTM(CubeTarget ct);
17static int estimate_drud_eofb(CubeTarget ct);
18static int estimate_dr_eofb(CubeTarget ct);
19static int estimate_drudfin_drud(CubeTarget ct);
20static int estimate_htr_drud(CubeTarget ct);
21static int estimate_htrfin_htr(CubeTarget ct);
22static int estimate_optimal_HTM(CubeTarget ct);
23
24/* Validators ****************************************************************/
25
26static bool always_valid(Alg *alg);
27static bool validate_singlecw_ending(Alg *alg);
28
29/* Pre-transformation detectors **********************************************/
30
31static Trans detect_pretrans_eofb(Cube cube);
32static Trans detect_pretrans_drud(Cube cube);
33
34/* Messages for when cube is not ready ***************************************/
35
36static char check_centers_msg[100] = "cube must be oriented (centers solved)";
37static char check_eo_msg[100] = "EO must be solved on given axis";
38static char check_dr_msg[100] = "DR must be solved on given axis";
39static char check_htr_msg[100] = "HTR must be solved";
40static char check_drany_msg[100] = "DR must be solved on at least one axis";
41
42/* Steps *********************************************************************/
43
44Step
45optimal_HTM = {
46 .shortname = "optimal",
47 .name = "Optimal solve (in HTM)",
48
49 .estimate = estimate_optimal_HTM,
50 .ready = check_centers,
51 .ready_msg = check_centers_msg,
52 .is_valid = always_valid,
53 .moveset = moveset_HTM,
54
55 .pre_trans = uf,
56};
57
58/* EO steps **************************/
59Step
60eoany_HTM = {
61 .shortname = "eo",
62 .name = "EO on any axis",
63
64 .estimate = estimate_eoany_HTM,
65 .ready = check_centers,
66 .ready_msg = check_centers_msg,
67 .is_valid = validate_singlecw_ending,
68 .moveset = moveset_HTM,
69
70 .pre_trans = uf,
71};
72
73Step
74eofb_HTM = {
75 .shortname = "eofb",
76 .name = "EO on F/B",
77
78 .estimate = estimate_eofb_HTM,
79 .ready = check_centers,
80 .ready_msg = check_centers_msg,
81 .is_valid = validate_singlecw_ending,
82 .moveset = moveset_HTM,
83
84 .pre_trans = uf,
85};
86
87Step
88eorl_HTM = {
89 .shortname = "eorl",
90 .name = "EO on R/L",
91
92 .estimate = estimate_eofb_HTM,
93 .ready = check_centers,
94 .ready_msg = check_centers_msg,
95 .is_valid = validate_singlecw_ending,
96 .moveset = moveset_HTM,
97
98 .pre_trans = ur,
99};
100
101Step
102eoud_HTM = {
103 .shortname = "eoud",
104 .name = "EO on U/D",
105
106 .estimate = estimate_eofb_HTM,
107 .ready = check_centers,
108 .ready_msg = check_centers_msg,
109 .is_valid = validate_singlecw_ending,
110 .moveset = moveset_HTM,
111
112 .pre_trans = fd,
113};
114
115/* CO steps **************************/
116Step
117coany_HTM = {
118 .shortname = "co",
119 .name = "CO on any axis",
120
121 .estimate = estimate_coany_HTM,
122 .ready = NULL,
123 .is_valid = validate_singlecw_ending,
124 .moveset = moveset_HTM,
125
126 .pre_trans = uf,
127};
128
129Step
130coud_HTM = {
131 .shortname = "coud",
132 .name = "CO on U/D",
133
134 .estimate = estimate_coud_HTM,
135 .ready = NULL,
136 .is_valid = validate_singlecw_ending,
137 .moveset = moveset_HTM,
138
139 .pre_trans = uf,
140};
141
142Step
143corl_HTM = {
144 .shortname = "corl",
145 .name = "CO on R/L",
146
147 .estimate = estimate_coud_HTM,
148 .ready = NULL,
149 .is_valid = validate_singlecw_ending,
150 .moveset = moveset_HTM,
151
152 .pre_trans = rf,
153};
154
155Step
156cofb_HTM = {
157 .shortname = "cofb",
158 .name = "CO on F/B",
159
160 .estimate = estimate_coud_HTM,
161 .ready = NULL,
162 .is_valid = validate_singlecw_ending,
163 .moveset = moveset_HTM,
164
165 .pre_trans = fd,
166};
167
168Step
169coany_URF = {
170 .shortname = "co-URF",
171 .name = "CO any axis (URF moveset)",
172
173 .estimate = estimate_coany_URF,
174 .ready = NULL,
175 .is_valid = validate_singlecw_ending,
176 .moveset = moveset_URF,
177
178 .pre_trans = uf,
179};
180
181Step
182coud_URF = {
183 .shortname = "coud-URF",
184 .name = "CO on U/D (URF moveset)",
185
186 .estimate = estimate_coud_URF,
187 .ready = NULL,
188 .is_valid = validate_singlecw_ending,
189 .moveset = moveset_URF,
190
191 .pre_trans = uf,
192};
193
194Step
195corl_URF = {
196 .shortname = "corl-URF",
197 .name = "CO on R/L (URF moveset)",
198
199 .estimate = estimate_coud_URF,
200 .ready = NULL,
201 .is_valid = validate_singlecw_ending,
202 .moveset = moveset_URF,
203
204 .pre_trans = rf,
205};
206
207Step
208cofb_URF = {
209 .shortname = "cofb-URF",
210 .name = "CO on F/B (URF moveset)",
211
212 .estimate = estimate_coud_URF,
213 .ready = NULL,
214 .is_valid = validate_singlecw_ending,
215 .moveset = moveset_URF,
216
217 .pre_trans = fd,
218};
219
220/* Misc corner steps *****************/
221Step
222cornershtr_HTM = {
223 .shortname = "chtr",
224 .name = "Solve corners to HTR state",
225
226 .estimate = estimate_cornershtr_HTM,
227 .ready = NULL,
228 .is_valid = validate_singlecw_ending,
229 .moveset = moveset_HTM,
230
231 .pre_trans = uf,
232};
233
234Step
235cornershtr_URF = {
236 .shortname = "chtr-URF",
237 .name = "Solve corners to HTR state (URF moveset)",
238
239 .estimate = estimate_cornershtr_URF,
240 .ready = NULL,
241 .is_valid = validate_singlecw_ending,
242 .moveset = moveset_URF,
243
244 .pre_trans = uf,
245};
246
247Step
248corners_HTM = {
249 .shortname = "corners",
250 .name = "Solve corners",
251
252 .estimate = estimate_corners_HTM,
253 .ready = NULL,
254 .is_valid = always_valid,
255 .moveset = moveset_HTM,
256
257 .pre_trans = uf,
258};
259
260Step
261corners_URF = {
262 .shortname = "corners-URF",
263 .name = "Solve corners (URF moveset)",
264
265 .estimate = estimate_corners_URF,
266 .ready = NULL,
267 .is_valid = always_valid,
268 .moveset = moveset_URF,
269
270 .pre_trans = uf,
271};
272
273/* DR steps **************************/
274Step
275drany_HTM = {
276 .shortname = "dr",
277 .name = "DR on any axis",
278
279 .estimate = estimate_drany_HTM,
280 .ready = check_centers,
281 .ready_msg = check_centers_msg,
282 .is_valid = validate_singlecw_ending,
283 .moveset = moveset_HTM,
284
285 .pre_trans = uf,
286};
287
288Step
289drud_HTM = {
290 .shortname = "drud",
291 .name = "DR on U/D",
292
293 .estimate = estimate_drud_HTM,
294 .ready = check_centers,
295 .ready_msg = check_centers_msg,
296 .is_valid = validate_singlecw_ending,
297 .moveset = moveset_HTM,
298
299 .pre_trans = uf,
300};
301
302Step
303drrl_HTM = {
304 .shortname = "drrl",
305 .name = "DR on R/L",
306
307 .estimate = estimate_drud_HTM,
308 .ready = check_centers,
309 .ready_msg = check_centers_msg,
310 .is_valid = validate_singlecw_ending,
311 .moveset = moveset_HTM,
312
313 .pre_trans = rf,
314};
315
316Step
317drfb_HTM = {
318 .shortname = "drfb",
319 .name = "DR on F/B",
320
321 .estimate = estimate_drud_HTM,
322 .ready = check_centers,
323 .ready_msg = check_centers_msg,
324 .is_valid = validate_singlecw_ending,
325 .moveset = moveset_HTM,
326
327 .pre_trans = fd,
328};
329
330/* DR from EO */
331Step
332dr_eo = {
333 .shortname = "dr-eo",
334 .name = "DR without breaking EO (automatically detected)",
335
336 .estimate = estimate_dr_eofb,
337 .ready = check_eofb,
338 .ready_msg = check_eo_msg,
339 .is_valid = validate_singlecw_ending,
340 .moveset = moveset_eofb,
341
342 .detect = detect_pretrans_eofb,
343};
344
345Step
346dr_eofb = {
347 .shortname = "dr-eofb",
348 .name = "DR on U/D or R/L without breaking EO on F/B",
349
350 .estimate = estimate_dr_eofb,
351 .ready = check_eofb,
352 .ready_msg = check_eo_msg,
353 .is_valid = validate_singlecw_ending,
354 .moveset = moveset_eofb,
355
356 .pre_trans = uf,
357};
358
359Step
360dr_eorl = {
361 .shortname = "dr-eorl",
362 .name = "DR on U/D or F/B without breaking EO on R/L",
363
364 .estimate = estimate_dr_eofb,
365 .ready = check_eofb,
366 .ready_msg = check_eo_msg,
367 .is_valid = validate_singlecw_ending,
368 .moveset = moveset_eofb,
369
370 .pre_trans = ur,
371};
372
373Step
374dr_eoud = {
375 .shortname = "dr-eoud",
376 .name = "DR on R/L or F/B without breaking EO on U/R",
377
378 .estimate = estimate_dr_eofb,
379 .ready = check_eofb,
380 .ready_msg = check_eo_msg,
381 .is_valid = validate_singlecw_ending,
382 .moveset = moveset_eofb,
383
384 .pre_trans = fd,
385};
386
387Step
388drud_eofb = {
389 .shortname = "drud-eofb",
390 .name = "DR on U/D without breaking EO on F/B",
391
392 .estimate = estimate_drud_eofb,
393 .ready = check_eofb,
394 .ready_msg = check_eo_msg,
395 .is_valid = validate_singlecw_ending,
396 .moveset = moveset_eofb,
397
398 .pre_trans = uf,
399};
400
401Step
402drrl_eofb = {
403 .shortname = "drrl-eofb",
404 .name = "DR on R/L without breaking EO on F/B",
405
406 .estimate = estimate_drud_eofb,
407 .ready = check_eofb,
408 .ready_msg = check_eo_msg,
409 .is_valid = validate_singlecw_ending,
410 .moveset = moveset_eofb,
411
412 .pre_trans = rf,
413};
414
415Step
416drud_eorl = {
417 .shortname = "drud-eorl",
418 .name = "DR on U/D without breaking EO on R/L",
419
420 .estimate = estimate_drud_eofb,
421 .ready = check_eofb,
422 .ready_msg = check_eo_msg,
423 .is_valid = validate_singlecw_ending,
424 .moveset = moveset_eofb,
425
426 .pre_trans = ur,
427};
428
429Step
430drfb_eorl = {
431 .shortname = "drfb-eorl",
432 .name = "DR on F/B without breaking EO on R/L",
433
434 .estimate = estimate_drud_eofb,
435 .ready = check_eofb,
436 .ready_msg = check_eo_msg,
437 .is_valid = validate_singlecw_ending,
438 .moveset = moveset_eofb,
439
440 .pre_trans = fr,
441};
442
443Step
444drfb_eoud = {
445 .shortname = "drfb-eoud",
446 .name = "DR on F/B without breaking EO on U/D",
447
448 .estimate = estimate_drud_eofb,
449 .ready = check_eofb,
450 .ready_msg = check_eo_msg,
451 .is_valid = validate_singlecw_ending,
452 .moveset = moveset_eofb,
453
454 .pre_trans = fd,
455};
456
457Step
458drrl_eoud = {
459 .shortname = "drrl-eoud",
460 .name = "DR on R/L without breaking EO on U/D",
461
462 .estimate = estimate_drud_eofb,
463 .ready = check_eofb,
464 .ready_msg = check_eo_msg,
465 .is_valid = validate_singlecw_ending,
466 .moveset = moveset_eofb,
467
468 .pre_trans = rd,
469};
470
471/* DR finish steps */
472Step
473dranyfin_DR = {
474 .shortname = "drfin",
475 .name = "DR finish on any axis without breaking DR",
476
477 .estimate = estimate_drudfin_drud,
478 .ready = check_drud,
479 .ready_msg = check_drany_msg,
480 .is_valid = always_valid,
481 .moveset = moveset_drud,
482
483 .detect = detect_pretrans_drud,
484};
485
486Step
487drudfin_drud = {
488 .shortname = "drudfin",
489 .name = "DR finish on U/D without breaking DR",
490
491 .estimate = estimate_drudfin_drud,
492 .ready = check_drud,
493 .ready_msg = check_dr_msg,
494 .is_valid = always_valid,
495 .moveset = moveset_drud,
496
497 .pre_trans = uf,
498};
499
500Step
501drrlfin_drrl = {
502 .shortname = "drrlfin",
503 .name = "DR finish on R/L without breaking DR",
504
505 .estimate = estimate_drudfin_drud,
506 .ready = check_drud,
507 .ready_msg = check_dr_msg,
508 .is_valid = always_valid,
509 .moveset = moveset_drud,
510
511 .pre_trans = rf,
512};
513
514Step
515drfbfin_drfb = {
516 .shortname = "drfbfin",
517 .name = "DR finish on F/B without breaking DR",
518
519 .estimate = estimate_drudfin_drud,
520 .ready = check_drud,
521 .ready_msg = check_dr_msg,
522 .is_valid = always_valid,
523 .moveset = moveset_drud,
524
525 .pre_trans = fd,
526};
527
528/* HTR from DR */
529Step
530htr_any = {
531 .shortname = "htr",
532 .name = "HTR from DR",
533
534 .estimate = estimate_htr_drud,
535 .ready = check_drud,
536 .ready_msg = check_drany_msg,
537 .is_valid = validate_singlecw_ending,
538 .moveset = moveset_drud,
539
540 .detect = detect_pretrans_drud,
541};
542
543Step
544htr_drud = {
545 .shortname = "htr-drud",
546 .name = "HTR from DR on U/D",
547
548 .estimate = estimate_htr_drud,
549 .ready = check_drud,
550 .ready_msg = check_dr_msg,
551 .is_valid = validate_singlecw_ending,
552 .moveset = moveset_drud,
553
554 .pre_trans = uf,
555};
556
557Step
558htr_drrl = {
559 .shortname = "htr-drrl",
560 .name = "HTR from DR on R/L",
561
562 .estimate = estimate_htr_drud,
563 .ready = check_drud,
564 .ready_msg = check_dr_msg,
565 .is_valid = validate_singlecw_ending,
566 .moveset = moveset_drud,
567
568 .pre_trans = rf,
569};
570
571Step
572htr_drfb = {
573 .shortname = "htr-drfb",
574 .name = "HTR from DR on F/B",
575
576 .estimate = estimate_htr_drud,
577 .ready = check_drud,
578 .ready_msg = check_dr_msg,
579 .is_valid = validate_singlecw_ending,
580 .moveset = moveset_drud,
581
582 .pre_trans = fd,
583};
584
585/* HTR finish */
586Step
587htrfin_htr = {
588 .shortname = "htrfin",
589 .name = "HTR finish without breaking HTR",
590
591 .estimate = estimate_htrfin_htr,
592 .ready = check_htr,
593 .ready_msg = check_htr_msg,
594 .is_valid = always_valid,
595 .moveset = moveset_htr,
596
597 .pre_trans = uf,
598};
599
600Step *steps[NSTEPS] = {
601 &optimal_HTM, /* first is default */
602
603 &eoany_HTM,
604 &eofb_HTM,
605 &eorl_HTM,
606 &eoud_HTM,
607
608 &coany_HTM,
609 &coud_HTM,
610 &corl_HTM,
611 &cofb_HTM,
612
613 &coany_URF,
614 &coud_URF,
615 &corl_URF,
616 &cofb_URF,
617
618 &drany_HTM,
619 &drud_HTM,
620 &drrl_HTM,
621 &drfb_HTM,
622
623 &dr_eo,
624 &dr_eofb,
625 &dr_eorl,
626 &dr_eoud,
627 &drud_eofb,
628 &drrl_eofb,
629 &drud_eorl,
630 &drfb_eorl,
631 &drfb_eoud,
632 &drrl_eoud,
633
634 &dranyfin_DR,
635 &drudfin_drud,
636 &drrlfin_drrl,
637 &drfbfin_drfb,
638
639 &htr_any,
640 &htr_drud,
641 &htr_drrl,
642 &htr_drfb,
643
644 &htrfin_htr,
645
646 &cornershtr_HTM,
647 &cornershtr_URF,
648 &corners_HTM,
649 &corners_URF,
650};
651
652/* Standard checkers (return lower bound) ************************************/
653
654static int
655estimate_eoany_HTM(CubeTarget ct)
656{
657 int r1, r2, r3;
658
659 r1 = ptableval(&pd_eofb_HTM, ct.cube);
660 r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, ct.cube));
661 r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, ct.cube));
662
663 return MIN(r1, MIN(r2, r3));
664}
665
666static int
667estimate_eofb_HTM(CubeTarget ct)
668{
669 return ptableval(&pd_eofb_HTM, ct.cube);
670}
671
672static int
673estimate_coany_HTM(CubeTarget ct)
674{
675 int r1, r2, r3;
676
677 r1 = ptableval(&pd_coud_HTM, ct.cube);
678 r2 = ptableval(&pd_coud_HTM, apply_trans(rf, ct.cube));
679 r3 = ptableval(&pd_coud_HTM, apply_trans(fd, ct.cube));
680
681 return MIN(r1, MIN(r2, r3));
682}
683
684static int
685estimate_coud_HTM(CubeTarget ct)
686{
687 return ptableval(&pd_coud_HTM, ct.cube);
688}
689
690static int
691estimate_coany_URF(CubeTarget ct)
692{
693 int r1, r2, r3;
694 CubeTarget ct2, ct3;
695
696 ct2.cube = apply_trans(rf, ct.cube);
697 ct2.target = ct.target;
698
699 ct3.cube = apply_trans(fd, ct.cube);
700 ct3.target = ct.target;
701
702 r1 = estimate_coud_URF(ct);
703 r2 = estimate_coud_URF(ct2);
704 r3 = estimate_coud_URF(ct3);
705
706 return MIN(r1, MIN(r2, r3));
707}
708
709static int
710estimate_coud_URF(CubeTarget ct)
711{
712 /* TODO: I can improve this by checking first the orientation of
713 * the corner in DBL and use that as a reference */
714
715 CubeTarget ct2 = {.cube = apply_move(z, ct.cube), .target = ct.target};
716 CubeTarget ct3 = {.cube = apply_move(x, ct.cube), .target = ct.target};
717
718 int ud = estimate_coud_HTM(ct);
719 int rl = estimate_coud_HTM(ct2);
720 int fb = estimate_coud_HTM(ct3);
721
722 return MIN(ud, MIN(rl, fb));
723}
724
725static int
726estimate_corners_HTM(CubeTarget ct)
727{
728 return ptableval(&pd_corners_HTM, ct.cube);
729}
730
731static int
732estimate_cornershtr_HTM(CubeTarget ct)
733{
734 return ptableval(&pd_cornershtr_HTM, ct.cube);
735}
736
737static int
738estimate_cornershtr_URF(CubeTarget ct)
739{
740 /* TODO: I can improve this by checking first the corner in DBL
741 * and use that as a reference */
742
743 int c, ret = 15;
744 Trans i;
745
746 for (i = 0; i < NROTATIONS; i++) {
747 ct.cube = apply_alg(rotation_alg(i), ct.cube);
748 c = estimate_cornershtr_HTM(ct);
749 ret = MIN(ret, c);
750 }
751
752 return ret;
753}
754
755static int
756estimate_corners_URF(CubeTarget ct)
757{
758 /* TODO: I can improve this by checking first the corner in DBL
759 * and use that as a reference */
760
761 int c, ret = 15;
762 Trans i;
763
764 for (i = 0; i < NROTATIONS; i++) {
765 ct.cube = apply_alg(rotation_alg(i), ct.cube);
766 c = estimate_corners_HTM(ct);
767 ret = MIN(ret, c);
768 }
769
770 return ret;
771}
772
773static int
774estimate_drany_HTM(CubeTarget ct)
775{
776 int r1, r2, r3;
777
778 r1 = ptableval(&pd_drud_sym16_HTM, ct.cube);
779 r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, ct.cube));
780 r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, ct.cube));
781
782 return MIN(r1, MIN(r2, r3));
783}
784
785static int
786estimate_drud_HTM(CubeTarget ct)
787{
788 return ptableval(&pd_drud_sym16_HTM, ct.cube);
789}
790
791static int
792estimate_drud_eofb(CubeTarget ct)
793{
794 return ptableval(&pd_drud_eofb, ct.cube);
795}
796
797static int
798estimate_dr_eofb(CubeTarget ct)
799{
800 int r1, r2;
801
802 r1 = ptableval(&pd_drud_eofb, ct.cube);
803 r2 = ptableval(&pd_drud_eofb, apply_trans(rf, ct.cube));
804
805 return MIN(r1, r2);
806}
807
808static int
809estimate_drudfin_drud(CubeTarget ct)
810{
811 int val = ptableval(&pd_drudfin_noE_sym16_drud, ct.cube);
812
813 if (val != 0)
814 return val;
815
816 return ct.cube.epose % 24 == 0 ? 0 : 1;
817}
818
819static int
820estimate_htr_drud(CubeTarget ct)
821{
822 return ptableval(&pd_htr_drud, ct.cube);
823}
824
825static int
826estimate_htrfin_htr(CubeTarget ct)
827{
828 return ptableval(&pd_htrfin_htr, ct.cube);
829}
830
831static int
832estimate_optimal_HTM(CubeTarget ct)
833{
834 int dr1, dr2, dr3, cor, ret;
835 Cube cube = ct.cube;
836
837 dr1 = ptableval(&pd_khuge_HTM, cube);
838 cor = estimate_corners_HTM(ct);
839 ret = MAX(dr1, cor);
840
841 if (ret > ct.target)
842 return ret;
843
844 cube = apply_trans(rf, ct.cube);
845 dr2 = ptableval(&pd_khuge_HTM, cube);
846 ret = MAX(ret, dr2);
847
848 if (ret > ct.target)
849 return ret;
850
851 cube = apply_trans(fd, ct.cube);
852 dr3 = ptableval(&pd_khuge_HTM, cube);
853
854 /* Michiel de Bondt's trick */
855 if (dr1 == dr2 && dr2 == dr3 && dr1 != 0)
856 dr3++;
857
858 return MAX(ret, dr3);
859}
860
861/* Validators ****************************************************************/
862
863static bool
864always_valid(Alg *alg)
865{
866 return true;
867}
868
869static bool
870validate_singlecw_ending(Alg *alg)
871{
872 int i;
873 bool nor, inv;
874 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
875
876 for (i = 0; i < alg->len; i++) {
877 if (alg->inv[i]) {
878 l2i = l1i;
879 l1i = alg->move[i];
880 } else {
881 l2 = l1;
882 l1 = alg->move[i];
883 }
884 }
885
886 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2));
887 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i));
888
889 return nor && inv;
890}
891
892/* Pre-transformation detectors **********************************************/
893
894static Trans
895detect_pretrans_eofb(Cube cube)
896{
897 Trans i;
898
899 for (i = 0; i < NROTATIONS; i++)
900 if (check_eofb(apply_trans(i, cube)))
901 return i;
902
903 return 0;
904}
905
906static Trans
907detect_pretrans_drud(Cube cube)
908{
909 Trans i;
910
911 for (i = 0; i < NROTATIONS; i++)
912 if (check_drud(apply_trans(i, cube)))
913 return i;
914
915 return 0;
916}
diff --git a/old/2021-11-10-beforeremovingchecker/steps.h b/old/2021-11-10-beforeremovingchecker/steps.h
new file mode 100644
index 0000000..aa3178c
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/steps.h
@@ -0,0 +1,10 @@
1#ifndef STEPS_H
2#define STEPS_H
3
4#include "pruning.h"
5
6#define NSTEPS 50
7
8extern Step * steps[NSTEPS];
9
10#endif
diff --git a/old/2021-11-10-beforeremovingchecker/symcoord.c b/old/2021-11-10-beforeremovingchecker/symcoord.c
new file mode 100644
index 0000000..9a4d49a
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/symcoord.c
@@ -0,0 +1,359 @@
1#include "symcoord.h"
2
3static Cube antindex_coud_sym16(uint64_t ind);
4static Cube antindex_cp_sym16(uint64_t ind);
5static Cube antindex_eofbepos_sym16(uint64_t ind);
6static Cube antindex_drud_sym16(uint64_t ind);
7static Cube antindex_drudfin_noE_sym16(uint64_t ind);
8static Cube antindex_khuge(uint64_t ind);
9
10static uint64_t index_coud_sym16(Cube cube);
11static uint64_t index_cp_sym16(Cube cube);
12static uint64_t index_eofbepos_sym16(Cube cube);
13static uint64_t index_drud_sym16(Cube cube);
14static uint64_t index_drudfin_noE_sym16(Cube cube);
15static uint64_t index_khuge(Cube cube);
16
17static void gensym(SymData *sd);
18static bool read_symdata_file(SymData *sd);
19static bool write_symdata_file(SymData *sd);
20
21/* Transformation groups and symmetry data ***********************************/
22
23static Trans
24trans_group_udfix[16] = {
25 uf, ur, ub, ul,
26 df, dr, db, dl,
27 uf_mirror, ur_mirror, ub_mirror, ul_mirror,
28 df_mirror, dr_mirror, db_mirror, dl_mirror,
29};
30
31static SymData
32sd_coud_16 = {
33 .filename = "sd_coud_16",
34 .coord = &coord_coud,
35 .sym_coord = &coord_coud_sym16,
36 .ntrans = 16,
37 .trans = trans_group_udfix
38};
39
40static SymData
41sd_cp_16 = {
42 .filename = "sd_cp_16",
43 .coord = &coord_cp,
44 .sym_coord = &coord_cp_sym16,
45 .ntrans = 16,
46 .trans = trans_group_udfix
47};
48
49static SymData
50sd_eofbepos_16 = {
51 .filename = "sd_eofbepos_16",
52 .coord = &coord_eofbepos,
53 .sym_coord = &coord_eofbepos_sym16,
54 .ntrans = 16,
55 .trans = trans_group_udfix
56};
57
58static int nsymdata = 3;
59static SymData * all_sd[] = {
60 &sd_coud_16,
61 &sd_cp_16,
62 &sd_eofbepos_16,
63};
64
65
66/* Coordinates and their implementation **************************************/
67
68Coordinate
69coord_eofbepos_sym16 = {
70 .index = index_eofbepos_sym16,
71 .cube = antindex_eofbepos_sym16,
72 .check = check_eofbepos,
73 .ntrans = 16,
74 .trans = trans_group_udfix,
75};
76
77Coordinate
78coord_coud_sym16 = {
79 .index = index_coud_sym16,
80 .cube = antindex_coud_sym16,
81 .check = check_coud,
82 .ntrans = 16,
83 .trans = trans_group_udfix,
84};
85
86Coordinate
87coord_cp_sym16 = {
88 .index = index_cp_sym16,
89 .cube = antindex_cp_sym16,
90 .check = check_cp,
91 .ntrans = 16,
92 .trans = trans_group_udfix,
93};
94
95Coordinate
96coord_drud_sym16 = {
97 .index = index_drud_sym16,
98 .cube = antindex_drud_sym16,
99 .check = check_drud,
100 .max = POW3TO7 * 64430,
101 .ntrans = 16,
102 .trans = trans_group_udfix,
103};
104
105Coordinate
106coord_drudfin_noE_sym16 = {
107 .index = index_drudfin_noE_sym16,
108 .cube = antindex_drudfin_noE_sym16,
109 .check = check_drudfin_noE,
110 .max = FACTORIAL8 * 2768,
111 .ntrans = 16,
112 .trans = trans_group_udfix,
113};
114
115Coordinate
116coord_khuge = {
117 .index = index_khuge,
118 .cube = antindex_khuge,
119 .check = check_khuge,
120 .max = POW3TO7 * FACTORIAL4 * 64430,
121 .ntrans = 16,
122 .trans = trans_group_udfix,
123};
124
125/* Functions *****************************************************************/
126
127static Cube
128antindex_coud_sym16(uint64_t ind)
129{
130 return sd_coud_16.rep[ind];
131}
132
133static Cube
134antindex_cp_sym16(uint64_t ind)
135{
136 return sd_cp_16.rep[ind];
137}
138
139static Cube
140antindex_eofbepos_sym16(uint64_t ind)
141{
142 return sd_eofbepos_16.rep[ind];
143}
144
145static Cube
146antindex_drud_sym16(uint64_t ind)
147{
148 Cube c;
149
150 c = antindex_eofbepos_sym16(ind/POW3TO7);
151 c.coud = ind % POW3TO7;
152 c.cofb = c.coud;
153 c.corl = c.coud;
154
155 return c;
156}
157
158static Cube
159antindex_drudfin_noE_sym16(uint64_t ind)
160{
161 Cube c1, c2;
162
163 c1 = coord_epud.cube(ind % FACTORIAL8);
164 c2 = antindex_cp_sym16(ind/FACTORIAL8);
165 c1.cp = c2.cp;
166
167 return c1;
168}
169
170static Cube
171antindex_khuge(uint64_t ind)
172{
173 Cube c;
174
175 c = antindex_eofbepos_sym16(ind/(FACTORIAL4*POW3TO7));
176 c.epose = ((c.epose / 24) * 24) + ((ind/POW3TO7) % 24);
177 c.coud = ind % POW3TO7;
178
179 return c;
180}
181
182static uint64_t
183index_coud_sym16(Cube cube)
184{
185 return sd_coud_16.class[coord_coud.index(cube)];
186}
187
188static uint64_t
189index_cp_sym16(Cube cube)
190{
191 return sd_cp_16.class[coord_cp.index(cube)];
192}
193
194static uint64_t
195index_drud_sym16(Cube cube)
196{
197 Trans t;
198 Cube c;
199
200 t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)];
201 c = apply_trans(t, cube);
202
203 return index_eofbepos_sym16(c) * POW3TO7 + c.coud;
204}
205
206static uint64_t
207index_drudfin_noE_sym16(Cube cube)
208{
209 Trans t;
210 Cube c;
211
212 t = sd_cp_16.transtorep[coord_cp.index(cube)];
213 c = apply_trans(t, cube);
214
215 return index_cp_sym16(c) * FACTORIAL8 + coord_epud.index(c);
216}
217
218static uint64_t
219index_eofbepos_sym16(Cube cube)
220{
221 return sd_eofbepos_16.class[coord_eofbepos.index(cube)];
222}
223
224static uint64_t
225index_khuge(Cube cube)
226{
227 Trans t;
228 Cube c;
229 uint64_t a;
230
231 t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)];
232 c = apply_trans(t, cube);
233 a = (index_eofbepos_sym16(c) * 24) + (c.epose % 24);
234
235 return a * POW3TO7 + c.coud;
236}
237
238/* Other functions ***********************************************************/
239
240static void
241gensym(SymData *sd)
242{
243 uint64_t i, in, nreps = 0;
244 int j;
245 Cube c, d;
246
247 if (sd->generated)
248 return;
249
250 sd->class = malloc(sd->coord->max * sizeof(uint64_t));
251 sd->rep = malloc(sd->coord->max * sizeof(Cube));
252 sd->transtorep = malloc(sd->coord->max * sizeof(Trans));
253
254 if (read_symdata_file(sd)) {
255 sd->generated = true;
256 return;
257 }
258
259 fprintf(stderr, "Cannot load %s, generating it\n", sd->filename);
260
261 for (i = 0; i < sd->coord->max; i++)
262 sd->class[i] = sd->coord->max + 1;
263
264 for (i = 0; i < sd->coord->max; i++) {
265 if (sd->class[i] == sd->coord->max + 1) {
266 c = sd->coord->cube(i);
267 sd->rep[nreps] = c;
268 for (j = 0; j < sd->ntrans; j++) {
269 d = apply_trans(sd->trans[j], c);
270 in = sd->coord->index(d);
271
272 if (sd->class[in] == sd->coord->max + 1) {
273 sd->class[in] = nreps;
274 sd->transtorep[in] =
275 inverse_trans(sd->trans[j]);
276 }
277 }
278 nreps++;
279 }
280 }
281
282 sd->sym_coord->max = nreps;
283 sd->rep = realloc(sd->rep, nreps * sizeof(Cube));
284 sd->generated = true;
285
286 fprintf(stderr, "Found %lu classes\n", nreps);
287
288 if (!write_symdata_file(sd))
289 fprintf(stderr, "Error writing SymData file\n");
290
291 return;
292}
293
294static bool
295read_symdata_file(SymData *sd)
296{
297 init_env();
298
299 FILE *f;
300 char fname[strlen(tabledir)+100];
301 uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max;
302 bool r = true;
303
304 strcpy(fname, tabledir);
305 strcat(fname, "/");
306 strcat(fname, sd->filename);
307
308 if ((f = fopen(fname, "rb")) == NULL)
309 return false;
310
311 r = r && fread(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1;
312 r = r && fread(sd->rep, sizeof(Cube), *sn, f) == *sn;
313 r = r && fread(sd->class, sizeof(uint64_t), n, f) == n;
314 r = r && fread(sd->transtorep, sizeof(Trans), n, f) == n;
315
316 fclose(f);
317 return r;
318}
319
320static bool
321write_symdata_file(SymData *sd)
322{
323 init_env();
324
325 FILE *f;
326 char fname[strlen(tabledir)+100];
327 uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max;
328 bool r = true;
329
330 strcpy(fname, tabledir);
331 strcat(fname, "/");
332 strcat(fname, sd->filename);
333
334 if ((f = fopen(fname, "wb")) == NULL)
335 return false;
336
337 r = r && fwrite(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1;
338 r = r && fwrite(sd->rep, sizeof(Cube), *sn, f) == *sn;
339 r = r && fwrite(sd->class, sizeof(uint64_t), n, f) == n;
340 r = r && fwrite(sd->transtorep, sizeof(Trans), n, f) == n;
341
342 fclose(f);
343 return r;
344}
345
346void
347init_symcoord()
348{
349 int i;
350
351 static bool initialized = false;
352 if (initialized)
353 return;
354 initialized = true;
355
356 for (i = 0; i < nsymdata; i++)
357 gensym(all_sd[i]);
358}
359
diff --git a/old/2021-11-10-beforeremovingchecker/symcoord.h b/old/2021-11-10-beforeremovingchecker/symcoord.h
new file mode 100644
index 0000000..f231c92
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/symcoord.h
@@ -0,0 +1,15 @@
1#ifndef SYMCOORD_H
2#define SYMCOORD_H
3
4#include "coord.h"
5
6extern Coordinate coord_coud_sym16;
7extern Coordinate coord_cp_sym16;
8extern Coordinate coord_eofbepos_sym16;
9extern Coordinate coord_drud_sym16;
10extern Coordinate coord_drudfin_noE_sym16;
11extern Coordinate coord_khuge;
12
13void init_symcoord();
14
15#endif
diff --git a/old/2021-11-10-beforeremovingchecker/trans.c b/old/2021-11-10-beforeremovingchecker/trans.c
new file mode 100644
index 0000000..ff3cdbb
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/trans.c
@@ -0,0 +1,372 @@
1#include "trans.h"
2
3/* Local functions ***********************************************************/
4
5static bool read_ttables_file();
6static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f);
7static bool write_ttables_file();
8
9/* Tables and other data *****************************************************/
10
11static int ep_mirror[12] = {
12 [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL,
13 [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL,
14 [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL
15};
16
17static int cp_mirror[8] = {
18 [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL,
19 [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL
20};
21
22static int cpos_mirror[6] = {
23 [U_center] = U_center, [D_center] = D_center,
24 [R_center] = L_center, [L_center] = R_center,
25 [F_center] = F_center, [B_center] = B_center
26};
27
28/* TODO Is there a more elegant way? */
29static char rotation_alg_string[100][NROTATIONS] = {
30 [uf] = "", [ur] = "y", [ub] = "y2", [ul] = "y3",
31 [df] = "z2", [dr] = "y z2", [db] = "x2", [dl] = "y3 z2",
32 [rf] = "z3", [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3",
33 [lf] = "z", [ld] = "z y3", [lb] = "z y2", [lu] = "z y",
34 [fu] = "x y2", [fr] = "x y", [fd] = "x", [fl] = "x y3",
35 [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3",
36};
37
38static int epose_source[NTRANS]; /* 0=epose, 1=eposs, 2=eposm */
39static int eposs_source[NTRANS];
40static int eposm_source[NTRANS];
41static int eofb_source[NTRANS]; /* 0=eoud, 1=eorl, 2=eofb */
42static int eorl_source[NTRANS];
43static int eoud_source[NTRANS];
44static int coud_source[NTRANS]; /* 0=coud, 1=corl, 2=cofb */
45static int cofb_source[NTRANS];
46static int corl_source[NTRANS];
47
48static int epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
49static int eposs_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
50static int eposm_ttable[NTRANS][FACTORIAL12/FACTORIAL8];
51static int eo_ttable[NTRANS][POW2TO11];
52static int cp_ttable[NTRANS][FACTORIAL8];
53static int co_ttable[NTRANS][POW3TO7];
54static int cpos_ttable[NTRANS][FACTORIAL6];
55static Move moves_ttable[NTRANS][NMOVES];
56
57/* Local functions implementation ********************************************/
58
59void
60init_trans() {
61 static bool initialized = false;
62 if (initialized)
63 return;
64 initialized = true;
65
66 Cube aux, cube, c[3];
67 CubeArray epcp;
68 int i, eparr[12], eoarr[12], cparr[8], coarr[8];
69 unsigned int ui;
70 Move mi, move;
71 Trans m;
72
73 /* Compute sources */
74 for (i = 0; i < NTRANS; i++) {
75 cube = apply_alg(rotation_alg(i), (Cube){0});
76
77 epose_source[i] = edge_slice(what_edge_at(cube, FR));
78 eposs_source[i] = edge_slice(what_edge_at(cube, UR));
79 eposm_source[i] = edge_slice(what_edge_at(cube, UF));
80 eofb_source[i] = what_center_at(cube, F_center)/2;
81 eorl_source[i] = what_center_at(cube, R_center)/2;
82 eoud_source[i] = what_center_at(cube, U_center)/2;
83 coud_source[i] = what_center_at(cube, U_center)/2;
84 cofb_source[i] = what_center_at(cube, F_center)/2;
85 corl_source[i] = what_center_at(cube, R_center)/2;
86 }
87
88 if (read_ttables_file())
89 return;
90
91 fprintf(stderr, "Cannot load %s, generating it\n", "ttables");
92
93 /* Initialize tables */
94 for (m = 0; m < NTRANS; m++) {
95 epcp = (CubeArray){ .ep = eparr, .cp = cparr };
96 cube = apply_alg(rotation_alg(m), (Cube){0});
97 cube_to_arrays(cube, &epcp, pf_epcp);
98 if (m >= NROTATIONS) {
99 apply_permutation(ep_mirror, eparr, 12);
100 apply_permutation(cp_mirror, cparr, 8);
101 }
102
103 for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) {
104 c[0] = admissible_ep((Cube){ .epose = ui }, pf_e);
105 c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s);
106 c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m);
107
108 cube = rotate_via_compose(m,c[epose_source[m]],pf_ep);
109 epose_ttable[m][ui] = cube.epose;
110
111 cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep);
112 eposs_ttable[m][ui] = cube.eposs;
113
114 cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep);
115 eposm_ttable[m][ui] = cube.eposm;
116 }
117 for (ui = 0; ui < POW2TO11; ui++ ) {
118 int_to_sum_zero_array(ui, 2, 12, eoarr);
119 apply_permutation(eparr, eoarr, 12);
120 eo_ttable[m][ui] = digit_array_to_int(eoarr, 11, 2);
121 }
122 for (ui = 0; ui < POW3TO7; ui++) {
123 int_to_sum_zero_array(ui, 3, 8, coarr);
124 apply_permutation(cparr, coarr, 8);
125 co_ttable[m][ui] = digit_array_to_int(coarr, 7, 3);
126 if (m >= NROTATIONS)
127 co_ttable[m][ui] =
128 invert_digits(co_ttable[m][ui], 3, 7);
129 }
130 for (ui = 0; ui < FACTORIAL8; ui++) {
131 cube = (Cube){ .cp = ui };
132 cube = rotate_via_compose(m, cube, pf_cp);
133 cp_ttable[m][ui] = cube.cp;
134 }
135 for (ui = 0; ui < FACTORIAL6; ui++) {
136 cube = (Cube){ .cpos = ui };
137 cube = rotate_via_compose(m, cube, pf_cpos);
138 cpos_ttable[m][ui] = cube.cpos;
139 }
140 for (mi = 0; mi < NMOVES; mi++) {
141 /* Old version:
142 *
143 aux = apply_trans(m, apply_move(mi, (Cube){0}));
144 for (move = 0; move < NMOVES; move++) {
145 cube = apply_move(inverse_move(move), aux);
146 mirr = apply_trans(uf_mirror, cube);
147 if (is_solved(cube) || is_solved(mirr))
148 moves_ttable[m][mi] = move;
149 }
150 */
151
152 aux = apply_trans(m, apply_move(mi, (Cube){0}));
153 for (move = 0; move < NMOVES; move++) {
154 cube = apply_move(inverse_move(move), aux);
155 if (is_solved(cube)) {
156 moves_ttable[m][mi] = move;
157 break;
158 }
159 }
160 }
161 }
162
163 if (!write_ttables_file())
164 fprintf(stderr, "Error writing ttables\n");
165}
166
167static bool
168read_ttables_file()
169{
170 init_env();
171
172 FILE *f;
173 char fname[strlen(tabledir)+20];
174 int b = sizeof(int);
175 bool r = true;
176 Move m;
177
178 /* Table sizes, used for reading and writing files */
179 uint64_t me[11] = {
180 [0] = FACTORIAL12/FACTORIAL8,
181 [1] = FACTORIAL12/FACTORIAL8,
182 [2] = FACTORIAL12/FACTORIAL8,
183 [3] = POW2TO11,
184 [4] = FACTORIAL8,
185 [5] = POW3TO7,
186 [6] = FACTORIAL6,
187 [7] = NMOVES
188 };
189
190 strcpy(fname, tabledir);
191 strcat(fname, "/");
192 strcat(fname, "ttables");
193
194 if ((f = fopen(fname, "rb")) == NULL)
195 return false;
196
197 for (m = 0; m < NTRANS; m++) {
198 r = r && fread(epose_ttable[m], b, me[0], f) == me[0];
199 r = r && fread(eposs_ttable[m], b, me[1], f) == me[1];
200 r = r && fread(eposm_ttable[m], b, me[2], f) == me[2];
201 r = r && fread(eo_ttable[m], b, me[3], f) == me[3];
202 r = r && fread(cp_ttable[m], b, me[4], f) == me[4];
203 r = r && fread(co_ttable[m], b, me[5], f) == me[5];
204 r = r && fread(cpos_ttable[m], b, me[6], f) == me[6];
205 r = r && fread(moves_ttable[m], b, me[7], f) == me[7];
206 }
207
208 fclose(f);
209 return r;
210}
211
212static Cube
213rotate_via_compose(Trans r, Cube c, PieceFilter f)
214{
215 static int zero12[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
216 static int zero8[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
217 static CubeArray ma = {
218 .ep = ep_mirror,
219 .eofb = zero12,
220 .eorl = zero12,
221 .eoud = zero12,
222 .cp = cp_mirror,
223 .coud = zero8,
224 .corl = zero8,
225 .cofb = zero8,
226 .cpos = cpos_mirror
227 };
228
229 Alg *inv = inverse_alg(rotation_alg(r));
230 Cube ret = {0};
231
232 if (r >= NROTATIONS)
233 ret = move_via_arrays(&ma, ret, f);
234 ret = apply_alg_generic(inv, ret, f, true);
235
236 ret = compose_filtered(c, ret, f);
237
238 ret = apply_alg_generic(rotation_alg(r), ret, f, true);
239 if (r >= NROTATIONS)
240 ret = move_via_arrays(&ma, ret, f);
241
242 free_alg(inv);
243 return ret;
244}
245
246static bool
247write_ttables_file()
248{
249 init_env();
250
251 FILE *f;
252 char fname[strlen(tabledir)+20];
253 bool r = true;
254 int b = sizeof(int);
255 Move m;
256
257 /* Table sizes, used for reading and writing files */
258 uint64_t me[11] = {
259 [0] = FACTORIAL12/FACTORIAL8,
260 [1] = FACTORIAL12/FACTORIAL8,
261 [2] = FACTORIAL12/FACTORIAL8,
262 [3] = POW2TO11,
263 [4] = FACTORIAL8,
264 [5] = POW3TO7,
265 [6] = FACTORIAL6,
266 [7] = NMOVES
267 };
268
269 strcpy(fname, tabledir);
270 strcat(fname, "/ttables");
271
272 if ((f = fopen(fname, "wb")) == NULL)
273 return false;
274
275 for (m = 0; m < NTRANS; m++) {
276 r = r && fwrite(epose_ttable[m], b, me[0], f) == me[0];
277 r = r && fwrite(eposs_ttable[m], b, me[1], f) == me[1];
278 r = r && fwrite(eposm_ttable[m], b, me[2], f) == me[2];
279 r = r && fwrite(eo_ttable[m], b, me[3], f) == me[3];
280 r = r && fwrite(cp_ttable[m], b, me[4], f) == me[4];
281 r = r && fwrite(co_ttable[m], b, me[5], f) == me[5];
282 r = r && fwrite(cpos_ttable[m], b, me[6], f) == me[6];
283 r = r && fwrite(moves_ttable[m], b, me[7], f) == me[7];
284 }
285
286 fclose(f);
287 return r;
288}
289
290/* Public functions **********************************************************/
291
292Cube
293apply_trans(Trans t, Cube cube)
294{
295 /*init_trans();*/
296
297 int aux_epos[3] = { cube.epose, cube.eposs, cube.eposm };
298 int aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb };
299 int aux_co[3] = { cube.coud, cube.corl, cube.cofb };
300
301 return (Cube) {
302 .epose = epose_ttable[t][aux_epos[epose_source[t]]],
303 .eposs = eposs_ttable[t][aux_epos[eposs_source[t]]],
304 .eposm = eposm_ttable[t][aux_epos[eposm_source[t]]],
305 .eofb = eo_ttable[t][aux_eo[eofb_source[t]]],
306 .eorl = eo_ttable[t][aux_eo[eorl_source[t]]],
307 .eoud = eo_ttable[t][aux_eo[eoud_source[t]]],
308 .coud = co_ttable[t][aux_co[coud_source[t]]],
309 .corl = co_ttable[t][aux_co[corl_source[t]]],
310 .cofb = co_ttable[t][aux_co[cofb_source[t]]],
311 .cp = cp_ttable[t][cube.cp],
312 .cpos = cpos_ttable[t][cube.cpos]
313 };
314}
315
316Trans
317inverse_trans(Trans t)
318{
319 /* TODO is there a more elegant way? */
320 static Trans inverse_trans_aux[NTRANS] = {
321 [uf] = uf, [ur] = ul, [ul] = ur, [ub] = ub,
322 [df] = df, [dr] = dr, [dl] = dl, [db] = db,
323 [rf] = lf, [rd] = bl, [rb] = rb, [ru] = fr,
324 [lf] = rf, [ld] = br, [lb] = lb, [lu] = fl,
325 [fu] = fu, [fr] = ru, [fd] = bu, [fl] = lu,
326 [bu] = fd, [br] = ld, [bd] = bd, [bl] = rd,
327
328 [uf_mirror] = uf_mirror, [ur_mirror] = ur_mirror,
329 [ul_mirror] = ul_mirror, [ub_mirror] = ub_mirror,
330 [df_mirror] = df_mirror, [dr_mirror] = dl_mirror,
331 [dl_mirror] = dr_mirror, [db_mirror] = db_mirror,
332 [rf_mirror] = rf_mirror, [rd_mirror] = br_mirror,
333 [rb_mirror] = lb_mirror, [ru_mirror] = fl_mirror,
334 [lf_mirror] = lf_mirror, [ld_mirror] = bl_mirror,
335 [lb_mirror] = rb_mirror, [lu_mirror] = fr_mirror,
336 [fu_mirror] = fu_mirror, [fr_mirror] = lu_mirror,
337 [fd_mirror] = bu_mirror, [fl_mirror] = ru_mirror,
338 [bu_mirror] = fd_mirror, [br_mirror] = rd_mirror,
339 [bd_mirror] = bd_mirror, [bl_mirror] = ld_mirror
340 };
341
342 return inverse_trans_aux[t];
343}
344
345Alg *
346rotation_alg(Trans t)
347{
348 int i;
349
350 static Alg *rotation_alg_arr[NROTATIONS];
351 static bool initialized = false;
352
353 if (!initialized) {
354 for (i = 0; i < NROTATIONS; i++)
355 rotation_alg_arr[i] = new_alg(rotation_alg_string[i]);
356
357 initialized = true;
358 }
359
360 return rotation_alg_arr[t % NROTATIONS];
361}
362
363void
364transform_alg(Trans t, Alg *alg)
365{
366 int i;
367
368 /*init_trans();*/
369
370 for (i = 0; i < alg->len; i++)
371 alg->move[i] = moves_ttable[t][alg->move[i]];
372}
diff --git a/old/2021-11-10-beforeremovingchecker/trans.h b/old/2021-11-10-beforeremovingchecker/trans.h
new file mode 100644
index 0000000..2eda568
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/trans.h
@@ -0,0 +1,13 @@
1#ifndef TRANS_H
2#define TRANS_H
3
4#include "moves.h"
5
6Cube apply_trans(Trans t, Cube cube);
7Trans inverse_trans(Trans t);
8Alg * rotation_alg(Trans i);
9void transform_alg(Trans i, Alg *alg);
10
11void init_trans();
12
13#endif
diff --git a/old/2021-11-10-beforeremovingchecker/utils.c b/old/2021-11-10-beforeremovingchecker/utils.c
new file mode 100644
index 0000000..f72a00e
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/utils.c
@@ -0,0 +1,274 @@
1#include "utils.h"
2
3void
4apply_permutation(int *perm, int *set, int n)
5{
6 int *aux = malloc(n * sizeof(int));
7 int i;
8
9 if (!is_perm(perm, n))
10 return;
11
12 for (i = 0; i < n; i++)
13 aux[i] = set[perm[i]];
14
15 memcpy(set, aux, n * sizeof(int));
16 free(aux);
17}
18
19int
20binomial(int n, int k)
21{
22 if (n < 0 || k < 0 || k > n)
23 return 0;
24
25 return factorial(n) / (factorial(k) * factorial(n-k));
26}
27
28int
29digit_array_to_int(int *a, int n, int b)
30{
31 int i, ret = 0, p = 1;
32
33 for (i = 0; i < n; i++, p *= b)
34 ret += a[i] * p;
35
36 return ret;
37}
38
39int
40factorial(int n)
41{
42 int i, ret = 1;
43
44 if (n < 0)
45 return 0;
46
47 for (i = 1; i <= n; i++)
48 ret *= i;
49
50 return ret;
51}
52
53void
54index_to_perm(int p, int n, int *r)
55{
56 int *a = malloc(n * sizeof(int));
57 int i, j, c;
58
59 for (i = 0; i < n; i++)
60 a[i] = 0;
61
62 if (p < 0 || p >= factorial(n))
63 for (i = 0; i < n; i++)
64 r[i] = -1;
65
66 for (i = 0; i < n; i++) {
67 c = 0;
68 j = 0;
69 while (c <= p / factorial(n-i-1))
70 c += a[j++] ? 0 : 1;
71 r[i] = j-1;
72 a[j-1] = 1;
73 p %= factorial(n-i-1);
74 }
75
76 free(a);
77}
78
79void
80index_to_subset(int s, int n, int k, int *r)
81{
82 int i, j, v;
83
84 if (s < 0 || s >= binomial(n, k)) {
85 for (i = 0; i < n; i++)
86 r[i] = -1;
87 return;
88 }
89
90 for (i = 0; i < n; i++) {
91 if (k == n-i) {
92 for (j = i; j < n; j++)
93 r[j] = 1;
94 return;
95 }
96
97 if (k == 0) {
98 for (j = i; j < n; j++)
99 r[j] = 0;
100 return;
101 }
102
103 v = binomial(n-i-1, k);
104 if (s >= v) {
105 r[i] = 1;
106 k--;
107 s -= v;
108 } else {
109 r[i] = 0;
110 }
111 }
112}
113
114void
115int_to_digit_array(int a, int b, int n, int *r)
116{
117 int i;
118
119 if (b <= 1)
120 for (i = 0; i < n; i++)
121 r[i] = 0;
122 else
123 for (i = 0; i < n; i++, a /= b)
124 r[i] = a % b;
125}
126
127void
128int_to_sum_zero_array(int x, int b, int n, int *a)
129{
130 int i, s = 0;
131
132 if (b <= 1) {
133 for (i = 0; i < n; i++)
134 a[i] = 0;
135 } else {
136 int_to_digit_array(x, b, n-1, a);
137 for (i = 0; i < n - 1; i++)
138 s = (s + a[i]) % b;
139 a[n-1] = (b - s) % b;
140 }
141}
142
143int
144invert_digits(int a, int b, int n)
145{
146 int i, ret, *r = malloc(n * sizeof(int));
147
148 int_to_digit_array(a, b, n, r);
149 for (i = 0; i < n; i++)
150 r[i] = (b-r[i]) % b;
151
152 ret = digit_array_to_int(r, n, b);
153 free(r);
154 return ret;
155}
156
157bool
158is_perm(int *a, int n)
159{
160 int *aux = malloc(n * sizeof(int));
161 int i;
162
163 for (i = 0; i < n; i++)
164 if (a[i] < 0 || a[i] >= n)
165 return false;
166 else
167 aux[a[i]] = 1;
168
169 for (i = 0; i < n; i++)
170 if (!aux[i])
171 return false;
172
173 free(aux);
174
175 return true;
176}
177
178bool
179is_subset(int *a, int n, int k)
180{
181 int i, sum = 0;
182
183 for (i = 0; i < n; i++)
184 sum += a[i] ? 1 : 0;
185
186 return sum == k;
187}
188
189int
190perm_sign(int *a, int n)
191{
192 int i, j, ret = 0;
193
194 if (!is_perm(a,n))
195 return -1;
196
197 for (i = 0; i < n; i++)
198 for (j = i+1; j < n; j++)
199 ret += (a[i] > a[j]) ? 1 : 0;
200
201 return ret % 2;
202}
203
204int
205perm_to_index(int *a, int n)
206{
207 int i, j, c, ret = 0;
208
209 if (!is_perm(a, n))
210 return -1;
211
212 for (i = 0; i < n; i++) {
213 c = 0;
214 for (j = i+1; j < n; j++)
215 c += (a[i] > a[j]) ? 1 : 0;
216 ret += factorial(n-i-1) * c;
217 }
218
219 return ret;
220}
221
222int
223powint(int a, int b)
224{
225 if (b < 0)
226 return 0;
227 if (b == 0)
228 return 1;
229
230 if (b % 2)
231 return a * powint(a, b-1);
232 else
233 return powint(a*a, b/2);
234}
235
236int
237subset_to_index(int *a, int n, int k)
238{
239 int i, ret = 0;
240
241 if (!is_subset(a, n, k))
242 return binomial(n, k);
243
244 for (i = 0; i < n; i++) {
245 if (k == n-i)
246 return ret;
247 if (a[i]) {
248 ret += binomial(n-i-1, k);
249 k--;
250 }
251 }
252
253 return ret;
254}
255
256void
257sum_arrays_mod(int *src, int *dst, int n, int m)
258{
259 int i;
260
261 for (i = 0; i < n; i++)
262 dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m;
263}
264
265void
266swap(int *a, int *b)
267{
268 int aux;
269
270 aux = *a;
271 *a = *b;
272 *b = aux;
273}
274
diff --git a/old/2021-11-10-beforeremovingchecker/utils.h b/old/2021-11-10-beforeremovingchecker/utils.h
new file mode 100644
index 0000000..80c33ae
--- /dev/null
+++ b/old/2021-11-10-beforeremovingchecker/utils.h
@@ -0,0 +1,41 @@
1#ifndef UTILS_H
2#define UTILS_H
3
4#include <stdbool.h>
5#include <stdlib.h>
6#include <string.h>
7
8#define POW2TO6 64ULL
9#define POW2TO11 2048ULL
10#define POW2TO12 4096ULL
11#define POW3TO7 2187ULL
12#define POW3TO8 6561ULL
13#define FACTORIAL4 24ULL
14#define FACTORIAL6 720ULL
15#define FACTORIAL7 5040ULL
16#define FACTORIAL8 40320ULL
17#define FACTORIAL12 479001600ULL
18#define BINOM12ON4 495ULL
19#define BINOM8ON4 70ULL
20#define MIN(a,b) (((a) < (b)) ? (a) : (b))
21#define MAX(a,b) (((a) > (b)) ? (a) : (b))
22
23void apply_permutation(int *perm, int *set, int n);
24int binomial(int n, int k);
25int digit_array_to_int(int *a, int n, int b);
26int factorial(int n);
27void index_to_perm(int p, int n, int *r);
28void index_to_subset(int s, int n, int k, int *r);
29void int_to_digit_array(int a, int b, int n, int *r);
30void int_to_sum_zero_array(int x, int b, int n, int *a);
31int invert_digits(int a, int b, int n);
32bool is_perm(int *a, int n);
33bool is_subset(int *a, int n, int k);
34int perm_sign(int *a, int n);
35int perm_to_index(int *a, int n);
36int powint(int a, int b);
37int subset_to_index(int *a, int n, int k);
38void sum_arrays_mod(int *src, int *dst, int n, int m);
39void swap(int *a, int *b);
40
41#endif

Generated with cgit - Back to sebastiano.tronto.net