commit 46c71563e0f52a64d3f88cff120701db947383a4
parent a17aa0ba3f116c495aa76e79c449fa80d96c766a
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 10 Nov 2021 01:47:56 +0100
Add day 10 and modified hashmap implementation
Diffstat:
9 files changed, 580 insertions(+), 28 deletions(-)
diff --git a/libs/include/hashmap.h b/libs/include/hashmap.h
@@ -31,11 +31,12 @@ struct hashmap {
};
void hashmap_init(struct hashmap *hm, int size, uint32_t (*hasher)(void *key, int len));
+void hashmap_clear(struct hashmap *hm);
void hashmap_free(struct hashmap *hm);
void hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value);
-void * hashmap_get(struct hashmap *hm, struct hashmap_key key);
-void * hashmap_pop(struct hashmap *hm, struct hashmap_key key);
+int hashmap_get(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst);
+int hashmap_pop(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst);
struct hashmap_iter hashmap_iter(void);
int hashmap_next(struct hashmap *hm, struct hashmap_iter *next);
diff --git a/libs/src/hashmap.c b/libs/src/hashmap.c
@@ -11,7 +11,7 @@ hashmap_init(struct hashmap *hm, int size, uint32_t (*hasher)(void *key, int len
}
void
-hashmap_free(struct hashmap *hm)
+hashmap_clear(struct hashmap *hm)
{
struct hashmap_iter iter;
struct hashmap_link *prev;
@@ -24,26 +24,19 @@ hashmap_free(struct hashmap *hm)
prev = iter.link;
}
free(prev);
- free(hm->buckets);
- hm->buckets = NULL;
+ memset(hm->buckets, 0, hm->size * sizeof(struct hashmap_link *));
}
void
-hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
+hashmap_free(struct hashmap *hm)
{
- struct hashmap_link **iter;
-
- iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
- while (*iter) iter = &((*iter)->next);
-
- *iter = CHKP(malloc(sizeof(struct hashmap_link)));
- (*iter)->key = key;
- (*iter)->value = value;
- (*iter)->next = NULL;
+ hashmap_clear(hm);
+ free(hm->buckets);
+ hm->buckets = NULL;
}
-void *
-hashmap_get(struct hashmap *hm, struct hashmap_key key)
+int
+hashmap_get(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst)
{
struct hashmap_link **iter;
struct hashmap_key ckey;
@@ -51,34 +44,48 @@ hashmap_get(struct hashmap *hm, struct hashmap_key key)
iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
while (*iter) {
ckey = (*iter)->key;
- if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len))
- return (*iter)->value;
+ if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len)) {
+ if (dst) *dst = *iter;
+ return 1;
+ }
iter = &((*iter)->next);
}
- return NULL;
+ return 0;
}
-void *
-hashmap_pop(struct hashmap *hm, struct hashmap_key key)
+int
+hashmap_pop(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst)
{
struct hashmap_link **iter;
struct hashmap_key ckey;
- void *value;
iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
while (*iter) {
ckey = (*iter)->key;
if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len)) {
*iter = (*iter)->next;
- value = (*iter)->value;
- free(*iter);
- return value;
+ if (dst) *dst = *iter;
+ return 1;
}
iter = &((*iter)->next);
}
- return NULL;
+ return 0;
+}
+
+void
+hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
+{
+ struct hashmap_link **iter;
+
+ iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
+ while (*iter) iter = &((*iter)->next);
+
+ *iter = CHKP(malloc(sizeof(struct hashmap_link)));
+ (*iter)->key = key;
+ (*iter)->value = value;
+ (*iter)->next = NULL;
}
struct hashmap_iter
diff --git a/src/06/main.c b/src/06/main.c
@@ -18,7 +18,11 @@ struct hashmap planets;
struct planet *
get_planet(const char *name)
{
- return hashmap_get(&planets, HASHMAP_KEY(name, strlen(name)));
+ struct hashmap_link *link;
+ int status;
+
+ status = hashmap_get(&planets, HASHMAP_KEY(name, strlen(name)), &link);
+ return status ? link->value : NULL;
}
struct planet *
diff --git a/src/10/Makefile b/src/10/Makefile
@@ -0,0 +1,12 @@
+CFLAGS = -g -I ../../libs/include -L ../../libs/build
+LDLIBS = -laoc -lm
+
+all: lib main
+
+clean:
+ rm main
+
+lib:
+ make -C ../../libs
+
+main: main.c ../../libs/build/libaoc.a
diff --git a/src/10/input b/src/10/input
@@ -0,0 +1,39 @@
+.............#..#.#......##........#..#
+.#...##....#........##.#......#......#.
+..#.#.#...#...#...##.#...#.............
+.....##.................#.....##..#.#.#
+......##...#.##......#..#.......#......
+......#.....#....#.#..#..##....#.......
+...................##.#..#.....#.....#.
+#.....#.##.....#...##....#####....#.#..
+..#.#..........#..##.......#.#...#....#
+...#.#..#...#......#..........###.#....
+##..##...#.#.......##....#.#..#...##...
+..........#.#....#.#.#......#.....#....
+....#.........#..#..##..#.##........#..
+........#......###..............#.#....
+...##.#...#.#.#......#........#........
+......##.#.....#.#.....#..#.....#.#....
+..#....#.###..#...##.#..##............#
+...##..#...#.##.#.#....#.#.....#...#..#
+......#............#.##..#..#....##....
+.#.#.......#..#...###...........#.#.##.
+........##........#.#...#.#......##....
+.#.#........#......#..........#....#...
+...............#...#........##..#.#....
+.#......#....#.......#..#......#.......
+.....#...#.#...#...#..###......#.##....
+.#...#..##................##.#.........
+..###...#.......#.##.#....#....#....#.#
+...#..#.......###.............##.#.....
+#..##....###.......##........#..#...#.#
+.#......#...#...#.##......#..#.........
+#...#.....#......#..##.............#...
+...###.........###.###.#.....###.#.#...
+#......#......#.#..#....#..#.....##.#..
+.##....#.....#...#.##..#.#..##.......#.
+..#........#.......##.##....#......#...
+##............#....#.#.....#...........
+........###.............##...#........#
+#.........#.....#..##.#.#.#..#....#....
+..............##.#.#.#...........#.....
diff --git a/src/10/main.c b/src/10/main.c
@@ -0,0 +1,247 @@
+#include "aoc.h"
+#include "hashmap.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+
+struct asteroid {
+ int x, y;
+
+ struct asteroid *next;
+};
+
+struct dir {
+ int dx, dy;
+};
+
+struct asteroid *asteroids;
+int width, height;
+
+uint32_t
+dir_hasher(void *dp, int len)
+{
+ struct dir *d;
+ uint32_t hash;
+
+ d = dp;
+ hash = ((uint16_t) d->dx & 0xFFFF);
+ hash |= ((uint16_t) d->dy & 0xFFFF) << 16;
+
+ return hash;
+}
+
+void
+add_asteroid(int x, int y)
+{
+ struct asteroid **iter;
+
+ for (iter = &asteroids; *iter; iter = &((*iter)->next));
+
+ *iter = CHKP(malloc(sizeof(struct asteroid)));
+ (*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_free(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 hashmap *hm, struct asteroid *a1)
+{
+ struct hashmap_key key;
+ struct hashmap_link *link;
+ struct asteroid *a2, *tmp;
+ struct dir dir, odir, *dira;
+
+ 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);
+
+ if (hashmap_get(hm, HASHMAP_KEY(&dir, sizeof(dir)), &link)) {
+ tmp = link->value;
+ 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 = a2;
+ } else {
+ key = HASHMAP_KEY(CHKP(memdup(&dir, sizeof(dir))), sizeof(dir));
+ hashmap_set(hm, key, a2);
+ }
+ }
+}
+
+float
+angle(struct asteroid *a, struct asteroid *base)
+{
+ double ang;
+
+ if (a->x == base->x)
+ return a->y > base->y ? 0 : -M_PI;
+ return atan2(base->x - a->x, a->y - base->y);
+}
+
+void
+find_base(struct asteroid **a_out, int *vis_out)
+{
+ struct asteroid *a1, *cand;
+ struct hashmap_iter iter;
+ struct hashmap dirmap;
+ int vis, maxvis;
+
+ hashmap_init(&dirmap, 100, dir_hasher);
+
+ maxvis = 0;
+ for (a1 = asteroids; a1; a1 = a1->next) {
+ debug("Asteroid @ %i,%i => ", a1->x, a1->y);
+ get_vis(&dirmap, a1);
+
+ vis = 0;
+ iter = hashmap_iter();
+ while (hashmap_next(&dirmap, &iter))
+ vis++;
+
+ debug("%i vis\n", vis);
+ if (maxvis == 0 || vis > maxvis) {
+ maxvis = vis;
+ cand = a1;
+ }
+
+ hashmap_clear(&dirmap);
+ }
+
+ ASSERT(cand != NULL);
+ hashmap_free(&dirmap);
+
+ if (vis_out) *vis_out = maxvis;
+ if (a_out) *a_out = cand;
+}
+
+void
+part1(void)
+{
+ struct asteroid *a;
+ int vis;
+
+ asteroids_init();
+ find_base(&a, &vis);
+
+ debug("Best at %i,%i with %i vis\n", a->x, a->y, vis);
+ aoc.answer = CHKP(aprintf("%i", vis));
+ aoc.solution = "299";
+
+ asteroids_free();
+}
+
+void
+part2(void)
+{
+ struct asteroid *base, *tmp;
+ struct hashmap_iter iter;
+ struct asteroid **list;
+ struct hashmap dirmap;
+ float prev, ang;
+ int i, k, len;
+
+ asteroids_init();
+ find_base(&base, NULL);
+
+ hashmap_init(&dirmap, 100, dir_hasher);
+ get_vis(&dirmap, base);
+
+ len = 0;
+ iter = hashmap_iter();
+ while (hashmap_next(&dirmap, &iter))
+ len++;
+
+ list = CHKP(malloc(sizeof(struct asteroid *) * len));
+
+ iter = hashmap_iter();
+ for (i = 0; hashmap_next(&dirmap, &iter); i++)
+ list[i] = iter.link->value;
+
+ 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++) {
+ debug("%i: %i %i %f\n", k+1, list[k]->x, list[k]->y, angle(list[k], base));
+ }
+
+ aoc.answer = CHKP(aprintf("%i", list[199]->x * 100 + list[199]->y));
+
+ asteroids_free();
+ hashmap_free(&dirmap);
+}
diff --git a/src/10/part1 b/src/10/part1
@@ -0,0 +1,130 @@
+--- Day 10: Monitoring Station ---
+
+You fly into the asteroid belt and reach the Ceres monitoring station. The Elves here have an
+emergency: they're having trouble tracking all of the asteroids and can't be sure they're safe.
+
+The Elves would like to build a new monitoring station in a nearby area of space; they hand you a
+map of all of the asteroids in that region (your puzzle input).
+
+The map indicates whether each position is empty (.) or contains an asteroid (#). The asteroids are
+much smaller than they appear on the map, and every asteroid is exactly in the center of its marked
+position. The asteroids can be described with X,Y coordinates where X is the distance from the left
+edge and Y is the distance from the top edge (so the top-left corner is 0,0 and the position
+immediately to its right is 1,0).
+
+Your job is to figure out which asteroid would be the best place to build a [1m[37mnew monitoring
+station[0m. A monitoring station can [1m[37mdetect[0m any asteroid to which it has
+[1m[37mdirect line of sight[0m - that is, there cannot be another asteroid [1m[37mexactly[0m
+between them. This line of sight can be at any angle, not just lines aligned to the grid or
+diagonally. The [1m[37mbest[0m location is the asteroid that can [1m[37mdetect[0m the largest
+number of other asteroids.
+
+For example, consider the following map:
+
+.#..#
+.....
+#####
+....#
+...[1m[37m#[0m#
+
+The best location for a new monitoring station on this map is the highlighted asteroid at 3,4
+because it can detect 8 asteroids, more than any other location. (The only asteroid it cannot detect
+is the one at 1,0; its view of this asteroid is blocked by the asteroid at 2,2.) All other asteroids
+are worse locations; they can detect 7 or fewer other asteroids. Here is the number of other
+asteroids a monitoring station on each asteroid could detect:
+
+.7..7
+.....
+67775
+....7
+...87
+
+Here is an asteroid (#) and some examples of the ways its line of sight might be blocked. If there
+were another asteroid at the location of a capital letter, the locations marked with the
+corresponding lowercase letter would be blocked and could not be detected:
+
+#.........
+...A......
+...B..a...
+.EDCG....a
+..F.c.b...
+.....c....
+..efd.c.gb
+.......c..
+....f...c.
+...e..d..c
+
+Here are some larger examples:
+
+
+ - Best is 5,8 with 33 other asteroids detected:
+
+......#.#.
+#..#.#....
+..#######.
+.#.#.###..
+.#..#.....
+..#....#.#
+#..#....#.
+.##.#..###
+##...[1m[37m#[0m..#.
+.#....####
+
+
+ - Best is 1,2 with 35 other asteroids detected:
+
+#.#...#.#.
+.###....#.
+.[1m[37m#[0m....#...
+##.#.#.#.#
+....#.#.#.
+.##..###.#
+..#...##..
+..##....##
+......#...
+.####.###.
+
+
+ - Best is 6,3 with 41 other asteroids detected:
+
+.#..#..###
+####.###.#
+....###.#.
+..###.[1m[37m#[0m#.#
+##.##.#.#.
+....###..#
+..#.#..#.#
+#..#.#.###
+.##...##.#
+.....#.#..
+
+
+ - Best is 11,13 with 210 other asteroids detected:
+
+.#..##.###...#######
+##.############..##.
+.#.######.########.#
+.###.#######.####.#.
+#####.##.#.##.###.##
+..#####..#.#########
+####################
+#.####....###.#.#.##
+##.#################
+#####.##.###..####..
+..######..##.#######
+####.##.####...##..#
+.#####..#.######.###
+##...#.####[1m[37m#[0m#####...
+#.##########.#######
+.####.#.###.###.#.##
+....##.##.###..#####
+.#.#.###########.###
+#.#.#.#####.####.###
+###.##.####.##.#..##
+
+
+
+Find the best location for a new monitoring station. [1m[37mHow many other asteroids can be
+detected from that location?[0m
+
+
diff --git a/src/10/part2 b/src/10/part2
@@ -0,0 +1,92 @@
+--- Part Two ---
+
+Once you give them the coordinates, the Elves quickly deploy an Instant Monitoring Station to the
+location and discover the worst: there are simply too many asteroids.
+
+The only solution is [1m[37mcomplete vaporization by giant laser[0m.
+
+Fortunately, in addition to an asteroid scanner, the new monitoring station also comes equipped with
+a giant rotating laser perfect for vaporizing asteroids. The laser starts by pointing
+[1m[37mup[0m and always rotates [1m[37mclockwise[0m, vaporizing any asteroid it hits.
+
+If multiple asteroids are [1m[37mexactly[0m in line with the station, the laser only has enough
+power to vaporize [1m[37mone[0m of them before continuing its rotation. In other words, the same
+asteroids that can be [1m[37mdetected[0m can be vaporized, but if vaporizing one asteroid makes
+another one detectable, the newly-detected asteroid won't be vaporized until the laser has returned
+to the same position by rotating a full 360 degrees.
+
+For example, consider the following map, where the asteroid with the new monitoring station (and
+laser) is marked X:
+
+.#....#####...#..
+##...##.#####..##
+##...#...#.#####.
+..#.....X...###..
+..#.#.....#....##
+
+The first nine asteroids to get vaporized, in order, would be:
+
+.#....###[1m[37m2[0m[1m[37m4[0m...#..
+##...##.[1m[37m1[0m[1m[37m3[0m#[1m[37m6[0m[1m[37m7[0m..[1m[37m9[0m#
+##...#...[1m[37m5[0m.[1m[37m8[0m####.
+..#.....X...###..
+..#.#.....#....##
+
+Note that some asteroids (the ones behind the asteroids marked 1, 5, and 7) won't have a chance to
+be vaporized until the next full rotation. The laser continues rotating; the next nine to be
+vaporized are:
+
+.#....###.....#..
+##...##...#.....#
+##...#......[1m[37m1[0m[1m[37m2[0m[1m[37m3[0m[1m[37m4[0m.
+..#.....X...[1m[37m5[0m##..
+..#.[1m[37m9[0m.....[1m[37m8[0m....[1m[37m7[0m[1m[37m6[0m
+
+The next nine to be vaporized are then:
+
+.[1m[37m8[0m....###.....#..
+[1m[37m5[0m[1m[37m6[0m...[1m[37m9[0m#...#.....#
+[1m[37m3[0m[1m[37m4[0m...[1m[37m7[0m...........
+..[1m[37m2[0m.....X....##..
+..[1m[37m1[0m..............
+
+Finally, the laser completes its first full rotation (1 through 3), a second rotation (4 through 8),
+and vaporizes the last asteroid (9) partway through its third rotation:
+
+......[1m[37m2[0m[1m[37m3[0m[1m[37m4[0m.....[1m[37m6[0m..
+......[1m[37m1[0m...[1m[37m5[0m.....[1m[37m7[0m
+.................
+........X....[1m[37m8[0m[1m[37m9[0m..
+.................
+
+In the large example above (the one with the best monitoring station location at 11,13):
+
+
+ - The 1st asteroid to be vaporized is at 11,12.
+
+ - The 2nd asteroid to be vaporized is at 12,1.
+
+ - The 3rd asteroid to be vaporized is at 12,2.
+
+ - The 10th asteroid to be vaporized is at 12,8.
+
+ - The 20th asteroid to be vaporized is at 16,0.
+
+ - The 50th asteroid to be vaporized is at 16,9.
+
+ - The 100th asteroid to be vaporized is at 10,16.
+
+ - The 199th asteroid to be vaporized is at 9,6.
+
+ - [1m[37mThe 200th asteroid to be vaporized is at 8,2.[0m
+
+ - The 201st asteroid to be vaporized is at 10,9.
+
+ - The 299th and final asteroid to be vaporized is at 11,1.
+
+
+The Elves are placing bets on which will be the [1m[37m200th[0m asteroid to be vaporized. Win
+the bet by determining which asteroid that will be; [1m[37mwhat do you get if you multiply its X
+coordinate by 100 and then add its Y coordinate?[0m (For example, 8,2 becomes [1m[37m802[0m.)
+
+
diff --git a/src/10/test.input b/src/10/test.input
@@ -0,0 +1,20 @@
+.#..##.###...#######
+##.############..##.
+.#.######.########.#
+.###.#######.####.#.
+#####.##.#.##.###.##
+..#####..#.#########
+####################
+#.####....###.#.#.##
+##.#################
+#####.##.###..####..
+..######..##.#######
+####.##.####...##..#
+.#####..#.######.###
+##...#.##########...
+#.##########.#######
+.####.#.###.###.#.##
+....##.##.###..#####
+.#.#.###########.###
+#.#.#.#####.####.###
+###.##.####.##.#..##
