aoc-2019-c

main.c (11146B)

#include "allocator.h"
#include "aoc.h"
#include "iccmp.h"
#include "dvec_s.h"
#include "vec_s.h"
#include "hmap_s.h"
#include "util.h"

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define DIR_COUNT 15

struct path {
	uint8_t dir[DIR_COUNT];
	uint8_t dircnt;
};

struct room {
	char *name;
	struct path path;
	uint8_t doors;
	struct dvec items;
};

struct state {
	uint8_t next;
	uint8_t back;
};

bool
path_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
{
	const struct path *p1 = k1.p, *p2 = k2.p;

	return p1->dircnt == p2->dircnt
		&& !memcmp(p1->dir, p2->dir, p1->dircnt);
}

uint32_t
path_hmap_hash(struct hmap_key k)
{
	const struct path *s = k.p;
	uint32_t hash;
	uint8_t i;

	hash = 0;
	for (i = 0; i < MIN(8, s->dircnt); i++)
		hash = (hash << 2) | s->dir[i];

	return hash;
}

const char *
path_str(struct path *path)
{
	static char buf[256];
	size_t i, len;
	ssize_t n;

	len = 0;
	for (i = 0; i < path->dircnt && len < sizeof(buf); i++) {
		if (len) {
			n = snprintf(buf + len, sizeof(buf) - len,
				" -> %c", adj_c[path->dir[i]]);
		} else {
			n = snprintf(buf + len, sizeof(buf) - len,
				"%c", adj_c[path->dir[i]]);
		}
		if (n <= 0) break;
		len += (size_t) n;
	}

	buf[len] = '\0';

	return buf;
}

void
read_output(struct icc *icc, struct dvec *out)
{
	const char *lpos, *lend;
	char line[256];
	char *c;

	dvec_clear(out);
	while (1) {
		switch (icc->state) {
		case ICC_OUTPUT:
			c = dvec_add_slot(out);
			*c = (char) mi_cast_uls(&icc->out);
			break;
		case ICC_RUN:
			break;
		default:
			goto exit;
		}
		icc_step_inst(icc);
	}

exit:
	c = dvec_add_slot(out);
	*c = '\0';

	if (aoc.debug == 2) {
		lpos = out->data;
		lend = out->data + out->len;
		while (readtok(line, sizeof(line), '\n', &lpos, lend))
			aoc_debug("OUT > %s\n", line);
		aoc_debug("\n");
	}
}

void
feed_input(struct icc *icc, struct dvec *input)
{
	size_t i;
	char *c;

	if (aoc.debug == 2)
		aoc_debug("\nIN  < %.*s", input->len, input->data);

	i = 0;
	while (i < input->len) {
		switch (icc->state) {
		case ICC_INPUT:
			c = dvec_at(input, i);
			mi_setv(&icc->in, (mi_ul) *c, MI_POS);
			i += 1;
			break;
		case ICC_RUN:
			break;
		default:
			return;
		}
		icc_step_inst(icc);
	}
}

void
parse_output(struct dvec *out, char **title, uint8_t *dirs, struct dvec *items)
{
	const char *lpos, *lend;
	char line[256];
	int state;
	char *c, *item;

	state = 0;
	*dirs = 0;
	*title = NULL;
	lpos = out->data;
	lend = lpos + out->len;
	while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
		if (!strcmp(line, "Doors here lead:")) {
			state = 1;
		} else if (!strcmp(line, "Items here:")) {
			state = 2;
		} else if (state == 0 && !strncmp(line, "== ", 3)) {
			c = strrchr(line, ' ');
			*c = '\0';
			*title = strdup(line + 3);
		} else if (state == 1 && !strncmp(line, "- ", 2)) {
			if (!strcmp(line + 2, "north")) {
				*dirs |= (1 << ADJ_NORTH);
			} else if (!strcmp(line + 2, "east")) {
				*dirs |= (1 << ADJ_EAST);
			} else if (!strcmp(line + 2, "south")) {
				*dirs |= (1 << ADJ_SOUTH);
			} else if (!strcmp(line + 2, "west")) {
				*dirs |= (1 << ADJ_WEST);
			} else {
				assert(0);
			}
		} else if (state == 2 && !strncmp(line, "- ", 2)) {
			item = strdup(line + 2);
			*(char **)dvec_add_slot(items) = item;
		}
	}
}

int
explore(struct icc *icc, struct dvec *in, struct dvec *out, struct hmap *states,
	struct hmap *map, struct path *path, struct dvec *items)
{
	struct hmap_link *link, **linkp;
	struct path *key;
	struct state *state;
	struct room *room;
	char **name;
	size_t dir;

	read_output(icc, out);

	link = hmap_get(states, (struct hmap_key) {.p = path});
	assert(link);
	state = link->value._p;

