commit 7c7cf8a8689dcbbbca5e3604a464d2526db31a2b
parent b657d9d900bf8d9d00c1dd7ddf6b1b27990e91c1
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 14 Apr 2023 18:44:15 +0200
seems to work
Diffstat:
| D | src/alg.c | | | 393 | ------------------------------------------------------------------------------- |
| D | src/alg.h | | | 49 | ------------------------------------------------- |
| M | src/cube.c | | | 253 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------- |
| M | src/cube.h | | | 36 | ++++++++++++++++++++++-------------- |
| M | src/main.c | | | 56 | ++++++++++++++++---------------------------------------- |
| M | src/pruning.c | | | 38 | ++++++++++++++++++++++++++++++++++++++ |
| M | src/pruning.h | | | 7 | +++++++ |
| M | src/solve.c | | | 134 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------- |
| M | src/solve.h | | | 3 | +-- |
9 files changed, 386 insertions(+), 583 deletions(-)
diff --git a/src/alg.c b/src/alg.c
@@ -1,393 +0,0 @@
-#define ALG_C
-
-#include "alg.h"
-
-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)
-{
- return m >= U && m <= B3;
-}
-
-bool
-allowed_URF(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == R || b == F;
-}
-
-bool
-allowed_eofb(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == D || b == R || b == L ||
- ((b == F || b == B) && m == b+1);
-}
-
-bool
-allowed_drud(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == D ||
- ((b == R || b == L || b == F || b == B) && m == b + 1);
-}
-
-bool
-allowed_htr(Move m)
-{
- Move b = base_move(m);
-
- return allowed_HTM(m) && m == b + 1;
-}
-
-void
-append_alg(AlgList *l, Alg *alg)
-{
- AlgListNode *node = malloc(sizeof(AlgListNode));
- int i;
-
- node->alg = new_alg("");
- for (i = 0; i < alg->len; i++)
- append_move(node->alg, alg->move[i], alg->inv[i]);
- node->next = NULL;
-
- if (++l->len == 1)
- l->first = node;
- else
- l->last->next = node;
- l->last = node;
-}
-
-void
-append_move(Alg *alg, Move m, bool inverse)
-{
- if (alg->len == alg->allocated)
- realloc_alg(alg, 2*alg->len);
-
- alg->move[alg->len] = m;
- alg->inv [alg->len] = inverse;
- alg->len++;
-}
-
-static int
-axis(Move m)
-{
- if (m == NULLMOVE)
- return 0;
-
- if (m >= U && m <= B3)
- return (m-1)/6 + 1;
-
- if (m >= Uw && m <= Bw3)
- return (m-1)/6 - 2;
-
- if (base_move(m) == E || base_move(m) == y)
- return 1;
-
- if (base_move(m) == M || base_move(m) == x)
- return 2;
-
- if (base_move(m) == S || base_move(m) == z)
- return 3;
-
- return -1;
-}
-
-Move
-base_move(Move m)
-{
- return m == NULLMOVE ? NULLMOVE : m - (m-1)%3;
-}
-
-bool
-commute(Move m1, Move m2)
-{
- return axis(m1) == axis(m2);
-}
-
-void
-copy_alg(Alg *src, Alg *dst)
-{
- int i;
-
- dst->len = 0; /* Overwrites */
- for (i = 0; i < src->len; i++)
- append_move(dst, src->move[i], src->inv[i]);
-}
-
-void
-free_alg(Alg *alg)
-{
- free(alg->move);
- free(alg->inv);
- free(alg);
-}
-
-void
-free_alglist(AlgList *l)
-{
- AlgListNode *aux, *i = l->first;
-
- while (i != NULL) {
- aux = i->next;
- free_alglistnode(i);
- i = aux;
- }
- free(l);
-}
-
-static void
-free_alglistnode(AlgListNode *aln)
-{
- free_alg(aln->alg);
- free(aln);
-}
-
-Alg *
-inverse_alg(Alg *alg)
-{
- Alg *ret = new_alg("");
- int i;
-
- for (i = alg->len-1; i >= 0; i--)
- append_move(ret, inverse_move(alg->move[i]), alg->inv[i]);
-
- return ret;
-}
-
-Move
-inverse_move(Move m)
-{
- return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
-}
-
-Alg *
-new_alg(char *str)
-{
- Alg *alg;
- int i;
- bool niss, move_read;
- Move j, m;
-
- alg = malloc(sizeof(Alg));
- alg->move = malloc(30 * sizeof(Move));
- alg->inv = malloc(30 * sizeof(bool));
- alg->allocated = 30;
- alg->len = 0;
-
- niss = false;
- for (i = 0; str[i]; i++) {
- if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
- continue;
-
- if (str[i] == '(' && niss) {
- fprintf(stderr, "Error reading moves: nested ( )\n");
- alg->len = 0;
- return alg;
- }
-
- if (str[i] == ')' && !niss) {
- fprintf(stderr, "Error reading moves: unmatched )\n");
- alg->len = 0;
- return alg;
- }
-
- if (str[i] == '(' || str[i] == ')') {
- niss = !niss;
- continue;
- }
-
- /* Single slash for comments */
- if (str[i] == '/') {
- while (str[i] && str[i] != '\n')
- i++;
-
- if (!str[i])
- i--;
-
- continue;
- }
-
- move_read = false;
- for (j = U; j < NMOVES; j++) {
- if (str[i] == move_string[j][0] ||
- (str[i] >= 'a' && str[i] <= 'z' &&
- str[i] == move_string[j][0]-('A'-'a') && j<=B)) {
- m = j;
- if (str[i] >= 'a' && str[i] <= 'z' && j<=B) {
- m += Uw - U;
- }
- if (m <= B && str[i+1]=='w') {
- m += Uw - U;
- i++;
- }
- if (str[i+1]=='2') {
- m += 1;
- i++;
- } else if (str[i+1] == '\'' ||
- str[i+1] == '3' ||
- str[i+1] == '`' ) {
- m += 2;
- i++;
- } else if ((int)str[i+1] == -62 &&
- (int)str[i+2] == -76) {
- /* Weird apostrophe */
- m += 2;
- i += 2;
- } else if ((int)str[i+1] == -30 &&
- (int)str[i+2] == -128 &&
- (int)str[i+3] == -103) {
- /* MacOS apostrophe */
- m += 2;
- i += 3;
- }
- append_move(alg, m, niss);
- move_read = true;
- break;
- }
- }
-
- if (!move_read) {
- free(alg);
- return new_alg("");
- }
- }
-
- if (niss) {
- fprintf(stderr, "Error reading moves: unmatched (\n");
- alg->len = 0;
- }
-
- return alg;
-}
-
-AlgList *
-new_alglist()
-{
- AlgList *ret = malloc(sizeof(AlgList));
-
- ret->len = 0;
- ret->first = NULL;
- ret->last = NULL;
-
- return ret;
-}
-
-void
-print_alg(Alg *alg)
-{
- char fill[4];
- int i;
- bool niss = false;
-
- for (i = 0; i < alg->len; i++) {
- if (!niss && alg->inv[i])
- strcpy(fill, i == 0 ? "(" : " (");
- if (niss && !alg->inv[i])
- strcpy(fill, ") ");
- if (niss == alg->inv[i])
- strcpy(fill, i == 0 ? "" : " ");
-
- printf("%s%s", fill, move_string[alg->move[i]]);
- niss = alg->inv[i];
- }
-
- if (niss)
- printf(")");
-
- printf("\n");
-}
-
-void
-print_alglist(AlgList *al)
-{
- AlgListNode *i;
-
- for (i = al->first; i != NULL; i = i->next)
- print_alg(i->alg);
-}
-
-static void
-realloc_alg(Alg *alg, int n)
-{
- if (alg == NULL) {
- fprintf(stderr, "Error: trying to reallocate NULL alg.\n");
- return;
- }
-
- if (n < alg->len) {
- fprintf(stderr, "Error: alg too long for reallocation ");
- fprintf(stderr, "(%d vs %d)\n", alg->len, n);
- return;
- }
-
- if (n > 1000000) {
- fprintf(stderr, "Warning: very long alg,");
- fprintf(stderr, "something might go wrong.\n");
- }
-
- alg->move = realloc(alg->move, n * sizeof(int));
- alg->inv = realloc(alg->inv, n * sizeof(int));
- alg->allocated = n;
-}
-
-bool
-singlecwend(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;
-}
-
-void
-swapmove(Move *m1, Move *m2)
-{
- Move aux;
-
- aux = *m1;
- *m1 = *m2;
- *m2 = aux;
-}
diff --git a/src/alg.h b/src/alg.h
@@ -1,49 +0,0 @@
-#ifndef ALG_H
-#define ALG_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);
-
-// pruning and solve?
-Move base_move(Move m);
-bool commute(Move m1, Move m2);
-
-// solve
-void free_alglist(AlgList *l);
-AlgList * new_alglist();
-void append_alg(AlgList *l, Alg *alg);
-
-// solve, private
-bool singlecwend(Alg *alg);
-void swapmove(Move *m1, Move *m2);
-
-// solve, change interface
-void print_alg(Alg *alg);
-void print_alglist(AlgList *al);
-
-#endif
-
diff --git a/src/cube.c b/src/cube.c
@@ -1,11 +1,40 @@
#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];
+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\'",
+};
+static char rotation_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",
+};
+
TransGroup
tgrp_udfix = {
.n = 16,
@@ -107,6 +136,58 @@ make_solved(Cube *cube)
memset(cube->co, 0, 8 * sizeof(int));
}
+Move
+base_move(Move m)
+{
+ return m == NULLMOVE ? NULLMOVE : m - (m-1)%3;
+}
+
+Move
+inverse_move(Move m)
+{
+ return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
+}
+
+bool
+commute(Move m1, Move m2)
+{
+ if (m1 > B3 || m2 > B3) {
+ fprintf(stderr, "Unexpected commute for non-HTM\n");
+ return false;
+ }
+
+ if (m1 == NULLMOVE || m2 == NULLMOVE)
+ return m1 == m2;
+
+ return (m1-1)/6 == (m2-1)/6;
+}
+
+void
+copy_alg(Alg *src, Alg *dst)
+{
+ int i;
+
+ dst->len = src->len;
+ for (i = 0; i < src->len; i++) {
+ dst->move[i] = src->move[i];
+ dst->inv[i] = src->inv[i];
+ }
+}
+
+void
+append_move(Alg *alg, Move m, bool inverse)
+{
+ alg->move[alg->len] = m;
+ alg->inv[alg->len] = inverse;
+ alg->len++;
+}
+
+void
+apply_move(Move m, Cube *cube)
+{
+ compose(&move_array[m], cube);
+}
+
void
apply_alg(Alg *alg, Cube *cube)
{
@@ -128,17 +209,132 @@ apply_alg(Alg *alg, Cube *cube)
apply_move(alg->move[i], cube);
}
-void
-apply_move(Move m, Cube *cube)
+static Move
+read_move(char *str, int *i)
{
- compose(&move_array[m], cube);
+ Move j, m;
+ char upper, lower, inv;
+
+ for (j = U; j < NMOVES; j++) {
+ upper = move_string[j][0];
+ lower = upper - ('A' - 'a');
+ if (str[*i] == upper || (str[*i] == lower && j <= B)) {
+ m = j;
+ if (str[*i] == lower)
+ m += Uw - U;
+ if (m <= B && str[*i+1] == 'w') {
+ m += Uw - U;
+ *i += 1;
+ }
+ if (str[*i+1]=='2') {
+ m += 1;
+ *i += 1;
+ }
+ inv = str[*i+1] == '\'' ||
+ str[*i+1] == '3' ||
+ str[*i+1] == '`';
+ /* TODO: add weird apostrophes */
+ if (inv) {
+ m += 2;
+ *i += 1;
+ }
+ return m;
+ }
+ }
+
+ return NULLMOVE;
+}
+
+bool
+apply_scramble(char *str, Cube *c)
+{
+ int i;
+ bool niss;
+ Cube normal, inverse;
+ Move move;
+
+ niss = false;
+ make_solved(&normal);
+ make_solved(&inverse);
+ for (i = 0; str[i]; i++) {
+ if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
+ continue;
+
+ if ((str[i] == '(' && niss) || (str[i] == ')' && !niss)) {
+ fprintf(stderr,
+ "Error reading moves: unmatched %c\n", str[i]);
+ return false;
+ }
+
+ if (str[i] == '(' || str[i] == ')') {
+ niss = !niss;
+ continue;
+ }
+
+ /* Single slash for comments */
+ if (str[i] == '/') {
+ while (str[i] && str[i] != '\n') i++;
+ if (!str[i]) i--;
+ continue;
+ }
+
+ move = read_move(str, &i);
+ if (move == NULLMOVE)
+ return false;
+ apply_move(move, niss ? &inverse : &normal);
+ }
+
+ if (niss) {
+ fprintf(stderr, "Error reading moves: unmatched (\n");
+ return false;
+ }
+
+ invert_cube(&inverse);
+ compose(c, &inverse);
+ copy_cube(&inverse, c);
+ compose(&normal, c);
+
+ return true;
+}
+
+int
+alg_string(Alg *alg, char *str)
+{
+ int i, n;
+ bool niss;
+ Move m;
+
+ niss = false;
+ for (i = 0, n = 0; i < alg->len; i++) {
+ if (!niss && alg->inv[i]) {
+ if (i != 0)
+ str[n++] = ' ';
+ str[n++] = '(';
+ }
+ if (niss && !alg->inv[i]) {
+ str[n++] = ')';
+ str[n++] = ' ';
+ }
+ if (niss == alg->inv[i] && i != 0)
+ str[n++] = ' ';
+ m = alg->move[i];
+ str[n++] = move_string[m][0];
+ if (move_string[m][1])
+ str[n++] = move_string[m][1];
+ niss = alg->inv[i];
+ }
+
+ if (niss)
+ str[n++] = ')';
+ str[n] = 0;
+
+ return n;
}
void
apply_trans(Trans t, Cube *cube)
{
- Cube aux;
- Alg *inv;
+ Cube aux, inv;
int i;
static Cube mirror_cube = {
@@ -149,22 +345,22 @@ apply_trans(Trans t, Cube *cube)
[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);
+ make_solved(&inv);
+ apply_scramble(rotation_string[t % (NTRANS/2)], &inv);
+ invert_cube(&inv);
+ compose(&inv, cube);
compose(&aux, cube);
- apply_alg(rotation_alg[t % (NTRANS/2)], cube);
+ apply_scramble(rotation_string[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
@@ -199,7 +395,6 @@ transform_trans(Trans t, Trans m)
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
@@ -289,9 +484,6 @@ init_moves() {
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:
@@ -303,36 +495,18 @@ init_moves() {
break;
default:
make_solved(&move_array[m]);
- apply_alg(equiv_alg[m], &move_array[m]);
+ apply_scramble(equiv_alg_string[m], &move_array[m]);
break;
}
}
-
- for (m = 0; m < NMOVES; m++)
- free_alg(equiv_alg[m]);
}
static void
init_trans() {
-
- 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);
@@ -349,19 +523,16 @@ init_trans() {
}
}
- 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_scramble("R' U' F", &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);
+ apply_scramble("F' U R", &cube);
if (is_solved(&cube)) {
/* This is the inverse of the correct
value, it will be inverted later */
@@ -376,10 +547,6 @@ init_trans() {
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
diff --git a/src/cube.h b/src/cube.h
@@ -22,6 +22,7 @@
#define BINOM8ON4 70ULL
#define NMOVES 55
#define NTRANS 48
+#define MAX_ALG_LEN 22
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
@@ -55,27 +56,34 @@ typedef enum {
} 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 { Move move[MAX_ALG_LEN]; bool inv[MAX_ALG_LEN]; int len; } 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);
-void invert_cube(Cube *cube);
-bool is_solved(Cube *cube);
-void make_solved(Cube *cube);
+void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */
+void copy_cube(Cube *src, Cube *dst);
+void invert_cube(Cube *cube);
+bool is_solved(Cube *cube);
+void make_solved(Cube *cube);
-void apply_alg(Alg *alg, Cube *cube);
-void apply_move(Move m, Cube *cube);
+Move base_move(Move m);
+bool commute(Move m1, Move m2);
+Move inverse_move(Move m);
-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 copy_alg(Alg *src, Alg *dst);
+void append_move(Alg *alg, Move m, bool inverse);
+void apply_move(Move m, Cube *cube);
+void apply_alg(Alg *alg, Cube *cube);
+bool apply_scramble(char *str, Cube *c);
+int alg_string(Alg *alg, char *str);
-void init_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/main.c b/src/main.c
@@ -1,44 +1,15 @@
#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;
-}
+#define MAX_SOLS 999
int
main(int argc, char *argv[])
{
- int i, m;
+ int i, m, n;
long val;
- Alg *scramble;
- AlgList *sols;
Cube c;
SolutionType t;
+ Alg sols[999];
if (argc < 2) {
fprintf(stderr, "Not enough arguments given\n");
@@ -47,7 +18,6 @@ main(int argc, char *argv[])
m = 0;
t = NORMAL;
- scramble = new_alg("");
init_env();
init_cube();
@@ -69,17 +39,23 @@ main(int argc, char *argv[])
}
}
- scramble = read_scramble(argc - i, &argv[i]);
- if (scramble->len <= 0) {
- fprintf(stderr, "Cannot read scramble\n");
+ if (i == argc) {
+ fprintf(stderr, "No scramble given\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);
+ if (!apply_scramble(argv[i], &c)) {
+ fprintf(stderr, "Invalid scramble: %s\n", argv[i]);
+ return 5;
+ }
+
+ n = solve(&c, argv[1], m, t, uf, sols); /* TODO: trans */
+ for (i = 0; i < n; i++) {
+ char buf[66];
+ int l = alg_string(&sols[i], buf);
+ printf("%s (%d)\n", buf, l);
+ }
return 0;
}
diff --git a/src/pruning.c b/src/pruning.c
@@ -15,6 +15,44 @@ static bool write_ptable_file(PruneData *pd);
PDGenData *active_pdg[256];
+bool
+allowed_HTM(Move m)
+{
+ return m >= U && m <= B3;
+}
+
+bool
+allowed_URF(Move m)
+{
+ Move b = base_move(m);
+
+ return b == U || b == R || b == F;
+}
+
+bool
+allowed_eofb(Move m)
+{
+ Move b = base_move(m);
+
+ return b == U || b == D || b == R || b == L ||
+ ((b == F || b == B) && m == b+1);
+}
+
+bool
+allowed_drud(Move m)
+{
+ Move b = base_move(m);
+
+ return b == U || b == D ||
+ ((b == R || b == L || b == F || b == B) && m == b + 1);
+}
+
+bool
+allowed_htr(Move m)
+{
+ return allowed_HTM(m) && m == base_move(m) + 1;
+}
+
PruneData *
genptable(PDGenData *pdg)
{
diff --git a/src/pruning.h b/src/pruning.h
@@ -23,6 +23,13 @@ typedef struct {
PruneData * pd;
} PDGenData;
+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);
+
void free_pd(PruneData *pd);
PruneData * genptable(PDGenData *data);
void print_ptable(PruneData *pd);
diff --git a/src/solve.c b/src/solve.c
@@ -21,7 +21,10 @@ typedef struct {
Cube * cube;
Movable ind[MAX_N_COORD];
Step * s;
- AlgList * sols;
+ Trans t;
+ SolutionType st;
+ int * nsols;
+ Alg * sols;
int d;
int bound;
bool can_niss;
@@ -32,6 +35,7 @@ typedef struct {
Alg * current_alg;
} DfsArg;
+static void append_sol(DfsArg *arg);
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);
@@ -40,6 +44,7 @@ static void dfs(DfsArg *arg);
static void dfs_niss(DfsArg *arg);
static bool dfs_move_checkstop(DfsArg *arg);
static bool niss_makes_sense(DfsArg *arg);
+static bool singlecwend(Alg *alg);
Step eofb_HTM = {
.shortname = "eofb",
@@ -67,6 +72,21 @@ Step drfin_drud = {
Step *steps[] = { &eofb_HTM, &drud_HTM, &drfin_drud, NULL };
+static void
+append_sol(DfsArg *arg)
+{
+ int i;
+
+ copy_alg(arg->current_alg, &arg->sols[*arg->nsols]);
+ transform_alg(inverse_trans(arg->t), &arg->sols[*arg->nsols]);
+
+ if (arg->st == INVERSE)
+ for (i = 0; i < arg->sols[*arg->nsols].len; i++)
+ arg->sols[*arg->nsols].inv[i] = true;
+
+ (*arg->nsols)++;
+}
+
static bool
allowed_next(Move m, Step *s, Move l0, Move l1)
{
@@ -97,11 +117,14 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
dst->cube = src->cube;
dst->s = src->s;
+ dst->t = src->t;
+ dst->st = src->st;
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->nsols = src->nsols;
dst->sols = src->sols;
dst->current_alg = src->current_alg;
@@ -139,15 +162,17 @@ dfs(DfsArg *arg)
{
Move m;
DfsArg newarg;
+ bool len, singlecw, niss;
if (dfs_move_checkstop(arg))
return;
if (arg->bound == 0) {
- if (arg->current_alg->len == arg->d &&
- singlecwend(arg->current_alg) &&
- (!arg->can_niss || arg->has_nissed))
- append_alg(arg->sols, arg->current_alg);
+ len = arg->current_alg->len == arg->d;
+ singlecw = singlecwend(arg->current_alg);
+ niss = !arg->can_niss || arg->has_nissed;
+ if (len && singlecw && niss)
+ append_sol(arg);
return;
}
@@ -171,35 +196,38 @@ dfs(DfsArg *arg)
static void
dfs_niss(DfsArg *arg)
{
+ int i;
DfsArg newarg;
- Alg *inv;
- Cube *c;
+ Cube c, newcube;
+ Move aux;
copy_dfsarg(arg, &newarg);
/* Invert current alg and scramble */
- newarg.cube = malloc(sizeof(Cube));
- inv = inverse_alg(arg->current_alg);
- c = malloc(sizeof(Cube));
+ newarg.cube = &newcube;
+
make_solved(newarg.cube);
- apply_alg(inv, newarg.cube);
- copy_cube(arg->cube, c);
- invert_cube(c);
- compose(c, newarg.cube);
+ apply_alg(arg->current_alg, newarg.cube);
+ invert_cube(newarg.cube);
+
+ copy_cube(arg->cube, &c);
+ invert_cube(&c);
+ compose(&c, newarg.cube);
/* New indexes */
compute_ind(&newarg);
- swapmove(&(newarg.last[0]), &(newarg.lastinv[0]));
- swapmove(&(newarg.last[1]), &(newarg.lastinv[1]));
+ /* Swap last moves */
+ for (i = 0; i < 2; i++) {
+ aux = newarg.last[i];
+ newarg.last[i] = newarg.lastinv[i];
+ newarg.lastinv[i] = aux;
+ }
+
newarg.niss = !(arg->niss);
newarg.has_nissed = true;
dfs(&newarg);
-
- free_alg(inv);
- free(c);
- free(newarg.cube);
}
static bool
@@ -231,32 +259,55 @@ static bool
niss_makes_sense(DfsArg *arg)
{
Cube testcube;
+ DfsArg aux;
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 estimate_step(arg->s, arg->ind) > 0;
+ aux.cube = &testcube;
+ aux.s = arg->s;
+ /* TODO: refactor compute_ind so we don't need full arg */
+ compute_ind(&aux);
+
+ return estimate_step(aux.s, aux.ind) > 0;
+}
+
+bool
+singlecwend(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 **********************************************************/
-AlgList *
-solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
+int
+solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t, Alg *sol)
{
- int i;
- AlgList *sols;
- AlgListNode *node;
+ int i, n;
+ Alg alg;
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++)
@@ -264,7 +315,7 @@ solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
step = steps[i];
if (step == NULL) {
fprintf(stderr, "No step to solve!\n");
- return sols;
+ return 0;
}
PDGenData pdg;
pdg.moveset = step->moveset;
@@ -283,6 +334,9 @@ solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
}
}
+ alg.len = 0;
+ n = 0;
+
/* Prepare cube for solve */
arg.cube = &c;
copy_cube(cube, arg.cube);
@@ -291,8 +345,11 @@ solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
apply_trans(t, arg.cube);
arg.s = step;
compute_ind(&arg);
+ arg.t = t;
+ arg.st = st;
arg.can_niss = st == NISS;
- arg.sols = sols;
+ arg.nsols = &n;
+ arg.sols = sol;
arg.d = m;
arg.niss = false;
arg.has_nissed = false;
@@ -300,17 +357,10 @@ solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t)
arg.last[1] = NULLMOVE;
arg.lastinv[0] = NULLMOVE;
arg.lastinv[1] = NULLMOVE;
- arg.current_alg = new_alg("");
+ arg.current_alg = &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;
- }
- return sols;
+ return n;
}
diff --git a/src/solve.h b/src/solve.h
@@ -2,10 +2,9 @@
#define SOLVE_H
#include "pruning.h"
-#include "alg.h"
typedef enum { NORMAL, INVERSE, NISS } SolutionType;
-AlgList *solve(Cube *cube, char *stepstr, int m, SolutionType st, Trans t);
+int solve(Cube *cube, char *step, int m, SolutionType st, Trans t, Alg *sol);
#endif
