uppga.c (4898B)
1 #include "common.h" 2 3 #define SEC 30ULL 4 #define NOTCOMPUTED UINT64_MAX 5 #define NONBR SIZE_MAX 6 7 #define ASIZE ((uint64_t)('Z' - 'A' + 1)) 8 #define MAP_SIZE (ASIZE * ASIZE) 9 10 typedef struct { 11 size_t n; 12 size_t m; 13 14 size_t nv; 15 uint64_t *v; // store computed values 16 17 uint64_t *flows; 18 size_t *nzflows; // maps position to index of nonzero flow (in e.g. state) 19 size_t **nbrs; 20 } valves; 21 22 static inline size_t statelen(valves v) { return v.m + 2; } 23 24 static inline size_t statemax(valves v) { 25 return ((v.n) * (SEC + 1) << v.m) - 1; 26 } 27 28 static inline int notime(uint64_t fs, valves v) { 29 return (fs >> v.m) % (SEC + 1) == 0; 30 } 31 32 static inline char *goto_nbrs(char *s) { 33 size_t i = 0, c = 0; 34 while (c != 9) { 35 if (s[i] == ' ') 36 c++; 37 i++; 38 } 39 return &(s[i]); 40 } 41 42 static inline size_t map_index(char *x) { 43 return ASIZE * ((uint64_t)(x[0] - 'A')) + ((uint64_t)(x[1] - 'A')); 44 } 45 46 void init_valves(valves *v, char **lines, const size_t n) { 47 v->n = n; 48 v->m = 0; 49 50 v->flows = malloc((v->n) * sizeof(*(v->flows))); 51 v->nzflows = malloc((v->n) * sizeof(*(v->nzflows))); 52 v->nbrs = malloc((v->n) * sizeof(*(v->nbrs))); 53 54 size_t i, j; 55 size_t map[MAP_SIZE]; 56 for (i = 0; i < MAP_SIZE; i++) 57 map[i] = SIZE_MAX; 58 for (i = 0; i < n; i++) { 59 char *line = lines[i]; 60 map[map_index(&line[6])] = i; 61 } 62 63 for (i = 0; i < n; i++) { 64 char *line = lines[i]; 65 66 char *flowstr = &line[23]; 67 uint64_t flow; 68 sread_next_u64(&flow, flowstr); 69 v->flows[i] = flow; 70 if (flow != 0) { 71 v->nzflows[i] = v->m + 2; 72 v->m++; 73 } else { 74 v->nzflows[i] = SIZE_MAX; 75 } 76 77 v->nbrs[i] = malloc((v->n) * sizeof(*(v->nbrs[i]))); 78 char *nbrs = goto_nbrs(line); 79 char *cn = nbrs; 80 j = 0; 81 while (cn[0] != '\n' && cn[0] != '\0') { 82 assert(cn[0] <= 'Z' && cn[0] >= 'A'); 83 assert(cn[1] <= 'Z' && cn[1] >= 'A'); 84 v->nbrs[i][j] = map[map_index(cn)]; 85 if (strlen(cn) < 4) { 86 j++; 87 break; 88 } 89 j++; 90 cn = &cn[4]; 91 } 92 while (j < v->n) { 93 v->nbrs[i][j] = NONBR; 94 j++; 95 } 96 } 97 98 v->nv = statemax(*v) + 1; 99 v->v = malloc((v->nv) * sizeof(*(v->v))); 100 for (i = 0; i < v->nv; i++) 101 v->v[i] = NOTCOMPUTED; 102 } 103 104 size_t f(const uint8_t *state, const valves *v) { 105 size_t r = ((unsigned long)state[0]) * (SEC + 1) + (unsigned long)state[1]; 106 size_t i; 107 for (i = 0; i < v->m; i++) { 108 r <<= 1; 109 if (state[i + 2]) 110 r++; 111 } 112 return r; 113 } 114 115 void f_inv(uint8_t *state, const size_t y, const valves *v) { 116 size_t i; 117 size_t slen = statelen(*v); 118 119 size_t x = y; 120 121 for (i = 1; i <= v->m; i++) { 122 if ((x & 0x01) != 0) { 123 state[slen - i] = 1; 124 } else { 125 state[slen - i] = 0; 126 } 127 x >>= 1; 128 } 129 130 assert(x < (SEC + 1) * (v->n)); 131 132 state[1] = (uint8_t)(x % (SEC + 1)); 133 state[0] = (uint8_t)(x / (SEC + 1)); 134 } 135 136 uint8_t *init_starting_state(valves v) { 137 uint8_t *r = malloc(statelen(v)); 138 139 r[0] = 0; // posituon AA == 0 140 r[1] = SEC; // 30 secs remaining 141 142 size_t i; 143 for (i = 2; i < v.m + 2; i++) 144 r[i] = 0; // no valves on 145 146 return r; 147 } 148 149 static inline uint64_t stateflow(const uint8_t *state, const valves *v) { 150 uint64_t r = 0; 151 size_t i; 152 for (i = 0; i < v->n; i++) { 153 if (v->flows[i] != 0) { 154 r += ((uint64_t)state[v->nzflows[i]]) * v->flows[i]; 155 } 156 } 157 return r; 158 } 159 160 void print_state(const uint8_t *state, const valves *v) { 161 printf("%u : %u : ", state[0], state[1]); 162 size_t i; 163 for (i = 0; i < v->m; i++) { 164 printf("%u ", state[i + 2]); 165 } 166 printf("\n"); 167 } 168 169 uint64_t recurse(const uint64_t fs, valves *v, int level) { 170 if (v->v[fs] != NOTCOMPUTED) 171 return v->v[fs]; 172 uint64_t r = 0; 173 174 if (notime(fs, *v)) { 175 v->v[fs] = r; 176 return r; 177 } 178 179 uint8_t state[statelen(*v)]; 180 f_inv(state, fs, v); 181 182 size_t pos = (size_t)state[0]; 183 184 // nonzero flow 185 if (v->flows[pos] != 0) { 186 if (state[v->nzflows[pos]] == 0) { 187 uint8_t new_state[statelen(*v)]; 188 memcpy(new_state, state, statelen(*v)); 189 new_state[v->nzflows[pos]] = 1; 190 new_state[1]--; 191 uint64_t t = stateflow(state, v) + recurse(f(new_state, v), v, level + 1); 192 if (t > r) 193 r = t; 194 } 195 } 196 197 // neighbours 198 size_t i = 0; 199 while (v->nbrs[pos][i] != NONBR) { 200 uint8_t new_state[statelen(*v)]; 201 memcpy(new_state, state, statelen(*v)); 202 new_state[1]--; 203 new_state[0] = (uint8_t)v->nbrs[pos][i]; 204 uint64_t t = stateflow(state, v) + recurse(f(new_state, v), v, level + 1); 205 if (t > r) 206 r = t; 207 i++; 208 } 209 210 v->v[fs] = r; 211 return r; 212 } 213 214 int main(int argc, char **argv) { 215 char **lines; 216 valves v; 217 size_t nlines = readlines(&lines, "sinput"); 218 219 init_valves(&v, lines, nlines); 220 221 uint8_t *starting_state = init_starting_state(v); 222 223 size_t f_ss = f(starting_state, &v); 224 uint8_t *tmp_state = malloc(statelen(v)); 225 f_inv(tmp_state, f_ss, &v); 226 227 uint64_t r = recurse(f_ss, &v, 0); 228 printf("%llu\n", r); 229 }