	linkp = hmap_link_pos(map, (struct hmap_key) {.p = path});
	if (!*linkp) {
		key = memdup(path, sizeof(struct path));
		room = malloc(sizeof(struct room));
		memcpy(&room->path, path, sizeof(struct path));
		dvec_init(&room->items, sizeof(char *), 0,
			&stdlib_strict_heap_allocator);
		parse_output(out, &room->name, &room->doors, &room->items);
		assert(room->name && room->doors);

		*linkp = hmap_link_alloc(map,
			(struct hmap_key) {.p = key},
			(struct hmap_val) {.p = room}, NULL);

		if (!strcmp(room->name, "Pressure-Sensitive Floor")) {
			assert(path->dircnt);
			path->dircnt -= 1;
			return path->dir[path->dircnt];
		}

		for (DVEC_ITER(&room->items, name)) {
			if (!strcmp(*name, "infinite loop"))
				continue;
			if (!strcmp(*name, "escape pod"))
				continue;
			if (!strcmp(*name, "photons"))
				continue;
			if (!strcmp(*name, "molten lava"))
				continue;
			if (!strcmp(*name, "giant electromagnet"))
				continue;
			*(char **)dvec_add_slot(items) = *name;
			dvec_clear(in);
			dvec_sprintf(in, "take %s\n", *name);
			feed_input(icc, in);
			read_output(icc, out);
		}
	} else {
		room = (*linkp)->value._p;
	}

	assert(path->dircnt != sizeof(path->dir) - 1);
	path->dircnt += 1;
	for (dir = state->next; dir < 4; dir++) {
		if (!(room->doors & (1 << dir)))
			continue;
		if (dir == state->back)
			continue;
		path->dir[path->dircnt - 1] = (uint8_t) dir;
		link = hmap_get(map, (struct hmap_key) {.p = path});
		if (link) continue;
		break;
	}
	state->next = (uint8_t) dir + 1;
	path->dircnt -= 1;

	if (dir >= 4) {
		if (!path->dircnt) return -1;
		path->dircnt -= 1;

		dir = state->back;
	} else {
		path->dircnt += 1;

		linkp = hmap_link_pos(states, (struct hmap_key) {.p = path});
		if (!*linkp) {
			aoc_debug("add: %s\n", path_str(path));
			key = memdup(path, sizeof(struct path));
			state = malloc(sizeof(struct state));
			state->next = 0;
			state->back = (dir + 2) % 4;
			*linkp = hmap_link_alloc(states,
				(struct hmap_key) {.p = key},
				(struct hmap_val) {.p = state}, NULL);
		}
	}

	return (int) dir;
}

void
input_from_dir(struct dvec *in, int dir)
{
	dvec_clear(in);
	switch (dir) {
	case ADJ_NORTH:
		dvec_add_slots(in, 7);
		strcpy(in->data, "north\n");
		break;
	case ADJ_EAST:
		dvec_add_slots(in, 6);
		strcpy(in->data, "east\n");
		break;
	case ADJ_SOUTH:
		dvec_add_slots(in, 7);
		strcpy(in->data, "south\n");
		break;
	case ADJ_WEST:
		dvec_add_slots(in, 6);
		strcpy(in->data, "west\n");
		break;
	}
}

void
get_path(struct hmap *map, struct path *path, const char *name)
{
	struct hmap_iter iter;
	struct room *room;

	for (HMAP_ITER(map, iter)) {
		room = iter.link->value._p;
		if (!strcmp(room->name, name)) {
			memcpy(path, &room->path, sizeof(struct path));
			return;
		}
	}

	assert(0);
}

void
move(struct icc *icc, struct dvec *in, struct dvec *out, int dir)
{
	input_from_dir(in, dir);
	feed_input(icc, in);
	read_output(icc, out);
}

void
move_to(struct icc *icc, struct dvec *in, struct dvec *out, struct path *path)
{
	ssize_t i;

	for (i = 0; i < path->dircnt; i++)
		move(icc, in, out, path->dir[i]);
}

void
move_back(struct icc *icc, struct dvec *in, struct dvec *out, struct path *path)
{
	ssize_t i;

	for (i = path->dircnt - 1; i >= 0; i--)
		move(icc, in, out, path->dir[i]);
}

void
interactive(struct icc *icc)
{
	int c;

	while (1) {
		switch (icc->state) {
		case ICC_INPUT:
			c = getc(stdin);
			if (c == 4) break;
			mi_setv(&icc->in, (mi_ul) c, MI_POS);
			break;
		case ICC_OUTPUT:
			c = (int) mi_cast_uls(&icc->out);
			putc(c, stdout);
			break;
		case ICC_RUN:
			break;
		default:
			assert(0);
		}
		icc_step_inst(icc);
		if (icc->state == ICC_INPUT && c <= 4)
			break;
	}
}

bool
find_items(struct icc *icc, struct dvec *in, struct dvec *out,
	struct dvec *items, struct dvec *taken, size_t depth, int dir)
{
	char **name, **other, **slot;

