advent2021

commit 8cd6edcd11d419092f195011c0640d01e06647e8
parent 5c08ef9d279ef19be6d6bd7dec69e6d00b0faf3f
Author: bsandro <[email protected]>
Date:   Mon, 13 Dec 2021 03:04:10 +0200

Day 12, puzzle 2

Diffstat:
M
day12/Makefile
 | 
2
+-
M
day12/puzzle.c
 | 
63
+++++++++++++++++++++++++++++++++++++++++----------------------

2 files changed, 42 insertions(+), 23 deletions(-)
diff --git a/day12/Makefile b/day12/Makefile
@@ -2,7 +2,7 @@ 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
+CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common
 LDFLAGS=-lc
 
 all: $(NAME)
diff --git a/day12/puzzle.c b/day12/puzzle.c
@@ -37,8 +37,9 @@ 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);
+int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited, bool p2);
 struct visit_t * visited_get(struct array_t *visited, int id);
+void visited_clean(struct array_t *visited);
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
@@ -58,7 +59,6 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 	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);
@@ -71,31 +71,27 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 	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);
+		assert(node != NULL);
 		struct array_t visited = { .data = NULL };
 		array_init(&visited, sizeof(void *), 10);
-		int count = traverse(&nodes, node, &visited);
+
+		*result1 += traverse(&nodes, node, &visited, false);
+		visited_clean(&visited);
+		*result2 += traverse(&nodes, node, &visited, true);
+		visited_clean(&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) {
+int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited, bool part2) {
 	assert(node != NULL);
 
 	if (node->is_end) {
@@ -108,11 +104,27 @@ int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited
 
 	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) {
+		if (part2 && visit->count > 0) {
+			struct visit_t **data = visited->data;
+			for (size_t i = 0; i < visited->count; ++i) {
+				struct visit_t *vvisit = data[i];
+				if (vvisit->count > 1 && vvisit->node_id != node->id) {
+					struct node_t *vnode = node_get(nodes, vvisit->node_id);
+					assert(vnode != NULL);
+					if (vnode->is_small) {
+						return 0;
+					}
+				}
+			}
+		} else if (!part2 && visit->count > 0) {
+			return 0;
+		}
+
+		if (visit->count > 1) {
 			return 0;
 		}
+
 		visit->count++;
 	}
 
@@ -121,10 +133,8 @@ int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited
 		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;
-		}
+		int ncount = traverse(nodes, neighbor, visited, part2);
+		count += ncount;
 	}
 
 	if (node->is_small) {
@@ -156,6 +166,17 @@ struct visit_t * visited_get(struct array_t *visited, int id) {
 	return visit;
 }
 
+void visited_clean(struct array_t *visited) {
+	assert(visited != NULL);
+	struct visit_t **data = visited->data;
+	assert(data != NULL);
+	for (size_t i = 0; i < visited->count; ++i) {
+		free(data[i]);
+	}
+	visited->count = 0;
+	bzero(visited->data, sizeof(void *) * visited->cap);
+}
+
 void add_path(struct array_t *nodes, const char *str) {
 	char names[2][NAME_LEN];
 	int i = 0;
@@ -176,7 +197,6 @@ void add_path(struct array_t *nodes, const char *str) {
 	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);
 	}
@@ -199,7 +219,6 @@ int node_add(struct array_t *nodes, const char *name) {
 		return node_id;
 	}
 
-	//printf("adding node %s...\n", name);
 	if (nodes->count >= nodes->cap) {
 		array_expand(nodes);
 	}