advent2021

puzzle.c (6555B)

---

 #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, 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");
 	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) {
 		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);
 
 	for (size_t i = 0; i < start->neighbors.count; ++i) {
 		int *data = start->neighbors.data;
 		struct node_t *node = node_get(&nodes, data[i]);
 		assert(node != NULL);
 		struct array_t visited = { .data = NULL };
 		array_init(&visited, sizeof(void *), 10);
 
 		*result1 += traverse(&nodes, node, &visited, false);
 		visited_clean(&visited);
 		*result2 += traverse(&nodes, node, &visited, true);
 		visited_clean(&visited);
 
 		free(visited.data);
 	}
 
 	free(nodes.data);
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
 int traverse(struct array_t *nodes, struct node_t *node, struct array_t *visited, bool part2) {
 	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);
 	if (node->is_small) {
 		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++;
 	}
 
 	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, part2);
 		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 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;
 	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-1);
 			++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);
 	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;
 	}
 
 	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-1);
 	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;
 }