	for (DVEC_ITER(items, name)) {
		for (DVEC_ITER(taken, other)) {
			if (!strcmp(*name, *other))
				break;
		}
		if (other) continue;

		dvec_clear(in);
		dvec_sprintf(in, "take %s\n", *name);
		feed_input(icc, in);
		read_output(icc, out);

		input_from_dir(in, dir);
		feed_input(icc, in);
		read_output(icc, out);

		slot = dvec_add_slot(taken);
		*slot = *name;

		for (DVEC_ITER(taken, other))
			aoc_debug("%s > ", *other);

		if (strstr(out->data, "lighter")) {
			aoc_debug("*lighter*\n");
		} else if (strstr(out->data, "heavier")) {
			aoc_debug("*heavier*\n");
			if (depth != items->len) {
				if (find_items(icc, in, out,
						items, taken, depth + 1, dir))
					return true;
			}
		} else {
			aoc_debug("*correct*\n");
			return true;
		}

		dvec_rm_slot(taken, slot);

		dvec_clear(in);
		dvec_sprintf(in, "drop %s\n", *name);
		feed_input(icc, in);
		read_output(icc, out);
	}

	return false;
}

void
part1(void)
{
	struct icc icc;
	struct dvec in, out;
	struct hmap map;
	struct hmap states;
	struct hmap_iter iter;
	struct dvec items;
	struct dvec taken;
	struct room *room;
	struct state *state;
	struct path path;
	struct path *key;
	size_t answer;
	char **name;
	char *str;
	int dir;

	icc_init(&icc);
	icc_parse_inst(&icc, aoc.input, aoc.input_size);

	dvec_init(&in, 1, 0, &stdlib_strict_heap_allocator);
	dvec_init(&out, 1, 0, &stdlib_strict_heap_allocator);

	hmap_init(&map, 32, path_hmap_hash, path_hmap_keycmp,
		&stdlib_strict_heap_allocator);
	hmap_init(&states, 32, path_hmap_hash, path_hmap_keycmp,
		&stdlib_strict_heap_allocator);

	dvec_init(&items, sizeof(char *), 0, &stdlib_strict_heap_allocator);
	dvec_init(&taken, sizeof(char *), 0, &stdlib_strict_heap_allocator);

	path.dircnt = 0;
	memset(path.dir, 0, DIR_COUNT);

	key = memdup(&path, sizeof(struct path));
	state = malloc(sizeof(struct state));
	state->back = 4;
	state->next = 0;
	hmap_add(&states, (struct hmap_key) {.p = key},
		(struct hmap_val) {.p = state});

	if (getenv("INTERACTIVE")) {
		interactive(&icc);
		goto exit;
	}

	while (1) {
		dir = explore(&icc, &in, &out, &states,
			&map, &path, &items);
		if (dir < 0) break;
		input_from_dir(&in, dir);
		feed_input(&icc, &in);
	}

	get_path(&map, &path, "Pressure-Sensitive Floor");
	path.dircnt -= 1;
	move_to(&icc, &in, &out, &path);

	for (DVEC_ITER(&items, name)) {
		dvec_clear(&in);
		dvec_sprintf(&in, "drop %s\n", *name);
		feed_input(&icc, &in);
		read_output(&icc, &out);
	}

	//interactive(&icc);
	assert(find_items(&icc, &in, &out, &items,
		&taken, 1, path.dir[path.dircnt]));
	path.dircnt += 1;

	str = strstr(out.data, "typing ");
	assert(str != NULL);
	assert(sscanf(str, "typing %lu on the keypad", &answer) == 1);

	aoc.answer = aprintf("%lu", answer);
	aoc.solution = "278664";

	for (HMAP_ITER(&map, iter)) {
		room = iter.link->value._p;
		aoc_debug("-- ROOM --\n");
		aoc_debug("path: %s\n", path_str(&room->path));
		aoc_debug("name: %s\n", room->name);
		aoc_debug("doors: %04b\n", room->doors);
		for (DVEC_ITER(&room->items, name))
			aoc_debug("- %s\n", *name);
		aoc_debug("\n");
	}

exit:
	for (HMAP_ITER(&map, iter)) {
		free(iter.link->key._p);
		room = iter.link->value._p;
		free(room->name);
		for (DVEC_ITER(&room->items, name))
			free(*name);
		dvec_deinit(&room->items);
		free(room);
	}
	hmap_deinit(&map);

	for (HMAP_ITER(&states, iter)) {
		free(iter.link->key._p);
		free(iter.link->value._p);
	}
	hmap_deinit(&states);

	dvec_deinit(&taken);
	dvec_deinit(&items);

	dvec_deinit(&out);
	dvec_deinit(&in);

	icc_deinit(&icc);
}

void
part2(void)
{
	aoc.answer = strdup("");
	aoc.solution = "";
}