From 4fb67201414169a2687f41c4056b2e284b4938cb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 22:05:00 +0100 Subject: Removed old files --- old/2021-11-10-beforeremovingchecker/alg.c | 366 --------- old/2021-11-10-beforeremovingchecker/alg.h | 35 - old/2021-11-10-beforeremovingchecker/commands.c | 329 -------- old/2021-11-10-beforeremovingchecker/commands.h | 13 - old/2021-11-10-beforeremovingchecker/coord.c | 629 ---------------- old/2021-11-10-beforeremovingchecker/coord.h | 40 - old/2021-11-10-beforeremovingchecker/cube.c | 716 ------------------ old/2021-11-10-beforeremovingchecker/cube.h | 40 - old/2021-11-10-beforeremovingchecker/cubetypes.h | 298 -------- old/2021-11-10-beforeremovingchecker/env.c | 45 -- old/2021-11-10-beforeremovingchecker/env.h | 15 - old/2021-11-10-beforeremovingchecker/moves.c | 474 ------------ old/2021-11-10-beforeremovingchecker/moves.h | 16 - old/2021-11-10-beforeremovingchecker/pf.c | 80 -- old/2021-11-10-beforeremovingchecker/pf.h | 18 - old/2021-11-10-beforeremovingchecker/pruning.c | 272 ------- old/2021-11-10-beforeremovingchecker/pruning.h | 23 - old/2021-11-10-beforeremovingchecker/shell.c | 99 --- old/2021-11-10-beforeremovingchecker/shell.h | 13 - old/2021-11-10-beforeremovingchecker/solve.c | 209 ------ old/2021-11-10-beforeremovingchecker/solve.h | 9 - old/2021-11-10-beforeremovingchecker/steps.c | 916 ----------------------- old/2021-11-10-beforeremovingchecker/steps.h | 10 - old/2021-11-10-beforeremovingchecker/symcoord.c | 359 --------- old/2021-11-10-beforeremovingchecker/symcoord.h | 15 - old/2021-11-10-beforeremovingchecker/trans.c | 372 --------- old/2021-11-10-beforeremovingchecker/trans.h | 13 - old/2021-11-10-beforeremovingchecker/utils.c | 274 ------- old/2021-11-10-beforeremovingchecker/utils.h | 41 - 29 files changed, 5739 deletions(-) delete mode 100644 old/2021-11-10-beforeremovingchecker/alg.c delete mode 100644 old/2021-11-10-beforeremovingchecker/alg.h delete mode 100644 old/2021-11-10-beforeremovingchecker/commands.c delete mode 100644 old/2021-11-10-beforeremovingchecker/commands.h delete mode 100644 old/2021-11-10-beforeremovingchecker/coord.c delete mode 100644 old/2021-11-10-beforeremovingchecker/coord.h delete mode 100644 old/2021-11-10-beforeremovingchecker/cube.c delete mode 100644 old/2021-11-10-beforeremovingchecker/cube.h delete mode 100644 old/2021-11-10-beforeremovingchecker/cubetypes.h delete mode 100644 old/2021-11-10-beforeremovingchecker/env.c delete mode 100644 old/2021-11-10-beforeremovingchecker/env.h delete mode 100644 old/2021-11-10-beforeremovingchecker/moves.c delete mode 100644 old/2021-11-10-beforeremovingchecker/moves.h delete mode 100644 old/2021-11-10-beforeremovingchecker/pf.c delete mode 100644 old/2021-11-10-beforeremovingchecker/pf.h delete mode 100644 old/2021-11-10-beforeremovingchecker/pruning.c delete mode 100644 old/2021-11-10-beforeremovingchecker/pruning.h delete mode 100644 old/2021-11-10-beforeremovingchecker/shell.c delete mode 100644 old/2021-11-10-beforeremovingchecker/shell.h delete mode 100644 old/2021-11-10-beforeremovingchecker/solve.c delete mode 100644 old/2021-11-10-beforeremovingchecker/solve.h delete mode 100644 old/2021-11-10-beforeremovingchecker/steps.c delete mode 100644 old/2021-11-10-beforeremovingchecker/steps.h delete mode 100644 old/2021-11-10-beforeremovingchecker/symcoord.c delete mode 100644 old/2021-11-10-beforeremovingchecker/symcoord.h delete mode 100644 old/2021-11-10-beforeremovingchecker/trans.c delete mode 100644 old/2021-11-10-beforeremovingchecker/trans.h delete mode 100644 old/2021-11-10-beforeremovingchecker/utils.c delete mode 100644 old/2021-11-10-beforeremovingchecker/utils.h (limited to 'old/2021-11-10-beforeremovingchecker') diff --git a/old/2021-11-10-beforeremovingchecker/alg.c b/old/2021-11-10-beforeremovingchecker/alg.c deleted file mode 100644 index 06c2d7b..0000000 --- a/old/2021-11-10-beforeremovingchecker/alg.c +++ /dev/null @@ -1,366 +0,0 @@ -#include "alg.h" - -/* Local functions ***********************************************************/ - -static void free_alglistnode(AlgListNode *aln); -static void realloc_alg(Alg *alg, int n); - -/* Movesets ******************************************************************/ - -bool -moveset_HTM(Move m) -{ - return m >= U && m <= B3; -} - -bool -moveset_URF(Move m) -{ - Move b = base_move(m); - - return b == U || b == R || b == F; -} - -bool -moveset_eofb(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || b == R || b == L || - ((b == F || b == B) && m == b+1); -} - -bool -moveset_drud(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || - ((b == R || b == L || b == F || b == B) && m == b + 1); -} - -bool -moveset_htr(Move m) -{ - Move b = base_move(m); - - return moveset_HTM(m) && m == b + 1; -} - - -/* Functions *****************************************************************/ - -void -append_alg(AlgList *l, Alg *alg) -{ - AlgListNode *node = malloc(sizeof(AlgListNode)); - int i; - - node->alg = new_alg(""); - for (i = 0; i < alg->len; i++) - append_move(node->alg, alg->move[i], alg->inv[i]); - node->next = NULL; - - if (++l->len == 1) - l->first = node; - else - l->last->next = node; - l->last = node; -} - -void -append_move(Alg *alg, Move m, bool inverse) -{ - if (alg->len == alg->allocated) - realloc_alg(alg, 2*alg->len); - - alg->move[alg->len] = m; - alg->inv [alg->len] = inverse; - alg->len++; -} - -Move -base_move(Move m) -{ - if (m == NULLMOVE) - return NULLMOVE; - else - return m - (m-1)%3; -} - -void -compose_alg(Alg *alg1, Alg *alg2) -{ - int i; - - for (i = 0; i < alg2->len; i++) - append_move(alg1, alg2->move[i], alg2->inv[i]); -} - -void -free_alg(Alg *alg) -{ - free(alg->move); - free(alg->inv); - free(alg); -} - -void -free_alglist(AlgList *l) -{ - AlgListNode *aux, *i = l->first; - - while (i != NULL) { - aux = i->next; - free_alglistnode(i); - i = aux; - } - free(l); -} - -static void -free_alglistnode(AlgListNode *aln) -{ - free_alg(aln->alg); - free(aln); -} - -Alg * -inverse_alg(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = alg->len-1; i >= 0; i--) - append_move(ret, inverse_move(alg->move[i]), alg->inv[i]); - - return ret; -} - -Move -inverse_move(Move m) -{ - return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3); -} - -char * -move_string(Move m) -{ - static char move_string_aux[NMOVES][7] = { - [NULLMOVE] = "-", - [U] = "U", [U2] = "U2", [U3] = "U\'", - [D] = "D", [D2] = "D2", [D3] = "D\'", - [R] = "R", [R2] = "R2", [R3] = "R\'", - [L] = "L", [L2] = "L2", [L3] = "L\'", - [F] = "F", [F2] = "F2", [F3] = "F\'", - [B] = "B", [B2] = "B2", [B3] = "B\'", - [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'", - [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'", - [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'", - [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'", - [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'", - [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'", - [M] = "M", [M2] = "M2", [M3] = "M\'", - [E] = "E", [E2] = "E2", [E3] = "E\'", - [S] = "S", [S2] = "S2", [S3] = "S\'", - [x] = "x", [x2] = "x2", [x3] = "x\'", - [y] = "y", [y2] = "y2", [y3] = "y\'", - [z] = "z", [z2] = "z2", [z3] = "z\'", - }; - - return move_string_aux[m]; -} - -void -movelist_to_position(Move *movelist, int *position) -{ - Move m; - - for (m = 0; m < NMOVES && movelist[m] != NULLMOVE; m++) - position[movelist[m]] = m; -} - -void -moveset_to_list(Moveset ms, Move *r) -{ - int n = 0; - Move i; - - if (ms == NULL) { - fprintf(stderr, "Error: no moveset given\n"); - return; - } - - for (i = U; i < NMOVES; i++) - if (ms(i)) - r[n++] = i; - - r[n] = NULLMOVE; -} - -Alg * -new_alg(char *str) -{ - Alg *alg = malloc(sizeof(Alg)); - int i; - bool niss = false, move_read; - Move j, m; - - alg->move = malloc(30 * sizeof(Move)); - alg->inv = malloc(30 * sizeof(bool)); - alg->allocated = 30; - alg->len = 0; - - for (i = 0; str[i]; i++) { - if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') - continue; - - if (str[i] == '(' && niss) { - fprintf(stderr, "Error reading moves: nested ( )\n"); - return alg; - } - - if (str[i] == ')' && !niss) { - fprintf(stderr, "Error reading moves: unmatched )\n"); - return alg; - } - - if (str[i] == '(' || str[i] == ')') { - niss = !niss; - continue; - } - - move_read = false; - for (j = 0; j < NMOVES; j++) { - if (str[i] == move_string(j)[0] || - (str[i] >= 'a' && str[i] <= 'z' && - str[i] == move_string(j)[0]-('A'-'a') && j<=B)) { - m = j; - if (str[i] >= 'a' && str[i] <= 'z' && j<=B) { - m += Uw - U; - } - if (m <= B && str[i+1]=='w') { - m += Uw - U; - i++; - } - if (str[i+1]=='2') { - m += 1; - i++; - } else if (str[i+1] == '\'' || - str[i+1] == '3' || - str[i+1] == '`' ) { - m += 2; - i++; - } else if ((int)str[i+1] == -62 && - (int)str[i+2] == -76) { - /* Weird apostrophe */ - m += 2; - i += 2; - } else if ((int)str[i+1] == -30 && - (int)str[i+2] == -128 && - (int)str[i+3] == -103) { - /* MacOS apostrophe */ - m += 2; - i += 3; - } - append_move(alg, m, niss); - move_read = true; - break; - } - } - - if (!move_read) { - alg = new_alg(""); - return alg; - } - } - - return alg; -} - -AlgList * -new_alglist() -{ - AlgList *ret = malloc(sizeof(AlgList)); - - ret->len = 0; - ret->first = NULL; - ret->last = NULL; - - return ret; -} - -Alg * -on_inverse(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = 0; i < alg->len; i++) - append_move(ret, alg->move[i], !alg->inv[i]); - - return ret; -} - -void -print_alg(Alg *alg, bool l) -{ - /* TODO: make it possible to print to stdout or to string */ - /* Maybe just return a string */ - char fill[4]; - int i; - bool niss = false; - - for (i = 0; i < alg->len; i++) { - if (!niss && alg->inv[i]) - strcpy(fill, i == 0 ? "(" : " ("); - if (niss && !alg->inv[i]) - strcpy(fill, ") "); - if (niss == alg->inv[i]) - strcpy(fill, i == 0 ? "" : " "); - - printf("%s%s", fill, move_string(alg->move[i])); - niss = alg->inv[i]; - } - - if (niss) - printf(")"); - if (l) - printf(" (%d)", alg->len); - - printf("\n"); -} - -void -print_alglist(AlgList *al, bool l) -{ - AlgListNode *i; - - for (i = al->first; i != NULL; i = i->next) - print_alg(i->alg, l); -} - -static void -realloc_alg(Alg *alg, int n) -{ - if (alg == NULL) { - fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); - return; - } - - if (n < alg->len) { - fprintf(stderr, "Error: alg too long for reallocation "); - fprintf(stderr, "(%d vs %d)\n", alg->len, n); - return; - } - - if (n > 1000000) { - fprintf(stderr, "Warning: very long alg,"); - fprintf(stderr, "something might go wrong.\n"); - } - - alg->move = realloc(alg->move, n * sizeof(int)); - alg->inv = realloc(alg->inv, n * sizeof(int)); - alg->allocated = n; -} - diff --git a/old/2021-11-10-beforeremovingchecker/alg.h b/old/2021-11-10-beforeremovingchecker/alg.h deleted file mode 100644 index 98900b4..0000000 --- a/old/2021-11-10-beforeremovingchecker/alg.h +++ /dev/null @@ -1,35 +0,0 @@ -#ifndef ALG_H -#define ALG_H - -#include -#include -#include - -#include "cubetypes.h" -#include "utils.h" - -bool moveset_HTM(Move m); -bool moveset_URF(Move m); -bool moveset_eofb(Move m); -bool moveset_drud(Move m); -bool moveset_htr(Move m); - -void append_alg(AlgList *l, Alg *alg); -void append_move(Alg *alg, Move m, bool inverse); -void compose_alg(Alg *alg1, Alg *alg2); -Move base_move(Move m); -void free_alg(Alg *alg); -void free_alglist(AlgList *l); -Alg * inverse_alg(Alg *alg); -Move inverse_move(Move m); -char * move_string(Move m); -void movelist_to_position(Move *ml, int *pos); -void moveset_to_list(Moveset ms, Move *lst); -Alg * new_alg(char *str); -AlgList * new_alglist(); -Alg * on_inverse(Alg *alg); -void print_alg(Alg *alg, bool l); -void print_alglist(AlgList *al, bool l); - -#endif - diff --git a/old/2021-11-10-beforeremovingchecker/commands.c b/old/2021-11-10-beforeremovingchecker/commands.c deleted file mode 100644 index b141229..0000000 --- a/old/2021-11-10-beforeremovingchecker/commands.c +++ /dev/null @@ -1,329 +0,0 @@ -#include "commands.h" - -/* Arg parsing functions *****************************************************/ - -CommandArgs * solvestep_parse_args(int c, char **v); -CommandArgs * help_parse_args(int c, char **v); -CommandArgs * print_parse_args(int c, char **v); -CommandArgs * parse_no_arg(int c, char **v); - -/* Exec functions ************************************************************/ - -static void solvestep_exec(CommandArgs *args); -static void steps_exec(CommandArgs *args); -static void commands_exec(CommandArgs *args); -static void print_exec(CommandArgs *args); -static void help_exec(CommandArgs *args); -static void quit_exec(CommandArgs *args); - -/* Local functions ***********************************************************/ - -static bool read_step(CommandArgs *args, char *str); -static bool read_scramble(int c, char **v, CommandArgs *args); - -/* Commands ******************************************************************/ - -Command -solvestep_cmd = { - .name = "solve", - .usage = "solve STEP [OPTIONS] SCRAMBLE", - .description = "Solve a step", - .parse_args = solvestep_parse_args, - .exec = solvestep_exec -}; - -Command -steps_cmd = { - .name = "steps", - .usage = "steps", - .description = "List available steps", - .parse_args = parse_no_arg, - .exec = steps_exec -}; - -Command -commands_cmd = { - .name = "commands", - .usage = "commands", - .description = "List available commands", - .parse_args = parse_no_arg, - .exec = commands_exec -}; - -Command -print_cmd = { - .name = "print", - .usage = "print SCRAMBLE", - .description = "Print written description of the cube", - .parse_args = print_parse_args, - .exec = print_exec, -}; - -Command -help_cmd = { - .name = "help", - .usage = "help [COMMAND]", - .description = "Display nissy manual page or help on specific command", - .parse_args = help_parse_args, - .exec = help_exec, -}; - -Command -quit_cmd = { - .name = "quit", - .usage = "quit", - .description = "Quit nissy", - .parse_args = parse_no_arg, - .exec = quit_exec, -}; - -Command *commands[NCOMMANDS] = { - &solvestep_cmd, - &steps_cmd, - &commands_cmd, - &help_cmd, - &print_cmd, - &quit_cmd -}; - -/* Arg parsing functions implementation **************************************/ - -CommandArgs * -solvestep_parse_args(int c, char **v) -{ - int i; - long val; - - CommandArgs *a = malloc(sizeof(CommandArgs)); - - a->success = false; - a->opts = malloc(sizeof(SolveOptions)); - a->step = steps[0]; - a->command = NULL; - a->scramble = NULL; - - a->opts->min_moves = 0; - a->opts->max_moves = 20; - a->opts->max_solutions = 1; - a->opts->optimal_only = false; - a->opts->can_niss = false; - a->opts->feedback = false; - a->opts->all = false; - a->opts->print_number = true; - - for (i = 0; i < c; i++) { - if (!strcmp(v[i], "-m")) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid min number of moves.\n"); - return a; - } - a->opts->min_moves = val; - } else if (!strcmp(v[i], "-M")) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid max number of moves.\n"); - return a; - } - a->opts->max_moves = val; - } else if (!strcmp(v[i], "-s")) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 1000000) { - fprintf(stderr, - "Invalid number of solutions.\n"); - return a; - } - a->opts->max_solutions = val; - } else if (!strcmp(v[i], "-o")) { - a->opts->optimal_only = true; - } else if (!strcmp(v[i], "-n")) { - a->opts->can_niss = true; - } else if (!strcmp(v[i], "-v")) { - a->opts->feedback = true; - } else if (!strcmp(v[i], "-a")) { - a->opts->all = true; - } else if (!strcmp(v[i], "-p")) { - a->opts->print_number = false; - } else if (!read_step(a, v[i])) { - break; - } - } - - a->success = read_scramble(c-i, &v[i], a); - return a; -} - -CommandArgs * -help_parse_args(int c, char **v) -{ - int i; - CommandArgs *a = malloc(sizeof(CommandArgs)); - - a->scramble = NULL; - a->opts = NULL; - a->step = NULL; - a->command = NULL; - - if (c == 1) { - for (i = 0; i < NCOMMANDS; i++) - if (commands[i] != NULL && - !strcmp(v[0], commands[i]->name)) - a->command = commands[i]; - if (a->command == NULL) - fprintf(stderr, "%s: command not found\n", v[0]); - } - - a->success = c == 0 || (c == 1 && a->command != NULL); - return a; -} - -CommandArgs * -parse_no_arg(int c, char **v) -{ - CommandArgs *a = malloc(sizeof(CommandArgs)); - - a->scramble = NULL; - a->opts = NULL; - a->step = NULL; - a->command = NULL; - - return a; -} - -CommandArgs * -print_parse_args(int c, char **v) -{ - CommandArgs *a = malloc(sizeof(CommandArgs)); - - a->opts = NULL; - a->step = NULL; - a->command = NULL; - - a->success = read_scramble(c-1, &v[1], a); - return a; -} - -/* Exec functions implementation *********************************************/ - -static void -solvestep_exec(CommandArgs *args) -{ - Cube c = apply_alg(args->scramble, (Cube){0}); - AlgList *sols = solve(c, args->step, args->opts); - print_alglist(sols, args->opts->print_number); - free_alglist(sols); -} - -static void -steps_exec(CommandArgs *args) -{ - int i; - - for (i = 0; i < NSTEPS && steps[i] != NULL; i++) - printf("%-15s %s\n", steps[i]->shortname, steps[i]->name); -} - -static void -commands_exec(CommandArgs *args) -{ - int i; - - for (i = 0; i < NCOMMANDS && commands[i] != NULL; i++) - printf("%s\n", commands[i]->usage); - -} - -static void -print_exec(CommandArgs *args) -{ - print_cube(apply_alg(args->scramble, (Cube){0})); -} - -static void -help_exec(CommandArgs *args) -{ - /* TODO: print full nissy manpage */ - if (args->command == NULL) { - printf("Type help COMMAND for information on a "); - printf("specific command.\n"); - printf("A more complete manual page is work in progress.\n"); - } else { - printf("Command %s: %s\nusage: %s\n", args->command->name, - args->command->description, args->command->usage); - } -} - -static void -quit_exec(CommandArgs *args) -{ - exit(0); -} - -/* Local functions implementation ********************************************/ - -static bool -read_step(CommandArgs *args, char *str) -{ - int i; - - for (i = 0; i < NSTEPS; i++) { - if (steps[i] != NULL && !strcmp(steps[i]->shortname, str)) { - args->step = steps[i]; - return true; - } - } - - return false; -} - -static bool -read_scramble(int c, char **v, CommandArgs *args) -{ - int i, k, n; - unsigned int j; - char *algstr; - - if (new_alg(v[0])->len == 0) { - fprintf(stderr, "%s: moves or option unrecognized\n", v[0]); - return false; - } - - n = 0; - for(i = 0; i < c; i++) - n += strlen(v[i]); - - algstr = malloc((n + 1) * sizeof(char)); - k = 0; - for (i = 0; i < c; i++) - for (j = 0; j < strlen(v[i]); j++) - algstr[k++] = v[i][j]; - algstr[k] = 0; - - args->scramble = new_alg(algstr); - free(algstr); - - if (args->scramble->len == 0) - fprintf(stderr, "Error reading scramble\n"); - - return args->scramble->len > 0; -} - -/* Public functions implementation *******************************************/ - -void -free_args(CommandArgs *args) -{ - if (args == NULL) - return; - - if (args->scramble != NULL) - free_alg(args->scramble); - if (args->opts != NULL) - free(args->opts); - - /* step and command must not be freed, they are static! */ - - free(args); -} diff --git a/old/2021-11-10-beforeremovingchecker/commands.h b/old/2021-11-10-beforeremovingchecker/commands.h deleted file mode 100644 index f2703fa..0000000 --- a/old/2021-11-10-beforeremovingchecker/commands.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef COMMANDS_H -#define COMMANDS_H - -#include "solve.h" -#include "steps.h" - -#define NCOMMANDS 10 - -void free_args(CommandArgs *args); - -extern Command * commands[NCOMMANDS]; - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/coord.c b/old/2021-11-10-beforeremovingchecker/coord.c deleted file mode 100644 index 343dfb3..0000000 --- a/old/2021-11-10-beforeremovingchecker/coord.c +++ /dev/null @@ -1,629 +0,0 @@ -#include "coord.h" - -static Cube antindex_eofb(uint64_t ind); -static Cube antindex_eofbepos(uint64_t ind); -static Cube antindex_epud(uint64_t ind); -static Cube antindex_coud(uint64_t ind); -static Cube antindex_corners(uint64_t ind); -static Cube antindex_cp(uint64_t ind); -static Cube antindex_cphtr(uint64_t); -static Cube antindex_cornershtr(uint64_t ind); -static Cube antindex_cornershtrfin(uint64_t ind); -static Cube antindex_drud(uint64_t ind); -static Cube antindex_drud_eofb(uint64_t ind); -static Cube antindex_htr_drud(uint64_t ind); -static Cube antindex_htrfin(uint64_t ind); - -static uint64_t index_eofb(Cube cube); -static uint64_t index_eofbepos(Cube cube); -static uint64_t index_epud(Cube cube); -static uint64_t index_coud(Cube cube); -static uint64_t index_corners(Cube cube); -static uint64_t index_cp(Cube cube); -static uint64_t index_cphtr(Cube cube); -static uint64_t index_cornershtr(Cube cube); -static uint64_t index_cornershtrfin(Cube cube); -static uint64_t index_drud(Cube cube); -static uint64_t index_drud_eofb(Cube cube); -static uint64_t index_htr_drud(Cube cube); -static uint64_t index_htrfin(Cube cube); - -static void init_cphtr_cosets(); -static void init_cphtr_left_cosets_bfs(int i, int c); -static void init_cphtr_right_cosets_color(int i, int c); -static void init_cornershtrfin(); - - -/* All sorts of useful costants and tables **********************************/ - -static int cphtr_left_cosets[FACTORIAL8]; -static int cphtr_right_cosets[FACTORIAL8]; -static int cphtr_right_rep[BINOM8ON4*6]; -static int cornershtrfin_ind[FACTORIAL8]; -static int cornershtrfin_ant[24*24/6]; - -/* Coordinates and their implementation **************************************/ - -Coordinate -coord_eofb = { - .index = index_eofb, - .cube = antindex_eofb, - .check = check_eofb, - .max = POW2TO11, - .ntrans = 1, -}; - -Coordinate -coord_eofbepos = { - .index = index_eofbepos, - .cube = antindex_eofbepos, - .check = check_eofbepos, - .max = POW2TO11 * BINOM12ON4, - .ntrans = 1, -}; - -Coordinate -coord_coud = { - .index = index_coud, - .cube = antindex_coud, - .check = check_coud, - .max = POW3TO7, - .ntrans = 1, -}; - -Coordinate -coord_corners = { - .index = index_corners, - .cube = antindex_corners, - .check = check_corners, - .max = POW3TO7 * FACTORIAL8, - .ntrans = 1, -}; - -Coordinate -coord_cp = { - .index = index_cp, - .cube = antindex_cp, - .check = check_cp, - .max = FACTORIAL8, - .ntrans = 1, -}; - -Coordinate -coord_cphtr = { - .index = index_cphtr, - .cube = antindex_cphtr, - .check = check_cphtr, - .max = BINOM8ON4 * 6, - .ntrans = 1, -}; - -Coordinate -coord_cornershtr = { - .index = index_cornershtr, - .cube = antindex_cornershtr, - .check = check_cornershtr, - .max = POW3TO7 * BINOM8ON4 * 6, - .ntrans = 1, -}; - -Coordinate -coord_cornershtrfin = { - .index = index_cornershtrfin, - .cube = antindex_cornershtrfin, - .check = check_cp, - .max = 24*24/6, - .ntrans = 1, -}; - -Coordinate -coord_epud = { - .index = index_epud, - .cube = antindex_epud, - .check = check_epud, - .max = FACTORIAL8, - .ntrans = 1, -}; - -Coordinate -coord_drud = { - .index = index_drud, - .cube = antindex_drud, - .check = check_drud, - .max = POW2TO11 * POW3TO7 * BINOM12ON4, - .ntrans = 1, -}; - -Coordinate -coord_htr_drud = { - .index = index_htr_drud, - .cube = antindex_htr_drud, - .check = check_drud, - .max = BINOM8ON4 * 6 * BINOM8ON4, - .ntrans = 1, -}; - -Coordinate -coord_htrfin = { - .index = index_htrfin, - .cube = antindex_htrfin, - .check = check_htr, - .max = 24 * 24 * 24 *24 * 24 / 6, /* should be /12 but it's ok */ - .ntrans = 1, -}; - -Coordinate -coord_drud_eofb = { - .index = index_drud_eofb, - .cube = antindex_drud_eofb, - .check = check_drud, - .max = POW3TO7 * BINOM12ON4, - .ntrans = 1, -}; - -/* Functions *****************************************************************/ - -static Cube -antindex_eofb(uint64_t ind) -{ - return (Cube){ .eofb = ind, .eorl = ind, .eoud = ind }; -} - -static Cube -antindex_eofbepos(uint64_t ind) -{ - Cube ret = {0}; - - ret.eofb = ind % POW2TO11; - ret.epose = (ind / POW2TO11) * 24; - - return ret; -} - -static Cube -antindex_epud(uint64_t ind) -{ - static bool initialized = false; - static Cube epud_aux[FACTORIAL8]; - int a[12]; - uint64_t ui; - CubeArray arr; - - if (!initialized) { - a[FR] = FR; - a[FL] = FL; - a[BL] = BL; - a[BR] = BR; - for (ui = 0; ui < FACTORIAL8; ui++) { - index_to_perm(ui, 8, a); - arr.ep = a; - epud_aux[ui] = arrays_to_cube(&arr, pf_ep); - } - - initialized = true; - } - - return epud_aux[ind]; -} - -static Cube -antindex_coud(uint64_t ind) -{ - return (Cube){ .coud = ind, .corl = ind, .cofb = ind }; -} - -static Cube -antindex_corners(uint64_t ind) -{ - Cube c = {0}; - - c.coud = ind / FACTORIAL8; - c.cp = ind % FACTORIAL8; - - return c; -} - -static Cube -antindex_cp(uint64_t ind) -{ - Cube c = {0}; - - c.cp = ind; - - return c; -} - -static Cube -antindex_cphtr(uint64_t ind) -{ - return (Cube) { .cp = cphtr_right_rep[ind] }; -} - -static Cube -antindex_cornershtr(uint64_t ind) -{ - Cube c = antindex_cphtr(ind % (BINOM8ON4 * 6)); - - c.coud = ind / (BINOM8ON4 * 6); - - return c; -} - -static Cube -antindex_cornershtrfin(uint64_t ind) -{ - return (Cube){ .cp = cornershtrfin_ant[ind] }; -} - -static Cube -antindex_drud(uint64_t ind) -{ - uint64_t epos, eofb; - Cube c; - - eofb = ind % POW2TO11; - epos = ind / (POW2TO11 * POW3TO7); - c = antindex_eofbepos(eofb + POW2TO11 * epos); - - c.coud = (ind / POW2TO11) % POW3TO7; - - return c; -} - -static Cube -antindex_drud_eofb(uint64_t ind) -{ - return antindex_drud(ind * POW2TO11); -} - -static Cube -antindex_htr_drud(uint64_t ind) -{ - Cube ret; - - ret = antindex_cphtr(ind / BINOM8ON4); - ret.eposs = (ind % BINOM8ON4) * FACTORIAL4; - - return ret; -} - -static Cube -antindex_htrfin(uint64_t ind) -{ - Cube ret; - - ret = antindex_cornershtrfin(ind/(24*24*24)); - - ret.eposm = ind % 24; - ind /= 24; - ret.eposs = ind % 24; - ind /= 24; - ret.epose = ind % 24; - - return ret; -} - -bool -check_centers(Cube cube) -{ - return cube.cpos == 0; -} - -bool -check_corners(Cube cube) -{ - return cube.cp == 0 && cube.coud == 0; -} - -bool -check_cp(Cube cube) -{ - return cube.cp == 0; -} - -bool -check_cphtr(Cube cube) -{ - return index_cphtr(cube) == 0; -} - -bool -check_cornershtr(Cube cube) -{ - return cube.coud == 0 && index_cphtr(cube) == 0; -} - -bool -check_coud(Cube cube) -{ - return cube.coud == 0; -} - -bool -check_drud(Cube cube) -{ - return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0; -} - -bool -check_htr(Cube cube) -{ - return check_cornershtr(cube) && - cube.eofb == 0 && cube.eorl == 0 && cube.eoud == 0; -} - -bool -check_drudfin_noE(Cube cube) -{ - return cube.eposs == 0 && cube.eposm == 0 && cube.cp == 0; -} - -bool -check_eofb(Cube cube) -{ - return cube.eofb == 0; -} - -bool -check_eofbepos(Cube cube) -{ - return cube.eofb == 0 && cube.epose / 24 == 0; -} - -bool -check_epose(Cube cube) -{ - return cube.epose == 0; -} - -bool -check_epud(Cube cube) -{ - return cube.eposs == 0 && cube.eposm == 0; -} - -bool -check_ep(Cube cube) -{ - return cube.epose == 0 && cube.eposs == 0 && cube.eposm == 0; -} - -bool -check_khuge(Cube cube) -{ - return check_drud(cube) && cube.epose % 24 == 0; -} - -bool -check_nothing(Cube cube) -{ - return is_admissible(cube); /*TODO: maybe change?*/ -} - -static uint64_t -index_eofb(Cube cube) -{ - return cube.eofb; -} - -static uint64_t -index_eofbepos(Cube cube) -{ - return (cube.epose / FACTORIAL4) * POW2TO11 + cube.eofb; -} - -static uint64_t -index_epud(Cube cube) -{ - uint64_t ret; - CubeArray *arr = new_cubearray(cube, pf_ep); - - ret = perm_to_index(arr->ep, 8); - free_cubearray(arr, pf_ep); - - return ret; -} - -static uint64_t -index_coud(Cube cube) -{ - return cube.coud; -} - -static uint64_t -index_corners(Cube cube) -{ - return cube.coud * FACTORIAL8 + cube.cp; -} - -static uint64_t -index_cp(Cube cube) -{ - return cube.cp; -} - -static uint64_t -index_cphtr(Cube cube) -{ - return cphtr_right_cosets[cube.cp]; -} - -static uint64_t -index_cornershtr(Cube cube) -{ - return cube.coud * BINOM8ON4 * 6 + index_cphtr(cube); -} - -static uint64_t -index_cornershtrfin(Cube cube) -{ - return cornershtrfin_ind[cube.cp]; -} - -static uint64_t -index_drud(Cube cube) -{ - uint64_t a, b, c; - - a = cube.eofb; - b = cube.coud; - c = cube.epose / FACTORIAL4; - - b *= POW2TO11; - c *= POW2TO11 * POW3TO7; - - return a + b + c; -} - -static uint64_t -index_drud_eofb(Cube cube) -{ - return index_drud(cube) / POW2TO11; -} - -static uint64_t -index_htr_drud(Cube cube) -{ - return index_cphtr(cube) * BINOM8ON4 + - (cube.eposs / FACTORIAL4) % BINOM8ON4; -} - -static uint64_t -index_htrfin(Cube cube) -{ - uint64_t epe, eps, epm, cp, ep; - - epe = cube.epose % 24; - eps = cube.eposs % 24; - epm = cube.eposm % 24; - ep = (epe * 24 + eps) *24 + epm; - cp = index_cornershtrfin(cube); - - return cp * 24 * 24 * 24 + ep; -} - -/* Init functions implementation *********************************************/ - -/* - * There is certainly a better way to do this, but for now I just use - * a "graph coloring" algorithm to compute the left cosets, and I compose - * with every possible cp to get the right cosets (it is possible that I am - * mixing up left and right). - * - * For doing it better "Mathematically", we need 3 things: - * - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other - * This is easy and it is done in the commented function cphtr_cp(). - * - Check that there is no ep/cp parity - * - Check that we are not in the "3c" case; this is the part I don't - * know how to do. - */ -static void -init_cphtr_cosets() -{ - unsigned int i; - int c = 0, d = 0; - - for (i = 0; i < FACTORIAL8; i++) { - cphtr_left_cosets[i] = -1; - cphtr_right_cosets[i] = -1; - } - - /* First we compute left cosets with a bfs */ - for (i = 0; i < FACTORIAL8; i++) - if (cphtr_left_cosets[i] == -1) - init_cphtr_left_cosets_bfs(i, c++); - - /* Then we compute right cosets using compose() */ - for (i = 0; i < FACTORIAL8; i++) - if (cphtr_right_cosets[i] == -1) - init_cphtr_right_cosets_color(i, d++); -} - -static void -init_cphtr_left_cosets_bfs(int i, int c) -{ - int j, jj, k, next[FACTORIAL8], next2[FACTORIAL8], n, n2; - Move moves[6] = {U2, D2, R2, L2, F2, B2}; - - n = 1; - next[0] = i; - cphtr_left_cosets[i] = c; - - while (n != 0) { - for (j = 0, n2 = 0; j < n; j++) { - for (k = 0; k < 6; k++) { - /*jj = cp_mtable[moves[k]][next[j]];*/ - /* TODO fix formatting */ - jj = apply_move(moves[k], (Cube){.cp=next[j]}).cp; - if (cphtr_left_cosets[jj] == -1) { - cphtr_left_cosets[jj] = c; - next2[n2++] = jj; - } - } - } - - for (j = 0; j < n2; j++) - next[j] = next2[j]; - n = n2; - } -} - -static void -init_cphtr_right_cosets_color(int i, int d) -{ - int cp; - unsigned int j; - - cphtr_right_rep[d] = i; - for (j = 0; j < FACTORIAL8; j++) { - if (cphtr_left_cosets[j] == 0) { - /* TODO: use antindexer, it's nicer */ - cp = compose((Cube){.cp = i}, (Cube){.cp = j}).cp; - cphtr_right_cosets[cp] = d; - } - } -} - -static void -init_cornershtrfin() -{ - unsigned int i, j; - int n, c; - Move m; - - for (i = 0; i < FACTORIAL8; i++) - cornershtrfin_ind[i] = -1; - cornershtrfin_ind[0] = 0; - - /* 10-pass, I think 5 is enough, but just in case */ - n = 1; - for (i = 0; i < 10; i++) { - for (j = 0; j < FACTORIAL8; j++) { - if (cornershtrfin_ind[j] == -1) - continue; - for (m = U; m < NMOVES; m++) { - if (moveset_htr(m)) { - c = apply_move(m, (Cube){.cp = j}).cp; - if (cornershtrfin_ind[c] == -1) { - cornershtrfin_ind[c] = n; - cornershtrfin_ant[n] = c; - n++; - } - } - } - } - } -} - -void -init_coord() -{ - static bool initialized = false; - if (initialized) - return; - initialized = true; - - init_cphtr_cosets(); - init_cornershtrfin(); -} - diff --git a/old/2021-11-10-beforeremovingchecker/coord.h b/old/2021-11-10-beforeremovingchecker/coord.h deleted file mode 100644 index 81c1e9c..0000000 --- a/old/2021-11-10-beforeremovingchecker/coord.h +++ /dev/null @@ -1,40 +0,0 @@ -#ifndef COORD_H -#define COORD_H - -#include "trans.h" - -extern Coordinate coord_eofb; -extern Coordinate coord_eofbepos; -extern Coordinate coord_coud; -extern Coordinate coord_cp; -extern Coordinate coord_cphtr; -extern Coordinate coord_corners; -extern Coordinate coord_cornershtr; -extern Coordinate coord_cornershtrfin; -extern Coordinate coord_epud; -extern Coordinate coord_drud; -extern Coordinate coord_drud_eofb; -extern Coordinate coord_htr_drud; -extern Coordinate coord_htrfin; - -bool check_centers(Cube cube); -bool check_corners(Cube cube); -bool check_cp(Cube cube); -bool check_cphtr(Cube cube); -bool check_cornershtr(Cube cube); -bool check_coud(Cube cube); -bool check_drud(Cube cube); -bool check_htr(Cube cube); -bool check_drudfin_noE(Cube cube); -bool check_eofb(Cube cube); -bool check_eofbepos(Cube cube); -bool check_epose(Cube cube); -bool check_ep(Cube cube); -bool check_epud(Cube cube); -bool check_khuge(Cube cube); -bool check_nothing(Cube cube); - -void init_coord(); - -#endif - diff --git a/old/2021-11-10-beforeremovingchecker/cube.c b/old/2021-11-10-beforeremovingchecker/cube.c deleted file mode 100644 index b621d7b..0000000 --- a/old/2021-11-10-beforeremovingchecker/cube.c +++ /dev/null @@ -1,716 +0,0 @@ -#include "cube.h" - -/* Local functions **********************************************************/ - -static int array_ep_to_epos(int *ep, int *eps_solved); -static int epos_from_arrays(int *epos, int *ep); - -/* Local functions implementation ********************************************/ - -static int -array_ep_to_epos(int *ep, int *ss) -{ - int epos[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - int eps[4]; - int i, j, is; - - for (i = 0, is = 0; i < 12; i++) { - for (j = 0; j < 4; j++) { - if (ep[i] == ss[j]) { - eps[is++] = j; - epos[i] = 1; - } - } - } - - for (i = 0; i < 4; i++) - swap(&epos[ss[i]], &epos[i+8]); - - return epos_from_arrays(epos, eps); -} - -static int -epos_from_arrays(int *epos, int *ep) -{ - return FACTORIAL4 * subset_to_index(epos,12,4) + perm_to_index(ep,4); -} - -/* Public functions implementation *******************************************/ - -Cube -arrays_to_cube(CubeArray *arr, PieceFilter f) -{ - Cube ret = {0}; - - static int epe_solved[4] = {FR, FL, BL, BR}; - static int eps_solved[4] = {UL, UR, DL, DR}; - static int epm_solved[4] = {UF, UB, DF, DB}; - - if (f.epose) - ret.epose = array_ep_to_epos(arr->ep, epe_solved); - if (f.eposs) - ret.eposs = array_ep_to_epos(arr->ep, eps_solved); - if (f.eposm) - ret.eposm = array_ep_to_epos(arr->ep, epm_solved); - if (f.eofb) - ret.eofb = digit_array_to_int(arr->eofb, 11, 2); - if (f.eorl) - ret.eorl = digit_array_to_int(arr->eorl, 11, 2); - if (f.eoud) - ret.eoud = digit_array_to_int(arr->eoud, 11, 2); - if (f.cp) - ret.cp = perm_to_index(arr->cp, 8); - if (f.coud) - ret.coud = digit_array_to_int(arr->coud, 7, 3); - if (f.corl) - ret.corl = digit_array_to_int(arr->corl, 7, 3); - if (f.cofb) - ret.cofb = digit_array_to_int(arr->cofb, 7, 3); - if (f.cpos) - ret.cpos = perm_to_index(arr->cpos, 6); - - return ret; -} - -Cube -compose_filtered(Cube c2, Cube c1, PieceFilter f) -{ - CubeArray *arr = new_cubearray(c2, f); - Cube ret; - - ret = move_via_arrays(arr, c1, f); - free_cubearray(arr, f); - - return ret; -} - -void -cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f) -{ - int i; - - static int epe_solved[4] = {FR, FL, BL, BR}; - static int eps_solved[4] = {UL, UR, DL, DR}; - static int epm_solved[4] = {UF, UB, DF, DB}; - - if (f.epose || f.eposs || f.eposm) - for (i = 0; i < 12; i++) - arr->ep[i] = -1; - - if (f.epose) - epos_to_partial_ep(cube.epose, arr->ep, epe_solved); - if (f.eposs) - epos_to_partial_ep(cube.eposs, arr->ep, eps_solved); - if (f.eposm) - epos_to_partial_ep(cube.eposm, arr->ep, epm_solved); - if (f.eofb) - int_to_sum_zero_array(cube.eofb, 2, 12, arr->eofb); - if (f.eorl) - int_to_sum_zero_array(cube.eorl, 2, 12, arr->eorl); - if (f.eoud) - int_to_sum_zero_array(cube.eoud, 2, 12, arr->eoud); - if (f.cp) - index_to_perm(cube.cp, 8, arr->cp); - if (f.coud) - int_to_sum_zero_array(cube.coud, 3, 8, arr->coud); - if (f.corl) - int_to_sum_zero_array(cube.corl, 3, 8, arr->corl); - if (f.cofb) - int_to_sum_zero_array(cube.cofb, 3, 8, arr->cofb); - if (f.cpos) - index_to_perm(cube.cpos, 6, arr->cpos); -} - -void -epos_to_partial_ep(int epos, int *ep, int *ss) -{ - int i, is, eposs[12], eps[4]; - - index_to_perm(epos % FACTORIAL4, 4, eps); - index_to_subset(epos / FACTORIAL4, 12, 4, eposs); - - for (i = 0; i < 4; i++) - swap(&eposs[ss[i]], &eposs[i+8]); - - for (i = 0, is = 0; i < 12; i++) - if (eposs[i]) - ep[i] = ss[eps[is++]]; -} - -void -free_cubearray(CubeArray *arr, PieceFilter f) -{ - if (f.epose || f.eposs || f.eposm) - free(arr->ep); - if (f.eofb) - free(arr->eofb); - if (f.eorl) - free(arr->eorl); - if (f.eoud) - free(arr->eoud); - if (f.cp) - free(arr->cp); - if (f.coud) - free(arr->coud); - if (f.corl) - free(arr->corl); - if (f.cofb) - free(arr->cofb); - if (f.cpos) - free(arr->cpos); - - free(arr); -} - -Cube -move_via_arrays(CubeArray *arr, Cube c, PieceFilter f) -{ - CubeArray *arrc = new_cubearray(c, f); - Cube ret; - - if (f.epose || f.eposs || f.eposm) - apply_permutation(arr->ep, arrc->ep, 12); - - if (f.eofb) { - apply_permutation(arr->ep, arrc->eofb, 12); - sum_arrays_mod(arr->eofb, arrc->eofb, 12, 2); - } - - if (f.eorl) { - apply_permutation(arr->ep, arrc->eorl, 12); - sum_arrays_mod(arr->eorl, arrc->eorl, 12, 2); - } - - if (f.eoud) { - apply_permutation(arr->ep, arrc->eoud, 12); - sum_arrays_mod(arr->eoud, arrc->eoud, 12, 2); - } - - if (f.cp) - apply_permutation(arr->cp, arrc->cp, 8); - - if (f.coud) { - apply_permutation(arr->cp, arrc->coud, 8); - sum_arrays_mod(arr->coud, arrc->coud, 8, 3); - } - - if (f.corl) { - apply_permutation(arr->cp, arrc->corl, 8); - sum_arrays_mod(arr->corl, arrc->corl, 8, 3); - } - - if (f.cofb) { - apply_permutation(arr->cp, arrc->cofb, 8); - sum_arrays_mod(arr->cofb, arrc->cofb, 8, 3); - } - - if (f.cpos) - apply_permutation(arr->cpos, arrc->cpos, 6); - - ret = arrays_to_cube(arrc, f); - free_cubearray(arrc, f); - - return ret; -} - -CubeArray * -new_cubearray(Cube cube, PieceFilter f) -{ - CubeArray *arr = malloc(sizeof(CubeArray)); - - if (f.epose || f.eposs || f.eposm) - arr->ep = malloc(12 * sizeof(int)); - if (f.eofb) - arr->eofb = malloc(12 * sizeof(int)); - if (f.eorl) - arr->eorl = malloc(12 * sizeof(int)); - if (f.eoud) - arr->eoud = malloc(12 * sizeof(int)); - if (f.cp) - arr->cp = malloc(8 * sizeof(int)); - if (f.coud) - arr->coud = malloc(8 * sizeof(int)); - if (f.corl) - arr->corl = malloc(8 * sizeof(int)); - if (f.cofb) - arr->cofb = malloc(8 * sizeof(int)); - if (f.cpos) - arr->cpos = malloc(6 * sizeof(int)); - - cube_to_arrays(cube, arr, f); - - return arr; -} - - -/* TODO: consider if this is good here or better in coord.c - in any case it is used in transformation init at the moment */ -Cube -admissible_ep(Cube cube, PieceFilter f) -{ - CubeArray *arr = new_cubearray(cube, f); - Cube ret; - bool used[12] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; - int i, j; - - for (i = 0; i < 12; i++) - if (arr->ep[i] != -1) - used[arr->ep[i]] = true; - - for (i = 0, j = 0; i < 12; i++) { - for ( ; j < 11 && used[j]; j++); - if (arr->ep[i] == -1) - arr->ep[i] = j++; - } - - ret = arrays_to_cube(arr, pf_ep); - free_cubearray(arr, f); - - return ret; -} - -Cube -compose(Cube c2, Cube c1) -{ - return compose_filtered(c2, c1, pf_all); -} - -int -edge_slice(Edge e) { - if (e < 0 || e > 11) - return -1; - - if (e == FR || e == FL || e == BL || e == BR) - return 0; - if (e == UR || e == UL || e == DR || e == DL) - return 1; - - return 2; -} - -bool -equal(Cube c1, Cube c2) -{ - return c1.eofb == c2.eofb && - c1.epose == c2.epose && - c1.eposs == c2.eposs && - c1.eposm == c2.eposm && - c1.coud == c2.coud && - c1.cp == c2.cp && - c1.cpos == c2.cpos; -} - -Cube -inverse_cube(Cube cube) -{ - CubeArray *arr = new_cubearray(cube, pf_all); - CubeArray *inv = new_cubearray((Cube){0}, pf_all); - Cube ret; - int i; - - for (i = 0; i < 12; i++) { - inv->ep[arr->ep[i]] = i; - inv->eofb[arr->ep[i]] = arr->eofb[i]; - inv->eorl[arr->ep[i]] = arr->eorl[i]; - inv->eoud[arr->ep[i]] = arr->eoud[i]; - } - - for (i = 0; i < 8; i++) { - inv->cp[arr->cp[i]] = i; - inv->coud[arr->cp[i]] = (3 - arr->coud[i]) % 3; - inv->corl[arr->cp[i]] = (3 - arr->corl[i]) % 3; - inv->cofb[arr->cp[i]] = (3 - arr->cofb[i]) % 3; - } - - for (int i = 0; i < 6; i++) - inv->cpos[arr->cpos[i]] = i; - - ret = arrays_to_cube(inv, pf_all); - free_cubearray(arr, pf_all); - free_cubearray(inv, pf_all); - - return ret; -} - -bool -is_admissible(Cube cube) -{ - /* TODO: this should check consistency of different orientations */ - /* TODO: check that centers are opposite and admissible */ - - CubeArray *a = new_cubearray(cube, pf_all); - int parity; - bool perm; - - perm = is_perm(a->ep, 12) && - is_perm(a->cp, 8) && - is_perm(a->cpos, 6); - parity = perm_sign(a->ep, 12) + - perm_sign(a->cp, 8) + - perm_sign(a->cpos, 6); - - return perm && parity % 2 == 0; -} - -bool -is_solved(Cube cube) -{ - /* TODO: move somewhere else, like in solve.c - int i; - if (reorient) { - for (i = 0; i < NROTATIONS; i++) - if (is_solved(apply_alg(rotation_algs[i], cube),false)) - return true; - return false; - } else { - return equal(cube, (Cube){0}); - } - */ - - return equal(cube, (Cube){0}); -} - -bool -is_solved_block(Cube cube, Block block) -{ - int i; - - for (i = 0; i < 12; i++) - if (block.edge[i] && !is_solved_edge(cube, i)) - return false; - for (i = 0; i < 8; i++) - if (block.corner[i] && !is_solved_corner(cube, i)) - return false; - for (i = 0; i < 6; i++) - if (block.center[i] && !is_solved_center(cube, i)) - return false; - - return true; -} - -bool -is_solved_center(Cube cube, Center c) -{ - return what_center_at(cube, c) == c; -} - -bool -is_solved_corner(Cube cube, Corner c) -{ - return what_corner_at(cube, c) == c && - what_orientation_corner(cube.coud, c); -} - -bool -is_solved_edge(Cube cube, Edge e) -{ - return what_edge_at(cube, e) == e && - what_orientation_edge(cube.eofb, e); -} - -int -piece_orientation(Cube cube, int piece, char *orientation) -{ - int arr[12], n, b, x; - - if (!strcmp(orientation, "eofb")) { - x = cube.eofb; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eorl")) { - x = cube.eorl; - n = 12; - b = 2; - } else if (!strcmp(orientation, "eoud")) { - x = cube.eoud; - n = 12; - b = 2; - } else if (!strcmp(orientation, "coud")) { - x = cube.coud; - n = 8; - b = 3; - } else if (!strcmp(orientation, "corl")) { - x = cube.corl; - n = 8; - b = 3; - } else if (!strcmp(orientation, "cofb")) { - x = cube.cofb; - n = 8; - b = 3; - } else { - return -1; - } - - int_to_sum_zero_array(x, b, n, arr); - if (piece < n) - return arr[piece]; - - return -1; -} - -void -print_cube(Cube cube) -{ - static char edge_string[12][7] = { - [UF] = "UF", [UL] = "UL", [UB] = "UB", [UR] = "UR", - [DF] = "DF", [DL] = "DL", [DB] = "DB", [DR] = "DR", - [FR] = "FR", [FL] = "FL", [BL] = "BL", [BR] = "BR" - }; - - static char corner_string[8][7] = { - [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR", - [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR" - }; - - static char center_string[6][7] = { - [U_center] = "U", [D_center] = "D", - [R_center] = "R", [L_center] = "L", - [F_center] = "F", [B_center] = "B" - }; - - for (int i = 0; i < 12; i++) - printf(" %s ", edge_string[what_edge_at(cube, i)]); - printf("\n"); - - for (int i = 0; i < 12; i++) - printf(" %d ", what_orientation_edge(cube.eofb, i)); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf("%s ", corner_string[what_corner_at(cube, i)]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf(" %d ", what_orientation_corner(cube.coud, i)); - printf("\n"); - - for (int i = 0; i < 6; i++) - printf(" %s ", center_string[what_center_at(cube, i)]); - printf("\n"); -} - -Cube -random_cube() -{ - CubeArray *arr = new_cubearray((Cube){0}, pf_4val); - Cube ret; - int ep, cp, eo, co; - - ep = rand() % FACTORIAL12; - cp = rand() % FACTORIAL8; - eo = rand() % POW2TO11; - co = rand() % POW3TO7; - - index_to_perm(ep, 12, arr->ep); - index_to_perm(cp, 8, arr->cp); - int_to_sum_zero_array(eo, 2, 12, arr->eofb); - int_to_sum_zero_array(co, 3, 8, arr->coud); - - if (perm_sign(arr->ep, 12) != perm_sign(arr->cp, 8)) - swap(&(arr->ep[0]), &(arr->ep[1])); - - ret = arrays_to_cube(arr, pf_4val); - free_cubearray(arr, pf_4val); - - return ret; -} - -Center -what_center_at(Cube cube, Center c) -{ - static bool initialized = false; - static Center aux[FACTORIAL6][6]; - static int i; - static unsigned int ui; - static CubeArray *arr; - - if (!initialized) { - for (ui = 0; ui < FACTORIAL6; ui++) { - arr = new_cubearray((Cube){.cpos = ui}, pf_cpos); - for (i = 0; i < 6; i++) - aux[ui][i] = arr->cpos[i]; - free_cubearray(arr, pf_cpos); - } - - initialized = true; - } - - return aux[cube.cpos][c]; -} - -Corner -what_corner_at(Cube cube, Corner c) -{ - static bool initialized = false; - static Corner aux[FACTORIAL8][8]; - static int i; - static unsigned int ui; - static CubeArray *arr; - - if (!initialized) { - for (ui = 0; ui < FACTORIAL8; ui++) { - arr = new_cubearray((Cube){.cp = ui}, pf_cp); - for (i = 0; i < 8; i++) - aux[ui][i] = arr->cp[i]; - free_cubearray(arr, pf_cp); - } - - initialized = true; - } - - return aux[cube.cp][c]; -} - -Edge -what_edge_at(Cube cube, Edge e) -{ - Edge ret; - CubeArray *arr = new_cubearray(cube, pf_ep); - - ret = arr->ep[e]; - - free_cubearray(arr, pf_ep); - return ret; -} - -int -what_orientation_corner(int co, Corner c) -{ - static bool initialized = false; - static int auxlast[POW3TO7]; - static int auxarr[8]; - static unsigned int ui; - - if (!initialized) { - for (ui = 0; ui < POW3TO7; ui++) { - int_to_sum_zero_array(ui, 3, 8, auxarr); - auxlast[ui] = auxarr[7]; - } - - initialized = true; - } - - if (c < 7) - return (co / powint(3, c)) % 3; - else - return auxlast[co]; -} - -int -what_orientation_edge(int eo, Edge e) -{ - static bool initialized = false; - static int auxlast[POW2TO11]; - static int auxarr[12]; - static unsigned int ui; - - if (!initialized) { - for (ui = 0; ui < POW2TO11; ui++) { - int_to_sum_zero_array(ui, 2, 12, auxarr); - auxlast[ui] = auxarr[11]; - } - - initialized = true; - } - - if (e < 11) - return (eo & (1 << e)) ? 1 : 0; - else - return auxlast[eo]; -} - -Center -where_is_center(Cube cube, Center c) -{ - static bool initialized = false; - static Center aux[FACTORIAL6][6]; - static int i; - static unsigned int ui; - static CubeArray *arr; - - if (!initialized) { - for (ui = 0; ui < FACTORIAL6; ui++) { - arr = new_cubearray((Cube){.cpos = ui}, pf_cpos); - for (i = 0; i < 6; i++) - aux[ui][arr->cpos[i]] = i; - free_cubearray(arr, pf_cpos); - } - - initialized = true; - } - - return aux[cube.cpos][c]; -} - -Corner -where_is_corner(Cube cube, Corner c) -{ - static bool initialized = false; - static Corner aux[FACTORIAL8][8]; - static int i; - static unsigned int ui; - static CubeArray *arr; - - if (!initialized) { - for (ui = 0; ui < FACTORIAL8; ui++) { - arr = new_cubearray((Cube){.cp = ui}, pf_cp); - for (i = 0; i < 8; i++) - aux[ui][arr->cp[i]] = i; - free_cubearray(arr, pf_cp); - } - - initialized = true; - } - return aux[cube.cp][c]; -} - -Edge -where_is_edge(Cube cube, Edge e) -{ - /* TODO: when I wrote this code I forgot to add the final - part, and now I can't remember how it was supposed to - work (i.e. how to recover the location of the edge - from these tables. I think it is either very easy or - wrong, in any case it is not a priority now. - Future Seba can deal with it. - - static bool initialized = false; - static Edge aux[3][FACTORIAL12/FACTORIAL8][12]; - static int i; - static unsigned int ui; - static CubeArray *arr; - - if (!initialized) { - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - arr = new_cubearray((Cube){.epose = ui}, pf_e); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 0) - aux[0][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_e); - - arr = new_cubearray((Cube){.eposs = ui}, pf_s); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 1) - aux[1][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_s); - - arr = new_cubearray((Cube){.eposm = ui}, pf_m); - for (i = 0; i < 12; i++) - if (edge_slice(arr->ep[i]) == 2) - aux[2][ui][arr->ep[i]] = i; - free_cubearray(arr, pf_m); - } - - initialized = true; - } - */ - - int i; - CubeArray *arr = new_cubearray(cube, pf_ep); - - for (i = 0; i < 12; i++) - if ((Edge)arr->ep[i] == e) - return i; - - return -1; -} diff --git a/old/2021-11-10-beforeremovingchecker/cube.h b/old/2021-11-10-beforeremovingchecker/cube.h deleted file mode 100644 index 98657ab..0000000 --- a/old/2021-11-10-beforeremovingchecker/cube.h +++ /dev/null @@ -1,40 +0,0 @@ -#ifndef CUBE_H -#define CUBE_H - -#include -#include - -#include "pf.h" -#include "utils.h" - -Cube admissible_ep(Cube cube, PieceFilter f); /* TODO: move? */ -Cube arrays_to_cube(CubeArray *arr, PieceFilter f); /* TODO: remove */ -Cube compose(Cube c2, Cube c1); /* Use c2 as an alg on c1 */ -Cube compose_filtered(Cube c2, Cube c1, PieceFilter f); -void cube_to_arrays(Cube cube, CubeArray *arr, PieceFilter f); -int edge_slice(Edge e); /* E=0, S=1, M=2 */ -bool equal(Cube c1, Cube c2); -Cube inverse_cube(Cube cube); -bool is_admissible(Cube cube); -bool is_solved(Cube cube); -bool block_solved(Cube cube, Block); /*TODO: rename to is_solved_block()*/ -bool is_solved_center(Cube cube, Center c); -bool is_solved_corner(Cube cube, Corner c); -bool is_solved_edge(Cube cube, Edge e); -void epos_to_partial_ep(int epos, int *ep, int *ss); -void free_cubearray(CubeArray *arr, PieceFilter f); /* TODO: remove */ -Cube move_via_arrays(CubeArray *arr, Cube c, PieceFilter pf); -CubeArray * new_cubearray(Cube cube, PieceFilter f); /* TODO: remove */ -void print_cube(Cube cube); -Cube random_cube(); -Center what_center_at(Cube cube, Center c); -Corner what_corner_at(Cube cube, Corner c); -Edge what_edge_at(Cube cube, Edge e); -int what_orientation_corner(int co, Corner c); -int what_orientation_edge(int eo, Edge e); -Center where_is_center(Cube cube, Center c); -Corner where_is_corner(Cube cube, Corner c); -Edge where_is_edge(Cube cube, Edge e); - -#endif - diff --git a/old/2021-11-10-beforeremovingchecker/cubetypes.h b/old/2021-11-10-beforeremovingchecker/cubetypes.h deleted file mode 100644 index 38a6f8d..0000000 --- a/old/2021-11-10-beforeremovingchecker/cubetypes.h +++ /dev/null @@ -1,298 +0,0 @@ -#ifndef CUBETYPES_H -#define CUBETYPES_H - -#include -#include - -#define NMOVES 55 /* Actually 55, but one is NULLMOVE */ -#define NTRANS 48 -#define NROTATIONS 24 - - -/* Typedefs ******************************************************************/ - -typedef enum center Center; -typedef enum corner Corner; -typedef enum edge Edge; -typedef enum move Move; -typedef enum trans Trans; - -typedef struct alg Alg; -typedef struct alglist AlgList; -typedef struct alglistnode AlgListNode; -typedef struct block Block; -typedef struct command Command; -typedef struct commandargs CommandArgs; -typedef struct coordinate Coordinate; -typedef struct cube Cube; -typedef struct cubearray CubeArray; -typedef struct cubetarget CubeTarget; -typedef struct dfsdata DfsData; -typedef struct piecefilter PieceFilter; -typedef struct prunedata PruneData; -typedef struct solveoptions SolveOptions; -typedef struct step Step; -typedef struct symdata SymData; - -typedef Cube (*AntiIndexer) (uint64_t); -typedef bool (*Checker) (Cube); -typedef int (*Estimator) (CubeTarget); -typedef bool (*Validator) (Alg *); -typedef void (*Exec) (CommandArgs *); -typedef uint64_t (*Indexer) (Cube); -typedef bool (*Moveset) (Move); -typedef CommandArgs * (*ArgParser) (int, char **); -typedef Trans (*TransDetector) (Cube); - - -/* Enums *********************************************************************/ - -enum -center -{ - U_center, D_center, - R_center, L_center, - F_center, B_center -}; - -enum -corner -{ - UFR, UFL, UBL, UBR, - DFR, DFL, DBL, DBR -}; - -enum -edge -{ - UF, UL, UB, UR, - DF, DL, DB, DR, - FR, FL, BL, BR -}; - -enum -move -{ - NULLMOVE, - U, U2, U3, D, D2, D3, - R, R2, R3, L, L2, L3, - F, F2, F3, B, B2, B3, - Uw, Uw2, Uw3, Dw, Dw2, Dw3, - Rw, Rw2, Rw3, Lw, Lw2, Lw3, - Fw, Fw2, Fw3, Bw, Bw2, Bw3, - M, M2, M3, - S, S2, S3, - E, E2, E3, - x, x2, x3, - y, y2, y3, - z, z2, z3, -}; - -enum -trans -{ - uf, ur, ub, ul, - df, dr, db, dl, - rf, rd, rb, ru, - lf, ld, lb, lu, - fu, fr, fd, fl, - bu, br, bd, bl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror, - rf_mirror, rd_mirror, rb_mirror, ru_mirror, - lf_mirror, ld_mirror, lb_mirror, lu_mirror, - fu_mirror, fr_mirror, fd_mirror, fl_mirror, - bu_mirror, br_mirror, bd_mirror, bl_mirror, -}; - - -/* Structs *******************************************************************/ - -struct -alg -{ - Move * move; - bool * inv; - int len; - int allocated; -}; - -struct -alglist -{ - AlgListNode * first; - AlgListNode * last; - int len; -}; - -struct -alglistnode -{ - Alg * alg; - AlgListNode * next; -}; - -struct -block -{ - bool edge[12]; - bool corner[8]; - bool center[6]; -}; - -struct -command -{ - /* TODO: more stuff to add? maybe complete help? */ - /* Maybe add list of options */ - char * name; - char * usage; - char * description; - ArgParser parse_args; - Exec exec; -}; - -struct -commandargs -{ - bool success; - Alg * scramble; - SolveOptions * opts; - Step * step; - Command * command; /* For help */ -}; - -struct -coordinate -{ - Indexer index; - AntiIndexer cube; - Checker check; - uint64_t max; - int ntrans; - Trans * trans; -}; - -struct -cube -{ - int epose; - int eposs; - int eposm; - int eofb; - int eorl; - int eoud; - int cp; - int coud; - int cofb; - int corl; - int cpos; -}; - -struct -cubearray -{ - int * ep; - int * eofb; - int * eorl; - int * eoud; - int * cp; - int * coud; - int * corl; - int * cofb; - int * cpos; -}; - -struct -cubetarget -{ - Cube cube; - int target; -}; - -struct -dfsdata -{ - int d; - int m; - int lb; - bool niss; - Move last1; - Move last2; - AlgList * sols; - Alg * current_alg; - Move sorted_moves[NMOVES]; - int move_position[NMOVES]; -}; - -struct -piecefilter -{ - bool epose; - bool eposs; - bool eposm; - bool eofb; - bool eorl; - bool eoud; - bool cp; - bool coud; - bool cofb; - bool corl; - bool cpos; -}; - -struct -prunedata -{ - char * filename; - uint8_t * ptable; - bool generated; - uint64_t n; - Coordinate * coord; - Moveset moveset; -}; - -struct -solveoptions -{ - /* TODO: add option to list *all* solutions satisfying other - constraints (min/max moves and optimality) */ - int min_moves; - int max_moves; - int max_solutions; - bool optimal_only; - bool can_niss; - bool feedback; /* TODO: rename with "verbose" */ - bool all; - bool print_number; -}; - -struct -step -{ - char * shortname; - char * name; - Estimator estimate; - Checker ready; - char * ready_msg; - Validator is_valid; - Moveset moveset; - Trans pre_trans; - TransDetector detect; -}; - -struct -symdata -{ - char * filename; - bool generated; - Coordinate * coord; - Coordinate * sym_coord; - int ntrans; - Trans * trans; - uint64_t * class; - Cube * rep; - Trans * transtorep; -}; - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/env.c b/old/2021-11-10-beforeremovingchecker/env.c deleted file mode 100644 index d13642f..0000000 --- a/old/2021-11-10-beforeremovingchecker/env.c +++ /dev/null @@ -1,45 +0,0 @@ -#include "env.h" - -bool initialized_env = false; -char *tabledir; - -void -init_env() -{ - char *nissydata = getenv("NISSYDATA"); - char *localdata = getenv("XDG_DATA_HOME"); - char *home = getenv("HOME"); - bool read, write; - - if (initialized_env) - return; - - if (nissydata != NULL) { - tabledir = malloc(strlen(nissydata) * sizeof(char) + 20); - strcpy(tabledir, nissydata); - } else if (localdata != NULL) { - tabledir = malloc(strlen(localdata) * sizeof(char) + 20); - strcpy(tabledir, localdata); - strcat(tabledir, "/nissy"); - } else if (home != NULL) { - tabledir = malloc(strlen(home) * sizeof(char) + 20); - strcpy(tabledir, home); - strcat(tabledir, "/.nissy"); - } - - mkdir(tabledir, 0777); - strcat(tabledir, "/tables"); - mkdir(tabledir, 0777); - - read = !access(tabledir, R_OK); - write = !access(tabledir, W_OK); - - if (!read) { - fprintf(stderr, "Table files cannot be read.\n"); - } else if (!write) { - fprintf(stderr, "Data directory not writable: "); - fprintf(stderr, "tables can be loaded, but not saved.\n"); - } - - initialized_env = true; -} diff --git a/old/2021-11-10-beforeremovingchecker/env.h b/old/2021-11-10-beforeremovingchecker/env.h deleted file mode 100644 index 871a9c1..0000000 --- a/old/2021-11-10-beforeremovingchecker/env.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef ENV_H -#define ENV_H - -#include -#include -#include -#include -#include -#include - -extern char *tabledir; - -void init_env(); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/moves.c b/old/2021-11-10-beforeremovingchecker/moves.c deleted file mode 100644 index 5ba17ca..0000000 --- a/old/2021-11-10-beforeremovingchecker/moves.c +++ /dev/null @@ -1,474 +0,0 @@ -#include "moves.h" - -/* Local functions ***********************************************************/ - -static Cube apply_move_cubearray(Move m, Cube cube, PieceFilter f); -static bool read_mtables_file(); -static bool write_mtables_file(); - -/* Tables and other data *****************************************************/ - -/* Every move is translated to a an alg before filling the - transition tables, see init_moves() */ - -static int edge_cycle[NMOVES][12] = -{ - [U] = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, - [x] = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, - [y] = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL } -}; - -static int corner_cycle[NMOVES][8] = -{ - [U] = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR }, - [x] = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR }, - [y] = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL } -}; - -static int center_cycle[NMOVES][6] = -{ - [x] = { F_center, B_center, R_center, L_center, D_center, U_center }, - [y] = { U_center, D_center, B_center, F_center, R_center, L_center } -}; - -static int eofb_flipped[NMOVES][12] = { - [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, - [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } -}; - -static int eorl_flipped[NMOVES][12] = { - [x] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, - [y] = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 } -}; - -static int eoud_flipped[NMOVES][12] = { - [U] = { [UF] = 1, [UL] = 1, [UB] = 1, [UR] = 1 }, - [x] = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, - [y] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } -}; - -static int coud_flipped[NMOVES][8] = { - [x] = { - [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, - [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 - } -}; - -static int corl_flipped[NMOVES][8] = { - [U] = { [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2 }, - [y] = { - [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, - [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 - } -}; - -static int cofb_flipped[NMOVES][8] = { - [U] = { [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1 }, - [x] = { - [UFR] = 1, [UBR] = 2, [UBL] = 1, [UFL] = 2, - [DFR] = 2, [DBR] = 1, [DBL] = 2, [DFL] = 1 - }, - [y] = { - [UFR] = 2, [UBR] = 1, [UBL] = 2, [UFL] = 1, - [DFR] = 1, [DBR] = 2, [DBL] = 1, [DFL] = 2 - } -}; - -static char equiv_alg_string[100][NMOVES] = { - [NULLMOVE] = "", - - [U] = " U ", - [U2] = " UU ", - [U3] = " UUU ", - [D] = " xx U xx ", - [D2] = " xx UU xx ", - [D3] = " xx UUU xx ", - [R] = " yx U xxxyyy ", - [R2] = " yx UU xxxyyy ", - [R3] = " yx UUU xxxyyy ", - [L] = " yyyx U xxxy ", - [L2] = " yyyx UU xxxy ", - [L3] = " yyyx UUU xxxy ", - [F] = " x U xxx ", - [F2] = " x UU xxx ", - [F3] = " x UUU xxx ", - [B] = " xxx U x ", - [B2] = " xxx UU x ", - [B3] = " xxx UUU x ", - - [Uw] = " xx U xx y ", - [Uw2] = " xx UU xx yy ", - [Uw3] = " xx UUU xx yyy ", - [Dw] = " U yyy ", - [Dw2] = " UU yy ", - [Dw3] = " UUU y ", - [Rw] = " yyyx U xxxy x ", - [Rw2] = " yyyx UU xxxy xx ", - [Rw3] = " yyyx UUU xxxy xxx ", - [Lw] = " yx U xxxyyy xxx ", - [Lw2] = " yx UU xxxyyy xx ", - [Lw3] = " yx UUU xxxyyy x ", - [Fw] = " xxx U x yxxxyyy ", - [Fw2] = " xxx UU x yxxyyy ", - [Fw3] = " xxx UUU x yxyyy ", - [Bw] = " x U xxx yxyyy ", - [Bw2] = " x UU xxx yxxyyy ", - [Bw3] = " x UUU xxx yxxxyyy ", - - [M] = " yx U xx UUU yxyyy ", - [M2] = " yx UU xx UU xxxy ", - [M3] = " yx UUU xx U yxxxy ", - [S] = " x UUU xx U yyyx ", - [S2] = " x UU xx UU yyx ", - [S3] = " x U xx UUU yx ", - [E] = " U xx UUU xxyyy ", - [E2] = " UU xx UU xxyy ", - [E3] = " UUU xx U xxy ", - - [x] = " x ", - [x2] = " xx ", - [x3] = " xxx ", - [y] = " y ", - [y2] = " yy ", - [y3] = " yyy ", - [z] = " yyy x y ", - [z2] = " yy xx ", - [z3] = " y x yyy " -}; - -/* Transition tables, to be loaded up at the beginning */ -static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eofb_mtable[NMOVES][POW2TO11]; -static int eorl_mtable[NMOVES][POW2TO11]; -static int eoud_mtable[NMOVES][POW2TO11]; -static int cp_mtable[NMOVES][FACTORIAL8]; -static int coud_mtable[NMOVES][POW3TO7]; -static int cofb_mtable[NMOVES][POW3TO7]; -static int corl_mtable[NMOVES][POW3TO7]; -static int cpos_mtable[NMOVES][FACTORIAL6]; - - -/* Local functions implementation ********************************************/ - -static Cube -apply_move_cubearray(Move m, Cube cube, PieceFilter f) -{ - /*init_moves();*/ - - CubeArray m_arr = { - edge_cycle[m], - eofb_flipped[m], - eorl_flipped[m], - eoud_flipped[m], - corner_cycle[m], - coud_flipped[m], - corl_flipped[m], - cofb_flipped[m], - center_cycle[m] - }; - - return move_via_arrays(&m_arr, cube, f); -} - -/* Public functions **********************************************************/ - -Cube -apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a) -{ - Cube ret = {0}; - int i; - - for (i = 0; i < alg->len; i++) - if (alg->inv[i]) - ret = a ? apply_move(alg->move[i], ret) : - apply_move_cubearray(alg->move[i], ret, f); - - ret = compose_filtered(c, inverse_cube(ret), f); - - for (i = 0; i < alg->len; i++) - if (!alg->inv[i]) - ret = a ? apply_move(alg->move[i], ret) : - apply_move_cubearray(alg->move[i], ret, f); - - return ret; -} - -Cube -apply_alg(Alg *alg, Cube cube) -{ - return apply_alg_generic(alg, cube, pf_all, true); -} - -Cube -apply_move(Move m, Cube cube) -{ - /*init_moves();*/ - - return (Cube) { - .epose = epose_mtable[m][cube.epose], - .eposs = eposs_mtable[m][cube.eposs], - .eposm = eposm_mtable[m][cube.eposm], - .eofb = eofb_mtable[m][cube.eofb], - .eorl = eorl_mtable[m][cube.eorl], - .eoud = eoud_mtable[m][cube.eoud], - .coud = coud_mtable[m][cube.coud], - .cofb = cofb_mtable[m][cube.cofb], - .corl = corl_mtable[m][cube.corl], - .cp = cp_mtable[m][cube.cp], - .cpos = cpos_mtable[m][cube.cpos] - }; -} - -void -init_moves() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - Cube c; - CubeArray arrs; - int i; - unsigned int ui; - Move m; - Alg *equiv_alg[NMOVES]; - - for (i = 0; i < NMOVES; i++) - equiv_alg[i] = new_alg(equiv_alg_string[i]); - - /* Generate all move cycles and flips; I do this regardless */ - for (i = 0; i < NMOVES; i++) { - if (i == U || i == x || i == y) - continue; - - c = apply_alg_generic(equiv_alg[i], (Cube){0}, pf_all, false); - - arrs = (CubeArray) { - edge_cycle[i], - eofb_flipped[i], - eorl_flipped[i], - eoud_flipped[i], - corner_cycle[i], - coud_flipped[i], - corl_flipped[i], - cofb_flipped[i], - center_cycle[i] - }; - cube_to_arrays(c, &arrs, pf_all); - } - - if (read_mtables_file()) - return; - - fprintf(stderr, "Cannot load %s, generating it\n", "mtables"); - - /* Initialize transition tables */ - for (m = 0; m < NMOVES; m++) { - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - c = (Cube){ .epose = ui }; - c = apply_move_cubearray(m, c, pf_e); - epose_mtable[m][ui] = c.epose; - - c = (Cube){ .eposs = ui }; - c = apply_move_cubearray(m, c, pf_s); - eposs_mtable[m][ui] = c.eposs; - - c = (Cube){ .eposm = ui }; - c = apply_move_cubearray(m, c, pf_m); - eposm_mtable[m][ui] = c.eposm; - } - for (ui = 0; ui < POW2TO11; ui++ ) { - c = (Cube){ .eofb = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eofb_mtable[m][ui] = c.eofb; - - c = (Cube){ .eorl = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eorl_mtable[m][ui] = c.eorl; - - c = (Cube){ .eoud = ui }; - c = apply_move_cubearray(m, c, pf_eo); - eoud_mtable[m][ui] = c.eoud; - } - for (ui = 0; ui < POW3TO7; ui++) { - c = (Cube){ .coud = ui }; - c = apply_move_cubearray(m, c, pf_co); - coud_mtable[m][ui] = c.coud; - - c = (Cube){ .corl = ui }; - c = apply_move_cubearray(m, c, pf_co); - corl_mtable[m][ui] = c.corl; - - c = (Cube){ .cofb = ui }; - c = apply_move_cubearray(m, c, pf_co); - cofb_mtable[m][ui] = c.cofb; - } - for (ui = 0; ui < FACTORIAL8; ui++) { - c = (Cube){ .cp = ui }; - c = apply_move_cubearray(m, c, pf_cp); - cp_mtable[m][ui] = c.cp; - } - for (ui = 0; ui < FACTORIAL6; ui++) { - c = (Cube){ .cpos = ui }; - c = apply_move_cubearray(m, c, pf_cpos); - cpos_mtable[m][ui] = c.cpos; - } - } - - if (!write_mtables_file()) - fprintf(stderr, "Error writing mtables\n"); - - for (i = 0; i < NMOVES; i++) - free_alg(equiv_alg[i]); -} - -static bool -read_mtables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+20]; - int m, b = sizeof(int); - bool r = true; - - /* Table sizes, used for reading and writing files */ - uint64_t me[11] = { - [0] = FACTORIAL12/FACTORIAL8, - [1] = FACTORIAL12/FACTORIAL8, - [2] = FACTORIAL12/FACTORIAL8, - [3] = POW2TO11, - [4] = POW2TO11, - [5] = POW2TO11, - [6] = FACTORIAL8, - [7] = POW3TO7, - [8] = POW3TO7, - [9] = POW3TO7, - [10] = FACTORIAL6 - }; - - strcpy(fname, tabledir); - strcat(fname, "/mtables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - for (m = 0; m < NMOVES; m++) { - r = r && fread(epose_mtable[m], b, me[0], f) == me[0]; - r = r && fread(eposs_mtable[m], b, me[1], f) == me[1]; - r = r && fread(eposm_mtable[m], b, me[2], f) == me[2]; - r = r && fread(eofb_mtable[m], b, me[3], f) == me[3]; - r = r && fread(eorl_mtable[m], b, me[4], f) == me[4]; - r = r && fread(eoud_mtable[m], b, me[5], f) == me[5]; - r = r && fread(cp_mtable[m], b, me[6], f) == me[6]; - r = r && fread(coud_mtable[m], b, me[7], f) == me[7]; - r = r && fread(corl_mtable[m], b, me[8], f) == me[8]; - r = r && fread(cofb_mtable[m], b, me[9], f) == me[9]; - r = r && fread(cpos_mtable[m], b, me[10], f) == me[10]; - } - - fclose(f); - return r; -} - -static bool -write_mtables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+20]; - int m, b = sizeof(int); - bool r = true; - - /* Table sizes, used for reading and writing files */ - uint64_t me[11] = { - [0] = FACTORIAL12/FACTORIAL8, - [1] = FACTORIAL12/FACTORIAL8, - [2] = FACTORIAL12/FACTORIAL8, - [3] = POW2TO11, - [4] = POW2TO11, - [5] = POW2TO11, - [6] = FACTORIAL8, - [7] = POW3TO7, - [8] = POW3TO7, - [9] = POW3TO7, - [10] = FACTORIAL6 - }; - - strcpy(fname, tabledir); - strcat(fname, "/mtables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - for (m = 0; m < NMOVES; m++) { - r = r && fwrite(epose_mtable[m], b, me[0], f) == me[0]; - r = r && fwrite(eposs_mtable[m], b, me[1], f) == me[1]; - r = r && fwrite(eposm_mtable[m], b, me[2], f) == me[2]; - r = r && fwrite(eofb_mtable[m], b, me[3], f) == me[3]; - r = r && fwrite(eorl_mtable[m], b, me[4], f) == me[4]; - r = r && fwrite(eoud_mtable[m], b, me[5], f) == me[5]; - r = r && fwrite(cp_mtable[m], b, me[6], f) == me[6]; - r = r && fwrite(coud_mtable[m], b, me[7], f) == me[7]; - r = r && fwrite(corl_mtable[m], b, me[8], f) == me[8]; - r = r && fwrite(cofb_mtable[m], b, me[9], f) == me[9]; - r = r && fwrite(cpos_mtable[m], b, me[10], f) == me[10]; - } - - fclose(f); - return r; -} - -bool -commute(Move m1, Move m2) -{ - static bool initialized = false; - static bool commute_aux[NMOVES][NMOVES]; - - if (!initialized) { - Cube c1, c2; - int i, j; - - for (i = 0; i < NMOVES; i++) { - for (j = 0; j < NMOVES; j++) { - c1 = apply_move(i, apply_move(j, (Cube){0})); - c2 = apply_move(j, apply_move(i, (Cube){0})); - commute_aux[i][j] = equal(c1, c2) && i && j; - } - } - - initialized = true; - } - - return commute_aux[m1][m2]; -} - -bool -possible_next(Move m1, Move m2, Move m3) -{ - static bool initialized = false; - static bool paux[NMOVES][NMOVES][NMOVES]; - - if (!initialized) { - int i, j, k; - bool p, q, c; - - for (i = 0; i < NMOVES; i++) { - for (j = 0; j < NMOVES; j++) { - for (k = 0; k < NMOVES; k++) { - p = j && base_move(j) == base_move(k); - q = i && base_move(i) == base_move(k); - c = commute(i, j); - paux[i][j][k] = !(p || (c && q)); - } - } - } - - initialized = true; - } - - return paux[m1][m2][m3]; -} diff --git a/old/2021-11-10-beforeremovingchecker/moves.h b/old/2021-11-10-beforeremovingchecker/moves.h deleted file mode 100644 index 082a080..0000000 --- a/old/2021-11-10-beforeremovingchecker/moves.h +++ /dev/null @@ -1,16 +0,0 @@ -#ifndef MOVES_H -#define MOVES_H - -#include "alg.h" -#include "cube.h" -#include "env.h" - -Cube apply_alg(Alg *alg, Cube cube); -Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a); -Cube apply_move(Move m, Cube cube); -bool commute(Move m1, Move m2); -bool possible_next(Move m1, Move m2, Move m3); - -void init_moves(); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/pf.c b/old/2021-11-10-beforeremovingchecker/pf.c deleted file mode 100644 index 34be4fd..0000000 --- a/old/2021-11-10-beforeremovingchecker/pf.c +++ /dev/null @@ -1,80 +0,0 @@ -#include "pf.h" - -PieceFilter -pf_all = { - .epose = true, - .eposs = true, - .eposm = true, - .eofb = true, - .eorl = true, - .eoud = true, - .cp = true, - .cofb = true, - .corl = true, - .coud = true, - .cpos = true -}; - -PieceFilter -pf_4val = { - .epose = true, - .eposs = true, - .eposm = true, - .eofb = true, - .coud = true, - .cp = true -}; - -PieceFilter -pf_epcp = { - .epose = true, - .eposs = true, - .eposm = true, - .cp = true -}; - -PieceFilter -pf_cpos = { - .cpos = true -}; - -PieceFilter -pf_cp = { - .cp = true -}; - -PieceFilter -pf_ep = { - .epose = true, - .eposs = true, - .eposm = true -}; - -PieceFilter -pf_e = { - .epose = true -}; - -PieceFilter -pf_s = { - .eposs = true -}; - -PieceFilter -pf_m = { - .eposm = true -}; - -PieceFilter -pf_eo = { - .eofb = true, - .eorl = true, - .eoud = true -}; - -PieceFilter -pf_co = { - .cofb = true, - .corl = true, - .coud = true -}; diff --git a/old/2021-11-10-beforeremovingchecker/pf.h b/old/2021-11-10-beforeremovingchecker/pf.h deleted file mode 100644 index 85ee1eb..0000000 --- a/old/2021-11-10-beforeremovingchecker/pf.h +++ /dev/null @@ -1,18 +0,0 @@ -#ifndef PF_H -#define PF_H - -#include "cubetypes.h" - -extern PieceFilter pf_all; -extern PieceFilter pf_4val; -extern PieceFilter pf_epcp; -extern PieceFilter pf_cpos; -extern PieceFilter pf_cp; -extern PieceFilter pf_ep; -extern PieceFilter pf_e; -extern PieceFilter pf_s; -extern PieceFilter pf_m; -extern PieceFilter pf_eo; -extern PieceFilter pf_co; - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/pruning.c b/old/2021-11-10-beforeremovingchecker/pruning.c deleted file mode 100644 index 86363f4..0000000 --- a/old/2021-11-10-beforeremovingchecker/pruning.c +++ /dev/null @@ -1,272 +0,0 @@ -#include "pruning.h" - -static void genptable_bfs(PruneData *pd, int d, Move *ms); -static void genptable_branch(PruneData *pd, uint64_t i, int d, Move *m); -static void ptable_update(PruneData *pd, Cube cube, int m); -static void ptable_update_index(PruneData *pd, uint64_t ind, int m); -static int ptableval_index(PruneData *pd, uint64_t ind); -static bool read_ptable_file(PruneData *pd); -static bool write_ptable_file(PruneData *pd); - -PruneData -pd_eofb_HTM = { - .filename = "pt_eofb_HTM", - .coord = &coord_eofb, - .moveset = moveset_HTM, -}; - -PruneData -pd_coud_HTM = { - .filename = "pt_coud_HTM", - .coord = &coord_coud, - .moveset = moveset_HTM, -}; - -PruneData -pd_cornershtr_HTM = { - .filename = "pt_cornershtr_withcosets_HTM", - .coord = &coord_cornershtr, - .moveset = moveset_HTM, -}; - -PruneData -pd_corners_HTM = { - .filename = "pt_corners_HTM", - .coord = &coord_corners, - .moveset = moveset_HTM, -}; - -PruneData -pd_drud_sym16_HTM = { - .filename = "pt_drud_sym16_HTM", - .coord = &coord_drud_sym16, - .moveset = moveset_HTM, -}; - -PruneData -pd_drud_eofb = { - .filename = "pt_drud_eofb", - .coord = &coord_drud_eofb, - .moveset = moveset_eofb, -}; - -PruneData -pd_drudfin_noE_sym16_drud = { - .filename = "pt_drudfin_noE_sym16_drud", - .coord = &coord_drudfin_noE_sym16, - .moveset = moveset_drud, -}; - -PruneData -pd_htr_drud = { - .filename = "pt_htr_drud", - .coord = &coord_htr_drud, - .moveset = moveset_drud, -}; - -PruneData -pd_htrfin_htr = { - .filename = "pt_htrfin_htr", - .coord = &coord_htrfin, - .moveset = moveset_htr, -}; - -PruneData -pd_khuge_HTM = { - .filename = "pt_khuge_HTM", - .coord = &coord_khuge, - .moveset = moveset_HTM, -}; - -void -genptable(PruneData *pd) -{ - Move ms[NMOVES]; - int d; - uint64_t j, oldn; - - if (pd->generated) - return; - - /* TODO: check if memory is enough, otherwise maybe exit gracefully? */ - pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t)); - - if (read_ptable_file(pd)) { - pd->generated = true; - return; - } - pd->generated = true; - - fprintf(stderr, "Cannot load %s, generating it\n", pd->filename); - - moveset_to_list(pd->moveset, ms); - - /* We use 4 bits per value, so any distance >= 15 is set to 15 */ - for (j = 0; j < pd->coord->max; j++) - ptable_update_index(pd, j, 15); - - for (j = 0; j < pd->coord->max; j++) - if (ptableval_index(pd, j) != 15) { - printf("Error, non-max value at index %lu!\n", j); - break; - } - printf("Table set, ready to start\n"); - - /*TODO: change, set to 0 for every solved state (might be more than 1)*/ - ptable_update(pd, (Cube){0}, 0); - pd->n = 1; - oldn = 0; - fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n", - 0, pd->n - oldn, pd->n, pd->coord->max); - oldn = 1; - for (d = 0; d < 15 && pd->n < pd->coord->max; d++) { - genptable_bfs(pd, d, ms); - fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n", - d+1, pd->n - oldn, pd->n, pd->coord->max); - oldn = pd->n; - } - - if (!write_ptable_file(pd)) - fprintf(stderr, "Error writing ptable file\n"); -} - -static void -genptable_bfs(PruneData *pd, int d, Move *ms) -{ - uint64_t i; - - for (i = 0; i < pd->coord->max; i++) - if (ptableval_index(pd, i) == d) - genptable_branch(pd, i, d, ms); -} - -static void -genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms) -{ - int i, j; - Cube ci, cc, c; - - /* - * This is the only line of the whole program where we REALLY need an - * anti-indexer function. We could get rid of it if only we could save - * a cube object for each index value as we go, but then we would need - * an incredible amount of memory to generate each ptable: assuming - * fields in struct cube are 32 bit ints that would take 88 times the - * memory of the table to be generated, more than 120Gb for - * ptable_khuge for example! - */ - ci = pd->coord->cube(ind); - - for (i = 0; i < pd->coord->ntrans; i++) { - /* For simplicity trans[] is NULL when ntrans = 1 */ - c = i == 0 ? ci : - apply_trans(pd->coord->trans[i], ci); - for (j = 0; ms[j] != NULLMOVE; j++) { - cc = apply_move(ms[j], c); - if (ptableval(pd, cc) > d+1) - ptable_update(pd, cc, d+1); - } - } -} - -void -print_ptable(PruneData *pd) -{ - uint64_t i, a[16]; - - for (i = 0; i < 16; i++) - a[i] = 0; - - if (!pd->generated) - genptable(pd); - - for (i = 0; i < pd->coord->max; i++) - a[ptableval_index(pd, i)]++; - - fprintf(stderr, "Values for table %s\n", pd->filename); - for (i = 0; i < 16; i++) - printf("%2lu\t%10lu\n", i, a[i]); -} - -uint64_t -ptablesize(PruneData *pd) -{ - return (pd->coord->max + 1) / 2; -} - -static void -ptable_update(PruneData *pd, Cube cube, int n) -{ - uint64_t ind = pd->coord->index(cube); - ptable_update_index(pd, ind, n); -} - -static void -ptable_update_index(PruneData *pd, uint64_t ind, int n) -{ - uint8_t oldval2 = pd->ptable[ind/2]; - int other = (ind % 2) ? oldval2 % 16 : oldval2 / 16; - - pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n; - pd->n++; -} - -int -ptableval(PruneData *pd, Cube cube) -{ - return ptableval_index(pd, pd->coord->index(cube)); -} - -static int -ptableval_index(PruneData *pd, uint64_t ind) -{ - if (!pd->generated) - genptable(pd); - - return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16; -} - -static bool -read_ptable_file(PruneData *pd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t r; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, pd->filename); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); - fclose(f); - - return r == ptablesize(pd); -} - -static bool -write_ptable_file(PruneData *pd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t written; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, pd->filename); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); - fclose(f); - - return written == ptablesize(pd); -} - diff --git a/old/2021-11-10-beforeremovingchecker/pruning.h b/old/2021-11-10-beforeremovingchecker/pruning.h deleted file mode 100644 index 631ee3a..0000000 --- a/old/2021-11-10-beforeremovingchecker/pruning.h +++ /dev/null @@ -1,23 +0,0 @@ -#ifndef PRUNING_H -#define PRUNING_H - -#include "symcoord.h" - -extern PruneData pd_eofb_HTM; -extern PruneData pd_coud_HTM; -extern PruneData pd_corners_HTM; -extern PruneData pd_cornershtr_HTM; -extern PruneData pd_drud_sym16_HTM; -extern PruneData pd_drud_eofb; -extern PruneData pd_drudfin_noE_sym16_drud; -extern PruneData pd_htr_drud; -extern PruneData pd_htrfin_htr; -extern PruneData pd_khuge_HTM; - -void genptable(PruneData *pd); -void print_ptable(PruneData *pd); -uint64_t ptablesize(PruneData *pd); -int ptableval(PruneData *pd, Cube cube); - -#endif - diff --git a/old/2021-11-10-beforeremovingchecker/shell.c b/old/2021-11-10-beforeremovingchecker/shell.c deleted file mode 100644 index e591faa..0000000 --- a/old/2021-11-10-beforeremovingchecker/shell.c +++ /dev/null @@ -1,99 +0,0 @@ -#include "shell.h" - -static void cleanwhitespaces(char *line); -static int parseline(char *line, char **v); - -static void -cleanwhitespaces(char *line) -{ - char *i; - - for (i = line; *i != 0; i++) - if (*i == '\t' || *i == '\n') - *i = ' '; -} - -/* This function assumes that **v is large enough */ -static int -parseline(char *line, char **v) -{ - char *t; - int n = 0; - - cleanwhitespaces(line); - - for (t = strtok(line, " "); t != NULL; t = strtok(NULL, " ")) - strcpy(v[n++], t); - - return n; -} - -void -exec_args(int c, char **v) -{ - int i; - Command *cmd = NULL; - CommandArgs *args; - - for (i = 0; i < NCOMMANDS; i++) - if (commands[i] != NULL && !strcmp(v[0], commands[i]->name)) - cmd = commands[i]; - - if (cmd == NULL) { - fprintf(stderr, "%s: command not found\n", v[0]); - return; - } - - args = cmd->parse_args(c-1, &v[1]); - if (!args->success) { - fprintf(stderr, "usage: %s\n", cmd->usage); - return; - } - - cmd->exec(args); - free_args(args); -} - -void -launch() -{ - int i, shell_argc; - char line[MAXLINELEN], **shell_argv; - - shell_argv = malloc(MAXNTOKENS * sizeof(char *)); - for (i = 0; i < MAXNTOKENS; i++) - shell_argv[i] = malloc((MAXTOKENLEN+1) * sizeof(char)); - - fprintf(stderr, "Welcome to Nissy 2.0 (demo version).\n"); - fprintf(stderr, "Limited commands available. "); - fprintf(stderr, "Type 'help' for a list.\n"); - - while (true) { - fprintf(stderr, "nissy-# "); - if (fgets(line, MAXLINELEN, stdin) == NULL) - break; - shell_argc = parseline(line, shell_argv); - exec_args(shell_argc, shell_argv); - } - - for (i = 0; i < MAXNTOKENS; i++) - free(shell_argv[i]); - free(shell_argv); -} - -/* We will have our main() here, for now */ -int -main(int argc, char *argv[]) -{ - init_moves(); - init_trans(); - init_coord(); - init_symcoord(); - - if (argc > 1) - exec_args(argc-1, &argv[1]); - else - launch(); - - return 0; -} diff --git a/old/2021-11-10-beforeremovingchecker/shell.h b/old/2021-11-10-beforeremovingchecker/shell.h deleted file mode 100644 index a72d136..0000000 --- a/old/2021-11-10-beforeremovingchecker/shell.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef SHELL_H -#define SHELL_H - -#include "commands.h" - -#define MAXLINELEN 10000 -#define MAXTOKENLEN 255 -#define MAXNTOKENS 255 - -void exec_args(int c, char **v); -void launch(); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/solve.c b/old/2021-11-10-beforeremovingchecker/solve.c deleted file mode 100644 index af685ec..0000000 --- a/old/2021-11-10-beforeremovingchecker/solve.c +++ /dev/null @@ -1,209 +0,0 @@ -#include "solve.h" - -/* Local functions ***********************************************************/ - -static bool allowed_next(Move move, DfsData *dd); -static void dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd); -static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd); -static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd); -static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd); -static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd); - -/* Local functions ***********************************************************/ - -static bool -allowed_next(Move move, DfsData *dd) -{ - -/* TODO: remove the commented part, was added to moves.c - static bool initialized = false; - static bool commute[NMOVES][NMOVES], pnext[NMOVES][NMOVES][NMOVES]; - - if (!initialized) { - Cube c1, c2; - int i, j, k; - bool p1, p2, cij; - - for (i = 0; i < NMOVES; i++) { - for (j = 0; j < NMOVES; j++) { - c1 = apply_move(i, apply_move(j, (Cube){0})); - c2 = apply_move(j, apply_move(i, (Cube){0})); - commute[i][j] = equal(c1, c2) && i && j; - for (k = 0; k < NMOVES; k++) { - p1 = j && base_move(j) == base_move(k); - p2 = i && base_move(i) == base_move(k); - cij = commute[i][j]; - pnext[i][j][k] = !(p1 || (cij && p2)); - } - } - } - - initialized = true; - } - - if (!pnext[dd->last2][dd->last1][move]) - return false; - - if (commute[dd->last1][move]) - return dd->move_position[dd->last1] < dd->move_position[move]; - - return true; -*/ - - if (!possible_next(dd->last2, dd->last1, move)) - return false; - - if (commute(dd->last1, move)) - return dd->move_position[dd->last1] < dd->move_position[move]; - - return true; -} - -static void -dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd) -{ - if (dfs_stop(c, s, opts, dd)) - return; - - if (dfs_check_solved(s, opts, dd)) - return; - - dfs_branch(c, s, opts, dd); - - if (opts->can_niss && !dd->niss) - dfs_niss(c, s, opts, dd); -} - -static void -dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd) -{ - Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves; - - int i, maxnsol = opts->max_solutions; - - for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) { - m = moves[i]; - if (allowed_next(m, dd)) { - dd->last2 = dd->last1; - dd->last1 = m; - append_move(dd->current_alg, m, dd->niss); - - dfs(apply_move(m, c), s, opts, dd); - - dd->current_alg->len--; - dd->last2 = l2; - dd->last1 = l1; - } - } -} - -static bool -dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd) -{ - if (dd->lb != 0) - return false; - - if (dd->current_alg->len == dd->d) { - if (s->is_valid(dd->current_alg) || opts->all) - append_alg(dd->sols, dd->current_alg); - - if (opts->feedback) - print_alg(dd->current_alg, false); - } - - return true; -} - -static void -dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd) -{ - Move l1 = dd->last1, l2 = dd->last2; - CubeTarget ct; - - ct.cube = apply_move(inverse_move(l1), (Cube){0}); - ct.target = 1; - - if (dd->current_alg->len == 0 || s->estimate(ct)) { - dd->niss = true; - dd->last1 = NULLMOVE; - dd->last2 = NULLMOVE; - - dfs(inverse_cube(c), s, opts, dd); - - dd->last1 = l1; - dd->last2 = l2; - dd->niss = false; - } -} - -static bool -dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) -{ - CubeTarget ct = { - .cube = c, - .target = dd->d - dd->current_alg->len - }; - - if (dd->sols->len >= opts->max_solutions) - return true; - - dd->lb = s->estimate(ct); - if (opts->can_niss && !dd->niss) - dd->lb = MIN(1, dd->lb); - - if (dd->current_alg->len + dd->lb > dd->d) - return true; - - return false; -} - -/* Public functions **********************************************************/ - -AlgList * -solve(Cube cube, Step *step, SolveOptions *opts) -{ - AlgListNode *node; - AlgList *sols = new_alglist(); - Cube c; - - if (step->detect != NULL) - step->pre_trans = step->detect(cube); - c = apply_trans(step->pre_trans, cube); - - DfsData dd = { - .m = 0, - .niss = false, - .lb = -1, - .last1 = NULLMOVE, - .last2 = NULLMOVE, - .sols = sols, - .current_alg = new_alg("") - }; - - if (step->ready != NULL && !step->ready(c)) { - fprintf(stderr, "Cube not ready for solving step: "); - fprintf(stderr, "%s\n", step->ready_msg); - return sols; - } - - moveset_to_list(step->moveset, dd.sorted_moves); - movelist_to_position(dd.sorted_moves, dd.move_position); - - for (dd.d = opts->min_moves; - dd.d <= opts->max_moves && - !(sols->len && opts->optimal_only) && - sols->len < opts->max_solutions; - dd.d++) { - if (opts->feedback) - fprintf(stderr, - "Found %d solutions, searching depth %d...\n", - sols->len, dd.d); - dfs(c, step, opts, &dd); - } - - for (node = sols->first; node != NULL; node = node->next) - transform_alg(inverse_trans(step->pre_trans), node->alg); - - free_alg(dd.current_alg); - return sols; -} diff --git a/old/2021-11-10-beforeremovingchecker/solve.h b/old/2021-11-10-beforeremovingchecker/solve.h deleted file mode 100644 index ff84e7e..0000000 --- a/old/2021-11-10-beforeremovingchecker/solve.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef SOLVE_H -#define SOLVE_H - -#include "moves.h" -#include "trans.h" - -AlgList * solve(Cube cube, Step *step, SolveOptions *opts); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/steps.c b/old/2021-11-10-beforeremovingchecker/steps.c deleted file mode 100644 index 7213766..0000000 --- a/old/2021-11-10-beforeremovingchecker/steps.c +++ /dev/null @@ -1,916 +0,0 @@ -#include "steps.h" - -/* Standard checkers (return lower bound) ************************************/ - -static int estimate_eoany_HTM(CubeTarget ct); -static int estimate_eofb_HTM(CubeTarget ct); -static int estimate_coany_HTM(CubeTarget ct); -static int estimate_coud_HTM(CubeTarget ct); -static int estimate_coany_URF(CubeTarget ct); -static int estimate_coud_URF(CubeTarget ct); -static int estimate_corners_HTM(CubeTarget ct); -static int estimate_cornershtr_HTM(CubeTarget ct); -static int estimate_corners_URF(CubeTarget ct); -static int estimate_cornershtr_URF(CubeTarget ct); -static int estimate_drany_HTM(CubeTarget ct); -static int estimate_drud_HTM(CubeTarget ct); -static int estimate_drud_eofb(CubeTarget ct); -static int estimate_dr_eofb(CubeTarget ct); -static int estimate_drudfin_drud(CubeTarget ct); -static int estimate_htr_drud(CubeTarget ct); -static int estimate_htrfin_htr(CubeTarget ct); -static int estimate_optimal_HTM(CubeTarget ct); - -/* Validators ****************************************************************/ - -static bool always_valid(Alg *alg); -static bool validate_singlecw_ending(Alg *alg); - -/* Pre-transformation detectors **********************************************/ - -static Trans detect_pretrans_eofb(Cube cube); -static Trans detect_pretrans_drud(Cube cube); - -/* Messages for when cube is not ready ***************************************/ - -static char check_centers_msg[100] = "cube must be oriented (centers solved)"; -static char check_eo_msg[100] = "EO must be solved on given axis"; -static char check_dr_msg[100] = "DR must be solved on given axis"; -static char check_htr_msg[100] = "HTR must be solved"; -static char check_drany_msg[100] = "DR must be solved on at least one axis"; - -/* Steps *********************************************************************/ - -Step -optimal_HTM = { - .shortname = "optimal", - .name = "Optimal solve (in HTM)", - - .estimate = estimate_optimal_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = always_valid, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -/* EO steps **************************/ -Step -eoany_HTM = { - .shortname = "eo", - .name = "EO on any axis", - - .estimate = estimate_eoany_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -eofb_HTM = { - .shortname = "eofb", - .name = "EO on F/B", - - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -eorl_HTM = { - .shortname = "eorl", - .name = "EO on R/L", - - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = ur, -}; - -Step -eoud_HTM = { - .shortname = "eoud", - .name = "EO on U/D", - - .estimate = estimate_eofb_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = fd, -}; - -/* CO steps **************************/ -Step -coany_HTM = { - .shortname = "co", - .name = "CO on any axis", - - .estimate = estimate_coany_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -coud_HTM = { - .shortname = "coud", - .name = "CO on U/D", - - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -corl_HTM = { - .shortname = "corl", - .name = "CO on R/L", - - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = rf, -}; - -Step -cofb_HTM = { - .shortname = "cofb", - .name = "CO on F/B", - - .estimate = estimate_coud_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = fd, -}; - -Step -coany_URF = { - .shortname = "co-URF", - .name = "CO any axis (URF moveset)", - - .estimate = estimate_coany_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, - - .pre_trans = uf, -}; - -Step -coud_URF = { - .shortname = "coud-URF", - .name = "CO on U/D (URF moveset)", - - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, - - .pre_trans = uf, -}; - -Step -corl_URF = { - .shortname = "corl-URF", - .name = "CO on R/L (URF moveset)", - - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, - - .pre_trans = rf, -}; - -Step -cofb_URF = { - .shortname = "cofb-URF", - .name = "CO on F/B (URF moveset)", - - .estimate = estimate_coud_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, - - .pre_trans = fd, -}; - -/* Misc corner steps *****************/ -Step -cornershtr_HTM = { - .shortname = "chtr", - .name = "Solve corners to HTR state", - - .estimate = estimate_cornershtr_HTM, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -cornershtr_URF = { - .shortname = "chtr-URF", - .name = "Solve corners to HTR state (URF moveset)", - - .estimate = estimate_cornershtr_URF, - .ready = NULL, - .is_valid = validate_singlecw_ending, - .moveset = moveset_URF, - - .pre_trans = uf, -}; - -Step -corners_HTM = { - .shortname = "corners", - .name = "Solve corners", - - .estimate = estimate_corners_HTM, - .ready = NULL, - .is_valid = always_valid, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -corners_URF = { - .shortname = "corners-URF", - .name = "Solve corners (URF moveset)", - - .estimate = estimate_corners_URF, - .ready = NULL, - .is_valid = always_valid, - .moveset = moveset_URF, - - .pre_trans = uf, -}; - -/* DR steps **************************/ -Step -drany_HTM = { - .shortname = "dr", - .name = "DR on any axis", - - .estimate = estimate_drany_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -drud_HTM = { - .shortname = "drud", - .name = "DR on U/D", - - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = uf, -}; - -Step -drrl_HTM = { - .shortname = "drrl", - .name = "DR on R/L", - - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = rf, -}; - -Step -drfb_HTM = { - .shortname = "drfb", - .name = "DR on F/B", - - .estimate = estimate_drud_HTM, - .ready = check_centers, - .ready_msg = check_centers_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_HTM, - - .pre_trans = fd, -}; - -/* DR from EO */ -Step -dr_eo = { - .shortname = "dr-eo", - .name = "DR without breaking EO (automatically detected)", - - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .detect = detect_pretrans_eofb, -}; - -Step -dr_eofb = { - .shortname = "dr-eofb", - .name = "DR on U/D or R/L without breaking EO on F/B", - - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = uf, -}; - -Step -dr_eorl = { - .shortname = "dr-eorl", - .name = "DR on U/D or F/B without breaking EO on R/L", - - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = ur, -}; - -Step -dr_eoud = { - .shortname = "dr-eoud", - .name = "DR on R/L or F/B without breaking EO on U/R", - - .estimate = estimate_dr_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = fd, -}; - -Step -drud_eofb = { - .shortname = "drud-eofb", - .name = "DR on U/D without breaking EO on F/B", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = uf, -}; - -Step -drrl_eofb = { - .shortname = "drrl-eofb", - .name = "DR on R/L without breaking EO on F/B", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = rf, -}; - -Step -drud_eorl = { - .shortname = "drud-eorl", - .name = "DR on U/D without breaking EO on R/L", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = ur, -}; - -Step -drfb_eorl = { - .shortname = "drfb-eorl", - .name = "DR on F/B without breaking EO on R/L", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = fr, -}; - -Step -drfb_eoud = { - .shortname = "drfb-eoud", - .name = "DR on F/B without breaking EO on U/D", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = fd, -}; - -Step -drrl_eoud = { - .shortname = "drrl-eoud", - .name = "DR on R/L without breaking EO on U/D", - - .estimate = estimate_drud_eofb, - .ready = check_eofb, - .ready_msg = check_eo_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_eofb, - - .pre_trans = rd, -}; - -/* DR finish steps */ -Step -dranyfin_DR = { - .shortname = "drfin", - .name = "DR finish on any axis without breaking DR", - - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_drany_msg, - .is_valid = always_valid, - .moveset = moveset_drud, - - .detect = detect_pretrans_drud, -}; - -Step -drudfin_drud = { - .shortname = "drudfin", - .name = "DR finish on U/D without breaking DR", - - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = moveset_drud, - - .pre_trans = uf, -}; - -Step -drrlfin_drrl = { - .shortname = "drrlfin", - .name = "DR finish on R/L without breaking DR", - - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = moveset_drud, - - .pre_trans = rf, -}; - -Step -drfbfin_drfb = { - .shortname = "drfbfin", - .name = "DR finish on F/B without breaking DR", - - .estimate = estimate_drudfin_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = always_valid, - .moveset = moveset_drud, - - .pre_trans = fd, -}; - -/* HTR from DR */ -Step -htr_any = { - .shortname = "htr", - .name = "HTR from DR", - - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_drany_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, - - .detect = detect_pretrans_drud, -}; - -Step -htr_drud = { - .shortname = "htr-drud", - .name = "HTR from DR on U/D", - - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, - - .pre_trans = uf, -}; - -Step -htr_drrl = { - .shortname = "htr-drrl", - .name = "HTR from DR on R/L", - - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, - - .pre_trans = rf, -}; - -Step -htr_drfb = { - .shortname = "htr-drfb", - .name = "HTR from DR on F/B", - - .estimate = estimate_htr_drud, - .ready = check_drud, - .ready_msg = check_dr_msg, - .is_valid = validate_singlecw_ending, - .moveset = moveset_drud, - - .pre_trans = fd, -}; - -/* HTR finish */ -Step -htrfin_htr = { - .shortname = "htrfin", - .name = "HTR finish without breaking HTR", - - .estimate = estimate_htrfin_htr, - .ready = check_htr, - .ready_msg = check_htr_msg, - .is_valid = always_valid, - .moveset = moveset_htr, - - .pre_trans = uf, -}; - -Step *steps[NSTEPS] = { - &optimal_HTM, /* first is default */ - - &eoany_HTM, - &eofb_HTM, - &eorl_HTM, - &eoud_HTM, - - &coany_HTM, - &coud_HTM, - &corl_HTM, - &cofb_HTM, - - &coany_URF, - &coud_URF, - &corl_URF, - &cofb_URF, - - &drany_HTM, - &drud_HTM, - &drrl_HTM, - &drfb_HTM, - - &dr_eo, - &dr_eofb, - &dr_eorl, - &dr_eoud, - &drud_eofb, - &drrl_eofb, - &drud_eorl, - &drfb_eorl, - &drfb_eoud, - &drrl_eoud, - - &dranyfin_DR, - &drudfin_drud, - &drrlfin_drrl, - &drfbfin_drfb, - - &htr_any, - &htr_drud, - &htr_drrl, - &htr_drfb, - - &htrfin_htr, - - &cornershtr_HTM, - &cornershtr_URF, - &corners_HTM, - &corners_URF, -}; - -/* Standard checkers (return lower bound) ************************************/ - -static int -estimate_eoany_HTM(CubeTarget ct) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_eofb_HTM, ct.cube); - r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, ct.cube)); - r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, ct.cube)); - - return MIN(r1, MIN(r2, r3)); -} - -static int -estimate_eofb_HTM(CubeTarget ct) -{ - return ptableval(&pd_eofb_HTM, ct.cube); -} - -static int -estimate_coany_HTM(CubeTarget ct) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_coud_HTM, ct.cube); - r2 = ptableval(&pd_coud_HTM, apply_trans(rf, ct.cube)); - r3 = ptableval(&pd_coud_HTM, apply_trans(fd, ct.cube)); - - return MIN(r1, MIN(r2, r3)); -} - -static int -estimate_coud_HTM(CubeTarget ct) -{ - return ptableval(&pd_coud_HTM, ct.cube); -} - -static int -estimate_coany_URF(CubeTarget ct) -{ - int r1, r2, r3; - CubeTarget ct2, ct3; - - ct2.cube = apply_trans(rf, ct.cube); - ct2.target = ct.target; - - ct3.cube = apply_trans(fd, ct.cube); - ct3.target = ct.target; - - r1 = estimate_coud_URF(ct); - r2 = estimate_coud_URF(ct2); - r3 = estimate_coud_URF(ct3); - - return MIN(r1, MIN(r2, r3)); -} - -static int -estimate_coud_URF(CubeTarget ct) -{ - /* TODO: I can improve this by checking first the orientation of - * the corner in DBL and use that as a reference */ - - CubeTarget ct2 = {.cube = apply_move(z, ct.cube), .target = ct.target}; - CubeTarget ct3 = {.cube = apply_move(x, ct.cube), .target = ct.target}; - - int ud = estimate_coud_HTM(ct); - int rl = estimate_coud_HTM(ct2); - int fb = estimate_coud_HTM(ct3); - - return MIN(ud, MIN(rl, fb)); -} - -static int -estimate_corners_HTM(CubeTarget ct) -{ - return ptableval(&pd_corners_HTM, ct.cube); -} - -static int -estimate_cornershtr_HTM(CubeTarget ct) -{ - return ptableval(&pd_cornershtr_HTM, ct.cube); -} - -static int -estimate_cornershtr_URF(CubeTarget ct) -{ - /* TODO: I can improve this by checking first the corner in DBL - * and use that as a reference */ - - int c, ret = 15; - Trans i; - - for (i = 0; i < NROTATIONS; i++) { - ct.cube = apply_alg(rotation_alg(i), ct.cube); - c = estimate_cornershtr_HTM(ct); - ret = MIN(ret, c); - } - - return ret; -} - -static int -estimate_corners_URF(CubeTarget ct) -{ - /* TODO: I can improve this by checking first the corner in DBL - * and use that as a reference */ - - int c, ret = 15; - Trans i; - - for (i = 0; i < NROTATIONS; i++) { - ct.cube = apply_alg(rotation_alg(i), ct.cube); - c = estimate_corners_HTM(ct); - ret = MIN(ret, c); - } - - return ret; -} - -static int -estimate_drany_HTM(CubeTarget ct) -{ - int r1, r2, r3; - - r1 = ptableval(&pd_drud_sym16_HTM, ct.cube); - r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, ct.cube)); - r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, ct.cube)); - - return MIN(r1, MIN(r2, r3)); -} - -static int -estimate_drud_HTM(CubeTarget ct) -{ - return ptableval(&pd_drud_sym16_HTM, ct.cube); -} - -static int -estimate_drud_eofb(CubeTarget ct) -{ - return ptableval(&pd_drud_eofb, ct.cube); -} - -static int -estimate_dr_eofb(CubeTarget ct) -{ - int r1, r2; - - r1 = ptableval(&pd_drud_eofb, ct.cube); - r2 = ptableval(&pd_drud_eofb, apply_trans(rf, ct.cube)); - - return MIN(r1, r2); -} - -static int -estimate_drudfin_drud(CubeTarget ct) -{ - int val = ptableval(&pd_drudfin_noE_sym16_drud, ct.cube); - - if (val != 0) - return val; - - return ct.cube.epose % 24 == 0 ? 0 : 1; -} - -static int -estimate_htr_drud(CubeTarget ct) -{ - return ptableval(&pd_htr_drud, ct.cube); -} - -static int -estimate_htrfin_htr(CubeTarget ct) -{ - return ptableval(&pd_htrfin_htr, ct.cube); -} - -static int -estimate_optimal_HTM(CubeTarget ct) -{ - int dr1, dr2, dr3, cor, ret; - Cube cube = ct.cube; - - dr1 = ptableval(&pd_khuge_HTM, cube); - cor = estimate_corners_HTM(ct); - ret = MAX(dr1, cor); - - if (ret > ct.target) - return ret; - - cube = apply_trans(rf, ct.cube); - dr2 = ptableval(&pd_khuge_HTM, cube); - ret = MAX(ret, dr2); - - if (ret > ct.target) - return ret; - - cube = apply_trans(fd, ct.cube); - dr3 = ptableval(&pd_khuge_HTM, cube); - - /* Michiel de Bondt's trick */ - if (dr1 == dr2 && dr2 == dr3 && dr1 != 0) - dr3++; - - return MAX(ret, dr3); -} - -/* Validators ****************************************************************/ - -static bool -always_valid(Alg *alg) -{ - return true; -} - -static bool -validate_singlecw_ending(Alg *alg) -{ - int i; - bool nor, inv; - Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; - - for (i = 0; i < alg->len; i++) { - if (alg->inv[i]) { - l2i = l1i; - l1i = alg->move[i]; - } else { - l2 = l1; - l1 = alg->move[i]; - } - } - - nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); - inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); - - return nor && inv; -} - -/* Pre-transformation detectors **********************************************/ - -static Trans -detect_pretrans_eofb(Cube cube) -{ - Trans i; - - for (i = 0; i < NROTATIONS; i++) - if (check_eofb(apply_trans(i, cube))) - return i; - - return 0; -} - -static Trans -detect_pretrans_drud(Cube cube) -{ - Trans i; - - for (i = 0; i < NROTATIONS; i++) - if (check_drud(apply_trans(i, cube))) - return i; - - return 0; -} diff --git a/old/2021-11-10-beforeremovingchecker/steps.h b/old/2021-11-10-beforeremovingchecker/steps.h deleted file mode 100644 index aa3178c..0000000 --- a/old/2021-11-10-beforeremovingchecker/steps.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef STEPS_H -#define STEPS_H - -#include "pruning.h" - -#define NSTEPS 50 - -extern Step * steps[NSTEPS]; - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/symcoord.c b/old/2021-11-10-beforeremovingchecker/symcoord.c deleted file mode 100644 index 9a4d49a..0000000 --- a/old/2021-11-10-beforeremovingchecker/symcoord.c +++ /dev/null @@ -1,359 +0,0 @@ -#include "symcoord.h" - -static Cube antindex_coud_sym16(uint64_t ind); -static Cube antindex_cp_sym16(uint64_t ind); -static Cube antindex_eofbepos_sym16(uint64_t ind); -static Cube antindex_drud_sym16(uint64_t ind); -static Cube antindex_drudfin_noE_sym16(uint64_t ind); -static Cube antindex_khuge(uint64_t ind); - -static uint64_t index_coud_sym16(Cube cube); -static uint64_t index_cp_sym16(Cube cube); -static uint64_t index_eofbepos_sym16(Cube cube); -static uint64_t index_drud_sym16(Cube cube); -static uint64_t index_drudfin_noE_sym16(Cube cube); -static uint64_t index_khuge(Cube cube); - -static void gensym(SymData *sd); -static bool read_symdata_file(SymData *sd); -static bool write_symdata_file(SymData *sd); - -/* Transformation groups and symmetry data ***********************************/ - -static Trans -trans_group_udfix[16] = { - uf, ur, ub, ul, - df, dr, db, dl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror, -}; - -static SymData -sd_coud_16 = { - .filename = "sd_coud_16", - .coord = &coord_coud, - .sym_coord = &coord_coud_sym16, - .ntrans = 16, - .trans = trans_group_udfix -}; - -static SymData -sd_cp_16 = { - .filename = "sd_cp_16", - .coord = &coord_cp, - .sym_coord = &coord_cp_sym16, - .ntrans = 16, - .trans = trans_group_udfix -}; - -static SymData -sd_eofbepos_16 = { - .filename = "sd_eofbepos_16", - .coord = &coord_eofbepos, - .sym_coord = &coord_eofbepos_sym16, - .ntrans = 16, - .trans = trans_group_udfix -}; - -static int nsymdata = 3; -static SymData * all_sd[] = { - &sd_coud_16, - &sd_cp_16, - &sd_eofbepos_16, -}; - - -/* Coordinates and their implementation **************************************/ - -Coordinate -coord_eofbepos_sym16 = { - .index = index_eofbepos_sym16, - .cube = antindex_eofbepos_sym16, - .check = check_eofbepos, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -Coordinate -coord_coud_sym16 = { - .index = index_coud_sym16, - .cube = antindex_coud_sym16, - .check = check_coud, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -Coordinate -coord_cp_sym16 = { - .index = index_cp_sym16, - .cube = antindex_cp_sym16, - .check = check_cp, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -Coordinate -coord_drud_sym16 = { - .index = index_drud_sym16, - .cube = antindex_drud_sym16, - .check = check_drud, - .max = POW3TO7 * 64430, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -Coordinate -coord_drudfin_noE_sym16 = { - .index = index_drudfin_noE_sym16, - .cube = antindex_drudfin_noE_sym16, - .check = check_drudfin_noE, - .max = FACTORIAL8 * 2768, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -Coordinate -coord_khuge = { - .index = index_khuge, - .cube = antindex_khuge, - .check = check_khuge, - .max = POW3TO7 * FACTORIAL4 * 64430, - .ntrans = 16, - .trans = trans_group_udfix, -}; - -/* Functions *****************************************************************/ - -static Cube -antindex_coud_sym16(uint64_t ind) -{ - return sd_coud_16.rep[ind]; -} - -static Cube -antindex_cp_sym16(uint64_t ind) -{ - return sd_cp_16.rep[ind]; -} - -static Cube -antindex_eofbepos_sym16(uint64_t ind) -{ - return sd_eofbepos_16.rep[ind]; -} - -static Cube -antindex_drud_sym16(uint64_t ind) -{ - Cube c; - - c = antindex_eofbepos_sym16(ind/POW3TO7); - c.coud = ind % POW3TO7; - c.cofb = c.coud; - c.corl = c.coud; - - return c; -} - -static Cube -antindex_drudfin_noE_sym16(uint64_t ind) -{ - Cube c1, c2; - - c1 = coord_epud.cube(ind % FACTORIAL8); - c2 = antindex_cp_sym16(ind/FACTORIAL8); - c1.cp = c2.cp; - - return c1; -} - -static Cube -antindex_khuge(uint64_t ind) -{ - Cube c; - - c = antindex_eofbepos_sym16(ind/(FACTORIAL4*POW3TO7)); - c.epose = ((c.epose / 24) * 24) + ((ind/POW3TO7) % 24); - c.coud = ind % POW3TO7; - - return c; -} - -static uint64_t -index_coud_sym16(Cube cube) -{ - return sd_coud_16.class[coord_coud.index(cube)]; -} - -static uint64_t -index_cp_sym16(Cube cube) -{ - return sd_cp_16.class[coord_cp.index(cube)]; -} - -static uint64_t -index_drud_sym16(Cube cube) -{ - Trans t; - Cube c; - - t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)]; - c = apply_trans(t, cube); - - return index_eofbepos_sym16(c) * POW3TO7 + c.coud; -} - -static uint64_t -index_drudfin_noE_sym16(Cube cube) -{ - Trans t; - Cube c; - - t = sd_cp_16.transtorep[coord_cp.index(cube)]; - c = apply_trans(t, cube); - - return index_cp_sym16(c) * FACTORIAL8 + coord_epud.index(c); -} - -static uint64_t -index_eofbepos_sym16(Cube cube) -{ - return sd_eofbepos_16.class[coord_eofbepos.index(cube)]; -} - -static uint64_t -index_khuge(Cube cube) -{ - Trans t; - Cube c; - uint64_t a; - - t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)]; - c = apply_trans(t, cube); - a = (index_eofbepos_sym16(c) * 24) + (c.epose % 24); - - return a * POW3TO7 + c.coud; -} - -/* Other functions ***********************************************************/ - -static void -gensym(SymData *sd) -{ - uint64_t i, in, nreps = 0; - int j; - Cube c, d; - - if (sd->generated) - return; - - sd->class = malloc(sd->coord->max * sizeof(uint64_t)); - sd->rep = malloc(sd->coord->max * sizeof(Cube)); - sd->transtorep = malloc(sd->coord->max * sizeof(Trans)); - - if (read_symdata_file(sd)) { - sd->generated = true; - return; - } - - fprintf(stderr, "Cannot load %s, generating it\n", sd->filename); - - for (i = 0; i < sd->coord->max; i++) - sd->class[i] = sd->coord->max + 1; - - for (i = 0; i < sd->coord->max; i++) { - if (sd->class[i] == sd->coord->max + 1) { - c = sd->coord->cube(i); - sd->rep[nreps] = c; - for (j = 0; j < sd->ntrans; j++) { - d = apply_trans(sd->trans[j], c); - in = sd->coord->index(d); - - if (sd->class[in] == sd->coord->max + 1) { - sd->class[in] = nreps; - sd->transtorep[in] = - inverse_trans(sd->trans[j]); - } - } - nreps++; - } - } - - sd->sym_coord->max = nreps; - sd->rep = realloc(sd->rep, nreps * sizeof(Cube)); - sd->generated = true; - - fprintf(stderr, "Found %lu classes\n", nreps); - - if (!write_symdata_file(sd)) - fprintf(stderr, "Error writing SymData file\n"); - - return; -} - -static bool -read_symdata_file(SymData *sd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; - bool r = true; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, sd->filename); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = r && fread(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; - r = r && fread(sd->rep, sizeof(Cube), *sn, f) == *sn; - r = r && fread(sd->class, sizeof(uint64_t), n, f) == n; - r = r && fread(sd->transtorep, sizeof(Trans), n, f) == n; - - fclose(f); - return r; -} - -static bool -write_symdata_file(SymData *sd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+100]; - uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; - bool r = true; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, sd->filename); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - r = r && fwrite(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; - r = r && fwrite(sd->rep, sizeof(Cube), *sn, f) == *sn; - r = r && fwrite(sd->class, sizeof(uint64_t), n, f) == n; - r = r && fwrite(sd->transtorep, sizeof(Trans), n, f) == n; - - fclose(f); - return r; -} - -void -init_symcoord() -{ - int i; - - static bool initialized = false; - if (initialized) - return; - initialized = true; - - for (i = 0; i < nsymdata; i++) - gensym(all_sd[i]); -} - diff --git a/old/2021-11-10-beforeremovingchecker/symcoord.h b/old/2021-11-10-beforeremovingchecker/symcoord.h deleted file mode 100644 index f231c92..0000000 --- a/old/2021-11-10-beforeremovingchecker/symcoord.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef SYMCOORD_H -#define SYMCOORD_H - -#include "coord.h" - -extern Coordinate coord_coud_sym16; -extern Coordinate coord_cp_sym16; -extern Coordinate coord_eofbepos_sym16; -extern Coordinate coord_drud_sym16; -extern Coordinate coord_drudfin_noE_sym16; -extern Coordinate coord_khuge; - -void init_symcoord(); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/trans.c b/old/2021-11-10-beforeremovingchecker/trans.c deleted file mode 100644 index ff3cdbb..0000000 --- a/old/2021-11-10-beforeremovingchecker/trans.c +++ /dev/null @@ -1,372 +0,0 @@ -#include "trans.h" - -/* Local functions ***********************************************************/ - -static bool read_ttables_file(); -static Cube rotate_via_compose(Trans r, Cube c, PieceFilter f); -static bool write_ttables_file(); - -/* Tables and other data *****************************************************/ - -static int ep_mirror[12] = { - [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL, - [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL, - [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL -}; - -static int cp_mirror[8] = { - [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL, - [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL -}; - -static int cpos_mirror[6] = { - [U_center] = U_center, [D_center] = D_center, - [R_center] = L_center, [L_center] = R_center, - [F_center] = F_center, [B_center] = B_center -}; - -/* TODO Is there a more elegant way? */ -static char rotation_alg_string[100][NROTATIONS] = { - [uf] = "", [ur] = "y", [ub] = "y2", [ul] = "y3", - [df] = "z2", [dr] = "y z2", [db] = "x2", [dl] = "y3 z2", - [rf] = "z3", [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3", - [lf] = "z", [ld] = "z y3", [lb] = "z y2", [lu] = "z y", - [fu] = "x y2", [fr] = "x y", [fd] = "x", [fl] = "x y3", - [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3", -}; - -static int epose_source[NTRANS]; /* 0=epose, 1=eposs, 2=eposm */ -static int eposs_source[NTRANS]; -static int eposm_source[NTRANS]; -static int eofb_source[NTRANS]; /* 0=eoud, 1=eorl, 2=eofb */ -static int eorl_source[NTRANS]; -static int eoud_source[NTRANS]; -static int coud_source[NTRANS]; /* 0=coud, 1=corl, 2=cofb */ -static int cofb_source[NTRANS]; -static int corl_source[NTRANS]; - -static int epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static int eposs_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static int eposm_ttable[NTRANS][FACTORIAL12/FACTORIAL8]; -static int eo_ttable[NTRANS][POW2TO11]; -static int cp_ttable[NTRANS][FACTORIAL8]; -static int co_ttable[NTRANS][POW3TO7]; -static int cpos_ttable[NTRANS][FACTORIAL6]; -static Move moves_ttable[NTRANS][NMOVES]; - -/* Local functions implementation ********************************************/ - -void -init_trans() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - Cube aux, cube, c[3]; - CubeArray epcp; - int i, eparr[12], eoarr[12], cparr[8], coarr[8]; - unsigned int ui; - Move mi, move; - Trans m; - - /* Compute sources */ - for (i = 0; i < NTRANS; i++) { - cube = apply_alg(rotation_alg(i), (Cube){0}); - - epose_source[i] = edge_slice(what_edge_at(cube, FR)); - eposs_source[i] = edge_slice(what_edge_at(cube, UR)); - eposm_source[i] = edge_slice(what_edge_at(cube, UF)); - eofb_source[i] = what_center_at(cube, F_center)/2; - eorl_source[i] = what_center_at(cube, R_center)/2; - eoud_source[i] = what_center_at(cube, U_center)/2; - coud_source[i] = what_center_at(cube, U_center)/2; - cofb_source[i] = what_center_at(cube, F_center)/2; - corl_source[i] = what_center_at(cube, R_center)/2; - } - - if (read_ttables_file()) - return; - - fprintf(stderr, "Cannot load %s, generating it\n", "ttables"); - - /* Initialize tables */ - for (m = 0; m < NTRANS; m++) { - epcp = (CubeArray){ .ep = eparr, .cp = cparr }; - cube = apply_alg(rotation_alg(m), (Cube){0}); - cube_to_arrays(cube, &epcp, pf_epcp); - if (m >= NROTATIONS) { - apply_permutation(ep_mirror, eparr, 12); - apply_permutation(cp_mirror, cparr, 8); - } - - for (ui = 0; ui < FACTORIAL12/FACTORIAL8; ui++) { - c[0] = admissible_ep((Cube){ .epose = ui }, pf_e); - c[1] = admissible_ep((Cube){ .eposs = ui }, pf_s); - c[2] = admissible_ep((Cube){ .eposm = ui }, pf_m); - - cube = rotate_via_compose(m,c[epose_source[m]],pf_ep); - epose_ttable[m][ui] = cube.epose; - - cube = rotate_via_compose(m,c[eposs_source[m]],pf_ep); - eposs_ttable[m][ui] = cube.eposs; - - cube = rotate_via_compose(m,c[eposm_source[m]],pf_ep); - eposm_ttable[m][ui] = cube.eposm; - } - for (ui = 0; ui < POW2TO11; ui++ ) { - int_to_sum_zero_array(ui, 2, 12, eoarr); - apply_permutation(eparr, eoarr, 12); - eo_ttable[m][ui] = digit_array_to_int(eoarr, 11, 2); - } - for (ui = 0; ui < POW3TO7; ui++) { - int_to_sum_zero_array(ui, 3, 8, coarr); - apply_permutation(cparr, coarr, 8); - co_ttable[m][ui] = digit_array_to_int(coarr, 7, 3); - if (m >= NROTATIONS) - co_ttable[m][ui] = - invert_digits(co_ttable[m][ui], 3, 7); - } - for (ui = 0; ui < FACTORIAL8; ui++) { - cube = (Cube){ .cp = ui }; - cube = rotate_via_compose(m, cube, pf_cp); - cp_ttable[m][ui] = cube.cp; - } - for (ui = 0; ui < FACTORIAL6; ui++) { - cube = (Cube){ .cpos = ui }; - cube = rotate_via_compose(m, cube, pf_cpos); - cpos_ttable[m][ui] = cube.cpos; - } - for (mi = 0; mi < NMOVES; mi++) { - /* Old version: - * - aux = apply_trans(m, apply_move(mi, (Cube){0})); - for (move = 0; move < NMOVES; move++) { - cube = apply_move(inverse_move(move), aux); - mirr = apply_trans(uf_mirror, cube); - if (is_solved(cube) || is_solved(mirr)) - moves_ttable[m][mi] = move; - } - */ - - aux = apply_trans(m, apply_move(mi, (Cube){0})); - for (move = 0; move < NMOVES; move++) { - cube = apply_move(inverse_move(move), aux); - if (is_solved(cube)) { - moves_ttable[m][mi] = move; - break; - } - } - } - } - - if (!write_ttables_file()) - fprintf(stderr, "Error writing ttables\n"); -} - -static bool -read_ttables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+20]; - int b = sizeof(int); - bool r = true; - Move m; - - /* Table sizes, used for reading and writing files */ - uint64_t me[11] = { - [0] = FACTORIAL12/FACTORIAL8, - [1] = FACTORIAL12/FACTORIAL8, - [2] = FACTORIAL12/FACTORIAL8, - [3] = POW2TO11, - [4] = FACTORIAL8, - [5] = POW3TO7, - [6] = FACTORIAL6, - [7] = NMOVES - }; - - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, "ttables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - for (m = 0; m < NTRANS; m++) { - r = r && fread(epose_ttable[m], b, me[0], f) == me[0]; - r = r && fread(eposs_ttable[m], b, me[1], f) == me[1]; - r = r && fread(eposm_ttable[m], b, me[2], f) == me[2]; - r = r && fread(eo_ttable[m], b, me[3], f) == me[3]; - r = r && fread(cp_ttable[m], b, me[4], f) == me[4]; - r = r && fread(co_ttable[m], b, me[5], f) == me[5]; - r = r && fread(cpos_ttable[m], b, me[6], f) == me[6]; - r = r && fread(moves_ttable[m], b, me[7], f) == me[7]; - } - - fclose(f); - return r; -} - -static Cube -rotate_via_compose(Trans r, Cube c, PieceFilter f) -{ - static int zero12[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - static int zero8[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; - static CubeArray ma = { - .ep = ep_mirror, - .eofb = zero12, - .eorl = zero12, - .eoud = zero12, - .cp = cp_mirror, - .coud = zero8, - .corl = zero8, - .cofb = zero8, - .cpos = cpos_mirror - }; - - Alg *inv = inverse_alg(rotation_alg(r)); - Cube ret = {0}; - - if (r >= NROTATIONS) - ret = move_via_arrays(&ma, ret, f); - ret = apply_alg_generic(inv, ret, f, true); - - ret = compose_filtered(c, ret, f); - - ret = apply_alg_generic(rotation_alg(r), ret, f, true); - if (r >= NROTATIONS) - ret = move_via_arrays(&ma, ret, f); - - free_alg(inv); - return ret; -} - -static bool -write_ttables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+20]; - bool r = true; - int b = sizeof(int); - Move m; - - /* Table sizes, used for reading and writing files */ - uint64_t me[11] = { - [0] = FACTORIAL12/FACTORIAL8, - [1] = FACTORIAL12/FACTORIAL8, - [2] = FACTORIAL12/FACTORIAL8, - [3] = POW2TO11, - [4] = FACTORIAL8, - [5] = POW3TO7, - [6] = FACTORIAL6, - [7] = NMOVES - }; - - strcpy(fname, tabledir); - strcat(fname, "/ttables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - for (m = 0; m < NTRANS; m++) { - r = r && fwrite(epose_ttable[m], b, me[0], f) == me[0]; - r = r && fwrite(eposs_ttable[m], b, me[1], f) == me[1]; - r = r && fwrite(eposm_ttable[m], b, me[2], f) == me[2]; - r = r && fwrite(eo_ttable[m], b, me[3], f) == me[3]; - r = r && fwrite(cp_ttable[m], b, me[4], f) == me[4]; - r = r && fwrite(co_ttable[m], b, me[5], f) == me[5]; - r = r && fwrite(cpos_ttable[m], b, me[6], f) == me[6]; - r = r && fwrite(moves_ttable[m], b, me[7], f) == me[7]; - } - - fclose(f); - return r; -} - -/* Public functions **********************************************************/ - -Cube -apply_trans(Trans t, Cube cube) -{ - /*init_trans();*/ - - int aux_epos[3] = { cube.epose, cube.eposs, cube.eposm }; - int aux_eo[3] = { cube.eoud, cube.eorl, cube.eofb }; - int aux_co[3] = { cube.coud, cube.corl, cube.cofb }; - - return (Cube) { - .epose = epose_ttable[t][aux_epos[epose_source[t]]], - .eposs = eposs_ttable[t][aux_epos[eposs_source[t]]], - .eposm = eposm_ttable[t][aux_epos[eposm_source[t]]], - .eofb = eo_ttable[t][aux_eo[eofb_source[t]]], - .eorl = eo_ttable[t][aux_eo[eorl_source[t]]], - .eoud = eo_ttable[t][aux_eo[eoud_source[t]]], - .coud = co_ttable[t][aux_co[coud_source[t]]], - .corl = co_ttable[t][aux_co[corl_source[t]]], - .cofb = co_ttable[t][aux_co[cofb_source[t]]], - .cp = cp_ttable[t][cube.cp], - .cpos = cpos_ttable[t][cube.cpos] - }; -} - -Trans -inverse_trans(Trans t) -{ - /* TODO is there a more elegant way? */ - static Trans inverse_trans_aux[NTRANS] = { - [uf] = uf, [ur] = ul, [ul] = ur, [ub] = ub, - [df] = df, [dr] = dr, [dl] = dl, [db] = db, - [rf] = lf, [rd] = bl, [rb] = rb, [ru] = fr, - [lf] = rf, [ld] = br, [lb] = lb, [lu] = fl, - [fu] = fu, [fr] = ru, [fd] = bu, [fl] = lu, - [bu] = fd, [br] = ld, [bd] = bd, [bl] = rd, - - [uf_mirror] = uf_mirror, [ur_mirror] = ur_mirror, - [ul_mirror] = ul_mirror, [ub_mirror] = ub_mirror, - [df_mirror] = df_mirror, [dr_mirror] = dl_mirror, - [dl_mirror] = dr_mirror, [db_mirror] = db_mirror, - [rf_mirror] = rf_mirror, [rd_mirror] = br_mirror, - [rb_mirror] = lb_mirror, [ru_mirror] = fl_mirror, - [lf_mirror] = lf_mirror, [ld_mirror] = bl_mirror, - [lb_mirror] = rb_mirror, [lu_mirror] = fr_mirror, - [fu_mirror] = fu_mirror, [fr_mirror] = lu_mirror, - [fd_mirror] = bu_mirror, [fl_mirror] = ru_mirror, - [bu_mirror] = fd_mirror, [br_mirror] = rd_mirror, - [bd_mirror] = bd_mirror, [bl_mirror] = ld_mirror - }; - - return inverse_trans_aux[t]; -} - -Alg * -rotation_alg(Trans t) -{ - int i; - - static Alg *rotation_alg_arr[NROTATIONS]; - static bool initialized = false; - - if (!initialized) { - for (i = 0; i < NROTATIONS; i++) - rotation_alg_arr[i] = new_alg(rotation_alg_string[i]); - - initialized = true; - } - - return rotation_alg_arr[t % NROTATIONS]; -} - -void -transform_alg(Trans t, Alg *alg) -{ - int i; - - /*init_trans();*/ - - for (i = 0; i < alg->len; i++) - alg->move[i] = moves_ttable[t][alg->move[i]]; -} diff --git a/old/2021-11-10-beforeremovingchecker/trans.h b/old/2021-11-10-beforeremovingchecker/trans.h deleted file mode 100644 index 2eda568..0000000 --- a/old/2021-11-10-beforeremovingchecker/trans.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef TRANS_H -#define TRANS_H - -#include "moves.h" - -Cube apply_trans(Trans t, Cube cube); -Trans inverse_trans(Trans t); -Alg * rotation_alg(Trans i); -void transform_alg(Trans i, Alg *alg); - -void init_trans(); - -#endif diff --git a/old/2021-11-10-beforeremovingchecker/utils.c b/old/2021-11-10-beforeremovingchecker/utils.c deleted file mode 100644 index f72a00e..0000000 --- a/old/2021-11-10-beforeremovingchecker/utils.c +++ /dev/null @@ -1,274 +0,0 @@ -#include "utils.h" - -void -apply_permutation(int *perm, int *set, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - if (!is_perm(perm, n)) - return; - - for (i = 0; i < n; i++) - aux[i] = set[perm[i]]; - - memcpy(set, aux, n * sizeof(int)); - free(aux); -} - -int -binomial(int n, int k) -{ - if (n < 0 || k < 0 || k > n) - return 0; - - return factorial(n) / (factorial(k) * factorial(n-k)); -} - -int -digit_array_to_int(int *a, int n, int b) -{ - int i, ret = 0, p = 1; - - for (i = 0; i < n; i++, p *= b) - ret += a[i] * p; - - return ret; -} - -int -factorial(int n) -{ - int i, ret = 1; - - if (n < 0) - return 0; - - for (i = 1; i <= n; i++) - ret *= i; - - return ret; -} - -void -index_to_perm(int p, int n, int *r) -{ - int *a = malloc(n * sizeof(int)); - int i, j, c; - - for (i = 0; i < n; i++) - a[i] = 0; - - if (p < 0 || p >= factorial(n)) - for (i = 0; i < n; i++) - r[i] = -1; - - for (i = 0; i < n; i++) { - c = 0; - j = 0; - while (c <= p / factorial(n-i-1)) - c += a[j++] ? 0 : 1; - r[i] = j-1; - a[j-1] = 1; - p %= factorial(n-i-1); - } - - free(a); -} - -void -index_to_subset(int s, int n, int k, int *r) -{ - int i, j, v; - - if (s < 0 || s >= binomial(n, k)) { - for (i = 0; i < n; i++) - r[i] = -1; - return; - } - - for (i = 0; i < n; i++) { - if (k == n-i) { - for (j = i; j < n; j++) - r[j] = 1; - return; - } - - if (k == 0) { - for (j = i; j < n; j++) - r[j] = 0; - return; - } - - v = binomial(n-i-1, k); - if (s >= v) { - r[i] = 1; - k--; - s -= v; - } else { - r[i] = 0; - } - } -} - -void -int_to_digit_array(int a, int b, int n, int *r) -{ - int i; - - if (b <= 1) - for (i = 0; i < n; i++) - r[i] = 0; - else - for (i = 0; i < n; i++, a /= b) - r[i] = a % b; -} - -void -int_to_sum_zero_array(int x, int b, int n, int *a) -{ - int i, s = 0; - - if (b <= 1) { - for (i = 0; i < n; i++) - a[i] = 0; - } else { - int_to_digit_array(x, b, n-1, a); - for (i = 0; i < n - 1; i++) - s = (s + a[i]) % b; - a[n-1] = (b - s) % b; - } -} - -int -invert_digits(int a, int b, int n) -{ - int i, ret, *r = malloc(n * sizeof(int)); - - int_to_digit_array(a, b, n, r); - for (i = 0; i < n; i++) - r[i] = (b-r[i]) % b; - - ret = digit_array_to_int(r, n, b); - free(r); - return ret; -} - -bool -is_perm(int *a, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - for (i = 0; i < n; i++) - if (a[i] < 0 || a[i] >= n) - return false; - else - aux[a[i]] = 1; - - for (i = 0; i < n; i++) - if (!aux[i]) - return false; - - free(aux); - - return true; -} - -bool -is_subset(int *a, int n, int k) -{ - int i, sum = 0; - - for (i = 0; i < n; i++) - sum += a[i] ? 1 : 0; - - return sum == k; -} - -int -perm_sign(int *a, int n) -{ - int i, j, ret = 0; - - if (!is_perm(a,n)) - return -1; - - for (i = 0; i < n; i++) - for (j = i+1; j < n; j++) - ret += (a[i] > a[j]) ? 1 : 0; - - return ret % 2; -} - -int -perm_to_index(int *a, int n) -{ - int i, j, c, ret = 0; - - if (!is_perm(a, n)) - return -1; - - for (i = 0; i < n; i++) { - c = 0; - for (j = i+1; j < n; j++) - c += (a[i] > a[j]) ? 1 : 0; - ret += factorial(n-i-1) * c; - } - - return ret; -} - -int -powint(int a, int b) -{ - if (b < 0) - return 0; - if (b == 0) - return 1; - - if (b % 2) - return a * powint(a, b-1); - else - return powint(a*a, b/2); -} - -int -subset_to_index(int *a, int n, int k) -{ - int i, ret = 0; - - if (!is_subset(a, n, k)) - return binomial(n, k); - - for (i = 0; i < n; i++) { - if (k == n-i) - return ret; - if (a[i]) { - ret += binomial(n-i-1, k); - k--; - } - } - - return ret; -} - -void -sum_arrays_mod(int *src, int *dst, int n, int m) -{ - int i; - - for (i = 0; i < n; i++) - dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m; -} - -void -swap(int *a, int *b) -{ - int aux; - - aux = *a; - *a = *b; - *b = aux; -} - diff --git a/old/2021-11-10-beforeremovingchecker/utils.h b/old/2021-11-10-beforeremovingchecker/utils.h deleted file mode 100644 index 80c33ae..0000000 --- a/old/2021-11-10-beforeremovingchecker/utils.h +++ /dev/null @@ -1,41 +0,0 @@ -#ifndef UTILS_H -#define UTILS_H - -#include -#include -#include - -#define POW2TO6 64ULL -#define POW2TO11 2048ULL -#define POW2TO12 4096ULL -#define POW3TO7 2187ULL -#define POW3TO8 6561ULL -#define FACTORIAL4 24ULL -#define FACTORIAL6 720ULL -#define FACTORIAL7 5040ULL -#define FACTORIAL8 40320ULL -#define FACTORIAL12 479001600ULL -#define BINOM12ON4 495ULL -#define BINOM8ON4 70ULL -#define MIN(a,b) (((a) < (b)) ? (a) : (b)) -#define MAX(a,b) (((a) > (b)) ? (a) : (b)) - -void apply_permutation(int *perm, int *set, int n); -int binomial(int n, int k); -int digit_array_to_int(int *a, int n, int b); -int factorial(int n); -void index_to_perm(int p, int n, int *r); -void index_to_subset(int s, int n, int k, int *r); -void int_to_digit_array(int a, int b, int n, int *r); -void int_to_sum_zero_array(int x, int b, int n, int *a); -int invert_digits(int a, int b, int n); -bool is_perm(int *a, int n); -bool is_subset(int *a, int n, int k); -int perm_sign(int *a, int n); -int perm_to_index(int *a, int n); -int powint(int a, int b); -int subset_to_index(int *a, int n, int k); -void sum_arrays_mod(int *src, int *dst, int n, int m); -void swap(int *a, int *b); - -#endif -- cgit v1.3