advent2023

commit e584643b1730db34a12cc42cc47f34b48aa9de36
parent 5f889027bb1ee05d04ee549c8c05641f21c6e01e
Author: bsandro <email@bsandro.tech>
Date:   Sat,  9 Dec 2023 03:57:14 +0200

day 08 p2

Diffstat:
M
day08/puzzle.c
 | 
121
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------

1 file changed, 93 insertions(+), 28 deletions(-)
diff --git a/day08/puzzle.c b/day08/puzzle.c
@@ -43,9 +43,44 @@ Node * find_node(Node *first, char name[4]) {
 
 typedef struct Anode {
 	Node *start;
-	int znodes[];
+	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') {
@@ -63,6 +98,14 @@ void print_nodes(Node *first) {
 	}
 }
 
+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) {
@@ -99,16 +142,16 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 			// starting nodes for p.2
 			if (node->name[2]=='A') {
 				++anodes_len;
-				anodes = realloc(anodes, anodes_len*sizeof(Anode*));
+				anodes = realloc(anodes, anodes_len*sizeof(Anode));
 				anodes[anodes_len-1].start = node;
-				//anodes[anodes_len-1].znodes = NULL;
+				anodes[anodes_len-1].znode = 0;
 			}
 		}
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
-	int steps = 0;
+	uint64_t steps = 0;
 	int il = strlen(instructions);
 	// p.1
 	Node *n = find_node(nodes, "AAA");
@@ -129,40 +172,62 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 			*result1 = steps;
 			break;
 		}
-		if (steps==INT_MAX) {
+		if (steps==UINT64_MAX) {
 			printf("steps overflow\n");
 			break;
 		}
 	}
 
 	// p.2
-	steps = 0;
-	while (1) {
-		char instr = instructions[steps % il];
-		if (instr!='L'&&instr!='R') {
-			printf("illegal instruction %c\n", instr);
-			break;
-		}
-		for (size_t i=0; i<anodes_len; ++i) {
-			Node *n = anodes[i];
-			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);
-				return;
+	// 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;
 			}
-			anodes[i] = nn;
-		}
-		++steps;
-		if (check_z_nodes(anodes, anodes_len)) {
-			*result2 = steps;
-			break;
-		}
-		if (steps==INT_MAX) {
-			printf("steps overflow\n");
-			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;