commit 69fdaf5b54c33f5597f235aa3f71ee5b810e7eae
parent e76280252fb8a5648f3ce2f85fac714a6d574f75
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 20 Dec 2023 16:32:41 +0100
Added solution for 20
Diffstat:
| A | 2023/20/20a.c | | | 101 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/20/20b.c | | | 143 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/20/graph.c | | | 77 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/20/graph.png | | | 0 | |
| A | 2023/20/input | | | 58 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 379 insertions(+), 0 deletions(-)
diff --git a/2023/20/20a.c b/2023/20/20a.c
@@ -0,0 +1,101 @@
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define N 100
+#define ischar(c) (c >= 'a' && c <= 'z')
+
+typedef struct {
+ int nin, nout, in[N], out[N];
+ char name[20], outc[N][20];
+ bool isff, ison, reg[N];
+} node_t;
+
+typedef struct {
+ int i, n, node[1000];
+ bool hi[1000];
+} queue_t;
+
+char *buf, line[N][N];
+int b, n;
+int64_t hitot, lowtot;
+node_t m[N];
+
+void add(queue_t *q, int v, bool hi) {
+ q->node[q->n] = v;
+ q->hi[q->n] = hi;
+ q->n++;
+}
+
+void send(queue_t *q, int v, bool hi) {
+ for (int j = 0; j < m[v].nout; j++) {
+ add(q, m[v].out[j], hi);
+ m[m[v].out[j]].reg[v] = hi;
+ if (hi) hitot++; else lowtot++;
+ }
+}
+
+void pushbutton(void) {
+ queue_t q = {0};
+
+ add(&q, b, false);
+ lowtot++;
+ while (q.i < q.n) {
+ int v = q.node[q.i];
+ bool hi = q.hi[q.i];
+ q.i++;
+
+ if (v == b) {
+ send(&q, v, hi);
+ } else if (m[v].isff) {
+ if (!hi)
+ send(&q, v, m[v].ison = !m[v].ison);
+ } else {
+ bool allhi = true;
+ for (int j = 0; j < m[v].nin; j++)
+ allhi = allhi && m[v].reg[m[v].in[j]];
+ send(&q, v, !allhi);
+ }
+ }
+}
+
+int main() {
+ for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
+ if (ischar(*buf)) b = n;
+ m[n].isff = *buf == '%';
+ if (!ischar(*buf)) buf++;
+ for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
+ buf += 4;
+ for (int i = 0; *buf != '\n'; i++) {
+ while (!ischar(*buf)) buf++;
+ for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
+ }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; m[i].outc[j][0]; j++) {
+ bool found = false;
+ for (int k = 0; k < n; k++) {
+ if (!strcmp(m[k].name, m[i].outc[j])) {
+ m[i].out[m[i].nout++] = k;
+ m[k].in[m[k].nin++] = i;
+ found = true;
+ }
+ }
+ if (!found) {
+ m[i].out[m[i].nout++] = n;
+ m[n].in[m[n].nin++] = i;
+ n++;
+ }
+ }
+ }
+
+ for (int i = 0; i < 1000; i++)
+ pushbutton();
+
+ printf("%" PRId64 " (%" PRId64 " low, %" PRId64 " hi)\n",
+ hitot * lowtot, lowtot, hitot);
+ return 0;
+}
diff --git a/2023/20/20b.c b/2023/20/20b.c
@@ -0,0 +1,143 @@
+/*
+This one is a bit weird. This program works only for my specific input
+(included in this folder). Similarly to number 8, this program outputs
+4 numbers and you have to take the lcm of them.
+
+I solved it this way:
+1. First, using a modified version of the code for part one (graph.c),
+ I printed the graph as a list of adjacency lists.
+2. I then went to https://csacademy.com/app/graph_editor and observed
+ the graph. I noticed that after the button is pressed, the signal
+ is sent to 4 independent parts of the graph. Each of these parts has
+ only one entry point and one exit point. The entry points were not
+ flip-flop nodes.
+3. Finally, I implemented the code to check how long it takes for the
+ graph to go back to the initial state, and I simulated sending a
+ signal to each of the 4 parts independently.
+*/
+
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define N 100
+#define ischar(c) (c >= 'a' && c <= 'z')
+
+typedef struct {
+ int nin, nout, in[N], out[N];
+ char name[20], outc[N][20];
+ bool isff, ison, reg[N];
+} node_t;
+
+typedef struct {
+ int i, n;
+ struct {int node; bool hi;} elem[500];
+} queue_t;
+
+char *buf, line[N][N];
+bool rx;
+int b, r, n;
+node_t m[N];
+queue_t q;
+
+void add(int v, bool hi) {
+ q.elem[q.n].node = v;
+ q.elem[q.n].hi = hi;
+ q.n++;
+}
+
+void send(int v, bool hi) {
+ for (int j = 0; j < m[v].nout; j++) {
+ add(m[v].out[j], hi);
+ m[m[v].out[j]].reg[v] = hi;
+ }
+}
+
+int findm(char *name) {
+ for (int k = 0; k < n; k++)
+ if (!strcmp(m[k].name, name))
+ return k;
+ return n;
+}
+
+void sig(int node, bool high) {
+ q.n = q.i = 0;
+ add(node, high);
+ while (q.i < q.n) {
+ int v = q.elem[q.i].node;
+ bool hi = q.elem[q.i].hi;
+ q.i++;
+
+ if (v == b) {
+ send(v, hi);
+ } else if (m[v].isff) {
+ if (!hi)
+ send(v, m[v].ison = !m[v].ison);
+ } else {
+ bool allhi = true;
+ for (int j = 0; j < m[v].nin; j++)
+ allhi = allhi && m[v].reg[m[v].in[j]];
+ send(v, !allhi);
+ }
+ }
+}
+
+bool isclean(void) {
+ for (int i = 0; i < n; i++) {
+ if (m[i].isff && m[i].ison)
+ return false;
+ else
+ for (int j = 0; j < m[i].nin; j++)
+ if (m[i].reg[j])
+ return false;
+ }
+ return true;
+}
+
+int64_t period(int node) {
+ int64_t npush = 0;
+ do {
+ sig(node, false);
+ npush++;
+ } while (!isclean());
+ return npush;
+}
+
+int main() {
+ for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
+ if (ischar(*buf)) b = n;
+ m[n].isff = *buf == '%';
+ if (!ischar(*buf)) buf++;
+ for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
+ buf += 4;
+ for (int i = 0; *buf != '\n'; i++) {
+ while (!ischar(*buf)) buf++;
+ for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
+ }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; m[i].outc[j][0]; j++) {
+ int k = findm(m[i].outc[j]);
+ m[i].out[m[i].nout++] = k;
+ m[k].in[m[k].nin++] = i;
+ if (k == n) {
+ for (int k = 0; m[i].outc[j][k]; k++)
+ m[n].name[k] = m[i].outc[j][k];
+ n++;
+ }
+ }
+ }
+
+ for (int i = 0; i < n; i++)
+ if (!strcmp(m[i].name, "rx"))
+ r = i;
+
+ printf("%" PRId64 "\n", period(19));
+ printf("%" PRId64 "\n", period(33));
+ printf("%" PRId64 "\n", period(39));
+ printf("%" PRId64 "\n", period(57));
+ return 0;
+}
diff --git a/2023/20/graph.c b/2023/20/graph.c
@@ -0,0 +1,77 @@
+/* Picture generated with https://csacademy.com/app/graph_editor/ */
+
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define N 100
+#define ischar(c) (c >= 'a' && c <= 'z')
+
+typedef struct {
+ int nin, nout, in[N], out[N];
+ char name[20], outc[N][20];
+ bool isff, ison, reg[N];
+} node_t;
+
+char *buf, line[N][N];
+bool rx;
+int b, r, n;
+int64_t npush;
+node_t m[N];
+
+int findm(char *name) {
+ for (int k = 0; k < n; k++)
+ if (!strcmp(m[k].name, name))
+ return k;
+ return n;
+}
+
+int main() {
+ for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
+ if (ischar(*buf)) b = n;
+ m[n].isff = *buf == '%';
+ if (!ischar(*buf)) buf++;
+ for (int i = 0; ischar(*buf); m[n].name[i++] = *(buf++)) ;
+ buf += 4;
+ for (int i = 0; *buf != '\n'; i++) {
+ while (!ischar(*buf)) buf++;
+ for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
+ }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; m[i].outc[j][0]; j++) {
+ int k = findm(m[i].outc[j]);
+ m[i].out[m[i].nout++] = k;
+ m[k].in[m[k].nin++] = i;
+ if (k == n) {
+ for (int k = 0; m[i].outc[j][k]; k++)
+ m[n].name[k] = m[i].outc[j][k];
+ n++;
+ }
+ }
+ }
+
+ for (int i = 0; i < n; i++)
+ if (!strcmp(m[i].name, "rx"))
+ r = i;
+
+/* Print adjacency list
+ printf("%d\n", n);
+ for (int i = 0; i < n; i++) {
+ printf("%d", m[i].nout);
+ for (int j = 0; j < m[i].nout; j++)
+ printf(" %d", m[i].out[j]);
+ printf("\n");
+ }
+ printf("broadcaster = %d, r = %d\n", b, r);
+*/
+
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < m[i].nout; j++)
+ printf("%d %d\n", i, m[i].out[j]);
+
+ return 0;
+}
diff --git a/2023/20/graph.png b/2023/20/graph.png
Binary files differ.
diff --git a/2023/20/input b/2023/20/input
@@ -0,0 +1,58 @@
+%vn -> ts, lq
+&ks -> dt
+%zt -> vl
+%xg -> ts, pb
+&xd -> qz, bc, zt, vk, hq, qx, gc
+&pm -> dt
+%gb -> vj, xd
+%qx -> gb
+%rl -> qn
+%lq -> gk
+%qm -> bf
+%zn -> vh, pf
+%lz -> kk, vr
+%bf -> rr
+%gx -> vr
+%zr -> vx, pf
+%lt -> ng, vr
+%hd -> mg, xd
+%mg -> xd
+%tx -> jg, vr
+%gk -> kx, ts
+&vr -> tr, vf, tx, ks, kk, jg
+broadcaster -> qz, tx, jr, hk
+%bc -> qx
+%xz -> lt, vr
+%jg -> sb
+%qn -> zr, pf
+%gc -> xv
+%vx -> lj, pf
+%vf -> cn
+&dt -> rx
+%sb -> lz, vr
+%kx -> xg
+%hk -> pf, tv
+%cb -> pf
+&dl -> dt
+%vl -> xd, bc
+%fl -> pp, pf
+%ng -> vr, gx
+%jr -> ts, qm
+%cd -> vn, ts
+%mt -> ts
+%rr -> ts, cd
+%tr -> xz
+%hq -> zt
+%xv -> hq, xd
+%vj -> xd, hd
+%pp -> zn
+%vh -> pf, cb
+%cn -> vr, tr
+%kk -> vf
+&pf -> pp, tv, rl, pm, hk
+&ts -> dl, qm, kx, lq, bf, jr
+%tv -> rl
+&vk -> dt
+%pb -> ts, mt
+%lj -> pf, fl
+%qz -> xd, gc
