aoc-2019-c

commit d670b95b371a9ee99df7b2f0e4c373fd57e48220
parent 347f52c467baff5257ee25e59b0688dac823abbe
Author: Louis Burda <quent.burda@gmail.com>
Date:   Fri, 24 Mar 2023 21:57:56 +0100

Add vector calculation helper

Diffstat:
M
15/main.c
 | 
96
+++++++++++++++++++++++++++++++------------------------------------------------
A
common/vec.h
 | 
116
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 153 insertions(+), 59 deletions(-)
diff --git a/15/main.c b/15/main.c
@@ -3,6 +3,7 @@
 #include "aoc.h"
 #include "iccmp.h"
 #include "hmap.h"
+#include "vec.h"
 
 #include <assert.h>
 #include <stdbool.h>
@@ -23,10 +24,6 @@ enum {
 	BLOCK_GOAL
 };
 
-struct vec2 {
-	int x, y;
-};
-
 struct state {
 	int back;
 	int next;
@@ -38,7 +35,7 @@ const char block_lut[] = {
 	'O'
 };
 
-const struct vec2 dirs[] = {
+const struct vec2i dirs[] = {
 	{ 0 },
 	{ 0, -1 },
 	{ 0, 1 },
@@ -53,7 +50,7 @@ const int rev[] = {
 uint32_t
 vec_hmap_hash(struct hmap_key key)
 {
-	const struct vec2 *vec = key.p;
+	const struct vec2i *vec = key.p;
 
 	return (uint32_t) (vec->x << 16) ^ (uint32_t) vec->y;
 }
@@ -61,7 +58,7 @@ vec_hmap_hash(struct hmap_key key)
 bool
 vec_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
 {
-	const struct vec2 *v1 = k1.p, *v2 = k2.p;
+	const struct vec2i *v1 = k1.p, *v2 = k2.p;
 
 	return v1->x == v2->x && v1->y == v2->y;
 }
@@ -69,21 +66,6 @@ vec_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
 int
 robot_move(struct icc *icc, int dir)
 {
-//	static struct vec2 pos = { 0 };
-//	struct vec2 npos;
-//
-//	npos.x = pos.x + dirs[dir].x;
-//	npos.y = pos.y + dirs[dir].y;
-//
-//
-//	if (ABS(npos.x) + ABS(npos.y) > 10)
-//		return BLOCK_WALL;
-//
-//	pos.x = npos.x;
-//	pos.y = npos.y;
-//
-//	return BLOCK_OPEN;
-//
 	while (icc->state != ICC_HALT) {
 		icc_step_inst(icc);
 		switch (icc->state) {
@@ -102,14 +84,14 @@ robot_move(struct icc *icc, int dir)
 }
 
 void
-print_map(struct hmap *map, struct vec2 droid)
+print_map(struct hmap *map, struct vec2i droid)
 {
 	struct hmap_link *link;
 	struct hmap_iter iter;
-	struct vec2 min = { 0 };
-	struct vec2 max = { 0 };
-	struct vec2 pos;
-	const struct vec2 *vec;
+	struct vec2i min = { 0 };
+	struct vec2i max = { 0 };
+	struct vec2i pos;
+	const struct vec2i *vec;
 
 	for (HMAP_ITER(map, &iter)) {
 		vec = iter.link->key.p;
@@ -149,49 +131,46 @@ print_map(struct hmap *map, struct vec2 droid)
 }
 
 size_t
-dijkstra_dist(struct hmap *map, struct vec2 start, const struct vec2 *end)
+dijkstra_dist(struct hmap *map, struct vec2i start, const struct vec2i *end)
 {
 	struct hmap_link *link, **linkp;
 	struct hmap_iter iter;
 	struct hmap seen;
 	struct dvec outer;
-	struct vec2 *vec;
-	struct vec2 pos, npos;
+	struct vec2i *vec;
+	struct vec2i pos, npos;
 	size_t dist, maxdist;
 	void *key;
 	int dir;
 
 	hmap_init(&seen, 32, vec_hmap_hash, vec_hmap_keycmp,
 		&stdlib_strict_heap_allocator);
-	dvec_init(&outer, sizeof(struct vec2),
+	dvec_init(&outer, sizeof(struct vec2i),
 		10, &stdlib_strict_heap_allocator);
 
 	vec = dvec_add_slot(&outer, NULL);
-	vec->x = start.x;
-	vec->y = start.y;
+	vec2i_set(vec, &start);
 
-	key = memdup(vec, sizeof(struct vec2));
+	key = memdup(vec, sizeof(struct vec2i));
 	hmap_add(&seen, (struct hmap_key) {.p = key},
 		(struct hmap_val) {.s = 0});
 
 	maxdist = 0;
 	while (!dvec_empty(&outer)) {
 		vec = dvec_back(&outer);
-		pos.x = vec->x;
-		pos.y = vec->y;
+		vec2i_set(&pos, vec);
 		link = hmap_get(&seen, (struct hmap_key) {.p = &pos});
 		assert(link);
 		dist = link->value.s + 1;
 		dvec_rm_slot(&outer, vec);
 
 		for (dir = 1; dir <= 4; dir++) {
-			npos.x = pos.x + dirs[dir].x;
-			npos.y = pos.y + dirs[dir].y;
+			vec2i_add(&npos, &pos, &dirs[dir]);
 			linkp = hmap_link_pos(&seen,
 				(struct hmap_key) {.p = &npos});
 			if (*linkp) continue;
 
-			if (end && !memcmp(&npos, end, sizeof(struct vec2)))
+			if (end && !memcmp(&npos, end, sizeof(struct vec2i)))
 				goto exit;
 
 			link = hmap_get(map, (struct hmap_key) {.p = &npos});
@@ -202,9 +181,8 @@ dijkstra_dist(struct hmap *map, struct vec2 start, const struct vec2 *end)
 				maxdist = dist;
 
 			vec = dvec_add_slot(&outer, NULL);
-			vec->x = npos.x;
-			vec->y = npos.y;
-			key = memdup(&npos, sizeof(struct vec2));
+			vec2i_set(vec, &npos);
+			key = memdup(&npos, sizeof(struct vec2i));
 			hmap_link_alloc(&seen, linkp,
 				(struct hmap_key) {.p = key},
 				(struct hmap_val) {.s = dist});
@@ -222,12 +200,12 @@ exit:
 
 void
 explore_map(struct icc *icc, struct hmap *map,
-	struct vec2 start, struct vec2 *tank)
+	struct vec2i start, struct vec2i *tank)
 {
 	struct hmap_link **linkp;
 	struct hmap_link *link;
 	struct dvec states;
-	struct vec2 pos, npos;
+	struct vec2i pos, npos;
 	struct state *state;
 	int move_result;
 	int move_dir;
@@ -240,8 +218,8 @@ explore_map(struct icc *icc, struct hmap *map,
 	state->back = -1;
 	state->next = 1;
 
-	pos = (struct vec2) { start.x, start.y };
-	key = memdup(&pos, sizeof(struct vec2));
+	vec2i_set(&pos, &start);
+	key = memdup(&pos, sizeof(struct vec2i));
 	hmap_add(map, (struct hmap_key) {.p = key},
 		(struct hmap_val) {.c = '.'});
 
@@ -252,8 +230,7 @@ explore_map(struct icc *icc, struct hmap *map,
 			if (state->next == state->back)
 				continue;
 			move_dir = state->next;
-			npos.x = pos.x + dirs[move_dir].x;
-			npos.y = pos.y + dirs[move_dir].y;
+			vec2i_add(&npos, &pos, &dirs[move_dir]);
 			link = hmap_get(map,
 				(struct hmap_key) {.p = &npos});
 			if (!link) break;
@@ -263,8 +240,7 @@ explore_map(struct icc *icc, struct hmap *map,
 			if (state->back <= 0) break;
 			move_result = robot_move(icc, state->back);
 			assert(move_result == BLOCK_OPEN);
-			pos.x += dirs[state->back].x;
-			pos.y += dirs[state->back].y;
+			vec2i_add(&pos, &pos, &dirs[state->back]);
 			dvec_rm_slot(&states, state);
 			if (aoc.debug) {
 				aoc_debug("Step: backtrack x %i y %i\n", pos.x, pos.y);
@@ -283,7 +259,7 @@ explore_map(struct icc *icc, struct hmap *map,
 		if (*linkp) {
 			(*linkp)->value.c = block_lut[move_result];
 		} else {
-			key = memdup(&npos, sizeof(struct vec2));
+			key = memdup(&npos, sizeof(struct vec2i));
 			hmap_link_alloc(map, linkp,
 				(struct hmap_key) {.p = key},
 				(struct hmap_val) {.c = block_lut[move_result]});
@@ -291,11 +267,9 @@ explore_map(struct icc *icc, struct hmap *map,
 
 		switch (move_result) {
 		case BLOCK_GOAL:
-			tank->x = npos.x;
-			tank->y = npos.y;
+			vec2i_set(tank, &npos);
 		case BLOCK_OPEN:
-			pos.x = npos.x;
-			pos.y = npos.y;
+			vec2i_set(&pos, &npos);
 			state = dvec_add_slot(&states, NULL);
 			state->back = rev[move_dir];
 			state->next = 1;
@@ -323,7 +297,7 @@ part1(void)
 	struct icc icc;
 	struct hmap_iter iter;
 	struct hmap map;
-	struct vec2 start, tank;
+	struct vec2i start, tank;
 	size_t dist;
 
 	icc_init(&icc);
@@ -332,11 +306,13 @@ part1(void)
 
 	icc_parse_inst(&icc, aoc.input, aoc.input_size);
 
-	start = (struct vec2) { 0, 0 };
+	start = (struct vec2i) { 0, 0 };
 	explore_map(&icc, &map, start, &tank);
 
 	dist = dijkstra_dist(&map, start, &tank);
+
 	aoc.answer = aprintf("%lu", dist);
+	aoc.solution = "234";
 
 	for (HMAP_ITER(&map, &iter))
 		free(iter.link->key._p);
@@ -350,7 +326,7 @@ part2(void)
 	struct icc icc;
 	struct hmap_iter iter;
 	struct hmap map;
-	struct vec2 start, tank;
+	struct vec2i start, tank;
 	size_t dist;
 
 	icc_init(&icc);
@@ -359,11 +335,13 @@ part2(void)
 
 	icc_parse_inst(&icc, aoc.input, aoc.input_size);
 
-	start = (struct vec2) { 0, 0 };
+	start = (struct vec2i) { 0, 0 };
 	explore_map(&icc, &map, start, &tank);
 
 	dist = dijkstra_dist(&map, tank, NULL);
+
 	aoc.answer = aprintf("%lu", dist);
+	aoc.solution = "292";
 
 	for (HMAP_ITER(&map, &iter))
 		free(iter.link->key._p);
diff --git a/common/vec.h b/common/vec.h
@@ -0,0 +1,116 @@
+#include <string.h>
+#include <stdlib.h>
+
+struct vec2i {
+	union {
+		struct {
+			ssize_t x, y;
+		};
+		ssize_t dims[2];
+	};
+};
+
+struct vec3i {
+	union {
+		struct {
+			ssize_t x, y, z;
+		};
+		ssize_t dims[3];
+	};
+};
+
+struct vec2f {
+	union {
+		struct {
+			double x, y;
+		};
+		double dims[2];
+	};
+};
+
+struct vec3f {
+	union {
+		struct {
+			double x, y, z;
+		};
+		double dims[3];
+	};
+};
+
+#define DEFINE_VEC_SET(name, type, dims) \
+	static inline void name(type *dst, type *src) { \
+		memcpy(dst, src, sizeof(type)); \
+	}
+
+#define DEFINE_VEC_ADD(name, type, n) \
+	static inline void name(type *dst, const type *a, const type *b) { \
+		for (int i = 0; i < n; i++) \
+			dst->dims[i] = a->dims[i] + b->dims[i]; \
+	}
+
+#define DEFINE_VEC_SUB(name, type, n) \
+	static inline void name(type *dst, const type *a, const type *b) { \
+		for (int i = 0; i < n; i++) \
+			dst->dims[i] = a->dims[i] - b->dims[i]; \
+	}
+
+#define DEFINE_VEC_MUL(name, type, prim, n) \
+	static inline void name(type *dst, const type *a, prim b) { \
+		for (int i = 0; i < n; i++) \
+			dst->dims[i] = a->dims[i] * b; \
+	}
+
+DEFINE_VEC_SET(vec2i_set, struct vec2i, 2);
+DEFINE_VEC_ADD(vec2i_add, struct vec2i, 2);
+DEFINE_VEC_SUB(vec2i_sub, struct vec2i, 2);
+DEFINE_VEC_MUL(vec2i_mul, struct vec2i, ssize_t, 2);
+
+static inline void
+vec2i_setv(struct vec2i *dst, ssize_t x, ssize_t y)
+{
+	dst->x = x;
+	dst->y = y;
+}
+
+DEFINE_VEC_SET(vec3i_set, struct vec3i, 3);
+DEFINE_VEC_ADD(vec3i_add, struct vec3i, 3);
+DEFINE_VEC_SUB(vec3i_sub, struct vec3i, 3);
+DEFINE_VEC_MUL(vec3i_mul, struct vec3i, ssize_t, 3);
+
+static inline void
+vec3i_setv(struct vec3i *dst, ssize_t x, ssize_t y, ssize_t z)
+{
+	dst->x = x;
+	dst->y = y;
+	dst->z = z;
+}
+
+DEFINE_VEC_SET(vec2f_set, struct vec2f, 2);
+DEFINE_VEC_ADD(vec2f_add, struct vec2f, 2);
+DEFINE_VEC_SUB(vec2f_sub, struct vec2f, 2);
+DEFINE_VEC_MUL(vec2f_mul, struct vec2f, double, 2);
+
+static inline void
+vec2f_setv(struct vec2f *dst, double x, double y)
+{
+	dst->x = x;
+	dst->y = y;
+}
+
+DEFINE_VEC_SET(vec3f_set, struct vec3f, 3);
+DEFINE_VEC_ADD(vec3f_add, struct vec3f, 3);
+DEFINE_VEC_SUB(vec3f_sub, struct vec3f, 3);
+DEFINE_VEC_MUL(vec3f_mul, struct vec3f, double, 3);
+
+static inline void
+vec3f_setv(struct vec3f *dst, double x, double y, double z)
+{
+	dst->x = x;
+	dst->y = y;
+	dst->z = z;
+}
+
+#undef DEFINE_VEC_SET
+#undef DEFINE_VEC_ADD
+#undef DEFINE_VEC_SUB
+#undef DEFINE_VEC_MUL