aoc-2019-c

Advent of Code 2019 Solutions in C
git clone https://git.sinitax.com/sinitax/aoc-2019-c
Log | Files | Refs | README | sfeed.txt

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}