20b.c (3160B)
1 /* 2 This one is a bit weird. This program works only for my specific input. 3 Similarly to day 8, this program outputs 4 numbers and you have to 4 take the lcm of them. 5 6 I solved it this way: 7 1. First, using a modified version of the code for part one (graph.c), 8 I printed the graph as a list of adjacency lists. 9 2. I then went to https://csacademy.com/app/graph_editor and observed 10 the graph. I noticed that after the button is pressed, the signal 11 is sent to 4 independent parts of the graph. Each of these parts has 12 only one entry point and one exit point. The entry points were not 13 flip-flop nodes. 14 3. Finally, I implemented the code to check how long it takes for the 15 graph to go back to the initial state, and I simulated sending a 16 signal to each of the 4 parts independently. 17 */ 18 19 #include <inttypes.h> 20 #include <stdbool.h> 21 #include <stdio.h> 22 #include <string.h> 23 24 #define N 100 25 #define ischar(c) (c >= 'a' && c <= 'z') 26 27 typedef struct { 28 int nin, nout, in[N], out[N]; 29 char name[20], outc[N][20]; 30 bool isff, ison, reg[N]; 31 } node_t; 32 33 typedef struct { 34 int i, n; 35 struct {int node; bool hi;} elem[500]; 36 } queue_t; 37 38 char *buf, line[N][N]; 39 bool rx; 40 int b, r, n; 41 node_t m[N]; 42 queue_t q; 43 44 void add(int v, bool hi) { 45 q.elem[q.n].node = v; 46 q.elem[q.n].hi = hi; 47 q.n++; 48 } 49 50 void send(int v, bool hi) { 51 for (int j = 0; j < m[v].nout; j++) { 52 add(m[v].out[j], hi); 53 m[m[v].out[j]].reg[v] = hi; 54 } 55 } 56 57 int findm(char *name) { 58 for (int k = 0; k < n; k++) 59 if (!strcmp(m[k].name, name)) 60 return k; 61 return n; 62 } 63 64 void sig(int node, bool high) { 65 q.n = q.i = 0; 66 add(node, high); 67 while (q.i < q.n) { 68 int v = q.elem[q.i].node; 69 bool hi = q.elem[q.i].hi; 70 q.i++; 71 72 if (v == b) { 73 send(v, hi); 74 } else if (m[v].isff) { 75 if (!hi) 76 send(v, m[v].ison = !m[v].ison); 77 } else { 78 bool allhi = true; 79 for (int j = 0; j < m[v].nin; j++) 80 allhi = allhi && m[v].reg[m[v].in[j]]; 81 send(v, !allhi); 82 } 83 } 84 } 85 86 bool isclean(void) { 87 for (int i = 0; i < n; i++) { 88 if (m[i].isff && m[i].ison) 89 return false; 90 else 91 for (int j = 0; j < m[i].nin; j++) 92 if (m[i].reg[j]) 93 return false; 94 } 95 return true; 96 } 97 98 int64_t period(int node) { 99 int64_t npush; 100 for (npush = 0; npush == 0 || !isclean(); npush++) 101 sig(node, false); 102 return npush; 103 } 104 105 int main() { 106 for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) { 107 if (ischar(*buf)) b = n; 108 m[n].isff = *buf == '%'; 109 if (!ischar(*buf)) buf++; 110 for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ; 111 buf += 4; 112 for (int i = 0; *buf != '\n'; i++) { 113 while (!ischar(*buf)) buf++; 114 for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ; 115 } 116 } 117 118 for (int i = 0; i < n; i++) { 119 for (int j = 0; m[i].outc[j][0]; j++) { 120 int k = findm(m[i].outc[j]); 121 m[i].out[m[i].nout++] = k; 122 m[k].in[m[k].nin++] = i; 123 if (k == n) { 124 for (int k = 0; m[i].outc[j][k]; k++) 125 m[n].name[k] = m[i].outc[j][k]; 126 n++; 127 } 128 } 129 } 130 131 for (int i = 0; i < n; i++) 132 if (!strcmp(m[i].name, "rx")) 133 r = i; 134 135 printf("%" PRId64 "\n", period(19)); 136 printf("%" PRId64 "\n", period(33)); 137 printf("%" PRId64 "\n", period(39)); 138 printf("%" PRId64 "\n", period(57)); 139 return 0; 140 }