commit 8a08277c07799bf8e05d18f8f3395fc53a53feb2
parent 4e5f9a4868c01aca0ef125c8cc50bbf6e208995c
Author: Jake Bauer <jbauer@paritybit.ca>
Date: Sat, 17 Dec 2022 19:12:51 -0500
Day 12 challenge complete
Diffstat:
| A | day12/input.txt | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | day12/main.c | | | 190 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 231 insertions(+), 0 deletions(-)
diff --git a/day12/input.txt b/day12/input.txt
@@ -0,0 +1,41 @@
+abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa
+abccccccccaaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccaaaaaa
+abccccccccccaaaaaaccaaaaaaaaaaaaaaaaccccccccccccccccacccccccccccccccccccaaaaa
+abcccccaaaacaaaaaaccaaaaaaaaaaaaaaaaacccccccccccccccaaaccccaccccccccccccccaaa
+abccccaaaaacaaccccccaaaaaacaaacaacaaaaaaacccccccccccaaaacccaacccccccccccccaaa
+abaaccaaaaaaccccaaacaaaacacaaacaaccaaaaaacccccccccccaklaccccccccccccccccccaac
+abaaccaaaaaaccaaaaaacccccccaaacccaaaaaaaccccccccccckkkllllccccccccccccccccccc
+abaaccaaaaaaccaaaaaacccccccaaaaacaaaaaaacccccccccckkkklllllcccccccaaaccaccccc
+abacccccaacccccaaaaacccccccaaaaaccaaaaaaacccccccckkkkpppllllccccccaaaaaaccccc
+abacccccccccccaaaaacccccccccaaaacccaaaaaaccccccckkkkpppppplllccccddddaaaccccc
+abccccccccccccaaaaaccccccccccaaaccaaaccccccccccckkkppppppppllllldddddddaccccc
+abccacccccccccccccccccccccccccccccaaccccccccccckkkopppupppplllmmmmdddddaacccc
+abccaaacaaaccccccccccccccccccccaaaaaaaaccccccckkkkopuuuuupppllmmmmmmddddacccc
+abccaaaaaaaccccccccccccccccccccaaaaaaaacccccjjkkkooouuuuuuppqqqqqmmmmddddcccc
+abccaaaaaacccccccccccccccaaccccccaaaacccccjjjjjjoooouuxuuuppqqqqqqmmmmdddcccc
+abcaaaaaaaacccccccccccccaaacccccaaaaaccccjjjjoooooouuuxxuuvvvvvqqqqmmmdddcccc
+abaaaaaaaaaacccccccaaaaaaacaacccaacaaacccjjjooooouuuuxxxxvvvvvvvqqqmmmdddcccc
+abaaaaaaaaaacccaaacaaaaaaaaaacccacccaaccjjjooootttuuuxxxyyvyyvvvqqqmmmeeecccc
+abcccaaacaaacccaaaaaaacaaaaaccccccccccccjjjooottttxxxxxxyyyyyyvvqqqmmmeeccccc
+abcccaaacccccccaaaaaacaaaaaccccaaccaacccjjjnnntttxxxxxxxyyyyyvvvqqqnneeeccccc
+SbccccaacccccccaaaaaaaaacaaacccaaaaaacccjjjnnntttxxxEzzzzyyyyvvqqqnnneeeccccc
+abcccccccccccccaaaaaaaaacaaccccaaaaaccccjjjnnnttttxxxxyyyyyvvvrrrnnneeecccccc
+abcccaacccccccaaaaaaaaaccccccccaaaaaacccciiinnnttttxxxyyyyywvvrrrnnneeecccccc
+abcccaaaaaaccaaaaaaaacccccccccaaaaaaaaccciiiinnnttttxyyywyyywvrrrnnneeecccccc
+abcccaaaaaaccaaaaaaaacccccccccaaaaaaaacccciiinnnntttxwywwyyywwwrrnnneeecccccc
+abcaaaaaaaccaaaaaaaaaccccccccccccaacccccccciiinnnttwwwwwwwwwwwwrrnnneeecccccc
+abcaaaaaaaccaaaaaacccccccccccccccaaccccccaaiiiinnttwwwwwwwwwwwrrrnnnffecccccc
+abcccaaaaaaccaaaaaccccccccccccccccccccaaaaaciiinnssswwwssssrwwrrrnnnfffcccccc
+abaacaaccaaccaaaccccccccaacccccccccccccaaaaaiiinnssssssssssrrrrrronnfffcccccc
+abaccaaccaacccccccccaaacaacccccccccccccaaaaaiiimmmssssssmoosrrrrooonffaaacccc
+abaaaccccaaaaaaccccccaaaaaccccccccccccaaaaaccihmmmmsssmmmoooooooooofffaaacccc
+abaaaccccaaaaaacccccccaaaaaacccccccccccccaacchhhmmmmmmmmmoooooooooffffaaccccc
+abaacccaaaaaaaccccccaaaaaaaaccccaaccccccccccchhhhmmmmmmmgggggooofffffaaaccccc
+abaacccaaaaaaaccccccaaaaaaaccccaaaaccccccccccchhhhmmmmhggggggggfffffaaaaccccc
+abccccccaaaaaaacccccaacaaaaacccaaaaccccccccccchhhhhhhhggggggggggfffaacaaccccc
+abccaacccaaaaaaccccccccaaaaaccaaaaacccccccccccchhhhhhhggaaaaaaccccccccccccccc
+abccaaaccaaccccccccccccccaaaaaaaaaccccccccccccccchhhhaaaccaaaacccccccccccccaa
+abaaaaaaaccccccccccccccccaaaaaaaaccccccccccccccccccccaaaccccaaccccccccccccaaa
+abaaaaaaaccccccccaaaccccacaaaaaacccccccccccccccccccccaaaccccccccccccccccccaaa
+abaaaaaacccccccaaaaacaaaaaaaaaaacccccccccccccccccccccaaccccccccccccccccaaaaaa
+abaaaaaacccccccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaaaa
diff --git a/day12/main.c b/day12/main.c
@@ -0,0 +1,190 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <err.h>
+
+struct coords
+{
+ int x;
+ int y;
+ int elevation;
+ int explored;
+ struct coords *parent;
+};
+
+struct FIFOqueue
+{
+ int size;
+ struct coords *contents[128];
+};
+
+void
+enqueue(struct FIFOqueue *queue, struct coords *item)
+{
+ queue->contents[queue->size++] = item;
+}
+
+struct coords*
+dequeue(struct FIFOqueue *queue)
+{
+ struct coords *item = queue->contents[0];
+ queue->size--;
+ for (int i = 0; i < queue->size; i++)
+ queue->contents[i] = queue->contents[i+1];
+ return item;
+}
+
+// Depth-first search algorithm
+int
+traverseMountain(struct coords *map[41][77], struct coords *start, struct coords *end)
+{
+ int steps = 0;
+
+ struct FIFOqueue *queue = (struct FIFOqueue *)malloc(sizeof(struct FIFOqueue));
+ queue->size = 0;
+
+ start->explored = 1;
+
+ enqueue(queue, start);
+
+ while (queue->size > 0)
+ {
+ // Current position
+ struct coords *cur = dequeue(queue);
+
+ if (cur == end)
+ {
+ int result = 0;
+ while (end->parent)
+ {
+ end = end->parent;
+ result++;
+ }
+ // Reset state
+ for(int x = 0; x < 41; x++)
+ {
+ for(int y = 0; y < 77; y++)
+ {
+ map[x][y]->explored = 0;
+ map[x][y]->parent = NULL;
+ }
+ }
+ free(queue);
+ return result;
+ }
+
+ // North
+ if (cur->y - 1 >= 0
+ && ! map[cur->x][cur->y - 1]->explored
+ && map[cur->x][cur->y - 1]->elevation - 1
+ <= map[cur->x][cur->y]->elevation)
+ {
+ map[cur->x][cur->y - 1]->explored = 1;
+ map[cur->x][cur->y - 1]->parent = map[cur->x][cur->y];
+ enqueue(queue, map[cur->x][cur->y - 1]);
+ }
+
+ // East
+ if (cur->x + 1 < 41
+ && ! map[cur->x + 1][cur->y]->explored
+ && map[cur->x + 1][cur->y]->elevation - 1
+ <= map[cur->x][cur->y]->elevation)
+ {
+ map[cur->x + 1][cur->y]->explored = 1;
+ map[cur->x + 1][cur->y]->parent = map[cur->x][cur->y];
+ enqueue(queue, map[cur->x + 1][cur->y]);
+ }
+
+ // South
+ if (cur->y + 1 < 77
+ && ! map[cur->x][cur->y + 1]->explored
+ && map[cur->x][cur->y + 1]->elevation - 1
+ <= map[cur->x][cur->y]->elevation)
+ {
+ map[cur->x][cur->y + 1]->explored = 1;
+ map[cur->x][cur->y + 1]->parent = map[cur->x][cur->y];
+ enqueue(queue, map[cur->x][cur->y + 1]);
+ }
+
+ // West
+ if (cur->x - 1 >= 0
+ && ! map[cur->x - 1][cur->y]->explored
+ && map[cur->x - 1][cur->y]->elevation - 1
+ <= map[cur->x][cur->y]->elevation)
+ {
+ map[cur->x - 1][cur->y]->explored = 1;
+ map[cur->x - 1][cur->y]->parent = map[cur->x][cur->y];
+ enqueue(queue, map[cur->x - 1][cur->y]);
+ }
+ }
+}
+
+int
+main (void)
+{
+ FILE *fp = fopen("input.txt", "r");
+ if (fp == NULL)
+ {
+ err(1, "Failed to open input.txt");
+ exit(EXIT_FAILURE);
+ }
+
+ struct coords *map[41][77] = { NULL };
+ struct coords *start = NULL;
+ struct coords *end = NULL;
+
+ int n = 0;
+ char *line = NULL;
+ size_t linesize = 0;
+ ssize_t linelen = 0;
+ while ((linelen = getline(&line, &linesize, fp)) != -1)
+ {
+ line[--linelen] = '\0';
+ for (int i = 0; i < linelen; i++)
+ {
+ map[n][i] = (struct coords *)malloc(sizeof(struct coords));
+ map[n][i]->x = n;
+ map[n][i]->y = i;
+ map[n][i]->elevation = (int)line[i];
+ map[n][i]->explored = 0;
+ map[n][i]->parent = NULL;
+
+ if (line[i] == 'S')
+ {
+ start = map[n][i];
+ start->elevation = 97; // 'a'
+ }
+ else if (line[i] == 'E')
+ {
+ end = map[n][i];
+ end->elevation = 123; // 'z' + 1
+ }
+ }
+ n++;
+ }
+ free(line);
+ if (ferror(fp))
+ err(1, "getline");
+ fclose(fp);
+
+ int part1 = traverseMountain(map, start, end);
+
+ int part2 = 999;
+ for(int x = 0; x < 41; x++)
+ {
+ for(int y = 0; y < 77; y++)
+ {
+ if (map[x][y]->elevation == 'a')
+ {
+ int temp = traverseMountain(map, map[x][y], end);
+ if (temp && temp < part2)
+ part2 = temp;
+ }
+ }
+ }
+
+ printf("The shortest path up to the peak requires %d steps.\n", part1);
+ printf("The shortest path from any lowest point requires %d steps.\n", part2);
+
+ exit(EXIT_SUCCESS);
+}
