puzzle_test.c (2766B)
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 10 16 #define MAP_HEIGHT 5 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_test(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 // too late for dynamic arrays 58 int clusters[CLUSTERS_SIZE] = {0}; 59 60 for (int i = 0; i < MAP_HEIGHT; ++i) { 61 for (int j = 0; j < MAP_WIDTH; ++j) { 62 int8_t c = map[i][j]; 63 bool is_low = true; 64 if (i > 0) 65 is_low &= c < map[i-1][j]; 66 if (i < MAP_HEIGHT - 1) 67 is_low &= c < map[i+1][j]; 68 if (j > 0) 69 is_low &= c < map[i][j-1]; 70 if (j < MAP_WIDTH - 1) 71 is_low &= c < map[i][j+1]; 72 73 if (is_low) { 74 *result1 += c + 1; 75 } 76 77 if (!tiles[i][j].seen) { 78 add_cluster(clusters, count_tiles(tiles, i, j)); 79 } 80 } 81 } 82 83 *result2 = 1; 84 for (int i = 0; i < CLUSTERS_SIZE; ++i) { 85 *result2 *= clusters[i]; 86 } 87 88 // mutiny! ignoring feof/ferror. 89 fclose(infile); 90 } 91 92 int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j) { 93 struct tile_t *tile = &tiles[i][j]; 94 if (tile->seen) return 0; 95 tile->seen = true; 96 if (tile->wall) return 0; 97 98 int count = 1; // current tile 99 // checking adjacent tiles recursively 100 if (i > 0) 101 count += count_tiles(tiles, i-1, j); 102 if (i < MAP_HEIGHT - 1) 103 count += count_tiles(tiles, i+1, j); 104 if (j > 0) 105 count += count_tiles(tiles, i, j-1); 106 if (j < MAP_WIDTH - 1) 107 count += count_tiles(tiles, i, j+1); 108 109 return count; 110 } 111 112 void add_cluster(int *clusters, int value) { 113 int *min_cluster = clusters; 114 for (int i = 0; i < CLUSTERS_SIZE; ++i) { 115 if (clusters[i] < *min_cluster) { 116 min_cluster = &clusters[i]; 117 } 118 } 119 if (value > *min_cluster) { 120 *min_cluster = value; 121 } 122 }