uppgb.c (8614B)
1 #include "common.h" 2 #include <sys/queue.h> 3 4 #define NDIRS 4 5 enum direction { RIGHT, DOWN, LEFT, UP }; 6 7 typedef struct { 8 size_t r; 9 size_t c; 10 enum direction dir; 11 } walker; 12 13 typedef SIMPLEQ_HEAD(listhead, entry) head_t; 14 typedef struct entry { 15 walker v; 16 SIMPLEQ_ENTRY(entry) entries; 17 } entry_t; 18 19 static inline uint64_t energizer_count(size_t start_r, size_t start_c, 20 enum direction start_dir, size_t nrows, 21 size_t ncols, char **lines, 22 uint8_t ***hit) { 23 size_t i, j; 24 // init queue 25 head_t head = SIMPLEQ_HEAD_INITIALIZER(head); 26 27 // initialize the start 28 walker start = {.r = start_r, .c = start_c, .dir = start_dir}; 29 entry_t *se = malloc(sizeof(*se)); 30 se->v = start; 31 SIMPLEQ_INSERT_HEAD(&head, se, entries); 32 hit[start_dir][start_r][start_c] = 1; 33 34 entry_t *c; 35 while (!SIMPLEQ_EMPTY(&head)) { 36 c = SIMPLEQ_FIRST(&head); 37 SIMPLEQ_REMOVE_HEAD(&head, entries); 38 39 walker t = c->v; 40 switch (t.dir) { 41 case RIGHT: 42 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '-') { 43 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 44 (c->v).c++; 45 SIMPLEQ_INSERT_TAIL(&head, c, entries); 46 hit[RIGHT][t.r][t.c + 1] = 1; 47 } else { 48 free(c); 49 } 50 } else if (lines[t.r][t.c] == '\\') { 51 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 52 (c->v).r++; 53 (c->v).dir = DOWN; 54 SIMPLEQ_INSERT_TAIL(&head, c, entries); 55 hit[DOWN][t.r + 1][t.c] = 1; 56 } else { 57 free(c); 58 } 59 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '|') { 60 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 61 (c->v).r--; 62 (c->v).dir = UP; 63 SIMPLEQ_INSERT_TAIL(&head, c, entries); 64 hit[UP][t.r - 1][t.c] = 1; 65 } else { 66 free(c); 67 } 68 69 if (lines[t.r][t.c] == '|' && t.r < nrows - 1 && 70 !hit[DOWN][t.r + 1][t.c]) { 71 entry_t *nc = malloc(sizeof(*nc)); 72 (nc->v).c = t.c; 73 (nc->v).r = t.r + 1; 74 (nc->v).dir = DOWN; 75 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 76 hit[DOWN][t.r + 1][t.c] = 1; 77 } 78 } 79 break; 80 case DOWN: 81 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '|') { 82 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 83 (c->v).r++; 84 SIMPLEQ_INSERT_TAIL(&head, c, entries); 85 hit[DOWN][t.r + 1][t.c] = 1; 86 } else { 87 free(c); 88 } 89 } else if (lines[t.r][t.c] == '\\') { 90 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 91 (c->v).c++; 92 (c->v).dir = RIGHT; 93 SIMPLEQ_INSERT_TAIL(&head, c, entries); 94 hit[RIGHT][t.r][t.c + 1] = 1; 95 } else { 96 free(c); 97 } 98 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '-') { 99 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 100 (c->v).c--; 101 (c->v).dir = LEFT; 102 SIMPLEQ_INSERT_TAIL(&head, c, entries); 103 hit[LEFT][t.r][t.c - 1] = 1; 104 } else { 105 free(c); 106 } 107 108 if (lines[t.r][t.c] == '-' && t.c < ncols - 1 && 109 !hit[RIGHT][t.r][t.c + 1]) { 110 entry_t *nc = malloc(sizeof(*nc)); 111 (nc->v).c = t.c + 1; 112 (nc->v).r = t.r; 113 (nc->v).dir = RIGHT; 114 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 115 hit[RIGHT][t.r][t.c + 1] = 1; 116 } 117 } 118 break; 119 case LEFT: 120 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '-') { 121 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 122 (c->v).c--; 123 SIMPLEQ_INSERT_TAIL(&head, c, entries); 124 hit[LEFT][t.r][t.c - 1] = 1; 125 } else { 126 free(c); 127 } 128 } else if (lines[t.r][t.c] == '\\') { 129 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 130 (c->v).r--; 131 (c->v).dir = UP; 132 SIMPLEQ_INSERT_TAIL(&head, c, entries); 133 hit[UP][t.r - 1][t.c] = 1; 134 } else { 135 free(c); 136 } 137 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '|') { 138 if (t.r < nrows - 1 && !hit[DOWN][t.r + 1][t.c]) { 139 (c->v).r++; 140 (c->v).dir = DOWN; 141 SIMPLEQ_INSERT_TAIL(&head, c, entries); 142 hit[DOWN][t.r + 1][t.c] = 1; 143 } else { 144 free(c); 145 } 146 147 if (lines[t.r][t.c] == '|' && t.r > 0 && !hit[UP][t.r - 1][t.c]) { 148 entry_t *nc = malloc(sizeof(*nc)); 149 (nc->v).c = t.c; 150 (nc->v).r = t.r - 1; 151 (nc->v).dir = UP; 152 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 153 hit[UP][t.r - 1][t.c] = 1; 154 } 155 } 156 break; 157 case UP: 158 if (lines[t.r][t.c] == '.' || lines[t.r][t.c] == '|') { 159 if (t.r > 0 && !hit[UP][t.r - 1][t.c]) { 160 (c->v).r--; 161 SIMPLEQ_INSERT_TAIL(&head, c, entries); 162 hit[UP][t.r - 1][t.c] = 1; 163 } else { 164 free(c); 165 } 166 } else if (lines[t.r][t.c] == '\\') { 167 if (t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 168 (c->v).c--; 169 (c->v).dir = LEFT; 170 SIMPLEQ_INSERT_TAIL(&head, c, entries); 171 hit[LEFT][t.r][t.c - 1] = 1; 172 } else { 173 free(c); 174 } 175 } else if (lines[t.r][t.c] == '/' || lines[t.r][t.c] == '-') { 176 if (t.c < ncols - 1 && !hit[RIGHT][t.r][t.c + 1]) { 177 (c->v).c++; 178 (c->v).dir = RIGHT; 179 SIMPLEQ_INSERT_TAIL(&head, c, entries); 180 hit[RIGHT][t.r][t.c + 1] = 1; 181 } else { 182 free(c); 183 } 184 185 if (lines[t.r][t.c] == '-' && t.c > 0 && !hit[LEFT][t.r][t.c - 1]) { 186 entry_t *nc = malloc(sizeof(*nc)); 187 (nc->v).c = t.c - 1; 188 (nc->v).r = t.r; 189 (nc->v).dir = LEFT; 190 SIMPLEQ_INSERT_TAIL(&head, nc, entries); 191 hit[LEFT][t.r][t.c - 1] = 1; 192 } 193 } 194 break; 195 } 196 } 197 198 uint64_t count = 0; 199 for (i = 0; i < nrows; i++) { 200 for (j = 0; j < ncols; j++) { 201 if (hit[RIGHT][i][j] || hit[LEFT][i][j] || hit[DOWN][i][j] || 202 hit[UP][i][j]) { 203 count++; 204 } 205 } 206 } 207 208 return count; 209 } 210 211 static inline void zeroise_hits(uint8_t ***hit, size_t nrows, size_t ncols) { 212 size_t i, j, k; 213 for (k = 0; k < NDIRS; k++) { 214 hit[k] = malloc(nrows * sizeof(*hit[k])); 215 for (i = 0; i < nrows; i++) { 216 hit[k][i] = malloc(ncols * sizeof(*hit[k][i])); 217 for (j = 0; j < ncols; j++) { 218 hit[k][i][j] = 0; 219 } 220 } 221 } 222 } 223 224 int main(int argc, char **argv) { 225 char **lines; 226 size_t nrows = readlines(&lines, "input"); 227 228 size_t ncols = strnlen(lines[0], 1024); 229 assert(ncols < 1024); 230 ncols--; 231 232 uint8_t **hit[NDIRS]; 233 size_t i, j, k; 234 for (k = 0; k < NDIRS; k++) { 235 hit[k] = malloc(nrows * sizeof(*hit[k])); 236 for (i = 0; i < nrows; i++) { 237 hit[k][i] = malloc(ncols * sizeof(*hit[k][i])); 238 for (j = 0; j < ncols; j++) { 239 hit[k][i][j] = 0; 240 } 241 } 242 } 243 244 uint64_t max_count = 0; 245 uint64_t count; 246 247 // top row, downwards 248 for (i = 0; i < ncols; i++) { 249 count = energizer_count(0, i, DOWN, nrows, ncols, lines, hit); 250 if (count > max_count) 251 max_count = count; 252 zeroise_hits(hit, nrows, ncols); 253 } 254 255 // bottom row, upwards 256 for (i = 0; i < ncols; i++) { 257 count = energizer_count(nrows - 1, i, UP, nrows, ncols, lines, hit); 258 if (count > max_count) 259 max_count = count; 260 zeroise_hits(hit, nrows, ncols); 261 } 262 263 // left side, rightwards 264 for (i = 0; i < nrows; i++) { 265 count = energizer_count(i, 0, RIGHT, nrows, ncols, lines, hit); 266 if (count > max_count) 267 max_count = count; 268 zeroise_hits(hit, nrows, ncols); 269 } 270 271 // right side, leftwards 272 for (i = 0; i < nrows; i++) { 273 count = energizer_count(i, ncols - 1, LEFT, nrows, ncols, lines, hit); 274 if (count > max_count) 275 max_count = count; 276 zeroise_hits(hit, nrows, ncols); 277 } 278 279 // remaining corners 280 count = energizer_count(0, 0, RIGHT, nrows, ncols, lines, hit); 281 if (count > max_count) 282 max_count = count; 283 zeroise_hits(hit, nrows, ncols); 284 count = energizer_count(0, ncols - 1, LEFT, nrows, ncols, lines, hit); 285 if (count > max_count) 286 max_count = count; 287 zeroise_hits(hit, nrows, ncols); 288 count = energizer_count(nrows - 1, 0, RIGHT, nrows, ncols, lines, hit); 289 if (count > max_count) 290 max_count = count; 291 zeroise_hits(hit, nrows, ncols); 292 count = energizer_count(nrows - 1, ncols - 1, LEFT, nrows, ncols, lines, hit); 293 if (count > max_count) 294 max_count = count; 295 zeroise_hits(hit, nrows, ncols); 296 297 printf("%llu\n", max_count); 298 }