aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/solve_h48.h77
-rw-r--r--test/104_h48set/00_small.in6
-rw-r--r--test/104_h48set/00_small.out3
-rw-r--r--test/104_h48set/01_large.in153
-rw-r--r--test/104_h48set/01_large.out83
-rw-r--r--test/104_h48set/h48set_tests.c69
6 files changed, 391 insertions, 0 deletions
diff --git a/src/solve_h48.h b/src/solve_h48.h
index 5f99d15..4bf9f78 100644
--- a/src/solve_h48.h
+++ b/src/solve_h48.h
@@ -24,6 +24,13 @@
24#define MAX_SOLUTION_LENGTH 20 24#define MAX_SOLUTION_LENGTH 20
25 25
26typedef struct { 26typedef struct {
27 int64_t n;
28 int64_t capacity;
29 int64_t mod;
30 int64_t *table;
31} h48set_t;
32
33typedef struct {
27 cube_t cube; 34 cube_t cube;
28 uint8_t depth; 35 uint8_t depth;
29 uint8_t maxdepth; 36 uint8_t maxdepth;
@@ -66,6 +73,13 @@ typedef struct {
66 char *s; 73 char *s;
67} dfsarg_solveh48stats_t; 74} dfsarg_solveh48stats_t;
68 75
76_static void h48set_create(h48set_t *, int64_t, int64_t);
77_static void h48set_clear(h48set_t *);
78_static void h48set_destroy(h48set_t *);
79_static_inline int64_t h48set_lookup(h48set_t *, int64_t);
80_static_inline void h48set_insert(h48set_t *, int64_t);
81_static_inline bool h48set_contains(h48set_t *, int64_t);
82
69_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t); 83_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
70_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t); 84_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
71_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t); 85_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
@@ -90,6 +104,69 @@ _static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_t, const void *,
90_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); 104_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
91_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); 105_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
92 106
107_static void
108h48set_create(h48set_t *set, int64_t capacity, int64_t mod)
109{
110 set->capacity = capacity;
111 set->mod = mod;
112
113 set->table = malloc(set->capacity * sizeof(int64_t));
114 h48set_clear(set);
115}
116
117_static void
118h48set_clear(h48set_t *set)
119{
120 int64_t i;
121
122 for (i = 0; i < set->capacity; i++)
123 set->table[i] = -1;
124
125 set->n = 0;
126}
127
128_static void
129h48set_destroy(h48set_t *set)
130{
131 free(set->table);
132}
133
134/* Returns the index in where x should be inserted, or -1 if x is in the set */
135_static_inline int64_t
136h48set_lookup(h48set_t *set, int64_t x)
137{
138 int64_t hash, i;
139
140 hash = ((x % set->capacity) * set->mod) % set->capacity;
141 for (i = hash; set->table[i] != -1; i = (i+1) % set->capacity)
142 if (set->table[i] == x)
143 return -1;
144
145 return i;
146}
147
148_static_inline void
149h48set_insert(h48set_t *set, int64_t x)
150{
151 int64_t i;
152
153 i = h48set_lookup(set, x);
154 if (i != -1) {
155 set->table[i] = x;
156 set->n++;
157 }
158}
159
160_static_inline bool
161h48set_contains(h48set_t *set, int64_t x)
162{
163 int64_t i;
164
165 i = h48set_lookup(set, x);
166
167 return i == -1;
168}
169
93_static_inline int64_t 170_static_inline int64_t
94coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h) 171coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
95{ 172{
diff --git a/test/104_h48set/00_small.in b/test/104_h48set/00_small.in
new file mode 100644
index 0000000..d788d5b
--- /dev/null
+++ b/test/104_h48set/00_small.in
@@ -0,0 +1,6 @@
111
27
33
434
545
634
diff --git a/test/104_h48set/00_small.out b/test/104_h48set/00_small.out
new file mode 100644
index 0000000..29c08e5
--- /dev/null
+++ b/test/104_h48set/00_small.out
@@ -0,0 +1,3 @@
12
234
345
diff --git a/test/104_h48set/01_large.in b/test/104_h48set/01_large.in
new file mode 100644
index 0000000..a70ef9a
--- /dev/null
+++ b/test/104_h48set/01_large.in
@@ -0,0 +1,153 @@
1307
2293
3150
4100053
5100045
6100007
7100007
8100011
9100072
10100033
11100015
12100013
13100068
14100047
15100046
16100000
17100076
18100021
19100019
20100015
21100049
22100052
23100071
24100058
25100009
26100060
27100030
28100051
29100069
30100011
31100051
32100014
33100031
34100017
35100076
36100016
37100030
38100037
39100011
40100002
41100029
42100022
43100038
44100075
45100066
46100051
47100020
48100039
49100029
50100087
51100099
52100041
53100042
54100026
55100060
56100006
57100010
58100079
59100046
60100086
61100010
62100036
63100047
64100069
65100041
66100074
67100090
68100092
69100020
70100096
71100046
72100028
73100072
74100096
75100025
76100001
77100067
78100044
79100063
80100026
81100062
82100091
83100012
84100073
85100051
86100010
87100096
88100043
89100025
90100077
91100089
92100005
93100024
94100091
95100046
96100053
97100058
98100065
99100051
100100056
101100025
102100093
103100088
104100033
105100073
106100048
107100059
108100027
109100045
110100012
111100059
112100084
113100017
114100048
115100004
116100051
117100016
118100088
119100033
120100064
121100060
122100043
123100084
124100026
125100051
126100060
127100069
128100015
129100014
130100038
131100068
132100038
133100097
134100017
135100013
136100053
137100019
138100018
139100081
140100071
141100025
142100014
143100016
144100011
145100069
146100079
147100063
148100070
149100072
150100095
151100042
152100008
153100022
diff --git a/test/104_h48set/01_large.out b/test/104_h48set/01_large.out
new file mode 100644
index 0000000..6632336
--- /dev/null
+++ b/test/104_h48set/01_large.out
@@ -0,0 +1,83 @@
182
2100000
3100001
4100002
5100004
6100005
7100006
8100007
9100008
10100009
11100010
12100011
13100012
14100013
15100014
16100015
17100016
18100017
19100018
20100019
21100020
22100021
23100022
24100024
25100025
26100026
27100027
28100028
29100029
30100030
31100031
32100033
33100036
34100037
35100038
36100039
37100041
38100042
39100043
40100044
41100045
42100046
43100047
44100048
45100049
46100051
47100052
48100053
49100056
50100058
51100059
52100060
53100062
54100063
55100064
56100065
57100066
58100067
59100068
60100069
61100070
62100071
63100072
64100073
65100074
66100075
67100076
68100077
69100079
70100081
71100084
72100086
73100087
74100088
75100089
76100090
77100091
78100092
79100093
80100095
81100096
82100097
83100099
diff --git a/test/104_h48set/h48set_tests.c b/test/104_h48set/h48set_tests.c
new file mode 100644
index 0000000..97811da
--- /dev/null
+++ b/test/104_h48set/h48set_tests.c
@@ -0,0 +1,69 @@
1#include "../test.h"
2
3char str[STRLENMAX];
4
5typedef struct {
6 int64_t n;
7 int64_t capacity;
8 int64_t mod;
9 int64_t *table;
10} h48set_t;
11
12void h48set_create(h48set_t *, int64_t, int64_t);
13void h48set_clear(h48set_t *);
14void h48set_destroy(h48set_t *);
15int64_t h48set_lookup(h48set_t *, int64_t);
16void h48set_insert(h48set_t *, int64_t);
17bool h48set_contains(h48set_t *, int64_t);
18
19int compare(const void *x, const void *y) {
20 int64_t a = *(int64_t *)x;
21 int64_t b = *(int64_t *)y;
22
23 if (a > b) return 1;
24 if (a == b) return 0;
25 return -1;
26}
27
28int64_t readl(void) {
29 fgets(str, STRLENMAX, stdin);
30 return atoll(str);
31}
32
33void run(void) {
34 bool f;
35 h48set_t set;
36 int64_t n, i, j, capacity, mod, *a, u;
37
38 capacity = readl();
39 mod = readl();
40 n = readl();
41
42 a = malloc(n * sizeof(int64_t));
43 for (i = 0; i < n; i++)
44 a[i] = readl();
45
46 /* Count unique elements */
47 u = 0;
48 for (i = 0; i < n; i++) {
49 for (j = 0, f = true; j < i; j++)
50 f = f && a[i] != a[j];
51 u += f;
52 }
53
54 h48set_create(&set, capacity, mod);
55 for (i = 0; i < n; i++)
56 h48set_insert(&set, a[i]);
57
58 for (i = 0, j = 0; i < set.capacity; i++)
59 if (set.table[i] != -1)
60 a[j++] = set.table[i];
61 qsort(a, j, sizeof(int64_t), compare);
62
63 printf("%" PRId64 "\n", set.n);
64 for (i = 0; i < j; i++)
65 printf("%" PRId64 "\n", a[i]);
66
67 h48set_destroy(&set);
68 free(a);
69}

Generated with cgit - Back to sebastiano.tronto.net