aoc-2019-c

main.c (4635B)

#include "aoc.h"
#include "allocator.h"
#include "util.h"
#include "hmap.h"

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

struct asteroid {
	int x, y;

	struct asteroid *next;
};

struct dir {
	int dx, dy;
};

struct asteroid *asteroids;
int width, height;

bool
hmap_dir_keycmp(struct hmap_key k1, struct hmap_key k2)
{
	const struct dir *d1 = k1.p, *d2 = k2.p;

	return d1->dx == d2->dx && d1->dy == d2->dy;
}

uint32_t
hmap_dir_hash(struct hmap_key key)
{
	const struct dir *dir = key.p;
	uint32_t hash;

	hash = ((uint32_t) dir->dx & 0xFFFF);
	hash |= ((uint32_t) dir->dy & 0xFFFF) << 16;

	return hash;
}

void
add_asteroid(int x, int y)
{
	struct asteroid **iter;

	for (iter = &asteroids; *iter; iter = &((*iter)->next));

	*iter = malloc(sizeof(struct asteroid));
	assert(*iter != NULL);
	(*iter)->x = x;
	(*iter)->y = y;
	(*iter)->next = NULL;
}

void
asteroids_init(void)
{
	char *p;
	int x, y;

	asteroids = NULL;
	width = height = 0;

	x = y = 0;
	for (p = aoc.input; *p; p++) {
		switch (*p) {
		case '\n':
			width = x;
			x = 0;
			height++;
			y++;
			break;
		case '#':
			add_asteroid(x, y);
		case '.':
			x++;
			break;
		}
	}

	assert(width != 0 && height != 0);
}

void
asteroids_deinit(void)
{
	struct asteroid *iter, *next;

	for (iter = asteroids; iter; iter = next) {
		next = iter->next;
		free(iter);
	}
}

int
gcd(int a, int b)
{
	int t;

	while (b) {
		t = b;
		b = a % b;
		a = t;
	}

	return a;
}

void
reduce_frac(struct dir *d)
{
	int cd;

	cd = gcd(ABS(d->dx), ABS(d->dy));
	d->dx /= cd;
	d->dy /= cd;
}

void
get_vis(struct hmap *hm, const struct asteroid *a1)
{
	struct hmap_link *link;
	const struct asteroid *a2, *tmp;
	struct dir dir, odir;
	void *key;
	int rc;

	for (a2 = asteroids; a2; a2 = a2->next) {
		if (a1 == a2) continue;

		dir.dx = a2->x - a1->x;
		dir.dy = a2->y - a1->y;
		reduce_frac(&dir);

		link = hmap_get(hm, (struct hmap_key) {.p = &dir});
		if (link) {
			tmp = link->value.p;
			odir = (struct dir) { tmp->x - a1->x, tmp->y - a1->y };
			dir = (struct dir) { a2->x - a1->x, a2->y - a1->y };
			if (ABS(odir.dx) + ABS(odir.dy) > ABS(dir.dx) + ABS(dir.dy))
				link->value.p = a2;
		} else {
			key = memdup(&dir, sizeof(struct dir));
			rc = hmap_add(hm, (struct hmap_key) {.p = key},
				(struct hmap_val) {.p = a2});
			assert(!rc);
		}
	}
}

float
angle(const struct asteroid *a, const struct asteroid *base)
{
	if (a->x == base->x)
		return a->y > base->y ? 0 : -(float) 3.1415926;

	return (float) atan2(base->x - a->x, a->y - base->y);
}

void
find_base(const struct asteroid **a_out, int *vis_out)
{
	struct asteroid *a1, *cand;
	struct hmap_iter iter;
	struct hmap dirmap;
	int vis, maxvis;

	hmap_init(&dirmap, 100, hmap_dir_hash, hmap_dir_keycmp,
		&stdlib_strict_heap_allocator);

	maxvis = 0;
	cand = NULL;
	for (a1 = asteroids; a1; a1 = a1->next) {
		aoc_debug("Asteroid @ %i,%i => ", a1->x, a1->y);
		get_vis(&dirmap, a1);

		vis = 0;
		for (HMAP_ITER(&dirmap, iter))
			vis++;
		aoc_debug("%i vis\n", vis);

		if (maxvis == 0 || vis > maxvis) {
			maxvis = vis;
			cand = a1;
		}

		for (HMAP_ITER(&dirmap, iter))
			free(iter.link->key._p);
		hmap_clear(&dirmap);
	}

	assert(cand != NULL);
	hmap_deinit(&dirmap);

	if (vis_out) *vis_out = maxvis;
	if (a_out) *a_out = cand;
}

void
part1(void)
{
	const struct asteroid *a;
	int vis;

	asteroids_init();
	find_base(&a, &vis);

	aoc_debug("Best at %i,%i with %i vis\n", a->x, a->y, vis);
	aoc.answer = aprintf("%i", vis);
	aoc.solution = "299";

	asteroids_deinit();
}

void
part2(void)
{
	const struct asteroid *base, *tmp;
	struct hmap_iter iter;
	const struct asteroid **list;
	struct hmap dirmap;
	int i, k, len;
	float prev;

	asteroids_init();
	find_base(&base, NULL);

	hmap_init(&dirmap, 100, hmap_dir_hash, hmap_dir_keycmp,
		&stdlib_strict_heap_allocator);
	get_vis(&dirmap, base);

	len = 0;
	for (HMAP_ITER(&dirmap, iter))
		len++;
	list = malloc(sizeof(struct asteroid *) * (size_t) len);
	assert(list != NULL);
	i = 0;
	for (HMAP_ITER(&dirmap, iter))
		list[i++] = iter.link->value.p;

	for (i = 0; i < len; i++) {
		for (k = 0; k < len - 1; k++) {
			if (angle(list[k], base) > angle(list[k+1], base)) {
				tmp = list[k];
				list[k] = list[k+1];
				list[k+1] = tmp;
			}
		}
	}

	prev = angle(list[0], base);
	for (k = 0; k < len; k++) {
		aoc_debug("%i: %i %i %f\n", k+1, list[k]->x,
			list[k]->y, angle(list[k], base));
	}

	aoc.answer = aprintf("%i", list[199]->x * 100 + list[199]->y);
	aoc.solution = "1419";

	free(list);

	for (HMAP_ITER(&dirmap, iter))
		free(iter.link->key._p);

	asteroids_deinit();
	hmap_deinit(&dirmap);
}