commit 3a2917331f01b49f9c3950b1458b1c6f0f53838f
parent 6998e1ac8e3a02cbcbd1ab5b2995c02cb3877c7f
Author: aabacchus <ben@bvnf.space>
Date: Mon, 12 Dec 2022 20:48:26 +0000
22.12 in C
Diffstat:
3 files changed, 251 insertions(+), 0 deletions(-)
diff --git a/2022/12/a.c b/2022/12/a.c
@@ -0,0 +1,205 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define HEIGHT 41//5
+#define WIDTH 171//8
+
+struct point {
+ int x, y;
+};
+
+struct nodel {
+ int dist;
+ struct point p;
+ struct nodel *next;
+};
+
+struct nodel *nodetop = NULL;
+int grid[HEIGHT][WIDTH] = {0};
+
+/* insert a node for dist and p so that nodetop is sorted */
+void
+node_push(int dist, struct point p) {
+ struct nodel *n = malloc(sizeof(struct nodel));
+ if (n == NULL) {
+ perror("malloc");
+ exit(1);
+ }
+ n->dist = dist;
+ n->p.x = p.x;
+ n->p.y = p.y;
+
+ struct nodel *t = nodetop;
+ if (t == NULL || t->dist < dist) {
+ n->next = t;
+ nodetop = n;
+ return;
+ }
+ for (; t != NULL; t = t->next) {
+ /* If anyone ever reads this, can you explain why part 2 requires `>=` and not `>`? Please tell me! */
+ if (t->next == NULL || t->next->dist >= dist) {
+ n->next = t->next;
+ t->next = n;
+ break;
+ }
+ }
+}
+
+struct nodel *
+node_pop(void) {
+ struct nodel *n = nodetop;
+ if (n != NULL)
+ nodetop = n->next;
+ return n;
+}
+
+void
+push_if_valid(int dist, int x, int y, int curheight, char partB) {
+ if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT)
+ return;
+ struct point p = {x, y};
+ if (partB == 0) {
+ if (grid[y][x] <= curheight + 1)
+ node_push(dist, p);
+ } else {
+ if (curheight <= grid[y][x] + 1)
+ node_push(dist, p);
+ }
+}
+
+int
+main(int argc, char **argv) {
+ char *buf = NULL;
+ size_t buflen = 0;
+ ssize_t n;
+ FILE *f;
+ struct point start, end;
+
+ int visited[HEIGHT][WIDTH] = {0};
+
+ nodetop = NULL;
+
+ if (argc != 2) {
+ fprintf(stderr, "usage: %s input\n", argv[0]);
+ return 1;
+ }
+
+ f = fopen(argv[1], "r");
+ if (f == NULL) {
+ perror(argv[1]);
+ return 1;
+ }
+
+ size_t row = 0;
+ while ((n = getline(&buf, &buflen, f)) != -1) {
+ if (buf[n - 1] == '\n') {
+ buf[n - 1] = '\0';
+ n--;
+ }
+ assert(n == WIDTH);
+ for (ssize_t i = 0; i < n; i++) {
+ switch (buf[i]) {
+ case 'S':
+ start.x = i;
+ start.y = row;
+ buf[i] = 'a';
+ break;
+ case 'E':
+ end.x = i;
+ end.y = row;
+ buf[i] = 'z';
+ break;
+ }
+ grid[row][i] = buf[i] - 'a';
+ }
+ row++;
+ }
+
+ free(buf);
+ fclose(f);
+
+ printf("start at (%d,%d)\nend at (%d,%d)\n", start.x, start.y, end.x, end.y);
+
+ for (int i = 0; i < HEIGHT; i++) {
+ for (int j = 0; j < WIDTH; j++)
+ printf("%c", grid[i][j] + 'a');
+ printf("\n");
+ }
+
+ node_push(0, start);
+ struct nodel *endpath;
+
+ while (1) {
+ struct nodel *n = node_pop();
+ if (n == NULL) {
+ fprintf(stderr, "reached end of node list.\n");
+ exit(1);
+ }
+ if (visited[n->p.y][n->p.x]) {
+ goto cont;
+ }
+ visited[n->p.y][n->p.x] = 1;
+ //fprintf(stderr, "%d,%d = %d\n", n->p.x, n->p.y, n->dist);
+
+ if (n->p.x == end.x && n->p.y == end.y) {
+ endpath = n;
+ break;
+ }
+
+ int curheight = grid[n->p.y][n->p.x];
+ push_if_valid(n->dist + 1, n->p.x - 1, n->p.y, curheight, 0);
+ push_if_valid(n->dist + 1, n->p.x + 1, n->p.y, curheight, 0);
+ push_if_valid(n->dist + 1, n->p.x, n->p.y - 1, curheight, 0);
+ push_if_valid(n->dist + 1, n->p.x, n->p.y + 1, curheight, 0);
+
+cont:
+ free(n);
+ }
+
+ printf("Part A: %d\n", endpath->dist);
+ free(endpath);
+
+ /* reset for part B */
+ while (node_pop() != NULL) ;
+ for (int y = 0; y < HEIGHT; y++)
+ for (int x = 0; x < WIDTH; x++)
+ visited[y][x] = 0;
+ nodetop = NULL;
+
+ /* This time start from the end and find the closest point of elevation a */
+ /* Have to reverse the neighbour selection rule so that going from lowest
+ * to end will still be possible. */
+ node_push(0, end);
+ while (1) {
+ struct nodel *n = node_pop();
+ if (n == NULL) {
+ fprintf(stderr, "reached end of node list.\n");
+ exit(1);
+ }
+ if (visited[n->p.y][n->p.x]) {
+ goto contB;
+ }
+ visited[n->p.y][n->p.x] = 1;
+ //fprintf(stderr, "%d,%d = %d\n", n->p.x, n->p.y, n->dist);
+
+ int curheight = grid[n->p.y][n->p.x];
+ if (curheight == 0) {
+ endpath = n;
+ break;
+ }
+
+ push_if_valid(n->dist + 1, n->p.x - 1, n->p.y, curheight, 1);
+ push_if_valid(n->dist + 1, n->p.x + 1, n->p.y, curheight, 1);
+ push_if_valid(n->dist + 1, n->p.x, n->p.y - 1, curheight, 1);
+ push_if_valid(n->dist + 1, n->p.x, n->p.y + 1, curheight, 1);
+
+contB:
+ free(n);
+ }
+
+ printf("Part B: %d (%d,%d)\n", endpath->dist, endpath->p.x, endpath->p.y);
+ free(endpath);
+
+ return 0;
+}
diff --git a/2022/12/example b/2022/12/example
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/2022/12/input b/2022/12/input
@@ -0,0 +1,41 @@
+abcccccaaaaaacccaaaccaaaaaaaacccaaaaaaccccccccccccccccccccccccccccaaaaaaaaaaaaaacacccccccccccccccccccccccccccccccaaaaaaaacccccccccccccccccccccccccccccccccccccccccccccaaaaa
+abcccccaaaaaaaacaaaaccaaaaaaccccaaaaaaccccccccccaaacccccccccccccccaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccaaaaaaaaaccccccaaaccccccccccccccccccccccccccccccccccaaaaaa
+abccccaaaaaaaaacaaaaccaaaaaaccccaaaaaaaaccccccccaaaccccccccccccccccaaaaaaaaaaaaaaccccaaaccccccccccccccccccccccccccaaaaaaaaccccacaaaccccccccccccccccaaccccccccccccccccaaaaaa
+abcccaaaaaaaaaacaaaccaaaaaaaacccccaaccaaacaaccccaaaaaaaccccccccccccaacaaaaaaaaaccccccaaaaccccccccccccccccccccaaacaaaaaaccccccaaaaaaaacccccccccccccaaaacccccccccccccccaaacaa
+abcccaaacaaaccccccccaaaaaaaaaaccccccccaaaaaacaaaaaaaaaaccccccccccccccaaaaaaaaaaccccccaaaaccccccccccccccccaaccaaacaaaaaaacccccaaaaaaaacccccccccccccaaaaccaaaccccccccccccccaa
+abcccccccaaaccccccccaaaaaaaaaaccccccaaaaaaaccaaaaaaaaacccccccccccccccaaaacaaaaaaaacccaaaaccccccccccccccccaaaaaaacaaccaaacccccccaaaaacccccccccccccccaaaaaaaaacccccccccccccaa
+abcccccccaacccccccccacaaaaaccaccccccaaaaaaacccaaaaaaaccccccaaacccccccaacacaaaaaaaacccccccccccccccccccccccaaaaaaccccccaaaccccccaaaaaccccccccccccjjkkaaaaaaaacccccccccccccccc
+abaccccccccccccccccccccaaaacccccccccccaaaaaaccccaaaaaaccccaaaacccccccccccccaaaaaaccccccccccaccaaccccccccccaaaaaaaaccccccccccccaaaaaaccccccccccjjjkkkkkaaaaccccccccaaccccccc
+abaccccccccaaaccccccccccaaccccccccccccaacaaacccaaaaaaaccccaaaacccccccccccccaaaaaaccccccccccaaaaacccccccccaaaaaaaaaccccccccccccaccaaacccccccccjjjjkkkkkkkaacccccccccaccccccc
+abaacccccccaaaaccccccccccaaaccccccccccaacccccccaaaacaaccccaaaacccccccccccccaaaaaacccccccccccaaaaaccccccccaaaaaaaacccccccaaccccccccccccccccccjjjjoooookkkkkllllllccccaaacccc
+abaacccccccaaaaccccccccccaaaaccccccccccccccccccaacaaacaaaccccccccccaaccccccaaacaaccccccccccaaaaaacccccccaaaaaaaccccccccaaaacccccccccccccccccjjjoooooopkkkklllllllccccaacccc
+abaccccccccaaacccccccccccaaaacccccccccccccccccccccaaaaaaacccccccccaaaccccccccccccccccccccccaaaaccccccaaaccccaaaccccccccaaaacccccccccccccccccjjooooooopppklppplllllcccaccccc
+abacccaaaaaccccccccccccccaaaccccccccccccccccccccccaaaaaaccccccaaaaaaaccccccccccccccccccccccccaaacccccaaacacccaaccccccccaaaaccccccccccccccccjjjooouuuupppppppppplllcccaccccc
+abccccaaaaacccccccccccccccccccccccccccccccccccccaaaaaaaaccccccaaaaaaaaaaccaacccccccccccccccccccccccaacaaaaaccccccccccccccccaaacccccaccaccccjjjoouuuuuupppppppppllllccaccccc
+abcccaaaaaacccccccccccccaaccccccaaacccccccccccccaaaaaaaaaccccccaaaaaaaaacaaaaccccccccccccccccccccccaaaaaaaaccccccccccccacccaaccccccaaaacccjjjjoouuuuuuupuuuvvpqqlllccaccccc
+abcccaaaaaaccccccccccccaaacaacccaaaaacccccccccccaaaaaaaaaaccccccaaaaaaaccaaaacccccccccccccccccccccccaaaaaccccccccccccccaaaaaaacccccaaaaaccijjooouuuxxxuuuuvvvqqqlmccccccccc
+abcccaaaaaaccccaacccccccaaaaaccaaaaaccccccccccccaaaaaacaaacccccaaaaaaccccaaaacccccccccccccccccccaaaccaaaaaccccaaaccccccaaaaaaaacccaaaaaaciiiinootuxxxxuuyyyvvqqqmmccccccccc
+abcccacaacccccaaacaaccaaaaaacccaaaaaccccccccccccaaaaaacccccccccaaaaaaaccccccccccccaaccacccccccccaaacaaacaaccaaaaaccccccaaaaaaaaaccaaaaaaiiinnnnnttxxxxxyyyyvvqqqmmdddcccccc
+abcccaaacaaacccaaaaaccaaaaaaaaccaaaaacccccccccccaaacaaaccccccccaaccaaaccccccccccccaaaaaccccccaaaaaaaaaacccccaaaaaacccccaaaaaaaaaccccaaciiinnnnttttxxxxxyyyyvvqqmmmdddcccccc
+abcccaaaaaaacaaaaaacccaacaaaaaccaacccccccccccaaaaaaaaaaaccccccccccccaacccccccccccaaaaacccccccaaaaaaaacccccccaaaaaacccccaaaaaaaaccccccciiinnnnttttxxxxxyyyyvvqqqmmmdddcccccc
+SbcccaaaaaaccaaaaaaaaccccaacccccccccccaacccccaaaaaaaaaaccccccccccccccccccccccccccaaaaaaccccccccaaaaaccccccccaaaaacccccaaaaaaaccccccccciiinnntttxxxEzzzzyyvvvqqqmmmdddcccccc
+abccaaaaaaaacaacaaaaacccaaccccccccccccaaacccccaaaaaaaaaaaccccccccccccccccccccccccccaaaacccccccaaaaaaccccccccaaaaaccccccacaaaaccccccccciiinnntttxxxxxyyyyyyvvvqqmmmdddcccccc
+abcaaaaaaaaaacccaacccccaacccccccccacacaaaccccccaaaaaaaaaacccccccccccccccccccccacccaaccccccccccaaaaaaccccccccccccccccccccaaaaaccccccccciiinnntttxxxxyyyyyyyyvvvqqmmmdddccccc
+abcaaaaaaaaaaccaaccaaaaaacccccccccaaaaaaaaaacccaaaaaaaaaacaaccccccccccccaaaaaaaaccccccccccccccaccaaaccccccccccccccccaaacaaacccccccccaaiiinnnttttxxwwyyyyyyyvvvqqmmmdddccccc
+abaaccaaacaaaccccccaaaaaaaccccccccaaaaaaaaaacccaaaaaaaacccaaaccccccccccccaaaaaacccccccccccccccccccccccccccccccccccccaaaaaaaaaacccaaaachhhnnnntttsswwyywwwwwvvvrrqkmdddccccc
+abaaacaaacccccccccccaaaaaaacccccccccaaaaaacccccaacccaaacccaaaaaaaccccccccaaaaaaccccccccccccccaaccccccccccccccccccccccaaaaaaaaacccaaaaaahhhmmmmmsssswwywwwwwwvrrrrkkdddccccc
+abaaaaaaacccccccccccaaaaaaacccccccccaaaaaaccccccaaccccccaaaaaaaaccccccccaaaaaaaaccccccccaaccaaaccccccccccccccccaacccccaaaaaaacccccaaaaahhhhhmmmmssswwwwwrrrrrrrrkkkeeeccccc
+abcaaaaaaccccccccccaaaaaacccccccccccaaaaaacccccaaaaccccaaaaaaaaacccccccaaaaaaaaaacccccccaaacaaacccccccccccccacaaaccccaaaaaaccccccaaaaacchhhhhmmmmsswwwwrrrrrrrrrkkkeeeccccc
+abaaaaaacccccccccccaaaaaaccccccccccaaaaaaaaccccaaaaccccaaaaaaaaccccccccaaaaaaaaaacaaacccaaaaaaccccccaacccccaaaaaccaccaaaaaaacccccaccaacccchhhhmmmssswwsrrrrrrrkkkkkeeeccccc
+abaaaaaaaccccccccaaccccaaccccccccccaaaaaaacccccaaaacccccccaaaaaacccaaccacaaaaaccccaaaccccaaaaaaaaaacaaaccccaaaaaaaaccaaacaaaccccccccccccccchhhhmmssssssrlllkkkkkkkeeecccccc
+abaaaaaaaaccccccaaacaacccccccccccccaaaaaaaaccccccccccccccaaaaaaacccaacccccaaaaccccaaaaaaaaaaaaaaaaaaaacccccccaaaaaccccccccaaaacccccccccccccchhgmmmsssssllllkkkkkeeeeeaacccc
+abcaaacaaacccccccaaaaaccccccccccccaaaaaaaaaccccccccccccccaaaccaaaaaaaaaacccaaccaaaaaaaaaaaaaaaaacaaaaaaaccccaaaaacccccccaaaaaacccccccccccccccggmmmlssslllllffeeeeeeeaaacccc
+abcaaacccccccccaaaaaacccccccaaacaaacaaaaaaacccccccccccccaaaaccccaaaaaaaacccccccaaaaaaaaaaaaaaaccaaaaaaaaccccaacaacccccccaaaaaacccccccccccccccgggmmlllllllfffffeeeeaaaaacccc
+abcaaccccccccccaaaaaaaacccccaaaaaaaaaaaaaccccccccccccccccaaaacccccaaaacccccaacccaaaaaaaccccaaaccaaaaaaaacccccccaaccccccccaaaaaaaccccccccccccccggglllllllffffffecacaaacccccc
+abcccccccccaaccaacaaaaaccccccaaaaaaaaaaaaccccccaaccaaccaaaaaaccccaaaaaccccaaccccccaaaaaacccaaaccaacaaaccaaaacccccccccccccaaaaaaaccccccccccccccggggllllfffffcccccccaaacccccc
+abcccccccaaaaaaccaaacccccccccaaaaaaaaccaaacccccaaaaaaccaaaaacccccaaaaaacccaaaccaaaaaaaaacccccccccccaaaccaaaaacccccccccccaaaaaaaaaccaaccccccccccggggggfffffccccccccccccccccc
+abcaaccccaaaaaaccaaccccccccaaaaaaaaaacccaacccccaaaaaccccaaaaaccccacccaaccaaaaccaaaaaccaacccccccccccccccaaaaaacccccccaaacaaaaaaaaaaaaacccccccccccgggggfffaacccccccccccccaccc
+abaaaccccaaaaaaccccccccaaacaaaaaaaaaaaaaaaaaaccaaaaaacccaaccacccccccaaaaaaaaaaaaaaaccccccccccccccaaaaccaaaaaacccccccaaaaaaaaaacaaaaaaccccccccccccagggfcaaaccccccccccccaaaaa
+abaaaacccaaaaaccccccccaaaacaaacaaacccaaaaaaaacaaaaaaaaccccccccccccccaaaaaaaaaaaaaaacccccccccccccaaaaacccaaaaaccccccccaaaaaacaaaaaaaaccccccccccccccaccccaaacccccccccccccaaaa
+abaaaaccccaaaaccccccccaaaacccccaaacccccaaaacccaaaaaaaacccccccccccccccaaaaaaaaaaaaaacccccccccccccaaaaaaccaaaccccccccccaaaaaaaaaaaaaaaaccccccccccccccccccccacccccccccccccaaaa
+abaacccccccccccccccccccaaacccccaacccccaaaaaacccccaacccccccccccccccccccccaaaaaaaaacccccccccccccccaaaaaacccccccccccccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccaaaaaa
