advent2021

puzzle.c (5301B)

---

 #define _DEFAULT_SOURCE
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <stdbool.h>
 #include <assert.h>
 #include <time.h>
 #include <inttypes.h>
 #include <ctype.h>
 
 #include "util.h"
 
 #define STR_LEN 1024
 #define MAP_WIDTH 500
 #define MAP_HEIGHT 500
 
 struct tile_t {
 	int x, y;
 	int g, h, f;
 	int p_x, p_y;
 };
 
 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");
 	if (infile == NULL) {
 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
 		return;
 	}
 
 	char buf[STR_LEN] = {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);
 		size_t len = strlen(buf);
 		line_width = len - 1;
 		assert(len > 0 && line_width < MAP_WIDTH);
 		for (int i = 0; i < line_width; ++i) {
 			if (isdigit((int)buf[i])) {
 				map.map[line_num][i] = buf[i] - '0';
 			}
 		}
 
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
 	map.base_width = line_width;
 	map.base_height = line_num;
 
 	struct tile_t start = {0};
 	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, end1);
 	*result2 = astar(&map, start, end2);
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
 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 };
 	array_init(&upcoming, sizeof(struct tile_t), 10);
 
 	array_push(&upcoming, start);
 
 	static const int dirs[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
 
 	while (upcoming.count > 0) {
 		// choosing upcoming node with the lowest f
 		struct tile_t *upcoming_data = upcoming.data;
 		struct tile_t current = upcoming_data[0];
 		for (size_t i = 0; i < upcoming.count; ++i) {
 			if (upcoming_data[i].f < current.f) {
 				current = upcoming_data[i];
 			}
 		}
 
 		if (current.x == end.x && current.y == end.y) {
 			free(upcoming.data);
 			free(visited.data);
 			return current.f;
 		}
 
 		array_push(&visited, current);
 		array_delete(&upcoming, current);
 
 		// iterating through adjacent nodes
 		for (int i = 0; i < 4; ++i) {
 			int x1 = current.x + dirs[i][0];
 			int y1 = current.y + dirs[i][1];
 			struct tile_t child = {.x=x1, .y=y1, .p_x = current.x, .p_y = current.y};
 			// end point is always bottom right
 			if (x1 > end.x || x1 < 0 || y1 > end.y || y1 < 0) {
 				continue;
 			}
 			if (array_has(&visited, child.x, child.y)) {
 				continue;
 			}
 			child.g = current.g + get_risk(map, x1, y1);
 			child.h = (end.y - y1) + (end.x - x1);
 			child.f = child.g + child.h;
 
 			struct tile_t *s = array_get(&upcoming, child.x, child.y);
 			if (s == NULL) {
 				array_push(&upcoming, child);
 			} else if (s->g <= child.g) {
 				continue;
 			}
 		}
 	}
 
 	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) {
 		printf("[%zu] %d,%d (f:%d,g:%d)\n", i, data[i].x, data[i].y, data[i].f, data[i].g);
 	}
 }
 
 void array_push(struct array_t *array, struct tile_t tile) {
 	if (array->count >= array->cap) {
 		array_expand(array);
 	}
 	struct tile_t *data = array->data;
 	data[array->count++] = tile;
 }
 
 struct tile_t * array_get(struct array_t *array, int x, int y) {
 	struct tile_t *data = array->data;
 	for (size_t i = 0; i < array->count; ++i) {
 		if (data[i].x == x && data[i].y == y) {
 			return &data[i];
 		}
 	}
 	return NULL;
 }
 
 bool array_has(struct array_t *array, int x, int y) {
 	return array_get(array, x, y) != NULL;
 }
 
 void array_delete(struct array_t *array, struct tile_t tile) {
 	assert(array != NULL);
 	if (!array_has(array, tile.x, tile.y)) return;
 
 	struct tile_t *data_new = calloc(array->cap, array->elem_size);
 	struct tile_t *data = array->data;
 	size_t count_new = 0;
 	for (size_t i = 0; i < array->count; ++i) {
 		if (data[i].x != tile.x || data[i].y != tile.y) {
 			data_new[count_new++] = data[i];
 		}
 	}
 	free(array->data);
 	array->data = data_new;
 	array->count = count_new;
 }