commit a1f776c9c5390b8409e7f44cb2a33d728d1200f3
parent 9c4f72ce260acc6398632cd9e396a54b0e494151
Author: Louis Burda <quent.burda@gmail.com>
Date: Tue, 4 Apr 2023 12:24:38 -0400
Add day 23
Diffstat:
| A | 23/info.mk | | | 4 | ++++ |
| A | 23/input | | | 2 | ++ |
| A | 23/main.c | | | 242 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 23/part1 | | | 37 | +++++++++++++++++++++++++++++++++++++ |
| A | 23/part2 | | | 22 | ++++++++++++++++++++++ |
5 files changed, 307 insertions(+), 0 deletions(-)
diff --git a/23/info.mk b/23/info.mk
@@ -0,0 +1,4 @@
+23_SRC = 23/main.c common/main.c common/iccmp.c common/aoc.c common/util.c
+23_SRC += lib/liballoc/build/liballoc.a lib/libmaxint/build/libmaxint.a
+23_SRC += lib/libhmap/build/libhmap.a lib/liblist/build/liblist.a
+23_HDR = common/aoc.h common/iccmp.h common/util.h
diff --git a/23/input b/23/input
@@ -0,0 +1,2 @@
+3,62,1001,62,11,10,109,2241,105,1,0,2066,1569,571,1239,2200,1342,2169,899,1173,2035,1540,1204,1637,1806,641,977,1272,1773,1144,1008,1699,2107,1107,1909,1872,833,802,1410,932,1072,1307,1938,2000,734,1837,2138,1039,1606,701,1373,608,866,1443,1478,771,1509,672,1969,1668,1738,0,0,0,0,0,0,0,0,0,0,0,0,3,64,1008,64,-1,62,1006,62,88,1006,61,170,1105,1,73,3,65,20102,1,64,1,21002,66,1,2,21102,105,1,0,1106,0,436,1201,1,-1,64,1007,64,0,62,1005,62,73,7,64,67,62,1006,62,73,1002,64,2,132,1,132,68,132,1002,0,1,62,1001,132,1,140,8,0,65,63,2,63,62,62,1005,62,73,1002,64,2,161,1,161,68,161,1102,1,1,0,1001,161,1,169,101,0,65,0,1102,1,1,61,1102,1,0,63,7,63,67,62,1006,62,203,1002,63,2,194,1,68,194,194,1006,0,73,1001,63,1,63,1106,0,178,21102,210,1,0,105,1,69,1202,1,1,70,1101,0,0,63,7,63,71,62,1006,62,250,1002,63,2,234,1,72,234,234,4,0,101,1,234,240,4,0,4,70,1001,63,1,63,1106,0,218,1105,1,73,109,4,21102,1,0,-3,21102,0,1,-2,20207,-2,67,-1,1206,-1,293,1202,-2,2,283,101,1,283,283,1,68,283,283,22001,0,-3,-3,21201,-2,1,-2,1106,0,263,21202,-3,1,-3,109,-4,2105,1,0,109,4,21101,1,0,-3,21101,0,0,-2,20207,-2,67,-1,1206,-1,342,1202,-2,2,332,101,1,332,332,1,68,332,332,22002,0,-3,-3,21201,-2,1,-2,1105,1,312,21202,-3,1,-3,109,-4,2105,1,0,109,1,101,1,68,359,20101,0,0,1,101,3,68,367,20102,1,0,2,21101,0,376,0,1105,1,436,22101,0,1,0,109,-1,2106,0,0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,109,8,21202,-6,10,-5,22207,-7,-5,-5,1205,-5,521,21101,0,0,-4,21101,0,0,-3,21101,0,51,-2,21201,-2,-1,-2,1201,-2,385,471,20102,1,0,-1,21202,-3,2,-3,22207,-7,-1,-5,1205,-5,496,21201,-3,1,-3,22102,-1,-1,-5,22201,-7,-5,-7,22207,-3,-6,-5,1205,-5,515,22102,-1,-6,-5,22201,-3,-5,-3,22201,-1,-4,-4,1205,-2,461,1106,0,547,21102,1,-1,-4,21202,-6,-1,-6,21207,-7,0,-5,1205,-5,547,22201,-7,-6,-7,21201,-4,1,-4,1105,1,529,21201,-4,0,-7,109,-8,2106,0,0,109,1,101,1,68,563,21002,0,1,0,109,-1,2106,0,0,1102,6581,1,66,1101,0,4,67,1101,598,0,68,1101,0,253,69,1101,0,1,71,1101,606,0,72,1106,0,73,0,0,0,0,0,0,0,0,27,85159,1102,6151,1,66,1101,0,2,67,1102,635,1,68,1101,302,0,69,1102,1,1,71,1101,0,639,72,1105,1,73,0,0,0,0,1,292724,1102,84653,1,66,1101,0,1,67,1101,0,668,68,1101,0,556,69,1101,0,1,71,1102,1,670,72,1106,0,73,1,11,34,14669,1102,96893,1,66,1101,0,1,67,1102,699,1,68,1102,556,1,69,1102,0,1,71,1102,701,1,72,1106,0,73,1,1705,1101,93557,0,66,1101,2,0,67,1101,728,0,68,1102,302,1,69,1101,1,0,71,1102,1,732,72,1106,0,73,0,0,0,0,41,155138,1101,102061,0,66,1101,4,0,67,1102,761,1,68,1102,1,302,69,1102,1,1,71,1102,1,769,72,1105,1,73,0,0,0,0,0,0,0,0,4,122394,1101,0,93497,66,1102,1,1,67,1102,1,798,68,1101,556,0,69,1101,1,0,71,1102,800,1,72,1106,0,73,1,-18,49,41897,1101,0,80071,66,1102,1,1,67,1101,0,829,68,1101,0,556,69,1102,1,1,71,1102,1,831,72,1105,1,73,1,-1474987,2,13162,1101,71473,0,66,1101,2,0,67,1102,860,1,68,1101,0,351,69,1102,1,1,71,1102,1,864,72,1105,1,73,0,0,0,0,255,32771,1101,77569,0,66,1101,0,2,67,1102,1,893,68,1102,1,302,69,1101,1,0,71,1102,1,897,72,1106,0,73,0,0,0,0,39,52396,1102,24799,1,66,1102,1,1,67,1101,926,0,68,1101,0,556,69,1101,2,0,71,1102,1,928,72,1105,1,73,1,211,39,13099,11,42299,1102,55399,1,66,1102,1,1,67,1101,959,0,68,1102,1,556,69,1101,8,0,71,1102,961,1,72,1105,1,73,1,2,41,77569,39,26198,27,170318,17,79714,3,78889,34,44007,4,61197,4,81596,1101,0,22993,66,1101,1,0,67,1102,1,1004,68,1102,1,556,69,1102,1,1,71,1101,0,1006,72,1105,1,73,1,2485433,2,19743,1101,0,32687,66,1101,0,1,67,1101,0,1035,68,1102,556,1,69,1102,1,1,71,1102,1037,1,72,1106,0,73,1,28661,16,15501,1102,1,44657,66,1101,1,0,67,1102,1,1066,68,1102,556,1,69,1102,1,2,71,1102,1,1068,72,1106,0,73,1,10,33,102061,4,40798,1102,53777,1,66,1101,3,0,67,1101,1099,0,68,1101,0,302,69,1101,0,1,71,1101,0,1105,72,1106,0,73,0,0,0,0,0,0,22,212991,1101,70997,0,66,1101,4,0,67,1102,1,1134,68,1102,1,253,69,1101,0,1,71,1101,0,1142,72,1106,0,73,0,0,0,0,0,0,0,0,38,93557,1102,93761,1,66,1101,1,0,67,1102,1171,1,68,1102,556,1,69,1102,1,0,71,1102,1,1173,72,1106,0,73,1,1625,1101,0,96973,66,1102,1,1,67,1102,1,1200,68,1102,556,1,69,1102,1,1,71,1102,1202,1,72,1105,1,73,1,13,24,102071,1101,0,42299,66,1102,1,3,67,1101,0,1231,68,1101,302,0,69,1102,1,1,71,1101,0,1237,72,1105,1,73,0,0,0,0,0,0,42,82763,1102,78889,1,66,1102,2,1,67,1102,1,1266,68,1102,1,302,69,1102,1,1,71,1102,1270,1,72,1105,1,73,0,0,0,0,34,29338,1102,5167,1,66,1102,3,1,67,1101,0,1299,68,1101,0,302,69,1101,0,1,71,1102,1,1305,72,1106,0,73,0,0,0,0,0,0,22,70997,1101,12697,0,66,1101,0,1,67,1101,1334,0,68,1101,0,556,69,1101,3,0,71,1101,0,1336,72,1105,1,73,1,5,33,306183,33,408244,4,20399,1102,1,99251,66,1101,0,1,67,1102,1369,1,68,1102,556,1,69,1102,1,1,71,1101,0,1371,72,1106,0,73,1,181,24,204142,1102,1,13099,66,1102,1,4,67,1102,1400,1,68,1101,302,0,69,1102,1,1,71,1102,1408,1,72,1106,0,73,0,0,0,0,0,0,0,0,1,73181,1102,1,85159,66,1102,1,2,67,1102,1437,1,68,1102,1,302,69,1101,1,0,71,1101,0,1441,72,1106,0,73,0,0,0,0,17,39857,1102,1,82763,66,1102,1,3,67,1101,1470,0,68,1102,1,302,69,1102,1,1,71,1101,0,1476,72,1106,0,73,0,0,0,0,0,0,1,146362,1102,44179,1,66,1102,1,1,67,1101,1505,0,68,1102,556,1,69,1102,1,1,71,1102,1507,1,72,1105,1,73,1,278,29,161331,1102,1,19457,66,1102,1,1,67,1101,1536,0,68,1102,1,556,69,1102,1,1,71,1102,1,1538,72,1105,1,73,1,17,39,39297,1101,0,60251,66,1101,0,1,67,1102,1567,1,68,1102,1,556,69,1102,1,0,71,1101,1569,0,72,1106,0,73,1,1621,1101,73181,0,66,1102,4,1,67,1101,0,1596,68,1101,0,253,69,1102,1,1,71,1102,1,1604,72,1105,1,73,0,0,0,0,0,0,0,0,25,71473,1101,0,99277,66,1102,1,1,67,1102,1633,1,68,1102,556,1,69,1101,1,0,71,1102,1635,1,72,1106,0,73,1,-661,24,408284,1102,1,2957,66,1101,1,0,67,1101,1664,0,68,1101,556,0,69,1101,1,0,71,1101,1666,0,72,1106,0,73,1,16,38,187114,1102,77687,1,66,1101,0,1,67,1101,1695,0,68,1102,1,556,69,1101,1,0,71,1101,1697,0,72,1105,1,73,1,160,4,101995,1102,79757,1,66,1102,1,1,67,1102,1,1726,68,1101,0,556,69,1101,5,0,71,1102,1728,1,72,1105,1,73,1,1,49,125691,29,53777,24,306213,16,5167,11,84598,1102,41897,1,66,1102,3,1,67,1102,1,1765,68,1102,302,1,69,1102,1,1,71,1102,1,1771,72,1105,1,73,0,0,0,0,0,0,22,141994,1102,1,39857,66,1102,2,1,67,1102,1800,1,68,1102,302,1,69,1102,1,1,71,1101,0,1804,72,1105,1,73,0,0,0,0,3,157778,1101,87671,0,66,1101,1,0,67,1102,1833,1,68,1102,556,1,69,1101,1,0,71,1101,1835,0,72,1105,1,73,1,64937,49,83794,1102,14669,1,66,1102,1,3,67,1102,1864,1,68,1101,0,302,69,1101,1,0,71,1101,0,1870,72,1105,1,73,0,0,0,0,0,0,40,6151,1101,0,102071,66,1102,4,1,67,1101,1899,0,68,1101,302,0,69,1102,1,1,71,1101,1907,0,72,1106,0,73,0,0,0,0,0,0,0,0,22,283988,1101,93169,0,66,1101,1,0,67,1102,1936,1,68,1101,0,556,69,1101,0,0,71,1101,1938,0,72,1105,1,73,1,1087,1102,1,92173,66,1101,0,1,67,1102,1,1965,68,1102,1,556,69,1101,1,0,71,1101,0,1967,72,1105,1,73,1,7751410,2,26324,1101,80897,0,66,1101,1,0,67,1102,1996,1,68,1101,0,556,69,1101,1,0,71,1102,1,1998,72,1106,0,73,1,-1275519,2,6581,1101,0,102481,66,1101,3,0,67,1101,2027,0,68,1102,302,1,69,1101,0,1,71,1101,0,2033,72,1106,0,73,0,0,0,0,0,0,1,219543,1102,1,2687,66,1102,1,1,67,1101,2062,0,68,1102,1,556,69,1101,1,0,71,1102,1,2064,72,1106,0,73,1,5807,29,107554,1101,0,32771,66,1101,0,1,67,1102,2093,1,68,1101,0,556,69,1102,6,1,71,1101,0,2095,72,1105,1,73,1,22083,40,12302,42,165526,42,248289,32,102481,32,204962,32,307443,1102,2791,1,66,1101,0,1,67,1101,0,2134,68,1101,0,556,69,1101,1,0,71,1102,2136,1,72,1106,0,73,1,-204,11,126897,1101,5669,0,66,1102,1,1,67,1102,2165,1,68,1101,556,0,69,1101,1,0,71,1101,2167,0,72,1106,0,73,1,125,33,204122,1101,94693,0,66,1102,1,1,67,1101,2196,0,68,1101,556,0,69,1101,1,0,71,1101,2198,0,72,1105,1,73,1,244,16,10334,1101,0,20399,66,1101,0,6,67,1102,1,2227,68,1101,0,302,69,1101,1,0,71,1102,1,2239,72,1106,0,73,0,0,0,0,0,0,0,0,0,0,0,0,25,142946
+
diff --git a/23/main.c b/23/main.c
@@ -0,0 +1,242 @@
+#include "aoc.h"
+#include "iccmp.h"
+#include "list.h"
+#include "maxint.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+struct packet {
+ struct maxint x, y;
+ size_t src_ip, dst_ip;
+
+ struct list_link link;
+};
+
+static struct packet nat_packet;
+static bool nat_avail = false;
+
+void
+feed_input(struct icc *icc, mi_ul imm)
+{
+ while (icc->state != ICC_HALT) {
+ if (icc->state == ICC_INPUT) {
+ mi_setv(&icc->in, imm, MI_POS);
+ icc_step_inst(icc);
+ break;
+ }
+ icc_step_inst(icc);
+ }
+}
+
+void
+free_packet(struct packet *packet)
+{
+ mi_deinit(&packet->x);
+ mi_deinit(&packet->y);
+ free(packet);
+}
+
+bool
+recv_packet(struct list *queues, struct maxint *val, int state, size_t ip)
+{
+ static struct packet *packet;
+ struct list_link *link;
+ char buf[64];
+
+ aoc_debug("INPUT %i\n", ip);
+ if (list_empty(&queues[ip])) {
+ mi_setv(val, 1, MI_NEG);
+ return false;
+ } else {
+ switch(state) {
+ case 0:
+ link = list_front(&queues[ip]);
+ packet = LIST_UPCAST(link, struct packet, link);
+ aoc_debug("%i <- %i (", packet->src_ip, packet->dst_ip);
+ mi_dec(&packet->x, buf, sizeof(buf), 0);
+ aoc_debug("%s, ", buf);
+ mi_dec(&packet->y, buf, sizeof(buf), 0);
+ aoc_debug("%s)\n", buf);
+ mi_set(val, &packet->x);
+ break;
+ case 1:
+ mi_set(val, &packet->y);
+ list_link_pop(&packet->link);
+ free_packet(packet);
+ break;
+ }
+ return true;
+ }
+}
+
+void
+send_packet(struct list *queues, struct maxint *val, int state, size_t ip)
+{
+ static struct packet *packet;
+ size_t dst;
+ char buf[64];
+
+ aoc_debug("OUTPUT %i\n", ip);
+ switch (state) {
+ case 0:
+ dst = (size_t) mi_cast_ul(val);
+ if (dst == 255) {
+ packet = &nat_packet;
+ } else {
+ packet = malloc(sizeof(struct packet));
+ }
+ mi_init(&packet->x);
+ mi_init(&packet->y);
+ packet->src_ip = ip;
+ packet->dst_ip = dst;
+ packet->link = LIST_LINK_INIT;
+ break;
+ case 1:
+ mi_set(&packet->x, val);
+ break;
+ case 2:
+ mi_set(&packet->y, val);
+ if (packet->dst_ip != 255) {
+ assert(packet->dst_ip < 50);
+ list_insert_back(&queues[packet->dst_ip], &packet->link);
+ } else {
+ nat_avail = true;
+ }
+ aoc_debug("%i <- %i (", packet->dst_ip, packet->src_ip);
+ mi_dec(&packet->x, buf, sizeof(buf), 0);
+ aoc_debug("%s, ", buf);
+ mi_dec(&packet->y, buf, sizeof(buf), 0);
+ aoc_debug("%s)\n", buf);
+ break;
+ }
+}
+
+bool
+nic_tick(struct icc *icc, struct list *queues, size_t ip)
+{
+ int out_state, in_state;
+ bool idle, done;
+
+ done = false;
+ idle = true;
+ in_state = 0;
+ out_state = 0;
+ while (!done && icc->state != ICC_HALT) {
+ switch (icc->state) {
+ case ICC_INPUT:
+ idle &= !recv_packet(queues, &icc->in, in_state, ip);
+ in_state = (in_state + 1) % 2;
+ if (!in_state) done = true;
+ break;
+ case ICC_OUTPUT:
+ send_packet(queues, &icc->out, out_state, ip);
+ out_state = (out_state + 1) % 3;
+ idle = false;
+ break;
+ defualt:
+ assert(icc->state == ICC_RUN);
+ }
+ icc_step_inst(icc);
+ }
+ assert(in_state == 0 && out_state == 0);
+
+ return idle;
+}
+
+void
+part1(void)
+{
+ struct list queues[256];
+ struct icc icc[50];
+ struct list_link *link;
+ struct packet *packet;
+ char buf[64];
+ size_t i;
+
+ for (i = 0; i < 50; i++) {
+ icc_init(&icc[i]);
+ icc_parse_inst(&icc[i], aoc.input, aoc.input_size);
+ feed_input(&icc[i], (mi_ul) i);
+ }
+
+ for (i = 0; i < 256; i++) {
+ list_init(&queues[i]);
+ }
+
+ while (!nat_avail) {
+ aoc_debug("-- TICK --\n");
+ for (i = 0; i < 50; i++)
+ nic_tick(&icc[i], queues, i);
+ }
+
+ mi_dec(&nat_packet.y, buf, sizeof(buf), 0);
+ aoc.answer = aprintf("%s", buf);
+ aoc.solution = "20225";
+
+ for (i = 0; i < 256; i++) {
+ for (LIST_ITER(&queues[i], link)) {
+ packet = LIST_UPCAST(link, struct packet, link);
+ free_packet(packet);
+ }
+ list_clear(&queues[i]);
+ }
+
+ for (i = 0; i < 50; i++)
+ icc_deinit(&icc[i]);
+}
+
+void
+part2(void)
+{
+ struct list queues[256];
+ struct icc icc[50];
+ struct list_link *link;
+ struct packet *packet;
+ size_t answer;
+ size_t last;
+ bool idle;
+ size_t i;
+
+ for (i = 0; i < 50; i++) {
+ list_init(&queues[i]);
+ icc_init(&icc[i]);
+ icc_parse_inst(&icc[i], aoc.input, aoc.input_size);
+ feed_input(&icc[i], (mi_ul) i);
+ }
+
+ while (1) {
+ aoc_debug("-- TICK --\n");
+
+ idle = true;
+ for (i = 0; i < 50; i++)
+ idle &= nic_tick(&icc[i], queues, i);
+
+ if (idle) {
+ assert(nat_avail);
+ packet = malloc(sizeof(struct packet));
+ memcpy(packet, &nat_packet, sizeof(struct packet));
+ list_insert_back(&queues[0], &packet->link);
+
+ if (mi_cast_ul(&packet->y) == last) {
+ answer = last;
+ break;
+ }
+ last = mi_cast_ul(&packet->y);
+
+ }
+ }
+
+ aoc.answer = aprintf("%lu", answer);
+
+ for (i = 0; i < 50; i++) {
+ for (LIST_ITER(&queues[i], link)) {
+ packet = LIST_UPCAST(link, struct packet, link);
+ free_packet(packet);
+ }
+ list_clear(&queues[i]);
+ icc_deinit(&icc[i]);
+ }
+}
diff --git a/23/part1 b/23/part1
@@ -0,0 +1,37 @@
+--- Day 23: Category Six ---
+
+The droids have finished repairing as much of the ship as they can. Their report indicates that
+this was a Category 6 disaster - not because it was that bad, but because it destroyed the stockpile
+of Category 6 network cables as well as most of the ship's network infrastructure.
+
+You'll need to rebuild the network from scratch.
+
+The computers on the network are standard Intcode computers that communicate by sending packets to
+each other. There are 50 of them in total, each running a copy of the same Network Interface
+Controller (NIC) software (your puzzle input). The computers have network addresses 0 through 49;
+when each computer boots up, it will request its network address via a single input instruction. Be
+sure to give each computer a unique network address.
+
+Once a computer has received its network address, it will begin doing work and communicating over
+the network by sending and receiving packets. All packets contain two values named X and Y. Packets
+sent to a computer are queued by the recipient and read in the order they are received.
+
+To send a packet to another computer, the NIC will use three output instructions that provide the
+destination address of the packet followed by its X and Y values. For example, three output
+instructions that provide the values 10, 20, 30 would send a packet with X=20 and Y=30 to the
+computer with address 10.
+
+To receive a packet from another computer, the NIC will use an input instruction. If the incoming
+packet queue is empty, provide -1. Otherwise, provide the X value of the next packet; the computer
+will then use a second input instruction to receive the Y value for the same packet. Once both
+values of the packet are read in this way, the packet is removed from the queue.
+
+Note that these input and output instructions never block. Specifically, output instructions do not
+wait for the sent packet to be received - the computer might send multiple packets before receiving
+any. Similarly, input instructions do not wait for a packet to arrive - if no packet is waiting,
+input instructions should receive -1.
+
+Boot up all 50 computers and attach them to your network. What is the Y value of the first packet
+sent to address 255?
+
+
diff --git a/23/part2 b/23/part2
@@ -0,0 +1,22 @@
+--- Part Two ---
+
+Packets sent to address 255 are handled by a device called a NAT (Not Always Transmitting). The NAT
+is responsible for managing power consumption of the network by blocking certain packets and
+watching for idle periods in the computers.
+
+If a packet would be sent to address 255, the NAT receives it instead. The NAT remembers only the
+last packet it receives; that is, the data in each packet it receives overwrites the NAT's packet
+memory with the new packet's X and Y values.
+
+The NAT also monitors all computers on the network. If all computers have empty incoming packet
+queues and are continuously trying to receive packets without sending packets, the network is
+considered idle.
+
+Once the network is idle, the NAT sends only the last packet it received to address 0; this will
+cause the computers on the network to resume activity. In this way, the NAT can throttle power
+consumption of the network when the ship needs power in other areas.
+
+Monitor packets released to the computer at address 0 by the NAT. What is the first Y value
+delivered by the NAT to the computer at address 0 twice in a row?
+
+
