main.c (7162B)
1#include "aoc.h" 2#include "dvec_s.h" 3#include "allocator.h" 4#include "util.h" 5#include "iccmp.h" 6#include "hmap.h" 7#include "vec.h" 8 9#include <assert.h> 10#include <stdbool.h> 11#include <stddef.h> 12#include <stdio.h> 13#include <stdlib.h> 14 15enum { 16 MOVE_NORTH = 1, 17 MOVE_SOUTH, 18 MOVE_WEST, 19 MOVE_EAST 20}; 21 22enum { 23 BLOCK_WALL = 0, 24 BLOCK_OPEN, 25 BLOCK_GOAL 26}; 27 28struct state { 29 int back; 30 int next; 31}; 32 33const char block_lut[] = { 34 '#', 35 '.', 36 'O' 37}; 38 39const struct vec2i dirs[] = { 40 { 0 }, 41 { 0, -1 }, 42 { 0, 1 }, 43 { -1, 0 }, 44 { 1, 0 }, 45}; 46 47const int rev[] = { 48 0, 2, 1, 4, 3 49}; 50 51uint32_t 52vec_hmap_hash(struct hmap_key key) 53{ 54 const struct vec2i *vec = key.p; 55 56 return (uint32_t) (vec->x << 16) ^ (uint32_t) vec->y; 57} 58 59bool 60vec_hmap_keycmp(struct hmap_key k1, struct hmap_key k2) 61{ 62 const struct vec2i *v1 = k1.p, *v2 = k2.p; 63 64 return v1->x == v2->x && v1->y == v2->y; 65} 66 67int 68robot_move(struct icc *icc, int dir) 69{ 70 while (icc->state != ICC_HALT) { 71 icc_step_inst(icc); 72 switch (icc->state) { 73 case ICC_INPUT: 74 mi_setv(&icc->in, (mi_ul) dir, MI_POS); 75 continue; 76 case ICC_OUTPUT: 77 return (int) mi_cast_ul(&icc->out); 78 case ICC_HALT: 79 case ICC_RUN: 80 continue; 81 } 82 } 83 84 return -1; 85} 86 87void 88print_map(struct hmap *map, struct vec2i droid) 89{ 90 struct hmap_link *link; 91 struct hmap_iter iter; 92 struct vec2i min = { 0 }; 93 struct vec2i max = { 0 }; 94 struct vec2i pos; 95 const struct vec2i *vec; 96 97 for (HMAP_ITER(map, iter)) { 98 vec = iter.link->key.p; 99 min.x = MIN(min.x, vec->x); 100 min.y = MIN(min.y, vec->y); 101 max.x = MAX(max.x, vec->x); 102 max.y = MAX(max.y, vec->y); 103 } 104 105 fprintf(stderr, "+"); 106 for (pos.x = min.x; pos.x <= max.x; pos.x++) 107 fprintf(stderr, "-"); 108 fprintf(stderr, "+\n"); 109 110 for (pos.y = min.y; pos.y <= max.y; pos.y++) { 111 fprintf(stderr, "|"); 112 for (pos.x = min.x; pos.x <= max.x; pos.x++) { 113 if (pos.x == droid.x && pos.y == droid.y) { 114 fprintf(stderr, "D"); 115 } else { 116 link = hmap_get(map, 117 (struct hmap_key) {.p = &pos}); 118 if (link) { 119 fprintf(stderr, "%c", link->value.c); 120 } else { 121 fprintf(stderr, " "); 122 } 123 } 124 } 125 fprintf(stderr, "|\n"); 126 } 127 128 fprintf(stderr, "+"); 129 for (pos.x = min.x; pos.x <= max.x; pos.x++) 130 fprintf(stderr, "-"); 131 fprintf(stderr, "+\n"); 132} 133 134size_t 135dijkstra_dist(struct hmap *map, struct vec2i start, const struct vec2i *end) 136{ 137 struct hmap_link *link, **linkp; 138 struct hmap_iter iter; 139 struct hmap seen; 140 struct dvec outer; 141 struct vec2i *vec; 142 struct vec2i pos, npos; 143 size_t dist, maxdist; 144 void *key; 145 int dir; 146 147 hmap_init(&seen, 32, vec_hmap_hash, vec_hmap_keycmp, 148 &stdlib_strict_heap_allocator); 149 dvec_init(&outer, sizeof(struct vec2i), 150 10, &stdlib_strict_heap_allocator); 151 152 vec = dvec_add_slot(&outer); 153 vec2i_set(vec, &start); 154 155 key = memdup(vec, sizeof(struct vec2i)); 156 hmap_add(&seen, (struct hmap_key) {.p = key}, 157 (struct hmap_val) {.s = 0}); 158 159 maxdist = 0; 160 while (!dvec_empty(&outer)) { 161 vec = dvec_back(&outer); 162 vec2i_set(&pos, vec); 163 link = hmap_get(&seen, (struct hmap_key) {.p = &pos}); 164 assert(link); 165 dist = link->value.s + 1; 166 dvec_rm_slot(&outer, vec); 167 168 for (dir = 1; dir <= 4; dir++) { 169 vec2i_add(&npos, &pos, &dirs[dir]); 170 linkp = hmap_link_pos(&seen, 171 (struct hmap_key) {.p = &npos}); 172 if (*linkp) continue; 173 174 if (end && !memcmp(&npos, end, sizeof(struct vec2i))) 175 goto exit; 176 177 link = hmap_get(map, (struct hmap_key) {.p = &npos}); 178 assert(link); 179 if (link->value.c != '.') continue; 180 181 if (!maxdist || dist > maxdist) 182 maxdist = dist; 183 184 vec = dvec_add_slot(&outer); 185 vec2i_set(vec, &npos); 186 key = memdup(&npos, sizeof(struct vec2i)); 187 *linkp = hmap_link_alloc(&seen, 188 (struct hmap_key) {.p = key}, 189 (struct hmap_val) {.s = dist}, NULL); 190 } 191 } 192 193exit: 194 for (HMAP_ITER(&seen, iter)) 195 free(iter.link->key._p); 196 dvec_deinit(&outer); 197 hmap_deinit(&seen); 198 199 return end ? dist : maxdist; 200} 201 202void 203explore_map(struct icc *icc, struct hmap *map, 204 struct vec2i start, struct vec2i *tank) 205{ 206 struct hmap_link **linkp; 207 struct hmap_link *link; 208 struct dvec states; 209 struct vec2i pos, npos; 210 struct state *state; 211 int move_result; 212 int move_dir; 213 void *key; 214 215 dvec_init(&states, sizeof(struct state), 216 10, &stdlib_strict_heap_allocator); 217 218 state = dvec_add_slot(&states); 219 state->back = -1; 220 state->next = 1; 221 222 vec2i_set(&pos, &start); 223 key = memdup(&pos, sizeof(struct vec2i)); 224 hmap_add(map, (struct hmap_key) {.p = key}, 225 (struct hmap_val) {.c = '.'}); 226 227 while (!dvec_empty(&states)) { 228 assert(!dvec_empty(&states)); 229 state = dvec_back(&states); 230 for (; state->next <= 4; state->next++) { 231 if (state->next == state->back) 232 continue; 233 move_dir = state->next; 234 vec2i_add(&npos, &pos, &dirs[move_dir]); 235 link = hmap_get(map, 236 (struct hmap_key) {.p = &npos}); 237 if (!link) break; 238 } 239 240 if (state->next > 4) { 241 if (state->back <= 0) break; 242 move_result = robot_move(icc, state->back); 243 assert(move_result == BLOCK_OPEN); 244 vec2i_add(&pos, &pos, &dirs[state->back]); 245 dvec_rm_slot(&states, state); 246 if (aoc.debug) { 247 aoc_debug("Step: backtrack x %i y %i\n", pos.x, pos.y); 248 print_map(map, pos); 249 aoc_debug("\n"); 250 } 251 continue; 252 } 253 state->next += 1; 254 255 assert(move_dir >= 1 && move_dir <= 4); 256 move_result = robot_move(icc, move_dir); 257 assert(move_result >= 0 && move_result <= 2); 258 259 linkp = hmap_link_pos(map, (struct hmap_key) {.p = &npos}); 260 if (*linkp) { 261 (*linkp)->value.c = block_lut[move_result]; 262 } else { 263 key = memdup(&npos, sizeof(struct vec2i)); 264 *linkp = hmap_link_alloc(map, 265 (struct hmap_key) {.p = key}, 266 (struct hmap_val) {.c = block_lut[move_result]}, 267 NULL); 268 } 269 270 switch (move_result) { 271 case BLOCK_GOAL: 272 vec2i_set(tank, &npos); 273 case BLOCK_OPEN: 274 vec2i_set(&pos, &npos); 275 state = dvec_add_slot(&states); 276 state->back = rev[move_dir]; 277 state->next = 1; 278 break; 279 case BLOCK_WALL: 280 break; 281 default: 282 assert(0); 283 } 284 285 if (aoc.debug) { 286 aoc_debug("Step: x %i y %i dx %i dy %i\n", 287 pos.x, pos.y, dirs[move_dir].x, dirs[move_dir].y); 288 print_map(map, pos); 289 aoc_debug("\n"); 290 } 291 } 292 293 dvec_deinit(&states); 294} 295 296void 297part1(void) 298{ 299 struct icc icc; 300 struct hmap_iter iter; 301 struct hmap map; 302 struct vec2i start, tank; 303 size_t dist; 304 305 icc_init(&icc); 306 hmap_init(&map, 32, vec_hmap_hash, vec_hmap_keycmp, 307 &stdlib_strict_heap_allocator); 308 309 icc_parse_inst(&icc, aoc.input, aoc.input_size); 310 311 start = (struct vec2i) { 0, 0 }; 312 explore_map(&icc, &map, start, &tank); 313 314 dist = dijkstra_dist(&map, start, &tank); 315 316 aoc.answer = aprintf("%lu", dist); 317 aoc.solution = "234"; 318 319 for (HMAP_ITER(&map, iter)) 320 free(iter.link->key._p); 321 hmap_deinit(&map); 322 icc_deinit(&icc); 323} 324 325void 326part2(void) 327{ 328 struct icc icc; 329 struct hmap_iter iter; 330 struct hmap map; 331 struct vec2i start, tank; 332 size_t dist; 333 334 icc_init(&icc); 335 hmap_init(&map, 32, vec_hmap_hash, vec_hmap_keycmp, 336 &stdlib_strict_heap_allocator); 337 338 icc_parse_inst(&icc, aoc.input, aoc.input_size); 339 340 start = (struct vec2i) { 0, 0 }; 341 explore_map(&icc, &map, start, &tank); 342 343 dist = dijkstra_dist(&map, tank, NULL); 344 345 aoc.answer = aprintf("%lu", dist); 346 aoc.solution = "292"; 347 348 for (HMAP_ITER(&map, iter)) 349 free(iter.link->key._p); 350 hmap_deinit(&map); 351 icc_deinit(&icc); 352}