commit 6addd1e45691406b36cacfbce5ba58cfd4e52689
parent 5460124838b98e5ec95bf7276c1705feb632b2be
Author: bsandro <[email protected]>
Date: Fri, 10 Dec 2021 01:33:44 +0200
Day 09, puzzle 2
Diffstat:
| M | day09/puzzle.c | | | 65 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------ |
| M | day09/puzzle_test.c | | | 66 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- |
2 files changed, 120 insertions(+), 11 deletions(-)
diff --git a/day09/puzzle.c b/day09/puzzle.c
@@ -11,11 +11,18 @@
#include <inttypes.h>
#include <ctype.h>
-#include "util.h"
+#define STR_LEN 1024
+#define MAP_WIDTH 100
+#define MAP_HEIGHT 100
+#define CLUSTERS_SIZE 3
-#define STR_LEN 1024
-#define MAP_WIDTH 100
-#define MAP_HEIGHT 100
+struct tile_t {
+ bool wall; // tile value is 9.
+ bool seen; // has been traversed or not
+};
+
+static int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j);
+static void add_cluster(int *clusters, int value);
void puzzle(const char *filename, long long *result1, long long *result2) {
FILE *infile = fopen(filename, "r");
@@ -28,9 +35,9 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
unsigned int line_num = 0;
int8_t map[MAP_HEIGHT][MAP_WIDTH] = {0};
+ struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH] = {0};
*result1 = 0;
- *result2 = 0;
while (fgets(buf, STR_LEN, infile) != NULL) {
assert(line_num < MAP_HEIGHT);
@@ -39,12 +46,16 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
for (int i = 0; i < MAP_WIDTH; ++i) {
assert(isdigit(buf[i]));
map[line_num][i] = buf[i] - '0';
+ struct tile_t tile = { .wall = buf[i] == '9', .seen = false };
+ tiles[line_num][i] = tile;
}
++line_num;
bzero(buf, STR_LEN);
}
+ int clusters[CLUSTERS_SIZE] = {0};
+
for (int i = 0; i < MAP_HEIGHT; ++i) {
for (int j = 0; j < MAP_WIDTH; ++j) {
int8_t c = map[i][j];
@@ -55,15 +66,57 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
is_low &= c < map[i+1][j];
if (j > 0)
is_low &= c < map[i][j-1];
- if (j < MAP_WIDTH -1)
+ if (j < MAP_WIDTH - 1)
is_low &= c < map[i][j+1];
if (is_low) {
*result1 += c + 1;
}
+
+ if (!tiles[i][j].seen) {
+ add_cluster(clusters, count_tiles(tiles, i, j));
+ }
}
}
+ *result2 = 1;
+ for (int i = 0; i < CLUSTERS_SIZE; ++i) {
+ printf("cluster #%i: %d\n", i, clusters[i]);
+ *result2 *= clusters[i];
+ }
+
// mutiny! ignoring feof/ferror.
fclose(infile);
}
+
+int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j) {
+ struct tile_t *tile = &tiles[i][j];
+ if (tile->seen) return 0;
+ tile->seen = true;
+ if (tile->wall) return 0;
+
+ int count = 1; // current tile
+ // checking adjacent tiles recursively
+ if (i > 0)
+ count += count_tiles(tiles, i-1, j);
+ if (i < MAP_HEIGHT - 1)
+ count += count_tiles(tiles, i+1, j);
+ if (j > 0)
+ count += count_tiles(tiles, i, j-1);
+ if (j < MAP_WIDTH - 1)
+ count += count_tiles(tiles, i, j+1);
+
+ return count;
+}
+
+void add_cluster(int *clusters, int value) {
+ int *min_cluster = clusters;
+ for (int i = 0; i < CLUSTERS_SIZE; ++i) {
+ if (clusters[i] < *min_cluster) {
+ min_cluster = &clusters[i];
+ }
+ }
+ if (value > *min_cluster) {
+ *min_cluster = value;
+ }
+}
diff --git a/day09/puzzle_test.c b/day09/puzzle_test.c
@@ -11,9 +11,18 @@
#include <inttypes.h>
#include <ctype.h>
-#define STR_LEN 1024
-#define MAP_WIDTH 10
-#define MAP_HEIGHT 5
+#define STR_LEN 1024
+#define MAP_WIDTH 10
+#define MAP_HEIGHT 5
+#define CLUSTERS_SIZE 3
+
+struct tile_t {
+ bool wall; // tile value is 9.
+ bool seen; // has been traversed or not
+};
+
+static int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j);
+static void add_cluster(int *clusters, int value);
void puzzle_test(const char *filename, long long *result1, long long *result2) {
FILE *infile = fopen(filename, "r");
@@ -26,9 +35,9 @@ void puzzle_test(const char *filename, long long *result1, long long *result2) {
unsigned int line_num = 0;
int8_t map[MAP_HEIGHT][MAP_WIDTH] = {0};
+ struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH] = {0};
*result1 = 0;
- *result2 = 0;
while (fgets(buf, STR_LEN, infile) != NULL) {
assert(line_num < MAP_HEIGHT);
@@ -37,12 +46,17 @@ void puzzle_test(const char *filename, long long *result1, long long *result2) {
for (int i = 0; i < MAP_WIDTH; ++i) {
assert(isdigit(buf[i]));
map[line_num][i] = buf[i] - '0';
+ struct tile_t tile = { .wall = buf[i] == '9', .seen = false };
+ tiles[line_num][i] = tile;
}
++line_num;
bzero(buf, STR_LEN);
}
+ // too late for dynamic arrays
+ int clusters[CLUSTERS_SIZE] = {0};
+
for (int i = 0; i < MAP_HEIGHT; ++i) {
for (int j = 0; j < MAP_WIDTH; ++j) {
int8_t c = map[i][j];
@@ -53,15 +67,57 @@ void puzzle_test(const char *filename, long long *result1, long long *result2) {
is_low &= c < map[i+1][j];
if (j > 0)
is_low &= c < map[i][j-1];
- if (j < MAP_WIDTH -1)
+ if (j < MAP_WIDTH - 1)
is_low &= c < map[i][j+1];
if (is_low) {
*result1 += c + 1;
}
+
+ if (!tiles[i][j].seen) {
+ add_cluster(clusters, count_tiles(tiles, i, j));
+ }
}
}
+ *result2 = 1;
+ for (int i = 0; i < CLUSTERS_SIZE; ++i) {
+ printf("cluster #%i: %d\n", i, clusters[i]);
+ *result2 *= clusters[i];
+ }
+
// mutiny! ignoring feof/ferror.
fclose(infile);
}
+
+int count_tiles(struct tile_t tiles[MAP_HEIGHT][MAP_WIDTH], int i, int j) {
+ struct tile_t *tile = &tiles[i][j];
+ if (tile->seen) return 0;
+ tile->seen = true;
+ if (tile->wall) return 0;
+
+ int count = 1; // current tile
+ // checking adjacent tiles recursively
+ if (i > 0)
+ count += count_tiles(tiles, i-1, j);
+ if (i < MAP_HEIGHT - 1)
+ count += count_tiles(tiles, i+1, j);
+ if (j > 0)
+ count += count_tiles(tiles, i, j-1);
+ if (j < MAP_WIDTH - 1)
+ count += count_tiles(tiles, i, j+1);
+
+ return count;
+}
+
+void add_cluster(int *clusters, int value) {
+ int *min_cluster = clusters;
+ for (int i = 0; i < CLUSTERS_SIZE; ++i) {
+ if (clusters[i] < *min_cluster) {
+ min_cluster = &clusters[i];
+ }
+ }
+ if (value > *min_cluster) {
+ *min_cluster = value;
+ }
+}
