day12.c

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include "../lib.h"

typedef struct {
	char *source;
	char *dest;
} conn_t; 

typedef struct {
	conn_t connections[1024];
	size_t connection_count;
} conn_list_t; 

char *alphas(char **file) {
	char *srcstr = *file;
	size_t srclen = 0;
	while (isalpha(**file)) {
		srclen += 1;
		*file += 1;
	} 
	return strndup(srcstr, srclen);
}

conn_list_t load_input(const char *path) {
	char *file = read_file(path);
	char *orig_file = file;
	if (file == NULL) {
		fprintf(stderr, "Couldn't load %s\n", path);
		exit(-1);
	}

	conn_list_t result = { 0 };
		
	while (!iseof(file)) {
		char *srcstr;
		size_t srclen = 0;
		while (isalpha(*file)) {
			char *source = alphas(&file);
			ignore_seq(&file, "-");
			char *destination = alphas(&file);
			skip_empty(&file);
			
			result.connections[result.connection_count++] = (conn_t) { source, destination };
		} 
	}
	
	free(orig_file);
	return result;
}


void free_connection_list(conn_list_t *list) {
	for (int i = 0; i < list->connection_count; i += 1) {
		free(list->connections[i].source);
		free(list->connections[i].dest);
	}
}


void print_connection_list(conn_list_t *list) {
	for (int i = 0; i < list->connection_count; i += 1) {
		conn_t *conn = &list->connections[i];
		printf("%s/%s\n", conn->source, conn->dest);
	}
}

typedef struct {
	char *node;
	size_t count;
} visit_t;

typedef struct {
	bool switched;
	visit_t visited[2048];
	size_t count;
} visit_list_t;

int count = 0;

void count_paths(conn_list_t *list, visit_list_t visit, char *node, int depth) {
	if (strcmp(node, "start") == 0 && depth != 0) {
		return;
	}

	for (int i = 0; i < visit.count; i += 1) {
		if (strcmp(visit.visited[i].node, node) == 0) {
			if (!visit.switched) {
				visit.switched = true;
				visit.visited[i].node = "$#534657823465782396459783265";
				count_paths(list, visit, node, depth);
			}
			return;
		}
	}
	
#if 0
	for (int i = 0; i < depth * 2; i += 1) {
		printf("%c", i % 2 ? '|' : ' ');
	}

	printf("%s\n", node);
#endif
			
	if (strcmp(node, "end") == 0) {
		count += 1;
		return;
	}

	if (islower(*node)) {
		visit.visited[visit.count++] = (visit_t) { node, 1 };
	}
	
	for (int i = 0; i < list->connection_count; i += 1) {
		conn_t *conn = &list->connections[i];
		
		if (strcmp(conn->source, node) == 0) {
			count_paths(list, visit, conn->dest, depth + 1);
		}
		if (strcmp(conn->dest, node) == 0) {
			count_paths(list, visit, conn->source, depth + 1);
		}
	}
}

int main() {
	conn_list_t input = load_input("day12/test_input.txt");
	print_connection_list(&input);
	count_paths(&input, (visit_list_t) { .switched = true }, "start", 0);
	printf("Part 1: %d\n", count);
	count = 0;
	count_paths(&input, (visit_list_t) { 0 }, "start", 0);
	printf("Part 2: %d\n", count);
	free_connection_list(&input);
}