aboutsummaryrefslogtreecommitdiff
path: root/2023/20
diff options
context:
space:
mode:
Diffstat (limited to '2023/20')
-rw-r--r--2023/20/20a.c101
-rw-r--r--2023/20/20b.c143
-rw-r--r--2023/20/graph.c77
-rw-r--r--2023/20/graph.pngbin0 -> 162513 bytes
4 files changed, 321 insertions, 0 deletions
diff --git a/2023/20/20a.c b/2023/20/20a.c
new file mode 100644
index 0000000..99b6874
--- /dev/null
+++ b/2023/20/20a.c
@@ -0,0 +1,101 @@
1#include <inttypes.h>
2#include <stdbool.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6
7#define N 100
8#define ischar(c) (c >= 'a' && c <= 'z')
9
10typedef struct {
11 int nin, nout, in[N], out[N];
12 char name[20], outc[N][20];
13 bool isff, ison, reg[N];
14} node_t;
15
16typedef struct {
17 int i, n, node[1000];
18 bool hi[1000];
19} queue_t;
20
21char *buf, line[N][N];
22int b, n;
23int64_t hitot, lowtot;
24node_t m[N];
25
26void add(queue_t *q, int v, bool hi) {
27 q->node[q->n] = v;
28 q->hi[q->n] = hi;
29 q->n++;
30}
31
32void send(queue_t *q, int v, bool hi) {
33 for (int j = 0; j < m[v].nout; j++) {
34 add(q, m[v].out[j], hi);
35 m[m[v].out[j]].reg[v] = hi;
36 if (hi) hitot++; else lowtot++;
37 }
38}
39
40void pushbutton(void) {
41 queue_t q = {0};
42
43 add(&q, b, false);
44 lowtot++;
45 while (q.i < q.n) {
46 int v = q.node[q.i];
47 bool hi = q.hi[q.i];
48 q.i++;
49
50 if (v == b) {
51 send(&q, v, hi);
52 } else if (m[v].isff) {
53 if (!hi)
54 send(&q, v, m[v].ison = !m[v].ison);
55 } else {
56 bool allhi = true;
57 for (int j = 0; j < m[v].nin; j++)
58 allhi = allhi && m[v].reg[m[v].in[j]];
59 send(&q, v, !allhi);
60 }
61 }
62}
63
64int main() {
65 for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
66 if (ischar(*buf)) b = n;
67 m[n].isff = *buf == '%';
68 if (!ischar(*buf)) buf++;
69 for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
70 buf += 4;
71 for (int i = 0; *buf != '\n'; i++) {
72 while (!ischar(*buf)) buf++;
73 for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
74 }
75 }
76
77 for (int i = 0; i < n; i++) {
78 for (int j = 0; m[i].outc[j][0]; j++) {
79 bool found = false;
80 for (int k = 0; k < n; k++) {
81 if (!strcmp(m[k].name, m[i].outc[j])) {
82 m[i].out[m[i].nout++] = k;
83 m[k].in[m[k].nin++] = i;
84 found = true;
85 }
86 }
87 if (!found) {
88 m[i].out[m[i].nout++] = n;
89 m[n].in[m[n].nin++] = i;
90 n++;
91 }
92 }
93 }
94
95 for (int i = 0; i < 1000; i++)
96 pushbutton();
97
98 printf("%" PRId64 " (%" PRId64 " low, %" PRId64 " hi)\n",
99 hitot * lowtot, lowtot, hitot);
100 return 0;
101}
diff --git a/2023/20/20b.c b/2023/20/20b.c
new file mode 100644
index 0000000..dc0d6b3
--- /dev/null
+++ b/2023/20/20b.c
@@ -0,0 +1,143 @@
1/*
2This one is a bit weird. This program works only for my specific input
3(included in this folder). Similarly to number 8, this program outputs
44 numbers and you have to take the lcm of them.
5
6I solved it this way:
71. First, using a modified version of the code for part one (graph.c),
8 I printed the graph as a list of adjacency lists.
92. 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.
143. 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 <stdlib.h>
23#include <string.h>
24
25#define N 100
26#define ischar(c) (c >= 'a' && c <= 'z')
27
28typedef struct {
29 int nin, nout, in[N], out[N];
30 char name[20], outc[N][20];
31 bool isff, ison, reg[N];
32} node_t;
33
34typedef struct {
35 int i, n;
36 struct {int node; bool hi;} elem[500];
37} queue_t;
38
39char *buf, line[N][N];
40bool rx;
41int b, r, n;
42node_t m[N];
43queue_t q;
44
45void add(int v, bool hi) {
46 q.elem[q.n].node = v;
47 q.elem[q.n].hi = hi;
48 q.n++;
49}
50
51void send(int v, bool hi) {
52 for (int j = 0; j < m[v].nout; j++) {
53 add(m[v].out[j], hi);
54 m[m[v].out[j]].reg[v] = hi;
55 }
56}
57
58int findm(char *name) {
59 for (int k = 0; k < n; k++)
60 if (!strcmp(m[k].name, name))
61 return k;
62 return n;
63}
64
65void sig(int node, bool high) {
66 q.n = q.i = 0;
67 add(node, high);
68 while (q.i < q.n) {
69 int v = q.elem[q.i].node;
70 bool hi = q.elem[q.i].hi;
71 q.i++;
72
73 if (v == b) {
74 send(v, hi);
75 } else if (m[v].isff) {
76 if (!hi)
77 send(v, m[v].ison = !m[v].ison);
78 } else {
79 bool allhi = true;
80 for (int j = 0; j < m[v].nin; j++)
81 allhi = allhi && m[v].reg[m[v].in[j]];
82 send(v, !allhi);
83 }
84 }
85}
86
87bool isclean(void) {
88 for (int i = 0; i < n; i++) {
89 if (m[i].isff && m[i].ison)
90 return false;
91 else
92 for (int j = 0; j < m[i].nin; j++)
93 if (m[i].reg[j])
94 return false;
95 }
96 return true;
97}
98
99int64_t period(int node) {
100 int64_t npush = 0;
101 do {
102 sig(node, false);
103 npush++;
104 } while (!isclean());
105 return npush;
106}
107
108int main() {
109 for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
110 if (ischar(*buf)) b = n;
111 m[n].isff = *buf == '%';
112 if (!ischar(*buf)) buf++;
113 for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
114 buf += 4;
115 for (int i = 0; *buf != '\n'; i++) {
116 while (!ischar(*buf)) buf++;
117 for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
118 }
119 }
120
121 for (int i = 0; i < n; i++) {
122 for (int j = 0; m[i].outc[j][0]; j++) {
123 int k = findm(m[i].outc[j]);
124 m[i].out[m[i].nout++] = k;
125 m[k].in[m[k].nin++] = i;
126 if (k == n) {
127 for (int k = 0; m[i].outc[j][k]; k++)
128 m[n].name[k] = m[i].outc[j][k];
129 n++;
130 }
131 }
132 }
133
134 for (int i = 0; i < n; i++)
135 if (!strcmp(m[i].name, "rx"))
136 r = i;
137
138 printf("%" PRId64 "\n", period(19));
139 printf("%" PRId64 "\n", period(33));
140 printf("%" PRId64 "\n", period(39));
141 printf("%" PRId64 "\n", period(57));
142 return 0;
143}
diff --git a/2023/20/graph.c b/2023/20/graph.c
new file mode 100644
index 0000000..bef0496
--- /dev/null
+++ b/2023/20/graph.c
@@ -0,0 +1,77 @@
1/* Picture generated with https://csacademy.com/app/graph_editor/ */
2
3#include <inttypes.h>
4#include <stdbool.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8
9#define N 100
10#define ischar(c) (c >= 'a' && c <= 'z')
11
12typedef struct {
13 int nin, nout, in[N], out[N];
14 char name[20], outc[N][20];
15 bool isff, ison, reg[N];
16} node_t;
17
18char *buf, line[N][N];
19bool rx;
20int b, r, n;
21int64_t npush;
22node_t m[N];
23
24int findm(char *name) {
25 for (int k = 0; k < n; k++)
26 if (!strcmp(m[k].name, name))
27 return k;
28 return n;
29}
30
31int main() {
32 for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
33 if (ischar(*buf)) b = n;
34 m[n].isff = *buf == '%';
35 if (!ischar(*buf)) buf++;
36 for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
37 buf += 4;
38 for (int i = 0; *buf != '\n'; i++) {
39 while (!ischar(*buf)) buf++;
40 for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
41 }
42 }
43
44 for (int i = 0; i < n; i++) {
45 for (int j = 0; m[i].outc[j][0]; j++) {
46 int k = findm(m[i].outc[j]);
47 m[i].out[m[i].nout++] = k;
48 m[k].in[m[k].nin++] = i;
49 if (k == n) {
50 for (int k = 0; m[i].outc[j][k]; k++)
51 m[n].name[k] = m[i].outc[j][k];
52 n++;
53 }
54 }
55 }
56
57 for (int i = 0; i < n; i++)
58 if (!strcmp(m[i].name, "rx"))
59 r = i;
60
61/* Print adjacency list
62 printf("%d\n", n);
63 for (int i = 0; i < n; i++) {
64 printf("%d", m[i].nout);
65 for (int j = 0; j < m[i].nout; j++)
66 printf(" %d", m[i].out[j]);
67 printf("\n");
68 }
69 printf("broadcaster = %d, r = %d\n", b, r);
70*/
71
72 for (int i = 0; i < n; i++)
73 for (int j = 0; j < m[i].nout; j++)
74 printf("%d %d\n", i, m[i].out[j]);
75
76 return 0;
77}
diff --git a/2023/20/graph.png b/2023/20/graph.png
new file mode 100644
index 0000000..93bca44
--- /dev/null
+++ b/2023/20/graph.png
Binary files differ

Generated with cgit - Back to sebastiano.tronto.net