uppgb.c (3087B)
1 #include "common.h" 2 3 static inline void bfsl(uint8_t *hitv, uint64_t *hitd, graph_t *g, size_t start, 4 size_t lmt, size_t nr, size_t nc) { 5 size_t i; 6 SIMPLEQ_HEAD(listead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); 7 8 entry_t *e = malloc(sizeof(*e)); 9 e->node = start; 10 e->dist = 0; 11 SIMPLEQ_INSERT_TAIL(&head, e, entries); 12 13 while (!SIMPLEQ_EMPTY(&head)) { 14 e = SIMPLEQ_FIRST(&head); 15 SIMPLEQ_REMOVE_HEAD(&head, entries); 16 17 if (e->dist < lmt) { 18 for (i = 0; i < g->nbrs[e->node].nmemb; i++) { 19 if (hitv[g->nbrs[e->node].data[i]] == 0) { 20 entry_t *ne = malloc(sizeof(*e)); 21 ne->node = g->nbrs[e->node].data[i]; 22 ne->dist = e->dist + 1; 23 hitv[ne->node] = 1; 24 hitd[ne->node] = ne->dist; 25 SIMPLEQ_INSERT_TAIL(&head, ne, entries); 26 } 27 } 28 } 29 30 free(e); 31 } 32 } 33 34 typedef struct u64p { 35 uint64_t x; 36 uint64_t y; 37 } u64p_t; 38 39 static inline u64p_t hitt(uint8_t *hitv, uint64_t *hitd, size_t nr, size_t nc) { 40 uint64_t ho = 0; 41 uint64_t he = 0; 42 size_t i; 43 44 for (i = 0; i < nr * nc; i++) { 45 if (hitv[i] == 1) { 46 if (hitd[i] % 2 == 0) { 47 he++; 48 } else { 49 ho++; 50 } 51 } 52 } 53 54 return (u64p_t){ho, he}; 55 } 56 57 static inline u64p_t hlong(uint8_t *hitv, uint64_t *hitd, size_t nr, size_t nc, 58 size_t v) { 59 uint64_t ho = 0; 60 uint64_t he = 0; 61 size_t i; 62 63 for (i = 0; i < nr * nc; i++) { 64 if (hitv[i] == 1 && hitd[i] > v) { 65 if (hitd[i] % 2 == 0) { 66 he++; 67 } else { 68 ho++; 69 } 70 } 71 } 72 73 return (u64p_t){ho, he}; 74 } 75 76 /** 77 * This function asserts the magic properties we need 78 * to hold (magic in the sense as not in the specification, 79 * but perhaps observable) for this solution to be 80 * correct. I detest this non-general heuristic shit... 81 */ 82 static inline void assert_magic(char **lines, uint64_t nr, uint64_t nc, 83 u64p_t start, uint64_t steps) { 84 assert(start.x == nr / 2); 85 assert(start.y == nc / 2); 86 assert(nr == nc); 87 assert(nr == 131); 88 assert(steps % nr == nr / 2); 89 90 assert(lines[start.x][start.y] == 'S'); 91 92 size_t i; 93 // S is on clear row/col!!! 94 for (i = 0; i < nr; i++) { 95 assert(lines[i][start.y] == '.' || lines[i][start.y] == 'S'); 96 assert(lines[start.x][i] == '.' || lines[start.x][i] == 'S'); 97 } 98 } 99 100 int main(int argc, char **argv) { 101 char **lines; 102 size_t i; 103 size_t nr = readlines(&lines, "input"); 104 size_t nc = strlen(lines[0]) - 1; 105 uint64_t steps = 26501365; 106 107 uint8_t hitv[nr * nc]; 108 memset(hitv, 0, nr * nc); 109 uint64_t hitd[nr * nc]; 110 for (i = 0; i < nr * nc; i++) 111 hitd[i] = UINT64_MAX; 112 113 u64p_t sstart = {65, 65}; 114 assert_magic(lines, nr, nc, sstart, steps); 115 116 graph_t g; 117 size_t start; 118 read_grid(&g, &start, lines, nc); 119 120 bfsl(hitv, hitd, &g, start, 131, nr, nc); 121 122 u64p_t c = hitt(hitv, hitd, nr, nc); 123 u64p_t uh = hlong(hitv, hitd, nr, nc, 65); 124 125 uint64_t x = steps / nr; 126 uint64_t v = 127 c.x * (x + 1) * (x + 1) + c.y * x * x - (x + 1) * uh.x + x * uh.y; 128 printf("%llu\n", v); 129 }