advent2021

commit 402fe5007adf3a0ba0e9dcd77a36e648d0070900
parent 417f3aae6145ef80efcf0092fd199ea3749455f9
Author: bsandro <[email protected]>
Date:   Thu, 16 Dec 2021 02:06:35 +0200

Day 15, puzzle 2 (slowest A* in the world)

Diffstat:
M
day15/Makefile
 | 
2
+-
M
day15/puzzle.c
 | 
93
+++++++++++++++++++++++++++++++++++++++++++++++++------------------------------

2 files changed, 59 insertions(+), 36 deletions(-)
diff --git a/day15/Makefile b/day15/Makefile
@@ -3,7 +3,7 @@ SRC=$(wildcard *.c ../common/*.c)
 DEPS:=$(wildcard *.h ../common/*.h)
 OBJ:=$(SRC:.c=.o)
 CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common
-LDFLAGS=-lc -lm
+LDFLAGS=-lc
 
 all: $(NAME)
 
diff --git a/day15/puzzle.c b/day15/puzzle.c
@@ -10,8 +10,6 @@
 #include <time.h>
 #include <inttypes.h>
 #include <ctype.h>
-#include <math.h>
-#include <unistd.h>
 
 #include "util.h"
 
@@ -25,12 +23,18 @@ struct tile_t {
 	int p_x, p_y;
 };
 
-int astar(int8_t map[MAP_HEIGHT][MAP_WIDTH], struct tile_t start, struct tile_t end);
+struct map_t {
+	int8_t map[MAP_HEIGHT][MAP_WIDTH];
+	int base_width, base_height;
+};
+
+int astar(struct map_t *map, struct tile_t start, struct tile_t end);
 void array_push(struct array_t *array, struct tile_t tile);
 struct tile_t * array_get(struct array_t *array, int x, int y);
 bool array_has(struct array_t *array, int x, int y);
 void array_delete(struct array_t *array, struct tile_t tile);
 void array_print(struct array_t *array);
+int get_risk(struct map_t *map, int x, int y);
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
@@ -40,9 +44,9 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 	}
 
 	char buf[STR_LEN] = {0};
-	unsigned int line_num = 0;
-	int8_t map[MAP_HEIGHT][MAP_WIDTH] = {0};
+	int line_num = 0;
 	int line_width = 0;
+	struct map_t map = {0};
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
 		assert(line_num < MAP_HEIGHT);
@@ -51,7 +55,7 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 		assert(len > 0 && line_width < MAP_WIDTH);
 		for (int i = 0; i < line_width; ++i) {
 			if (isdigit((int)buf[i])) {
-				map[line_num][i] = buf[i] - '0';
+				map.map[line_num][i] = buf[i] - '0';
 			}
 		}
 
@@ -59,20 +63,27 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 		bzero(buf, STR_LEN);
 	}
 
+	map.base_width = line_width;
+	map.base_height = line_num;
+
 	struct tile_t start = {0};
-	struct tile_t end = {
-		.x = line_width - 1,
-		.y = line_num - 1
+	struct tile_t end1 = {
+		.x = map.base_width - 1,
+		.y = map.base_height - 1
+	};
+	struct tile_t end2 = {
+		.x = map.base_width*5 - 1,
+		.y = map.base_height*5 - 1
 	};
 
-	*result1 = astar(map, start, end);
-	*result2 = 0;
+	*result1 = astar(&map, start, end1);
+	*result2 = astar(&map, start, end2);
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
-int astar(int8_t map[MAP_HEIGHT][MAP_WIDTH], struct tile_t start, struct tile_t end) {
+int astar(struct map_t *map, struct tile_t start, struct tile_t end) {
 	struct array_t visited = { .data = NULL };
 	array_init(&visited, sizeof(struct tile_t), 10);
 	struct array_t upcoming = { .data = NULL };
@@ -92,26 +103,15 @@ int astar(int8_t map[MAP_HEIGHT][MAP_WIDTH], struct tile_t start, struct tile_t 
 			}
 		}
 
-		//printf("current: %d,%d (%d)\n", current.x, current.y, current.f);
 		if (current.x == end.x && current.y == end.y) {
-			//printf("end!\n");
 			free(upcoming.data);
 			free(visited.data);
 			return current.f;
 		}
 
-
-		//printf("upcoming(begin):\n");
-		//array_print(&upcoming);
-
 		array_push(&visited, current);
 		array_delete(&upcoming, current);
 
-		//printf("visited:\n");
-		//array_print(&visited);
-		//printf("upcoming(after delete):\n");
-		//array_print(&upcoming);
-
 		// iterating through adjacent nodes
 		for (int i = 0; i < 4; ++i) {
 			int x1 = current.x + dirs[i][0];
@@ -124,31 +124,54 @@ int astar(int8_t map[MAP_HEIGHT][MAP_WIDTH], struct tile_t start, struct tile_t 
 			if (array_has(&visited, child.x, child.y)) {
 				continue;
 			}
-			child.g = current.g + map[y1][x1];
+			child.g = current.g + get_risk(map, x1, y1);
 			child.h = (end.y - y1) + (end.x - x1);
 			child.f = child.g + child.h;
-			//printf("(%d,%d g:%d h:%d f:%d)", child.x, child.y, child.g, child.h, child.f);
 
 			struct tile_t *s = array_get(&upcoming, child.x, child.y);
 			if (s == NULL) {
-				//printf("pushing child %d,%d to upcoming\n", child.x, child.y);
 				array_push(&upcoming, child);
-			} else {
-				if (s->g <= child.g) {
-					continue;
-				}
+			} else if (s->g <= child.g) {
+				continue;
 			}
 		}
-		//printf("\n");
-		//printf("upcoming(end %zu):\n", upcoming.count);
-		//array_print(&upcoming);
-		//printf("\n");
-		//sleep(1);
 	}
 
+	printf("error\n");
+	free(upcoming.data);
+	free(visited.data);
 	return 0;
 }
 
+int get_risk(struct map_t *map, int x, int y) {
+	assert(map != NULL);
+	if (x < map->base_width && y < map->base_height) {
+		return map->map[y][x];
+	}
+
+	// quadrants and stuff
+	static const int quadrants[5][5] = {
+		{0, 1, 2, 3, 4},
+		{1, 2, 3, 4, 5},
+		{2, 3, 4, 5, 6},
+		{3, 4, 5, 6, 7},
+		{4, 5, 6, 7, 8}
+	};
+	int qx = x / map->base_width;
+	int qy = y / map->base_height;
+	int x1 = x % map->base_width;
+	int y1 = y % map->base_height;
+	assert(qx < 5 && qy < 5);
+	int m = quadrants[qy][qx];
+
+	int risk = map->map[y1][x1] + m;
+	if (risk > 9) {
+		risk -= 9;
+	}
+
+	return risk;
+}
+
 void array_print(struct array_t *array) {
 	struct tile_t *data = array->data;
 	for (size_t i = 0; i < array->count; ++i) {