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

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <stdlib.h>

struct planet {
	char *name;
	struct planet *parent;
	struct dvec children;
};

struct hmap planets;

struct planet *
planets_get(const char *name)
{
	struct hmap_link *link;
	struct hmap_key key;

	key.p = name;
	link = hmap_get(&planets, key);
	return link ? link->value._p : NULL;
}

struct planet *
planets_add(const char *name)
{
	struct planet *planet;
	char *key;

	planet = malloc(sizeof(struct planet));
	if (!planet) die("main: planets_add: malloc");

	planet->name = aprintf("%s", name);
	planet->parent = NULL;
	dvec_init(&planet->children, sizeof(struct planet *),
		3, &stdlib_heap_allocator);

	key = aprintf("%s", name);
	assert(!hmap_add(&planets, (struct hmap_key) {.p = key},
		(struct hmap_val) {.p = planet}));

	return planet;
}

void
planets_init()
{
	struct planet *parent, *child, **slot;
	const char *pos, *end;
	char buf[256], *sep;

	hmap_init(&planets, 100, hmap_str_hash,
		hmap_str_keycmp, &stdlib_heap_allocator);

	pos = aoc.input;
	end = aoc.input + aoc.input_size;
	while (readtok(buf, sizeof(buf), '\n', &pos, end)) {
		sep = strchr(buf, ')');
		if (!sep) die("main: bad format");
		*sep = '\0';

		parent = planets_get(buf);
		if (!parent) parent = planets_add(buf);

		child = planets_get(sep + 1);
		if (!child) child = planets_add(sep + 1);

		slot = dvec_add_slot(&parent->children);
		*slot = child;

		if (child->parent) die("main unexpected parent");
		child->parent = parent;
	}
}

void
planets_deinit()
{
	struct hmap_iter iter;
	struct planet *p;

	for (HMAP_ITER(&planets, iter)) {
		free(iter.link->key._p);
		p = iter.link->value._p;
		dvec_deinit(&p->children);
		free(p->name);
		free(p);
	}

	hmap_deinit(&planets);
}

void
part1(void)
{
	struct hmap_iter iter;
	const struct planet *p;
	int orbits;

	planets_init();

	orbits = 0;
	for (HMAP_ITER(&planets, iter)) {
		p = iter.link->value.p;
		while (p->parent) {
			orbits += 1;
			p = p->parent;
		}
	}

	aoc.answer = aprintf("%i", orbits);
	aoc.solution = "119831";

	planets_deinit();
}

void
part2(void)
{
	struct planet *p1, *p2, *san, *you;
	int s1, s2;

	planets_init();

	san = planets_get("SAN");
	if (!san) die("main: missing planet SAN");
	you = planets_get("YOU");
	if (!you) die("main: missing planet YOU");

	for (s1 = 0, p1 = you; p1; p1 = p1->parent, s1++) {
		for (s2 = 0, p2 = san; p2; p2 = p2->parent, s2++) {
			if (!strcmp(p1->name, p2->name))
				goto exit;
		}
	}
exit:

	aoc.answer = aprintf("%i", s1 + s2 - 2);
	aoc.solution = "322";

	planets_deinit();
}