main.c (2702B)
1#include "aoc.h" 2#include "allocator.h" 3#include "hmap.h" 4#include "dvec_s.h" 5#include "util.h" 6 7#include <assert.h> 8#include <errno.h> 9#include <stdio.h> 10#include <string.h> 11#include <stdint.h> 12#include <stdlib.h> 13 14struct planet { 15 char *name; 16 struct planet *parent; 17 struct dvec children; 18}; 19 20struct hmap planets; 21 22struct planet * 23planets_get(const char *name) 24{ 25 struct hmap_link *link; 26 struct hmap_key key; 27 28 key.p = name; 29 link = hmap_get(&planets, key); 30 return link ? link->value._p : NULL; 31} 32 33struct planet * 34planets_add(const char *name) 35{ 36 struct planet *planet; 37 char *key; 38 39 planet = malloc(sizeof(struct planet)); 40 if (!planet) die("main: planets_add: malloc"); 41 42 planet->name = aprintf("%s", name); 43 planet->parent = NULL; 44 dvec_init(&planet->children, sizeof(struct planet *), 45 3, &stdlib_heap_allocator); 46 47 key = aprintf("%s", name); 48 assert(!hmap_add(&planets, (struct hmap_key) {.p = key}, 49 (struct hmap_val) {.p = planet})); 50 51 return planet; 52} 53 54void 55planets_init() 56{ 57 struct planet *parent, *child, **slot; 58 const char *pos, *end; 59 char buf[256], *sep; 60 61 hmap_init(&planets, 100, hmap_str_hash, 62 hmap_str_keycmp, &stdlib_heap_allocator); 63 64 pos = aoc.input; 65 end = aoc.input + aoc.input_size; 66 while (readtok(buf, sizeof(buf), '\n', &pos, end)) { 67 sep = strchr(buf, ')'); 68 if (!sep) die("main: bad format"); 69 *sep = '\0'; 70 71 parent = planets_get(buf); 72 if (!parent) parent = planets_add(buf); 73 74 child = planets_get(sep + 1); 75 if (!child) child = planets_add(sep + 1); 76 77 slot = dvec_add_slot(&parent->children); 78 *slot = child; 79 80 if (child->parent) die("main unexpected parent"); 81 child->parent = parent; 82 } 83} 84 85void 86planets_deinit() 87{ 88 struct hmap_iter iter; 89 struct planet *p; 90 91 for (HMAP_ITER(&planets, iter)) { 92 free(iter.link->key._p); 93 p = iter.link->value._p; 94 dvec_deinit(&p->children); 95 free(p->name); 96 free(p); 97 } 98 99 hmap_deinit(&planets); 100} 101 102void 103part1(void) 104{ 105 struct hmap_iter iter; 106 const struct planet *p; 107 int orbits; 108 109 planets_init(); 110 111 orbits = 0; 112 for (HMAP_ITER(&planets, iter)) { 113 p = iter.link->value.p; 114 while (p->parent) { 115 orbits += 1; 116 p = p->parent; 117 } 118 } 119 120 aoc.answer = aprintf("%i", orbits); 121 aoc.solution = "119831"; 122 123 planets_deinit(); 124} 125 126void 127part2(void) 128{ 129 struct planet *p1, *p2, *san, *you; 130 int s1, s2; 131 132 planets_init(); 133 134 san = planets_get("SAN"); 135 if (!san) die("main: missing planet SAN"); 136 you = planets_get("YOU"); 137 if (!you) die("main: missing planet YOU"); 138 139 for (s1 = 0, p1 = you; p1; p1 = p1->parent, s1++) { 140 for (s2 = 0, p2 = san; p2; p2 = p2->parent, s2++) { 141 if (!strcmp(p1->name, p2->name)) 142 goto exit; 143 } 144 } 145exit: 146 147 aoc.answer = aprintf("%i", s1 + s2 - 2); 148 aoc.solution = "322"; 149 150 planets_deinit(); 151}