From 709005f9a565405d9413eebf8c4ccaff53f0654a Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 22 Dec 2023 16:44:48 +0100 Subject: Added solutions for 21 and 22 --- 2023/21/21a.c | 54 +++++++++++++++++++++++++++++++++ 2023/21/21b.c | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2023/21/fuckyou.png | Bin 0 -> 544 bytes 2023/21/fuckyou2.png | Bin 0 -> 523 bytes 4 files changed, 137 insertions(+) create mode 100644 2023/21/21a.c create mode 100644 2023/21/21b.c create mode 100644 2023/21/fuckyou.png create mode 100644 2023/21/fuckyou2.png (limited to '2023/21') diff --git a/2023/21/21a.c b/2023/21/21a.c new file mode 100644 index 0000000..a4009d9 --- /dev/null +++ b/2023/21/21a.c @@ -0,0 +1,54 @@ +#include +#include +#include +#include + +#define N 200 + +typedef struct { int i, j; } point_t; + +char map[N][N]; +int n, nq, nnext; +point_t s, q[N*N], nextq[N*N]; + +bool bad(point_t p) { + int i = p.i, j = p.j; + return i < 0 || j < 0 || i >= n || j >= n || map[i][j] == '#'; +} + +void add(point_t p) { + if (bad(p)) return; + for (int i = 0; i < nnext; i++) + if (nextq[i].i == p.i && nextq[i].j == p.j) + return; + nextq[nnext++] = p; +} + +point_t up(point_t p) { return (point_t) {.i = p.i-1, .j = p.j}; } +point_t down(point_t p) { return (point_t) {.i = p.i+1, .j = p.j}; } +point_t right(point_t p) { return (point_t) {.i = p.i, .j = p.j+1}; } +point_t left(point_t p) { return (point_t) {.i = p.i, .j = p.j-1}; } + +int main() { + for (n = 0; fgets(map[n], N, stdin) != NULL; n++) + for (int i = 0; map[n][i] != '\n'; i++) + if (map[n][i] == 'S') + s = (point_t) {.i = n, .j = i}; + + int d = 64; + add(s); + for (int i = 0; i < d; i++) { + memcpy(q, nextq, nnext * sizeof(point_t)); + nq = nnext; + nnext = 0; + for (int j = 0; j < nq; j++) { + add(up(q[j])); + add(down(q[j])); + add(right(q[j])); + add(left(q[j])); + } + } + + printf("%d\n", nnext); + return 0; +} diff --git a/2023/21/21b.c b/2023/21/21b.c new file mode 100644 index 0000000..1748185 --- /dev/null +++ b/2023/21/21b.c @@ -0,0 +1,83 @@ +/* +This is another problem I did not enjoy. Once again, it was only solvable +because of the carefully crafted input case. This makes the problem +solvable, but at the same time it leaves you wondering - which unsaid +assumptions are true and which are not? + +For example, in my first 14 attempts or so I assumed that every non-# cell +was reached at the same time as if there were no #-cells. A reasonable +assumption, and almost true. Unfortunately there were some cells that +were completely enclosed by #-cells, and thus unreachable. See fuckyou.png +and fuckyou2.png. +*/ + +#include +#include +#include +#include +#include + +#define N 200 +#define S 202300L /* My input was 202300*131+65 */ + +char map[N][N]; +int64_t n; + +int go(char m[][N], int i, int j) { + if (i >= 0 && j >= 0 && i < n && j < n && m[i][j] == '.') { + m[i][j] = 'S'; + return 1; + } + return 0; +} + +int64_t flood(int64_t x, int64_t y, int64_t steps) { + int64_t c, i, j; + char tmp[N][N]; + for (int i = 0; i < n; i++) memcpy(tmp[i], map[i], n*sizeof(char)); + tmp[x][y] = 'S'; + for (int s = 0; s < steps; s++) { + for (i = 0, c = 0; i < n; i++) { + for (j = (s+x+y+i)%2; j < n; j += 2) { + if (tmp[i][j] == 'S') { + tmp[i][j] = '.'; + c += go(tmp, i-1, j) + + go(tmp, i+1, j) + + go(tmp, i, j-1) + + go(tmp, i, j+1); + } + } + } + } + return c; +} + +int main() { + for (n = 0; fgets(map[n], N, stdin) != NULL; n++) ; + map[n/2][n/2] = '.'; + + int64_t fulleven = flood(n/2, n/2, n-1); + int64_t fullodd = flood(n/2, n/2, n); + int64_t arrowr = flood(n/2, 0, n-1); + int64_t arrowl = flood(n/2, n-1, n-1); + int64_t arrowd = flood(0, n/2, n-1); + int64_t arrowu = flood(n-1, n/2, n-1); + int64_t topl = flood(0, 0, n/2-1); + int64_t topr = flood(0, n-1, n/2-1); + int64_t botl = flood(n-1, 0, n/2-1); + int64_t botr = flood(n-1, n-1, n/2-1); + int64_t cutbr = flood(0, 0, n/2+n-1); + int64_t cutbl = flood(0, n-1, n/2+n-1); + int64_t cuttr = flood(n-1, 0, n/2+n-1); + int64_t cuttl = flood(n-1, n-1, n/2+n-1); + + int64_t fulls = S*S*fulleven + (S-1)*(S-1)*fullodd; + int64_t smallborder = S*(topl + topr + botl + botr); + int64_t bigborder = (S-1)*(cutbr + cutbl + cuttr + cuttl); + int64_t arrows = arrowr + arrowl + arrowu + arrowd; + int64_t final = fulls + smallborder + bigborder + arrows; + + printf("%" PRId64 "\n", final); + + return 0; +} diff --git a/2023/21/fuckyou.png b/2023/21/fuckyou.png new file mode 100644 index 0000000..4fb5ddc Binary files /dev/null and b/2023/21/fuckyou.png differ diff --git a/2023/21/fuckyou2.png b/2023/21/fuckyou2.png new file mode 100644 index 0000000..2885148 Binary files /dev/null and b/2023/21/fuckyou2.png differ -- cgit v1.3