commit 5c08ef9d279ef19be6d6bd7dec69e6d00b0faf3f
parent 42396cd320317f4cd68c8b51c878a5b628477ae6
Author: bsandro <[email protected]>
Date: Sun, 12 Dec 2021 22:30:42 +0200
Day 12, puzzle 1
Diffstat:
7 files changed, 373 insertions(+), 0 deletions(-)
diff --git a/day12/Makefile b/day12/Makefile
@@ -0,0 +1,31 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.c ../common/*.c)
+DEPS:=$(wildcard *.h ../common/*.h)
+OBJ:=$(SRC:.c=.o)
+CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common
+LDFLAGS=-lc
+
+all: $(NAME)
+
+.PHONY: clean run
+
+clean:
+ rm -f $(OBJ) $(NAME)
+
+%.o : %.c $(DEPS)
+ @$(CC) $(CFLAGS) -c $< -o $@
+
+$(NAME): $(OBJ)
+ @$(CC) $(OBJ) -o $@ $(LDFLAGS)
+
+run: $(NAME)
+ @./$(NAME) input.txt
+
+test: $(NAME)
+ @./$(NAME) test1.txt
+
+test2: $(NAME)
+ @./$(NAME) test2.txt
+
+test3: $(NAME)
+ @./$(NAME) test3.txt
diff --git a/day12/input.txt b/day12/input.txt
@@ -0,0 +1,25 @@
+ey-dv
+AL-ms
+ey-lx
+zw-YT
+hm-zw
+start-YT
+start-ms
+dv-YT
+hm-ms
+end-ey
+AL-ey
+end-hm
+rh-hm
+dv-ms
+AL-dv
+ey-SP
+hm-lx
+dv-start
+end-lx
+zw-AL
+hm-AL
+lx-zw
+ey-zw
+zw-dv
+YT-ms
diff --git a/day12/main.c b/day12/main.c
@@ -0,0 +1,29 @@
+#include <stdio.h>
+#include <time.h>
+#include <string.h>
+
+void puzzle(const char *filename, long long *res1, long long *res2);
+
+int main(int argc, char *argv[]) {
+ printf("Advent of Code: day 12\n");
+ double time_start = clock();
+
+ if (argc <= 1) {
+ printf("Usage: %s inputfile.txt\n", argv[0]);
+ return -1;
+ }
+
+ const char *filename = argv[1];
+ long long counter1 = -1;
+ long long counter2 = -1;
+
+ puzzle(filename, &counter1, &counter2);
+
+ printf("Puzzle #1: %lld\n", counter1);
+ printf("Puzzle #2: %lld\n", counter2);
+
+ double elapsed = clock() - time_start;
+ printf("Elapsed: %f\n", elapsed / CLOCKS_PER_SEC);
+
+ return 0;
+}
diff --git a/day12/puzzle.c b/day12/puzzle.c
@@ -0,0 +1,253 @@
+#define _DEFAULT_SOURCE
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <strings.h>
+#include <assert.h>
+#include <ctype.h>
+#include <limits.h>
+#include <stdbool.h>
+
+#include "util.h"
+
+#define STR_LEN 32
+#define NAME_LEN 8
+#define NAME_START "start"
+#define NAME_END "end"
+
+struct node_t {
+ int id;
+ char name[NAME_LEN];
+ struct array_t neighbors;
+ bool is_start;
+ bool is_end;
+ bool is_small;
+};
+
+struct visit_t {
+ int node_id;
+ int count;
+};
+
+bool is_str_lowercase(const char *str);
+struct node_t * node_get(struct array_t *nodes, int id);
+int node_find(struct array_t *nodes, const char *name);
+int node_add(struct array_t *nodes, const char *name);
+void add_path(struct array_t *nodes, const char *str);
+void neighbor_add(struct node_t *a, int id);
+int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited);
+struct visit_t * visited_get(struct array_t *visited, int id);
+
+void puzzle(const char *filename, long long *result1, long long *result2) {
+ FILE *infile = fopen(filename, "r");
+ if (infile == NULL) {
+ fprintf(stderr, "fopen() error: %s\n", strerror(errno));
+ return;
+ }
+
+ char buf[STR_LEN] = {0};
+ unsigned int line_num = 0;
+
+ *result1 = 0;
+ *result2 = 0;
+
+ struct array_t nodes = { .data = NULL };
+ // @todo handle reallocates
+ array_init(&nodes, sizeof(struct node_t), 10);
+
+ while (fgets(buf, STR_LEN, infile) != NULL) {
+ //printf("path: %s", buf);
+ add_path(&nodes, buf);
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+
+ int start_id = node_find(&nodes, "start");
+ int end_id = node_find(&nodes, "end");
+ assert(start_id != -1 && end_id != -1);
+ struct node_t *start = node_get(&nodes, start_id);
+ struct node_t *end = node_get(&nodes, end_id);
+ assert(start != NULL && end != NULL);
+
+ // task #1
+ for (size_t i = 0; i < start->neighbors.count; ++i) {
+ int *data = start->neighbors.data;
+ struct node_t *node = node_get(&nodes, data[i]);
+ if (node == NULL) {
+ printf("node %d was not found!\n", data[i]);
+ assert(false);
+ }
+ //assert(node != NULL);
+ struct array_t visited = { .data = NULL };
+ array_init(&visited, sizeof(void *), 10);
+ int count = traverse(&nodes, node, &visited);
+ free(visited.data);
+ // @todo free visited records as well
+ //printf("node %s(%d) sub-routes count: %d\n", node->name, node->id, count);
+ *result1 += count;
+ }
+
+ // @todo free neighbors
+ free(nodes.data);
+ // mutiny! ignoring feof/ferror.
+ fclose(infile);
+}
+
+int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited) {
+ assert(node != NULL);
+
+ if (node->is_end) {
+ return 1;
+ }
+
+ if (node->is_start) {
+ return 0;
+ }
+
+ struct visit_t *visit = visited_get(visited, node->id);
+ assert(visit != NULL);
+ //printf("traversing node %s(%d) visits: %d\n", node->name, node->id, visit->count);
+ if (node->is_small) {
+ if (visit->count > 0) {
+ return 0;
+ }
+ visit->count++;
+ }
+
+ int count = 0;
+ for (size_t i = 0; i < node->neighbors.count; ++i) {
+ int *data = node->neighbors.data;
+ struct node_t *neighbor = node_get(nodes, data[i]);
+ assert(neighbor != NULL);
+ int ncount = traverse(nodes, neighbor, visited);
+ if (ncount != -1) {
+ count += ncount;
+ }
+ }
+
+ if (node->is_small) {
+ visit->count--;
+ }
+
+ return count;
+}
+
+struct visit_t * visited_get(struct array_t *visited, int id) {
+ assert(visited != NULL);
+ struct visit_t **data = visited->data;
+ assert(data != NULL);
+ for (size_t i = 0; i < visited->count; ++i) {
+ if (data[i]->node_id == id) {
+ return data[i];
+ }
+ }
+
+ if (visited->count >= visited->cap) {
+ array_expand(visited);
+ }
+ data = visited->data; // could be reallocated
+ struct visit_t *visit = malloc(sizeof(struct visit_t));
+ assert(visit != NULL);
+ visit->node_id = id;
+ visit->count = 0;
+ data[visited->count++] = visit;
+ return visit;
+}
+
+void add_path(struct array_t *nodes, const char *str) {
+ char names[2][NAME_LEN];
+ int i = 0;
+ char *tmp = strndup(str, STR_LEN);
+ assert(tmp != NULL);
+ char *token = NULL;
+ while ((token = strsep(&tmp, "-\n")) != NULL) {
+ if (*token != '\0') {
+ assert(i < 2);
+ assert(strlen(token) < NAME_LEN);
+ strncpy(names[i], token, NAME_LEN);
+ ++i;
+ }
+ }
+ assert(i == 2);
+ int id_a = node_add(nodes, names[0]);
+ int id_b = node_add(nodes, names[1]);
+ struct node_t *a = node_get(nodes, id_a);
+ struct node_t *b = node_get(nodes, id_b);
+ assert(a != NULL && b != NULL);
+ //printf("path: %s(%d), %s(%d)\n", a->name, a->id, b->name, b->id);
+ if (!b->is_start) {
+ neighbor_add(a, b->id);
+ }
+ if (!a->is_start) {
+ neighbor_add(b, a->id);
+ }
+}
+
+void neighbor_add(struct node_t *a, int id) {
+ if (a->neighbors.count >= a->neighbors.cap) {
+ array_expand(&a->neighbors);
+ }
+ int *data = a->neighbors.data;
+ data[a->neighbors.count++] = id;
+}
+
+int node_add(struct array_t *nodes, const char *name) {
+ int node_id = node_find(nodes, name);
+ if (node_id != -1) {
+ return node_id;
+ }
+
+ //printf("adding node %s...\n", name);
+ if (nodes->count >= nodes->cap) {
+ array_expand(nodes);
+ }
+ static int last_id = 1;
+ struct node_t *data = (struct node_t *)nodes->data;
+ struct node_t *node = &data[nodes->count++];
+ node->id = last_id++;
+ strncpy(node->name, name, NAME_LEN);
+ if (strncmp(node->name, NAME_START, NAME_LEN) == 0) {
+ node->is_start = true;
+ } else if (strncmp(node->name, NAME_END, NAME_LEN) == 0) {
+ node->is_end = true;
+ } else if (is_str_lowercase(node->name)) {
+ node->is_small = true;
+ }
+ array_init(&node->neighbors, sizeof(int), 5);
+ return node->id;
+}
+
+int node_find(struct array_t *nodes, const char *name) {
+ struct node_t *data = (struct node_t *)nodes->data;
+ for (size_t i = 0; i < nodes->count; ++i) {
+ struct node_t *node = &data[i];
+ if (strncmp(node->name, name, NAME_LEN) == 0) {
+ return node->id;
+ }
+ }
+ return -1;
+}
+
+struct node_t * node_get(struct array_t *nodes, int id) {
+ struct node_t *data = (struct node_t *)nodes->data;
+ for (size_t i = 0; i < nodes->count; ++i) {
+ struct node_t *node = &data[i];
+ if (node->id == id) {
+ return node;
+ }
+ }
+ return NULL;
+}
+
+bool is_str_lowercase(const char *str) {
+ assert(str != NULL);
+ size_t len = strlen(str);
+ for (size_t i = 0; i < len; ++i) {
+ if (!islower(str[i])) {
+ return false;
+ }
+ }
+ return true;
+}
diff --git a/day12/test1.txt b/day12/test1.txt
@@ -0,0 +1,7 @@
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/day12/test2.txt b/day12/test2.txt
@@ -0,0 +1,10 @@
+dc-end
+HN-start
+start-kj
+dc-start
+dc-HN
+LN-dc
+HN-end
+kj-sa
+kj-HN
+kj-dc
diff --git a/day12/test3.txt b/day12/test3.txt
@@ -0,0 +1,18 @@
+fs-end
+he-DX
+fs-he
+start-DX
+pj-DX
+end-zg
+zg-sl
+zg-pj
+pj-he
+RW-he
+fs-DX
+pj-RW
+zg-RW
+start-pj
+he-WI
+zg-he
+pj-fs
+start-RW
