commit b657d9d900bf8d9d00c1dd7ddf6b1b27990e91c1
parent a125e69c8ce0a2764b1e50b2dad0a4fa9d141ef4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 14 Apr 2023 14:16:29 +0200
A new start
Diffstat:
| M | Makefile | | | 3 | ++- |
| A | main.c | | | 0 | |
| M | src/alg.c | | | 212 | +++++++++++++++++++++---------------------------------------------------------- |
| M | src/alg.h | | | 116 | +++++++++++++++++++++---------------------------------------------------------- |
| D | src/commands.c | | | 553 | ------------------------------------------------------------------------------- |
| D | src/commands.h | | | 206 | ------------------------------------------------------------------------------- |
| M | src/coord.c | | | 177 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------- |
| M | src/coord.h | | | 73 | +++++++++++++++++++++++++++++-------------------------------------------- |
| M | src/cube.c | | | 406 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------- |
| M | src/cube.h | | | 75 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- |
| D | src/cubetypes.h | | | 360 | ------------------------------------------------------------------------------- |
| M | src/env.c | | | 4 | ++++ |
| M | src/env.h | | | 1 | - |
| A | src/main.c | | | 85 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| D | src/moves.c | | | 283 | ------------------------------------------------------------------------------- |
| D | src/moves.h | | | 14 | -------------- |
| M | src/pruning.c | | | 229 | ++++++++++++++++--------------------------------------------------------------- |
| M | src/pruning.h | | | 22 | +++++++++++++++++++++- |
| D | src/shell.c | | | 189 | ------------------------------------------------------------------------------- |
| D | src/shell.h | | | 14 | -------------- |
| M | src/solve.c | | | 507 | +++++++++++++++++++++++++++---------------------------------------------------- |
| M | src/solve.h | | | 10 | +++++----- |
| D | src/steps.c | | | 221 | ------------------------------------------------------------------------------- |
| D | src/steps.h | | | 277 | ------------------------------------------------------------------------------- |
| D | src/trans.c | | | 190 | ------------------------------------------------------------------------------- |
| D | src/trans.h | | | 32 | -------------------------------- |
| D | src/utils.c | | | 290 | ------------------------------------------------------------------------------- |
| D | src/utils.h | | | 43 | ------------------------------------------- |
28 files changed, 992 insertions(+), 3600 deletions(-)
diff --git a/Makefile b/Makefile
@@ -9,7 +9,8 @@ CPPFLAGS = -DVERSION=\"${VERSION}\"
CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \
-Wno-unused-parameter -O3 ${CPPFLAGS}
DBGFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \
- -Wno-unused-parameter -g ${CPPFLAGS}
+ -Wno-unused-parameter \
+ -g ${CPPFLAGS}
CC = cc
diff --git a/main.c b/main.c
diff --git a/src/alg.c b/src/alg.c
@@ -6,6 +6,28 @@ static int axis(Move m);
static void free_alglistnode(AlgListNode *aln);
static void realloc_alg(Alg *alg, int n);
+static char move_string[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\'",
+};
+
bool
allowed_HTM(Move m)
{
@@ -43,18 +65,7 @@ allowed_htr(Move m)
{
Move b = base_move(m);
- return moveset_HTM.allowed(m) && m == b + 1;
-}
-
-bool
-allowed_next_all(Move l2, Move l1, Move m)
-{
- bool p, q;
-
- p = l1 != NULLMOVE && base_move(l1) == base_move(m);
- q = l2 != NULLMOVE && base_move(l2) == base_move(m);
-
- return !(p || (commute(l1, l2) && q));
+ return allowed_HTM(m) && m == b + 1;
}
void
@@ -113,10 +124,7 @@ axis(Move m)
Move
base_move(Move m)
{
- if (m == NULLMOVE)
- return NULLMOVE;
- else
- return m - (m-1)%3;
+ return m == NULLMOVE ? NULLMOVE : m - (m-1)%3;
}
bool
@@ -126,19 +134,13 @@ commute(Move m1, Move m2)
}
void
-compose_alg(Alg *alg1, Alg *alg2)
+copy_alg(Alg *src, Alg *dst)
{
int i;
- for (i = 0; i < alg2->len; i++)
- append_move(alg1, alg2->move[i], alg2->inv[i]);
-}
-
-void
-copy_alg(Alg *src, Alg *dst)
-{
dst->len = 0; /* Overwrites */
- compose_alg(dst, src);
+ for (i = 0; i < src->len; i++)
+ append_move(dst, src->move[i], src->inv[i]);
}
void
@@ -169,16 +171,6 @@ free_alglistnode(AlgListNode *aln)
free(aln);
}
-void
-inplace(Alg * (*f)(Alg *), Alg *alg)
-{
- Alg *aux;
-
- aux = f(alg);
- copy_alg(aux, alg);
- free(aux);
-}
-
Alg *
inverse_alg(Alg *alg)
{
@@ -197,34 +189,6 @@ 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];
-}
-
Alg *
new_alg(char *str)
{
@@ -274,9 +238,9 @@ new_alg(char *str)
move_read = false;
for (j = U; j < NMOVES; j++) {
- if (str[i] == move_string(j)[0] ||
+ if (str[i] == move_string[j][0] ||
(str[i] >= 'a' && str[i] <= 'z' &&
- str[i] == move_string(j)[0]-('A'-'a') && j<=B)) {
+ str[i] == move_string[j][0]-('A'-'a') && j<=B)) {
m = j;
if (str[i] >= 'a' && str[i] <= 'z' && j<=B) {
m += Uw - U;
@@ -337,20 +301,8 @@ new_alglist()
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)
+print_alg(Alg *alg)
{
char fill[4];
int i;
@@ -364,25 +316,23 @@ print_alg(Alg *alg, bool l)
if (niss == alg->inv[i])
strcpy(fill, i == 0 ? "" : " ");
- printf("%s%s", fill, move_string(alg->move[i]));
+ 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)
+print_alglist(AlgList *al)
{
AlgListNode *i;
for (i = al->first; i != NULL; i = i->next)
- print_alg(i->alg, l);
+ print_alg(i->alg);
}
static void
@@ -409,85 +359,35 @@ realloc_alg(Alg *alg, int n)
alg->allocated = n;
}
-void
-swapmove(Move *m1, Move *m2)
-{
- Move aux;
-
- aux = *m1;
- *m1 = *m2;
- *m2 = aux;
-}
-
-char *
-trans_string(Trans t)
-{
- static char trans_string_aux[NTRANS][20] = {
- [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul",
- [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl",
- [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru",
- [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu",
- [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl",
- [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl",
-
- [uf_mirror] = "uf*", [ur_mirror] = "ur*",
- [ub_mirror] = "ub*", [ul_mirror] = "ul*",
- [df_mirror] = "df*", [dr_mirror] = "dr*",
- [db_mirror] = "db*", [dl_mirror] = "dl*",
- [rf_mirror] = "rf*", [rd_mirror] = "rd*",
- [rb_mirror] = "rb*", [ru_mirror] = "ru*",
- [lf_mirror] = "lf*", [ld_mirror] = "ld*",
- [lb_mirror] = "lb*", [lu_mirror] = "lu*",
- [fu_mirror] = "fu*", [fr_mirror] = "fr*",
- [fd_mirror] = "fd*", [fl_mirror] = "fl*",
- [bu_mirror] = "bu*", [br_mirror] = "br*",
- [bd_mirror] = "bd*", [bl_mirror] = "bl*",
- };
-
- return trans_string_aux[t];
-}
-
-Alg *
-unniss(Alg *alg)
+bool
+singlecwend(Alg *alg)
{
int i;
- Alg *ret;
+ bool nor, inv;
+ Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
- ret = new_alg("");
+ for (i = 0; i < alg->len; i++) {
+ if (alg->inv[i]) {
+ l2i = l1i;
+ l1i = alg->move[i];
+ } else {
+ l2 = l1;
+ l1 = alg->move[i];
+ }
+ }
- for (i = 0; i < alg->len; i++)
- if (!alg->inv[i])
- append_move(ret, alg->move[i], false);
-
- for (i = alg->len-1; i >= 0; i--)
- if (alg->inv[i])
- append_move(ret, inverse_move(alg->move[i]), false);
-
- return ret;
+ 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;
}
void
-init_moveset(Moveset *ms)
+swapmove(Move *m1, Move *m2)
{
- int j;
- uint64_t l, one;
- Move m, l2, l1;
-
- one = 1;
-
- for (j = 0, m = U; m < NMOVES; m++)
- if (ms->allowed(m))
- ms->sorted_moves[j++] = m;
- ms->sorted_moves[j] = NULLMOVE;
-
- for (l1 = 0; l1 < NMOVES; l1++) {
- for (l2 = 0; l2 < NMOVES; l2++) {
- ms->mask[l2][l1] = 0;
- for (l=0; ms->sorted_moves[l]!=NULLMOVE; l++) {
- m = ms->sorted_moves[l];
- if (ms->allowed_next(l2, l1, m))
- ms->mask[l2][l1] |= (one<<m);
- }
- }
- }
+ Move aux;
+
+ aux = *m1;
+ *m1 = *m2;
+ *m2 = aux;
}
diff --git a/src/alg.h b/src/alg.h
@@ -1,105 +1,49 @@
#ifndef ALG_H
#define ALG_H
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "cubetypes.h"
-#include "utils.h"
+// solve, private
+typedef struct alglistnode {
+ Alg *alg;
+ struct alglistnode *next;
+} AlgListNode;
+typedef struct {
+ AlgListNode *first;
+ AlgListNode *last;
+ int len;
+} AlgList;
+
+//cube
+void copy_alg(Alg *src, Alg *dst);
+void free_alg(Alg *alg);
+Alg * new_alg(char *str);
+void append_move(Alg *alg, Move m, bool inverse);
+Alg * inverse_alg(Alg *alg);
+Move inverse_move(Move m);
+// pruning
bool allowed_all(Move m);
bool allowed_HTM(Move m);
bool allowed_URF(Move m);
bool allowed_eofb(Move m);
bool allowed_drud(Move m);
bool allowed_htr(Move m);
-bool allowed_next_all(Move l2, Move l1, Move m);
-void append_alg(AlgList *l, Alg *alg);
-void append_move(Alg *alg, Move m, bool inverse);
+
+// pruning and solve?
Move base_move(Move m);
-void compose_alg(Alg *alg1, Alg *alg2);
bool commute(Move m1, Move m2);
-void copy_alg(Alg *src, Alg *dst);
-void free_alg(Alg *alg);
+
+// solve
void free_alglist(AlgList *l);
-void inplace(Alg * (*f)(Alg *), Alg *alg);
-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);
-void swapmove(Move *m1, Move *m2);
-char * trans_string(Trans t); /* Here because similar to move_string, move? */
-Alg * unniss(Alg *alg);
-
-void init_moveset(Moveset *ms);
-
-/* Movesets ******************************************************************/
-
-#ifndef ALG_C
-
-extern Moveset moveset_HTM;
-extern Moveset moveset_URF;
-extern Moveset moveset_eofb;
-extern Moveset moveset_drud;
-extern Moveset moveset_htr;
-
-extern Moveset * all_ms[];
-
-#else
-
-Moveset
-moveset_HTM = {
- .name = "HTM",
- .allowed = allowed_HTM,
- .allowed_next = allowed_next_all,
-};
-
-Moveset
-moveset_URF = {
- .name = "URF",
- .allowed = allowed_URF,
- .allowed_next = allowed_next_all,
-};
-
-Moveset
-moveset_eofb = {
- .name = "eofb",
- .allowed = allowed_eofb,
- .allowed_next = allowed_next_all,
-};
-
-Moveset
-moveset_drud = {
- .name = "drud",
- .allowed = allowed_drud,
- .allowed_next = allowed_next_all,
-};
-
-Moveset
-moveset_htr = {
- .name = "htr",
- .allowed = allowed_htr,
- .allowed_next = allowed_next_all,
-};
+void append_alg(AlgList *l, Alg *alg);
-Moveset *
-all_ms[] = {
- &moveset_HTM,
- &moveset_URF,
- &moveset_eofb,
- &moveset_drud,
- &moveset_htr,
- NULL
-};
+// solve, private
+bool singlecwend(Alg *alg);
+void swapmove(Move *m1, Move *m2);
-#endif
+// solve, change interface
+void print_alg(Alg *alg);
+void print_alglist(AlgList *al);
#endif
diff --git a/src/commands.c b/src/commands.c
@@ -1,553 +0,0 @@
-#define COMMANDS_C
-
-#include "commands.h"
-
-static bool read_step(CommandArgs *args, char *str);
-static bool read_scrtype(CommandArgs *args, char *str);
-static bool read_scramble(int c, char **v, CommandArgs *args);
-
-/* Arg parsing functions implementation **************************************/
-
-CommandArgs *
-solve_parse_args(int c, char **v)
-{
- int i;
- bool infinitesols, fixedmsols;
- long val;
-
- CommandArgs *a = new_args();
-
- a->opts->min_moves = 0;
- a->opts->max_moves = 20;
- a->opts->max_solutions = 1;
- a->opts->nthreads = 1;
- a->opts->optimal = -1;
- a->opts->can_niss = false;
- a->opts->verbose = false;
- a->opts->all = false;
- a->opts->print_number = true;
- a->opts->count_only = false;
-
- fixedmsols = false;
- infinitesols = false;
-
- for (i = 0; i < c; i++) {
- if (!strcmp(v[i], "-m") && i+1 < c) {
- val = strtol(v[++i], NULL, 10);
- if (val < 0 || val > 100) {
- fprintf(stderr,
- "Invalid min number of moves"
- "(0 <= N <= 100).\n");
- return a;
- }
- a->opts->min_moves = val;
- } else if (!strcmp(v[i], "-M") && i+1 < c) {
- val = strtol(v[++i], NULL, 10);
- if (val < 0 || val > 100) {
- fprintf(stderr,
- "Invalid max number of moves"
- "(0 <= N <= 100).\n");
- return a;
- }
- a->opts->max_moves = val;
- infinitesols = true;
- } else if (!strcmp(v[i], "-t") && i+1 < c) {
- val = strtol(v[++i], NULL, 10);
- if (val < 1 || val > 64) {
- fprintf(stderr,
- "Invalid number of threads."
- "1 <= t <= 64\n");
- return a;
- }
- a->opts->nthreads = val;
- } else if (!strcmp(v[i], "-n") && i+1 < c) {
- 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;
- fixedmsols = true;
- } else if (!strcmp(v[i], "-o")) {
- a->opts->optimal = 0;
- infinitesols = true;
- } else if (!strcmp(v[i], "-O") && i+1 < c) {
- val = strtol(v[++i], NULL, 10);
- if (val < 0 || val > 100 ||
- (val == 0 && strcmp("0", v[i]))) {
- fprintf(stderr,
- "Invalid max number of moves"
- " (0 <= N <= 100).\n");
- return a;
- }
- a->opts->optimal = val;
- infinitesols = true;
- } else if (!strcmp(v[i], "-N")) {
- a->opts->can_niss = true;
- } else if (!strcmp(v[i], "-i")) {
- a->scrstdin = true;
- } else if (!strcmp(v[i], "-v")) {
- a->opts->verbose = true;
- } else if (!strcmp(v[i], "-a")) {
- a->opts->all = true;
- } else if (!strcmp(v[i], "-p")) {
- a->opts->print_number = false;
- } else if (!strcmp(v[i], "-c")) {
- a->opts->count_only = true;
- } else if (!read_step(a, v[i])) {
- break;
- }
- }
-
- if (infinitesols && !fixedmsols)
- a->opts->max_solutions = 1000000; /* 1M = +infty */
-
- a->success = (a->scrstdin && i == c) || read_scramble(c-i, &v[i], a);
- return a;
-}
-
-CommandArgs *
-scramble_parse_args(int c, char **v)
-{
- int i;
- long val;
-
- CommandArgs *a = new_args();
-
- a->success = true;
- a->n = 1;
-
- for (i = 0; i < c; i++) {
- if (!strcmp(v[i], "-n") && i+1 < c) {
- val = strtol(v[++i], NULL, 10);
- if (val < 1 || val > 1000000) {
- fprintf(stderr,
- "Invalid number of scrambles.\n");
- a->success = false;
- return a;
- }
- a->n = val;
- } else if (!read_scrtype(a, v[i])) {
- a->success = false;
- return a;
- }
- }
-
- return a;
-}
-
-CommandArgs *
-gen_parse_args(int c, char **v)
-{
- int val;
- CommandArgs *a = new_args();
-
- a->opts->nthreads = 64;
- a->success = false;
-
- if (c == 0) {
- a->success = true;
- } else {
- if (!strcmp(v[0], "-t") && c > 1) {
- val = strtol(v[1], NULL, 10);
- if (val < 1 || val > 64) {
- fprintf(stderr,
- "Invalid number of threads."
- "1 <= t <= 64\n");
- return a;
- }
- a->opts->nthreads = val;
- a->success = true;
- }
- }
-
- return a;
-}
-
-CommandArgs *
-help_parse_args(int c, char **v)
-{
- int i;
- CommandArgs *a = new_args();
-
- if (c == 1) {
- for (i = 0; commands[i] != NULL; i++)
- if (!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_only_scramble(int c, char **v)
-{
- CommandArgs *a = new_args();
-
- if (!strcmp(v[0], "-i")) {
- a->scrstdin = true;
- a->success = c == 1;
- } else {
- a->success = read_scramble(c, v, a);
- }
-
- return a;
-}
-
-CommandArgs *
-parse_no_arg(int c, char **v)
-{
- CommandArgs *a = new_args();
-
- a->success = true;
-
- return a;
-}
-
-/* Exec functions implementation *********************************************/
-
-void
-solve_exec(CommandArgs *args)
-{
- Cube c;
- AlgList *sols;
-
- make_solved(&c);
- apply_alg(args->scramble, &c);
- sols = solve(&c, args->step, args->opts);
-
- if (args->opts->count_only)
- printf("%d\n", sols->len);
- else
- print_alglist(sols, args->opts->print_number);
-
- free_alglist(sols);
-}
-
-void
-scramble_exec(CommandArgs *args)
-{
- Cube cube;
- Alg *scr, *ruf, *aux;
- int i, j, eo, ep, co, cp;
- uint64_t ui, uj, uk;
-
- srand(time(NULL));
-
- for (i = 0; i < args->n; i++) {
-
- if (!strcmp(args->scrtype, "dr")) {
- ui = rand() % FACTORIAL8;
- uj = rand() % FACTORIAL8;
- uk = rand() % FACTORIAL4;
-
- make_solved(&cube);
- index_to_perm(ui, 8, cube.cp);
- index_to_perm(uj, 8, cube.ep);
- index_to_perm(uk, 4, cube.ep + 8);
- for (j = 8; j < 12; j++)
- cube.ep[j] += 8;
- } else if (!strcmp(args->scrtype, "htr")) {
- make_solved(&cube);
- /* TODO */
- } else {
- ep = rand() % FACTORIAL12;
- cp = rand() % FACTORIAL8;
- eo = rand() % POW2TO11;
- co = rand() % POW3TO7;
-
- if (!strcmp(args->scrtype, "eo")) {
- eo = 0;
- } else if (!strcmp(args->scrtype, "corners")) {
- eo = 0;
- ep = 0;
- } else if (!strcmp(args->scrtype, "edges")) {
- co = 0;
- cp = 0;
- }
-
- make_solved(&cube);
- index_to_perm(ep, 12, cube.ep);
- index_to_perm(cp, 8, cube.cp);
- int_to_sum_zero_array(eo, 2, 12, cube.eo);
- int_to_sum_zero_array(co, 3, 8, cube.co);
- }
-
- if (!is_admissible(&cube)) {
- if (!strcmp(args->scrtype, "corners"))
- swap(&cube.cp[UFR], &cube.cp[UFL]);
- else
- swap(&cube.ep[UF], &cube.ep[UB]);
- }
-
- /* TODO: can be optimized for htr and dr using htrfin, drfin */
- scr = solve_2phase(&cube, 1);
-
- if (!strcmp(args->scrtype, "fmc")) {
- aux = new_alg("");
- copy_alg(scr, aux);
- /* Trick to rufify for free: rotate the scramble *
- * so that it does not start with F or end with R */
- for (j = 0; j < NROTATIONS; j++) {
- if (base_move(scr->move[0]) != F &&
- base_move(scr->move[0]) != B &&
- base_move(scr->move[scr->len-1]) != R &&
- base_move(scr->move[scr->len-1]) != L)
- break;
- copy_alg(aux, scr);
- transform_alg(j, scr);
- }
- copy_alg(scr, aux);
- ruf = new_alg("R' U' F");
- copy_alg(ruf, scr);
- compose_alg(scr, aux);
- compose_alg(scr, ruf);
- free_alg(aux);
- free_alg(ruf);
- }
- print_alg(scr, false);
- free_alg(scr);
- }
-}
-
-void
-gen_exec(CommandArgs *args)
-{
-/* TODO:
- int i;
-
- fprintf(stderr, "Generating coordinates...\n");
- fprintf(stderr, "Generating pruning tables...\n");
- for (i = 0; all_pd[i] != NULL; i++)
- genptable(all_pd[i], args->opts->nthreads);
-*/
-
- fprintf(stderr, "Done!\n");
-}
-
-void
-invert_exec(CommandArgs *args)
-{
- Alg *inv;
-
- inv = inverse_alg(args->scramble);
- print_alg(inv, false);
-
- free_alg(inv);
-}
-
-void
-steps_exec(CommandArgs *args)
-{
- int i;
-
- for (i = 0; steps[i] != NULL; i++)
- printf("%-15s %s\n", steps[i]->shortname, steps[i]->name);
-}
-
-void
-commands_exec(CommandArgs *args)
-{
- int i;
-
- for (i = 0; commands[i] != NULL; i++)
- printf("%s\n", commands[i]->usage);
-
-}
-
-void
-freemem_exec(CommandArgs *args)
-{
-/* TODO:
- int i;
-
- for (i = 0; all_pd[i] != NULL; i++)
- free_pd(all_pd[i]);
-
- for (i = 0; all_sd[i] != NULL; i++)
- free_sd(all_sd[i]);
-*/
-}
-
-void
-print_exec(CommandArgs *args)
-{
- Cube c;
-
- make_solved(&c);
- apply_alg(args->scramble, &c);
- print_cube(&c);
-}
-
-void
-twophase_exec(CommandArgs *args)
-{
- Cube c;
- Alg *sol;
-
- make_solved(&c);
- apply_alg(args->scramble, &c);
- sol = solve_2phase(&c, 1);
-
- print_alg(sol, false);
- free_alg(sol);
-}
-
-void
-help_exec(CommandArgs *args)
-{
- if (args->command == NULL) {
- printf(
- "Use the nissy command \"help COMMAND\" for a short "
- "description of a specific command.\n"
- "Use the nissy command \"commands\" for a list of "
- "available commands.\n"
- "See the manual page for more details. The manual"
- " page is available with \"man nissy\" on a UNIX"
- " system (such as Linux or MacOS) or in pdf and html"
- " format in the docs folder.\n"
- "Nissy is available for free at "
- "https://nissy.tronto.net\n"
- );
- } else {
- printf("Command %s: %s\nusage: %s\n", args->command->name,
- args->command->description, args->command->usage);
- }
-}
-
-void
-quit_exec(CommandArgs *args)
-{
- exit(0);
-}
-
-void
-cleanup_exec(CommandArgs *args)
-{
- Alg *alg;
-
- alg = cleanup(args->scramble);
- print_alg(alg, false);
-
- free_alg(alg);
-}
-
-void
-unniss_exec(CommandArgs *args)
-{
- Alg *aux;
-
- aux = unniss(args->scramble);
- print_alg(aux, false);
- free(aux);
-}
-
-void
-version_exec(CommandArgs *args)
-{
- printf(VERSION"\n");
-}
-
-/* Local functions implementation ********************************************/
-
-static bool
-read_scramble(int c, char **v, CommandArgs *args)
-{
- int i, k, n;
- unsigned int j;
- char *algstr;
-
- if (c < 1) {
- fprintf(stderr, "Error: no scramble given?\n");
- return false;
- }
-
- for(n = 0, 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;
-}
-
-static bool
-read_scrtype(CommandArgs *args, char *str)
-{
- int i;
- static char *scrtypes[20] =
- { "eo", "corners", "edges", "fmc", "dr", "htr", NULL };
-
- for (i = 0; scrtypes[i] != NULL; i++) {
- if (!strcmp(scrtypes[i], str)) {
- strcpy(args->scrtype, scrtypes[i]);
- return true;
- }
- }
-
- return false;
-}
-
-static bool
-read_step(CommandArgs *args, char *str)
-{
- int i;
-
- for (i = 0; steps[i] != NULL; i++) {
- if (!strcmp(steps[i]->shortname, str)) {
- args->step = steps[i];
- return true;
- }
- }
-
- return false;
-}
-
-/* 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);
-}
-
-CommandArgs *
-new_args()
-{
- CommandArgs *args = malloc(sizeof(CommandArgs));
-
- args->success = false;
- args->scrstdin = false;
- args->scramble = NULL; /* initialized in read_scramble */
- args->opts = malloc(sizeof(SolveOptions));
-
- /* step and command are static */
- args->step = steps[0]; /* default: first step in list */
- args->command = NULL;
-
- return args;
-}
diff --git a/src/commands.h b/src/commands.h
@@ -1,206 +0,0 @@
-#ifndef COMMANDS_H
-#define COMMANDS_H
-
-#include <time.h>
-
-#include "solve.h"
-#include "steps.h"
-
-void free_args(CommandArgs *args);
-CommandArgs * new_args();
-
-/* Arg parsing functions *****************************************************/
-
-CommandArgs * gen_parse_args(int c, char **v);
-CommandArgs * help_parse_args(int c, char **v);
-CommandArgs * parse_only_scramble(int c, char **v);
-CommandArgs * parse_no_arg(int c, char **v);
-CommandArgs * solve_parse_args(int c, char **v);
-CommandArgs * scramble_parse_args(int c, char **v);
-
-/* Exec functions ************************************************************/
-
-void gen_exec(CommandArgs *args);
-void cleanup_exec(CommandArgs *args);
-void invert_exec(CommandArgs *args);
-void solve_exec(CommandArgs *args);
-void scramble_exec(CommandArgs *args);
-void steps_exec(CommandArgs *args);
-void commands_exec(CommandArgs *args);
-void freemem_exec(CommandArgs *args);
-void print_exec(CommandArgs *args);
-void twophase_exec(CommandArgs *args);
-void help_exec(CommandArgs *args);
-void quit_exec(CommandArgs *args);
-void unniss_exec(CommandArgs *args);
-void version_exec(CommandArgs *args);
-
-/* Commands ******************************************************************/
-
-#ifndef COMMANDS_C
-
-extern Command cleanup_cmd;
-extern Command commands_cmd;
-extern Command freemem_cmd;
-extern Command gen_cmd;
-extern Command help_cmd;
-extern Command invert_cmd;
-extern Command print_cmd;
-extern Command quit_cmd;
-extern Command scramble_cmd;
-extern Command solve_cmd;
-extern Command steps_cmd;
-extern Command unniss_cmd;
-extern Command version_cmd;
-
-extern Command *commands[];
-
-#else
-
-Command
-solve_cmd = {
- .name = "solve",
- .usage = "solve STEP [OPTIONS] SCRAMBLE",
- .description = "Solve a step; see command steps for a list of steps",
- .parse_args = solve_parse_args,
- .exec = solve_exec
-};
-
-Command
-scramble_cmd = {
- .name = "scramble",
- .usage = "scramble [TYPE] [-n N]",
- .description = "Get a random-position scramble",
- .parse_args = scramble_parse_args,
- .exec = scramble_exec,
-};
-
-Command
-gen_cmd = {
- .name = "gen",
- .usage = "gen [-t N]",
- .description = "Generate all tables [using N threads]",
- .parse_args = gen_parse_args,
- .exec = gen_exec
-};
-
-Command
-invert_cmd = {
- .name = "invert",
- .usage = "invert SCRAMBLE]",
- .description = "Invert a scramble",
- .parse_args = parse_only_scramble,
- .exec = invert_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
-freemem_cmd = {
- .name = "freemem",
- .usage = "freemem",
- .description = "free large tables from RAM",
- .parse_args = parse_no_arg,
- .exec = freemem_exec,
-};
-
-Command
-print_cmd = {
- .name = "print",
- .usage = "print SCRAMBLE",
- .description = "Print written description of the cube",
- .parse_args = parse_only_scramble,
- .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
-twophase_cmd = {
- .name = "twophase",
- .usage = "twophase",
- .description = "Find a solution quickly using a 2-phase method",
- .parse_args = parse_only_scramble,
- .exec = twophase_exec,
-};
-
-Command
-quit_cmd = {
- .name = "quit",
- .usage = "quit",
- .description = "Quit nissy",
- .parse_args = parse_no_arg,
- .exec = quit_exec,
-};
-
-Command
-cleanup_cmd = {
- .name = "cleanup",
- .usage = "cleanup SCRAMBLE",
- .description = "Rewrite a scramble using only standard moves (HTM)",
- .parse_args = parse_only_scramble,
- .exec = cleanup_exec,
-};
-
-Command
-unniss_cmd = {
- .name = "unniss",
- .usage = "unniss SCRAMBLE",
- .description = "Rewrite a scramble without NISS",
- .parse_args = parse_only_scramble,
- .exec = unniss_exec,
-};
-
-Command
-version_cmd = {
- .name = "version",
- .usage = "version",
- .description = "print nissy version",
- .parse_args = parse_no_arg,
- .exec = version_exec,
-};
-
-Command *commands[] = {
- &commands_cmd,
- &freemem_cmd,
- &gen_cmd,
- &help_cmd,
- &invert_cmd,
- &print_cmd,
- &quit_cmd,
- &solve_cmd,
- &scramble_cmd,
- &steps_cmd,
- &twophase_cmd,
- &cleanup_cmd,
- &unniss_cmd,
- &version_cmd,
- NULL
-};
-
-#endif
-
-#endif
diff --git a/src/coord.c b/src/coord.c
@@ -14,6 +14,161 @@ static bool write_coord_mtable(Coordinate *coord);
static bool write_coord_sd(Coordinate *coord);
static bool write_coord_ttable(Coordinate *coord);
+/* Utility functions *********************************************************/
+
+int
+factorial(int n)
+{
+ int i, ret = 1;
+
+ if (n < 0)
+ return 0;
+
+ for (i = 1; i <= n; i++)
+ ret *= i;
+
+ return ret;
+}
+
+int
+perm_to_index(int *a, int n)
+{
+ int i, j, c, ret = 0;
+
+ 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;
+}
+
+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);
+}
+
+int
+binomial(int n, int k)
+{
+ if (n < 0 || k < 0 || k > n)
+ return 0;
+
+ return factorial(n) / (factorial(k) * factorial(n-k));
+}
+
+int
+subset_to_index(int *a, int n, int k)
+{
+ int i, ret = 0;
+
+ 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
+index_to_subset(int s, int n, int k, int *r)
+{
+ int i, j, v;
+
+ 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;
+ }
+ }
+}
+
+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;
+}
+
+void
+int_to_digit_array(int a, int b, int n, int *r)
+{
+ int i;
+
+ 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;
+
+ 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
+perm_sign(int *a, int n)
+{
+ int i, j, ret = 0;
+
+ for (i = 0; i < n; i++)
+ for (j = i+1; j < n; j++)
+ ret += (a[i] > a[j]) ? 1 : 0;
+
+ return ret % 2;
+}
+
/* Indexers ******************************************************************/
uint64_t
@@ -35,17 +190,6 @@ index_cp(Cube *cube)
}
uint64_t
-index_cpudsep(Cube *cube)
-{
- int i, c[8];
-
- for (i = 0; i < 8; i++)
- c[i] = cube->cp[i] < 4 ? 0 : 1;
-
- return (uint64_t)subset_to_index(c, 8, 4);
-}
-
-uint64_t
index_epe(Cube *cube)
{
int i, e[4];
@@ -109,17 +253,6 @@ invindex_cp(uint64_t ind, Cube *cube)
}
void
-invindex_cpudsep(uint64_t ind, Cube *cube)
-{
- int i, j, k, c[8];
-
- index_to_subset(ind, 8, 4, c);
- for (i = 0, j = 0, k = 4; i < 8; i++)
- cube->cp[i] = c[i] == 0 ? j++ : k++;
-}
-
-
-void
invindex_epe(uint64_t ind, Cube *cube)
{
int i;
diff --git a/src/coord.h b/src/coord.h
@@ -1,7 +1,33 @@
#ifndef COORD_H
#define COORD_H
-#include "trans.h"
+#include <inttypes.h>
+
+#include "cube.h"
+#include "env.h"
+
+typedef enum { COMP_COORD, SYM_COORD, SYMCOMP_COORD } CoordType;
+typedef struct {
+ int n;
+ uint64_t (*index)(Cube *);
+ void (*to_cube)(uint64_t, Cube *);
+} Indexer;
+typedef struct coordinate {
+ char * name;
+ CoordType type;
+ bool generated;
+ Indexer * i[99];
+ uint64_t max;
+ uint64_t * mtable[NMOVES];
+ uint64_t * ttable[NTRANS];
+ TransGroup * tgrp;
+ struct coordinate * base[2];
+ uint64_t * symclass;
+ uint64_t * symrep;
+ Trans * transtorep;
+ Trans * ttrep_move[NMOVES];
+ uint64_t * selfsim;
+} Coordinate;
void gen_coord(Coordinate *coord);
uint64_t index_coord(Coordinate *coord, Cube *cube,
@@ -18,19 +44,15 @@ uint64_t trans_coord(Coordinate *coord, Trans t, uint64_t ind);
extern Coordinate coord_eofb;
extern Coordinate coord_coud;
extern Coordinate coord_cp;
-extern Coordinate coord_cpudsep;
extern Coordinate coord_epos;
extern Coordinate coord_epe;
extern Coordinate coord_eposepe;
extern Coordinate coord_epud;
extern Coordinate coord_eofbepos;
-extern Coordinate coord_coud_cpudsep;
extern Coordinate coord_eofbepos_sym16;
-extern Coordinate coord_cp_sym16;
-extern Coordinate coord_corners_sym16;
extern Coordinate coord_drud_sym16;
+extern Coordinate coord_cp_sym16;
extern Coordinate coord_drudfin_noE_sym16;
-extern Coordinate coord_nxopt31;
#else
@@ -63,15 +85,6 @@ i_cp = {
.to_cube = invindex_cp,
};
-uint64_t index_cpudsep(Cube *cube);
-void invindex_cpudsep(uint64_t ind, Cube *ret);
-Indexer
-i_cpudsep = {
- .n = BINOM8ON4,
- .index = index_cpudsep,
- .to_cube = invindex_cpudsep,
-};
-
uint64_t index_epos(Cube *cube);
void invindex_epos(uint64_t ind, Cube *ret);
Indexer
@@ -132,13 +145,6 @@ coord_cp = {
};
Coordinate
-coord_cpudsep = {
- .name = "cpudsep",
- .type = COMP_COORD,
- .i = {&i_cpudsep, NULL},
-};
-
-Coordinate
coord_epos = {
.name = "epos",
.type = COMP_COORD,
@@ -153,7 +159,7 @@ coord_epe = {
};
Coordinate
-coord_eposepe = { /* Has to be done by hand, hard compose epos + epe */
+coord_eposepe = {
.name = "eposepe",
.type = COMP_COORD,
.i = {&i_eposepe, NULL},
@@ -173,13 +179,6 @@ coord_eofbepos = {
.i = {&i_epos, &i_eofb, NULL},
};
-Coordinate
-coord_coud_cpudsep = {
- .name = "coud_cpudsep",
- .type = COMP_COORD,
- .i = {&i_coud, &i_cpudsep, NULL},
-};
-
/* Symcoordinates ************************************************************/
Coordinate
@@ -201,13 +200,6 @@ coord_cp_sym16 = {
/* "Symcomp" coordinates *****************************************************/
Coordinate
-coord_corners_sym16 = {
- .name = "corners_sym16",
- .type = SYMCOMP_COORD,
- .base = {&coord_cp_sym16, &coord_coud},
-};
-
-Coordinate
coord_drud_sym16 = {
.name = "drud_sym16",
.type = SYMCOMP_COORD,
@@ -221,13 +213,6 @@ coord_drudfin_noE_sym16 = {
.base = {&coord_cp_sym16, &coord_epud},
};
-Coordinate
-coord_nxopt31 = {
- .name = "nxopt31",
- .type = SYMCOMP_COORD,
- .base = {&coord_eofbepos_sym16, &coord_coud_cpudsep},
-};
-
#endif
#endif
diff --git a/src/cube.c b/src/cube.c
@@ -1,19 +1,55 @@
-#define CUBE_C
-
#include "cube.h"
+static Cube move_array[NMOVES];
+static Alg *rotation_alg[NTRANS/2];
+Move moves_ttable[NTRANS][NMOVES];
+Trans trans_ttable[NTRANS][NTRANS];
+Trans trans_itable[NTRANS];
+
+TransGroup
+tgrp_udfix = {
+ .n = 16,
+ .t = {
+ 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 void
+apply_permutation(int *perm, int *set, int n, int *aux)
+{
+ int i;
+
+ for (i = 0; i < n; i++)
+ aux[i] = set[perm[i]];
+
+ memcpy(set, aux, n * sizeof(int));
+}
+
+static void
+sum_arrays_mod(int *src, int *dst, int n, int m)
+{
+ int i;
+
+ for (i = 0; i < n; i++)
+ dst[i] = (src[i] + dst[i]) % m;
+}
+
void
compose(Cube *c2, Cube *c1)
{
- apply_permutation(c2->ep, c1->ep, 12);
- apply_permutation(c2->ep, c1->eo, 12);
+ int aux[12];
+
+ apply_permutation(c2->ep, c1->ep, 12, aux);
+ apply_permutation(c2->ep, c1->eo, 12, aux);
sum_arrays_mod(c2->eo, c1->eo, 12, 2);
- apply_permutation(c2->cp, c1->cp, 8);
- apply_permutation(c2->cp, c1->co, 8);
- sum_arrays_mod(c2->co, c1->co, 8, 3);
+ apply_permutation(c2->cp, c1->cp, 8, aux);
+ apply_permutation(c2->cp, c1->co, 8, aux);
- apply_permutation(c2->xp, c1->xp, 6);
+ sum_arrays_mod(c2->co, c1->co, 8, 3);
}
void
@@ -23,27 +59,6 @@ copy_cube(Cube *src, Cube *dst)
memcpy(dst->eo, src->eo, 12 * sizeof(int));
memcpy(dst->cp, src->cp, 8 * sizeof(int));
memcpy(dst->co, src->co, 8 * sizeof(int));
- memcpy(dst->xp, src->xp, 6 * sizeof(int));
-}
-
-bool
-equal(Cube *c1, Cube *c2)
-{
- int i;
-
- for (i = 0; i < 12; i++)
- if (c1->ep[i] != c2->ep[i] || c1->eo[i] != c2->eo[i])
- return false;
-
- for (i = 0; i < 8; i++)
- if (c1->cp[i] != c2->cp[i] || c1->co[i] != c2->co[i])
- return false;
-
- for (i = 0; i < 6; i++)
- if (c1->xp[i] != c2->xp[i])
- return false;
-
- return true;
}
void
@@ -63,43 +78,22 @@ invert_cube(Cube *cube)
cube->cp[aux.cp[i]] = i;
cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3;
}
-
- for (i = 0; i < 6; i++)
- cube->xp[aux.xp[i]] = i;
}
bool
-is_admissible(Cube *c) {
- bool perm;
- int sign, i;
- int sum_e, sum_c;
-
- perm = is_perm(c->ep, 12) && is_perm(c->cp, 8) && is_perm(c->xp, 6);
-
- sign = perm_sign(c->ep,12) + perm_sign(c->cp,8) + perm_sign(c->xp,6);
+is_solved(Cube *cube)
+{
+ int i;
- for (i = 0, sum_e = 0; i < 12; i++)
- if (c->eo[i] > 1)
+ for (i = 0; i < 12; i++)
+ if (cube->eo[i] != 0 || cube->ep[i] != i)
return false;
- else
- sum_e += c->eo[i];
- for (i = 0, sum_c = 0; i < 8; i++)
- if (c->co[i] > 2)
+ for (i = 0; i < 8; i++)
+ if (cube->co[i] != 0 || cube->cp[i] != i)
return false;
- else
- sum_c += c->co[i];
- return (perm && sign % 2 == 0 && sum_e % 2 == 0 && sum_c % 2 == 0);
-}
-
-bool
-is_solved(Cube *cube)
-{
- Cube solved_cube;
- make_solved(&solved_cube);
-
- return equal(cube, &solved_cube);
+ return true;
}
void
@@ -111,46 +105,286 @@ make_solved(Cube *cube)
memset(cube->eo, 0, 12 * sizeof(int));
memcpy(cube->cp, sorted, 8 * sizeof(int));
memset(cube->co, 0, 8 * sizeof(int));
- memcpy(cube->xp, sorted, 6 * sizeof(int));
}
void
-print_cube(Cube *cube)
+apply_alg(Alg *alg, Cube *cube)
+{
+ Cube aux;
+ int i;
+
+ copy_cube(cube, &aux);
+ make_solved(cube);
+
+ for (i = 0; i < alg->len; i++)
+ if (alg->inv[i])
+ apply_move(alg->move[i], cube);
+
+ invert_cube(cube);
+ compose(&aux, cube);
+
+ for (i = 0; i < alg->len; i++)
+ if (!alg->inv[i])
+ apply_move(alg->move[i], cube);
+}
+
+void
+apply_move(Move m, Cube *cube)
+{
+ compose(&move_array[m], cube);
+}
+
+void
+apply_trans(Trans t, Cube *cube)
+{
+ Cube aux;
+ Alg *inv;
+ int i;
+
+ static Cube mirror_cube = {
+ .ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL,
+ [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL,
+ [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL },
+ .cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL,
+ [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL },
+ };
+
+ inv = inverse_alg(rotation_alg[t % (NTRANS/2)]);
+ copy_cube(cube, &aux);
+ make_solved(cube);
+
+ if (t >= NTRANS/2)
+ compose(&mirror_cube, cube);
+ apply_alg(inv, cube);
+ compose(&aux, cube);
+ apply_alg(rotation_alg[t % (NTRANS/2)], cube);
+ if (t >= NTRANS/2) {
+ compose(&mirror_cube, cube);
+ for (i = 0; i < 8; i++)
+ cube->co[i] = (3 - cube->co[i]) % 3;
+ }
+
+ free_alg(inv);
+}
+
+Trans
+inverse_trans(Trans t)
+{
+ return trans_itable[t];
+}
+
+void
+transform_alg(Trans t, Alg *alg)
{
- 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"
+ int i;
+
+ for (i = 0; i < alg->len; i++)
+ alg->move[i] = transform_move(t, alg->move[i]);
+}
+
+Move
+transform_move(Trans t, Move m)
+{
+ return moves_ttable[t][m];
+}
+
+Trans
+transform_trans(Trans t, Trans m)
+{
+ return trans_ttable[t][m];
+}
+
+/* Initialization ************************************************************/
+
+static void
+init_moves() {
+ Move m;
+ Alg *equiv_alg[NMOVES];
+
+ /* Moves are represented as cubes and applied using compose().
+ * Every move is translated to a an <U, x, y> alg before filling
+ * the transition tables. */
+ 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 "
};
- static char corner_string[8][7] = {
- [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR",
- [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR"
+ const Cube mcu = {
+ .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
+ .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, 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"
+ const Cube mcx = {
+ .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
+ .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
+ .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
+ .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
+ [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 },
};
- for (int i = 0; i < 12; i++)
- printf(" %s ", edge_string[cube->ep[i]]);
- printf("\n");
+ const Cube mcy = {
+ .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL },
+ .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 },
+ .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL },
+ };
- for (int i = 0; i < 12; i++)
- printf(" %" PRIu8 " ", cube->eo[i]);
- printf("\n");
+ move_array[U] = mcu;
+ move_array[x] = mcx;
+ move_array[y] = mcy;
+
+ for (m = 0; m < NMOVES; m++)
+ equiv_alg[m] = new_alg(equiv_alg_string[m]);
+
+ for (m = 0; m < NMOVES; m++) {
+ switch (m) {
+ case NULLMOVE:
+ make_solved(&move_array[m]);
+ break;
+ case U:
+ case x:
+ case y:
+ break;
+ default:
+ make_solved(&move_array[m]);
+ apply_alg(equiv_alg[m], &move_array[m]);
+ break;
+ }
+ }
- for (int i = 0; i < 8; i++)
- printf("%s ", corner_string[cube->cp[i]]);
- printf("\n");
+ for (m = 0; m < NMOVES; m++)
+ free_alg(equiv_alg[m]);
+}
- for (int i = 0; i < 8; i++)
- printf(" %" PRIu8 " ", cube->co[i]);
- printf("\n");
+static void
+init_trans() {
- for (int i = 0; i < 6; i++)
- printf(" %s ", center_string[cube->xp[i]]);
- printf("\n");
+ int i;
+ Alg *nonsym_alg, *nonsym_inv;
+ Cube aux, cube;
+ Move mi, move;
+ Trans t, u, v;
+
+ char rotation_alg_string[100][NTRANS/2] = {
+ [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",
+ };
+
+ for (i = 0; i < NTRANS/2; i++)
+ rotation_alg[i] = new_alg(rotation_alg_string[i]);
+
+ for (t = 0; t < NTRANS; t++) {
+ for (mi = 0; mi < NMOVES; mi++) {
+ make_solved(&aux);
+ apply_move(mi, &aux);
+ apply_trans(t, &aux);
+ for (move = 0; move < NMOVES; move++) {
+ copy_cube(&aux, &cube);
+ apply_move(inverse_move(move), &cube);
+ if (is_solved(&cube)) {
+ moves_ttable[t][mi] = move;
+ break;
+ }
+ }
+ }
+ }
+
+ nonsym_alg = new_alg("R' U' F");
+ nonsym_inv = inverse_alg(nonsym_alg);
+
+ for (t = 0; t < NTRANS; t++) {
+ for (u = 0; u < NTRANS; u++) {
+ make_solved(&aux);
+ apply_alg(nonsym_alg, &aux);
+ apply_trans(u, &aux);
+ apply_trans(t, &aux);
+ for (v = 0; v < NTRANS; v++) {
+ copy_cube(&aux, &cube);
+ apply_trans(v, &cube);
+ apply_alg(nonsym_inv, &cube);
+ if (is_solved(&cube)) {
+ /* This is the inverse of the correct
+ value, it will be inverted later */
+ trans_ttable[t][u] = v;
+ if (v == uf)
+ trans_itable[t] = u;
+ break;
+ }
+ }
+ }
+ }
+ for (t = 0; t < NTRANS; t++)
+ for (u = 0; u < NTRANS; u++)
+ trans_ttable[t][u] = trans_itable[trans_ttable[t][u]];
+
+
+ free_alg(nonsym_alg);
+ free_alg(nonsym_inv);
+}
+
+void
+init_cube()
+{
+ init_moves();
+ init_trans();
}
diff --git a/src/cube.h b/src/cube.h
@@ -2,19 +2,80 @@
#define CUBE_H
#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
-#include "cubetypes.h"
-#include "env.h"
-#include "utils.h"
+#define false 0
+#define true 1
+#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 NMOVES 55
+#define NTRANS 48
+#define MIN(a,b) (((a) < (b)) ? (a) : (b))
+#define MAX(a,b) (((a) > (b)) ? (a) : (b))
+
+typedef int bool;
+typedef enum edge { UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR } Edge;
+typedef enum { UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR } Corner;
+typedef enum {
+ 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,
+} Move;
+typedef enum {
+ 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,
+} Trans;
+
+typedef struct { int ep[12]; int eo[12]; int cp[8]; int co[8]; } Cube;
+typedef struct { Move *move; bool *inv; int len; int allocated; } Alg;
+typedef struct { int n; Trans t[NTRANS]; } TransGroup;
+
+extern TransGroup tgrp_udfix;
void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */
void copy_cube(Cube *src, Cube *dst);
-bool equal(Cube *c1, Cube *c2);
void invert_cube(Cube *cube);
-bool is_admissible(Cube *cube);
bool is_solved(Cube *cube);
void make_solved(Cube *cube);
-void print_cube(Cube *cube);
-#endif
+void apply_alg(Alg *alg, Cube *cube);
+void apply_move(Move m, Cube *cube);
+void apply_trans(Trans t, Cube *cube);
+Trans inverse_trans(Trans t);
+void transform_alg(Trans t, Alg *alg);
+Move transform_move(Trans t, Move m);
+Trans transform_trans(Trans t, Trans m);
+
+void init_cube();
+
+
+#endif
diff --git a/src/cubetypes.h b/src/cubetypes.h
@@ -1,360 +0,0 @@
-#ifndef CUBETYPES_H
-#define CUBETYPES_H
-
-#include <stdbool.h>
-#include <inttypes.h>
-#include <pthread.h>
-
-#define NMOVES 55 /* Actually 54, but one is NULLMOVE */
-#define NTRANS 48
-#define NROTATIONS 24
-#define entry_group_t uint8_t /* For pruning tables */
-
-#define MAX_N_COORD 6
-
-/* Enums *********************************************************************/
-
-typedef enum
-center
-{
- U_center, D_center,
- R_center, L_center,
- F_center, B_center
-} Center;
-
-typedef enum
-corner
-{
- UFR, UFL, UBL, UBR,
- DFR, DFL, DBL, DBR
-} Corner;
-
-typedef enum
-coordtype
-{
- COMP_COORD, SYM_COORD, SYMCOMP_COORD
-} CoordType;
-
-typedef enum
-edge
-{
- UF, UL, UB, UR,
- DF, DL, DB, DR,
- FR, FL, BL, BR
-} Edge;
-
-typedef 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,
-} Move;
-
-typedef 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,
-} Trans;
-
-
-/* Typedefs ******************************************************************/
-
-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 dfsarg DfsArg;
-typedef struct indexer Indexer;
-typedef struct movable Movable;
-typedef struct moveset Moveset;
-typedef struct pdgendata PDGenData;
-typedef struct prunedata PruneData;
-typedef struct solveoptions SolveOptions;
-typedef struct step Step;
-typedef struct stepalt StepAlt;
-typedef struct symdata SymData;
-typedef struct threaddatasolve ThreadDataSolve;
-typedef struct threaddatagenpt ThreadDataGenpt;
-typedef struct transgroup TransGroup;
-
-typedef bool (*Checker) (Cube *);
-typedef bool (*Validator) (Alg *);
-typedef void (*Exec) (CommandArgs *);
-typedef CommandArgs * (*ArgParser) (int, char **);
-typedef int (*TransFinder) (uint64_t, Trans *);
-
-
-/* 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
-{
- 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 */
- int n;
- char scrtype[20];
- bool scrstdin;
- bool header;
-};
-
-struct
-coordinate
-{
- char * name;
- CoordType type;
- bool generated;
- Indexer * i[99];
- uint64_t max;
- uint64_t * mtable[NMOVES];
- uint64_t * ttable[NTRANS];
- TransGroup * tgrp;
- Coordinate * base[2];
- uint64_t * symclass;
- uint64_t * symrep;
- Trans * transtorep;
- Trans * ttrep_move[NMOVES];
- uint64_t * selfsim;
-};
-
-struct
-cube
-{
- int ep[12];
- int eo[12];
- int cp[8];
- int co[8];
- int xp[6];
-};
-
-struct
-movable
-{
- uint64_t val;
- Trans t;
-};
-
-struct
-dfsarg
-{
- Cube * cube;
- Movable ind[MAX_N_COORD];
- Trans t;
- StepAlt * sa;
- SolveOptions * opts;
- int d;
- int bound;
- bool niss;
- Move last[2];
- Move lastinv[2];
- AlgList * sols;
- pthread_mutex_t * sols_mutex;
- Alg * current_alg;
-};
-
-struct
-indexer
-{
- int n;
- uint64_t (*index)(Cube *);
- void (*to_cube)(uint64_t, Cube *);
-};
-
-struct
-moveset
-{
- char * name;
- bool (*allowed)(Move);
- bool (*allowed_next)(Move, Move, Move);
- Move sorted_moves[NMOVES+1];
- uint64_t mask[NMOVES][NMOVES];
-};
-
-struct
-pdgendata
-{
- Coordinate * coord;
- Moveset * moveset;
- bool compact;
- PruneData * pd;
-};
-
-struct
-prunedata
-{
- entry_group_t * ptable;
- uint64_t n;
- Coordinate * coord;
- Moveset * moveset;
- bool compact;
- int base;
- uint64_t count[16];
- uint64_t fbmod;
-};
-
-struct
-solveoptions
-{
- int min_moves;
- int max_moves;
- int max_solutions;
- int nthreads;
- int optimal;
- bool can_niss;
- bool verbose;
- bool all;
- bool print_number;
- bool count_only;
-};
-
-struct
-step
-{
- char * shortname;
- char * name;
- StepAlt * alt[99];
- Trans t[99];
- char * ready_msg;
-};
-
-struct
-stepalt
-{
- Checker ready;
- bool final;
- Moveset * moveset;
- /* Just a comment, (TODO: remove this): moveset is really a stepalt
- * property, because for example we may want to define a "fingertrick
- * friendly ZBLL" step, where we allow either <R U D> or <R U F> as
- * movesets (or similar) */
- int n_coord;
- Coordinate * coord[MAX_N_COORD];
- Trans coord_trans[MAX_N_COORD];
- PruneData * pd[MAX_N_COORD];
- bool compact_pd[MAX_N_COORD];
- Coordinate * fallback_coord[MAX_N_COORD];
- PruneData * fallback_pd[MAX_N_COORD];
- uint64_t fbmod[MAX_N_COORD];
- int n_dbtrick;
- int dbtrick[MAX_N_COORD][3];
- Validator is_valid;
-};
-
-/*
-struct
-symdata
-{
- char * filename;
- bool generated;
- Coordinate * coord;
- Coordinate * sym_coord;
- int ntrans;
- Trans * trans;
- uint64_t * class;
- uint64_t * unsym;
- Trans * transtorep;
- uint64_t * selfsim;
-};
-*/
-
-
-struct
-threaddatasolve
-{
- DfsArg arg;
- int thid;
- AlgList * start;
- AlgListNode ** node;
- pthread_mutex_t * start_mutex;
-};
-
-struct
-threaddatagenpt
-{
- int thid;
- int nthreads;
- PruneData * pd;
- int d;
- int nchunks;
- pthread_mutex_t ** mutex;
- pthread_mutex_t * upmutex;
-};
-
-struct
-transgroup
-{
- int n;
- Trans t[NTRANS];
-};
-
-#endif
diff --git a/src/env.c b/src/env.c
@@ -2,6 +2,10 @@
#include "env.h"
+typedef int bool;
+#define true 1
+#define false 0
+
bool initialized_env = false;
char *tabledir;
diff --git a/src/env.h b/src/env.h
@@ -1,7 +1,6 @@
#ifndef ENV_H
#define ENV_H
-#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
diff --git a/src/main.c b/src/main.c
@@ -0,0 +1,85 @@
+#include "solve.h"
+
+static Alg *
+read_scramble(int c, char **v)
+{
+ int i, k, n;
+ unsigned int j;
+ char *algstr;
+ Alg *scr;
+
+ if (c < 1) {
+ fprintf(stderr, "Error: no scramble given\n");
+ return false;
+ }
+
+ for(n = 0, 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;
+
+ scr = new_alg(algstr);
+
+ free(algstr);
+
+ return scr;
+}
+
+int
+main(int argc, char *argv[])
+{
+ int i, m;
+ long val;
+ Alg *scramble;
+ AlgList *sols;
+ Cube c;
+ SolutionType t;
+
+ if (argc < 2) {
+ fprintf(stderr, "Not enough arguments given\n");
+ return -1;
+ }
+
+ m = 0;
+ t = NORMAL;
+ scramble = new_alg("");
+
+ init_env();
+ init_cube();
+
+ for (i = 2; i < argc; i++) {
+ if (!strcmp(argv[i], "-m") && i+1 < argc) {
+ val = strtol(argv[++i], NULL, 10);
+ if (val < 0 || val > 100) {
+ fprintf(stderr, "Invalid number of moves\n");
+ return 2;
+ }
+ m = val;
+ } else if (!strcmp(argv[i], "-I")) {
+ t = INVERSE;
+ } else if (!strcmp(argv[i], "-N")) {
+ t = NISS;
+ } else {
+ break;
+ }
+ }
+
+ scramble = read_scramble(argc - i, &argv[i]);
+ if (scramble->len <= 0) {
+ fprintf(stderr, "Cannot read scramble\n");
+ return 4;
+ }
+
+ make_solved(&c);
+ apply_alg(scramble, &c);
+ sols = solve(&c, argv[1], m, t, uf); /* TODO: trans */
+ print_alglist(sols);
+ free_alglist(sols);
+
+ return 0;
+}
diff --git a/src/moves.c b/src/moves.c
@@ -1,283 +0,0 @@
-#define MOVES_C
-
-#include "moves.h"
-
-/* Local functions ***********************************************************/
-
-static void cleanup_aux(Alg *alg, Alg *ret, bool inv);
-
-/* Tables and other data *****************************************************/
-
-/* Moves are represented as cubes and applied using compose(). Every move is *
- * translated to a an <U, x, y> alg before filling the transition tables. *
- * See init_moves(). */
-
-static Cube move_array[NMOVES];
-
-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 "
-};
-
-
-/* Public functions **********************************************************/
-
-void
-apply_alg(Alg *alg, Cube *cube)
-{
- Cube aux;
- int i;
-
- copy_cube(cube, &aux);
- make_solved(cube);
-
- for (i = 0; i < alg->len; i++)
- if (alg->inv[i])
- apply_move(alg->move[i], cube);
-
- invert_cube(cube);
- compose(&aux, cube);
-
- for (i = 0; i < alg->len; i++)
- if (!alg->inv[i])
- apply_move(alg->move[i], cube);
-}
-
-void
-apply_move(Move m, Cube *cube)
-{
- compose(&move_array[m], cube);
-}
-
-Alg *
-cleanup(Alg *alg)
-{
- int i, j, k, b[2], n, L;
- Move bb, m;
- Alg *ret;
-
- ret = new_alg("");
- cleanup_aux(alg, ret, false);
- cleanup_aux(alg, ret, true);
-
- do {
- for (i = 0, j = 0, n = 0; i < ret->len; i = j) {
- if (ret->move[i] > B3) {
- ret->move[n] = ret->move[i];
- ret->inv[n] = ret->inv[i];
- n++;
- j++;
- continue;
- }
-
- bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6;
- while (j < ret->len &&
- ret->move[j] <= B3 &&
- ret->inv[j] == ret->inv[i] &&
- 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb)
- j++;
-
- for (k = i, b[0] = 0, b[1] = 0; k < j; k++) {
- m = ret->move[k];
- if (base_move(m) == bb)
- b[0] = (b[0]+1+m-base_move(m)) % 4;
- else
- b[1] = (b[1]+1+m-base_move(m)) % 4;
- }
-
- for (k = 0; k < 2; k++) {
- if (b[k] != 0) {
- ret->move[n] = bb + b[k] - 1 + 3*k;
- ret->inv[n] = ret->inv[i];
- n++;
- }
- }
- }
-
- L = ret->len;
- ret->len = n;
- } while (L != n);
-
- return ret;
-}
-
-static void
-cleanup_aux(Alg *alg, Alg *ret, bool inv)
-{
- int i, j;
- Cube c, d;
- Move m;
- Alg *equiv_alg;
-
- make_solved(&c);
- for (i = 0; i < alg->len; i++) {
- if (alg->inv[i] != inv)
- continue;
-
- equiv_alg = new_alg(equiv_alg_string[alg->move[i]]);
-
- for (j = 0; j < equiv_alg->len; j++)
- if (equiv_alg->move[j] == U)
- append_move(ret, 3 * c.xp[U_center] + 1, inv);
- else
- apply_move(equiv_alg->move[j], &c);
-
- free_alg(equiv_alg);
- }
-
- m = NULLMOVE;
- switch (c.xp[F_center]) {
- case U_center:
- m = x3;
- break;
- case D_center:
- m = x;
- break;
- case R_center:
- m = y;
- break;
- case L_center:
- m = y3;
- break;
- case B_center:
- if (c.xp[U_center] == U_center)
- m = y2;
- else
- m = x2;
- break;
- default:
- break;
- }
-
- make_solved(&d);
- apply_move(m, &d);
- if (m != NULLMOVE)
- append_move(ret, m, inv);
-
- m = NULLMOVE;
- if (c.xp[U_center] == d.xp[D_center]) {
- m = z2;
- } else if (c.xp[U_center] == d.xp[R_center]) {
- m = z3;
- } else if (c.xp[U_center] == d.xp[L_center]) {
- m = z;
- }
- if (m != NULLMOVE)
- append_move(ret, m, inv);
-}
-
-void
-init_moves() {
- static bool initialized = false;
- if (initialized)
- return;
- initialized = true;
-
- Move m;
- Alg *equiv_alg[NMOVES];
-
- static const Cube mcu = {
- .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
- .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR },
- };
- static const Cube mcx = {
- .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
- .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
- .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
- .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
- [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 },
- .xp = { F_center, B_center, R_center,
- L_center, D_center, U_center },
- };
- static const Cube mcy = {
- .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL },
- .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 },
- .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL },
- .xp = { U_center, D_center, B_center,
- F_center, R_center, L_center },
- };
-
- move_array[U] = mcu;
- move_array[x] = mcx;
- move_array[y] = mcy;
-
- for (m = 0; m < NMOVES; m++)
- equiv_alg[m] = new_alg(equiv_alg_string[m]);
-
- for (m = 0; m < NMOVES; m++) {
- switch (m) {
- case NULLMOVE:
- make_solved(&move_array[m]);
- break;
- case U:
- case x:
- case y:
- break;
- default:
- make_solved(&move_array[m]);
- apply_alg(equiv_alg[m], &move_array[m]);
- break;
- }
- }
-
- for (m = 0; m < NMOVES; m++)
- free_alg(equiv_alg[m]);
-}
-
diff --git a/src/moves.h b/src/moves.h
@@ -1,14 +0,0 @@
-#ifndef MOVES_H
-#define MOVES_H
-
-#include "alg.h"
-#include "cube.h"
-#include "env.h"
-
-void apply_alg(Alg *alg, Cube *cube);
-void apply_move(Move m, Cube *cube);
-Alg * cleanup(Alg *alg);
-
-void init_moves();
-
-#endif
diff --git a/src/pruning.c b/src/pruning.c
@@ -5,35 +5,21 @@
#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t))
-static int findchunk(PruneData *pd, int nchunks, uint64_t i);
-static void genptable_bfs(PruneData *pd, int d, int nt, int nc);
+static void genptable_bfs(PruneData *pd, int d);
+static void fixnasty(PruneData *pd, uint64_t i, int d);
static void genptable_compress(PruneData *pd);
-static void genptable_fixnasty(PruneData *pd, int d, int nthreads);
static void genptable_setbase(PruneData *pd);
-static void * instance_bfs(void *arg);
-static void * instance_fixnasty(void *arg);
static void ptable_update(PruneData *pd, uint64_t ind, int m);
static bool read_ptable_file(PruneData *pd);
static bool write_ptable_file(PruneData *pd);
PDGenData *active_pdg[256];
-int
-findchunk(PruneData *pd, int nchunks, uint64_t i)
-{
- uint64_t chunksize;
-
- chunksize = pd->coord->max / (uint64_t)nchunks;
- chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP);
-
- return MIN(nchunks-1, (int)(i / chunksize));
-}
-
PruneData *
-genptable(PDGenData *pdg, int nthreads)
+genptable(PDGenData *pdg)
{
bool compact;
- int d, nchunks, i;
+ int d, i;
uint64_t oldn, sz;
PruneData *pd;
@@ -59,25 +45,11 @@ genptable(PDGenData *pdg, int nthreads)
if (read_ptable_file(pd))
goto genptable_done;
- if (nthreads < 4) {
- fprintf(stderr,
- "--- Warning ---\n"
- "You are using only %d threads to generate the pruning"
- "tables. This can take a while.\n"
- "Unless you did this intentionally, you should re-run"
- "this command with `-t 4' or more.\n"
- "---------------\n\n", nthreads
- );
- }
-
-
/* For the first steps we proceed the same way for compact and not */
compact = pd->compact;
pd->compact = false;
- nchunks = MIN(ptablesize(pd), 100000);
- fprintf(stderr, "Generating pt_%s_%s with %d threads\n",
- pd->coord->name, pd->moveset->name, nthreads);
+ fprintf(stderr, "Generating pt_%s\n", pd->coord->name);
memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t));
for (i = 0; i < 16; i++)
@@ -86,15 +58,14 @@ genptable(PDGenData *pdg, int nthreads)
ptable_update(pd, 0, 0);
pd->n = 1;
oldn = 0;
- genptable_fixnasty(pd, 0, nthreads);
+ fixnasty(pd, 0, 0);
fprintf(stderr, "Depth %d done, generated %"
PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
0, pd->n - oldn, pd->n, pd->coord->max);
oldn = pd->n;
pd->count[0] = pd->n;
for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
- genptable_bfs(pd, d, nthreads, nchunks);
- genptable_fixnasty(pd, d+1, nthreads);
+ genptable_bfs(pd, d);
fprintf(stderr, "Depth %d done, generated %"
PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
d+1, pd->n - oldn, pd->n, pd->coord->max);
@@ -122,37 +93,45 @@ genptable_done:
}
static void
-genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
+genptable_bfs(PruneData *pd, int d)
{
- int i;
- pthread_t t[nthreads];
- ThreadDataGenpt td[nthreads];
- pthread_mutex_t *mtx[nchunks], *upmtx;
-
- upmtx = malloc(sizeof(pthread_mutex_t));
- pthread_mutex_init(upmtx, NULL);
- for (i = 0; i < nchunks; i++) {
- mtx[i] = malloc(sizeof(pthread_mutex_t));
- pthread_mutex_init(mtx[i], NULL);
+ uint64_t i, ii;
+ int pval;
+ Move m;
+
+ for (i = 0; i < pd->coord->max; i++) {
+ pval = ptableval(pd, i);
+ if (pval != d)
+ continue;
+ for (m = U; m <= B3; m++) {
+ if (!pd->moveset(m))
+ continue;
+ ii = move_coord(pd->coord, m, i, NULL);
+ ptable_update(pd, ii, d+1);
+ fixnasty(pd, ii, d+1);
+ }
}
+}
- for (i = 0; i < nthreads; i++) {
- td[i].thid = i;
- td[i].nthreads = nthreads;
- td[i].pd = pd;
- td[i].d = d;
- td[i].nchunks = nchunks;
- td[i].mutex = mtx;
- td[i].upmutex = upmtx;
- pthread_create(&t[i], NULL, instance_bfs, &td[i]);
- }
+static void
+fixnasty(PruneData *pd, uint64_t i, int d)
+{
+ uint64_t ii, ss, M;
+ int j;
+ Trans t;
- for (i = 0; i < nthreads; i++)
- pthread_join(t[i], NULL);
+ if (pd->coord->type != SYMCOMP_COORD)
+ return;
- free(upmtx);
- for (i = 0; i < nchunks; i++)
- free(mtx[i]);
+ M = pd->coord->base[1]->max;
+ ss = pd->coord->base[0]->selfsim[i/M];
+ for (j = 0; j < pd->coord->base[0]->tgrp->n; j++) {
+ t = pd->coord->base[0]->tgrp->t[j];
+ if (t == uf || !(ss & ((uint64_t)1<<t)))
+ continue;
+ ii = trans_coord(pd->coord, t, i);
+ ptable_update(pd, ii, d);
+ }
}
static void
@@ -181,34 +160,6 @@ genptable_compress(PruneData *pd)
}
static void
-genptable_fixnasty(PruneData *pd, int d, int nthreads)
-{
- int i;
- pthread_t t[nthreads];
- ThreadDataGenpt td[nthreads];
- pthread_mutex_t *upmtx;
-
- if (pd->coord->type != SYMCOMP_COORD)
- return;
-
- upmtx = malloc(sizeof(pthread_mutex_t));
- pthread_mutex_init(upmtx, NULL);
- for (i = 0; i < nthreads; i++) {
- td[i].thid = i;
- td[i].nthreads = nthreads;
- td[i].pd = pd;
- td[i].d = d;
- td[i].upmutex = upmtx;
- pthread_create(&t[i], NULL, instance_fixnasty, &td[i]);
- }
-
- for (i = 0; i < nthreads; i++)
- pthread_join(t[i], NULL);
-
- free(upmtx);
-}
-
-static void
genptable_setbase(PruneData *pd)
{
int i;
@@ -224,99 +175,12 @@ genptable_setbase(PruneData *pd)
}
}
-static void *
-instance_bfs(void *arg)
-{
- ThreadDataGenpt *td;
- uint64_t i, ii, blocksize, rmin, rmax, updated;
- int j, pval, ichunk;
- Move *ms;
-
- td = (ThreadDataGenpt *)arg;
- ms = td->pd->moveset->sorted_moves;
- blocksize = td->pd->coord->max / (uint64_t)td->nthreads;
- rmin = ((uint64_t)td->thid) * blocksize;
- rmax = td->thid == td->nthreads - 1 ?
- td->pd->coord->max :
- ((uint64_t)td->thid + 1) * blocksize;
-
- updated = 0;
- for (i = rmin; i < rmax; i++) {
- ichunk = findchunk(td->pd, td->nchunks, i);
- pthread_mutex_lock(td->mutex[ichunk]);
- pval = ptableval(td->pd, i);
- pthread_mutex_unlock(td->mutex[ichunk]);
- if (pval == td->d) {
- for (j = 0; ms[j] != NULLMOVE; j++) {
- /* ii = td->pd->coord->move(ms[j], i); */
- ii = move_coord(td->pd->coord, ms[j], i, NULL);
- ichunk = findchunk(td->pd, td->nchunks, ii);
- pthread_mutex_lock(td->mutex[ichunk]);
- pval = ptableval(td->pd, ii);
- if (pval > td->d+1) {
- ptable_update(td->pd, ii, td->d+1);
- updated++;
- }
- pthread_mutex_unlock(td->mutex[ichunk]);
- }
- }
- }
-
- pthread_mutex_lock(td->upmutex);
- td->pd->n += updated;
- pthread_mutex_unlock(td->upmutex);
-
- return NULL;
-}
-
-static void *
-instance_fixnasty(void *arg)
-{
- ThreadDataGenpt *td;
- uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M;
- int j;
- Trans t;
-
- td = (ThreadDataGenpt *)arg;
-
- /* We know type = SYMCOMP_COORD */
- M = td->pd->coord->base[1]->max;
- blocksize = (td->pd->coord->base[0]->max / td->nthreads) * M;
- rmin = ((uint64_t)td->thid) * blocksize;
- rmax = td->thid == td->nthreads - 1 ?
- td->pd->coord->max :
- ((uint64_t)td->thid + 1) * blocksize;
-
- updated = 0;
- for (i = rmin; i < rmax; i++) {
- if (ptableval(td->pd, i) == td->d) {
- ss = td->pd->coord->base[0]->selfsim[i/M];
- for (j = 0; j < td->pd->coord->base[0]->tgrp->n; j++) {
- t = td->pd->coord->base[0]->tgrp->t[j];
- if (t == uf || !(ss & ((uint64_t)1<<t)))
- continue;
- ii = trans_coord(td->pd->coord, t, i);
- if (ptableval(td->pd, ii) > td->d) {
- ptable_update(td->pd, ii, td->d);
- updated++;
- }
- }
- }
- }
-
- pthread_mutex_lock(td->upmutex);
- td->pd->n += updated;
- pthread_mutex_unlock(td->upmutex);
-
- return NULL;
-}
-
void
print_ptable(PruneData *pd)
{
uint64_t i;
- printf("Table %s_%s\n", pd->coord->name, pd->moveset->name);
+ printf("Table %s\n", pd->coord->name);
printf("Base value: %d\n", pd->base);
for (i = 0; i < 16; i++)
printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
@@ -339,12 +203,15 @@ ptable_update(PruneData *pd, uint64_t ind, int n)
entry_group_t mask;
uint64_t i;
+ if (ptableval(pd, ind) <= n)
+ return;
+
sh = 4 * (ind % ENTRIES_PER_GROUP);
mask = ((entry_group_t)15) << sh;
i = ind/ENTRIES_PER_GROUP;
-
pd->ptable[i] &= ~mask;
pd->ptable[i] |= (((entry_group_t)n)&15) << sh;
+ pd->n++;
}
int
@@ -382,8 +249,6 @@ read_ptable_file(PruneData *pd)
strcpy(fname, tabledir);
strcat(fname, "/pt_");
strcat(fname, pd->coord->name);
- strcat(fname, "_");
- strcat(fname, pd->moveset->name);
if ((f = fopen(fname, "rb")) == NULL)
return false;
@@ -411,8 +276,6 @@ write_ptable_file(PruneData *pd)
strcpy(fname, tabledir);
strcat(fname, "/pt_");
strcat(fname, pd->coord->name);
- strcat(fname, "_");
- strcat(fname, pd->moveset->name);
if ((f = fopen(fname, "wb")) == NULL)
return false;
diff --git a/src/pruning.h b/src/pruning.h
@@ -3,8 +3,28 @@
#include "coord.h"
+#define entry_group_t uint8_t
+
+typedef bool (Moveset)(Move);
+typedef struct {
+ entry_group_t * ptable;
+ uint64_t n;
+ Coordinate * coord;
+ Moveset * moveset;
+ bool compact;
+ int base;
+ uint64_t count[16];
+ uint64_t fbmod;
+} PruneData;
+typedef struct {
+ Coordinate * coord;
+ Moveset * moveset;
+ bool compact;
+ PruneData * pd;
+} PDGenData;
+
void free_pd(PruneData *pd);
-PruneData * genptable(PDGenData *data, int nthreads);
+PruneData * genptable(PDGenData *data);
void print_ptable(PruneData *pd);
uint64_t ptablesize(PruneData *pd);
int ptableval(PruneData *pd, uint64_t ind);
diff --git a/src/shell.c b/src/shell.c
@@ -1,189 +0,0 @@
-#define SHELL_C
-
-#include "shell.h"
-
-static void cleanwhitespaces(char *line);
-static int parseline(char *line, char **v);
-
-bool
-checkfiles()
-{
- /* TODO: add more checks (other files, use checksum...) */
- /* How to check for pruning tables with new method? */
- /* Solution: use list of steps */
- /*
- char fname[strlen(tabledir)+100];
- int i;
-
- for (i = 0; all_pd[i] != NULL; i++) {
- strcpy(fname, tabledir);
- strcat(fname, "/");
- strcat(fname, all_pd[i]->filename);
- if ((f = fopen(fname, "rb")) == NULL)
- return false;
- else
- fclose(f);
- }
- */
-
- return true;
-}
-
-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;
- char line[MAXLINELEN];
- Command *cmd = NULL;
- CommandArgs *args;
- Alg *scramble;
-
- for (i = 0; commands[i] != NULL; i++)
- if (!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;
- }
-
- if (args->scrstdin) {
- while (true) {
- if (fgets(line, MAXLINELEN, stdin) == NULL) {
- clearerr(stdin);
- break;
- }
-
- scramble = new_alg(line);
-
- printf(">>> Line: %s", line);
-
- if (scramble != NULL && scramble->len > 0) {
- args->scramble = scramble;
- cmd->exec(args);
- free_alg(scramble);
- args->scramble = NULL;
- }
- }
- } else {
- cmd->exec(args);
- }
- free_args(args);
-}
-
-void
-launch(bool batchmode)
-{
- 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));
-
- if (!batchmode) {
- fprintf(stderr, "Welcome to Nissy "VERSION".\n"
- "Type \"commands\" for a list of commands.\n");
- }
-
- while (true) {
- if (!batchmode) {
- fprintf(stdout, "nissy-# ");
- }
-
- if (fgets(line, MAXLINELEN, stdin) == NULL)
- break;
-
- if (batchmode) {
- printf(">>>\n"
- ">>> Executing command: %s"
- ">>>\n", line);
- }
-
- shell_argc = parseline(line, shell_argv);
-
- if (shell_argc > 0)
- exec_args(shell_argc, shell_argv);
- }
-
- for (i = 0; i < MAXNTOKENS; i++)
- free(shell_argv[i]);
- free(shell_argv);
-}
-
-int
-main(int argc, char *argv[])
-{
- char *closing_cmd[1] = { "freemem" };
-
- init_env();
- init_trans();
-
-/*
- Cube c;
- make_solved(&c);
- c.co[0] = 1;
- c.co[6] = 2;
- print_cube(&c);
- apply_trans(uf_mirror, &c);
- print_cube(&c);
-*/
-
-/*
- test_coord(&coord_coud_cpudsep);
-*/
-
- if (!checkfiles()) {
- fprintf(stderr,
- "--- Warning ---\n"
- "Some pruning tables are missing or unreadable\n"
- "You can generate them with `nissy gen'.\n"
- "---------------\n\n"
- );
- }
-
- if (argc > 1) {
- if (!strcmp(argv[1], "-b")) {
- launch(true);
- } else {
- exec_args(argc-1, &argv[1]);
- }
- } else {
- launch(false);
- }
-
- exec_args(1, closing_cmd);
-
- return 0;
-}
diff --git a/src/shell.h b/src/shell.h
@@ -1,14 +0,0 @@
-#ifndef SHELL_H
-#define SHELL_H
-
-#include "commands.h"
-
-#define MAXLINELEN 10000
-#define MAXTOKENLEN 255
-#define MAXNTOKENS 255
-
-bool checkfiles();
-void exec_args(int c, char **v);
-void launch(bool batchmode);
-
-#endif
diff --git a/src/solve.c b/src/solve.c
@@ -2,58 +2,92 @@
#include "solve.h"
-/* Local functions ***********************************************************/
-
-static bool allowed_next(Move move, StepAlt *sa, Move l0, Move l1);
-static bool cancel_niss(DfsArg *arg);
+#define MAX_N_COORD 3
+
+typedef struct { uint64_t val; Trans t; } Movable;
+typedef struct {
+ char * shortname;
+ bool filter;
+ Moveset * moveset;
+ Coordinate * coord[MAX_N_COORD];
+ PruneData * pd[MAX_N_COORD];
+ bool compact_pd[MAX_N_COORD];
+ Coordinate * fallback_coord[MAX_N_COORD];
+ PruneData * fallback_pd[MAX_N_COORD];
+ uint64_t fbmod[MAX_N_COORD];
+
+} Step;
+typedef struct {
+ Cube * cube;
+ Movable ind[MAX_N_COORD];
+ Step * s;
+ AlgList * sols;
+ int d;
+ int bound;
+ bool can_niss;
+ bool niss;
+ bool has_nissed;
+ Move last[2];
+ Move lastinv[2];
+ Alg * current_alg;
+} DfsArg;
+
+static bool allowed_next(Move move, Step *s, Move l0, Move l1);
+static void compute_ind(DfsArg *arg);
static void copy_dfsarg(DfsArg *src, DfsArg *dst);
+static int estimate_step(Step *step, Movable *ind);
static void dfs(DfsArg *arg);
-static void dfs_add_sol(DfsArg *arg);
static void dfs_niss(DfsArg *arg);
static bool dfs_move_checkstop(DfsArg *arg);
-static void * instance_thread(void *arg);
-static void multidfs(DfsArg *arg);
static bool niss_makes_sense(DfsArg *arg);
-static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
-/* Local functions ***********************************************************/
+Step eofb_HTM = {
+ .shortname = "eofb",
+ .filter = true,
+ .moveset = allowed_HTM,
+ .coord = {&coord_eofb, NULL},
+ .compact_pd = {false},
+};
+
+Step drud_HTM = {
+ .shortname = "drud",
+ .filter = true,
+ .moveset = allowed_HTM,
+ .coord = {&coord_drud_sym16, NULL},
+ .compact_pd = {false}, /* TODO: compactify! */
+};
+
+Step drfin_drud = {
+ .shortname = "drudfin",
+ .filter = false,
+ .moveset = allowed_drud,
+ .coord = {&coord_drudfin_noE_sym16, &coord_epe, NULL},
+ .compact_pd = {false}, /* TODO: compactify! */
+};
+
+Step *steps[] = { &eofb_HTM, &drud_HTM, &drfin_drud, NULL };
static bool
-allowed_next(Move m, StepAlt *sa, Move l0, Move l1)
+allowed_next(Move m, Step *s, Move l0, Move l1)
{
- bool allowed, order;
- uint64_t mbit;
+ bool p, q, allowed, order;
- mbit = ((uint64_t)1) << m;
- allowed = mbit & sa->moveset->mask[l1][l0];
+ p = l0 != NULLMOVE && base_move(l0) == base_move(m);
+ q = l1 != NULLMOVE && base_move(l1) == base_move(m);
+ allowed = !(p || (commute(l0, l1) && q));
order = !commute(l0, m) || l0 < m;
return allowed && order;
}
-static bool
-cancel_niss(DfsArg *arg)
+void
+compute_ind(DfsArg *arg)
{
- Moveset *ms;
- Move i1, i2;
- bool p, p1, p2, q, q1, q2;
-
- if (arg->lastinv[0] == NULLMOVE)
- return false;
-
- ms = arg->sa->moveset;
- i1 = inverse_move(arg->lastinv[0]);
- i2 = inverse_move(arg->lastinv[1]);
-
- p1 = !ms->allowed_next(arg->last[1], arg->last[0], i1);
- p2 = !ms->allowed_next(arg->last[1], i1, arg->last[0]);
- p = p1 || (commute(i1, arg->last[0]) && p2);
-
- q1 = !ms->allowed_next(arg->last[1], arg->last[0], i2);
- q2 = !ms->allowed_next(arg->last[1], i2, arg->last[0]);
- q = q1 || (commute(i2, arg->last[0]) && q2);
+ int i;
- return p || (commute(i1, i2) && q);
+ for (i = 0; arg->s->coord[i] != NULL; i++)
+ arg->ind[i].val = index_coord(arg->s->coord[i],
+ arg->cube, &arg->ind[i].t);
}
static void
@@ -62,14 +96,13 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
int i;
dst->cube = src->cube;
- dst->t = src->t;
- dst->sa = src->sa;
- dst->opts = src->opts;
+ dst->s = src->s;
dst->d = src->d;
dst->bound = src->bound; /* In theory not needed */
+ dst->can_niss = src->can_niss;
dst->niss = src->niss;
+ dst->has_nissed = src->has_nissed;
dst->sols = src->sols;
- dst->sols_mutex = src->sols_mutex;
dst->current_alg = src->current_alg;
for (i = 0; i < 2; i++) {
@@ -77,16 +110,33 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
dst->lastinv[i] = src->lastinv[i];
}
- for (i = 0; i < src->sa->n_coord; i++) {
+ for (i = 0; src->s->coord[i] != NULL; i++) {
dst->ind[i].val = src->ind[i].val;
dst->ind[i].t = src->ind[i].t;
}
}
+static int
+estimate_step(Step *step, Movable *ind)
+{
+ int i, v, ret = -1;
+
+ for (i = 0; step->coord[i] != NULL; i++) {
+ v = ptableval(step->pd[i], ind[i].val);
+ if (v == step->pd[i]->base && step->compact_pd[i])
+ v = ptableval(step->fallback_pd[i],
+ ind[i].val / step->fbmod[i]);
+ if (v == 0 && ind[i].val != 0)
+ v = 1;
+ ret = MAX(ret, v);
+ }
+
+ return ret;
+}
+
static void
dfs(DfsArg *arg)
{
- int i;
Move m;
DfsArg newarg;
@@ -94,14 +144,17 @@ dfs(DfsArg *arg)
return;
if (arg->bound == 0) {
- if (arg->current_alg->len == arg->d)
- dfs_add_sol(arg);
+ if (arg->current_alg->len == arg->d &&
+ singlecwend(arg->current_alg) &&
+ (!arg->can_niss || arg->has_nissed))
+ append_alg(arg->sols, arg->current_alg);
return;
}
- for (i = 0; arg->sa->moveset->sorted_moves[i] != NULLMOVE; i++) {
- m = arg->sa->moveset->sorted_moves[i];
- if (allowed_next(m, arg->sa, arg->last[0], arg->last[1])) {
+ for (m = U; m <= B3; m++) {
+ if (!arg->s->moveset(m))
+ continue;
+ if (allowed_next(m, arg->s, arg->last[0], arg->last[1])) {
copy_dfsarg(arg, &newarg);
newarg.last[1] = arg->last[0];
newarg.last[0] = m;
@@ -116,30 +169,6 @@ dfs(DfsArg *arg)
}
static void
-dfs_add_sol(DfsArg *arg)
-{
- bool valid, accepted, nisscanc;
-
- valid = arg->sa->is_valid==NULL || arg->sa->is_valid(arg->current_alg);
- accepted = valid || arg->opts->all;
- nisscanc = arg->sa->final && cancel_niss(arg);
-
- if (accepted && !nisscanc) {
- pthread_mutex_lock(arg->sols_mutex);
-
- if (arg->sols->len < arg->opts->max_solutions) {
- append_alg(arg->sols, arg->current_alg);
- transform_alg(
- inverse_trans(arg->t), arg->sols->last->alg);
- if (arg->opts->verbose)
- print_alg(arg->sols->last->alg, false);
- }
-
- pthread_mutex_unlock(arg->sols_mutex);
- }
-}
-
-static void
dfs_niss(DfsArg *arg)
{
DfsArg newarg;
@@ -159,11 +188,12 @@ dfs_niss(DfsArg *arg)
compose(c, newarg.cube);
/* New indexes */
- compute_ind(newarg.sa, newarg.cube, newarg.ind);
+ compute_ind(&newarg);
swapmove(&(newarg.last[0]), &(newarg.lastinv[0]));
swapmove(&(newarg.last[1]), &(newarg.lastinv[1]));
newarg.niss = !(arg->niss);
+ newarg.has_nissed = true;
dfs(&newarg);
@@ -175,144 +205,26 @@ dfs_niss(DfsArg *arg)
static bool
dfs_move_checkstop(DfsArg *arg)
{
- bool b;
- int i, goal;
+ int i;
Move mm;
Trans tt = uf; /* Avoid uninitialized warning */
/* Moving */
if (arg->last[0] != NULLMOVE) {
- for (i = 0; i < arg->sa->n_coord; i++) {
+ for (i = 0; arg->s->coord[i] != NULL; i++) {
mm = transform_move(arg->ind[i].t, arg->last[0]);
- arg->ind[i].val = move_coord(arg->sa->coord[i],
+ arg->ind[i].val = move_coord(arg->s->coord[i],
mm, arg->ind[i].val, &tt);
arg->ind[i].t = transform_trans(tt, arg->ind[i].t);
}
}
/* Computing bound for coordinates */
- goal = arg->d - arg->current_alg->len;
- arg->bound = estimate_stepalt(arg->sa, arg->ind, goal);
- if (arg->opts->can_niss && !arg->niss)
+ arg->bound = estimate_step(arg->s, arg->ind);
+ if (arg->can_niss && !arg->niss)
arg->bound = MIN(1, arg->bound);
- if (arg->bound > goal) {
- b = true;
- } else {
- pthread_mutex_lock(arg->sols_mutex);
- b = arg->sols->len >= arg->opts->max_solutions;
- pthread_mutex_unlock(arg->sols_mutex);
- }
-
- return b;
-}
-
-static void *
-instance_thread(void *arg)
-{
- bool b, inv;
- Cube c;
- Move m;
- ThreadDataSolve *td;
- AlgListNode *node;
- DfsArg darg;
-
- td = (ThreadDataSolve *)arg;
-
- while (1) {
- b = false;
-
- pthread_mutex_lock(td->start_mutex);
- if ((node = *(td->node)) == NULL)
- b = true;
- else
- *(td->node) = (*(td->node))->next;
- pthread_mutex_unlock(td->start_mutex);
-
- if (b)
- break;
-
- inv = node->alg->inv[0];
- m = node->alg->move[0];
-
- copy_cube(td->arg.cube, &c);
- if (inv)
- invert_cube(&c);
-
- copy_dfsarg(&td->arg, &darg);
- compute_ind(td->arg.sa, &c, darg.ind);
- darg.cube = &c;
-
- darg.niss = inv;
- darg.last[0] = m;
- darg.last[1] = NULLMOVE;
- darg.lastinv[0] = NULLMOVE;
- darg.lastinv[1] = NULLMOVE;
- darg.current_alg = new_alg("");
- append_move(darg.current_alg, m, inv);
-
- dfs(&darg);
-
- free_alg(darg.current_alg);
- }
-
- return NULL;
-}
-
-static void
-multidfs(DfsArg *arg)
-{
- int i;
- Cube local_cube;
- Alg *alg;
- AlgList *start;
- AlgListNode **node;
- pthread_t t[arg->opts->nthreads];
- ThreadDataSolve td[arg->opts->nthreads];
- pthread_mutex_t *start_mutex, *sols_mutex;
-
- node = malloc(sizeof(AlgListNode *));
- start_mutex = malloc(sizeof(pthread_mutex_t));
- sols_mutex = malloc(sizeof(pthread_mutex_t));
-
- start = new_alglist();
- pthread_mutex_init(start_mutex, NULL);
- pthread_mutex_init(sols_mutex, NULL);
-
- for (i = 0; arg->sa->moveset->sorted_moves[i] != NULLMOVE; i++) {
- alg = new_alg("");
- append_move(alg, arg->sa->moveset->sorted_moves[i], false);
- append_alg(start, alg);
- if (arg->opts->can_niss && !arg->sa->final) {
- alg->inv[0] = true;
- append_alg(start, alg);
- }
- free_alg(alg);
- }
- *node = start->first;
-
- copy_cube(arg->cube, &local_cube);
-
- for (i = 0; i < arg->opts->nthreads; i++) {
- copy_dfsarg(arg, &(td[i].arg));
- td[i].arg.cube = &local_cube;
- td[i].arg.sols_mutex = sols_mutex;
-
- td[i].thid = i;
- td[i].start = start;
- td[i].node = node;
- td[i].start_mutex = start_mutex;
-
- pthread_create(&t[i], NULL, instance_thread, &td[i]);
- }
-
- for (i = 0; i < arg->opts->nthreads; i++)
- pthread_join(t[i], NULL);
-
- free_alglist(start);
- free(node);
- free(start_mutex);
- free(sols_mutex);
+ return arg->bound + arg->current_alg->len > arg->d ;
}
static bool
@@ -320,162 +232,85 @@ niss_makes_sense(DfsArg *arg)
{
Cube testcube;
- if (arg->sa->final || arg->niss || !arg->opts->can_niss)
+ if (arg->niss || !arg->can_niss || arg->current_alg->len == 0)
return false;
make_solved(&testcube);
apply_move(inverse_move(arg->last[0]), &testcube);
- return arg->current_alg->len == 0 ||
- estimate_stepalt(arg->sa, arg->ind, 0) > 0;
-}
-
-static bool
-solvestop(int d, int op, SolveOptions *opts, AlgList *sols)
-{
- bool opt_done, max_moves_exceeded, max_sols_exceeded;
-
- opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op;
- max_moves_exceeded = d > opts->max_moves;
- max_sols_exceeded = sols->len >= opts->max_solutions;
-
- return opt_done || max_moves_exceeded || max_sols_exceeded;
+ return estimate_step(arg->s, arg->ind) > 0;
}
/* Public functions **********************************************************/
AlgList *
-solve(Cube *cube, Step *step, SolveOptions *opts)
+solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
{
- int i, d, op;
- bool ready[99], one_ready, zerosol;
- Movable ind[99][10];
- AlgList *s;
- Cube *c[99];
- DfsArg arg[99];
-
- prepare_step(step, opts);
- s = new_alglist();
-
- for (i = 0, one_ready = false; step->alt[i] != NULL; i++) {
- c[i] = malloc(sizeof(Cube));
- copy_cube(cube, c[i]);
- apply_trans(step->t[i], c[i]);
-
- arg[i].cube = c[i];
- arg[i].t = step->t[i];
- arg[i].sa = step->alt[i];
- arg[i].opts = opts;
- arg[i].sols = s;
-
- if ((ready[i] = step->alt[i]->ready(c[i]))) {
- one_ready = true;
- /* Only for local use for 0 moves solutions */
- compute_ind(step->alt[i], c[i], ind[i]);
- }
- }
- if (!one_ready) {
- fprintf(stderr, "Cube not ready for solving step: ");
- fprintf(stderr, "%s\n", step->ready_msg);
- return s;
+ int i;
+ AlgList *sols;
+ AlgListNode *node;
+ Cube c;
+ DfsArg arg;
+ Step *step;
+
+ /* TODO: checks for steps being ready and not solved are
+ done somewhere else */
+
+ sols = new_alglist();
+
+ /* Prepare step TODO: remove all initialization! */
+ step = NULL;
+ for (i = 0; steps[i] != NULL; i++)
+ if (!strcmp(steps[i]->shortname, stepstr))
+ step = steps[i];
+ if (step == NULL) {
+ fprintf(stderr, "No step to solve!\n");
+ return sols;
}
-
- /* If the empty moves sequence is a solution for one of the
- * alternatives, all longer solutions will be discarded, so we may
- * just set its ready[] value to false. If the solution is accepted
- * we append it and start searching from d = 1. */
- for (i = 0, zerosol = false; step->alt[i] != NULL; i++) {
- if (ready[i] && estimate_stepalt(step->alt[i],ind[i],0) == 0) {
- ready[i] = false;
- zerosol = true;
+ PDGenData pdg;
+ pdg.moveset = step->moveset;
+ for (i = 0; step->coord[i] != NULL; i++) {
+ gen_coord(step->coord[i]);
+ pdg.coord = step->coord[i];
+ pdg.compact = step->compact_pd[i];
+ pdg.pd = NULL;
+ step->pd[i] = genptable(&pdg);
+ if (step->compact_pd[i]) {
+ gen_coord(step->fallback_coord[i]);
+ pdg.coord = step->fallback_coord[i];
+ pdg.compact = false;
+ pdg.pd = NULL;
+ step->fallback_pd[i] = genptable(&pdg);
}
}
- if (zerosol && opts->min_moves == 0) {
- append_alg(s, new_alg(""));
- opts->min_moves = 1;
- if (opts->verbose)
- printf("Step is already solved"
- "(empty alg is a solution)\n");
- }
- for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) {
- if (opts->verbose)
- fprintf(stderr, "Searching depth %d\n", d);
-
- for (i=0; step->alt[i]!=NULL && !solvestop(d,op,opts,s); i++) {
- if (!ready[i])
- continue;
-
- arg[i].d = d;
- multidfs(&arg[i]);
-
- if (s->len > 0 && op == -1)
- op = d;
- }
+ /* Prepare cube for solve */
+ arg.cube = &c;
+ copy_cube(cube, arg.cube);
+ if (st == INVERSE)
+ invert_cube(arg.cube);
+ apply_trans(t, arg.cube);
+ arg.s = step;
+ compute_ind(&arg);
+ arg.can_niss = st == NISS;
+ arg.sols = sols;
+ arg.d = m;
+ arg.niss = false;
+ arg.has_nissed = false;
+ arg.last[0] = NULLMOVE;
+ arg.last[1] = NULLMOVE;
+ arg.lastinv[0] = NULLMOVE;
+ arg.lastinv[1] = NULLMOVE;
+ arg.current_alg = new_alg("");
+
+ dfs(&arg);
+
+ for (node = sols->first; node != NULL; node = node->next) {
+ transform_alg(inverse_trans(t), node->alg);
+ if (st == INVERSE)
+ for (i = 0; i < node->alg->len; i++)
+ node->alg->inv[i] = true;
}
- for (i = 0; step->alt[i] != NULL; i++)
- free(c[i]);
-
- return s;
+ return sols;
}
-/* TODO: make more general! */
-Alg *
-solve_2phase(Cube *cube, int nthreads)
-{
- int bestlen, newb;
- Alg *bestalg, *ret;
- AlgList *sols1, *sols2;
- AlgListNode *i;
- Cube c;
- SolveOptions opts1, opts2;
-
- opts1.min_moves = 0;
- opts1.max_moves = 13;
- opts1.max_solutions = 20;
- opts1.nthreads = nthreads;
- opts1.optimal = 3;
- opts1.can_niss = false;
- opts1.verbose = false;
- opts1.all = true;
-
- opts2.min_moves = 0;
- opts2.max_moves = 19;
- opts2.max_solutions = 1;
- opts2.nthreads = nthreads;
- opts2.can_niss = false;
- opts2.verbose = false;
-
- /* We skip step1 if it is solved on U/D */
- if (check_drud(cube)) {
- sols1 = new_alglist();
- append_alg(sols1, new_alg(""));
- } else {
- sols1 = solve(cube, &drud_HTM, &opts1);
- }
- bestalg = new_alg("");
- bestlen = 999;
- for (i = sols1->first; i != NULL; i = i->next) {
- copy_cube(cube, &c);
- apply_alg(i->alg, &c);
- sols2 = solve(&c, &dranyfin_DR, &opts2);
-
- if (sols2->len > 0) {
- newb = i->alg->len + sols2->first->alg->len;
- if (newb < bestlen) {
- bestlen = newb;
- copy_alg(i->alg, bestalg);
- compose_alg(bestalg, sols2->first->alg);
- }
- }
-
- free_alglist(sols2);
- }
-
- free_alglist(sols1);
-
- ret = cleanup(bestalg);
- free_alg(bestalg);
-
- return ret;
-}
diff --git a/src/solve.h b/src/solve.h
@@ -1,11 +1,11 @@
#ifndef SOLVE_H
#define SOLVE_H
-#include "moves.h"
-#include "steps.h"
-#include "trans.h"
+#include "pruning.h"
+#include "alg.h"
-AlgList * solve(Cube *cube, Step *step, SolveOptions *opts);
-Alg * solve_2phase(Cube *cube, int nthreads);
+typedef enum { NORMAL, INVERSE, NISS } SolutionType;
+
+AlgList *solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t);
#endif
diff --git a/src/steps.c b/src/steps.c
@@ -1,221 +0,0 @@
-#define STEPS_C
-
-#include "steps.h"
-
-/* TODO: change all checkers to use coordinates! */
-
-bool
-check_centers(Cube *cube)
-{
- int i;
-
- for (i = 0; i < 6; i++)
- if (cube->xp[i] != i)
- return false;
-
- return true;
-}
-
-bool
-check_coud_HTM(Cube *cube)
-{
- int i;
-
- for (i = 0; i < 8; i++)
- if (cube->co[i] != 0)
- return false;
-
- return true;
-}
-
-bool
-check_coud_URF(Cube *cube)
-{
- Cube c2, c3;
-
- copy_cube(cube, &c2);
- copy_cube(cube, &c3);
-
- apply_move(z, &c2);
- apply_move(x, &c3);
-
- return check_coud_HTM(cube) ||
- check_coud_HTM(&c2) ||
- check_coud_HTM(&c3);
-}
-
-bool
-check_cp_HTM(Cube *cube)
-{
- int i;
-
- for (i = 0; i < 8; i++)
- if (cube->cp[i] != i)
- return false;
-
- return true;
-}
-
-bool
-check_corners_HTM(Cube *cube)
-{
- return check_coud_HTM(cube) && check_cp_HTM(cube);
-}
-
-bool
-check_corners_URF(Cube *cube)
-{
- Cube c;
- Trans i;
-
- for (i = 0; i < NROTATIONS; i++) {
- copy_cube(cube, &c);
- apply_alg(rotation_alg(i), &c);
- if (check_corners_HTM(&c))
- return true;
- }
-
- return false;
-}
-
-bool
-check_cornershtr(Cube *cube)
-{
- /* TODO (use coord) */
- return true;
-}
-
-bool
-check_eofb(Cube *cube)
-{
- /* TODO (use coord) */
- return true;
-}
-
-bool
-check_drud(Cube *cube)
-{
- /* TODO (use coord) */
- return true;
-}
-
-bool
-check_htr(Cube *cube)
-{
- /* TODO (check_drud(cube) and coord_htr_drud == 0) */
- return true;
-}
-
-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;
-}
-
-/* Public functions **********************************************************/
-
-void
-compute_ind(StepAlt *a, Cube *cube, Movable *ind)
-{
- int i;
- Cube mvd;
- Trans t, tt;
-
- for (i = 0; i < a->n_coord; i++) {
- t = a->coord_trans[i];
- copy_cube(cube, &mvd);
- apply_trans(t, &mvd);
-
- ind[i].val = index_coord(a->coord[i], &mvd, &tt);
- ind[i].t = transform_trans(tt, t);
- }
-}
-
-int
-estimate_stepalt(StepAlt *a, Movable *ind, int goal)
-{
- int i, ret, est[a->n_coord];
-
- for (i = 0; i < a->n_coord; i++) {
- est[i] = ptableval(a->pd[i], ind[i].val);
- if (est[i] == a->pd[i]->base && a->compact_pd[i])
- est[i] = ptableval(a->fallback_pd[i],
- ind[i].val/a->fbmod[i]);
- if (ind[i].val != 0 && est[i] == 0) /* est == 0 iff solved */
- est[i] = 1;
-/*
-TODO: remove this debug code
-printf("%d: est=%d | ", i, est[i]);
-*/
-
- if (est[i] > goal)
- return est[i];
- }
-
- for (i = 0; i < a->n_dbtrick; i++)
- if (est[a->dbtrick[i][0]] > 0 &&
- est[a->dbtrick[i][0]] == est[a->dbtrick[i][1]] &&
- est[a->dbtrick[i][0]] == est[a->dbtrick[i][2]])
- est[a->dbtrick[i][0]] += 1;
-
- for (i = 0, ret = -1; i < a->n_coord; i++)
- ret = MAX(ret, est[i]);
-
-/*
-TODO: remove this debug code
-printf("Final estimate: %d\n", ret);
-*/
-
- return ret;
-}
-
-void
-prepare_step(Step *step, SolveOptions *opts)
-{
- int i, j;
- PDGenData pdg;
- StepAlt *a;
-
- for (i = 0; step->alt[i] != NULL; i++) {
- a = step->alt[i];
- init_moveset(a->moveset);
- pdg.moveset = a->moveset;
- for (j = 0; j < a->n_coord; j++) {
- gen_coord(a->coord[j]);
-
- pdg.coord = a->coord[j];
- pdg.compact = a->compact_pd[j];
- pdg.pd = NULL;
-
- a->pd[j] = genptable(&pdg, opts->nthreads);
-
- if (a->compact_pd[j]) {
- gen_coord(a->fallback_coord[j]);
-
- pdg.coord = a->fallback_coord[j];
- pdg.compact = false;
- pdg.pd = NULL;
-
- a->fallback_pd[j] =
- genptable(&pdg, opts->nthreads);
- }
- }
- }
-}
diff --git a/src/steps.h b/src/steps.h
@@ -1,277 +0,0 @@
-#ifndef STEPS_H
-#define STEPS_H
-
-#include "pruning.h"
-
-bool check_centers(Cube *cube);
-bool check_coud_HTM(Cube *cube);
-bool check_coud_URF(Cube *cube);
-bool check_cp_HTM(Cube *cube);
-bool check_corners_HTM(Cube *cube);
-bool check_corners_URF(Cube *cube);
-bool check_cornershtr(Cube *cube);
-bool check_eofb(Cube *cube);
-bool check_drud(Cube *cube);
-bool check_htr(Cube *cube);
-void compute_ind(StepAlt *a, Cube *cube, Movable *ind);
-int estimate_stepalt(StepAlt *a, Movable *ind, int goal);
-void prepare_step(Step *step, SolveOptions *opts);
-bool always_valid(Alg *alg);
-bool validate_singlecw_ending(Alg *alg);
-
-#ifndef STEPS_C
-
-extern char check_centers_msg[100];
-extern char check_eo_msg[100];
-extern char check_dr_msg[100];
-extern char check_htr_msg[100];
-extern char check_drany_msg[100];
-
-extern StepAlt sa_nxopt31_HTM;
-extern StepAlt sa_eofb_HTM;
-extern StepAlt sa_drud_HTM;
-extern StepAlt sa_drfin_drud;
-
-extern Step optimal_HTM;
-extern Step eoany_HTM;
-extern Step eofb_HTM;
-extern Step eorl_HTM;
-extern Step eoud_HTM;
-extern Step drany_HTM;
-extern Step drud_HTM;
-extern Step drrl_HTM;
-extern Step drfb_HTM;
-extern Step dranyfin_DR;
-extern Step drudfin_drud;
-extern Step drrlfin_drrl;
-extern Step drfbfin_drfb;
-
-extern Step *steps[];
-
-#else
-
-char check_centers_msg[100] = "cube must be oriented (centers solved)";
-char check_eo_msg[100] = "EO must be solved on given axis";
-char check_dr_msg[100] = "DR must be solved on given axis";
-char check_htr_msg[100] = "HTR must be solved";
-char check_drany_msg[100] = "DR must be solved on at least one axis";
-
-/* Optimal solvers *******************/
-/* TODO: build options for smaller optimal solvers */
-
-StepAlt
-sa_nxopt31_HTM = {
- .ready = check_centers,
- .final = true,
- .moveset = &moveset_HTM,
- .n_coord = 6,
- .coord = {&coord_nxopt31, &coord_nxopt31, &coord_nxopt31,
- &coord_eposepe, &coord_eposepe, &coord_eposepe},
- /* TODO: use khuge as fallback? */
- .coord_trans = {uf, rd, bl, uf, rd, bl},
- .compact_pd = {true, true, true, false, false, false},
- .fallback_coord = {&coord_drud_sym16, &coord_drud_sym16,
- &coord_drud_sym16},
- .fbmod = {BINOM8ON4, BINOM8ON4, BINOM8ON4},
- .n_dbtrick = 1, /* TODO: change to 2 when khuge */
- .dbtrick = {{0, 1, 2}},
- .is_valid = NULL,
-};
-Step
-optimal_HTM = {
- .shortname = "optimal",
- .name = "Optimal solve (in HTM)",
- .alt = {&sa_nxopt31_HTM, NULL},
- .t = {uf},
- .ready_msg = check_centers_msg,
-};
-
-/* Optimal after EO ******************/
-/* TODO: eofin_eo (generic), eofbfin_eofb, eorlfin_eorl, eoudfin_eoud */
-
-/* EO steps **************************/
-/* TODO: eoany_HTM (generic), eofb_HTM, eorl_HTM, eoud_HTM */
-
-StepAlt
-sa_eofb_HTM = {
- .ready = check_centers,
- .final = false,
- .moveset = &moveset_HTM,
- .n_coord = 1,
- .coord = {&coord_eofb},
- .coord_trans = {uf},
- .compact_pd = {false},
- .n_dbtrick = 0,
- .is_valid = validate_singlecw_ending,
-};
-Step
-eoany_HTM = {
- .shortname = "eo",
- .name = "EO on any axis",
- .alt = {&sa_eofb_HTM, &sa_eofb_HTM, &sa_eofb_HTM, NULL},
- .t = {uf, ur, fd},
- .ready_msg = check_centers_msg,
-};
-Step
-eofb_HTM = {
- .shortname = "eofb",
- .name = "EO on F/B",
- .alt = {&sa_eofb_HTM, NULL},
- .t = {uf},
- .ready_msg = check_centers_msg,
-};
-Step
-eorl_HTM = {
- .shortname = "eorl",
- .name = "EO on R/L",
- .alt = {&sa_eofb_HTM, NULL},
- .t = {ur},
- .ready_msg = check_centers_msg,
-};
-Step
-eoud_HTM = {
- .shortname = "eoud",
- .name = "EO on U/D",
- .alt = {&sa_eofb_HTM, NULL},
- .t = {fd},
- .ready_msg = check_centers_msg,
-};
-
-/* CO steps **************************/
-/* TODO: coany_HTM (generic), cofb_HTM, corl_HTM, coud_HTM */
-/* TODO: coany_URF (generic), cofb_URF, corl_URF, coud_URF */
-
-/* Misc corner steps *****************/
-/* TODO: cornershtr_HTM, cornershtr_URF, corners_HTM, corners_URF */
-/* TODO (new): corners_drud */
-
-/* DR steps **************************/
-/* TODO: dr_eo (generic) */
-/* TODO: dr_eofb (generic), dr_eorl (generic), dr_eoud (generic) */
-/* TODO: drud_eofb, drrl_eofb, drud_eorl, drfb_eorl, drrl_eoud, drfb_eoud */
-
-StepAlt
-sa_drud_HTM = {
- .ready = check_centers,
- .final = false,
- .moveset = &moveset_HTM,
- .n_coord = 1,
- .coord = {&coord_drud_sym16},
- .coord_trans = {uf},
- .compact_pd = {false}, /* TODO: maybe compactify */
- .n_dbtrick = 0,
- .is_valid = validate_singlecw_ending,
-};
-Step
-drany_HTM = {
- .shortname = "dr",
- .name = "DR on any axis",
- .alt = {&sa_drud_HTM, &sa_drud_HTM, &sa_drud_HTM, NULL},
- .t = {uf, rf, fd},
- .ready_msg = check_centers_msg,
-};
-Step
-drud_HTM = {
- .shortname = "drud",
- .name = "DR on U/D",
- .alt = {&sa_drud_HTM, NULL},
- .t = {uf},
- .ready_msg = check_centers_msg,
-};
-Step
-drrl_HTM = {
- .shortname = "drrl",
- .name = "DR on R/L",
- .alt = {&sa_drud_HTM, NULL},
- .t = {rf},
- .ready_msg = check_centers_msg,
-};
-Step
-drfb_HTM = {
- .shortname = "drfb",
- .name = "DR on F/B",
- .alt = {&sa_drud_HTM, NULL},
- .t = {fd},
- .ready_msg = check_centers_msg,
-};
-
-/* DR finish steps */
-StepAlt
-sa_drfin_drud = {
- .ready = check_drud,
- .final = true,
- .moveset = &moveset_drud,
- .n_coord = 1,
- .coord = {&coord_drudfin_noE_sym16}, /* TODO: maybe no noE */
- .coord_trans = {uf},
- .compact_pd = {false}, /* TODO: maybe compactify */
- .n_dbtrick = 0,
- .is_valid = NULL,
-};
-Step
-dranyfin_DR = {
- .shortname = "drfin",
- .name = "DR finish on any axis without breaking DR",
- .alt = {&sa_drfin_drud, &sa_drfin_drud, &sa_drfin_drud, NULL},
- .t = {uf, rf, fd},
- .ready_msg = check_dr_msg,
-};
-Step
-drudfin_drud = {
- .shortname = "drudfin",
- .name = "DR finis on U/D without breaking DR",
- .alt = {&sa_drfin_drud, NULL},
- .t = {uf},
- .ready_msg = check_dr_msg,
-};
-Step
-drrlfin_drrl = {
- .shortname = "drrlfin",
- .name = "DR finish on R/L without breaking DR",
- .alt = {&sa_drfin_drud, NULL},
- .t = {rf},
- .ready_msg = check_dr_msg,
-};
-Step
-drfbfin_drfb = {
- .shortname = "drfbfin",
- .name = "DR finish on F/B without breaking DR",
- .alt = {&sa_drfin_drud, NULL},
- .t = {fd},
- .ready_msg = check_dr_msg,
-};
-
-/* HTR from DR */
-/* TODO: htr_any (generic), htr_drud, htr_drrl, htr_drfb */
-
-/* HTR finish */
-/* TODO: htrfin_htr */
-
-Step *steps[] = {
- &optimal_HTM, /* first is default */
-
- &eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM,
- &drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM,
- &dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb,
-
-/* TODO:
- &optimal_light_HTM,
-
- &eofin_eo, &eofbfin_eofb, &eorlfin_eorl, &eoudfin_eoud,
- &coany_HTM, &coud_HTM, &corl_HTM, &cofb_HTM,
- &coany_URF, &coud_URF, &corl_URF, &cofb_URF,
- &dr_eo, &dr_eofb, &dr_eorl, &dr_eoud,
- &drud_eofb, &drrl_eofb,
- &drud_eorl, &drfb_eorl,
- &drfb_eoud, &drrl_eoud,
- &htr_any, &htr_drud, &htr_drrl, &htr_drfb,
- &htrfin_htr,
- &cornershtr_HTM, &cornershtr_URF, &corners_HTM, &corners_URF,
- NULL
-*/
-
-};
-
-#endif
-
-#endif
diff --git a/src/trans.c b/src/trans.c
@@ -1,190 +0,0 @@
-#define TRANS_C
-
-#include "trans.h"
-
-/* Local functions ***********************************************************/
-
-/* Tables and other data *****************************************************/
-
-static Cube mirror_cube = {
-.ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL,
- [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL,
- [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL },
-.cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL,
- [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL },
-.xp = { [U_center] = U_center, [D_center] = D_center,
- [R_center] = L_center, [L_center] = R_center,
- [F_center] = F_center, [B_center] = B_center }
-};
-
-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 Alg *rotation_alg_arr[NROTATIONS];
-Move moves_ttable[NTRANS][NMOVES];
-Trans trans_ttable[NTRANS][NTRANS];
-Trans trans_itable[NTRANS];
-
-/* Public functions **********************************************************/
-
-void
-apply_trans(Trans t, Cube *cube)
-{
- Cube aux;
- Alg *inv;
- int i;
-
- inv = inverse_alg(rotation_alg(t % NROTATIONS));
- copy_cube(cube, &aux);
- make_solved(cube);
-
- if (t >= NROTATIONS)
- compose(&mirror_cube, cube);
- apply_alg(inv, cube);
- compose(&aux, cube);
- apply_alg(rotation_alg(t % NROTATIONS), cube);
- if (t >= NROTATIONS) {
- compose(&mirror_cube, cube);
- for (i = 0; i < 8; i++)
- cube->co[i] = (3 - cube->co[i]) % 3;
- }
-
- free_alg(inv);
-}
-
-/*
-Trans
-inverse_trans(Trans t)
-{
- 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];
-}
-*/
-
-Trans
-inverse_trans(Trans t)
-{
- return trans_itable[t];
-}
-
-Alg *
-rotation_alg(Trans i)
-{
- return rotation_alg_arr[i % NROTATIONS];
-}
-
-void
-transform_alg(Trans t, Alg *alg)
-{
- int i;
-
- for (i = 0; i < alg->len; i++)
- alg->move[i] = transform_move(t, alg->move[i]);
-}
-
-Move
-transform_move(Trans t, Move m)
-{
- return moves_ttable[t][m];
-}
-
-Trans
-transform_trans(Trans t, Trans m)
-{
- return trans_ttable[t][m];
-}
-
-void
-init_trans() {
- static bool initialized = false;
- if (initialized)
- return;
- initialized = true;
-
- int i;
- Alg *nonsym_alg, *nonsym_inv;
- Cube aux, cube;
- Move mi, move;
- Trans t, u, v;
-
- init_moves();
-
- for (i = 0; i < NROTATIONS; i++)
- rotation_alg_arr[i] = new_alg(rotation_alg_string[i]);
-
- for (t = 0; t < NTRANS; t++) {
- for (mi = 0; mi < NMOVES; mi++) {
- make_solved(&aux);
- apply_move(mi, &aux);
- apply_trans(t, &aux);
- for (move = 0; move < NMOVES; move++) {
- copy_cube(&aux, &cube);
- apply_move(inverse_move(move), &cube);
- if (is_solved(&cube)) {
- moves_ttable[t][mi] = move;
- break;
- }
- }
- }
- }
-
- nonsym_alg = new_alg("R' U' F");
- nonsym_inv = inverse_alg(nonsym_alg);
-
- for (t = 0; t < NTRANS; t++) {
- for (u = 0; u < NTRANS; u++) {
- make_solved(&aux);
- apply_alg(nonsym_alg, &aux);
- apply_trans(u, &aux);
- apply_trans(t, &aux);
- for (v = 0; v < NTRANS; v++) {
- copy_cube(&aux, &cube);
- apply_trans(v, &cube);
- apply_alg(nonsym_inv, &cube);
- if (is_solved(&cube)) {
- /* This is the inverse of the correct
- value, it will be inverted later */
- trans_ttable[t][u] = v;
- if (v == uf)
- trans_itable[t] = u;
- break;
- }
- }
- }
- }
- for (t = 0; t < NTRANS; t++)
- for (u = 0; u < NTRANS; u++)
- trans_ttable[t][u] = trans_itable[trans_ttable[t][u]];
-
-
- free_alg(nonsym_alg);
- free_alg(nonsym_inv);
-}
-
diff --git a/src/trans.h b/src/trans.h
@@ -1,32 +0,0 @@
-#ifndef TRANS_H
-#define TRANS_H
-
-#include "moves.h"
-
-void apply_trans(Trans t, Cube *cube);
-Trans inverse_trans(Trans t);
-Alg * rotation_alg(Trans i);
-void transform_alg(Trans t, Alg *alg);
-Move transform_move(Trans t, Move m);
-Trans transform_trans(Trans t, Trans m);
-
-void init_trans();
-
-#ifndef TRANS_C
-
-extern TransGroup tgrp_udfix;
-
-#else
-
-TransGroup
-tgrp_udfix = {
- .n = 16,
- .t = { uf, ur, ub, ul,
- df, dr, db, dl,
- uf_mirror, ur_mirror, ub_mirror, ul_mirror,
- df_mirror, dr_mirror, db_mirror, dl_mirror },
-};
-
-#endif
-
-#endif
diff --git a/src/utils.c b/src/utils.c
@@ -1,290 +0,0 @@
-#define UTILS_C
-
-#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;
- bool ret = true;
-
- for (i = 0; i < n; i++)
- aux[i] = 0;
-
- for (i = 0; i < n; i++) {
- if (a[i] < 0 || a[i] >= n)
- ret = false;
- else
- aux[a[i]] = 1;
- }
-
- for (i = 0; i < n; i++)
- if (!aux[i])
- ret = false;
-
- free(aux);
- return ret;
-}
-
-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 factorial(n);
-
- 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;
-}
-
-void
-swapu64(uint64_t *a, uint64_t *b)
-{
- uint64_t aux;
-
- aux = *a;
- *a = *b;
- *b = aux;
-}
-
diff --git a/src/utils.h b/src/utils.h
@@ -1,43 +0,0 @@
-#ifndef UTILS_H
-#define UTILS_H
-
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-#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);
-void swapu64(uint64_t *a, uint64_t *b);
-
-#endif
