main.c (5381B)
1#include "aoc.h" 2#include "allocator.h" 3#include "util.h" 4#include "hmap.h" 5#include "dvec_s.h" 6 7#include <assert.h> 8#include <stdbool.h> 9#include <stddef.h> 10#include <stdint.h> 11#include <stdio.h> 12#include <stdlib.h> 13 14struct ingredient { 15 char name[8]; 16 size_t amount; 17}; 18 19struct reaction { 20 struct dvec ingredients; 21 struct ingredient result; 22 23}; 24 25void 26parse_reactions(struct hmap *reactions) 27{ 28 const char *pos, *sep, *lpos, *lend; 29 struct reaction *reaction; 30 struct ingredient ingredient; 31 char line[256]; 32 void *slot; 33 int rc; 34 35 lpos = aoc.input; 36 lend = lpos + aoc.input_size; 37 while (readtok(line, sizeof(line), '\n', &lpos, lend)) { 38 if (strspn(line, " \r\n\t\v") == strlen(line)) 39 continue; 40 41 reaction = malloc(sizeof(struct reaction)); 42 assert(reaction != NULL); 43 dvec_init(&reaction->ingredients, sizeof(struct ingredient), 44 10, &stdlib_strict_heap_allocator); 45 46 pos = line; 47 while (1) { 48 sep = strchr(pos, ','); 49 if (!sep) sep = strchr(pos, '>'); 50 51 rc = sscanf(pos, "%lu %[^,= ]", 52 &ingredient.amount, ingredient.name); 53 assert(rc == 2); 54 55 if (sep) { 56 slot = dvec_add_slot(&reaction->ingredients); 57 memcpy(slot, &ingredient, 58 sizeof(struct ingredient)); 59 } else { 60 memcpy(&reaction->result, &ingredient, 61 sizeof(struct ingredient)); 62 } 63 64 if (!sep) break; 65 pos = sep + 2; 66 } 67 68 hmap_add(reactions, 69 (struct hmap_key) {.p = reaction->result.name}, 70 (struct hmap_val) {.p = reaction}); 71 } 72} 73 74size_t 75add_excess(struct hmap *hmap, struct ingredient *result, struct reaction *reaction) 76{ 77 struct hmap_link **link; 78 size_t n, amount, excess; 79 80 amount = result->amount; 81 link = hmap_link_pos(hmap, (struct hmap_key) {.p = reaction->result.name}); 82 if (link && *link) { 83 aoc_debug("get excess %s = %u\n", reaction->result.name, 84 (*link)->value.u); 85 if ((*link)->value.u >= amount) { 86 (*link)->value.u -= (unsigned int) amount; 87 return 0; 88 } else { 89 amount -= (*link)->value.u; 90 (*link)->value.u = 0; 91 } 92 } 93 94 n = CEILDIV(amount, reaction->result.amount); 95 excess = n * reaction->result.amount - amount; 96 aoc_debug("set excess %s = %lu\n", reaction->result.name, excess); 97 if (link && *link) { 98 (*link)->value.u = (unsigned int) excess; 99 } else { 100 hmap_add(hmap, (struct hmap_key) {.p = reaction->result.name}, 101 (struct hmap_val) {.u = (unsigned int) excess}); 102 } 103 104 return n; 105} 106 107size_t 108calculate_ore(struct hmap *reactions, struct hmap *excess, 109 const char *name, size_t amount) 110{ 111 struct hmap_link *link; 112 struct reaction *reaction; 113 struct ingredient ingredient; 114 struct ingredient result; 115 struct dvec reactants; 116 struct ingredient *slot, *slot2; 117 size_t ore, n; 118 119 dvec_init(&reactants, sizeof(struct ingredient), 120 10, &stdlib_strict_heap_allocator); 121 122 slot = dvec_add_slot(&reactants); 123 ingredient.amount = amount; 124 snprintf(ingredient.name, 8, "%s", name); 125 memcpy(slot, &ingredient, sizeof(struct ingredient)); 126 127 ore = 0; 128 while (!dvec_empty(&reactants)) { 129 slot = dvec_back(&reactants); 130 memcpy(&result, slot, sizeof(struct ingredient)); 131 dvec_rm_slot(&reactants, slot); 132 133 link = hmap_get(reactions, (struct hmap_key) {.p = result.name}); 134 assert(link != NULL); 135 reaction = link->value._p; 136 137 n = add_excess(excess, &result, reaction); 138 if (!n) continue; 139 140 for (DVEC_ITER(&reaction->ingredients, slot)) { 141 aoc_debug("%lu %s needs %lu %s\n", 142 result.amount, result.name, 143 slot->amount * n, slot->name); 144 if (!strcmp(slot->name, "ORE")) { 145 ore += slot->amount * n; 146 } else { 147 snprintf(ingredient.name, 8, "%s", slot->name); 148 ingredient.amount = slot->amount * n; 149 slot2 = dvec_add_slot(&reactants); 150 memcpy(slot2, &ingredient, sizeof(struct ingredient)); 151 } 152 } 153 } 154 155 dvec_deinit(&reactants); 156 157 return ore; 158} 159 160void 161part1(void) 162{ 163 struct hmap_iter iter; 164 struct hmap reactions; 165 struct hmap excess; 166 struct reaction *reaction; 167 size_t ore; 168 169 hmap_init(&reactions, 256, hmap_str_hash, hmap_str_keycmp, 170 &stdlib_strict_heap_allocator); 171 hmap_init(&excess, 256, hmap_str_hash, hmap_str_keycmp, 172 &stdlib_strict_heap_allocator); 173 174 parse_reactions(&reactions); 175 176 ore = calculate_ore(&reactions, &excess, "FUEL", 1); 177 178 aoc.answer = aprintf("%lu", ore); 179 aoc.solution = "1582325"; 180 181 for (HMAP_ITER(&reactions, iter)) { 182 reaction = iter.link->value._p; 183 dvec_deinit(&reaction->ingredients); 184 free(iter.link->value._p); 185 } 186 hmap_deinit(&excess); 187 hmap_deinit(&reactions); 188} 189 190void 191part2(void) 192{ 193 const size_t max_ore = 1000000000000UL; 194 struct hmap_iter iter; 195 struct hmap reactions; 196 struct hmap excess; 197 struct reaction *reaction; 198 size_t fuel_min, fuel_max; 199 size_t ore, fuel; 200 201 hmap_init(&reactions, 256, hmap_str_hash, hmap_str_keycmp, 202 &stdlib_strict_heap_allocator); 203 hmap_init(&excess, 256, hmap_str_hash, hmap_str_keycmp, 204 &stdlib_strict_heap_allocator); 205 206 parse_reactions(&reactions); 207 208 fuel_min = 1; 209 fuel_max = max_ore; 210 while (1) { 211 fuel = (fuel_min + fuel_max) / 2; 212 if (fuel == fuel_min) break; 213 ore = calculate_ore(&reactions, &excess, "FUEL", fuel); 214 if (ore > max_ore) { 215 fuel_max = fuel; 216 } else if (ore < max_ore) { 217 fuel_min = fuel; 218 } else { 219 break; 220 } 221 hmap_clear(&excess); 222 } 223 224 aoc.answer = aprintf("%lu", fuel); 225 aoc.solution = "2267486"; 226 227 for (HMAP_ITER(&reactions, iter)) { 228 reaction = iter.link->value._p; 229 dvec_deinit(&reaction->ingredients); 230 free(iter.link->value._p); 231 } 232 hmap_deinit(&excess); 233 hmap_deinit(&reactions); 234}