From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- 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 insertions(+) create mode 100644 old/2021-11-10-beforeremovingchecker/alg.c create mode 100644 old/2021-11-10-beforeremovingchecker/alg.h create mode 100644 old/2021-11-10-beforeremovingchecker/commands.c create mode 100644 old/2021-11-10-beforeremovingchecker/commands.h create mode 100644 old/2021-11-10-beforeremovingchecker/coord.c create mode 100644 old/2021-11-10-beforeremovingchecker/coord.h create mode 100644 old/2021-11-10-beforeremovingchecker/cube.c create mode 100644 old/2021-11-10-beforeremovingchecker/cube.h create mode 100644 old/2021-11-10-beforeremovingchecker/cubetypes.h create mode 100644 old/2021-11-10-beforeremovingchecker/env.c create mode 100644 old/2021-11-10-beforeremovingchecker/env.h create mode 100644 old/2021-11-10-beforeremovingchecker/moves.c create mode 100644 old/2021-11-10-beforeremovingchecker/moves.h create mode 100644 old/2021-11-10-beforeremovingchecker/pf.c create mode 100644 old/2021-11-10-beforeremovingchecker/pf.h create mode 100644 old/2021-11-10-beforeremovingchecker/pruning.c create mode 100644 old/2021-11-10-beforeremovingchecker/pruning.h create mode 100644 old/2021-11-10-beforeremovingchecker/shell.c create mode 100644 old/2021-11-10-beforeremovingchecker/shell.h create mode 100644 old/2021-11-10-beforeremovingchecker/solve.c create mode 100644 old/2021-11-10-beforeremovingchecker/solve.h create mode 100644 old/2021-11-10-beforeremovingchecker/steps.c create mode 100644 old/2021-11-10-beforeremovingchecker/steps.h create mode 100644 old/2021-11-10-beforeremovingchecker/symcoord.c create mode 100644 old/2021-11-10-beforeremovingchecker/symcoord.h create mode 100644 old/2021-11-10-beforeremovingchecker/trans.c create mode 100644 old/2021-11-10-beforeremovingchecker/trans.h create mode 100644 old/2021-11-10-beforeremovingchecker/utils.c create 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 new file mode 100644 index 0000000..06c2d7b --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/alg.c @@ -0,0 +1,366 @@ +#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 new file mode 100644 index 0000000..98900b4 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/alg.h @@ -0,0 +1,35 @@ +#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 new file mode 100644 index 0000000..b141229 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/commands.c @@ -0,0 +1,329 @@ +#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 new file mode 100644 index 0000000..f2703fa --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/commands.h @@ -0,0 +1,13 @@ +#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 new file mode 100644 index 0000000..343dfb3 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/coord.c @@ -0,0 +1,629 @@ +#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 new file mode 100644 index 0000000..81c1e9c --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/coord.h @@ -0,0 +1,40 @@ +#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 new file mode 100644 index 0000000..b621d7b --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/cube.c @@ -0,0 +1,716 @@ +#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 new file mode 100644 index 0000000..98657ab --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/cube.h @@ -0,0 +1,40 @@ +#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 new file mode 100644 index 0000000..38a6f8d --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/cubetypes.h @@ -0,0 +1,298 @@ +#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 new file mode 100644 index 0000000..d13642f --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/env.c @@ -0,0 +1,45 @@ +#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 new file mode 100644 index 0000000..871a9c1 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/env.h @@ -0,0 +1,15 @@ +#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 new file mode 100644 index 0000000..5ba17ca --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/moves.c @@ -0,0 +1,474 @@ +#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 new file mode 100644 index 0000000..082a080 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/moves.h @@ -0,0 +1,16 @@ +#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 new file mode 100644 index 0000000..34be4fd --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/pf.c @@ -0,0 +1,80 @@ +#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 new file mode 100644 index 0000000..85ee1eb --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/pf.h @@ -0,0 +1,18 @@ +#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 new file mode 100644 index 0000000..86363f4 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/pruning.c @@ -0,0 +1,272 @@ +#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 new file mode 100644 index 0000000..631ee3a --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/pruning.h @@ -0,0 +1,23 @@ +#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 new file mode 100644 index 0000000..e591faa --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/shell.c @@ -0,0 +1,99 @@ +#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 new file mode 100644 index 0000000..a72d136 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/shell.h @@ -0,0 +1,13 @@ +#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 new file mode 100644 index 0000000..af685ec --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/solve.c @@ -0,0 +1,209 @@ +#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 new file mode 100644 index 0000000..ff84e7e --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/solve.h @@ -0,0 +1,9 @@ +#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 new file mode 100644 index 0000000..7213766 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/steps.c @@ -0,0 +1,916 @@ +#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 new file mode 100644 index 0000000..aa3178c --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/steps.h @@ -0,0 +1,10 @@ +#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 new file mode 100644 index 0000000..9a4d49a --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/symcoord.c @@ -0,0 +1,359 @@ +#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 new file mode 100644 index 0000000..f231c92 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/symcoord.h @@ -0,0 +1,15 @@ +#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 new file mode 100644 index 0000000..ff3cdbb --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/trans.c @@ -0,0 +1,372 @@ +#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 new file mode 100644 index 0000000..2eda568 --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/trans.h @@ -0,0 +1,13 @@ +#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 new file mode 100644 index 0000000..f72a00e --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/utils.c @@ -0,0 +1,274 @@ +#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 new file mode 100644 index 0000000..80c33ae --- /dev/null +++ b/old/2021-11-10-beforeremovingchecker/utils.h @@ -0,0 +1,41 @@ +#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