commit 1e09f86c26b95fc3f27a214dc46a6966d5311cd0
parent a1f776c9c5390b8409e7f44cb2a33d728d1200f3
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 5 Apr 2023 08:13:30 -0400
Add day 24
Diffstat:
11 files changed, 732 insertions(+), 6 deletions(-)
diff --git a/24/info.mk b/24/info.mk
@@ -0,0 +1,5 @@
+24_SRC = 24/part1.c 24/part2.c common/main.c common/aoc.c common/util.c
+24_SRC += common/vec_s.c common/hmap_s.c
+24_SRC += lib/liballoc/build/liballoc.a lib/libdvec/build/libdvec.a
+24_SRC += lib/libhmap/build/libhmap.a
+24_HDR = common/aoc.h common/util.h
diff --git a/24/input b/24/input
@@ -0,0 +1,6 @@
+#..##
+#.#..
+#...#
+##..#
+#..##
+
diff --git a/24/part1 b/24/part1
@@ -0,0 +1,77 @@
+--- Day 24: Planet of Discord ---
+
+You land on Eris, your last stop before reaching Santa. As soon as you do, your sensors start
+picking up strange life forms moving around: Eris is infested with bugs! With an over 24-hour
+roundtrip for messages between you and Earth, you'll have to deal with this problem on your own.
+
+Eris isn't a very large place; a scan of the entire area fits into a 5x5 grid (your puzzle input).
+The scan shows bugs (#) and empty spaces (.).
+
+Each minute, The bugs live and die based on the number of bugs in the four adjacent tiles:
+
+
+ - A bug dies (becoming an empty space) unless there is exactly one bug adjacent to it.
+
+ - An empty space becomes infested with a bug if exactly one or two bugs are adjacent to it.
+
+
+Otherwise, a bug or empty space remains the same. (Tiles on the edges of the grid have fewer than
+four adjacent tiles; the missing tiles count as empty space.) This process happens in every location
+simultaneously; that is, within the same minute, the number of adjacent bugs is counted for every
+tile first, and then the tiles are updated.
+
+Here are the first few minutes of an example scenario:
+
+Initial state:
+....#
+#..#.
+#..##
+..#..
+#....
+
+After 1 minute:
+#..#.
+####.
+###.#
+##.##
+.##..
+
+After 2 minutes:
+#####
+....#
+....#
+...#.
+#.###
+
+After 3 minutes:
+#....
+####.
+...##
+#.##.
+.##.#
+
+After 4 minutes:
+####.
+....#
+##..#
+.....
+##...
+
+To understand the nature of the bugs, watch for the first time a layout of bugs and empty spaces
+matches any previous layout. In the example above, the first layout to appear twice is:
+
+.....
+.....
+.....
+#....
+.#...
+
+To calculate the biodiversity rating for this layout, consider each tile left-to-right in the top
+row, then left-to-right in the second row, and so on. Each of these tiles is worth biodiversity
+points equal to increasing powers of two: 1, 2, 4, 8, 16, 32, and so on. Add up the biodiversity
+points for tiles with bugs; in this example, the 16th tile (32768 points) and 22nd tile (2097152
+points) have bugs, a total biodiversity rating of 2129920.
+
+What is the biodiversity rating for the first layout that appears twice?
+
+
diff --git a/24/part1.c b/24/part1.c
@@ -0,0 +1,147 @@
+#include "allocator.h"
+#include "aoc.h"
+#include "vec_s.h"
+#include "dvec_s.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+static char *
+load_map(size_t *maxx, size_t *h)
+{
+ const char *lpos, *lend;
+ size_t rows, cols, len;
+ char line[256];
+ char *map;
+
+ map = NULL;
+ rows = 0;
+ cols = 0;
+
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ len = strlen(line);
+ if (!len) continue;
+ if (!cols) cols = len;
+ assert(len == cols);
+ map = realloc(map, cols * (rows + 1) + 1);
+ memcpy(map + cols * rows, line, cols);
+ rows += 1;
+ }
+ map[rows * cols] = '\0';
+
+ *maxx = cols;
+ *h = rows;
+
+ return map;
+}
+
+static void
+print_map(char *map, size_t w, size_t h)
+{
+ size_t y;
+
+ for (y = 0; y < h; y++)
+ aoc_debug("%.*s\n", w, &map[y * w]);
+}
+
+static uint64_t
+map_id(char *map, size_t w, size_t h)
+{
+ size_t x, y, b;
+ uint64_t id;
+
+ b = 0;
+ id = 0;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (map[y * w + x] == '#')
+ id |= 1 << b;
+ b += 1;
+ }
+ }
+
+ return id;
+}
+
+static void
+step(char *prev, char *next, size_t w, size_t h)
+{
+ struct vec2i pos, npos;
+ size_t i, k, count;
+
+ for (pos.y = 0; (size_t) pos.y < h; pos.y++) {
+ for (pos.x = 0; (size_t) pos.x < w; pos.x++) {
+ count = 0;
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, &pos, &adj[i]);
+ if (npos.x < 0 || (size_t) npos.x >= w)
+ continue;
+ if (npos.y < 0 || (size_t) npos.y >= h)
+ continue;
+ k = (size_t) npos.y * w + (size_t) npos.x;
+ if (prev[k] == '#') count += 1;
+ }
+ k = (size_t) pos.y * w + (size_t) pos.x;
+ if (prev[k] == '#' && count != 1) {
+ next[k] = '.';
+ } else if (prev[k] == '.' && (count == 1 || count == 2)) {
+ next[k] = '#';
+ } else {
+ next[k] = prev[k];
+ }
+ }
+ }
+}
+
+void
+part1(void)
+{
+ struct dvec ids;
+ char *map, *next, *tmp;
+ uint64_t *slot, id;
+ size_t w, h, i;
+ uint64_t answer;
+
+ map = load_map(&w, &h);
+ next = memdup(map, w * h + 1);
+
+ dvec_init(&ids, sizeof(uint64_t), 0, &stdlib_strict_heap_allocator);
+ slot = dvec_add_slot(&ids);
+ *slot = map_id(map, w, h);
+
+ aoc_debug("INIT\n");
+ print_map(map, w, h);
+
+ answer = 0;
+ while (!answer) {
+ step(map, next, w, h);
+ tmp = map;
+ map = next;
+ next = tmp;
+
+ aoc_debug("$ %i\n", ids.len);
+ print_map(map, w, h);
+
+ id = map_id(map, w, h);
+ for (i = 0; i < ids.len; i++) {
+ aoc_debug("%lu vs %lu\n", id, *(uint64_t *)dvec_at(&ids, i));
+ if (*(uint64_t *)dvec_at(&ids, i) == id) {
+ answer = id;
+ break;
+ }
+ }
+
+ slot = dvec_add_slot(&ids);
+ *slot = id;
+ }
+
+ aoc.answer = aprintf("%lu", answer);
+
+ dvec_deinit(&ids);
+ free(next);
+ free(map);
+}
diff --git a/24/part2 b/24/part2
@@ -0,0 +1,185 @@
+--- Part Two ---
+
+After careful analysis, one thing is certain: you have no idea where all these bugs are coming from.
+
+Then, you remember: Eris is an old Plutonian settlement! Clearly, the bugs are coming from
+recursively-folded space.
+
+This 5x5 grid is only one level in an infinite number of recursion levels. The tile in the middle of
+the grid is actually another 5x5 grid, the grid in your scan is contained as the middle tile of a
+larger 5x5 grid, and so on. Two levels of grids look like this:
+
+ | | | |
+ | | | |
+ | | | |
+-----+-----+---------+-----+-----
+ | | | |
+ | | | |
+ | | | |
+-----+-----+---------+-----+-----
+ | | | | | | | |
+ | |-+-+-+-+-| |
+ | | | | | | | |
+ | |-+-+-+-+-| |
+ | | | |?| | | |
+ | |-+-+-+-+-| |
+ | | | | | | | |
+ | |-+-+-+-+-| |
+ | | | | | | | |
+-----+-----+---------+-----+-----
+ | | | |
+ | | | |
+ | | | |
+-----+-----+---------+-----+-----
+ | | | |
+ | | | |
+ | | | |
+
+(To save space, some of the tiles are not drawn to scale.) Remember, this is only a small part of
+the infinitely recursive grid; there is a 5x5 grid that contains this diagram, and a 5x5 grid that
+contains that one, and so on. Also, the ? in the diagram contains another 5x5 grid, which itself
+contains another 5x5 grid, and so on.
+
+The scan you took (your puzzle input) shows where the bugs are on a single level of this structure.
+The middle tile of your scan is empty to accommodate the recursive grids within it. Initially, no
+other levels contain bugs.
+
+Tiles still count as adjacent if they are directly up, down, left, or right of a given tile. Some
+tiles have adjacent tiles at a recursion level above or below its own level. For example:
+
+ | | | |
+ 1 | 2 | 3 | 4 | 5
+ | | | |
+-----+-----+---------+-----+-----
+ | | | |
+ 6 | 7 | 8 | 9 | 10
+ | | | |
+-----+-----+---------+-----+-----
+ | |A|B|C|D|E| |
+ | |-+-+-+-+-| |
+ | |F|G|H|I|J| |
+ | |-+-+-+-+-| |
+ 11 | 12 |K|L|?|N|O| 14 | 15
+ | |-+-+-+-+-| |
+ | |P|Q|R|S|T| |
+ | |-+-+-+-+-| |
+ | |U|V|W|X|Y| |
+-----+-----+---------+-----+-----
+ | | | |
+ 16 | 17 | 18 | 19 | 20
+ | | | |
+-----+-----+---------+-----+-----
+ | | | |
+ 21 | 22 | 23 | 24 | 25
+ | | | |
+
+
+ - Tile 19 has four adjacent tiles: 14, 18, 20, and 24.
+
+ - Tile G has four adjacent tiles: B, F, H, and L.
+
+ - Tile D has four adjacent tiles: 8, C, E, and I.
+
+ - Tile E has four adjacent tiles: 8, D, 14, and J.
+
+ - Tile 14 has eight adjacent tiles: 9, E, J, O, T, Y, 15, and 19.
+
+ - Tile N has eight adjacent tiles: I, O, S, and five tiles within the sub-grid marked ?.
+
+
+The rules about bugs living and dying are the same as before.
+
+For example, consider the same initial state as above:
+
+....#
+#..#.
+#.?##
+..#..
+#....
+
+The center tile is drawn as ? to indicate the next recursive grid. Call this level 0; the grid
+within this one is level 1, and the grid that contains this one is level -1. Then, after ten
+minutes, the grid at each level would look like this:
+
+Depth -5:
+..#..
+.#.#.
+..?.#
+.#.#.
+..#..
+
+Depth -4:
+...#.
+...##
+..?..
+...##
+...#.
+
+Depth -3:
+#.#..
+.#...
+..?..
+.#...
+#.#..
+
+Depth -2:
+.#.##
+....#
+..?.#
+...##
+.###.
+
+Depth -1:
+#..##
+...##
+..?..
+...#.
+.####
+
+Depth 0:
+.#...
+.#.##
+.#?..
+.....
+.....
+
+Depth 1:
+.##..
+#..##
+..?.#
+##.##
+#####
+
+Depth 2:
+###..
+##.#.
+#.?..
+.#.##
+#.#..
+
+Depth 3:
+..###
+.....
+#.?..
+#....
+#...#
+
+Depth 4:
+.###.
+#..#.
+#.?..
+##.#.
+.....
+
+Depth 5:
+####.
+#..#.
+#.?#.
+####.
+.....
+
+In this example, after 10 minutes, a total of 99 bugs are present.
+
+Starting with your scan, how many bugs are present after 200 minutes?
+
+
diff --git a/24/part2.c b/24/part2.c
@@ -0,0 +1,288 @@
+#include "allocator.h"
+#include "hmap.h"
+#include "hmap_s.h"
+#include "aoc.h"
+#include "vec_s.h"
+#include "dvec_s.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+struct layer {
+ char cells[5][5];
+ uint8_t adj[5][5];
+};
+
+struct cell {
+ size_t adj;
+ char c;
+};
+
+static void
+load_map(struct hmap *map)
+{
+ const char *lpos, *lend;
+ struct layer *layer;
+ size_t x, y, len;
+ char line[256];
+
+ y = 0;
+ layer = malloc(sizeof(struct layer));
+ lpos = aoc.input;
+ lend = lpos + aoc.input_size;
+ while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
+ len = strlen(line);
+ for (x = 0; x < len; x++)
+ layer->cells[y][x] = line[x];
+ y += 1;
+ }
+
+ hmap_add(map, (struct hmap_key) {.ss = 0},
+ (struct hmap_val) {.p = layer});
+}
+
+static void
+print_layer(struct hmap *map, ssize_t z)
+{
+ struct hmap_link *link;
+ const struct layer *layer;
+ size_t x, y;
+
+ link = hmap_get(map, (struct hmap_key) {.ss = z});
+ if (link) layer = link->value.p;
+ for (y = 0; y < 5; y++) {
+ for (x = 0; x < 5; x++) {
+ if (x == 2 && y == 2) {
+ aoc_debug("?");
+ } else if (link) {
+ aoc_debug("%c", layer->cells[y][x]);
+ } else {
+ aoc_debug(".");
+ }
+ }
+ aoc_debug("\n");
+ }
+}
+
+static void
+print_layers(struct hmap *map, ssize_t minz, ssize_t maxz)
+{
+ ssize_t z;
+
+ for (z = minz; z <= maxz; z++) {
+ aoc_debug("Z %li\n", z);
+ print_layer(map, z);
+ aoc_debug("\n");
+ }
+}
+
+static size_t
+map_count(struct hmap *map)
+{
+ const struct layer *layer;
+ struct hmap_iter iter;
+ size_t x, y, count;
+
+ count = 0;
+ for (HMAP_ITER(map, &iter)) {
+ layer = iter.link->value.p;
+ for (y = 0; y < 5; y++) {
+ for (x = 0; x < 5; x++) {
+ if (x == 2 && y == 2)
+ continue;
+ if (layer->cells[y][x] == '#')
+ count += 1;
+ }
+ }
+ }
+
+ return count;
+}
+
+static size_t
+top_cells(const struct layer *layer)
+{
+ size_t i, count;
+
+ count = 0;
+ for (i = 0; i < 5; i++)
+ count += layer->cells[0][i] == '#';
+
+ return count;
+}
+
+static size_t
+right_cells(const struct layer *layer)
+{
+ size_t i, count;
+
+ count = 0;
+ for (i = 0; i < 5; i++)
+ count += layer->cells[i][4] == '#';
+
+ return count;
+}
+
+static size_t
+bottom_cells(const struct layer *layer)
+{
+ size_t i, count;
+
+ count = 0;
+ for (i = 0; i < 5; i++)
+ count += layer->cells[4][i] == '#';
+
+ return count;
+}
+
+static size_t
+left_cells(const struct layer *layer)
+{
+ size_t i, count;
+
+ count = 0;
+ for (i = 0; i < 5; i++)
+ count += layer->cells[i][0] == '#';
+
+ return count;
+}
+
+static size_t
+cell_count(struct hmap *map, struct layer *layer,
+ struct vec2i *pos, size_t dir, ssize_t z)
+{
+ struct hmap_link *link;
+ const struct layer *nlayer;
+ size_t count;
+
+ count = 0;
+ if (pos->x == 2 && pos->y == 2) {
+ link = hmap_get(map, (struct hmap_key) {.ss = z + 1});
+ if (!link) return 0;
+ nlayer = link->value.p;
+ switch (dir) {
+ case ADJ_NORTH:
+ return bottom_cells(nlayer);
+ case ADJ_EAST:
+ return left_cells(nlayer);
+ case ADJ_SOUTH:
+ return top_cells(nlayer);
+ case ADJ_WEST:
+ return right_cells(nlayer);
+ }
+ return count;
+ } else if (pos->x < 0 || pos->x >= 5 || pos->y < 0 || pos->y >= 5) {
+ link = hmap_get(map, (struct hmap_key) {.ss = z - 1});
+ if (!link) return 0;
+ nlayer = link->value.p;
+ if (pos->x < 0) {
+ return nlayer->cells[2][1] == '#';
+ } else if (pos->x >= 5) {
+ return nlayer->cells[2][3] == '#';
+ } else if (pos->y < 0) {
+ return nlayer->cells[1][2] == '#';
+ } else if (pos->y >= 5) {
+ return nlayer->cells[3][2] == '#';
+ }
+ } else {
+ return layer->cells[pos->y][pos->x] == '#';
+ }
+
+ assert(0);
+}
+
+static void
+step(struct hmap *map)
+{
+ struct hmap_iter iter;
+ struct hmap_link **linkp;
+ struct hmap_link *link;
+ struct vec2i pos, npos;
+ ssize_t z, minz, maxz;
+ struct layer *layer;
+ size_t i, count;
+ char *cell;
+
+ minz = maxz = 0;
+ for (HMAP_ITER(map, &iter)) {
+ layer = iter.link->value._p;
+ if (memchr(layer->cells, '#', 5 * 5)) {
+ minz = MIN(minz, iter.link->key.ss);
+ maxz = MAX(maxz, iter.link->key.ss);
+ }
+ }
+ minz -= 1;
+ maxz += 1;
+
+ for (z = minz; z <= maxz; z++) {
+ linkp = hmap_link_pos(map,
+ (struct hmap_key) {.ss = z});
+ if (!*linkp) {
+ layer = malloc(sizeof(struct layer));
+ memset(layer->cells, '.', 5 * 5);
+ hmap_link_alloc(map, linkp,
+ (struct hmap_key) {.ss = z},
+ (struct hmap_val) {.p = layer});
+ } else {
+ layer = (*linkp)->value._p;
+ }
+
+ for (pos.y = 0; pos.y < 5; pos.y++) {
+ for (pos.x = 0; pos.x < 5; pos.x++) {
+ count = 0;
+ for (i = 0; i < 4; i++) {
+ vec2i_add(&npos, &pos, &adj[i]);
+ count += cell_count(map,
+ layer, &npos, i, z);
+ }
+ layer->adj[pos.y][pos.x] = (uint8_t) count;
+ }
+ }
+ }
+
+ for (z = minz; z <= maxz; z++) {
+ for (pos.y = 0; pos.y < 5; pos.y++) {
+ for (pos.x = 0; pos.x < 5; pos.x++) {
+ link = hmap_get(map,
+ (struct hmap_key) {.ss = z});
+ layer = link->value._p;
+ cell = &layer->cells[pos.y][pos.x];
+ count = layer->adj[pos.y][pos.x];
+ if (*cell == '#' && count != 1) {
+ *cell = '.';
+ } else if (*cell == '.' && (count == 1 || count == 2)) {
+ *cell = '#';
+ }
+ }
+ }
+ }
+}
+
+
+void
+part2(void)
+{
+ struct hmap_iter iter;
+ struct hmap map;
+ size_t i, answer;
+
+ hmap_init(&map, 32, ssizet_hmap_hash, ssizet_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ load_map(&map);
+
+ for (i = 0; i < 200; i++) {
+ step(&map);
+ aoc_debug("-- MIN %lu --\n\n", i);
+ print_layers(&map, -5, 5);
+ }
+
+ answer = map_count(&map);
+ aoc.answer = aprintf("%lu", answer);
+
+ for (HMAP_ITER(&map, &iter))
+ free(iter.link->value._p);
+ hmap_deinit(&map);
+}
diff --git a/24/test1 b/24/test1
@@ -0,0 +1,5 @@
+#..#.
+####.
+###.#
+##.##
+.##..
diff --git a/24/test2 b/24/test2
@@ -0,0 +1,5 @@
+....#
+#..#.
+#.?##
+..#..
+#....
diff --git a/common/hmap_s.c b/common/hmap_s.c
@@ -36,13 +36,13 @@ vec3i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
}
uint32_t
-sizet_hmap_hash(struct hmap_key key)
+ssizet_hmap_hash(struct hmap_key key)
{
- return (uint32_t) key.s * 1737;
+ return (uint32_t) (key.s * 1737);
}
bool
-sizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+ssizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
{
- return k1.s == k2.s;
+ return k1.ss == k2.ss;
}
diff --git a/common/hmap_s.h b/common/hmap_s.h
@@ -6,5 +6,5 @@ bool vec2i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
uint32_t vec3i_hmap_hash(struct hmap_key key);
bool vec3i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
-uint32_t sizet_hmap_hash(struct hmap_key key);
-bool sizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
+uint32_t ssizet_hmap_hash(struct hmap_key key);
+bool ssizet_hmap_keycmp(struct hmap_key k1, struct hmap_key k2);
diff --git a/common/vec.h b/common/vec.h
@@ -128,6 +128,14 @@ vec3f_setv(struct vec3f *dst, double x, double y, double z)
dst->z = z;
}
+static inline void
+vec3i_add_2i(struct vec3i *dst, const struct vec3i *a, const struct vec2i *b)
+{
+ dst->x = a->x + b->x;
+ dst->y = a->y + b->y;
+ dst->z = a->z;
+}
+
#undef DEFINE_VEC_SET
#undef DEFINE_VEC_ADD
#undef DEFINE_VEC_SUB
