commit 7946c8efc2e2a44a8e78e1263c1691ce9f412a09
parent 3d060c348fdfff074a9b902d56f539664789d831
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu, 18 Jul 2024 11:09:50 +0200
Converted set to map
Diffstat:
13 files changed, 638 insertions(+), 379 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,14 +1,38 @@
Bug in esep table generation
- - Re-do stats
+ - 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?)
- - try DFS for h0 solver
- - use dfs for computing big table, save distance %3 until the last two steps,
- then clean the table and double loop over moves to fill the value
- - dfs for tables with h=1 to 10?
-
+ - compute all tables for h<11
+ - compute visited up to a fixed depth (7? 8?)
+ - compute additional step (if needed) to fill <=base
+ - brute-force the last 2 steps (only 18 moves + 18*15 move pairs)
+ - 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?
+ - optimize
+ - use cached values for invcoord_esep? check if it is faster
+
+(OLD:
- Fails for UFRUFU, try command
./run solve -solver H48 -options "2;20" -n 1 -M 10 -cube \
"$(./run frommoves -moves "UFRUFU")"
+)
+
+table base for k=2 (4 most common values start at)
+ 0 8
+ 1 8
+ 2 8
+ 3 8 or 9 (very close)
+ 4 9
+ 5 9
+ 6 9
+ 7 9 or 10 (very close)
+ 8 10
+ 9 10
+ 10 10
+ 11 11
Solver
- cleanup h48 solver
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -1,3 +1,7 @@
+#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF)
+#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF)
+#define MAP_KEYSHIFT UINT64_C(40)
+
#define COCSEP_CLASSES ((size_t)3393)
#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7)
#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8)
@@ -24,11 +28,16 @@
#define MAX_SOLUTION_LENGTH 20
typedef struct {
- int64_t n;
- int64_t capacity;
- int64_t mod;
- int64_t *table;
-} h48set_t;
+ uint64_t n;
+ uint64_t capacity;
+ uint64_t mod;
+ uint64_t *table;
+} h48map_t;
+
+typedef struct {
+ uint64_t key;
+ uint64_t val;
+} kvpair_t;
typedef struct {
cube_t cube;
@@ -41,6 +50,16 @@ typedef struct {
cube_t *rep;
} dfsarg_cocsep_t;
+/* TODO keep or not? */
+typedef struct {
+ cube_t cube;
+ int8_t nmoves;
+ int8_t depth;
+ uint8_t moves[MAX_SOLUTION_LENGTH];
+ uint32_t *cocsepdata;
+ h48map_t *visited;
+} dfsarg_genh48set_t;
+
typedef struct {
uint8_t depth;
uint32_t *cocsepdata;
@@ -74,30 +93,31 @@ typedef struct {
char *s;
} dfsarg_solveh48stats_t;
-_static void h48set_create(h48set_t *, int64_t, int64_t);
-_static void h48set_clear(h48set_t *);
-_static void h48set_destroy(h48set_t *);
-_static_inline int64_t h48set_lookup(h48set_t *, int64_t);
-_static_inline void h48set_insert(h48set_t *, int64_t);
-_static_inline bool h48set_contains(h48set_t *, int64_t);
-_static inline int64_t h48set_save(h48set_t *, int64_t *);
+_static void h48map_create(h48map_t *, uint64_t, uint64_t);
+_static void h48map_clear(h48map_t *);
+_static void h48map_destroy(h48map_t *);
+_static uint64_t h48map_lookup(h48map_t *, uint64_t);
+_static void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
+_static uint64_t h48map_value(h48map_t *, uint64_t);
+_static kvpair_t h48map_nextkvpair(h48map_t *, uint64_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);
+_static_inline bool get_visited(const uint8_t *, int64_t);
+_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 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 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 *);
_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
-_static_inline bool get_visited(const uint8_t *, int64_t);
-_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 *);
@@ -109,78 +129,84 @@ _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
-h48set_create(h48set_t *set, int64_t capacity, int64_t mod)
+h48map_create(h48map_t *map, uint64_t capacity, uint64_t mod)
{
- set->capacity = capacity;
- set->mod = mod;
+ map->capacity = capacity;
+ map->mod = mod;
- set->table = malloc(set->capacity * sizeof(int64_t));
- h48set_clear(set);
+ map->table = malloc(map->capacity * sizeof(int64_t));
+ h48map_clear(map);
}
_static void
-h48set_clear(h48set_t *set)
+h48map_clear(h48map_t *map)
{
- int64_t i;
-
- for (i = 0; i < set->capacity; i++)
- set->table[i] = -1;
-
- set->n = 0;
+ memset(map->table, 0xFF, map->capacity * sizeof(uint64_t));
+ map->n = 0;
}
_static void
-h48set_destroy(h48set_t *set)
+h48map_destroy(h48map_t *map)
{
- free(set->table);
+ free(map->table);
}
-/* Returns the index in where x should be inserted, or -1 if x is in the set */
-_static_inline int64_t
-h48set_lookup(h48set_t *set, int64_t x)
+_static_inline uint64_t
+h48map_lookup(h48map_t *map, uint64_t x)
{
- int64_t hash, i;
+ uint64_t hash, i;
- hash = ((x % set->capacity) * set->mod) % set->capacity;
- for (i = hash; set->table[i] != -1; i = (i+1) % set->capacity)
- if (set->table[i] == x)
- return -1;
+ hash = ((x % map->capacity) * map->mod) % map->capacity;
+ for (i = hash;
+ map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
+ i = (i+1) % map->capacity
+ ) ;
return i;
}
_static_inline void
-h48set_insert(h48set_t *set, int64_t x)
+h48map_insertmin(h48map_t *map, uint64_t key, uint64_t val)
{
- int64_t i;
+ uint64_t i, oldval, min;
- i = h48set_lookup(set, x);
- if (i != -1) {
- set->table[i] = x;
- set->n++;
- }
+ i = h48map_lookup(map, key);
+ oldval = map->table[i] >> MAP_KEYSHIFT;
+ min = _min(val, oldval);
+
+ map->n += map->table[i] == MAP_UNSET;
+ map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT);
}
-_static_inline bool
-h48set_contains(h48set_t *set, int64_t x)
+_static_inline uint64_t
+h48map_value(h48map_t *map, uint64_t key)
{
- int64_t i;
-
- i = h48set_lookup(set, x);
-
- return i == -1;
+ return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT;
}
-_static int64_t
-h48set_save(h48set_t *set, int64_t *a)
+_static kvpair_t
+h48map_nextkvpair(h48map_t *map, uint64_t *p)
{
- int64_t i, j;
-
- for (i = 0, j = 0; i < set->capacity; i++)
- if (set->table[i] != -1)
- a[j++] = set->table[i];
+ kvpair_t kv;
+ uint64_t pair;
+
+ kv.key = MAP_UNSET;
+ kv.val = MAP_UNSET;
+
+ DBG_ASSERT(*p < map->capacity, kv,
+ "Error looping over map: given index %" PRIu64 " is out of "
+ "range [0,%" PRIu64 "]", *p, map->capacity);
+
+ for ( ; *p < map->capacity; (*p)++) {
+ if (map->table[*p] != MAP_UNSET) {
+ pair = map->table[(*p)++];
+ kv.key = pair & MAP_KEYMASK;
+ kv.val = pair >> MAP_KEYSHIFT;
+ return kv;
+ }
+ }
- return j;
+ return kv;
}
_static_inline int64_t
@@ -358,6 +384,34 @@ 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;
+
+ cube = solvedcube();
+ coord = coord_h48(cube, cocsepdata, 11);
+ for (i = 0; i < n; i++) {
+ for (j = 0; (coord = h48map_next(map, &j)) != -1; ) {
+ cube = invcoord_h48(coord, cocsepdata, 11);
+ for (m = 0; m < 18; m++) {
+ d = move(cube, m);
+TODO
+ }
+ }
+ }
+*/
+}
+
+_static int64_t
+gen_h48set_short_dfs(dfsarg_genh48set_t *arg)
+{
+ /* TODO */
+}
+
/*
TODO description
generating fixed table with h=0, k=4
@@ -756,9 +810,9 @@ solve_h48stats(
for (i = 0; i < 12; i++)
solutions[i] = (char)99;
- for (arg.depth = 0;
- arg.depth <= maxmoves && solutions[11] == 99;
- arg.depth++)
+ for (arg.depth = 0;
+ arg.depth <= maxmoves && solutions[11] == 99;
+ arg.depth++)
{
arg.nmoves = 0;
solve_h48stats_dfs(&arg);
diff --git a/src/utils.h b/src/utils.h
@@ -1,4 +1,6 @@
#define _swap(x, y) do { x ^= y; y ^= x; x ^= y; } while (0)
+#define _min(x, y) ((x) < (y) ? (x) : (y))
+#define _max(x, y) ((x) > (y) ? (x) : (y))
_static int64_t factorial(int64_t);
_static bool isperm(uint8_t *, int64_t);
diff --git a/test/112_h48map/00_small.in b/test/112_h48map/00_small.in
@@ -0,0 +1,11 @@
+11
+7
+4
+34
+12
+45
+7
+34
+13
+45
+5
diff --git a/test/112_h48map/00_small.out b/test/112_h48map/00_small.out
@@ -0,0 +1,3 @@
+2
+34 12
+45 5
diff --git a/test/112_h48map/01_large.in b/test/112_h48map/01_large.in
@@ -0,0 +1,303 @@
+307
+293
+150
+100053
+417
+100045
+164
+100007
+235
+100007
+207
+100011
+406
+100072
+29
+100033
+188
+100015
+358
+100013
+248
+100068
+218
+100047
+398
+100046
+263
+100000
+471
+100076
+219
+100021
+115
+100019
+329
+100015
+178
+100049
+59
+100052
+319
+100071
+232
+100058
+174
+100009
+46
+100060
+349
+100030
+287
+100051
+203
+100069
+359
+100011
+296
+100051
+223
+100014
+233
+100031
+264
+100017
+180
+100076
+22
+100016
+213
+100030
+55
+100037
+3
+100011
+467
+100002
+165
+100029
+161
+100022
+67
+100038
+374
+100075
+4
+100066
+156
+100051
+144
+100020
+480
+100039
+265
+100029
+195
+100087
+245
+100099
+287
+100041
+308
+100042
+32
+100026
+312
+100060
+434
+100006
+392
+100010
+269
+100079
+414
+100046
+161
+100086
+139
+100010
+88
+100036
+117
+100047
+376
+100069
+17
+100041
+314
+100074
+320
+100090
+225
+100092
+424
+100020
+325
+100096
+318
+100046
+238
+100028
+13
+100072
+73
+100096
+262
+100025
+82
+100001
+107
+100067
+410
+100044
+449
+100063
+276
+100026
+392
+100062
+407
+100091
+411
+100012
+400
+100073
+331
+100051
+83
+100010
+385
+100096
+484
+100043
+352
+100025
+207
+100077
+272
+100089
+192
+100005
+291
+100024
+243
+100091
+445
+100046
+162
+100053
+380
+100058
+157
+100065
+464
+100051
+306
+100056
+236
+100025
+198
+100093
+230
+100088
+494
+100033
+70
+100073
+218
+100048
+486
+100059
+77
+100027
+142
+100045
+418
+100012
+68
+100059
+448
+100084
+339
+100017
+39
+100048
+83
+100004
+321
+100051
+441
+100016
+308
+100088
+334
+100033
+476
+100064
+51
+100060
+324
+100043
+149
+100084
+116
+100026
+351
+100051
+396
+100060
+377
+100069
+301
+100015
+319
+100014
+466
+100038
+194
+100068
+41
+100038
+295
+100097
+394
+100017
+34
+100013
+223
+100053
+339
+100019
+67
+100018
+24
+100081
+205
+100071
+440
+100025
+228
+100014
+169
+100016
+121
+100011
+444
+100069
+460
+100079
+139
+100063
+169
+100070
+132
+100072
+119
+100095
+126
+100042
+217
+100008
+272
+100022
+121
diff --git a/test/112_h48map/01_large.out b/test/112_h48map/01_large.out
@@ -0,0 +1,83 @@
+82
+100000 471
+100001 107
+100002 165
+100004 321
+100005 291
+100006 392
+100007 207
+100008 272
+100009 46
+100010 88
+100011 296
+100012 68
+100013 223
+100014 169
+100015 178
+100016 121
+100017 34
+100018 24
+100019 67
+100020 325
+100021 115
+100022 67
+100024 243
+100025 82
+100026 312
+100027 142
+100028 13
+100029 161
+100030 55
+100031 264
+100033 70
+100036 117
+100037 3
+100038 194
+100039 265
+100041 308
+100042 32
+100043 149
+100044 449
+100045 164
+100046 161
+100047 376
+100048 83
+100049 59
+100051 83
+100052 319
+100053 339
+100056 236
+100058 157
+100059 77
+100060 324
+100062 407
+100063 169
+100064 51
+100065 464
+100066 156
+100067 410
+100068 41
+100069 17
+100070 132
+100071 232
+100072 29
+100073 218
+100074 320
+100075 4
+100076 22
+100077 272
+100079 139
+100081 205
+100084 116
+100086 139
+100087 245
+100088 334
+100089 192
+100090 225
+100091 411
+100092 424
+100093 230
+100095 126
+100096 262
+100097 394
+100099 287
diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c
@@ -0,0 +1,88 @@
+#include "../test.h"
+
+#define MAP_KEYSHIFT UINT64_C(40)
+
+typedef struct {
+ uint64_t n;
+ uint64_t capacity;
+ uint64_t mod;
+ 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_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 *);
+
+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) {
+ h48map_t map;
+ uint64_t n, i, j, capacity, mod, x, y, v;
+ kvpair_t kv, *a, *b;
+
+ capacity = readl();
+ mod = 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);
+ 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;
+ 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);
+ if (map.n != j)
+ printf("Wrong number of elements: map->n = %" PRIu64 ", "
+ "but scan returns %" PRIu64 "\n", map.n, j);
+ for (i = 0; i < n; i++) {
+ v = h48map_value(&map, a[i].key);
+ if (v > a[i].val)
+ printf("Value for key %" PRId64 " is larger than "
+ "expected (%" PRIu64 " > %" PRIu64 ")\n",
+ a[i].key, v, a[i].val);
+ }
+
+ h48map_destroy(&map);
+ free(a);
+ free(b);
+}
diff --git a/test/112_h48set/00_small.in b/test/112_h48set/00_small.in
@@ -1,6 +0,0 @@
-11
-7
-3
-34
-45
-34
diff --git a/test/112_h48set/00_small.out b/test/112_h48set/00_small.out
@@ -1,3 +0,0 @@
-2
-34
-45
diff --git a/test/112_h48set/01_large.in b/test/112_h48set/01_large.in
@@ -1,153 +0,0 @@
-307
-293
-150
-100053
-100045
-100007
-100007
-100011
-100072
-100033
-100015
-100013
-100068
-100047
-100046
-100000
-100076
-100021
-100019
-100015
-100049
-100052
-100071
-100058
-100009
-100060
-100030
-100051
-100069
-100011
-100051
-100014
-100031
-100017
-100076
-100016
-100030
-100037
-100011
-100002
-100029
-100022
-100038
-100075
-100066
-100051
-100020
-100039
-100029
-100087
-100099
-100041
-100042
-100026
-100060
-100006
-100010
-100079
-100046
-100086
-100010
-100036
-100047
-100069
-100041
-100074
-100090
-100092
-100020
-100096
-100046
-100028
-100072
-100096
-100025
-100001
-100067
-100044
-100063
-100026
-100062
-100091
-100012
-100073
-100051
-100010
-100096
-100043
-100025
-100077
-100089
-100005
-100024
-100091
-100046
-100053
-100058
-100065
-100051
-100056
-100025
-100093
-100088
-100033
-100073
-100048
-100059
-100027
-100045
-100012
-100059
-100084
-100017
-100048
-100004
-100051
-100016
-100088
-100033
-100064
-100060
-100043
-100084
-100026
-100051
-100060
-100069
-100015
-100014
-100038
-100068
-100038
-100097
-100017
-100013
-100053
-100019
-100018
-100081
-100071
-100025
-100014
-100016
-100011
-100069
-100079
-100063
-100070
-100072
-100095
-100042
-100008
-100022
diff --git a/test/112_h48set/01_large.out b/test/112_h48set/01_large.out
@@ -1,83 +0,0 @@
-82
-100000
-100001
-100002
-100004
-100005
-100006
-100007
-100008
-100009
-100010
-100011
-100012
-100013
-100014
-100015
-100016
-100017
-100018
-100019
-100020
-100021
-100022
-100024
-100025
-100026
-100027
-100028
-100029
-100030
-100031
-100033
-100036
-100037
-100038
-100039
-100041
-100042
-100043
-100044
-100045
-100046
-100047
-100048
-100049
-100051
-100052
-100053
-100056
-100058
-100059
-100060
-100062
-100063
-100064
-100065
-100066
-100067
-100068
-100069
-100070
-100071
-100072
-100073
-100074
-100075
-100076
-100077
-100079
-100081
-100084
-100086
-100087
-100088
-100089
-100090
-100091
-100092
-100093
-100095
-100096
-100097
-100099
diff --git a/test/112_h48set/h48set_tests.c b/test/112_h48set/h48set_tests.c
@@ -1,64 +0,0 @@
-#include "../test.h"
-
-char str[STRLENMAX];
-
-typedef struct {
- int64_t n;
- int64_t capacity;
- int64_t mod;
- int64_t *table;
-} h48set_t;
-
-void h48set_create(h48set_t *, int64_t, int64_t);
-void h48set_clear(h48set_t *);
-void h48set_destroy(h48set_t *);
-int64_t h48set_lookup(h48set_t *, int64_t);
-void h48set_insert(h48set_t *, int64_t);
-bool h48set_contains(h48set_t *, int64_t);
-int64_t h48set_save(h48set_t *, int64_t *);
-
-int compare(const void *x, const void *y) {
- int64_t a = *(int64_t *)x;
- int64_t b = *(int64_t *)y;
-
- if (a > b) return 1;
- if (a == b) return 0;
- return -1;
-}
-
-int64_t readl(void) {
- fgets(str, STRLENMAX, stdin);
- return atoll(str);
-}
-
-void run(void) {
- h48set_t set;
- int64_t n, i, k, capacity, mod, *a, *b;
-
- capacity = readl();
- mod = readl();
- n = readl();
-
- a = malloc(n * sizeof(int64_t));
- b = malloc(n * sizeof(int64_t));
- for (i = 0; i < n; i++)
- a[i] = readl();
-
- h48set_create(&set, capacity, mod);
- for (i = 0; i < n; i++)
- h48set_insert(&set, a[i]);
-
- k = h48set_save(&set, b);
- qsort(b, k, sizeof(int64_t), compare);
-
- printf("%" PRId64 "\n", k);
- for (i = 0; i < k; i++)
- printf("%" PRId64 "\n", b[i]);
- for (i = 0; i < n; i++)
- if (!h48set_contains(&set, a[i]))
- printf("Set does not contain %" PRId64 "\n", a[i]);
-
- h48set_destroy(&set);
- free(a);
- free(b);
-}
