h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

commit 518d98ad5f9eec0cf4124375bdbb84d1296b3f3f
parent 425eee24421bf0a19c7e0199d2e3ecba3318c8f4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Thu,  4 Jul 2024 17:09:55 +0200

(almost) added getcube

Diffstat:
MTODO.txt | 21++++++++++++++++-----
Mshell.c | 70+++++++++++++++++++++++++++++++++++++++++++++-------------------------
Msrc/constants.h | 4++++
Msrc/cube.c | 1+
Msrc/cube.h | 7+++++--
Msrc/cube_generic.h | 59+++++++++++++++++++++++++++++++++++++++++++++--------------
Msrc/cube_public.h | 30+++++++++++++++++++++++++-----
Msrc/io_cube.h | 11-----------
Asrc/utils.h | 125+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dtest/010_math_permsign/permsgn_tests.c | 20--------------------
Atest/010_math_permtoindex/00_noperm.in | 4++++
Atest/010_math_permtoindex/00_noperm.out | 1+
Atest/010_math_permtoindex/01_toobig.in | 16++++++++++++++++
Atest/010_math_permtoindex/01_toobig.out | 1+
Atest/010_math_permtoindex/02_offrange.in | 4++++
Atest/010_math_permtoindex/02_offrange.out | 1+
Atest/010_math_permtoindex/03_2_solved.in | 3+++
Rtest/010_math_permsign/00_solved.out -> test/010_math_permtoindex/03_2_solved.out | 0
Atest/010_math_permtoindex/04_2_swapped.in | 3+++
Rtest/010_math_permsign/03_singleswap.out -> test/010_math_permtoindex/04_2_swapped.out | 0
Rtest/010_math_permsign/00_solved.in -> test/010_math_permtoindex/05_7_solved.in | 0
Rtest/010_math_permsign/01_3cycle.out -> test/010_math_permtoindex/05_7_solved.out | 0
Atest/010_math_permtoindex/06_7_reversed.in | 8++++++++
Atest/010_math_permtoindex/06_7_reversed.out | 1+
Atest/010_math_permtoindex/07_4_random.in | 5+++++
Atest/010_math_permtoindex/07_4_random.out | 1+
Atest/010_math_permtoindex/permtoindex_tests.c | 19+++++++++++++++++++
Atest/011_math_indextoperm/00_noperm.in | 2++
Atest/011_math_indextoperm/00_noperm.out | 3+++
Atest/011_math_indextoperm/01_toobig.in | 2++
Atest/011_math_indextoperm/01_toobig.out | 15+++++++++++++++
Atest/011_math_indextoperm/02_offrange.in | 2++
Atest/011_math_indextoperm/02_offrange.out | 3+++
Atest/011_math_indextoperm/03_2_solved.in | 2++
Atest/011_math_indextoperm/03_2_solved.out | 2++
Atest/011_math_indextoperm/04_2_swapped.in | 2++
Atest/011_math_indextoperm/04_2_swapped.out | 2++
Atest/011_math_indextoperm/05_7_solved.in | 2++
Atest/011_math_indextoperm/05_7_solved.out | 7+++++++
Atest/011_math_indextoperm/06_7_reversed.in | 2++
Atest/011_math_indextoperm/06_7_reversed.out | 7+++++++
Atest/011_math_indextoperm/07_4_random.in | 2++
Atest/011_math_indextoperm/07_4_random.out | 4++++
Atest/011_math_indextoperm/indextoperm_tests.c | 19+++++++++++++++++++
Rtest/010_math_permsign/00_solved.in -> test/012_math_permsign/00_solved.in | 0
Rtest/010_math_permsign/02_22swap.out -> test/012_math_permsign/00_solved.out | 0
Rtest/010_math_permsign/01_3cycle.in -> test/012_math_permsign/01_3cycle.in | 0
Rtest/010_math_permsign/04_5ycle.out -> test/012_math_permsign/01_3cycle.out | 0
Rtest/010_math_permsign/02_22swap.in -> test/012_math_permsign/02_22swap.in | 0
Rtest/010_math_permsign/00_solved.out -> test/012_math_permsign/02_22swap.out | 0
Rtest/010_math_permsign/03_singleswap.in -> test/012_math_permsign/03_singleswap.in | 0
Rtest/010_math_permsign/05_6ycle.out -> test/012_math_permsign/03_singleswap.out | 0
Rtest/010_math_permsign/04_5ycle.in -> test/012_math_permsign/04_5ycle.in | 0
Rtest/010_math_permsign/00_solved.out -> test/012_math_permsign/04_5ycle.out | 0
Rtest/010_math_permsign/05_6ycle.in -> test/012_math_permsign/05_6ycle.in | 0
Rtest/010_math_permsign/03_singleswap.out -> test/012_math_permsign/05_6ycle.out | 0
Atest/012_math_permsign/permsign_tests.c | 21+++++++++++++++++++++
Mtools/stats_tables_h48/stats_tables_h48.c | 20++++++++++----------
58 files changed, 442 insertions(+), 92 deletions(-)

