commit 3c9efb490ccbe1b0d7768d77fcdcac012c00e8c6
parent 05bdcfef13ef2bdd05df6af13a74ec3cd7fcd22f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun, 30 Jun 2024 12:44:47 +0200
Added a solver, but found out h48 table is broken
Diffstat:
10 files changed, 265 insertions(+), 60 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -5,6 +5,7 @@ gen
debuggen
perf.data
perf.data.old
+run
tables/*
test/*/runtest
test/run
diff --git a/Makefile b/Makefile
@@ -24,4 +24,8 @@ shell: cube.o
mkdir -p tables
${CC} ${CFLAGS} -o run cube.o shell.c
-.PHONY: all clean test benchmark shell
+debugshell: debugcube.o
+ mkdir -p tables
+ ${CC} ${DBGFLAGS} -o run debugcube.o shell.c
+
+.PHONY: all clean test benchmark shell debugshell
diff --git a/README.md b/README.md
@@ -27,3 +27,20 @@ $ TEST=coord make test
```
Due to ongoing changes, benchmarks are currently broken.
+
+## Solving
+
+Notes for myself while this is work in progress
+
+```
+$ make shell
+$ ./run frommoves -moves (scramble)
+```
+
+copy the result, then
+
+```
+$ ./run solve -solver "H48" -options "2;20" -n 1 -M 10 -cube (paste here)
+```
+
+Options can be changed from `2;20` to `n;20` for larger tables.
diff --git a/TODO.txt b/TODO.txt
@@ -1,8 +1,16 @@
Solver
- - write a solver (how many tricks? some, but not all are needed)
+ - fix and cleanup current implementation
+ - fails for UFRUFU when using full table
+ SOMETHING IS WRONG FOR coord_h48 = 3! (pvalue 15??)
+ - do not copy dfsarg, change and undo
+ - implement and use premove (and test) instead of inverting
- benchmark for solve
table generation, where to keep tables? in benchmark folder or in tables/?
+ - more tricks for solver, optimize, try larger tables
- remove solve_simple and maybe the whole solve_generic
+ - shell: silently accept other formats too?
+ - shell: allow generating multiple tables for different options
+ - gendata: move info at start of tables?
Cleanup cube_public and interface
- remove options, use only solver name
@@ -17,6 +25,8 @@ Goal: find out which k value is best
Improvements
- check hash of generated data
+ - use interleaved tables (e.g. big table with k=2 or k=1 and interleaved
+ small table with k=4 for better backup pruning)
## H48 optimal solver (some has already been implemented)
diff --git a/shell.c b/shell.c
@@ -1,5 +1,6 @@
#include <inttypes.h>
#include <errno.h>
+#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
@@ -28,7 +29,6 @@ typedef struct {
int8_t maxmoves;
int8_t optimal;
int64_t maxsolutions;
- int64_t datasize; /* Option for gendata + solve, TODO change? */
} args_t;
static void print_cube_result(int64_t, char [static 22]);
@@ -39,9 +39,7 @@ static int64_t inverse_exec(args_t *);
static int64_t applymoves_exec(args_t *);
static int64_t applytrans_exec(args_t *);
static int64_t frommoves_exec(args_t *);
-static int64_t readcube_exec(args_t *);
-static int64_t writecube_exec(args_t *);
-static int64_t convertcube_exec(args_t *);
+static int64_t convert_exec(args_t *);
static int64_t datasize_exec(args_t *);
static int64_t gendata_exec(args_t *);
static int64_t solve_exec(args_t *);
@@ -76,9 +74,7 @@ struct {
COMMAND("applymoves", applymoves_exec),
COMMAND("applytrans", applytrans_exec),
COMMAND("frommoves", frommoves_exec),
- COMMAND("readcube", readcube_exec),
- COMMAND("writecube", writecube_exec),
- COMMAND("convertcube", convertcube_exec),
+ COMMAND("convert", convert_exec),
COMMAND("datasize", datasize_exec),
COMMAND("gendata", gendata_exec),
COMMAND("solve", solve_exec),
@@ -199,43 +195,19 @@ frommoves_exec(args_t *args)
char result[22];
int64_t ret;
- ret = nissy_frommoves(args->str_trans, result);
+ ret = nissy_frommoves(args->str_moves, result);
print_cube_result(ret, result);
return ret;
}
static int64_t
-readcube_exec(args_t *args)
-{
- char result[22];
- int64_t ret;
-
- ret = nissy_readcube(args->str_format, args->str_cube, result);
- print_cube_result(ret, result);
-
- return ret;
-}
-
-static int64_t
-writecube_exec(args_t *args)
-{
- char result[PRINTCUBE_BUFFER_SIZE];
- int64_t ret;
-
- ret = nissy_writecube(args->str_format, args->str_cube, result);
- print_str_result(ret, result);
-
- return ret;
-}
-
-static int64_t
-convertcube_exec(args_t *args)
+convert_exec(args_t *args)
{
char result[PRINTCUBE_BUFFER_SIZE];
int64_t ret;
- ret = nissy_convertcube(
+ ret = nissy_convert(
args->str_format_in, args->str_format_out, args->str_cube, result);
print_str_result(ret, result);
@@ -275,14 +247,17 @@ gendata_exec(args_t *args)
if (tablepaths[i] == NULL) {
fprintf(stderr, "Cannot write data to file\n");
+ fclose(file);
return -2;
}
size = nissy_datasize(args->str_solver, args->str_options);
+
if (size < 0) {
fprintf(stderr,
"Unknown error in retrieving data size"
"(make sure solver is valid)\n");
+ fclose(file);
return -3;
}
@@ -291,19 +266,23 @@ gendata_exec(args_t *args)
ret = nissy_gendata(args->str_solver, args->str_options, buf);
if (ret < 0) {
fprintf(stderr, "Unknown error in generating data\n");
+ fclose(file);
free(buf);
return -4;
}
if (ret != size) {
- fprintf(stderr, "Unknown error: unexpected data size\n");
+ fprintf(stderr, "Unknown error: unexpected data size "
+ "(got %zu, expected %zu)\n", ret, size);
+ fclose(file);
free(buf);
return -5;
}
written = fwrite(buf, size, 1, file);
+ fclose(file);
free(buf);
- if (written != (int64_t)size) {
+ if (written != 1) {
fprintf(stderr,
"Error: data was generated correctly, but could not be "
"written to file (generated %" PRId64 " bytes, written "
@@ -311,7 +290,6 @@ gendata_exec(args_t *args)
return -6;
}
- args->datasize = size;
fprintf(stderr, "Data written to %s\n", path);
return 0;
@@ -323,7 +301,7 @@ solve_exec(args_t *args)
int i;
FILE *file;
char *buf, solutions[SOLUTIONS_BUFFER_SIZE], path[MAX_PATH_LENGTH];
- int64_t ret, gendata_ret;
+ int64_t ret, gendata_ret, size;
size_t read;
for (i = 0; tablepaths[i] != NULL; i++) {
@@ -344,23 +322,30 @@ solve_exec(args_t *args)
}
/* Ugh, this is not elegant TODO */
- for (i = 0; tablepaths[i] != NULL; i++) {
- strcpy(path, tablepaths[i]);
- strcat(path, args->str_solver);
- file = fopen(path, "rb");
- if (file != NULL)
- break;
+ if (file == NULL) {
+ for (i = 0; tablepaths[i] != NULL; i++) {
+ strcpy(path, tablepaths[i]);
+ strcat(path, args->str_solver);
+ file = fopen(path, "rb");
+ if (file != NULL)
+ break;
+ }
}
if (tablepaths[i] == NULL) {
fprintf(stderr, "Error: data file not found\n");
+ fclose(file);
return -1;
}
- buf = malloc(args->datasize);
- read = fread(buf, args->datasize, 1, file);
- if (read != args->datasize) {
- fprintf(stderr, "Error reading data from file\n");
+ size = nissy_datasize(args->str_solver, args->str_options);
+ buf = malloc(size);
+ read = fread(buf, size, 1, file);
+ fclose(file);
+ if (read != 1) {
+ fprintf(stderr, "Error reading data from file: "
+ "fread() returned %zu instead of 1 when attempting to"
+ "read %" PRId64 " bytes from file %s\n", read, size, path);
return -2;
}
@@ -413,7 +398,7 @@ parse_args(int argc, char **argv, args_t *args)
options[j].name);
return 1;
}
- if (!options[j].set(n, argv+i, args)) {
+ if (!options[j].set(n, argv+i+1, args)) {
fprintf(stderr,
"Error parsing arguments for option %s\n",
options[j].name);
@@ -448,7 +433,8 @@ parse_int64(char *argv, int64_t *result)
{
*result = strtoll(argv, NULL, 10);
- return errno != 0;
+ /* TODO: figure out how errno works and use it */
+ return true;
}
static bool
@@ -565,11 +551,22 @@ set_maxsolutions(int argc, char **argv, args_t *args)
return parse_int64(argv[0], &args->maxsolutions);
}
+void log_stderr(const char *str, ...)
+{
+ va_list args;
+
+ va_start(args, str);
+ vfprintf(stderr, str, args);
+ va_end(args);
+}
+
int main(int argc, char **argv)
{
int parse_error;
args_t args;
+ nissy_setlogger(log_stderr);
+
parse_error = parse_args(argc-1, argv+1, &args);
if (parse_error)
return parse_error;
diff --git a/src/cube_public.h b/src/cube_public.h
@@ -89,7 +89,7 @@ nissy_frommoves(
}
int64_t
-nissy_convertcube(
+nissy_convert(
const char *format_in,
const char *format_out,
const char *cube_string,
@@ -155,6 +155,7 @@ nissy_solve(
{
cube_t c;
int64_t ret;
+ int h;
c = readcube_B32(cube);
@@ -188,8 +189,12 @@ nissy_solve(
return -1;
}
- if (!strcmp(solver, "h48")) {
- LOG("h48 solver not implemented yet\n");
+ /* TODO define and use solve_options_t */
+ if (!strcmp(solver, "H48")) {
+ h = atoi(options); /* TODO: better parsing */
+ ret = solve_h48(
+ c, minmoves, maxmoves, maxsolutions,
+ (uint8_t)h, data, solutions);
ret = -1;
} else if (!strcmp(solver, "simple")) {
ret = solve_simple(
diff --git a/src/solve_generic.h b/src/solve_generic.h
@@ -21,7 +21,7 @@ solve_generic_appendsolution(dfsarg_generic_t *arg)
{
int strl;
- strl = writemoves(arg->moves, arg->depth, *arg->nextsol);
+ strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
LOG("Solution found: %s\n", *arg->nextsol);
*arg->nextsol += strl;
**arg->nextsol = '\n';
@@ -53,7 +53,6 @@ solve_generic_dfs(dfsarg_generic_t *arg)
return 1;
}
- /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */
nextarg = *arg;
nextarg.nmoves = arg->nmoves + 1;
for (m = 0, ret = 0; m < 18; m++) {
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -11,6 +11,8 @@
#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16))
#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8))
#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8))
+#define CBOUND_MASK UINT32_C(0xFF)
+#define CBOUND(x) ((x) & CBOUND_MASK)
#define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h))
#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8))
@@ -19,6 +21,8 @@
#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8))
#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8)))
+#define MAX_SOLUTION_LENGTH 20
+
typedef struct {
cube_t cube;
uint8_t depth;
@@ -39,6 +43,20 @@ typedef struct {
cube_t *crep;
} bfsarg_esep_t;
+typedef struct {
+ cube_t cube;
+ cube_t inverse;
+ int8_t nmoves;
+ int8_t depth;
+ uint8_t moves[MAX_SOLUTION_LENGTH];
+ int64_t *nsols;
+ int64_t maxsolutions;
+ uint8_t h;
+ uint32_t *cocsepdata;
+ uint32_t *h48data;
+ char **nextsol;
+} dfsarg_solveh48_t;
+
_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
@@ -53,6 +71,13 @@ _static_inline void set_visited(uint8_t *, int64_t);
_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
+_static void solve_h48_appendsolution(dfsarg_solveh48_t *);
+_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
+_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
+_static_inline bool solve_h48_stop(dfsarg_solveh48_t *);
+_static int64_t solve_h48_dfs(dfsarg_solveh48_t *);
+_static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
+
_static_inline int64_t
coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
{
@@ -238,8 +263,11 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
cube_t crep[COCSEP_CLASSES];
size_t cocsepsize, infosize;
+ /* TODO: move info at start of tables (all tables!) */
infosize = 4 * maxdepth;
cocsepsize = gendata_cocsep(buf, selfsim, crep);
+ infosize = 88;
+
if (buf == NULL)
goto gendata_h48_return_size;
@@ -272,7 +300,6 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
}
info[0] = arg.depth-1;
- infosize = 4 * (size_t)(info[0] + 2);
LOG("h48 pruning table computed\n");
LOG("Maximum pruning value: %" PRIu32 "\n", info[0]);
@@ -353,3 +380,148 @@ set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
buf32[ESEP_IND(i)] =
(buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i));
}
+
+_static void
+solve_h48_appendsolution(dfsarg_solveh48_t *arg)
+{
+ int strl;
+
+ strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
+ LOG("Solution found: %s\n", *arg->nextsol);
+ *arg->nextsol += strl;
+ **arg->nextsol = '\n';
+ (*arg->nextsol)++;
+ (*arg->nsols)++;
+}
+
+_static_inline int8_t
+get_h48_cdata(cube_t cube, uint32_t *cocsepdata, uint32_t *cdata)
+{
+ int64_t coord;
+
+ coord = coord_cocsep(cube);
+ *cdata = cocsepdata[coord];
+
+ return CBOUND(*cdata);
+}
+
+_static_inline int8_t
+get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data)
+{
+ int64_t coord;
+
+ coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
+ return get_esep_pval(h48data, coord);
+}
+
+_static_inline bool
+solve_h48_stop(dfsarg_solveh48_t *arg)
+{
+ uint32_t data, data_inv;
+ int8_t bound;
+
+ bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
+ if (bound + arg->nmoves > arg->depth)
+ return true;
+
+ bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
+ if (bound + arg->nmoves > arg->depth)
+ return true;
+
+/*
+ bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data);
+LOG("Using pval %" PRId8 "\n", bound);
+ if (bound + arg->nmoves > arg->depth)
+ return true;
+
+ bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data);
+ if (bound + arg->nmoves > arg->depth)
+ return true;
+*/
+
+ return false;
+}
+
+_static int64_t
+solve_h48_dfs(dfsarg_solveh48_t *arg)
+{
+ dfsarg_solveh48_t nextarg;
+ int64_t ret;
+ uint8_t m;
+
+ if (*arg->nsols == arg->maxsolutions)
+ return 0;
+
+ if (solve_h48_stop(arg))
+ return 0;
+
+ if (issolved(arg->cube)) {
+ if (arg->nmoves != arg->depth)
+ return 0;
+ solve_h48_appendsolution(arg);
+ return 1;
+ }
+
+ /* TODO: avoid copy, change arg and undo changes after recursion */
+ nextarg = *arg;
+ nextarg.nmoves = arg->nmoves + 1;
+ ret = 0;
+ for (m = 0; m < 18; m++) {
+ nextarg.moves[arg->nmoves] = m;
+ if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
+ /* If a move is not allowed, neither are its 180
+ * and 270 degree variations */
+ m += 2;
+ continue;
+ }
+ nextarg.cube = move(arg->cube, m);
+ nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
+ ret += solve_h48_dfs(&nextarg);
+ }
+
+ return ret;
+}
+
+_static int64_t
+solve_h48(
+ cube_t cube,
+ int8_t minmoves,
+ int8_t maxmoves,
+ int8_t maxsolutions,
+ uint8_t h,
+ const void *data,
+ char *solutions
+)
+{
+ int64_t nsols;
+ dfsarg_solveh48_t arg;
+
+ arg = (dfsarg_solveh48_t) {
+ .cube = cube,
+ .inverse = inverse(cube),
+ .nsols = &nsols,
+ .maxsolutions = maxsolutions,
+ .h = h,
+ .cocsepdata = (uint32_t *)data,
+ .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4,
+ .nextsol = &solutions
+ };
+
+ nsols = 0;
+ for (arg.depth = minmoves;
+ arg.depth <= maxmoves && nsols < maxsolutions;
+ arg.depth++)
+ {
+ LOG("Found %" PRId64 " solutions, searching at depth %"
+ PRId8 "\n", nsols, arg.depth);
+ arg.nmoves = 0;
+ solve_h48_dfs(&arg);
+ }
+
+/*
+for (int64_t i = 0; i < 4; i++)
+LOG("Data for coord = %" PRId64 ": %" PRIu8 "\n",
+i, get_esep_pval(arg.h48data, i));
+*/
+ return nsols;
+}
diff --git a/test/103_gendata_h48/00_h_0.out b/test/103_gendata_h48/00_h_0.out
@@ -1,4 +1,4 @@
-59903545
+59903605
cocsepdata:
Classes: 3393
diff --git a/test/103_gendata_h48/01_h_1.out b/test/103_gendata_h48/01_h_1.out
@@ -1,4 +1,4 @@
-118687270
+118687330
cocsepdata:
Classes: 3393
