commit 61e03f9f4eecf3d5811b11c44c9ef778f0a93bc7 parent a016aa7f78c86c59bab3ae4970f8cc339186bc91 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sun, 14 Jul 2024 21:28:37 +0200 Found a sneaky bug (it's all a mess now) Diffstat:
28 files changed, 148 insertions(+), 48 deletions(-)
diff --git a/Makefile b/Makefile @@ -15,7 +15,7 @@ clean: rm -rf *.o run test: debugcube.o - CC="${CC} ${DBGFLAGS}" ./test/test.sh + CC="${CC} -D${CUBETYPE} ${DBGFLAGS}" ./test/test.sh tool: cube.o mkdir -p tools/results diff --git a/TODO.txt b/TODO.txt @@ -1,3 +1,12 @@ +Bug in cocsepdata + - Add tests for ttrep + - check that ttrep indeed brings to representative + - Fix? + - Once fixed, fix other tests + - maybe add longtest, e.g. as a tool? + - Clean up mixed bfs fromdone / fromnew, use as new for h0k4 + - Re-do stats + Check stats for all tables using H48stats solver - try DFS for h0 solver - compare results, the bfs method could be wrong diff --git a/src/solve_h48.h b/src/solve_h48.h @@ -244,7 +244,7 @@ invcoord_h48(int64_t i, const cube_t *crep, uint8_t h) /* Each element of the cocsep table is a uint32_t used as follows: - Lowest 8-bit block: pruning value - - Second-lower 8-bit block: "ttrep" (transformation to representative) + - Second-lowest 8-bit block: "ttrep" (transformation to representative) - Top 16-bit block: symcoord value After the data as described above, more auxiliary information is appended: - A uint32_t representing the number of symmetry classes @@ -331,7 +331,7 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg) if (arg->selfsim != NULL) arg->selfsim[*arg->n] |= is << t; set_visited(arg->visited, j); - tinv = inverse_trans(t); + tinv = inverse_trans(t) * (1-is); olddepth = (uint8_t)(arg->buf32[j] & 0xFF); cc += olddepth == 0xFF; @@ -425,13 +425,12 @@ gendata_h48h0k4_bfs(bfsarg_esep_t *arg) TODO: the new method gives a slightly different answer. If the new method is correct, then the old bfs method is wrong. Which one is it? Try also DFS and compare results (it could be faster). -/* +*/ if (2 * arg->done < (int64_t)ESEP_MAX(0)) return gendata_h48h0k4_bfs_fromdone(arg); else return gendata_h48h0k4_bfs_fromnew(arg); -*/ - return gendata_h48h0k4_bfs_fromdone(arg); +// return gendata_h48h0k4_bfs_fromnew(arg); } _static int64_t @@ -439,7 +438,8 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) { uint8_t c, m, x; uint32_t cc; - int64_t i, j, k, t, cocsep_coord, sim; + int64_t i, j, k, t, cocsep_coord; + uint64_t sim; cube_t cube, moved, transd; for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { @@ -461,10 +461,29 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) set_esep_pval(arg->buf32, j, arg->depth); cc += x != arg->depth; cocsep_coord = j / H48_ESIZE(0); - sim = arg->selfsim[cocsep_coord] >> 1; - for (t = 1; t < 48 && sim; t++, sim >>= 1) { - if (!(sim & 1)) + sim = arg->selfsim[cocsep_coord] >> UINT64_C(1); + for (t = 1; t < 48 && sim; t++, sim >>= UINT64_C(1)) { + if (!(sim & UINT64_C(1))) { + transd = transform(moved, t); + k = coord_h48(transd, arg->cocsepdata, 0); + if (k != j) { +LOG("t=%" PRId64 ", tinv=%" PRIu8 "\n", t, inverse_trans(t)); +int64_t ccm = coord_cocsep(moved); +int64_t repm = coord_cocsep(arg->crep[j/H48_ESIZE(0)]); +LOG("moved: full %" PRId64 ", cocsep %" PRId64 ", rep %" PRId64 ", ttrep %" PRId32 "\n", j, ccm, repm, TTREP(arg->cocsepdata[ccm])); +int64_t cct = coord_cocsep(transd); +int64_t rept = coord_cocsep(arg->crep[k/H48_ESIZE(0)]); +LOG("moved: full %" PRId64 ", cocsep %" PRId64 ", rep %" PRId64 ", ttrep %" PRId32 "\n", j, cct, rept, TTREP(arg->cocsepdata[cct])); +/* + char q[150]; + writecube_H48(moved, q); + LOG("%s\n", q) + writecube_H48(transd, q); + LOG("%s\n", q) +*/ + } continue; + } transd = transform(moved, t); k = coord_h48(transd, arg->cocsepdata, 0); x = get_esep_pval(arg->buf32, k); @@ -497,7 +516,10 @@ gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) j = coord_h48(moved, arg->cocsepdata, 0); x = get_esep_pval(arg->buf32, j); if (x < arg->depth) +{ +if (x < arg->depth -1) LOG("WAT %" PRIu8 " while scanning %" PRIu8 "\n",x, arg->depth); goto neighbor_found; +} } continue; neighbor_found: diff --git a/test/101_cocsep_selfsim/cocsep_selfsim_tests.c b/test/101_cocsep_selfsim/cocsep_selfsim_tests.c @@ -1,38 +0,0 @@ -/* - * This test is tricky, we only have two cases for now: the solved cube - * and the cube that is one quarter-turn-move off (all such cases are - * equivalent due to symmetry). Adding more tests requires figuring out - * by hand which one is the first position in its class to be reached. - * Note that the .out file need a space before each newline. - */ -#include "../test.h" - -#define COCSEP_CLASSES 3393 - -size_t gendata_cocsep(void *, uint64_t *, cube_t *); -int64_t coord_cocsep(cube_t); - -void run(void) { - char str[STRLENMAX]; - uint32_t buf[300000], data; - int64_t coord, coclass; - uint64_t selfsim[COCSEP_CLASSES], sim, t; - cube_t cube, rep[COCSEP_CLASSES]; - - gendata_cocsep(buf, selfsim, rep); - - /* All cases in the same test so we do not generate data many times */ - - while (fgets(str, STRLENMAX, stdin) != NULL) { - cube = readcube("H48", str); - coord = coord_cocsep(cube); - data = buf[coord]; - coclass = (data & (0xFFFU << 16)) >> 16; - sim = selfsim[coclass]; - for (t = 0; t < 48 && sim; t++, sim >>= 1) { - if (sim & 1) - printf("%" PRId64 " ", t); - } - printf("\n"); - } -} diff --git a/test/101_cocsep_transform_invariant/00_solved.in b/test/101_cocsep_transform_invariant/00_solved.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/101_cocsep_transform_invariant/00_solved.out diff --git a/test/101_cocsep_transform_invariant/01_U.in b/test/101_cocsep_transform_invariant/01_U.in @@ -0,0 +1 @@ +UR0 UL0 DB0 DF0 UB0 UF0 DL0 DR0 FR0 FL0 BL0 BR0 UBR0 UFL0 DFL0 DBR0 UFR0 UBL0 DFR0 DBL0 diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/101_cocsep_transform_invariant/01_U.out diff --git a/test/101_cocsep_transform_invariant/02_scrambled.in b/test/101_cocsep_transform_invariant/02_scrambled.in @@ -0,0 +1 @@ +DL1 BR0 DR0 UR1 DF0 FL1 BL0 UL0 FR0 UF0 DB1 UB0 UFR0 DBL1 DBR0 UFL1 DFR1 DFL1 UBL2 UBR0 diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/101_cocsep_transform_invariant/02_scrambled.out diff --git a/test/101_cocsep_transform_invariant/cocsep_transform_invariant.c b/test/101_cocsep_transform_invariant/cocsep_transform_invariant.c @@ -0,0 +1,33 @@ +#include "../test.h" + +#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16)) +#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16)) + +#define COCSEP_CLASSES 3393 + +size_t gendata_cocsep(void *, uint64_t *, cube_t *); +cube_t transform(cube_t, uint8_t); +int64_t coord_cocsep(cube_t); + +void run(void) { + uint8_t t; + uint32_t buf[300000]; + uint64_t selfsim[COCSEP_CLASSES]; + int64_t coord, tcoord; + char str[STRLENMAX]; + cube_t cube, transd, rep[COCSEP_CLASSES]; + + fgets(str, STRLENMAX, stdin); + cube = readcube("H48", str); + + gendata_cocsep(buf, selfsim, rep); + + coord = (int64_t)COCLASS(buf[coord_cocsep(cube)]); + for (t = 0; t < 48; t++) { + transd = transform(cube, t); + tcoord = (int64_t)COCLASS(buf[coord_cocsep(transd)]); + if (coord != tcoord) + printf("Error: expected %" PRId64 + " but got %" PRId64 "\n", coord, tcoord); + } +} diff --git a/test/101_cocsep_selfsim/00_all.in b/test/102_cocsep_selfsim/00_all.in diff --git a/test/101_cocsep_selfsim/00_all.out b/test/102_cocsep_selfsim/00_all.out diff --git a/test/102_cocsep_selfsim/cocsep_selfsim_tests.c b/test/102_cocsep_selfsim/cocsep_selfsim_tests.c @@ -0,0 +1,38 @@ +/* + * This test is tricky, we only have two cases for now: the solved cube + * and the cube that is one quarter-turn-move off (all such cases are + * equivalent due to symmetry). Adding more tests requires figuring out + * by hand which one is the first position in its class to be reached. + * Note that the .out files need a space before each newline. + */ +#include "../test.h" + +#define COCSEP_CLASSES 3393 + +size_t gendata_cocsep(void *, uint64_t *, cube_t *); +int64_t coord_cocsep(cube_t); + +void run(void) { + char str[STRLENMAX]; + uint32_t buf[300000], data; + int64_t coord, coclass; + uint64_t selfsim[COCSEP_CLASSES], sim, t; + cube_t cube, rep[COCSEP_CLASSES]; + + gendata_cocsep(buf, selfsim, rep); + + /* All cases in the same test so we do not generate data many times */ + + while (fgets(str, STRLENMAX, stdin) != NULL) { + cube = readcube("H48", str); + coord = coord_cocsep(cube); + data = buf[coord]; + coclass = (data & (0xFFFU << 16)) >> 16; + sim = selfsim[coclass]; + for (t = 0; t < 48 && sim; t++, sim >>= 1) { + if (sim & 1) + printf("%" PRId64 " ", t); + } + printf("\n"); + } +} diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/103_cocsep_ttrep/00_all.in diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/103_cocsep_ttrep/00_all.out diff --git a/test/103_cocsep_ttrep/cocsep_ttrep_tests.c b/test/103_cocsep_ttrep/cocsep_ttrep_tests.c @@ -0,0 +1,33 @@ +#include "../test.h" + +#define COCSEP_CLASSES 3393 + +uint8_t inverse_trans(uint8_t); +cube_t transform_corners(cube_t); +int64_t coord_cocsep(cube_t); +size_t gendata_cocsep(void *, uint64_t *, cube_t *); + +void run(void) { + uint8_t t, tinv; + uint32_t buf[300000], tt; + uint64_t selfsim[COCSEP_CLASSES]; + int64_t i, j; + cube_t rep[COCSEP_CLASSES], c, d; + + gendata_cocsep(buf, selfsim, rep); + + for (i = 0; i < COCSEP_CLASSES; i++) { + c = rep[i]; + for (t = 0; t < 48; t++) { + tinv = inverse_trans(t); + d = transform_corners(c); + j = coord_cocsep(d); + tt = (buf[j] & (0xFF << 8)) >> 8; + if (tt != tinv) + printf("cocsep %" PRId64 " <- %" PRId64 ": " + "expected t %" PRIu8 " (inverse of %" + PRIu8 "), got %" PRIu32 "\n", + i, j, tinv, t, tt); + } + } +} diff --git a/test/102_coord_invcoord_h48/00_all.in b/test/110_coord_invcoord_h48/00_all.in diff --git a/test/102_coord_invcoord_h48/00_all.out b/test/110_coord_invcoord_h48/00_all.out diff --git a/test/102_coord_invcoord_h48/coord_invcoord_h48_tests.c b/test/110_coord_invcoord_h48/coord_invcoord_h48_tests.c diff --git a/test/103_gendata_h48_h0/00_h_0.in b/test/111_gendata_h48_h0/00_h_0.in diff --git a/test/103_gendata_h48_h0/00_h_0.out b/test/111_gendata_h48_h0/00_h_0.out diff --git a/test/103_gendata_h48_h0/gendata_h48_tests.c b/test/111_gendata_h48_h0/gendata_h48_tests.c diff --git a/test/104_h48set/00_small.in b/test/112_h48set/00_small.in diff --git a/test/104_h48set/00_small.out b/test/112_h48set/00_small.out diff --git a/test/104_h48set/01_large.in b/test/112_h48set/01_large.in diff --git a/test/104_h48set/01_large.out b/test/112_h48set/01_large.out diff --git a/test/104_h48set/h48set_tests.c b/test/112_h48set/h48set_tests.c