day11.c (3715B)
1 /* 2 Test input #1 works only with part1 of the puzzle. 3 Test input #2 works only with part2 of the puzzle. 4 */ 5 6 #include <stdio.h> 7 #include <string.h> 8 #include <strings.h> 9 #include <stdbool.h> 10 #include <stdlib.h> 11 #include <inttypes.h> 12 #include "cputime.h" 13 14 #define NAME_LEN 4 15 #define MAX_NODES 10000 16 17 typedef struct Node { 18 char name[NAME_LEN]; 19 int adj_l; 20 int adj[32]; 21 bool visited; 22 bool dead; 23 } Node; 24 25 typedef struct { 26 Node nodes[MAX_NODES]; 27 int cnt; 28 } Nodes; 29 30 Node * find(Nodes *nodes, char name[4]) { 31 Node *n = NULL; 32 for (int i=0;i<nodes->cnt;++i) { 33 if (strncmp(name, nodes->nodes[i].name, NAME_LEN-1)==0) { 34 return &nodes->nodes[i]; 35 } 36 } 37 return n; 38 } 39 40 int find_index(Nodes *nodes, char name[4]) { 41 for (int i=0;i<nodes->cnt;++i) { 42 if (strncmp(name, nodes->nodes[i].name, NAME_LEN-1)==0) { 43 return i; 44 } 45 } 46 return -1; 47 } 48 49 int get_index(Nodes *nodes, Node *node) { 50 for (int i=0;i<nodes->cnt;++i) { 51 if (&nodes->nodes[i]==node) { 52 return i; 53 } 54 } 55 return -1; 56 } 57 58 int find_or_create(Nodes *nodes, char name[4]) { 59 int idx = find_index(nodes, name); 60 if (idx!=-1) return idx; 61 idx = nodes->cnt++; 62 Node *n = &nodes->nodes[idx]; 63 strcpy(n->name, name); 64 return idx; 65 } 66 67 int bfs(Nodes *nodes) { 68 int num = 0; 69 int start = find_index(nodes, "you"); 70 int end = find_index(nodes, "out"); 71 if (start==-1||end==-1) return -1; 72 int queue[MAX_NODES] = {0}; 73 int front = 0; 74 int back = 0; 75 queue[back++] = start; 76 while (front<back) { 77 if (front>=MAX_NODES||back>=MAX_NODES) exit(1); 78 int cur = queue[front++]; 79 if (cur==end) num++; 80 Node *cur_node = &nodes->nodes[cur]; 81 for (int i=0;i<cur_node->adj_l;++i) { 82 queue[back++] = cur_node->adj[i]; 83 } 84 } 85 return num; 86 } 87 88 int64_t dfs_walk(Nodes *nodes, int idx, int out) { 89 Node *n = &nodes->nodes[idx]; 90 if (idx==out) return 1; 91 if (n->dead) return 0; 92 n->visited = true; 93 int64_t num = 0; 94 for (int i=0;i<n->adj_l;++i) { 95 if (nodes->nodes[n->adj[i]].visited) continue; 96 num += dfs_walk(nodes, n->adj[i], out); 97 } 98 n->visited = false; 99 if (num==0) { 100 n->dead = true; 101 } 102 return num; 103 } 104 105 int64_t dfs(Nodes *nodes, int from, int to) { 106 int num = 0; 107 for (int i=0;i<nodes->nodes[from].adj_l;++i) { 108 num += dfs_walk(nodes, nodes->nodes[from].adj[i], to); 109 } 110 for (int i=0;i<nodes->cnt;++i) nodes->nodes[i].dead = false; 111 return num; 112 } 113 // svr -> fft -> dac -> out; dac never connects to fft 114 int64_t part2(Nodes *nodes) { 115 int svr = find_index(nodes, "svr"); 116 int out = find_index(nodes, "out"); 117 int dac = find_index(nodes, "dac"); 118 int fft = find_index(nodes, "fft"); 119 if (svr==-1||out==-1||dac==-1||fft==-1) return -1; 120 int64_t n1 = dfs(nodes, svr, fft); 121 int64_t n2 = dfs(nodes, fft, dac); 122 int64_t n3 = dfs(nodes, dac, out); 123 return n1*n2*n3; 124 } 125 126 int main(void) { 127 char buf[NAME_LEN]; 128 int buf_l = 0; 129 Nodes *nodes = malloc(sizeof(Nodes)); 130 bzero(nodes, sizeof(Nodes)); 131 Node *node = NULL; 132 for (int c=getchar();c!=EOF;c=getchar()) { 133 if (c>='a'&&c<='z') buf[buf_l++] = c; 134 else if (c==':') { 135 node = &nodes->nodes[find_or_create(nodes, buf)]; 136 buf_l = 0; 137 } else if (c=='\n'||(c==' '&&buf_l>0)) { 138 node->adj[node->adj_l++] = find_or_create(nodes, buf); 139 buf_l = 0; 140 if (c=='\n') node = NULL; 141 } 142 } 143 144 int p1 = bfs(nodes); 145 int64_t p2 = part2(nodes); 146 printf("p1: %d\np2: %"PRIi64"\n", p1, p2); 147 return 0; 148 } 149 // 15380569 too low