advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs | README | LICENSE

puzzle.c (2732B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <errno.h>
      6 #include <string.h>
      7 #include <strings.h>
      8 #include <stdbool.h>
      9 #include <assert.h>
     10 #include <time.h>
     11 #include <inttypes.h>
     12 #include <ctype.h>
     13 
     14 #define STR_LEN 1024
     15 #define MAP_WIDTH 100
     16 #define MAP_HEIGHT 100
     17 #define CLUSTERS_SIZE 3
     18 
     19 struct tile_t {
     20 	bool wall; // tile value is 9.
     21 	bool seen; // has been traversed or not
     22 };
     23 
     24 static int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j);
     25 static void add_cluster(int *clusters, int value);
     26 
     27 void puzzle(const char *filename, long long *result1, long long *result2) {
     28 	FILE *infile = fopen(filename, "r");
     29 	if (infile == NULL) {
     30 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     31 		return;
     32 	}
     33 
     34 	char buf[STR_LEN] = {0};
     35 	unsigned int line_num = 0;
     36 
     37 	int8_t map[MAP_HEIGHT][MAP_WIDTH] = {0};
     38 	struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH] = {0};
     39 
     40 	*result1 = 0;
     41 
     42 	while (fgets(buf, STR_LEN, infile) != NULL) {
     43 		assert(line_num < MAP_HEIGHT);
     44 		size_t len = strlen(buf);
     45 		assert(len > 0 && (len-1) == MAP_WIDTH);
     46 		for (int i = 0; i < MAP_WIDTH; ++i) {
     47 			assert(isdigit((int)buf[i]));
     48 			map[line_num][i] = buf[i] - '0';
     49 			struct tile_t tile = { .wall = buf[i] == '9', .seen = false };
     50 			tiles[line_num][i] = tile;
     51 		}
     52 
     53 		++line_num;
     54 		bzero(buf, STR_LEN);
     55 	}
     56 
     57 	int clusters[CLUSTERS_SIZE] = {0};
     58 
     59 	for (int i = 0; i < MAP_HEIGHT; ++i) {
     60 		for (int j = 0; j < MAP_WIDTH; ++j) {
     61 			int8_t c = map[i][j];
     62 			bool is_low = true;
     63 			if (i > 0)
     64 				is_low &= c < map[i-1][j];
     65 			if (i < MAP_HEIGHT - 1)
     66 				is_low &= c < map[i+1][j];
     67 			if (j > 0)
     68 				is_low &= c < map[i][j-1];
     69 			if (j < MAP_WIDTH - 1)
     70 				is_low &= c < map[i][j+1];
     71 
     72 			if (is_low) {
     73 				*result1 += c + 1;
     74 			}
     75 
     76 			if (!tiles[i][j].seen) {
     77 				add_cluster(clusters, count_tiles(tiles, i, j));
     78 			}
     79 		}
     80 	}
     81 
     82 	*result2 = 1;
     83 	for (int i = 0; i < CLUSTERS_SIZE; ++i) {
     84 		*result2 *= clusters[i];
     85 	}
     86 
     87 	// mutiny! ignoring feof/ferror.
     88 	fclose(infile);
     89 }
     90 
     91 int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j) {
     92 	struct tile_t *tile = &tiles[i][j];
     93 	if (tile->seen) return 0;
     94 	tile->seen = true;
     95 	if (tile->wall) return 0;
     96 
     97 	int count = 1; // current tile
     98 	// checking adjacent tiles recursively
     99 	if (i > 0)
    100 		count += count_tiles(tiles, i-1, j);
    101 	if (i < MAP_HEIGHT - 1)
    102 		count += count_tiles(tiles, i+1, j);
    103 	if (j > 0)
    104 		count += count_tiles(tiles, i, j-1);
    105 	if (j < MAP_WIDTH - 1)
    106 		count += count_tiles(tiles, i, j+1);
    107 
    108 	return count;
    109 }
    110 
    111 void add_cluster(int *clusters, int value) {
    112 	int *min_cluster = clusters;
    113 	for (int i = 0; i < CLUSTERS_SIZE; ++i) {
    114 		if (clusters[i] < *min_cluster) {
    115 			min_cluster = &clusters[i];
    116 		}
    117 	}
    118 	if (value > *min_cluster) {
    119 		*min_cluster = value;
    120 	}
    121 }