advent2025

commit 9e218d4783dc432e405a84c993f919178022bbe2
parent 7fd372e83bd54861fc4e26e8cc1ebba8b9f427ba
Author: bsandro <email@bsandro.tech>
Date:   Thu, 11 Dec 2025 19:15:17 +0200

day11 p2 does not work yet

Diffstat:
M
day11.c
 | 
109
++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------

1 file changed, 77 insertions(+), 32 deletions(-)
diff --git a/day11.c b/day11.c
@@ -1,15 +1,18 @@
 #include <stdio.h>
 #include <string.h>
+#include <strings.h>
 #include <stdbool.h>
+#include <stdlib.h>
 #include "cputime.h"
 
 #define NAME_LEN 4
-#define MAX_NODES 600
+#define MAX_NODES 100000
 
 typedef struct Node {
     char name[NAME_LEN];
     int adj_l;
-    struct Node *adj[32];
+    int adj[32];
+    bool visited;
 } Node;
 
 typedef struct {
@@ -27,68 +30,110 @@ Node * find(Nodes *nodes, char name[4]) {
     return n;
 }
 
-Node * find_or_create(Nodes *nodes, char name[4]) {
-    Node *n = find(nodes, name);
-    if (n!=NULL) return n;
-    n = &nodes->nodes[nodes->cnt++];
+int find_index(Nodes *nodes, char name[4]) {
+    for (int i=0;i<nodes->cnt;++i) {
+        if (strncmp(name, nodes->nodes[i].name, NAME_LEN-1)==0) {
+            return i;
+        }
+    }
+    return -1;
+}
+
+int get_index(Nodes *nodes, Node *node) {
+    for (int i=0;i<nodes->cnt;++i) {
+        if (&nodes->nodes[i]==node) {
+            return i;
+        }
+    }
+    return -1;
+}
+
+int find_or_create(Nodes *nodes, char name[4]) {
+    int idx = find_index(nodes, name);
+    if (idx!=-1) return idx;
+    idx = nodes->cnt++;
+    Node *n = &nodes->nodes[idx];
     strcpy(n->name, name);
-    return n;
+    return idx;
 }
 
-int bfs1(Nodes *nodes) {
+int bfs(Nodes *nodes) {
     int num = 0;
-    Node *start = find(nodes, "you");
-    Node *end = find(nodes, "out");
-    Node *queue[MAX_NODES] = {0};
+    int start = find_index(nodes, "you");
+    int end = find_index(nodes, "out");
+    int queue[MAX_NODES] = {0};
     int front = 0;
     int back = 0;
     queue[back++] = start;
     while (front<back) {
-        Node *cur = queue[front++];
+        int cur = queue[front++];
         if (cur==end) num++;
-        for (int i=0;i<cur->adj_l;++i) {
-            queue[back++] = cur->adj[i];
+        Node *cur_node = &nodes->nodes[cur];
+        for (int i=0;i<cur_node->adj_l;++i) {
+            queue[back++] = cur_node->adj[i];
         }
     }
     return num;
 }
 
-int bfs2(Nodes *nodes) {
+int dfs_walk(Nodes *nodes, int idx) {
+    int end = find_index(nodes, "out");
+    int dac = find_index(nodes, "dac");
+    int fft = find_index(nodes, "fft");
+    if (idx==end) {
+        if (nodes->nodes[dac].visited&&nodes->nodes[fft].visited) return 1;
+        else return 0;
+    }
+    Node *n = &nodes->nodes[idx];
+    n->visited = true;
     int num = 0;
-    Node *start = find(nodes, "you");
-    Node *end = find(nodes, "out");
-    Node *queue[MAX_NODES] = {0};
-    int front = 0;
-    int back = 0;
-    queue[back++] = start;
-    while (front<back) {
-        Node *cur = queue[front++];
-        if (cur==end) num++;
-        for (int i=0;i<cur->adj_l;++i) {
-            queue[back++] = cur->adj[i];
-        }
+    for (int i=0;i<n->adj_l;++i) {
+        num += dfs_walk(nodes, 0);
+    }
+    n->visited = false;
+    return num;
+}
+
+int dfs(Nodes *nodes) {
+    int num = 0;
+    Node *start = find(nodes, "svr");
+    for (int i=0;i<start->adj_l;++i) {
+        num += dfs_walk(nodes, start->adj[i]);
     }
     return num;
 }
 
+void print_nodes(Nodes *nodes) {
+    printf("%d nodes\n", nodes->cnt);
+    for (int i=0;i<nodes->cnt;++i) {
+        printf("(%d) [%s] -> ", i, nodes->nodes[i].name);
+        for (int j=0;j<nodes->nodes[i].adj_l;++j) {
+            printf("[%d:%s]", nodes->nodes[i].adj[j], nodes->nodes[nodes->nodes[i].adj[j]].name);
+        }
+        printf("\n");
+    }
+}
+
 int main(void) {
     char buf[NAME_LEN];
     int buf_l = 0;
-    Nodes nodes = {0};
+    Nodes *nodes = malloc(sizeof(Nodes));
+    bzero(nodes, sizeof(Nodes));
     Node *node = NULL;
     for (int c=getchar();c!=EOF;c=getchar()) {
         if (c>='a'&&c<='z') buf[buf_l++] = c;
         else if (c==':') {
-            node = find_or_create(&nodes, buf);
+            node = &nodes->nodes[find_or_create(nodes, buf)];
             buf_l = 0;
         } else if (c=='\n'||(c==' '&&buf_l>0)) {
-            node->adj[node->adj_l++] = find_or_create(&nodes, buf);
+            node->adj[node->adj_l++] = find_or_create(nodes, buf);
             buf_l = 0;
             if (c=='\n') node = NULL;
         }
     }
 
-    int p1 = bfs1(&nodes);
-    printf("p1: %d\n", p1);
+    int p1 = bfs(nodes);
+    int p2 = 0;//dfs(nodes);
+    printf("p1: %d\np2: %d\n", p1, p2);
     return 0;
 }