aoc-2019-c

main.c (4961B)

#include "aoc.h"
#include "util.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAXA(a, b) (ABS(a) > ABS(b) ? (a) : (b))
#define MINA(a, b) (ABS(a) > ABS(b) ? (b) : (a))

struct line {
	int sx, sy;
	int ex, ey;

	struct line *next;
};

struct line *
parse_lines(const char **pos, const char *end)
{
	char buf[2048], part[64];
	const char *lpos, *lend;
	struct line *line, *start, **iter;
	int x, y, val;

	aoc_debug("START\n");

	if (!readtok(buf, sizeof(buf), '\n', pos, end))
		die("parse_lines: end of file");

	start = line = NULL;
	iter = &line;

	x = y = 0;
	lpos = buf;
	lend = buf + strlen(buf);
	while (readtok(part, sizeof(part), ',', &lpos, lend)) {
		*iter = line = malloc(sizeof(struct line));
		if (!line) die("parse_lines: oom");

		if (!start) start = line;

		line->next = NULL;
		line->sx = x;
		line->sy = y;

		val = (int) parsei64(part+1);
		switch (part[0]) {
		case 'L':
			x -= val;
			break;
		case 'R':
			x += val;
			break;
		case 'D':
			y -= val;
			break;
		case 'U':
			y += val;
			break;
		default:
			die("parse_lines: invalid move: %s", part);
		}

		aoc_debug("%i %i\n", x, y);

		line->ex = x;
		line->ey = y;

		iter = &(*iter)->next;
	}

	aoc_debug("END\n");

	return start;
}

void
free_lines(struct line *line)
{
	struct line *next;

	while (line) {
		next = line->next;
		free(line);
		line = next;
	}
}

int
do_intersect(struct line *l1, struct line *l2)
{
	int inx, iny;

	inx = MAX(l1->sx, l1->ex) >= MIN(l2->sx, l2->ex)
		&& MAX(l2->sx, l2->ex) >= MIN(l1->sx, l1->ex);
	iny = MAX(l1->sy, l1->ey) >= MIN(l2->sy, l2->ey)
		&& MAX(l2->sy, l2->ey) >= MIN(l1->sy, l1->ey);

	return inx && iny;
}

void
intersection_near_origin(struct line *l1, struct line *l2, int *x, int *y)
{
	if (l1->sx == l1->ex && l2->sx == l2->ex) {
		*x = l1->sx;
		*y = MAXA(
			MINA(l1->sy, l1->ey),
			MINA(l2->sy, l2->ey)
		);
	} else if (l1->sy == l1->ey && l2->sy == l2->ey) {
		*y = l1->sy;
		*x = MAXA(
			MINA(l1->sx, l1->ex),
			MINA(l2->sy, l2->ey)
		);
	} else {
		*x = (l1->sx == l1->ex) ? l1->sx : l2->sx;
		*y = (l1->sy == l1->ey) ? l1->sy : l2->sy;
	}
}

void
intersection_least_steps(struct line *l1, struct line *l2, int *x, int *y)
{
	int in1, in2;

	if (l1->sx == l1->ex && l2->sx == l2->ex) {
		/* if both ends or both starts of lines are part of the intersection,
		 * any one of them will give the same best dist,
		 * otherwise the start that intersects is the best fit */
		*x = l1->sx;
		in1 = l1->sy <= MAX(l2->sy, l2->ey) && l1->sy >= MIN(l2->sy, l2->ey);
		in2 = l2->sy <= MAX(l1->sy, l1->ey) && l2->sy >= MIN(l1->sy, l1->ey);
		*y = in1 ? l1->sy : (in2 ? l2->sy : l2->ey);
	} else if (l1->sy == l1->ey && l2->sy == l2->ey) {
		/* same for x-axis */
		*y = l1->sy;
		in1 = l1->sx <= MAX(l2->sx, l2->ex) && l1->sx >= MIN(l2->sx, l2->ex);
		in2 = l2->sx <= MAX(l1->sx, l1->ex) && l2->sx >= MIN(l1->sx, l1->ex);
		*x = in1 ? l1->sx : (in2 ? l2->sx : l2->ex);
	} else {
		*x = (l1->sx == l1->ex) ? l1->sx : l2->sx;
		*y = (l1->sy == l1->ey) ? l1->sy : l2->sy;
	}
}

int
calc_dist(struct line *lines, struct line *end, int x, int y)
{
	struct line *iter;
	int dist;

	dist = 0;
	for (iter = lines; iter != end; iter = iter->next) {
		dist += ABS(iter->ex - iter->sx);
		dist += ABS(iter->ey - iter->sy);
		aoc_debug("D: %i\n", dist);
	}

	dist += ABS(x - iter->sx);
	dist += ABS(y - iter->sy);
	aoc_debug("D: %i\n", dist);

	return dist;
}

void
part1(void)
{
	struct line *lines1, *lines2;
	struct line *iter1, *iter2;
	const char *pos, *end;
	int nx, ny, hit;
	int x, y;

	pos = aoc.input;
	end = aoc.input + aoc.input_size;
	lines1 = parse_lines(&pos, end);
	lines2 = parse_lines(&pos, end);

	x = y = 0;
	for (iter1 = lines1; iter1; iter1 = iter1->next) {
		for (iter2 = lines2; iter2; iter2 = iter2->next) {
			hit = do_intersect(iter1, iter2);
			if (!hit) continue;
			intersection_near_origin(iter1, iter2, &nx, &ny);
			if (!x && !y || ABS(nx) + ABS(ny) < ABS(x) + ABS(y)) {
				x = nx;
				y = ny;
			}
		}
	}

	aoc_debug("dist(%i, %i) = %i\n", x, y, ABS(x) + ABS(y));
	aoc.answer = aprintf("%i", ABS(x) + ABS(y));
	aoc.solution = "209";

	free_lines(lines1);
	free_lines(lines2);
}

void
part2(void)
{
	struct line *lines1, *lines2;
	struct line *iter1, *iter2;
	const char *pos, *end;
	int nx, ny, nd, hit;
	int x, y, d;

	pos = aoc.input;
	end = aoc.input + aoc.input_size;
	lines1 = parse_lines(&pos, end);
	lines2 = parse_lines(&pos, end);

	x = y = 0;
	for (iter1 = lines1; iter1; iter1 = iter1->next) {
		for (iter2 = lines2; iter2; iter2 = iter2->next) {
			hit = do_intersect(iter1, iter2);
			if (!hit) continue;
			intersection_least_steps(iter1, iter2, &nx, &ny);
			nd = calc_dist(lines1, iter1, nx, ny);
			nd += calc_dist(lines2, iter2, nx, ny);
			if (!x && !y || nd < d) {
				d = nd;
				x = nx;
				y = ny;
			}
		}
	}

	aoc_debug("steps(%i, %i) = %i\n", x, y, d);
	aoc.answer = aprintf("%i", d);
	aoc.solution = "43258";

	free_lines(lines1);
	free_lines(lines2);
}