advent2023

puzzle.c (4940B)

---

 #define _DEFAULT_SOURCE
 
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <assert.h>
 #include <stdbool.h>
 #include <inttypes.h>
 
 #define STR_LEN 2048
 
 typedef struct Node {
 	char name[4];
 	char left[4];
 	char right[4];
 	struct Node *next;
 } Node;
 
 Node * new_node(Node *orig) {
 	Node *node = malloc(sizeof(Node));
 	memset(node, 0, sizeof(Node));
 	if (orig!=NULL) {
 		strncpy(node->name, orig->name, 4);
 		strncpy(node->left, orig->left, 4);
 		strncpy(node->right, orig->right, 4);
 	}
 	return node;
 }
 
 Node * find_node(Node *first, char name[4]) {
 	Node *node = first;
 	while (node!=NULL) {
 		if (strncmp(name, node->name, 3)==0) {
 			return node;
 		}
 		node = node->next;
 	}
 	return NULL;
 }
 
 typedef struct Anode {
 	Node *start;
 	uint64_t znode;
 } Anode;
 
 typedef struct Item {
 	Node *node;
 	uint64_t steps;
 	struct Item *next;
 } Item;
 Item * new_item() {
 	Item *item = malloc(sizeof(Item));
 	memset(item, 0, sizeof(Item));
 	return item;
 }
 Item * find_item(Item *items, Node *node) {
 	Item *item = items;
 	while (item!=NULL) {
 		if (item->node == node) return item;
 		item = item->next;
 	}
 	return NULL;
 }
 void print_items(Item *items) {
 	Item *item = items;
 	while (item!=NULL) {
 		printf("%s[%" PRIu64 "] -> ", item->node->name, item->steps);
 		item = item->next;
 	}
 	printf("\n");
 }
 void free_items(Item *items) {
 	Item *item = items;
 	while (item!=NULL) {
 		Item *n = item->next;
 		free(item);
 		item = n;
 	}
 }
 
 bool check_z_nodes(Anode *anodes, size_t len) {
 	for (size_t i=0; i<len; ++i) {
 		if (anodes[i].start->name[2]!='Z') {
 			return false;
 		}
 	}
 	return true;
 }
 
 void print_nodes(Node *first) {
 	Node *node = first;
 	while (node!=NULL) {
 		printf("n:%s, l:%s, r:%s\n", node->name, node->left, node->right);
 		node=node->next;
 	}
 }
 
 static uint64_t gcd(uint64_t a, uint64_t b) {
 	return b==0 ? a : gcd(b, a%b);
 }
 
 static uint64_t lcm(uint64_t a, uint64_t b) {
 	return (a*b)/gcd(a,b);
 }
 
 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;
 
 	Node *nodes = NULL;
 	Node *nodes_last = NULL;
 	Anode *anodes = NULL;
 	size_t anodes_len = 0;
 	const char *instructions = NULL;
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
 		// first line is always instructions
 		size_t len = strlen(buf);
 		if (line_num==0) {
 			instructions = strndup(buf, len-1); // removing \n
 		} else if (len>1) {
 			Node *node = new_node(NULL);
 			int cnt = sscanf(buf, "%3s = (%3s, %3s)\n", node->name, node->left, node->right);
 			if (cnt!=3) {
 				free(node);
 				printf("error %d parsing %s\n", cnt, buf);
 				return;
 			}
 			if (nodes==NULL) nodes = node;
 			if (nodes_last!=NULL) nodes_last->next = node;
 			nodes_last = node;
 
 			// starting nodes for p.2
 			if (node->name[2]=='A') {
 				++anodes_len;
 				anodes = realloc(anodes, anodes_len*sizeof(Anode));
 				anodes[anodes_len-1].start = node;
 				anodes[anodes_len-1].znode = 0;
 			}
 		}
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
 	uint64_t steps = 0;
 	int il = strlen(instructions);
 	// p.1
 	Node *n = find_node(nodes, "AAA");
 	while (1) {
 		char instr = instructions[steps % il];
 		if (instr!='L'&&instr!='R') {
 			printf("illegal instruction %c\n", instr);
 			break;
 		}
 		Node *nn = find_node(nodes, instr=='L'?n->left:n->right);
 		if (nn==NULL) {
 			printf("node %s was not found\n", instr=='L'?n->left:n->right);
 			break;
 		}
 		n=nn;
 		++steps;
 		if (strcmp(n->name, "ZZZ")==0) {
 			*result1 = steps;
 			break;
 		}
 		if (steps==UINT64_MAX) {
 			printf("steps overflow\n");
 			break;
 		}
 	}
 
 	// p.2
 	// fill anodes with znode
 	for (size_t i=0; i<anodes_len; ++i) {
 		steps = 0;
 		Node *n = anodes[i].start;
 		//printf("filling anode %s\n", n->name);
 		Item *hist = NULL;
 		Item *hist_last = NULL;
 		Node *z = NULL;
 		Node *w = NULL;
 		while (1) {
 			char instr = instructions[steps%il];
 			n = find_node(nodes, instr=='L'?n->left:n->right);
 			//printf("checking %s\n", n->name);
 			if (n->name[2]=='Z') {
 				if (z!=NULL&&n!=z) {
 					printf("z nodes are different\n");
 				}
 				anodes[i].znode = steps+1;
 				z = n;
 			}
 			if (find_item(hist, n)==NULL) {
 				Item *it = new_item();
 				it->node = n;
 				it->steps = steps;
 				if (hist==NULL) hist=it;
 				if (hist_last!=NULL) hist_last->next=it;
 				hist_last=it;
 			} else if (w==NULL) {
 				//printf("anode %s wrapped up on %s (%" PRIu64 ")\n", anodes[i].start->name, n->name, steps+1);
 				w = n;
 				//free_items(hist);
 				//break;
 			}
 			++steps;
 			if (z!=NULL) {
 				free_items(hist);
 				break;
 			}
 			if (steps==UINT64_MAX) {
 				break;
 			}
 		}
 	}
 
 	*result2 = anodes[0].znode;
 	for (size_t i=1; i<anodes_len; ++i) {
 		*result2 = lcm(*result2, anodes[i].znode);
 	}
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 	(void)result2;
 }