commit e20e4f550ae373414d9bc106b1615a5c5896c9c4
parent 7946c8efc2e2a44a8e78e1263c1691ce9f412a09
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu, 18 Jul 2024 19:39:44 +0200
Added pre-computation of short h48 positions
Diffstat:
9 files changed, 210 insertions(+), 45 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,18 +1,19 @@
Bug in esep table generation
- - add pre-computation of h48 coordinates at distance <=7?
- - unit tests (but how do I test? just leave it there to check regressions)
- - Add long-running test for h0k4 (maybe as a tool?)
- compute all tables for h<11
- - compute visited up to a fixed depth (7? 8?)
+ x compute visited up to a fixed depth 8
- compute additional step (if needed) to fill <=base
- - brute-force the last 2 steps (only 18 moves + 18*15 move pairs)
+ - brute-force the last 2 steps (only 18 moves + 18*15 move pairs, + sim)
- compare with known h0 results (from long-running test)
- compute table for h=11
- - is is worth pre-computing stuff?
- can it be unified to the other computation, or is it much better
to do it ad hoc?
+ - Add long-running test for h0k4 (maybe as a tool?)
+ - tests for other sizes?
- optimize
- use cached values for invcoord_esep? check if it is faster
+ - Unify and improve performance of finding nasty sim
+ (right now we don't even use selfsim)
+ - parallelize with pthread
(OLD:
- Fails for UFRUFU, try command
diff --git a/src/cube_transform_with_switch.h b/src/cube_transform_with_switch.h
@@ -118,7 +118,7 @@ transform_edges(cube_t c, uint8_t t)
case _trans_BLm:
return _trans_edges_mirrored(BLm, c);
default:
- LOG("transform error, unknown transformation\n");
+ LOG("transform error, unknown transformation %" PRIu8 "\n", t);
return zero;
}
}
@@ -224,7 +224,7 @@ transform_corners(cube_t c, uint8_t t)
case _trans_BLm:
return _trans_corners_mirrored(BLm, c);
default:
- LOG("transform error, unknown transformation\n");
+ LOG("transform error, unknown transformation %" PRIu8 "\n", t);
return zero;
}
}
@@ -330,7 +330,7 @@ transform(cube_t c, uint8_t t)
case _trans_BLm:
return _trans_mirrored(BLm, c);
default:
- LOG("transform error, unknown transformation\n");
+ LOG("transform error, unknown transformation %" PRIu8 "\n", t);
return zero;
}
}
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -30,7 +30,7 @@
typedef struct {
uint64_t n;
uint64_t capacity;
- uint64_t mod;
+ uint64_t randomizer;
uint64_t *table;
} h48map_t;
@@ -112,7 +112,8 @@ _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
_static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
-_static int64_t gen_h48map_short(uint8_t, const uint32_t *, h48map_t *);
+_static uint64_t gen_h48short(
+ uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *);
_static size_t gendata_h48h0k4(void *, uint8_t);
_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
@@ -123,16 +124,17 @@ _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 int64_t solve_h48(
+ cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
_static void
-h48map_create(h48map_t *map, uint64_t capacity, uint64_t mod)
+h48map_create(h48map_t *map, uint64_t capacity, uint64_t randomizer)
{
map->capacity = capacity;
- map->mod = mod;
+ map->randomizer = randomizer;
map->table = malloc(map->capacity * sizeof(int64_t));
h48map_clear(map);
@@ -156,7 +158,7 @@ h48map_lookup(h48map_t *map, uint64_t x)
{
uint64_t hash, i;
- hash = ((x % map->capacity) * map->mod) % map->capacity;
+ hash = ((x % map->capacity) * map->randomizer) % map->capacity;
for (i = hash;
map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
i = (i+1) % map->capacity
@@ -384,32 +386,55 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
return cc;
}
-_static int64_t
-gen_h48map_short(uint8_t n, const uint32_t *cocsepdata, h48map_t *map)
-{
-/*
- uint8_t i, j, m;
- int64_t coord;
- cube_t cube, d;
+_static uint64_t
+gen_h48short(
+ uint8_t n,
+ const uint32_t *cocsepdata,
+ const cube_t *crep,
+ const uint64_t *selfsim,
+ h48map_t *map
+) {
+ uint8_t i, m, t;
+ int64_t coord, cc;
+ uint64_t j, oldn, sim;
+ kvpair_t kv;
+ cube_t cube, d, e;
cube = solvedcube();
coord = coord_h48(cube, cocsepdata, 11);
+ h48map_insertmin(map, coord, 0);
+ oldn = 0;
+ LOG("Short h48: generating depth 0\nfound %" PRIu8 "\n", map->n-oldn);
for (i = 0; i < n; i++) {
- for (j = 0; (coord = h48map_next(map, &j)) != -1; ) {
- cube = invcoord_h48(coord, cocsepdata, 11);
+ LOG("Short h48: generating depth %" PRIu8 "\n", i+1);
+ j = 0;
+ oldn = map->n;
+ for (kv = h48map_nextkvpair(map, &j);
+ j != map->capacity;
+ kv = h48map_nextkvpair(map, &j)
+ ) {
+ if (kv.val != i)
+ continue;
+ cube = invcoord_h48(kv.key, crep, 11);
for (m = 0; m < 18; m++) {
d = move(cube, m);
-TODO
+ coord = coord_h48(d, cocsepdata, 11);
+ h48map_insertmin(map, coord, i+1);
+ cc = coord / H48_ESIZE(11);
+ sim = selfsim[cc] >> UINT64_C(1);
+ for (t = 1; t < 48 && sim; t++) {
+ /* TODO: optimize by using transform_edges,
+ corner coordinate is kept */
+ e = transform(d, t);
+ coord = coord_h48(e, cocsepdata, 11);
+ h48map_insertmin(map, coord, i+1);
+ }
}
}
+ LOG("found %" PRIu8 "\n", map->n-oldn);
}
-*/
-}
-_static int64_t
-gen_h48set_short_dfs(dfsarg_genh48set_t *arg)
-{
- /* TODO */
+ return map->n;
}
/*
@@ -511,7 +536,7 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
cc += x != arg->depth;
cocsep_coord = j / H48_ESIZE(0);
sim = arg->selfsim[cocsep_coord] >> UINT64_C(1);
- for (t = 1; t < 48 && sim; t++, sim >>= UINT64_C(1)) {
+ for (t = 1; t < 48 && sim; t++) {
/* TODO: use only selfsim */
transd = transform(moved, t);
k = coord_h48(transd, arg->cocsepdata, 0);
@@ -553,7 +578,7 @@ neighbor_found:
cc++;
cocsep_coord = i / H48_ESIZE(0);
sim = arg->selfsim[cocsep_coord] >> 1;
- for (t = 1; t < 48 && sim; t++, sim >>= 1) {
+ for (t = 1; t < 48 && sim; t++) {
/* TODO: use only selfsim */
transd = transform(cube, t);
j = coord_h48(transd, arg->cocsepdata, 0);
diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c
@@ -1,11 +1,12 @@
#include "../test.h"
#define MAP_KEYSHIFT UINT64_C(40)
+#define MAXPOS 1000
typedef struct {
uint64_t n;
uint64_t capacity;
- uint64_t mod;
+ uint64_t randomizer;
uint64_t *table;
} h48map_t;
@@ -15,9 +16,7 @@ typedef struct {
} kvpair_t;
void h48map_create(h48map_t *, uint64_t, uint64_t);
-void h48map_clear(h48map_t *);
void h48map_destroy(h48map_t *);
-uint64_t h48map_lookup(h48map_t *, uint64_t);
void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
uint64_t h48map_value(h48map_t *, uint64_t);
kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
@@ -40,28 +39,26 @@ uint64_t readl(void) {
void run(void) {
h48map_t map;
- uint64_t n, i, j, capacity, mod, x, y, v;
- kvpair_t kv, *a, *b;
+ uint64_t n, i, j, capacity, randomizer, x, y, v;
+ kvpair_t kv, a[MAXPOS], b[MAXPOS];
capacity = readl();
- mod = readl();
+ randomizer = readl();
n = readl();
- a = malloc(n * sizeof(kvpair_t));
- b = malloc(n * sizeof(kvpair_t));
for (i = 0; i < n; i++) {
x = readl();
y = readl();
a[i] = (kvpair_t) { .key = x, .val = y };
}
- h48map_create(&map, capacity, mod);
+ h48map_create(&map, capacity, randomizer);
for (i = 0; i < n; i++)
h48map_insertmin(&map, a[i].key, a[i].val);
i = 0;
for (kv = h48map_nextkvpair(&map, &i), j = 0;
- i != map.capacity;
+ i != map.capacity && j < MAXPOS;
kv = h48map_nextkvpair(&map, &i)
) {
b[j++] = kv;
@@ -83,6 +80,4 @@ void run(void) {
}
h48map_destroy(&map);
- free(a);
- free(b);
}
diff --git a/test/113_gen_h48short/00_depth_1.in b/test/113_gen_h48short/00_depth_1.in
@@ -0,0 +1,28 @@
+73
+157
+1
+
+For longer test:
+
+20000003
+20000023
+8
+
+Short h48: generating depth 0
+found 1
+Short h48: generating depth 1
+found 1
+Short h48: generating depth 2
+found 4
+Short h48: generating depth 3
+found 34
+Short h48: generating depth 4
+found 333
+Short h48: generating depth 5
+found 3815
+Short h48: generating depth 6
+found 45382
+Short h48: generating depth 7
+found 548562
+Short h48: generating depth 8
+found 6839723
diff --git a/test/113_gen_h48short/00_depth_1.out b/test/113_gen_h48short/00_depth_1.out
@@ -0,0 +1,3 @@
+2
+0 0
+71075840 1
diff --git a/test/113_gen_h48short/01_depth_3.in b/test/113_gen_h48short/01_depth_3.in
@@ -0,0 +1,3 @@
+73
+157
+3
diff --git a/test/113_gen_h48short/01_depth_3.out b/test/113_gen_h48short/01_depth_3.out
@@ -0,0 +1,40 @@
+40
+0 0
+70981632 3
+71075840 1
+71086080 3
+142067712 2
+218789888 3
+218884096 2
+283879424 2
+283899904 3
+283953152 3
+283973632 2
+360548808 3
+360835072 3
+473668032 3
+473956352 3
+499869696 3
+500011008 3
+598679552 3
+599109185 3
+662171648 3
+662601226 3
+724818316 3
+725106688 3
+790513664 3
+790607872 3
+904991108 3
+926726144 3
+928729088 3
+1009662340 3
+1088755203 3
+1171758595 3
+1206452224 3
+1206480896 3
+1277360128 3
+1277454336 3
+1403695492 3
+1403697540 3
+1403736452 3
+1403738500 3
diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c
@@ -0,0 +1,70 @@
+#include "../test.h"
+
+#define COCSEP_CLASSES 3393
+#define MAXPOS 200
+
+typedef struct {
+ uint64_t n;
+ uint64_t capacity;
+ uint64_t randomizer;
+ uint64_t *table;
+} h48map_t;
+
+typedef struct {
+ uint64_t key;
+ uint64_t val;
+} kvpair_t;
+
+void h48map_create(h48map_t *, uint64_t, uint64_t);
+void h48map_destroy(h48map_t *);
+kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
+size_t gendata_cocsep(void *, uint64_t *, cube_t *);
+uint64_t gen_h48short(
+ uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *);
+
+char str[STRLENMAX];
+
+int compare(const void *x, const void *y) {
+ uint64_t a = ((kvpair_t *)x)->key;
+ uint64_t b = ((kvpair_t *)y)->key;
+
+ if (a > b) return 1;
+ if (a == b) return 0;
+ return -1;
+}
+
+uint64_t readl(void) {
+ fgets(str, STRLENMAX, stdin);
+ return atoll(str);
+}
+
+void run(void) {
+ uint32_t cocsepdata[300000];
+ h48map_t map;
+ uint64_t n, i, j, capacity, randomizer, selfsim[COCSEP_CLASSES];
+ kvpair_t kv, b[MAXPOS];
+ cube_t crep[COCSEP_CLASSES];
+
+ capacity = readl();
+ randomizer = readl();
+ n = readl();
+
+ h48map_create(&map, capacity, randomizer);
+ gendata_cocsep(cocsepdata, selfsim, crep);
+ gen_h48short(n, cocsepdata, crep, selfsim, &map);
+
+ i = 0;
+ for (kv = h48map_nextkvpair(&map, &i), j = 0;
+ i != map.capacity && j < MAXPOS;
+ kv = h48map_nextkvpair(&map, &i)
+ ) {
+ b[j++] = kv;
+ }
+ qsort(b, j, sizeof(kvpair_t), compare);
+
+ printf("%" PRIu64 "\n", map.n);
+ for (i = 0; i < j; i++)
+ printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val);
+
+ h48map_destroy(&map);
+}
