commit 20c9d752bab453ade281fc814950636577093428
parent 744cb4c6f5e12f84d5a77d8eee69a60c81d53fee
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 2 Apr 2023 10:19:44 -0400
Add day 19
Diffstat:
| A | 19/info.mk | | | 4 | ++++ |
| A | 19/input | | | 2 | ++ |
| A | 19/main.c | | | 155 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 19/part1 | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | 19/part2 | | | 58 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | common/iccmp.c | | | 29 | ++++++++++++++++++++++++----- |
6 files changed, 286 insertions(+), 5 deletions(-)
diff --git a/19/info.mk b/19/info.mk
@@ -0,0 +1,4 @@
+19_SRC = 19/main.c common/main.c common/iccmp.c common/aoc.c common/util.c
+19_SRC += lib/liballoc/build/liballoc.a lib/libmaxint/build/libmaxint.a
+19_SRC += lib/libhmap/build/libhmap.a lib/libdvec/build/libdvec.a
+19_HDR = common/aoc.h common/iccmp.h common/util.h
diff --git a/19/input b/19/input
@@ -0,0 +1,2 @@
+109,424,203,1,21102,11,1,0,1105,1,282,21102,1,18,0,1105,1,259,1201,1,0,221,203,1,21101,0,31,0,1105,1,282,21102,38,1,0,1106,0,259,21001,23,0,2,22101,0,1,3,21101,0,1,1,21102,1,57,0,1105,1,303,2101,0,1,222,21001,221,0,3,20102,1,221,2,21102,259,1,1,21101,80,0,0,1106,0,225,21101,0,111,2,21102,1,91,0,1105,1,303,2102,1,1,223,20101,0,222,4,21102,1,259,3,21102,1,225,2,21102,1,225,1,21101,0,118,0,1105,1,225,20101,0,222,3,21102,148,1,2,21102,1,133,0,1106,0,303,21202,1,-1,1,22001,223,1,1,21102,148,1,0,1106,0,259,2101,0,1,223,20102,1,221,4,21001,222,0,3,21101,0,17,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,0,195,0,106,0,109,20207,1,223,2,20102,1,23,1,21102,-1,1,3,21101,0,214,0,1105,1,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,2102,1,-4,249,22101,0,-3,1,21202,-2,1,2,21202,-1,1,3,21102,1,250,0,1105,1,225,22102,1,1,-4,109,-5,2106,0,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2105,1,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,22102,1,-2,-2,109,-3,2106,0,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,21202,-2,1,3,21101,0,343,0,1105,1,303,1105,1,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,21201,-4,0,1,21102,384,1,0,1106,0,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21202,1,1,-4,109,-5,2106,0,0
+
diff --git a/19/main.c b/19/main.c
@@ -0,0 +1,155 @@
+#include "aoc.h"
+#include "iccmp.h"
+#include "allocator.h"
+#include "dvec_s.h"
+#include "util.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+bool
+deploy(struct icc *icc, size_t x, size_t y)
+{
+ int input;
+
+ input = 0;
+ while (icc->state != ICC_HALT) {
+ icc_step_inst(icc);
+ switch (icc->state) {
+ case ICC_INPUT:
+ switch (input) {
+ case 0:
+ mi_setv(&icc->in, x, MI_POS);
+ input++;
+ break;
+ case 1:
+ mi_setv(&icc->in, y, MI_POS);
+ input++;
+ break;
+ }
+ break;
+ case ICC_OUTPUT:
+ return mi_cast_ul(&icc->out);
+ }
+ }
+
+ assert(false);
+}
+
+void
+part1(void)
+{
+ struct icc icc, save;
+ size_t x, y;
+ size_t answer;
+ bool inbeam;
+ bool inbeam_p;
+ size_t beam_start;
+
+ icc_init(&icc);
+ icc_parse_inst(&icc, aoc.input, aoc.input_size);
+
+ while (icc.state == ICC_RUN)
+ icc_step_inst(&icc);
+ assert(icc.state == ICC_INPUT);
+
+ icc_init(&save);
+ icc_copy(&save, &icc);
+
+ answer = 0;
+ beam_start = 0;
+ for (y = 0; y < 50; y++) {
+ inbeam_p = false;
+ for (x = beam_start; x < 50; x++) {
+ icc_copy(&icc, &save);
+ inbeam = deploy(&icc, x, y);
+ aoc_debug("%lu %lu %i\n", y, x, inbeam);
+ if (inbeam && !inbeam_p)
+ beam_start = x;
+ if (!inbeam && inbeam_p)
+ break;
+ inbeam_p = inbeam;
+
+ answer += inbeam;
+ }
+ }
+
+ aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "141";
+
+ icc_deinit(&icc);
+}
+
+void
+part2(void)
+{
+ const size_t sqw = 100, sqh = 100;
+ struct icc icc, save;
+ struct dvec ends;
+ size_t x, y;
+ size_t answer;
+ size_t beam_start;
+ size_t beam_end;
+ size_t *end;
+ bool inbeam;
+
+ icc_init(&icc);
+ icc_parse_inst(&icc, aoc.input, aoc.input_size);
+
+ while (icc.state == ICC_RUN)
+ icc_step_inst(&icc);
+ assert(icc.state == ICC_INPUT);
+
+ icc_init(&save);
+ icc_copy(&save, &icc);
+
+ dvec_init(&ends, sizeof(size_t), 10, &stdlib_strict_heap_allocator);
+
+ answer = 0;
+
+ beam_start = beam_end = 0;
+ for (y = 0; ; y++) {
+ inbeam = false;
+ for (x = beam_start; !inbeam; x++) {
+ if (x > beam_start + 10) {
+ aoc_debug("SKIP %lu\n", y);
+ end = dvec_add_slot(&ends);
+ *end = 0;
+ goto skip;
+ }
+ icc_copy(&icc, &save);
+ inbeam = deploy(&icc, x, y);
+ }
+ beam_start = x - 1;
+
+ inbeam = true;
+ if (beam_end < beam_start) beam_end = beam_start + 1;
+ for (x = beam_end; inbeam; x++) {
+ icc_copy(&icc, &save);
+ inbeam = deploy(&icc, x, y);
+ }
+ beam_end = x - 1;
+
+ end = dvec_add_slot(&ends);
+ *end = beam_end;
+
+ if (y >= sqh - 1) {
+ end = dvec_at(&ends, y - (sqh - 1));
+ if (*end >= beam_start + sqw) {
+ answer = beam_start * 10000 + (y - (sqh - 1));
+ goto exit;
+ }
+ }
+
+skip:
+ aoc_debug("%lu %lu %lu\n", y, beam_start, beam_end);
+ }
+
+exit:
+ aoc.answer = aprintf("%lu", answer);
+
+ dvec_deinit(&ends);
+ icc_deinit(&save);
+ icc_deinit(&icc);
+}
diff --git a/19/part1 b/19/part1
@@ -0,0 +1,43 @@
+--- Day 19: Tractor Beam ---
+
+Unsure of the state of Santa's ship, you borrowed the tractor beam technology from Triton. Time to
+test it out.
+
+When you're safely away from anything else, you activate the tractor beam, but nothing happens.
+It's hard to tell whether it's working if there's nothing to use it on. Fortunately, your ship's
+drone system can be configured to deploy a drone to specific coordinates and then check whether it's
+being pulled. There's even an Intcode program (your puzzle input) that gives you access to the drone
+system.
+
+The program uses two input instructions to request the X and Y position to which the drone should be
+deployed. Negative numbers are invalid and will confuse the drone; all numbers should be zero or
+positive.
+
+Then, the program will output whether the drone is stationary (0) or being pulled by something (1).
+For example, the coordinate X=0, Y=0 is directly in front of the tractor beam emitter, so the drone
+control program will always report 1 at that location.
+
+To better understand the tractor beam, it is important to get a good picture of the beam itself. For
+example, suppose you scan the 10x10 grid of points closest to the emitter:
+
+ X
+ 0-> 9
+ 0#.........
+ |.#........
+ v..##......
+ ...###....
+ ....###...
+Y .....####.
+ ......####
+ ......####
+ .......###
+ 9........##
+
+In this example, the number of points affected by the tractor beam in the 10x10 area closest to the
+emitter is 27.
+
+However, you'll need to scan a larger area to understand the shape of the beam. How many points are
+affected by the tractor beam in the 50x50 area closest to the emitter? (For each of X and Y, this
+will be 0 through 49.)
+
+
diff --git a/19/part2 b/19/part2
@@ -0,0 +1,58 @@
+--- Part Two ---
+
+You aren't sure how large Santa's ship is. You aren't even sure if you'll need to use this thing on
+Santa's ship, but it doesn't hurt to be prepared. You figure Santa's ship might fit in a 100x100
+square.
+
+The beam gets wider as it travels away from the emitter; you'll need to be a minimum distance away
+to fit a square of that size into the beam fully. (Don't rotate the square; it should be aligned to
+the same axes as the drone grid.)
+
+For example, suppose you have the following tractor beam readings:
+
+#.......................................
+.#......................................
+..##....................................
+...###..................................
+....###.................................
+.....####...............................
+......#####.............................
+......######............................
+.......#######..........................
+........########........................
+.........#########......................
+..........#########.....................
+...........##########...................
+...........############.................
+............############................
+.............#############..............
+..............##############............
+...............###############..........
+................###############.........
+................#################.......
+.................########OOOOOOOOOO.....
+..................#######OOOOOOOOOO#....
+...................######OOOOOOOOOO###..
+....................#####OOOOOOOOOO#####
+.....................####OOOOOOOOOO#####
+.....................####OOOOOOOOOO#####
+......................###OOOOOOOOOO#####
+.......................##OOOOOOOOOO#####
+........................#OOOOOOOOOO#####
+.........................OOOOOOOOOO#####
+..........................##############
+..........................##############
+...........................#############
+............................############
+.............................###########
+
+In this example, the 10x10 square closest to the emitter that fits entirely within the tractor beam
+has been marked O. Within it, the point closest to the emitter (the only highlighted O) is at X=25,
+Y=20.
+
+Find the 100x100 square closest to the emitter that fits entirely within the tractor beam; within
+that square, find the point closest to the emitter. What value do you get if you take that point's
+X coordinate, multiply it by 10000, then add the point's Y coordinate? (In the example above, this
+would be 250020.)
+
+
diff --git a/common/iccmp.c b/common/iccmp.c
@@ -105,12 +105,33 @@ icc_deinit(struct icc *icc)
void
icc_copy(struct icc *dst, struct icc *src)
{
+ struct hmap_iter hmap_iter;
+ struct maxint *key, *value;
+
dst->state = src->state;
mi_set(&dst->rip, &src->rip);
mi_set(&dst->base, &src->base);
mi_set(&dst->in, &src->in);
mi_set(&dst->out, &src->out);
- hmap_copy(&dst->instructions, &src->instructions);
+
+ for (HMAP_ITER(&dst->instructions, &hmap_iter)) {
+ mi_deinit(hmap_iter.link->key._p);
+ free(hmap_iter.link->key._p);
+ mi_deinit(hmap_iter.link->value._p);
+ free(hmap_iter.link->value._p);
+ }
+ hmap_clear(&dst->instructions);
+
+ for (HMAP_ITER(&src->instructions, &hmap_iter)) {
+ key = malloc(sizeof(struct maxint));
+ mi_init(key);
+ mi_set(key, hmap_iter.link->key.p);
+ value = malloc(sizeof(struct maxint));
+ mi_init(value);
+ mi_set(value, hmap_iter.link->value.p);
+ hmap_add(&dst->instructions, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.p = value});
+ }
}
void
@@ -144,13 +165,11 @@ icc_parse_inst(struct icc *icc, const char *str, size_t len)
key = malloc(sizeof(struct maxint));
assert(key != NULL);
-
- val = malloc(sizeof(struct maxint));
- assert(val != NULL);
-
mi_init(key);
mi_setv(key, (mi_ul) rip, MI_POS);
+ val = malloc(sizeof(struct maxint));
+ assert(val != NULL);
mi_init(val);
mi_setv(val, (mi_ul) ABS(v), v >= 0 ? MI_POS : MI_NEG);
