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 }