nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit 3bfd0bb403d62bd942d1912d085ea59b156062fd
parent 374c33d1412f8f3a35dd3eb874dcaef82d60fff4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Fri, 10 Feb 2023 23:30:20 +0100

Added (just a few) tests for alg and added fields to alg struct

Diffstat:
MTODO/2.1.md | 27++++++++++++++++++++++++++-
Msrc/alg.c | 113++++++++++++++++++++++++++++++++++++++++++++++---------------------------------
Msrc/alg.h | 10+++++-----
Msrc/cubetypes.h | 4++++
Msrc/solve.c | 24+++++-------------------
Atests/alg_tests.c | 266+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Atests/alg_tests.h | 20++++++++++++++++++++
Mtests/test.c | 3+++
8 files changed, 395 insertions(+), 72 deletions(-)

diff --git a/TODO/2.1.md b/TODO/2.1.md @@ -1,5 +1,31 @@ # TODO-list for version 2.1 (or is it 3.0 at this point?) +## Alg and moveset changes (prerequisite for solve.h) + +### moveset.h +* split off from alg.h + +### alg.h +* There is a (future) bug in the way the solver checks if a move can +be appended (allowed_next and similar): the last two moves are not enough. +* Example: using QTM we have last 3 moves U U D. Considering only last 2, +U could be appended, but it cannot (cancel to U'). +* Solution: the per-moveset bool allowed_next() should take an alg as +parameter. There are going to be basically two versions, one for QTM and +one for HTM (but more may be added). +* Alg should be extended to remember the list of moves on inverse / normal +separately (without looping over moves). +* Maybe another parameter to know if it can assume there has not been +any double switching, i.e. if the last moves are the only ones to +be checked and there is no need to go back further (e.g. if alg is +U (... stuff on inverse ...) D I don't want to have to check back +to the U, but in practice we can often assume this does not happen). +* Then we can remove last and lastinv from dfsdata. +* move also can_niss to alg.h +* the check for the order of the moves (to avoid counting L R and R L as +different) can be made separately. Maybe add a "compare" function for moves, +such that non-commuting moves are not comparable (return -1 0 1). + ## Rework solver * The architecture is the following: solve.h contains a solve() public @@ -24,7 +50,6 @@ necessary). Maybe cleanup solveoptions too (e.g. threads not necessary). * solve.h depends only on moves (dependency on step and trans is removed). * preparation step should be reworked, maybe removed or delegated to the specific implementations. -* allowed_moves and cancel_niss are moved to move.h. * All dfs stuff in the same function. Maybe remove also solvestop. * Move two-step solve to a different module diff --git a/src/alg.c b/src/alg.c @@ -84,30 +84,42 @@ append_move(Alg *alg, Move m, bool inverse) alg->move[alg->len] = m; alg->inv [alg->len] = inverse; alg->len++; + + if (inverse) + alg->move_inverse[alg->len_inverse++] = m; + else + alg->move_normal[alg->len_normal++] = m; } 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; + static int aux[] = { + [NULLMOVE] = 0, + + [U] = 1, [U2] = 1, [U3] = 1, + [D] = 1, [D2] = 1, [D3] = 1, + [Uw] = 1, [Uw2] = 1, [Uw3] = 1, + [Dw] = 1, [Dw2] = 1, [Dw3] = 1, + [E] = 1, [E2] = 1, [E3] = 1, + [y] = 1, [y2] = 1, [y3] = 1, + + [R] = 2, [R2] = 2, [R3] = 2, + [L] = 2, [L2] = 2, [L3] = 2, + [Rw] = 2, [Rw2] = 2, [Rw3] = 2, + [Lw] = 2, [Lw2] = 2, [Lw3] = 2, + [M] = 2, [M2] = 2, [M3] = 2, + [x] = 2, [x2] = 2, [x3] = 2, + + [F] = 3, [F2] = 3, [F3] = 3, + [B] = 3, [B2] = 3, [B3] = 3, + [Fw] = 3, [Fw2] = 3, [Fw3] = 3, + [Bw] = 3, [Bw2] = 3, [Bw3] = 3, + [S] = 3, [S2] = 3, [S3] = 3, + [z] = 3, [z2] = 3, [z3] = 3, + }; - return -1; + return aux[m]; } Move @@ -137,7 +149,7 @@ compose_alg(Alg *alg1, Alg *alg2) void copy_alg(Alg *src, Alg *dst) { - dst->len = 0; /* Overwrites */ + dst->len = dst->len_normal = dst->len_inverse = 0; compose_alg(dst, src); } @@ -169,16 +181,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) { @@ -234,10 +236,14 @@ new_alg(char *str) 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; + alg->allocated = 30; + alg->move = malloc(alg->allocated * sizeof(Move)); + alg->inv = malloc(alg->allocated * sizeof(bool)); + alg->move_normal = malloc(alg->allocated * sizeof(Move)); + alg->move_inverse = malloc(alg->allocated * sizeof(Move)); + alg->len = 0; + alg->len_normal = 0; + alg->len_inverse = 0; niss = false; for (i = 0; str[i]; i++) { @@ -246,13 +252,13 @@ new_alg(char *str) if (str[i] == '(' && niss) { fprintf(stderr, "Error reading moves: nested ( )\n"); - alg->len = 0; + alg->len = alg->len_normal = alg->len_inverse = 0; return alg; } if (str[i] == ')' && !niss) { fprintf(stderr, "Error reading moves: unmatched )\n"); - alg->len = 0; + alg->len = alg->len_normal = alg->len_inverse = 0; return alg; } @@ -319,7 +325,7 @@ new_alg(char *str) if (niss) { fprintf(stderr, "Error reading moves: unmatched (\n"); - alg->len = 0; + alg->len = alg->len_normal = alg->len_inverse = 0; } return alg; @@ -349,6 +355,19 @@ on_inverse(Alg *alg) return ret; } +bool +possible_next(Move m, Moveset *ms, Move l0, Move l1) +{ + bool allowed, order; + uint64_t mbit; + + mbit = ((uint64_t)1) << m; + allowed = mbit & ms->mask[l1][l0]; + order = !commute(l0, m) || l0 < m; + + return allowed && order; +} + void print_alg(Alg *alg, bool l) { @@ -404,8 +423,10 @@ realloc_alg(Alg *alg, int n) fprintf(stderr, "something might go wrong.\n"); } - alg->move = realloc(alg->move, n * sizeof(int)); - alg->inv = realloc(alg->inv, n * sizeof(int)); + alg->move = realloc(alg->move, n * sizeof(int)); + alg->inv = realloc(alg->inv, n * sizeof(int)); + alg->move_normal = realloc(alg->move_normal, n * sizeof(int)); + alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int)); alg->allocated = n; } @@ -455,14 +476,12 @@ unniss(Alg *alg) ret = new_alg(""); - 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); - + for (i = 0; i < alg->len_normal; i++) + append_move(ret, alg->move_normal[i], false); + + for (i = 0; i < alg->len_inverse; i++) + append_move(ret, inverse_move(alg->move_inverse[i]), false); + return ret; } @@ -483,7 +502,7 @@ init_moveset(Moveset *ms) 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++) { + 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); diff --git a/src/alg.h b/src/alg.h @@ -15,6 +15,11 @@ 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 moveset_to_list(Moveset ms, Move *lst); +void init_moveset(Moveset *ms); +bool possible_next(Move m, Moveset *ms, Move l0, Move l1); + void append_alg(AlgList *l, Alg *alg); void append_move(Alg *alg, Move m, bool inverse); Move base_move(Move m); @@ -23,12 +28,9 @@ bool commute(Move m1, Move m2); void copy_alg(Alg *src, Alg *dst); void free_alg(Alg *alg); 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); @@ -38,8 +40,6 @@ 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 diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -122,6 +122,10 @@ alg bool * inv; int len; int allocated; + Move * move_normal; + int len_normal; + Move * move_inverse; + int len_inverse; }; struct diff --git a/src/solve.c b/src/solve.c @@ -4,7 +4,6 @@ /* Local functions ***********************************************************/ -static bool allowed_next(Move move, Step *s, Move l0, Move l1); static bool cancel_niss(DfsArg *arg); static void copy_dfsarg(DfsArg *src, DfsArg *dst); static void dfs(DfsArg *arg); @@ -19,19 +18,6 @@ static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); /* Local functions ***********************************************************/ static bool -allowed_next(Move m, Step *s, Move l0, Move l1) -{ - bool allowed, order; - uint64_t mbit; - - mbit = ((uint64_t)1) << m; - allowed = mbit & s->moveset->mask[l1][l0]; - order = !commute(l0, m) || l0 < m; - - return allowed && order; -} - -static bool cancel_niss(DfsArg *arg) { Moveset *ms; @@ -82,16 +68,14 @@ copy_dfsarg(DfsArg *src, DfsArg *dst) dst->ind[i].t = src->ind[i].t; } -/* src->s->copy_extra(src, dst); -*/ } static void dfs(DfsArg *arg) { int i; - Move m; + Move m, l0, l1; DfsArg newarg; if (dfs_move_checkstop(arg)) @@ -105,9 +89,11 @@ dfs(DfsArg *arg) for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { m = arg->s->moveset->sorted_moves[i]; - if (allowed_next(m, arg->s, arg->last[0], arg->last[1])) { + l0 = arg->last[0]; + l1 = arg->last[1]; + if (possible_next(m, arg->s->moveset, l0, l1)) { copy_dfsarg(arg, &newarg); - newarg.last[1] = arg->last[0]; + newarg.last[1] = l0; newarg.last[0] = m; append_move(arg->current_alg, m, newarg.niss); dfs(&newarg); diff --git a/tests/alg_tests.c b/tests/alg_tests.c @@ -0,0 +1,266 @@ +#include "alg_tests.h" + +bool testmethod_append_move(void *); +bool testmethod_new_alg(void *); +/* +bool testmethod_compose_alg(void *); +bool testmethod_inverse_alg(void *); +bool testmethod_on_inverse(void *); +bool testmethod_unniss(void *); +*/ + +typedef struct { + Move *move; + bool *inv; + int len; + Move m; + bool inverse; +} append_move_t; + +Move m_app1[] = {F, x, D3}; +bool i_app1[] = {true, false, false}; +append_move_t append_move_case1 = { + .move = m_app1, + .inv = i_app1, + .len = 3, + .m = L3, + .inverse = false, +}; + +Move m_app2[] = {S, U, x2, M2}; +bool i_app2[] = {true, false, true, true}; +append_move_t append_move_case2 = { + .move = m_app2, + .inv = i_app2, + .len = 4, + .m = R, + .inverse = true, +}; + +Move m_app3[] = {U, U, U, U, U}; +bool i_app3[] = {false, false, false, false, false}; +append_move_t append_move_case3 = { + .move = m_app3, + .inv = i_app3, + .len = 5, + .m = U, + .inverse = false, +}; + +append_move_t *append_move_cases[] = { + &append_move_case1, + &append_move_case2, + &append_move_case3, +}; + +Test test_append_move = { + .name = "Appending a move to and alg", + .t = testmethod_append_move, + .cases = (void **)append_move_cases, +}; + +typedef struct { + char *str; + Move *move; + bool *inv; + int len; + Move *move_normal; + int len_normal; + Move *move_inverse; + int len_inverse; +} new_alg_t; + +/* Alg F U B' (L3 D) x M (S) y3 */ +Move m_new1[] = {F, U, B3, L3, D, x, M, S, y3}; +Move mn_new1[] = {F, U, B3, x, M, y3}; +Move mi_new1[] = {L3, D, S}; +bool i_new1[] = {false, false, false, true, true, false, false, true, false}; +new_alg_t new_alg_case1 = { + .str = "F U B' (L3 D) x M (S) y3", + .move = m_new1, + .inv = i_new1, + .len = 9, + .move_normal = mn_new1, + .len_normal = 6, + .move_inverse = mi_new1, + .len_inverse = 3, +}; +new_alg_t *new_alg_cases[] = {&new_alg_case1}; + +Test test_new_alg = { + .name = "Initializing an alg from a string", + .t = testmethod_new_alg, + .cases = (void **)new_alg_cases, +}; + +Test *alg_all_tests[] = { + &test_append_move, + &test_new_alg, +/* + &test_append_alg, + &test_compose_alg, + &test_inverse_alg, + &test_on_inverse, + &test_unniss, +*/ + NULL +}; +TestSuite alg_suite = { + .setup = NULL, + .tests = alg_all_tests, + .teardown = NULL, +}; + +TestSuite *alg_suites[] = { + &alg_suite, + NULL +}; + +bool +testmethod_append_move(void *a) +{ + append_move_t *b = (append_move_t *)a; + int li, ln; + Alg *alg; + + /* Small to test reallocation */ + alg = malloc(sizeof(Alg)); + alg->allocated = 5; + alg->move = malloc(alg->allocated * sizeof(Move)); + alg->inv = malloc(alg->allocated * sizeof(bool)); + alg->len = b->len; + memcpy(alg->move, b->move, alg->len * sizeof(Move)); + memcpy(alg->inv, b->inv, alg->len * sizeof(bool)); + alg->move_normal = malloc(alg->allocated * sizeof(Move)); + alg->move_inverse = malloc(alg->allocated * sizeof(Move)); + + li = ln = 0; + for (int i = 0; i < alg->len; i++) { + if (alg->inv[i]) + alg->move_inverse[li++] = alg->move[i]; + else + alg->move_normal[ln++] = alg->move[i]; + } + alg->len_inverse = li; + alg->len_normal = ln; + + append_move(alg, b->m, b->inverse); + + if (alg->len != b->len + 1) { + printf("Alg has wrong len (%d instead of %d)\n", + alg->len, b->len + 1); + goto append_move_fail; + } + if (alg->move[alg->len-1] != b->m) { + printf("Wrong last move (%s instead of %s)\n", + move_string(alg->move[alg->len-1]), + move_string(b->m)); + goto append_move_fail; + } + if (alg->inv[alg->len-1] != b->inverse) { + printf("Wrong inverse flag for last move " + "(%s instead of %s)\n", + b->inverse ? "normal" : "inverse", + b->inverse ? "inverse" : "normal"); + goto append_move_fail; + } + if (b->inverse) { + if (alg->len_inverse != li + 1 || + alg->len_normal != ln) { + printf("%d moves on normal (should be %d)" + " and %d on inverse (should be %d)\n", + alg->len_normal, ln, + alg->len_inverse, li + 1); + goto append_move_fail; + } + if (alg->move_inverse[alg->len_inverse-1] != b->m) { + printf("Wrong move on inverse (%s instead of %s)\n", + move_string(alg->move_inverse[alg->len-1]), + move_string(b->m)); + goto append_move_fail; + } + } else { + if (alg->len_inverse != li || + alg->len_normal != ln + 1) { + printf("%d moves on normal (should be %d)" + " and %d on inverse (should be %d)\n", + alg->len_normal, ln, + alg->len_inverse, li + 1); + goto append_move_fail; + } + if (alg->move_normal[alg->len_normal-1] != b->m) { + printf("Wrong move on normal (%s instead of %s)\n", + move_string(alg->move_normal[alg->len-1]), + move_string(b->m)); + goto append_move_fail; + } + } + + free(alg); + return true; + +append_move_fail: + free(alg); + return false; +} + +bool +testmethod_new_alg(void *a) +{ + new_alg_t *b = (new_alg_t *)a; + Alg *alg = new_alg(b->str); + + if (alg->len != b->len) { + printf("Algs have different length (%d instead of %d)\n", + alg->len, b->len); + goto new_alg_fail; + } + + for (int i = 0; i < alg->len; i++) { + if (alg->move[i] != b->move[i] || alg->inv[i] != b->inv[i]) { + printf("Algs differ on move %d\n", i); + printf("Expected: %s\nActual: ", b->str); + print_alg(alg, false); + goto new_alg_fail; + } + } + + if (alg->len_normal != b->len_normal) { + printf("Algs have different number of moves on normal" + " (%d instead of %d)\n", + alg->len_normal, b->len_normal); + goto new_alg_fail; + } + for (int i = 0; i < alg->len_normal; i++) { + if (alg->move_normal[i] != b->move_normal[i]) { + printf("Algs have different move %d on normal" + " (%s instead of %s)\n", i, + move_string(alg->move_normal[i]), + move_string(b->move_normal[i])); + goto new_alg_fail; + } + } + + if (alg->len_inverse != b->len_inverse) { + printf("Algs have different number of moves on inverse" + " (%d instead of %d)\n", + alg->len_inverse, b->len_inverse); + goto new_alg_fail; + } + for (int i = 0; i < alg->len_inverse; i++) { + if (alg->move_inverse[i] != b->move_inverse[i]) { + printf("Algs have different move %d on inverse:\n" + " (%s instead of %s)\n", i, + move_string(alg->move_inverse[i]), + move_string(b->move_inverse[i])); + goto new_alg_fail; + } + } + + free(alg); + return true; + +new_alg_fail: + free(alg); + return false; +} diff --git a/tests/alg_tests.h b/tests/alg_tests.h @@ -0,0 +1,20 @@ +#ifndef ALG_TESTS_H +#define ALG_TESTS_H + +#include "../src/alg.h" +#include "test_common.h" + +extern Test test_append_move; +extern Test test_new_alg; +/* +extern Test test_compose_alg; +extern Test test_inverse_alg; +extern Test test_on_inverse; +extern Test test_unniss; +*/ + +extern TestSuite alg_suite; + +extern TestSuite *alg_suites[]; + +#endif diff --git a/tests/test.c b/tests/test.c @@ -1,5 +1,6 @@ #include <stdio.h> +#include "alg_tests.h" #include "coord_tests.h" #include "fst_tests.h" @@ -54,9 +55,11 @@ int main(int argc, char *argv[]) { init_trans(); /**************************************/ + TestModule alg = { .name = "alg", .suites = alg_suites }; TestModule fst = { .name = "fst", .suites = fst_suites }; TestModule coord = { .name = "coord", .suites = coord_suites }; TestModule *modules[999] = { + &alg, &fst, &coord, NULL