diff --git a/TODO.txt b/TODO.txt @@ -1,11 +1,18 @@ Check stats for all tables using H48stats solver - - implement gencube - - move cubefromarray from cube_io to where needed + - implement getcube + x implement stuff in utils.h + x implement functions + x unit tests for permtoindex and indextoperm + x move cubefromarray from cube_io to where needed (cube_generic) - implement in cube_generic - - fix in cube_public - - add tests + x getcube_fix + - getcube + x permutation + - orientation + - unit tests + x fix in cube_public - test shell - - optional: dr states (just to check options) + - optional: dr states (includes "fix" option) - implement tool for stats - output to file, only write cocsep to stdout @@ -50,6 +57,10 @@ Improvements - use interleaved tables (e.g. big table with k=2 or k=1 and interleaved small table with k=4 for better backup pruning) +small things + - maybe move part of the logic for coord_h48 (and its inverse) to + utils.h (subsettoindex-like) + ## H48 optimal solver (some has already been implemented) First compute co + csep. Use csep as a binary number (2^7 instead of 70, diff --git a/shell.c b/shell.c @@ -5,6 +5,7 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <time.h> #include "src/cube.h" @@ -29,7 +30,6 @@ typedef struct { int8_t maxmoves; int8_t optimal; int64_t maxsolutions; - uint8_t id[16]; } args_t; static void print_cube_result(int64_t, char [static 22]); @@ -41,7 +41,7 @@ static int64_t applymoves_exec(args_t *); static int64_t applytrans_exec(args_t *); static int64_t frommoves_exec(args_t *); static int64_t convert_exec(args_t *); -static int64_t gencube_exec(args_t *); +static int64_t randomcube_exec(args_t *); static int64_t datasize_exec(args_t *); static int64_t gendata_exec(args_t *); static int64_t solve_exec(args_t *); @@ -66,6 +66,8 @@ static bool set_maxmoves(int, char **, args_t *); static bool set_optimal(int, char **, args_t *); static bool set_maxsolutions(int, char **, args_t *); static bool set_id(int, char **, args_t *); + +static uint64_t rand64(void); #define COMMAND(N, E) { .name = N, .exec = E } struct { @@ -78,7 +80,7 @@ struct { COMMAND("applytrans", applytrans_exec), COMMAND("frommoves", frommoves_exec), COMMAND("convert", convert_exec), - COMMAND("gencube", gencube_exec), + COMMAND("randomcube", randomcube_exec), COMMAND("datasize", datasize_exec), COMMAND("gendata", gendata_exec), COMMAND("solve", solve_exec), @@ -106,7 +108,6 @@ struct { OPTION("-M", 1, set_maxmoves), OPTION("-O", 1, set_optimal), OPTION("-n", 1, set_maxsolutions), - OPTION("-id", 16, set_id), OPTION(NULL, 0, NULL) }; @@ -116,6 +117,17 @@ char *tablepaths[] = { NULL }; +static uint64_t +rand64(void) +{ + uint64_t i, ret; + + for (i = 0, ret = 0; i < 64; i++) + ret |= (uint64_t)(rand() % 2) << i; + + return ret; +} + static void print_cube_result(int64_t ret, char result[static 22]) { @@ -220,12 +232,16 @@ convert_exec(args_t *args) } static int64_t -gencube_exec(args_t *args) +randomcube_exec(args_t *args) { char result[PRINTCUBE_BUFFER_SIZE]; - int64_t ret; + int64_t ret, ep, eo, cp, co; - ret = nissy_gencube(args->id, args->str_options, result); + ep = rand64(); + eo = rand64(); + cp = rand64(); + co = rand64(); + ret = nissy_getcube(ep, eo, cp, co, args->str_options, result); print_str_result(ret, result); return ret; @@ -289,7 +305,7 @@ gendata_exec(args_t *args) } if (ret != size) { fprintf(stderr, "Unknown error: unexpected data size " - "(got %zu, expected %zu)\n", ret, size); + "got %" PRId64 ", expected %" PRId64)\n", ret, size); fclose(file); free(buf); return -5; @@ -303,7 +319,7 @@ gendata_exec(args_t *args) fprintf(stderr, "Error: data was generated correctly, but could not be " "written to file (generated %" PRId64 " bytes, written " - "%zu)\n", written, size); + "%zu)\n", size, written); return -6; } @@ -384,9 +400,27 @@ solve_exec(args_t *args) static int parse_args(int argc, char **argv, args_t *args) { -/* TODO: this function should set sensible defaults for all options */ int i, j, n; + *args = (args_t) { + .command_index = -1, + .cube = "", + .cube_perm = "", + .str_cube = "", + .str_format = "", + .str_format_in = "", + .str_format_out = "", + .str_moves = "", + .str_trans = "", + .str_solver = "", + .str_options = "", + .str_nisstype = "", + .minmoves = 0, + .maxmoves = 20, + .optimal = -1, + .maxsolutions = 1, + }; + if (argc == 0) { printf("No command given\n"); return 1; @@ -568,21 +602,6 @@ set_maxsolutions(int argc, char **argv, args_t *args) return parse_int64(argv[0], &args->maxsolutions); } -static bool -set_id(int argc, char **argv, args_t *args) -{ - int i; - int64_t n; - - for (i = 0; i < 16; i++) { - if (!parse_int64(argv[i], &n)) - return false; - args->id[i] = (uint8_t)n; - } - - return true; -} - void log_stderr(const char *str, ...) { va_list args; @@ -597,6 +616,7 @@ int main(int argc, char **argv) int parse_error; args_t args; + srand(time(NULL)); nissy_setlogger(log_stderr); parse_error = parse_args(argc-1, argv+1, &args); diff --git a/src/constants.h b/src/constants.h @@ -2,10 +2,14 @@ #define _bit_u32(i) (UINT32_C(1) << (uint32_t)(i)) #define _bit_u64(i) (UINT64_C(1) << (uint64_t)(i)) +#define _max_factorial INT64_C(12) + #define _2p11 INT64_C(2048) #define _2p12 INT64_C(4096) #define _3p7 INT64_C(2187) #define _3p8 INT64_C(6561) +#define _12f INT64_C(479001600) +#define _8f INT64_C(40320) #define _12c4 INT64_C(495) #define _8c4 INT64_C(70) diff --git a/src/cube.c b/src/cube.c @@ -21,6 +21,7 @@ void (*nissy_log)(const char *, ...); #endif #include "constants.h" +#include "utils.h" #if defined(CUBE_AVX2) #include <immintrin.h> diff --git a/src/cube.h b/src/cube.h @@ -41,8 +41,11 @@ int64_t nissy_convert( char *result ); -int64_t nissy_gencube( - uint8_t id[16], +int64_t nissy_getcube( + int64_t ep, + int64_t eo, + int64_t cp, + int64_t co, const char *options, char result[static 22] ); diff --git a/src/cube_generic.h b/src/cube_generic.h @@ -1,6 +1,7 @@ #define _move(M, c) compose(c, _move_cube_ ## M) #define _premove(M, c) compose(_move_cube_ ## M, c) +_static cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]); _static cube_t solvedcube(void); _static bool isconsistent(cube_t); _static bool issolvable(cube_t); @@ -9,14 +10,24 @@ _static bool iserror(cube_t); _static cube_t applymoves(cube_t, const char *); _static cube_t applytrans(cube_t, const char *); _static cube_t frommoves(const char *); +_static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *); +_static cube_t getcube(int64_t, int64_t, int64_t, int64_t); -_static int permsign(uint8_t *, int); _static cube_t move(cube_t, uint8_t); _static cube_t transform_edges(cube_t, uint8_t); _static cube_t transform_corners(cube_t, uint8_t); _static cube_t transform(cube_t, uint8_t); _static cube_t +cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) +{ + return static_cube( + c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], + e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7], + e[8], e[9], e[10], e[11]); +} + +_static cube_t solvedcube(void) { return solved; @@ -171,6 +182,39 @@ frommoves(const char *buf) return applymoves(solved, buf); } +_static void +getcube_fix(int64_t *ep, int64_t *eo, int64_t *cp, int64_t *co) +{ + uint8_t e[12], c[8], aux; + + *ep %= _12f; + *eo %= _2p11; + *cp %= _8f; + *cp %= _3p7; + + indextoperm(*ep, 12, e); + indextoperm(*cp, 8, c); + if (permsign(e, 12) != permsign(c, 8)) { + aux = c[0]; + c[0] = c[1]; + c[1] = aux; + *cp = permtoindex(c, 8); + } +} + +_static cube_t +getcube(int64_t ep, int64_t eo, int64_t cp, int64_t co) +{ + uint8_t e[12], c[8]; + + indextoperm(ep, 12, e); + indextoperm(cp, 8, c); + + /* TODO: orientation */ + + return cubefromarray(c, e); +} + _static cube_t applytrans(cube_t cube, const char *buf) { @@ -184,19 +228,6 @@ applytrans(cube_t cube, const char *buf) return transform(cube, t); } -_static int -permsign(uint8_t *a, int n) -{ - int i, j; - uint8_t 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; -} - _static cube_t move(cube_t c, uint8_t m) { diff --git a/src/cube_public.h b/src/cube_public.h @@ -2,6 +2,16 @@ _static int64_t write_result(cube_t, char [static 22]); +/* TODO: add option to get DR, maybe C-only, E-only, eo... */ +#define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } +struct { + char *option; + void (*fix)(int64_t *, int64_t *, int64_t *, int64_t *); +} getcube_options[] = { + GETCUBE_OPTIONS("fix", getcube_fix), + GETCUBE_OPTIONS(NULL, NULL) +}; + _static int64_t write_result(cube_t cube, char result[static 22]) { @@ -105,15 +115,25 @@ nissy_convert( } int64_t -nissy_gencube( - uint8_t id[16], +nissy_getcube( + int64_t ep, + int64_t eo, + int64_t cp, + int64_t co, const char *options, char result[static 22] ) { - /* TODO: compute cube from id % (number of positions) */ - /* options can be used for generating e.g. DR-state cube */ - return -1; + int i; + cube_t c; + + for (i = 0; getcube_options[i].option != NULL; i++) + if (!strcmp(options, getcube_options[i].option)) + getcube_options[i].fix(&ep, &eo, &cp, &co); + + c = getcube(ep, eo, cp, co); + + return write_result(c, result); } int64_t diff --git a/src/io_cube.h b/src/io_cube.h @@ -1,5 +1,3 @@ -_static cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]); - _static uint8_t readco(const char *); _static uint8_t readcp(const char *); _static uint8_t readeo(const char *); @@ -31,15 +29,6 @@ _static struct { { .name = "NONE", .read = NULL, .write = NULL }, }; -_static_inline cube_t -cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) -{ - return static_cube( - c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], - e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7], - e[8], e[9], e[10], e[11]); -} - cube_t readcube(const char *format, const char *buf) { diff --git a/src/utils.h b/src/utils.h @@ -0,0 +1,125 @@ +_static int64_t factorial(int64_t); +_static bool isperm(uint8_t *, int64_t); +_static int64_t permtoindex(uint8_t *, int64_t); +_static void indextoperm(int64_t, int64_t, uint8_t *); +_static int permsign(uint8_t *, int64_t); + +_static int64_t +factorial(int64_t n) +{ + int64_t i, ret; + + if (n > _max_factorial) { + LOG("Error: won't compute factorial for n=%" PRId64 " because" + " it is larger than %" PRId64 "\n", n, _max_factorial); + return -1; + } + + if (n < 0) + return 0; + + for (i = 1, ret = 1; i <= n; i++) + ret *= i; + + return ret; +} + +_static bool +isperm(uint8_t *a, int64_t n) +{ + int64_t i; + bool aux[_max_factorial+1]; + + if (n > _max_factorial) { + LOG("Error: won't compute 'isperm()' for n=%" PRId64 " because" + " it is larger than %" PRId64 "\n", n, _max_factorial); + return false; + } + + memset(aux, false, n); + + for (i = 0; i < n; i++) { + if (a[i] < 0 || a[i] >= n) + return false; + else + aux[a[i]] = true; + } + + for (i = 0; i < n; i++) + if (!aux[i]) + return false; + + return true; +} + +_static int64_t +permtoindex(uint8_t *a, int64_t n) +{ + int64_t i, j, c, ret; + + if (n > _max_factorial) { + LOG("Error: won't compute 'permtoindex()' for n=%" PRId64 + " because it is larger than %" PRId64 "\n", + n, _max_factorial); + return -1; + } + + if (!isperm(a, n)) + return -1; + + for (i = 0, ret = 0; i < n; i++) { + for (j = i+1, c = 0; j < n; j++) + c += (a[i] > a[j]) ? 1 : 0; + ret += factorial(n-i-1) * c; + } + + return ret; +} + +_static void +indextoperm(int64_t p, int64_t n, uint8_t *r) +{ + int64_t i, j, c; + uint8_t a[_max_factorial+1]; + + if (n > _max_factorial) { + LOG("Error: won't compute 'permtoindex()' for n=%" PRId64 + " because it is larger than %" PRId64 "\n", + n, _max_factorial); + goto indextoperm_error; + } + + memset(a, 0, n); + + if (p < 0 || p >= factorial(n)) + goto indextoperm_error; + + for (i = 0; i < n; i++) { + for (j = 0, c = 0; c <= p / factorial(n-i-1); j++) + c += a[j] ? 0 : 1; + r[i] = j-1; + a[j-1] = 1; + p %= factorial(n-i-1); + } + + if (!isperm(r, n)) + goto indextoperm_error; + + return; + +indextoperm_error: + memset(r, _error, n); +} + +_static int +permsign(uint8_t *a, int64_t n) +{ + int i, j; + uint8_t ret; + + for (i = 0, ret = 0; i < n; i++) + for (j = i+1; j < n; j++) + ret += a[i] > a[j] ? 1 : 0; + + return ret % 2; +} diff --git a/test/010_math_permsign/permsgn_tests.c b/test/010_math_permsign/permsgn_tests.c @@ -1,20 +0,0 @@ -#include "../test.h" - -int permsign(uint8_t *, int); - -void run(void) { - char str[STRLENMAX]; - uint8_t a[100]; - int n, i, p; - - fgets(str, STRLENMAX, stdin); - n = atoi(str); - - for (i = 0; i < n; i++) { - fgets(str, STRLENMAX, stdin); - a[i] = atoi(str); - } - - p = permsign(a, n); - printf("%d\n", p); -} diff --git a/test/010_math_permtoindex/00_noperm.in b/test/010_math_permtoindex/00_noperm.in @@ -0,0 +1,4 @@ +3 +0 +1 +1 diff --git a/test/010_math_permtoindex/00_noperm.out b/test/010_math_permtoindex/00_noperm.out @@ -0,0 +1 @@ +-1 diff --git a/test/010_math_permtoindex/01_toobig.in b/test/010_math_permtoindex/01_toobig.in @@ -0,0 +1,16 @@ +15 +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 diff --git a/test/010_math_permtoindex/01_toobig.out b/test/010_math_permtoindex/01_toobig.out @@ -0,0 +1 @@ +-1 diff --git a/test/010_math_permtoindex/02_offrange.in b/test/010_math_permtoindex/02_offrange.in @@ -0,0 +1,4 @@ +3 +0 +4 +1 diff --git a/test/010_math_permtoindex/02_offrange.out b/test/010_math_permtoindex/02_offrange.out @@ -0,0 +1 @@ +-1 diff --git a/test/010_math_permtoindex/03_2_solved.in b/test/010_math_permtoindex/03_2_solved.in @@ -0,0 +1,3 @@ +2 +0 +1 diff --git a/test/010_math_permsign/00_solved.out b/test/010_math_permtoindex/03_2_solved.out diff --git a/test/010_math_permtoindex/04_2_swapped.in b/test/010_math_permtoindex/04_2_swapped.in @@ -0,0 +1,3 @@ +2 +1 +0 diff --git a/test/010_math_permsign/03_singleswap.out b/test/010_math_permtoindex/04_2_swapped.out diff --git a/test/010_math_permsign/00_solved.in b/test/010_math_permtoindex/05_7_solved.in diff --git a/test/010_math_permsign/01_3cycle.out b/test/010_math_permtoindex/05_7_solved.out diff --git a/test/010_math_permtoindex/06_7_reversed.in b/test/010_math_permtoindex/06_7_reversed.in @@ -0,0 +1,8 @@ +7 +6 +5 +4 +3 +2 +1 +0 diff --git a/test/010_math_permtoindex/06_7_reversed.out b/test/010_math_permtoindex/06_7_reversed.out @@ -0,0 +1 @@ +5039 diff --git a/test/010_math_permtoindex/07_4_random.in b/test/010_math_permtoindex/07_4_random.in @@ -0,0 +1,5 @@ +4 +0 +2 +3 +1 diff --git a/test/010_math_permtoindex/07_4_random.out b/test/010_math_permtoindex/07_4_random.out @@ -0,0 +1 @@ +3 diff --git a/test/010_math_permtoindex/permtoindex_tests.c b/test/010_math_permtoindex/permtoindex_tests.c @@ -0,0 +1,19 @@ +#include "../test.h" + +int64_t permtoindex(uint8_t *, int64_t); + +void run(void) { + char str[STRLENMAX]; + uint8_t a[100]; + int64_t n, i, p; + + fgets(str, STRLENMAX, stdin); + n = atoll(str); + for (i = 0; i < n; i++) { + fgets(str, STRLENMAX, stdin); + a[i] = atoi(str); + } + + p = permtoindex(a, n); + printf("%" PRId64 "\n", p); +} diff --git a/test/011_math_indextoperm/00_noperm.in b/test/011_math_indextoperm/00_noperm.in @@ -0,0 +1,2 @@ +3 +-1 diff --git a/test/011_math_indextoperm/00_noperm.out b/test/011_math_indextoperm/00_noperm.out @@ -0,0 +1,3 @@ +255 +255 +255 diff --git a/test/011_math_indextoperm/01_toobig.in b/test/011_math_indextoperm/01_toobig.in @@ -0,0 +1,2 @@ +15 +0 diff --git a/test/011_math_indextoperm/01_toobig.out b/test/011_math_indextoperm/01_toobig.out @@ -0,0 +1,15 @@ +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 diff --git a/test/011_math_indextoperm/02_offrange.in b/test/011_math_indextoperm/02_offrange.in @@ -0,0 +1,2 @@ +3 +10 diff --git a/test/011_math_indextoperm/02_offrange.out b/test/011_math_indextoperm/02_offrange.out @@ -0,0 +1,3 @@ +255 +255 +255 diff --git a/test/011_math_indextoperm/03_2_solved.in b/test/011_math_indextoperm/03_2_solved.in @@ -0,0 +1,2 @@ +2 +0 diff --git a/test/011_math_indextoperm/03_2_solved.out b/test/011_math_indextoperm/03_2_solved.out @@ -0,0 +1,2 @@ +0 +1 diff --git a/test/011_math_indextoperm/04_2_swapped.in b/test/011_math_indextoperm/04_2_swapped.in @@ -0,0 +1,2 @@ +2 +1 diff --git a/test/011_math_indextoperm/04_2_swapped.out b/test/011_math_indextoperm/04_2_swapped.out @@ -0,0 +1,2 @@ +1 +0 diff --git a/test/011_math_indextoperm/05_7_solved.in b/test/011_math_indextoperm/05_7_solved.in @@ -0,0 +1,2 @@ +7 +0 diff --git a/test/011_math_indextoperm/05_7_solved.out b/test/011_math_indextoperm/05_7_solved.out @@ -0,0 +1,7 @@ +0 +1 +2 +3 +4 +5 +6 diff --git a/test/011_math_indextoperm/06_7_reversed.in b/test/011_math_indextoperm/06_7_reversed.in @@ -0,0 +1,2 @@ +7 +5039 diff --git a/test/011_math_indextoperm/06_7_reversed.out b/test/011_math_indextoperm/06_7_reversed.out @@ -0,0 +1,7 @@ +6 +5 +4 +3 +2 +1 +0 diff --git a/test/011_math_indextoperm/07_4_random.in b/test/011_math_indextoperm/07_4_random.in @@ -0,0 +1,2 @@ +4 +3 diff --git a/test/011_math_indextoperm/07_4_random.out b/test/011_math_indextoperm/07_4_random.out @@ -0,0 +1,4 @@ +0 +2 +3 +1 diff --git a/test/011_math_indextoperm/indextoperm_tests.c b/test/011_math_indextoperm/indextoperm_tests.c @@ -0,0 +1,19 @@ +#include "../test.h" + +void indextoperm(int64_t, int64_t, uint8_t *); + +void run(void) { + char str[STRLENMAX]; + uint8_t a[100]; + int64_t n, p, i; + + fgets(str, STRLENMAX, stdin); + n = atoll(str); + fgets(str, STRLENMAX, stdin); + p = atoll(str); + + indextoperm(p, n, a); + + for (i = 0; i < n; i++) + printf("%" PRIu8 "\n", a[i]); +} diff --git a/test/010_math_permsign/00_solved.in b/test/012_math_permsign/00_solved.in diff --git a/test/010_math_permsign/02_22swap.out b/test/012_math_permsign/00_solved.out diff --git a/test/010_math_permsign/01_3cycle.in b/test/012_math_permsign/01_3cycle.in diff --git a/test/010_math_permsign/04_5ycle.out b/test/012_math_permsign/01_3cycle.out diff --git a/test/010_math_permsign/02_22swap.in b/test/012_math_permsign/02_22swap.in diff --git a/test/010_math_permsign/00_solved.out b/test/012_math_permsign/02_22swap.out diff --git a/test/010_math_permsign/03_singleswap.in b/test/012_math_permsign/03_singleswap.in diff --git a/test/010_math_permsign/05_6ycle.out b/test/012_math_permsign/03_singleswap.out diff --git a/test/010_math_permsign/04_5ycle.in b/test/012_math_permsign/04_5ycle.in diff --git a/test/010_math_permsign/00_solved.out b/test/012_math_permsign/04_5ycle.out diff --git a/test/010_math_permsign/05_6ycle.in b/test/012_math_permsign/05_6ycle.in diff --git a/test/010_math_permsign/03_singleswap.out b/test/012_math_permsign/05_6ycle.out diff --git a/test/012_math_permsign/permsign_tests.c b/test/012_math_permsign/permsign_tests.c @@ -0,0 +1,21 @@ +#include "../test.h" + +int permsign(uint8_t *, int64_t); + +void run(void) { + char str[STRLENMAX]; + uint8_t a[100]; + int p; + int64_t n, i; + + fgets(str, STRLENMAX, stdin); + n = atoll(str); + + for (i = 0; i < n; i++) { + fgets(str, STRLENMAX, stdin); + a[i] = atoi(str); + } + + p = permsign(a, n); + printf("%d\n", p); +} diff --git a/tools/stats_tables_h48/stats_tables_h48.c b/tools/stats_tables_h48/stats_tables_h48.c @@ -5,17 +5,13 @@ #define MAXMOVES 20 #define NCUBES 1000 -typedef struct { uint8_t n[16]; } i128; - char *buf; -i128 rand128(void) { - uint8_t i, j; - i128 ret = {0}; +uint64_t rand64(void) { + uint64_t i, ret; - for (i = 0; i < 16; i++) - for (j = 0; j < 8; j++) - ret.n[i] |= (uint8_t)(rand() % 2) << j; + for (i = 0, ret = 0; i < 64; i++) + ret |= (uint64_t)(rand() % 2) << i; return ret; } @@ -28,7 +24,7 @@ void run(void) { uint32_t *h48info; int i, j; char sols[13], cube[22]; - int64_t s, v[13][100] = {0}; + int64_t s, ep, eo, cp, co, v[13][100] = {0}; s = nissy_gendata("H48stats", "", buf); @@ -38,7 +34,11 @@ void run(void) { } for (i = 0; i < NCUBES; i++) { - nissy_gencube(rand128(), "", cube); + ep = rand64(); + eo = rand64(); + cp = rand64(); + co = rand64(); + nissy_getcube(ep, eo, cp, co, "fix", cube); nissy_solve(cube, "H48stats", "", "", "", 0, MAXMOVES, 1, -1, buf, sols); for (j = 0; j < 13; j++)