aoc-2019-c

main.c (20982B)

#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));
	paths = dvec_alloc(sizeof(struct path), 1,
		&stdlib_strict_heap_allocator, NULL);
	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));
					paths = dvec_alloc(sizeof(struct path),
						1, &stdlib_strict_heap_allocator,
						NULL);
					*linkp = hmap_link_alloc(&distmap,
						(struct hmap_key) {.p = pos},
						(struct hmap_val) {.p = paths},
						NULL);
				}

				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(const void *p1, const void *p2, void *u)
{
	const struct state *s1 = p1, *s2 = p2;

	return s1->dist < s2->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));
			progs = dvec_alloc(sizeof(struct prog), 1,
				&stdlib_strict_heap_allocator, NULL);
			*linkp = hmap_link_alloc(distmap,
				(struct hmap_key) {.p = pos},
				(struct hmap_val) {.p = progs}, NULL);
		}

		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,
				LIST_OFFSET(struct state, link), NULL);
		}
	}
}

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;
	size_t mdist;

	/*
	 * - 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_insert_back(&active, &cstate->link);

	pos = memdup(start, sizeof(struct vec2i));
	progs = dvec_alloc(sizeof(struct prog), 1,
		&stdlib_strict_heap_allocator, NULL);
	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);
	}

	mdist = 0;
	while (!list_empty(&active)) {
		list_link = list_front(&active);
		cstate = LIST_UPCAST(list_link, struct state, link);
		if (cstate->acquired == (1U << keycnt) - 1) {
			mdist = cstate->dist;
			goto exit;
		}

		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);
	}

exit:
	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 mdist;
}

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(const void *p1, const void *p2, void *u)
{
	const struct state_multi *s1 = p1, *s2 = p2;

	return s1->dist < s2->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);
				progs = dvec_alloc(sizeof(struct prog), 1,
					&stdlib_strict_heap_allocator, NULL);
				*linkp = hmap_link_alloc(distmap,
					(struct hmap_key) {.p = pos},
					(struct hmap_val) {.p = progs}, NULL);
			}

			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,
					LIST_OFFSET(struct state_multi, link),
					NULL);
			}
		}
	}
}

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 mdist;
	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_insert_back(&active, &cstate->link);

	pos = memdup(starts, sizeof(struct vec2i) * 4);
	progs = dvec_alloc(sizeof(struct prog), 1,
		&stdlib_strict_heap_allocator, NULL);
	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);
		}
	}

	mdist = 0;
	while (!list_empty(&active)) {
		list_link = list_front(&active);
		cstate = LIST_UPCAST(list_link, struct state_multi, link);
		if (cstate->acquired == (1U << keycnt) - 1) {
			mdist = cstate->dist;
			goto exit;
		}

		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);
	}

exit:
	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 mdist;
}

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, &center, &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], &center, &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);
}