uppgb.c (9409B)
1 #include <assert.h> 2 #include <stdint.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <sys/queue.h> 6 7 #include <dict.h> 8 #include <reading.h> 9 #include <stack_u64.h> 10 11 dict_t *names; 12 13 #define MAX_CONDITIONS 32 14 #define MAX_NBRS 2048 15 16 typedef struct { 17 uint64_t bounds[4][2]; 18 } cond_t; 19 20 typedef struct { 21 size_t n; 22 size_t entry[MAX_CONDITIONS]; 23 size_t iftru[MAX_CONDITIONS]; 24 cond_t condition[MAX_CONDITIONS]; 25 } cond_list_t; 26 27 typedef struct { 28 size_t nnbrs; 29 size_t *nbrs; 30 cond_t *cond; 31 } edge_list_t; 32 33 static inline size_t add_name(char *name) { 34 sd sdname; 35 sd_init_str(&sdname, name); 36 void *p = dict_lookup(names, sdname); 37 38 if (p != NULL) { 39 return *(size_t *)p; 40 } else { 41 size_t *x = malloc(sizeof(*x)); 42 *x = names->nelts; 43 dict_insert(names, sdname, x); 44 45 return *x; 46 } 47 } 48 49 static inline void parse_end_condition(cond_list_t *res, char *s) { 50 assert(res->n < MAX_CONDITIONS); 51 cond_t v = { 52 .bounds = { 53 {0, UINT64_MAX}, {0, UINT64_MAX}, {0, UINT64_MAX}, {0, UINT64_MAX}}}; 54 res->condition[res->n] = v; 55 res->entry[res->n] = SIZE_MAX; 56 res->iftru[res->n] = add_name(s); 57 res->n++; 58 } 59 60 static inline void parse_mid_condition(cond_list_t *res, char *s) { 61 assert(res->n < MAX_CONDITIONS); 62 63 size_t entry = SIZE_MAX; 64 switch (s[0]) { 65 case 'x': 66 entry = 0; 67 break; 68 case 'm': 69 entry = 1; 70 break; 71 case 'a': 72 entry = 2; 73 break; 74 case 's': 75 entry = 3; 76 break; 77 } 78 79 assert(entry != SIZE_MAX); 80 assert(entry < 5); 81 82 cond_t v = { 83 .bounds = { 84 {0, UINT64_MAX}, {0, UINT64_MAX}, {0, UINT64_MAX}, {0, UINT64_MAX}}}; 85 res->condition[res->n] = v; 86 87 uint64_t bound_value; 88 char *cp = sread_next_u64(&bound_value, s); 89 assert(cp[0] == ':'); 90 cp++; 91 res->iftru[res->n] = add_name(cp); 92 93 switch (s[1]) { 94 case '>': 95 res->condition[res->n].bounds[entry][0] = bound_value; 96 break; 97 case '<': 98 res->condition[res->n].bounds[entry][1] = bound_value; 99 break; 100 case '=': 101 assert(bound_value > 0); 102 assert(bound_value < UINT64_MAX); 103 res->condition[res->n].bounds[entry][0] = bound_value - 1; 104 res->condition[res->n].bounds[entry][1] = bound_value + 1; 105 break; 106 default: 107 assert(1 == 2); 108 } 109 110 res->entry[res->n] = entry; 111 res->n++; 112 } 113 114 static inline cond_list_t parse_conds(char *s) { 115 cond_list_t res; 116 res.n = 0; 117 118 char *sa = strtok(s, ","); 119 while (sa != NULL) { 120 if (!strstr(sa, ":")) { 121 parse_end_condition(&res, sa); 122 } else { 123 parse_mid_condition(&res, sa); 124 } 125 sa = strtok(NULL, ","); 126 } 127 128 return res; 129 } 130 131 static inline cond_list_t parse_line(stack_u64 *linerow, char *line) { 132 cond_list_t r; 133 134 if (strlen(line) < 2) { 135 r.n = SIZE_MAX; 136 return r; 137 } 138 139 char *sa = strtok(line, "{}"); 140 size_t row = add_name(sa); 141 sa = strtok(NULL, "{}"); 142 while (sa != NULL) { 143 r = parse_conds(sa); 144 sa = strtok(NULL, "{}"); 145 } 146 147 stack_u64_push(linerow, row); 148 149 return r; 150 } 151 152 static inline cond_list_t tail_cond_list(cond_list_t clist) { 153 cond_list_t r; 154 r.n = clist.n - 1; 155 156 size_t i; 157 for (i = 0; i < r.n; i++) { 158 r.entry[i] = clist.entry[i + 1]; 159 r.iftru[i] = clist.iftru[i + 1]; 160 r.condition[i] = clist.condition[i + 1]; 161 } 162 163 return r; 164 } 165 166 static inline uint64_t mmax(const uint64_t x, const uint64_t y) { 167 return x < y ? y : x; 168 } 169 170 static inline uint64_t mmin(const uint64_t x, const uint64_t y) { 171 return x < y ? x : y; 172 } 173 174 static inline void append_list(cond_list_t *r, cond_list_t *a) { 175 assert(r->n + a->n <= MAX_CONDITIONS); 176 177 size_t i; 178 for (i = 0; i < a->n; i++) { 179 r->entry[r->n] = a->entry[i]; 180 r->condition[r->n] = a->condition[i]; 181 r->iftru[r->n] = a->iftru[i]; 182 r->n++; 183 } 184 } 185 186 static cond_list_t exclusive_conditions(cond_list_t clist, cond_t base) { 187 if (clist.n == 1) { 188 assert(clist.entry[0] == SIZE_MAX); // end condition 189 cond_list_t ret; 190 ret.n = 1; 191 ret.condition[0] = base; 192 return ret; 193 } 194 195 size_t entry = clist.entry[0]; 196 cond_list_t tail = tail_cond_list(clist); 197 cond_t head = clist.condition[0]; 198 199 cond_t andro = base; 200 int halist = 0; 201 cond_list_t alist; 202 int hblist = 0; 203 cond_list_t blist; 204 andro.bounds[entry][0] = mmax(base.bounds[entry][0], head.bounds[entry][0]); 205 andro.bounds[entry][1] = mmin(base.bounds[entry][1], head.bounds[entry][1]); 206 207 if (head.bounds[entry][0] != 0) { 208 // recurse a 209 halist = 1; 210 cond_t nbase = base; 211 nbase.bounds[entry][0] = base.bounds[entry][0]; 212 nbase.bounds[entry][1] = 213 mmin(base.bounds[entry][1], head.bounds[entry][0] + 1); 214 alist = exclusive_conditions(tail, nbase); 215 } 216 217 if (head.bounds[entry][1] != UINT64_MAX) { 218 // recurse b 219 hblist = 1; 220 cond_t nbase = base; 221 nbase.bounds[entry][1] = base.bounds[entry][1]; 222 nbase.bounds[entry][0] = 223 mmax(base.bounds[entry][0], head.bounds[entry][1] - 1); 224 blist = exclusive_conditions(tail, nbase); 225 } 226 227 cond_list_t ret; 228 ret.n = 1; 229 ret.condition[0] = andro; 230 231 if (halist) { 232 // append alist to ret 233 append_list(&ret, &alist); 234 } 235 236 if (hblist) { 237 // append blist to ret 238 append_list(&ret, &blist); 239 } 240 241 return ret; 242 } 243 244 static inline void add_edge(edge_list_t *rgraph, size_t from, size_t to, 245 cond_t cond) { 246 size_t nn = rgraph[from].nnbrs; 247 assert(nn < MAX_NBRS); 248 rgraph[from].nbrs[nn] = to; 249 rgraph[from].cond[nn] = cond; 250 rgraph[from].nnbrs++; 251 } 252 253 static inline void reverse_graph(edge_list_t *rgraph, size_t n, 254 cond_list_t *clists, size_t nclists, 255 stack_u64 *froms) { 256 size_t i, j; 257 for (i = 0; i < nclists; i++) { 258 for (j = 0; j < clists[i].n; j++) { 259 add_edge(rgraph, clists[i].iftru[j], froms->data[i], 260 clists[i].condition[j]); 261 } 262 } 263 } 264 265 static inline cond_t intersect_condition(cond_t ca, cond_t cb) { 266 return (cond_t){.bounds = {{mmax(ca.bounds[0][0], cb.bounds[0][0]), 267 mmin(ca.bounds[0][1], cb.bounds[0][1])}, 268 {mmax(ca.bounds[1][0], cb.bounds[1][0]), 269 mmin(ca.bounds[1][1], cb.bounds[1][1])}, 270 {mmax(ca.bounds[2][0], cb.bounds[2][0]), 271 mmin(ca.bounds[2][1], cb.bounds[2][1])}, 272 {mmax(ca.bounds[3][0], cb.bounds[3][0]), 273 mmin(ca.bounds[3][1], cb.bounds[3][1])}}}; 274 } 275 276 static inline int sensible_condition(cond_t c) { 277 if (c.bounds[0][0] + 2 > c.bounds[0][1]) 278 return 0; 279 if (c.bounds[1][0] + 2 > c.bounds[1][1]) 280 return 0; 281 if (c.bounds[2][0] + 2 > c.bounds[2][1]) 282 return 0; 283 if (c.bounds[3][0] + 2 > c.bounds[3][1]) 284 return 0; 285 return 1; 286 } 287 288 static inline uint64_t count_cond(cond_t c) { 289 uint64_t p = 1; 290 p *= (c.bounds[0][1] - 1 - c.bounds[0][0]); 291 p *= (c.bounds[1][1] - 1 - c.bounds[1][0]); 292 p *= (c.bounds[2][1] - 1 - c.bounds[2][0]); 293 p *= (c.bounds[3][1] - 1 - c.bounds[3][0]); 294 return p; 295 } 296 297 typedef struct entry { 298 size_t vx; 299 cond_t cond; 300 301 SIMPLEQ_ENTRY(entry) entries; 302 } entry_t; 303 304 static inline uint64_t allpath_cond(edge_list_t *rgraph, size_t start, 305 size_t end, cond_t scond) { 306 uint64_t sumsi = 0; 307 308 SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 309 entry_t *np = malloc(sizeof(*np)); 310 np->vx = start; 311 np->cond = scond; 312 SIMPLEQ_INSERT_HEAD(&head, np, entries); 313 314 while (!SIMPLEQ_EMPTY(&head)) { 315 np = SIMPLEQ_FIRST(&head); 316 SIMPLEQ_REMOVE_HEAD(&head, entries); 317 318 if (np->vx == end) { 319 sumsi += count_cond(np->cond); 320 } else { 321 size_t i; 322 for (i = 0; i < rgraph[np->vx].nnbrs; i++) { 323 cond_t ic = intersect_condition(rgraph[np->vx].cond[i], np->cond); 324 if (sensible_condition(ic)) { 325 entry_t *nnp = malloc(sizeof(*nnp)); 326 nnp->vx = rgraph[np->vx].nbrs[i]; 327 nnp->cond = ic; 328 SIMPLEQ_INSERT_TAIL(&head, nnp, entries); 329 } 330 } 331 } 332 333 free(np); 334 } 335 336 return sumsi; 337 } 338 339 int main(int argc, char **argv) { 340 char **lines; 341 size_t nlines = readlines(&lines, "input"); 342 343 names = malloc(sizeof(*names)); 344 dict_init(names); 345 346 size_t nclists = 0; 347 cond_list_t clists[nlines]; 348 stack_u64 froms; 349 stack_u64_init(&froms); 350 clists[0] = parse_line(&froms, lines[0]); 351 nclists++; 352 353 while (clists[nclists - 1].n != SIZE_MAX) { 354 clists[nclists] = parse_line(&froms, lines[nclists]); 355 nclists++; 356 } 357 nclists--; 358 359 size_t i, j; 360 for (i = 0; i < nclists; i++) { 361 cond_t base = {.bounds = {{0, UINT64_MAX}, 362 {0, UINT64_MAX}, 363 {0, UINT64_MAX}, 364 {0, UINT64_MAX}}}; 365 cond_list_t excl = exclusive_conditions(clists[i], base); 366 for (j = 0; j < excl.n; j++) { 367 clists[i].condition[j] = excl.condition[j]; 368 } 369 } 370 371 size_t n = names->nelts; 372 edge_list_t rgraph[n]; 373 for (i = 0; i < n; i++) { 374 rgraph[i].nnbrs = 0; 375 rgraph[i].nbrs = malloc(MAX_NBRS * sizeof(*(rgraph[i].nbrs))); 376 rgraph[i].cond = malloc(MAX_NBRS * sizeof(*(rgraph[i].cond))); 377 } 378 reverse_graph(rgraph, n, clists, nclists, &froms); 379 380 cond_t scond = {.bounds = {{0, 4001}, {0, 4001}, {0, 4001}, {0, 4001}}}; 381 size_t start = add_name("A"); 382 size_t end = add_name("in"); 383 uint64_t sum = allpath_cond(rgraph, start, end, scond); 384 385 printf("%llu\n", sum); 386 387 stack_u64_clear(&froms); 388 free(names); 389 }