commit 744cb4c6f5e12f84d5a77d8eee69a60c81d53fee
parent 019fd07126c76913fdf62ee2bc1813e666ddf25c
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 26 Mar 2023 15:56:15 +0200
Add day 18
Diffstat:
28 files changed, 1403 insertions(+), 50 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -5,3 +5,4 @@ main
build
vgcore*
.gdb_history
+perf.data
diff --git a/.gitmodules b/.gitmodules
@@ -10,3 +10,9 @@
[submodule "lib/libhmap"]
path = lib/libhmap
url = git@sinitax.com:snx/libhmap
+[submodule "lib/liblist"]
+ path = lib/liblist
+ url = git@sinitax.com:snx/liblist
+[submodule "lib/libpq"]
+ path = lib/libpq
+ url = git@sinitax.com:snx/libpq
diff --git a/06/main.c b/06/main.c
@@ -1,7 +1,7 @@
#include "aoc.h"
-#include "dvec.h"
-#include "hmap.h"
#include "allocator.h"
+#include "hmap.h"
+#include "dvec_s.h"
#include "util.h"
#include <assert.h>
@@ -57,7 +57,6 @@ planets_init()
struct planet *parent, *child, **slot;
const char *pos, *end;
char buf[256], *sep;
- int rc;
hmap_init(&planets, 100, hmap_str_hash,
hmap_str_keycmp, &stdlib_heap_allocator);
@@ -75,8 +74,7 @@ planets_init()
child = planets_get(sep + 1);
if (!child) child = planets_add(sep + 1);
- slot = dvec_add_slot(&parent->children, &rc);
- if (rc) die("main: dvec_add_slot");
+ slot = dvec_add_slot(&parent->children);
*slot = child;
if (child->parent) die("main unexpected parent");
diff --git a/07/main.c b/07/main.c
@@ -1,7 +1,7 @@
-#include "allocator.h"
#include "aoc.h"
#include "icc.h"
#include "util.h"
+#include "allocator.h"
#include <assert.h>
#include <string.h>
diff --git a/10/main.c b/10/main.c
@@ -1,5 +1,5 @@
-#include "allocator.h"
#include "aoc.h"
+#include "allocator.h"
#include "util.h"
#include "hmap.h"
diff --git a/11/main.c b/11/main.c
@@ -1,5 +1,5 @@
-#include "allocator.h"
#include "aoc.h"
+#include "allocator.h"
#include "iccmp.h"
#include "hmap.h"
#include "util.h"
diff --git a/12/main.c b/12/main.c
@@ -1,6 +1,6 @@
#include "aoc.h"
#include "allocator.h"
-#include "dvec.h"
+#include "dvec_s.h"
#include "util.h"
#include "maxint.h"
@@ -26,7 +26,7 @@ moons_init(struct dvec *vec)
{
char *p, *tok, *val;
struct moon m, *slot;
- int i, rc;
+ int i;
m.vel = (struct vec3) { 0, 0, 0 };
dvec_init(vec, 100, sizeof(struct moon), &stdlib_strict_heap_allocator);
@@ -36,8 +36,7 @@ moons_init(struct dvec *vec)
val = tok;
for (i = 0; i < 3 && (val = strchr(val + 1, '=')); i++)
m.pos.axis[i] = (int) strtol(val + 1, NULL, 10);
- slot = dvec_add_slot(vec, &rc);
- assert(!rc);
+ slot = dvec_add_slot(vec);
memcpy(slot, &m, sizeof(struct moon));
tok = p + 1;
}
diff --git a/13/main.c b/13/main.c
@@ -1,5 +1,5 @@
-#include "allocator.h"
#include "aoc.h"
+#include "allocator.h"
#include "iccmp.h"
#include "hmap.h"
#include "maxint.h"
diff --git a/14/main.c b/14/main.c
@@ -1,8 +1,8 @@
-#include "allocator.h"
#include "aoc.h"
+#include "allocator.h"
#include "util.h"
#include "hmap.h"
-#include "dvec.h"
+#include "dvec_s.h"
#include <assert.h>
#include <stdbool.h>
@@ -53,7 +53,7 @@ parse_reactions(struct hmap *reactions)
assert(rc == 2);
if (sep) {
- slot = dvec_add_slot(&reaction->ingredients, NULL);
+ slot = dvec_add_slot(&reaction->ingredients);
memcpy(slot, &ingredient,
sizeof(struct ingredient));
} else {
@@ -119,7 +119,7 @@ calculate_ore(struct hmap *reactions, struct hmap *excess,
dvec_init(&reactants, sizeof(struct ingredient),
10, &stdlib_strict_heap_allocator);
- slot = dvec_add_slot(&reactants, NULL);
+ slot = dvec_add_slot(&reactants);
ingredient.amount = amount;
snprintf(ingredient.name, 8, "%s", name);
memcpy(slot, &ingredient, sizeof(struct ingredient));
@@ -137,7 +137,7 @@ calculate_ore(struct hmap *reactions, struct hmap *excess,
n = add_excess(excess, &result, reaction);
if (!n) continue;
- for (DVEC_ITER(&reaction->ingredients, &slot)) {
+ for (DVEC_ITER(&reaction->ingredients, slot)) {
aoc_debug("%lu %s needs %lu %s\n",
result.amount, result.name,
slot->amount * n, slot->name);
@@ -146,7 +146,7 @@ calculate_ore(struct hmap *reactions, struct hmap *excess,
} else {
snprintf(ingredient.name, 8, "%s", slot->name);
ingredient.amount = slot->amount * n;
- slot2 = dvec_add_slot(&reactants, NULL);
+ slot2 = dvec_add_slot(&reactants);
memcpy(slot2, &ingredient, sizeof(struct ingredient));
}
}
diff --git a/15/main.c b/15/main.c
@@ -1,6 +1,7 @@
+#include "aoc.h"
+#include "dvec_s.h"
#include "allocator.h"
#include "util.h"
-#include "aoc.h"
#include "iccmp.h"
#include "hmap.h"
#include "vec.h"
@@ -148,7 +149,7 @@ dijkstra_dist(struct hmap *map, struct vec2i start, const struct vec2i *end)
dvec_init(&outer, sizeof(struct vec2i),
10, &stdlib_strict_heap_allocator);
- vec = dvec_add_slot(&outer, NULL);
+ vec = dvec_add_slot(&outer);
vec2i_set(vec, &start);
key = memdup(vec, sizeof(struct vec2i));
@@ -180,7 +181,7 @@ dijkstra_dist(struct hmap *map, struct vec2i start, const struct vec2i *end)
if (!maxdist || dist > maxdist)
maxdist = dist;
- vec = dvec_add_slot(&outer, NULL);
+ vec = dvec_add_slot(&outer);
vec2i_set(vec, &npos);
key = memdup(&npos, sizeof(struct vec2i));
hmap_link_alloc(&seen, linkp,
@@ -214,7 +215,7 @@ explore_map(struct icc *icc, struct hmap *map,
dvec_init(&states, sizeof(struct state),
10, &stdlib_strict_heap_allocator);
- state = dvec_add_slot(&states, NULL);
+ state = dvec_add_slot(&states);
state->back = -1;
state->next = 1;
@@ -270,7 +271,7 @@ explore_map(struct icc *icc, struct hmap *map,
vec2i_set(tank, &npos);
case BLOCK_OPEN:
vec2i_set(&pos, &npos);
- state = dvec_add_slot(&states, NULL);
+ state = dvec_add_slot(&states);
state->back = rev[move_dir];
state->next = 1;
break;
diff --git a/16/main.c b/16/main.c
@@ -1,7 +1,7 @@
+#include "aoc.h"
#include "allocator.h"
#include "util.h"
-#include "aoc.h"
-#include "dvec.h"
+#include "dvec_s.h"
#include <assert.h>
#include <string.h>
@@ -19,7 +19,7 @@ parse_input(struct dvec *phases)
assert(sep != NULL);
for (c = aoc.input; c < sep; c++) {
- val = dvec_add_slot(phases, NULL);
+ val = dvec_add_slot(phases);
*val = *c - '0';
}
}
@@ -105,7 +105,7 @@ fft_dup(struct dvec *phases, size_t offset, size_t rounds, size_t dup)
dvec_clear(phases);
for (i = 0; i < 8; i++) {
- slot = dvec_add_slot(phases, NULL);
+ slot = dvec_add_slot(phases);
*slot = lut[rounds * lutlen + i];
}
@@ -171,7 +171,7 @@ part2(void)
answer[i] = 0;
aoc.answer = answer;
- aoc.solution = "";
+ aoc.solution = "73556504";
dvec_deinit(&phases);
}
diff --git a/17/main.c b/17/main.c
@@ -1,8 +1,9 @@
+#include "aoc.h"
#include "allocator.h"
#include "util.h"
-#include "aoc.h"
#include "iccmp.h"
#include "hmap.h"
+#include "dvec_s.h"
#include "vec.h"
#include <assert.h>
@@ -191,12 +192,12 @@ add_path(struct hmap *paths, struct path *path)
link = hmap_link_pos(paths, (struct hmap_key) {.p = &path->start});
if (*link) {
list = (*link)->value._p;
- memcpy(dvec_add_slot(list, NULL), path, sizeof(struct path));
+ memcpy(dvec_add_slot(list), path, sizeof(struct path));
} else {
key = memdup(&path->start, sizeof(struct vec2i));
dvec_alloc(&list, sizeof(struct path),
1, &stdlib_strict_heap_allocator);
- memcpy(dvec_add_slot(list, NULL), path, sizeof(struct path));
+ memcpy(dvec_add_slot(list), path, sizeof(struct path));
hmap_add(paths,
(struct hmap_key) {.p = key},
(struct hmap_val) {.p = list});
@@ -266,7 +267,7 @@ gen_insts(struct dvec *insts, struct hmap *paths,
found = false;
list = link->value._p;
- for (DVEC_ITER(list, &path)) {
+ for (DVEC_ITER(list, path)) {
if (vec2i_eql(&ppos, &path->end))
continue;
found = true;
@@ -290,14 +291,14 @@ gen_insts(struct dvec *insts, struct hmap *paths,
type = type == 'L' ? 'R' : 'L';
}
for (; cnt > 0; cnt--) {
- inst = dvec_add_slot(insts, NULL);
+ inst = dvec_add_slot(insts);
*inst = type;
}
dir = ndir;
cnt = (int) ABS(path->end.x - path->start.x)
+ (int) ABS(path->end.y - path->start.y);
- inst = dvec_add_slot(insts, NULL);
+ inst = dvec_add_slot(insts);
*inst = (char) -cnt;
}
}
@@ -309,7 +310,7 @@ insts_line(struct dvec *insts)
char *c;
str = NULL;
- for (DVEC_ITER(insts, &c)) {
+ for (DVEC_ITER(insts, c)) {
if (str) str = apprintf(str, ",");
if (*c < 0) {
str = apprintf(str, "%i", -*c);
@@ -331,28 +332,28 @@ gen_func(struct dvec *insts, struct dvec *main,
size_t i;
for (i = start; i < MIN(insts->len, start + len); i++) {
- inst = dvec_add_slot(cur, NULL);
+ inst = dvec_add_slot(cur);
*inst = *(char *)dvec_at(insts, i);
}
- inst = dvec_add_slot(main, NULL);
+ inst = dvec_add_slot(main);
*inst = cc;
while (1) {
if (f1 && i + f1->len <= insts->len
&& !memcmp(dvec_at(insts, i), f1->data, f1->len)) {
i += f1->len;
- inst = dvec_add_slot(main, NULL);
+ inst = dvec_add_slot(main);
*inst = c1;
} else if (f2 && i + f2->len <= insts->len
&& !memcmp(dvec_at(insts, i), f2->data, f2->len)) {
i += f2->len;
- inst = dvec_add_slot(main, NULL);
+ inst = dvec_add_slot(main);
*inst = c2;
} else if (i + cur->len <= insts->len
&& !memcmp(dvec_at(insts, i), cur->data, cur->len)) {
i += cur->len;
- inst = dvec_add_slot(main, NULL);
+ inst = dvec_add_slot(main);
*inst = cc;
} else {
break;
diff --git a/18/info.mk b/18/info.mk
@@ -0,0 +1,4 @@
+18_SRC = 18/main.c common/main.c common/aoc.c common/util.c
+18_SRC += lib/libdvec/build/libdvec.a lib/liballoc/build/liballoc.a
+18_SRC += lib/libhmap/build/libhmap.a lib/liblist/build/liblist.a
+18_HDR = common/aoc.h common/util.h
diff --git a/18/input b/18/input
@@ -0,0 +1,82 @@
+#################################################################################
+#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
+#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
+#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
+#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
+#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
+#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
+#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
+#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
+#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
+#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
+#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
+###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
+#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
+#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
+#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
+#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
+#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
+#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
+#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
+#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
+#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
+###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
+#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
+#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
+#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
+###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
+#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
+#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
+#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
+#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
+#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
+#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
+#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
+#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
+#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
+#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
+#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
+#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
+#.......................#.....#.............#.#.............#.....#...........#.#
+#######################################.@.#######################################
+#...............#.....#.....#.............#.........................D.......#..u#
+#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
+#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
+#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
+#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
+#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
+#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
+#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
+#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
+###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
+#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
+#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
+#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
+#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
+#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
+#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
+#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
+###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
+#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
+#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
+#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
+#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
+#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
+#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
+#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
+###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
+#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
+#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
+#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
+#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
+#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
+#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
+#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
+#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
+#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
+###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
+#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
+#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
+#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
+#################################################################################
+
diff --git a/18/main.c b/18/main.c
@@ -0,0 +1,898 @@
+#include "aoc.h"
+#include "allocator.h"
+#include "dvec_s.h"
+#include "hmap.h"
+#include "util.h"
+#include "list.h"
+#include "vec.h"
+
+#include <signal.h>
+#include <assert.h>
+#include <ctype.h>
+#include <stdbool.h>
+#include <stdint.h>
+
+struct state {
+ struct vec2i pos;
+ uint32_t acquired;
+ size_t dist;
+ struct list_link link;
+};
+
+struct state_multi {
+ struct vec2i pos[4];
+ uint32_t acquired;
+ size_t dist;
+ struct list_link link;
+};
+
+struct prog {
+ uint32_t acquired;
+ size_t dist;
+};
+
+struct path {
+ uint32_t required;
+ size_t dist;
+};
+
+struct keypath {
+ uint32_t required;
+ size_t dist;
+ struct vec2i pos;
+ uint32_t keymask;
+ char key;
+};
+
+struct node {
+ struct dvec edges;
+ int key;
+};
+
+const struct vec2i dirs[] = {
+ { 0, -1 },
+ { 1, 0 },
+ { 0, 1 },
+ { -1, 0 },
+};
+
+static inline bool
+bit_subset(uint32_t a, uint32_t b)
+{
+ return (a & b) == a;
+}
+
+static inline bool
+bit_proper_subset(uint32_t a, uint32_t b)
+{
+ return bit_subset(a, b) && (a < b);
+}
+
+static inline bool
+bit_superset(uint32_t a, uint32_t b)
+{
+ return (a & b) == b;
+}
+
+static inline bool
+bit_proper_superset(uint32_t a, uint32_t b)
+{
+ return bit_superset(a, b) && (a > b);
+}
+
+bool
+vec2i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ const struct vec2i *v1 = k1.p, *v2 = k2.p;
+
+ return vec2i_eql(v1, v2);
+}
+
+uint32_t
+vec2i_hmap_hash(struct hmap_key key)
+{
+ const struct vec2i *v = key.p;
+
+ return (uint32_t) v->x + (uint32_t) v->y * 80;
+}
+
+bool
+vec2i_multi_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ const struct vec2i *v1 = k1.p, *v2 = k2.p;
+ size_t i;
+
+ for (i = 0; i < 4; i++) {
+ if (!vec2i_eql(&v1[i], &v2[i]))
+ return false;
+ }
+
+ return true;
+}
+
+uint32_t
+vec2i_multi_hmap_hash(struct hmap_key key)
+{
+ const struct vec2i *v = key.p;
+ uint32_t hash;
+ size_t i;
+
+ hash = 0;
+ for (i = 0; i < 4; i++)
+ hash += (uint32_t) v[i].x + (uint32_t) v[i].y * 80;
+
+ return hash;
+}
+
+void
+print_map(const struct hmap *map, struct hmap *distmap,
+ const struct vec2i *start, uint32_t acquired)
+{
+ struct hmap_iter iter;
+ struct hmap_link *link;
+ struct vec2i min, max;
+ struct vec2i pos;
+ uint32_t mask;
+ char c;
+
+ vec2i_set(&min, start);
+ vec2i_set(&max, start);
+ for (HMAP_ITER(map, &iter)) {
+ vec2i_set(&pos, iter.link->key._p);
+ if (pos.x < min.x) min.x = pos.x;
+ if (pos.y < min.y) min.y = pos.y;
+ if (pos.x > max.x) max.x = pos.x;
+ if (pos.y > max.y) max.y = pos.y;
+ }
+
+ aoc_debug("+");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++)
+ aoc_debug("-");
+ aoc_debug("+\n");
+
+ for (pos.y = min.y; pos.y <= max.y; pos.y++) {
+ aoc_debug("|");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++) {
+ if (vec2i_eql(&pos, start)) {
+ aoc_debug("\x1b[5m@\x1b[0m");
+ continue;
+ }
+
+ link = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (link) {
+ c = link->value.c;
+ if (isalpha(c)) {
+ mask = islower(c) ? 1 << (c - 'a')
+ : 1 << (c - 'A');
+ if (acquired & mask) {
+ aoc_debug("\x1b[90m%c\x1b[0m", c);
+ } else {
+ aoc_debug("%c", c);
+ }
+ continue;
+ }
+
+ link = hmap_get(distmap,
+ (struct hmap_key) {.p = &pos});
+ if (link) {
+ aoc_debug(" ");
+ } else {
+ aoc_debug("%c", c);
+ }
+ } else {
+ aoc_debug(" ");
+ }
+ }
+ aoc_debug("|\n");
+ }
+
+ aoc_debug("+");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++)
+ aoc_debug("-");
+ aoc_debug("+\n");
+}
+
+void
+parse_input(struct hmap *map, struct vec2i *start, size_t *keycnt)
+{
+ const char *lpos, *lend;
+ const char *c;
+ char line[256];
+ struct vec2i pos;
+ void *key;
+
+ *keycnt = 0;
+
+ lpos = aoc.input;
+ lend = aoc.input + aoc.input_size;
+ vec2i_setv(&pos, 0, 0);
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ pos.x = 0;
+ for (c = line; *c; c++) {
+ key = memdup(&pos, sizeof(struct vec2i));
+ hmap_add(map, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.c = *c});
+ if (islower(*c)) *keycnt += 1;
+ if (*c == '@') vec2i_set(start, &pos);
+ pos.x += 1;
+ }
+ pos.y += 1;
+ }
+}
+
+bool
+update_paths(struct dvec *paths, size_t dist, uint32_t required)
+{
+ struct path *path;
+
+ for (DVEC_ITER(paths, path)) {
+ if (dist < path->dist) {
+ if (bit_subset(required, path->required)) {
+ path->required = required;
+ path->dist = dist;
+ return true;
+ }
+ } else if (dist == path->dist) {
+ if (bit_proper_subset(required, path->required)) {
+ path->required = required;
+ return true;
+ }
+ } else {
+ if (bit_superset(required, path->required))
+ return false;
+ }
+ }
+
+ path = dvec_add_slot(paths);
+ path->dist = dist;
+ path->required = required;
+
+ return true;
+}
+
+void
+add_node(struct hmap *graph, const struct hmap *map,
+ const struct vec2i *start, int key)
+{
+ struct hmap_iter iter;
+ struct dvec active, active_next;
+ struct state state, *cstate, *nstate;
+ struct dvec *paths;
+ struct path *path;
+ struct keypath *keypath;
+ struct hmap_link *link, **linkp;
+ struct hmap distmap;
+ struct node *node;
+ struct vec2i *pos;
+ size_t i;
+ char c;
+
+ /*
+ * - dijkstra from start pos
+ * - when we encounter a door, must have acquired corresponding key
+ * - distmap resolves to dvec of paths
+ * - only save new distance if less than all known paths
+ * and/or path requires a subset of keys
+ *
+ * - loop over keys in generated distance map
+ * - add keys as edges to node
+ */
+
+ dvec_init(&active, sizeof(struct state), 10,
+ &stdlib_strict_heap_allocator);
+ dvec_init(&active_next, sizeof(struct state), 10,
+ &stdlib_strict_heap_allocator);
+ hmap_init(&distmap, 64, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ cstate = dvec_add_slot(&active_next);
+ vec2i_set(&cstate->pos, start);
+ cstate->acquired = 0;
+ cstate->dist = 0;
+
+ pos = memdup(start, sizeof(struct vec2i));
+ dvec_alloc(&paths, sizeof(struct path), 1,
+ &stdlib_strict_heap_allocator);
+ path = dvec_add_slot(paths);
+ path->dist = 0;
+ path->required = 0;
+ hmap_add(&distmap, (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = paths});
+
+ while (!dvec_empty(&active_next)) {
+ dvec_swap(&active, &active_next);
+ dvec_clear(&active_next);
+
+ for (DVEC_ITER(&active, cstate)) {
+ for (i = 0; i < ARRLEN(dirs); i++) {
+ vec2i_add(&state.pos, &cstate->pos, &dirs[i]);
+
+ link = hmap_get(map,
+ (struct hmap_key) {.p = &state.pos});
+ assert(link != NULL);
+ c = link->value.c;
+ if (c == '#') continue;
+
+ state.dist = cstate->dist + 1;
+ state.acquired = cstate->acquired;
+ if (isupper(c)) /* need key for door */
+ state.acquired |= (1U << (c - 'A'));
+
+ linkp = hmap_link_pos(&distmap,
+ (struct hmap_key) {.p = &state.pos});
+ if (*linkp) {
+ paths = (*linkp)->value._p;
+ } else {
+ pos = memdup(&state.pos, sizeof(struct vec2i));
+ dvec_alloc(&paths, sizeof(struct path),
+ 1, &stdlib_strict_heap_allocator);
+ hmap_link_alloc(&distmap, linkp,
+ (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = paths});
+ }
+
+ if (update_paths(paths, state.dist, state.acquired)) {
+ nstate = dvec_add_slot(&active_next);
+ memcpy(nstate, &state, sizeof(struct state));
+ }
+ }
+ }
+ }
+
+ node = malloc(sizeof(struct node));
+ node->key = key;
+ dvec_init(&node->edges, sizeof(struct keypath), 1,
+ &stdlib_strict_heap_allocator);
+ for (HMAP_ITER(map, &iter)) {
+ c = iter.link->value.c;
+ if (vec2i_eql(iter.link->key.p, start))
+ continue;
+ if (islower(c)) {
+ link = hmap_get(&distmap, iter.link->key);
+ if (!link) continue;
+ pos = iter.link->key._p;
+ for (DVEC_ITER(link->value.p, path)) {
+ keypath = dvec_add_slot(&node->edges);
+ keypath->key = c;
+ keypath->keymask = 1U << (c - 'a');
+ keypath->dist = path->dist;
+ keypath->required = path->required;
+ vec2i_set(&keypath->pos, iter.link->key.p);
+ }
+ }
+ }
+ pos = memdup(start, sizeof(struct vec2i));
+ hmap_add(graph, (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = node});
+
+ if (aoc.debug == 2) {
+ aoc_debug("add_node: %li %li\n", start->x, start->y);
+ print_map(map, &distmap, start, 0);
+ for (DVEC_ITER(&node->edges, keypath)) {
+ aoc_debug("path: %c %3lu %032b\n", keypath->key,
+ keypath->dist, keypath->required);
+ }
+ aoc_debug("\n");
+ }
+
+ for (HMAP_ITER(&distmap, &iter)) {
+ free(iter.link->key._p);
+ dvec_free(iter.link->value._p);
+ }
+ hmap_deinit(&distmap);
+ dvec_deinit(&active_next);
+ dvec_deinit(&active);
+}
+
+void
+gen_graph(struct hmap *graph, const struct hmap *map,
+ const struct vec2i *start, size_t keycnt)
+{
+ struct hmap_iter iter;
+
+ add_node(graph, map, start, -1);
+ for (HMAP_ITER(map, &iter)) {
+ if (islower(iter.link->value.c)) {
+ add_node(graph, map, iter.link->key.p,
+ iter.link->value.c - 'a');
+ }
+ }
+}
+
+void
+sort_edges(struct dvec *edges)
+{
+ struct keypath tmp, *a, *b;
+ size_t i, k;
+
+ if (!edges->len) return;
+ for (i = 0; i < edges->len - 1; i++) {
+ for (k = 0; k < edges->len - 1; k++) {
+ a = dvec_at(edges, k);
+ b = dvec_at(edges, k + 1);
+ if (a->dist > b->dist) {
+ memcpy(&tmp, b, sizeof(struct keypath));
+ memcpy(b, a, sizeof(struct keypath));
+ memcpy(a, &tmp, sizeof(struct keypath));
+ }
+ }
+ }
+}
+
+struct prog *
+update_progs(struct dvec *progs, size_t dist, uint32_t acquired)
+{
+ struct prog *prog;
+
+ for (DVEC_ITER(progs, prog)) {
+ if (bit_superset(acquired, prog->acquired)) {
+ if (dist < prog->dist) {
+ prog->acquired = acquired;
+ prog->dist = dist;
+ return prog;
+ } else if (dist == prog->dist) {
+ if (acquired > prog->acquired) {
+ prog->acquired = acquired;
+ return prog;
+ } else {
+ return NULL;
+ }
+ }
+ }
+ }
+
+ prog = dvec_add_slot(progs);
+ prog->dist = dist;
+ prog->acquired = acquired;
+
+ return prog;
+}
+
+struct state *
+state_alloc(const struct vec2i *pos, size_t dist, uint32_t acquired)
+{
+ struct state *state;
+
+ state = malloc(sizeof(struct state));
+ vec2i_set(&state->pos, pos);
+ state->dist = dist;
+ state->acquired = acquired;
+ state->link = LIST_LINK_INIT;
+
+ return state;
+}
+
+bool
+state_dist_ordering(struct list_link *_a, struct list_link *_b)
+{
+ struct state *a, *b;
+
+ a = LIST_UPCAST(_a, struct state, link);
+ b = LIST_UPCAST(_b, struct state, link);
+
+ return a->dist < b->dist;
+}
+
+void
+add_keys(struct list *active, struct hmap *graph,
+ struct hmap *distmap, struct state *cstate, size_t keycnt)
+{
+ struct hmap_link *link, **linkp;
+ struct state state, *nstate;
+ struct keypath *keypath;
+ struct dvec *progs;
+ struct node *node;
+ struct prog *prog;
+ struct vec2i *pos;
+
+ link = hmap_get(graph, (struct hmap_key) {.p = &cstate->pos});
+ assert(link != NULL);
+ node = link->value._p;
+
+ for (DVEC_ITER(&node->edges, keypath)) {
+ if (cstate->acquired & keypath->keymask)
+ continue;
+
+ if (!bit_superset(cstate->acquired, keypath->required))
+ continue;
+
+ vec2i_set(&state.pos, &keypath->pos);
+ state.dist = cstate->dist + keypath->dist;
+ state.acquired = cstate->acquired | keypath->keymask;
+
+ linkp = hmap_link_pos(distmap, (struct hmap_key) {.p = &state.pos});
+ if (*linkp) {
+ progs = (*linkp)->value._p;
+ } else {
+ pos = memdup(&state.pos, sizeof(struct vec2i));
+ dvec_alloc(&progs, sizeof(struct prog), 1,
+ &stdlib_strict_heap_allocator);
+ hmap_link_alloc(distmap, linkp,
+ (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = progs});
+ }
+
+ if ((prog = update_progs(progs, state.dist, state.acquired))) {
+ aoc_debug("updated prog %i %i %032b %032b\n",
+ prog->dist, state.dist, prog->acquired, state.acquired);
+ nstate = state_alloc(&state.pos, state.dist, state.acquired);
+ list_insert_sorted(active, &nstate->link, false,
+ state_dist_ordering);
+ }
+ }
+}
+
+size_t
+min_dist_all_keys(struct hmap *graph, const struct vec2i *start, size_t keycnt)
+{
+ struct list_link *list_link;
+ struct hmap_link *hmap_link;
+ struct hmap_iter iter;
+ struct hmap distmap;
+ struct list active;
+ struct state *cstate;
+ struct dvec *progs;
+ struct prog *prog;
+ struct node *node;
+ struct vec2i *pos;
+
+ /*
+ * - dijkstra from starting node
+ * - only move over edges that we collected keys for
+ * - distmap resolves to dvec of progs
+ * - only save new distance if less than all known progs
+ * and/or we have a superset of previous keys
+ * - if we reach key and have, save mindist
+ */
+
+ list_init(&active);
+ hmap_init(&distmap, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ cstate = state_alloc(start, 0, 0);
+ list_push_back(&active, &cstate->link);
+
+ pos = memdup(start, sizeof(struct vec2i));
+ dvec_alloc(&progs, sizeof(struct prog), 1,
+ &stdlib_strict_heap_allocator);
+ prog = dvec_add_slot(progs);
+ prog->acquired = 0;
+ prog->dist = 0;
+ hmap_add(&distmap, (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = progs});
+
+ for (HMAP_ITER(graph, &iter)) {
+ node = iter.link->value._p;
+ sort_edges(&node->edges);
+ }
+
+ while (!list_empty(&active)) {
+ list_link = list_front(&active);
+ cstate = LIST_UPCAST(list_link, struct state, link);
+ if (cstate->acquired == (1U << keycnt) - 1)
+ return cstate->dist;
+
+ list_link_pop(list_link);
+
+ hmap_link = hmap_get(&distmap, (struct hmap_key) {.p = &cstate->pos});
+ assert(link != NULL);
+ for (DVEC_ITER(hmap_link->value.p, prog)) {
+ if (prog->dist < cstate->dist) {
+ if (bit_superset(prog->acquired,
+ cstate->acquired))
+ break;
+ } else if (prog->dist == cstate->dist) {
+ if (bit_proper_superset(prog->acquired,
+ cstate->acquired))
+ break;
+ }
+ }
+ if (prog) {
+ free(cstate);
+ continue;
+ }
+
+ aoc_debug("active %02li %02li %032b %lu\n",
+ cstate->pos.x, cstate->pos.y,
+ cstate->acquired, cstate->dist);
+
+ add_keys(&active, graph, &distmap, cstate, keycnt);
+
+ free(cstate);
+ }
+
+ for (HMAP_ITER(&distmap, &iter)) {
+ free(iter.link->key._p);
+ dvec_free(iter.link->value._p);
+ }
+ hmap_deinit(&distmap);
+ list_free_items(&active, free, LIST_OFFSET(struct state, link));
+
+ return 0;
+}
+
+void
+write_map(struct hmap *map, ssize_t x, ssize_t y, char c)
+{
+ struct hmap_link *hmap_link;
+ struct vec2i pos;
+
+ vec2i_setv(&pos, x, y);
+ hmap_link = hmap_get(map, (struct hmap_key) {.p = &pos});
+ assert(hmap_link);
+ hmap_link->value.c = c;
+}
+
+struct state_multi *
+state_multi_alloc(const struct vec2i *pos, size_t dist, uint32_t acquired)
+{
+ struct state_multi *state;
+
+ state = malloc(sizeof(struct state_multi));
+ memcpy(state->pos, pos, 4 * sizeof(struct vec2i));
+ state->dist = dist;
+ state->acquired = acquired;
+ state->link = LIST_LINK_INIT;
+
+ return state;
+}
+
+bool
+state_multi_dist_ordering(struct list_link *_a, struct list_link *_b)
+{
+ struct state_multi *a, *b;
+
+ a = LIST_UPCAST(_a, struct state_multi, link);
+ b = LIST_UPCAST(_b, struct state_multi, link);
+
+ return a->dist < b->dist;
+}
+
+void
+add_keys_multi(struct list *active, struct hmap *graphs,
+ struct hmap *distmap, struct state_multi *cstate, size_t keycnt)
+{
+ struct hmap_link *link, **linkp;
+ struct state_multi state, *nstate;
+ struct keypath *keypath;
+ struct dvec *progs;
+ struct node *node;
+ struct prog *prog;
+ struct vec2i *pos;
+ size_t i;
+
+ for (i = 0; i < 4; i++) {
+ link = hmap_get(&graphs[i], (struct hmap_key) {.p = &cstate->pos[i]});
+ assert(link != NULL);
+ node = link->value._p;
+
+ for (DVEC_ITER(&node->edges, keypath)) {
+ if (cstate->acquired & keypath->keymask)
+ continue;
+
+ if (!bit_subset(keypath->required, cstate->acquired))
+ continue;
+
+ memcpy(state.pos, cstate->pos, 4 * sizeof(struct vec2i));
+ vec2i_set(&state.pos[i], &keypath->pos);
+ state.dist = cstate->dist + keypath->dist;
+ state.acquired = cstate->acquired | keypath->keymask;
+
+ linkp = hmap_link_pos(distmap, (struct hmap_key) {.p = state.pos});
+ if (*linkp) {
+ aoc_debug("old\n");
+ progs = (*linkp)->value._p;
+ } else {
+ pos = memdup(state.pos, sizeof(struct vec2i) * 4);
+ dvec_alloc(&progs, sizeof(struct prog), 1,
+ &stdlib_strict_heap_allocator);
+ hmap_link_alloc(distmap, linkp,
+ (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = progs});
+ }
+
+ if ((prog = update_progs(progs, state.dist, state.acquired))) {
+ aoc_debug("update prog %li,%li %li,%li %li,%li %li,%li "
+ "%i %i %032b %032b\n",
+ state.pos[0].x, state.pos[0].y,
+ state.pos[1].x, state.pos[1].y,
+ state.pos[2].x, state.pos[2].y,
+ state.pos[3].x, state.pos[3].y,
+ prog->dist, state.dist,
+ prog->acquired, state.acquired);
+ nstate = state_multi_alloc(state.pos, state.dist, state.acquired);
+ list_insert_sorted(active, &nstate->link,
+ false, state_multi_dist_ordering);
+ }
+ }
+ }
+}
+
+size_t
+min_dist_all_keys_multi(struct hmap *graphs, const struct vec2i *starts, size_t keycnt)
+{
+ struct list_link *list_link;
+ struct hmap_link *hmap_link;
+ struct hmap_iter hmap_iter;
+ struct hmap distmap;
+ struct list active;
+ struct state_multi *cstate;
+ struct dvec *progs;
+ struct prog *prog;
+ struct node *node;
+ struct vec2i *pos;
+ size_t i;
+
+ /*
+ * - dijkstra from starting node
+ * - only move over edges that we collected keys for
+ * - distmap resolves to dvec of progs
+ * - only save new distance if less than all known progs
+ * and/or we have a superset of previous keys
+ * - if we reach key and have, save mindist
+ */
+
+ list_init(&active);
+ hmap_init(&distmap, 256, vec2i_multi_hmap_hash, vec2i_multi_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ cstate = state_multi_alloc(starts, 0, 0);
+ list_push_back(&active, &cstate->link);
+
+ pos = memdup(starts, sizeof(struct vec2i) * 4);
+ dvec_alloc(&progs, sizeof(struct prog), 1,
+ &stdlib_strict_heap_allocator);
+ prog = dvec_add_slot(progs);
+ prog->acquired = 0;
+ prog->dist = 0;
+ hmap_add(&distmap, (struct hmap_key) {.p = pos},
+ (struct hmap_val) {.p = progs});
+
+ for (i = 0; i < 4; i++) {
+ for (HMAP_ITER(&graphs[i], &hmap_iter)) {
+ node = hmap_iter.link->value._p;
+ sort_edges(&node->edges);
+ }
+ }
+
+ while (!list_empty(&active)) {
+ list_link = list_front(&active);
+ cstate = LIST_UPCAST(list_link, struct state_multi, link);
+ if (cstate->acquired == (1U << keycnt) - 1)
+ return cstate->dist;
+
+ list_link_pop(list_link);
+
+ hmap_link = hmap_get(&distmap, (struct hmap_key) {.p = cstate->pos});
+ assert(hmap_link != NULL);
+ for (DVEC_ITER(hmap_link->value.p, prog)) {
+ if (prog->dist < cstate->dist) {
+ if (bit_superset(prog->acquired,
+ cstate->acquired))
+ break;
+ } else if (prog->dist == cstate->dist) {
+ if (bit_proper_superset(prog->acquired,
+ cstate->acquired))
+ break;
+ }
+ }
+ if (prog) {
+ free(cstate);
+ continue;
+ }
+
+ aoc_debug("active %li,%li %li,%li %li,%li %li,%li %032b %li\n",
+ cstate->pos[0].x, cstate->pos[0].y,
+ cstate->pos[1].x, cstate->pos[1].y,
+ cstate->pos[2].x, cstate->pos[2].y,
+ cstate->pos[3].x, cstate->pos[3].y,
+ cstate->acquired, cstate->dist);
+
+ add_keys_multi(&active, graphs, &distmap, cstate, keycnt);
+
+ free(cstate);
+ }
+
+ for (HMAP_ITER(&distmap, &hmap_iter)) {
+ free(hmap_iter.link->key._p);
+ dvec_free(hmap_iter.link->value._p);
+ }
+ hmap_deinit(&distmap);
+ list_free_items(&active, free, LIST_OFFSET(struct state_multi, link));
+
+ return 0;
+}
+
+void
+part1(void)
+{
+ struct hmap_iter iter;
+ struct hmap map;
+ struct hmap graph;
+ struct vec2i start;
+ struct node *node;
+ size_t keycnt;
+ size_t answer;
+
+ signal(SIGUSR1, exit);
+
+ hmap_init(&map, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ hmap_init(&graph, 32, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ parse_input(&map, &start, &keycnt);
+
+ gen_graph(&graph, &map, &start, keycnt);
+
+ answer = min_dist_all_keys(&graph, &start, keycnt);
+ aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "5402";
+
+ for (HMAP_ITER(&graph, &iter)) {
+ free(iter.link->key._p);
+ node = iter.link->value._p;
+ dvec_deinit(&node->edges);
+ free(node);
+ }
+ hmap_deinit(&graph);
+
+ for (HMAP_ITER(&map, &iter)) {
+ free(iter.link->key._p);
+ }
+ hmap_deinit(&map);
+}
+
+void
+part2(void)
+{
+ struct hmap_iter hmap_iter;
+ struct hmap map;
+ struct hmap graphs[4];
+ struct vec2i center;
+ struct vec2i starts[4];
+ struct node *node;
+ size_t keycnt;
+ size_t answer;
+ size_t i;
+
+ signal(SIGUSR1, exit);
+
+ hmap_init(&map, 256, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ parse_input(&map, ¢er, &keycnt);
+
+ write_map(&map, center.x - 1, center.y, '#');
+ write_map(&map, center.x + 1, center.y, '#');
+ write_map(&map, center.x, center.y - 1, '#');
+ write_map(&map, center.x, center.y + 1, '#');
+ write_map(&map, center.x, center.y, '#');
+
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&starts[i], ¢er, &dirs[i]);
+ vec2i_add(&starts[i], &starts[i], &dirs[(i+1)%4]);
+ hmap_init(&graphs[i], 32, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ gen_graph(&graphs[i], &map, &starts[i], keycnt);
+ }
+
+ answer = min_dist_all_keys_multi(graphs, starts, keycnt);
+ aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "2138";
+
+ for (i = 0; i < 4; i++) {
+ for (HMAP_ITER(&graphs[i], &hmap_iter)) {
+ free(hmap_iter.link->key._p);
+ node = hmap_iter.link->value._p;
+ dvec_deinit(&node->edges);
+ free(node);
+ }
+ hmap_deinit(&graphs[i]);
+ }
+
+ for (HMAP_ITER(&map, &hmap_iter)) {
+ free(hmap_iter.link->key._p);
+ }
+ hmap_deinit(&map);
+}
diff --git a/18/part1 b/18/part1
@@ -0,0 +1,117 @@
+--- Day 18: Many-Worlds Interpretation ---
+
+As you approach Neptune, a planetary security system detects you and activates a giant tractor beam
+on Triton! You have no choice but to land.
+
+A scan of the local area reveals only one interesting feature: a massive underground vault. You
+generate a map of the tunnels (your puzzle input). The tunnels are too narrow to move diagonally.
+
+Only one entrance (marked @) is present among the open passages (marked .) and stone walls (#), but
+you also detect an assortment of keys (shown as lowercase letters) and doors (shown as uppercase
+letters). Keys of a given letter open the door of the same letter: a opens A, b opens B, and so on.
+You aren't sure which key you need to disable the tractor beam, so you'll need to collect all of
+them.
+
+For example, suppose you have the following map:
+
+#########
+#b.A.@.a#
+#########
+
+Starting from the entrance (@), you can only access a large door (A) and a key (a). Moving toward
+the door doesn't help you, but you can move 2 steps to collect the key, unlocking A in the process:
+
+#########
+#b.....@#
+#########
+
+Then, you can move 6 steps to collect the only other key, b:
+
+#########
+#@......#
+#########
+
+So, collecting every key took a total of 8 steps.
+
+Here is a larger example:
+
+########################
+#f.D.E.e.C.b.A.@.a.B.c.#
+######################.#
+#d.....................#
+########################
+
+The only reasonable move is to take key a and unlock door A:
+
+########################
+#f.D.E.e.C.b.....@.B.c.#
+######################.#
+#d.....................#
+########################
+
+Then, do the same with key b:
+
+########################
+#f.D.E.e.C.@.........c.#
+######################.#
+#d.....................#
+########################
+
+...and the same with key c:
+
+########################
+#f.D.E.e.............@.#
+######################.#
+#d.....................#
+########################
+
+Now, you have a choice between keys d and e. While key e is closer, collecting it now would be
+slower in the long run than collecting key d first, so that's the best choice:
+
+########################
+#f...E.e...............#
+######################.#
+#@.....................#
+########################
+
+Finally, collect key e to unlock door E, then collect key f, taking a grand total of 86 steps.
+
+Here are a few more examples:
+
+
+ - ########################
+#...............b.C.D.f#
+#.######################
+#.....@.a.B.c.d.A.e.F.g#
+########################
+
+Shortest path is 132 steps: b, a, c, d, f, e, g
+
+
+ - #################
+#i.G..c...e..H.p#
+########.########
+#j.A..b...f..D.o#
+########@########
+#k.E..a...g..B.n#
+########.########
+#l.F..d...h..C.m#
+#################
+
+Shortest paths are 136 steps;one is: a, f, b, j, g, n, h, d, l, o, e, p, c, i, k, m
+
+
+ - ########################
+#@..............ac.GI.b#
+###d#e#f################
+###A#B#C################
+###g#h#i################
+########################
+
+Shortest paths are 81 steps; one is: a, c, f, i, d, g, b, e, h
+
+
+
+How many steps is the shortest path that collects all of the keys?
+
+
diff --git a/18/part2 b/18/part2
@@ -0,0 +1,184 @@
+--- Part Two ---
+
+You arrive at the vault only to discover that there is not one vault, but four - each with its own
+entrance.
+
+On your map, find the area in the middle that looks like this:
+
+...
+.@.
+...
+
+Update your map to instead use the correct data:
+
+@#@
+###
+@#@
+
+This change will split your map into four separate sections, each with its own entrance:
+
+####### #######
+#a.#Cd# #a.#Cd#
+##...## ##@#@##
+##.@.## --> #######
+##...## ##@#@##
+#cB#Ab# #cB#Ab#
+####### #######
+
+Because some of the keys are for doors in other vaults, it would take much too long to collect all
+of the keys by yourself. Instead, you deploy four remote-controlled robots. Each starts at one of
+the entrances (@).
+
+Your goal is still to collect all of the keys in the fewest steps, but now, each robot has its own
+position and can move independently. You can only remotely control a single robot at a time.
+Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key
+or door is found.
+
+For example, in the map above, the top-left robot first collects key a, unlocking door A in the
+bottom-right vault:
+
+#######
+#@.#Cd#
+##.#@##
+#######
+##@#@##
+#cB#.b#
+#######
+
+Then, the bottom-right robot collects key b, unlocking door B in the bottom-left vault:
+
+#######
+#@.#Cd#
+##.#@##
+#######
+##@#.##
+#c.#.@#
+#######
+
+Then, the bottom-left robot collects key c:
+
+#######
+#@.#.d#
+##.#@##
+#######
+##.#.##
+#@.#.@#
+#######
+
+Finally, the top-right robot collects key d:
+
+#######
+#@.#.@#
+##.#.##
+#######
+##.#.##
+#@.#.@#
+#######
+
+In this example, it only took 8 steps to collect all of the keys.
+
+Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple
+keys to be collected:
+
+###############
+#d.ABC.#.....a#
+######@#@######
+###############
+######@#@######
+#b.....#.....c#
+###############
+
+First, the top-right, bottom-left, and bottom-right robots take turns collecting keys a, b, and c, a
+total of 6 + 6 + 6 = 18 steps. Then, the top-left robot can access key d, spending another 6 steps;
+collecting all of the keys here takes a minimum of 24 steps.
+
+Here's a more complex example:
+
+#############
+#DcBa.#.GhKl#
+#.###@#@#I###
+#e#d#####j#k#
+###C#@#@###J#
+#fEbA.#.FgHi#
+#############
+
+
+ - Top-left robot collects key a.
+
+ - Bottom-left robot collects key b.
+
+ - Top-left robot collects key c.
+
+ - Bottom-left robot collects key d.
+
+ - Top-left robot collects key e.
+
+ - Bottom-left robot collects key f.
+
+ - Bottom-right robot collects key g.
+
+ - Top-right robot collects key h.
+
+ - Bottom-right robot collects key i.
+
+ - Top-right robot collects key j.
+
+ - Bottom-right robot collects key k.
+
+ - Top-right robot collects key l.
+
+
+In the above example, the fewest steps to collect all of the keys is 32.
+
+Here's an example with more choices:
+
+#############
+#g#f.D#..h#l#
+#F###e#E###.#
+#dCba@#@BcIJ#
+#############
+#nK.L@#@G...#
+#M###N#H###.#
+#o#m..#i#jk.#
+#############
+
+One solution with the fewest steps is:
+
+
+ - Top-left robot collects key e.
+
+ - Top-right robot collects key h.
+
+ - Bottom-right robot collects key i.
+
+ - Top-left robot collects key a.
+
+ - Top-left robot collects key b.
+
+ - Top-right robot collects key c.
+
+ - Top-left robot collects key d.
+
+ - Top-left robot collects key f.
+
+ - Top-left robot collects key g.
+
+ - Bottom-right robot collects key k.
+
+ - Bottom-right robot collects key j.
+
+ - Top-right robot collects key l.
+
+ - Bottom-left robot collects key n.
+
+ - Bottom-left robot collects key m.
+
+ - Bottom-left robot collects key o.
+
+
+This example requires at least 72 steps to collect all keys.
+
+After updating your map and using the remote-controlled robots, what is the fewest steps necessary
+to collect all of the keys?
+
+
diff --git a/18/test1 b/18/test1
@@ -0,0 +1,6 @@
+########################
+#@..............ac.GI.b#
+###d#e#f################
+###A#B#C################
+###g#h#i################
+########################
diff --git a/18/test2 b/18/test2
@@ -0,0 +1,5 @@
+########################
+#f.D.E.e.C.b.A.@.a.B.c.#
+######################.#
+#d.....................#
+########################
diff --git a/18/test3 b/18/test3
@@ -0,0 +1,7 @@
+#######
+#a.#Cd#
+##...##
+##.@.##
+##...##
+#cB#Ab#
+#######
diff --git a/Makefile b/Makefile
@@ -1,14 +1,21 @@
CFLAGS = -I lib/libdvec/include -I lib/libhmap/include
CFLAGS += -I lib/libmaxint/include -I lib/liballoc/include
+CFLAGS += -I lib/liblist/include
+
CFLAGS += -Wunused-variable -Wunused-function -Wformat
CFLAGS += -Wconversion -Wsign-compare
CFLAGS += -I common -g -Werror
ifeq "$(DEBUG)" "1"
+CFLAGS += -DLIBDVEC_ASSERT_ARGS -DLIBDVEC_ASSERT_ALLOC
LIBDVEC_ENV = DEBUG=1 ASSERT_ALLOC=1 ASSERT_ARGS=1
-LIBHMAP_ENV = DEBUG=1
+CFLAGS += -DLIBHMAP_ASSERT_ARGS -DLIBHMAP_ASSERT_ALLOC
+LIBHMAP_ENV = DEBUG=1 ASSERT_ALLOC=1 ASSERT_ARGS=1
LIBMAXINT_ENV = DEBUG=1
LIBALLOC_ENV = DEBUG=1
+CFLAGS += -DLIBLIST_ASSERT_ARGS
+LIBLIST_ENV = DEBUG=1
+LIBPQ_ENV = DEBUG=1
endif
DAYS = $(shell seq 1 24 | xargs printf "%02i\n")
@@ -29,6 +36,12 @@ lib/libmaxint/build/libmaxint.a:
lib/liballoc/build/liballoc.a:
make -C lib/liballoc build/liballoc.a $(LIBALLOC_ENV)
+lib/liblist/build/liblist.a:
+ make -C lib/liblist build/liblist.a $(LIBLIST_ENV)
+
+lib/libpq/build/libpq.a:
+ make -C lib/libpq build/libpq.a $(LIBPQ_ENV)
+
define make-day
all:: $1/main
run:: $1/run
@@ -48,7 +61,7 @@ clean:
cleanall: clean
make -C lib/libdvec clean
- make -C lib/libhashmap clean
+ make -C lib/libhmap clean
make -C lib/libmaxint clean
make -C lib/liballoc clean
diff --git a/common/dvec_s.h b/common/dvec_s.h
@@ -0,0 +1,29 @@
+#include "dvec.h"
+
+#include <assert.h>
+
+static inline void *
+dvec_add_slots(struct dvec *dvec, size_t count)
+{
+ assert(!dvec_add(dvec, dvec->len, count));
+
+ return dvec->data + (dvec->len - count) * dvec->dsize;
+}
+
+static inline void *
+dvec_add_slot(struct dvec *dvec)
+{
+ return dvec_add_slots(dvec, 1);
+}
+
+static inline void
+dvec_rm_slots(struct dvec *dvec, void *slot, size_t count)
+{
+ dvec_remove(dvec, ((size_t) (slot - dvec->data)) / dvec->dsize, count);
+}
+
+static inline void
+dvec_rm_slot(struct dvec *dvec, void *slot)
+{
+ dvec_rm_slots(dvec, slot, 1);
+}
diff --git a/common/icc.c b/common/icc.c
@@ -2,7 +2,7 @@
#include "allocator.h"
#include "aoc.h"
#include "util.h"
-#include "dvec.h"
+#include "dvec_s.h"
#include <assert.h>
#include <stdbool.h>
@@ -76,14 +76,12 @@ icc_parse_inst(struct icc *icc, const char *str, size_t len)
const char *pos, *end;
char buf[256];
int val, *slot;
- int rc;
pos = str;
end = str + len;
while (readtok(buf, sizeof(buf), ',', &pos, end)) {
val = (int) parsei64(buf);
- slot = dvec_add_slot(&icc->instructions, &rc);
- assert(slot);
+ slot = dvec_add_slot(&icc->instructions);
*slot = val;
}
}
diff --git a/common/main.c b/common/main.c
@@ -8,6 +8,7 @@ struct aoc aoc;
int
main(int argc, const char **argv)
{
+ const char *envvar;
FILE *f;
if (argc <= 1) {
@@ -18,7 +19,8 @@ main(int argc, const char **argv)
aoc.part = atoi(argv[1]);
aoc.args = &argv[2];
- aoc.debug = getenv("AOC_DEBUG") != NULL;
+ envvar = getenv("AOC_DEBUG");
+ aoc.debug = envvar ? atoi(envvar) : 0;
/* parse user input */
aoc.inputfile = getenv("AOC_INPUT");
diff --git a/common/util.c b/common/util.c
@@ -106,7 +106,7 @@ apprintf(char *str, const char *fmtstr, ...)
}
void *
-memdup(void *data, size_t size)
+memdup(const void *data, size_t size)
{
void *new;
diff --git a/common/util.h b/common/util.h
@@ -26,7 +26,7 @@ int64_t parsei64(const char *str);
char *aprintf(const char *fmtstr, ...);
char *apprintf(char *alloc, const char *fmtstr, ...);
-void *memdup(void *data, size_t size);
+void *memdup(const void *data, size_t size);
void readall(FILE *f, void **data, size_t *read);
diff --git a/lib/liblist b/lib/liblist
@@ -0,0 +1 @@
+Subproject commit ff57ed0d47a21614c0fd3f7f3be9d7a0233958e7
diff --git a/lib/libpq b/lib/libpq
@@ -0,0 +1 @@
+Subproject commit 46465417e54567584f6d26c157e7ae345e01088e
