commit 019fd07126c76913fdf62ee2bc1813e666ddf25c
parent 976f5e7b4682dc7f1735b9fd11dd4d7c56f5c8df
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 25 Mar 2023 19:25:58 +0100
Add day 17
Diffstat:
10 files changed, 845 insertions(+), 7 deletions(-)
diff --git a/17/info.mk b/17/info.mk
@@ -0,0 +1,4 @@
+17_SRC = 17/main.c common/main.c common/iccmp.c common/aoc.c common/util.c
+17_SRC += lib/libdvec/build/libdvec.a lib/liballoc/build/liballoc.a
+17_SRC += lib/libmaxint/build/libmaxint.a lib/libhmap/build/libhmap.a
+17_HDR = common/aoc.h common/iccmp.h common/util.h
diff --git a/17/input b/17/input
@@ -0,0 +1,2 @@
+1,330,331,332,109,2538,1102,1182,1,15,1102,1407,1,24,1001,0,0,570,1006,570,36,1002,571,1,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,15,1,15,1008,15,1407,570,1006,570,14,21101,58,0,0,1106,0,786,1006,332,62,99,21101,0,333,1,21102,73,1,0,1106,0,579,1101,0,0,572,1101,0,0,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,102,1,574,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1106,0,81,21102,1,340,1,1106,0,177,21102,477,1,1,1106,0,177,21102,1,514,1,21101,176,0,0,1105,1,579,99,21102,184,1,0,1106,0,579,4,574,104,10,99,1007,573,22,570,1006,570,165,101,0,572,1182,21101,375,0,1,21102,211,1,0,1106,0,579,21101,1182,11,1,21102,222,1,0,1106,0,979,21101,0,388,1,21101,233,0,0,1105,1,579,21101,1182,22,1,21101,0,244,0,1106,0,979,21101,0,401,1,21102,1,255,0,1106,0,579,21101,1182,33,1,21101,0,266,0,1106,0,979,21101,414,0,1,21101,277,0,0,1105,1,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21102,1182,1,1,21101,313,0,0,1106,0,622,1005,575,327,1101,0,1,575,21102,1,327,0,1106,0,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,2,12,0,109,4,1202,-3,1,586,21001,0,0,-1,22101,1,-3,-3,21101,0,0,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1106,0,597,109,-4,2106,0,0,109,5,1201,-4,0,629,21002,0,1,-2,22101,1,-4,-4,21102,1,0,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,653,20102,1,0,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21101,0,702,0,1105,1,786,21201,-1,-1,-1,1106,0,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21102,1,731,0,1105,1,786,1105,1,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,756,0,0,1106,0,786,1106,0,774,21202,-1,-11,1,22101,1182,1,1,21102,1,774,0,1106,0,622,21201,-3,1,-3,1106,0,640,109,-5,2106,0,0,109,7,1005,575,802,20101,0,576,-6,20101,0,577,-5,1105,1,814,21102,1,0,-1,21102,1,0,-5,21102,1,0,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,29,-3,22201,-6,-3,-3,22101,1407,-3,-3,2102,1,-3,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21101,1,0,-1,1106,0,924,1205,-2,873,21101,0,35,-4,1105,1,924,1202,-3,1,878,1008,0,1,570,1006,570,916,1001,374,1,374,1201,-3,0,895,1102,2,1,0,1201,-3,0,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,922,20102,1,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,29,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,39,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1102,1,1,575,21101,973,0,0,1106,0,786,99,109,-7,2106,0,0,109,6,21102,0,1,-4,21101,0,0,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1105,1,1041,21102,1,-4,-2,1106,0,1041,21101,0,-5,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,1202,-2,1,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,2101,0,-2,0,1105,1,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1105,1,989,21101,0,439,1,1106,0,1150,21102,477,1,1,1106,0,1150,21101,0,514,1,21101,0,1149,0,1105,1,579,99,21101,1157,0,0,1106,0,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,1201,-5,0,1176,1201,-4,0,0,109,-6,2106,0,0,0,5,24,1,3,1,24,1,3,1,24,1,3,1,24,1,3,5,9,12,7,1,9,1,9,2,7,1,9,1,9,2,7,1,9,1,9,2,7,1,9,1,5,6,7,1,9,1,5,1,4,11,7,1,5,1,12,1,1,1,7,1,5,1,6,11,1,11,12,1,1,1,1,1,1,1,3,1,18,11,20,1,1,1,1,1,22,11,18,1,1,1,1,1,1,1,3,1,16,11,1,1,16,1,1,1,1,1,1,1,1,1,1,1,1,1,10,11,1,1,1,1,1,1,1,1,10,1,5,1,1,1,3,1,1,1,1,1,1,1,10,1,5,7,1,5,10,1,7,1,7,1,12,1,7,1,7,1,20,1,7,1,20,11,26,1,1,1,26,5,26,1,1,1,26,1,1,1,26,1,1,1,18,5,3,1,1,1,18,1,3,1,3,1,1,1,18,1,3,1,3,1,1,1,18,1,3,1,3,1,1,1,18,1,3,5,1,1,18,1,9,1,18,11,8
+
diff --git a/17/main.c b/17/main.c
@@ -0,0 +1,606 @@
+#include "allocator.h"
+#include "util.h"
+#include "aoc.h"
+#include "iccmp.h"
+#include "hmap.h"
+#include "vec.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+enum {
+ DIR_NORTH,
+ DIR_EAST,
+ DIR_SOUTH,
+ DIR_WEST,
+};
+
+struct path {
+ struct vec2i start, end;
+};
+
+static const struct vec2i dirs[] = {
+ [DIR_NORTH] = { 0, -1 },
+ [DIR_EAST] = { 1, 0 },
+ [DIR_SOUTH] = { 0, 1 },
+ [DIR_WEST] = { -1, 0 },
+};
+
+bool
+vec2i_hmap_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+ const struct vec2i *v1 = k1.p, *v2 = k2.p;
+
+ return v1->x == v2->x && v1->y == v2->y;
+}
+
+uint32_t
+vec2i_hmap_hash(struct hmap_key key)
+{
+ const struct vec2i *v = key.p;
+
+ return (uint32_t) (v->x << 16) ^ (uint32_t) v->y;
+}
+
+int
+dir_from_char(char c)
+{
+ switch (c) {
+ case '^':
+ return DIR_NORTH;
+ case '>':
+ return DIR_EAST;
+ case 'v':
+ return DIR_SOUTH;
+ case '<':
+ return DIR_WEST;
+ default:
+ return -1;
+ }
+}
+
+int
+dir_from_path(struct path *path)
+{
+ if (path->end.x > path->start.x)
+ return DIR_EAST;
+ else if (path->end.x < path->start.x)
+ return DIR_WEST;
+ else if (path->end.y > path->start.y)
+ return DIR_SOUTH;
+ else if (path->end.y < path->start.y)
+ return DIR_NORTH;
+ assert(0);
+}
+
+void
+receive_map(struct icc *icc, struct hmap *map,
+ struct vec2i *min, struct vec2i *max,
+ struct vec2i *dpos, int *ddir)
+{
+ struct hmap_iter iter;
+ struct vec2i pos;
+ void *key;
+ char c;
+
+ for (HMAP_ITER(map, &iter))
+ free(iter.link->key._p);
+ hmap_clear(map);
+
+ vec2i_setv(min, 0, 0);
+ vec2i_setv(max, 0, 0);
+ vec2i_setv(&pos, 0, 0);
+ while (icc->state != ICC_HALT) {
+ icc_step_inst(icc);
+ if (icc->state == ICC_INPUT)
+ break;
+ if (icc->state == ICC_OUTPUT) {
+ c = (char) mi_cast_ul(&icc->out);
+ if (c == '\n') {
+ if (pos.x == 0) break;
+ pos.y += 1;
+ pos.x = 0;
+ } else {
+ if (dir_from_char(c) >= 0) {
+ vec2i_set(dpos, &pos);
+ *ddir = dir_from_char(c);
+ }
+ key = memdup(&pos, sizeof(struct vec2i));
+ hmap_add(map, (struct hmap_key) {.p = key},
+ (struct hmap_val) {.c = c});
+ if (pos.x > max->x) max->x = pos.x;
+ if (pos.y > max->y) max->y = pos.y;
+ if (pos.x < min->x) min->x = pos.x;
+ if (pos.y < min->y) min->y = pos.y;
+ pos.x += 1;
+ }
+ }
+ }
+}
+
+void
+receive_output(struct icc *icc)
+{
+ aoc_debug("ICC> ");
+ while (icc->state != ICC_HALT) {
+ icc_step_inst(icc);
+ if (icc->state == ICC_INPUT)
+ break;
+ if (icc->state == ICC_OUTPUT)
+ aoc_debug("%c", (char) mi_cast_ul(&icc->out));
+ }
+ assert(icc->state != ICC_HALT);
+}
+
+void
+print_map(struct hmap *map, struct vec2i min, struct vec2i max)
+{
+ struct hmap_link *link;
+ struct vec2i pos;
+
+ aoc_debug("+");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++)
+ aoc_debug("-");
+ aoc_debug("+\n");
+
+ for (pos.y = min.y; pos.y <= max.y; pos.y++) {
+ aoc_debug("|");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++) {
+ link = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (link) aoc_debug("%c", link->value.c);
+ else aoc_debug(" ");
+ }
+ aoc_debug("|\n");
+ }
+
+ aoc_debug("+");
+ for (pos.x = min.x; pos.x <= max.x; pos.x++)
+ aoc_debug("-");
+ aoc_debug("+\n");
+}
+
+void
+find_path_end(struct hmap *map, struct vec2i start,
+ size_t dir, struct vec2i *end)
+{
+ struct hmap_link *link;
+ struct vec2i ppos, pos;
+
+ vec2i_set(&pos, &start);
+ while (1) {
+ vec2i_set(&ppos, &pos);
+ vec2i_add(&pos, &pos, &dirs[dir]);
+ link = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (!link || link->value.c != '#')
+ break;
+ }
+
+ vec2i_set(end, &ppos);
+}
+
+void
+add_path(struct hmap *paths, struct path *path)
+{
+ struct hmap_link **link;
+ struct dvec *list;
+ void *key;
+
+ link = hmap_link_pos(paths, (struct hmap_key) {.p = &path->start});
+ if (*link) {
+ list = (*link)->value._p;
+ memcpy(dvec_add_slot(list, NULL), path, sizeof(struct path));
+ } else {
+ key = memdup(&path->start, sizeof(struct vec2i));
+ dvec_alloc(&list, sizeof(struct path),
+ 1, &stdlib_strict_heap_allocator);
+ memcpy(dvec_add_slot(list, NULL), path, sizeof(struct path));
+ hmap_add(paths,
+ (struct hmap_key) {.p = key},
+ (struct hmap_val) {.p = list});
+ }
+}
+
+void
+gen_paths(struct hmap *paths, struct hmap *map,
+ struct vec2i min, struct vec2i max)
+{
+ struct hmap_link *link;
+ struct vec2i pos, npos;
+ struct vec2i end;
+ struct path path;
+ bool side[4];
+ bool endpoint;
+ size_t i;
+
+ vec2i_setv(&pos, 0, 0);
+ for (pos.y = min.y; pos.y <= max.y; pos.y++) {
+ for (pos.x = min.x; pos.x <= max.x; pos.x++) {
+ link = hmap_get(map, (struct hmap_key) {.p = &pos});
+ if (!link || link->value.c == '.')
+ continue;
+
+ for (i = 0; i < ARRLEN(dirs); i++) {
+ side[i] = false;
+ vec2i_add(&npos, &pos, &dirs[i]);
+ link = hmap_get(map, (struct hmap_key) {.p = &npos});
+ side[i] = link ? link->value.c == '#' : false;
+ }
+
+ endpoint = (side[DIR_NORTH] != side[DIR_SOUTH]);
+ endpoint |= (side[DIR_WEST] != side[DIR_EAST]);
+ if (endpoint) {
+ aoc_debug("node %li %li\n", pos.x, pos.y);
+ for (i = 0; i < ARRLEN(dirs); i++) {
+ if (!side[i]) continue;
+ find_path_end(map, pos, i, &end);
+ vec2i_set(&path.start, &pos);
+ vec2i_set(&path.end, &end);
+ add_path(paths, &path);
+ }
+ }
+ }
+ }
+}
+
+void
+gen_insts(struct dvec *insts, struct hmap *paths,
+ struct vec2i start, int ddir)
+{
+ struct hmap_link *link;
+ struct dvec *list;
+ struct path *path;
+ struct vec2i ppos, pos;
+ char *inst, type;
+ int cnt, dir, ndir;
+ bool found;
+
+ dir = ddir;
+ vec2i_set(&pos, &start);
+ vec2i_set(&ppos, &pos);
+ while (1) {
+ link = hmap_get(paths, (struct hmap_key) {.p = &pos});
+ assert(link != NULL);
+
+ found = false;
+ list = link->value._p;
+ for (DVEC_ITER(list, &path)) {
+ if (vec2i_eql(&ppos, &path->end))
+ continue;
+ found = true;
+ break;
+ }
+
+ if (!found) break;
+
+ aoc_debug("path %i %i -> %i %i\n", path->start.x, path->start.y,
+ path->end.x, path->end.y);
+
+ vec2i_set(&ppos, &pos);
+ vec2i_set(&pos, &path->end);
+
+ ndir = dir_from_path(path);
+ aoc_debug("ndir %i\n", ndir);
+ type = ndir > dir ? 'R' : 'L';
+ cnt = ABS(ndir - dir);
+ if (cnt > 2) {
+ cnt = 4 - cnt;
+ type = type == 'L' ? 'R' : 'L';
+ }
+ for (; cnt > 0; cnt--) {
+ inst = dvec_add_slot(insts, NULL);
+ *inst = type;
+ }
+ dir = ndir;
+
+ cnt = (int) ABS(path->end.x - path->start.x)
+ + (int) ABS(path->end.y - path->start.y);
+ inst = dvec_add_slot(insts, NULL);
+ *inst = (char) -cnt;
+ }
+}
+
+char *
+insts_line(struct dvec *insts)
+{
+ char *str;
+ char *c;
+
+ str = NULL;
+ for (DVEC_ITER(insts, &c)) {
+ if (str) str = apprintf(str, ",");
+ if (*c < 0) {
+ str = apprintf(str, "%i", -*c);
+ } else {
+ str = apprintf(str, "%c", *c);
+ }
+ }
+ str = apprintf(str, "\n");
+
+ return str;
+}
+
+size_t
+gen_func(struct dvec *insts, struct dvec *main,
+ struct dvec *cur, char cc, size_t start, size_t len,
+ struct dvec *f1, char c1, struct dvec *f2, char c2)
+{
+ char *inst;
+ size_t i;
+
+ for (i = start; i < MIN(insts->len, start + len); i++) {
+ inst = dvec_add_slot(cur, NULL);
+ *inst = *(char *)dvec_at(insts, i);
+ }
+
+ inst = dvec_add_slot(main, NULL);
+ *inst = cc;
+
+ while (1) {
+ if (f1 && i + f1->len <= insts->len
+ && !memcmp(dvec_at(insts, i), f1->data, f1->len)) {
+ i += f1->len;
+ inst = dvec_add_slot(main, NULL);
+ *inst = c1;
+ } else if (f2 && i + f2->len <= insts->len
+ && !memcmp(dvec_at(insts, i), f2->data, f2->len)) {
+ i += f2->len;
+ inst = dvec_add_slot(main, NULL);
+ *inst = c2;
+ } else if (i + cur->len <= insts->len
+ && !memcmp(dvec_at(insts, i), cur->data, cur->len)) {
+ i += cur->len;
+ inst = dvec_add_slot(main, NULL);
+ *inst = cc;
+ } else {
+ break;
+ }
+ }
+
+ return i;
+}
+
+void
+gen_funcs(struct dvec *insts, struct dvec *main,
+ struct dvec *fa, struct dvec *fb, struct dvec *fc)
+{
+ size_t alen, blen, clen;
+ size_t lens, pos;
+ char *line;
+
+ lens = 0;
+ while (lens < 20 * 20 * 20) {
+ dvec_clear(main);
+ dvec_clear(fa);
+ dvec_clear(fb);
+ dvec_clear(fc);
+
+ lens += 1;
+ alen = (lens / 20 / 20) % 20;
+ blen = (lens / 20) % 20;
+ clen = lens % 20;
+ if (!alen || !blen || !clen)
+ continue;
+
+ pos = 0;
+ pos = gen_func(insts, main, fa, 'A', pos, alen, NULL, 0, NULL, 0);
+ pos = gen_func(insts, main, fb, 'B', pos, blen, fa, 'A', NULL, 0);
+ pos = gen_func(insts, main, fc, 'C', pos, clen, fa, 'A', fb, 'B');
+
+ assert(fa->len == alen);
+ assert(fb->len == blen);
+ assert(fc->len == clen);
+
+ if (aoc.debug && main->len > 3) {
+ line = insts_line(main);
+ aoc_debug("%2li %2li | %2li %2li %2li %s",
+ pos, insts->len, alen, blen, clen, line);
+ free(line);
+
+ line = insts_line(insts);
+ aoc_debug("%s", line);
+ free(line);
+
+ line = insts_line(fa);
+ aoc_debug("%s", line);
+ free(line);
+
+ line = insts_line(fb);
+ aoc_debug("%s", line);
+ free(line);
+
+ line = insts_line(fc);
+ aoc_debug("%s", line);
+ free(line);
+
+ aoc_debug("\n");
+ }
+
+ if (pos == insts->len && main->len <= 20)
+ return;
+ }
+ assert(0);
+}
+
+void
+send_line(struct icc *icc, const char *line)
+{
+ const char *c;
+
+ c = line;
+ while (icc->state != ICC_HALT && *c) {
+ icc_step_inst(icc);
+ switch (icc->state) {
+ case ICC_HALT:
+ case ICC_RUN:
+ continue;
+ case ICC_INPUT:
+ mi_setv(&icc->in, (mi_ul) *c, MI_POS);
+ c += 1;
+ break;
+ default:
+ receive_output(icc);
+ assert(0);
+ }
+ }
+ assert(icc->state != ICC_HALT);
+}
+
+void
+part1(void)
+{
+ struct icc icc;
+ struct hmap map;
+ struct hmap_link *link;
+ struct hmap_iter iter;
+ struct vec2i pos, npos;
+ struct vec2i min, max;
+ struct vec2i dpos;
+ size_t answer;
+ size_t i;
+ int ddir;
+
+ icc_init(&icc);
+ hmap_init(&map, 32, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+
+ icc_parse_inst(&icc, aoc.input, aoc.input_size);
+
+ receive_map(&icc, &map, &min, &max, &dpos, &ddir);
+
+ if (aoc.debug)
+ print_map(&map, min, max);
+
+ vec2i_setv(&pos, 0, 0);
+ answer = 0;
+ for (pos.y = min.y; pos.y <= max.y; pos.y++) {
+ for (pos.x = min.x; pos.x <= max.x; pos.x++) {
+ link = hmap_get(&map, (struct hmap_key) {.p = &pos});
+ if (!link || link->value.c == '.')
+ continue;
+ for (i = 0; i < ARRLEN(dirs); i++) {
+ vec2i_add(&npos, &pos, &dirs[i]);
+ link = hmap_get(&map, (struct hmap_key) {.p = &npos});
+ if (!link || link->value.c != '#')
+ break;
+ }
+ if (i == ARRLEN(dirs))
+ answer += (size_t) pos.x * (size_t) pos.y;
+ }
+ }
+
+ aoc.answer = aprintf("%lu", answer);
+ aoc.solution = "4112";
+
+ for (HMAP_ITER(&map, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&map);
+ icc_deinit(&icc);
+}
+
+void
+part2(void)
+{
+ struct icc icc;
+ struct hmap map;
+ struct hmap paths;
+ struct dvec insts;
+ struct dvec main;
+ struct dvec fa, fb, fc;
+ struct hmap_iter iter;
+ struct vec2i min, max;
+ struct vec2i dpos;
+ struct maxint mi_addr = MI_INIT;
+ struct maxint mi_val = MI_INIT;
+ mi_ul ul_addr, ul_val;
+ char *line, buf[256];
+ int ddir;
+
+ icc_init(&icc);
+ hmap_init(&map, 32, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ hmap_init(&paths, 32, vec2i_hmap_hash, vec2i_hmap_keycmp,
+ &stdlib_strict_heap_allocator);
+ dvec_init(&insts, sizeof(char), 32, &stdlib_strict_heap_allocator);
+ dvec_init(&main, sizeof(char), 0, &stdlib_strict_heap_allocator);
+ dvec_init(&fa, sizeof(char), 0, &stdlib_strict_heap_allocator);
+ dvec_init(&fb, sizeof(char), 0, &stdlib_strict_heap_allocator);
+ dvec_init(&fc, sizeof(char), 0, &stdlib_strict_heap_allocator);
+
+ icc_parse_inst(&icc, aoc.input, aoc.input_size);
+
+ icc_write(&icc, mi_imm(&mi_addr, &ul_addr, 0, MI_POS),
+ mi_imm(&mi_val, &ul_val, 2, MI_POS));
+
+ receive_map(&icc, &map, &min, &max, &dpos, &ddir);
+
+ if (aoc.debug)
+ print_map(&map, min, max);
+
+ gen_paths(&paths, &map, min, max);
+
+ gen_insts(&insts, &paths, dpos, ddir);
+
+ if (aoc.debug) {
+ aoc_debug("%li insts\n", insts.len);
+ line = insts_line(&insts);
+ aoc_debug("%s", line);
+ free(line);
+ }
+
+ gen_funcs(&insts, &main, &fa, &fb, &fc);
+
+ receive_output(&icc);
+ line = insts_line(&main);
+ if (aoc.debug) printf("main %s", line);
+ send_line(&icc, line);
+ free(line);
+
+ receive_output(&icc);
+ line = insts_line(&fa);
+ if (aoc.debug) printf("A %s", line);
+ send_line(&icc, line);
+ free(line);
+
+ receive_output(&icc);
+ line = insts_line(&fb);
+ if (aoc.debug) printf("B %s", line);
+ send_line(&icc, line);
+ free(line);
+
+ receive_output(&icc);
+ line = insts_line(&fc);
+ if (aoc.debug) printf("C %s", line);
+ send_line(&icc, line);
+ free(line);
+
+ receive_output(&icc);
+ send_line(&icc, "n\n");
+
+ while (icc.state != ICC_HALT)
+ icc_step_inst(&icc);
+exit:
+ mi_dec(&icc.out, buf, sizeof(buf), 0);
+ aoc.answer = aprintf("%s", buf);
+ aoc.solution = "578918";
+
+ dvec_deinit(&fc);
+ dvec_deinit(&fb);
+ dvec_deinit(&fa);
+ dvec_deinit(&main);
+ dvec_deinit(&insts);
+
+ for (HMAP_ITER(&paths, &iter)) {
+ free(iter.link->key._p);
+ dvec_free(iter.link->value._p);
+ }
+ hmap_deinit(&paths);
+
+ for (HMAP_ITER(&map, &iter))
+ free(iter.link->key._p);
+ hmap_deinit(&map);
+
+ icc_deinit(&icc);
+}
diff --git a/17/part1 b/17/part1
@@ -0,0 +1,73 @@
+--- Day 17: Set and Forget ---
+
+An early warning system detects an incoming solar flare and automatically activates the ship's
+electromagnetic shield. Unfortunately, this has cut off the Wi-Fi for many small robots that,
+unaware of the impending danger, are now trapped on exterior scaffolding on the unsafe side of the
+shield. To rescue them, you'll have to act quickly!
+
+The only tools at your disposal are some wired cameras and a small vacuum robot currently asleep at
+its charging station. The video quality is poor, but the vacuum robot has a needlessly bright LED
+that makes it easy to spot no matter where it is.
+
+An Intcode program, the Aft Scaffolding Control and Information Interface (ASCII, your puzzle
+input), provides access to the cameras and the vacuum robot. Currently, because the vacuum robot is
+asleep, you can only access the cameras.
+
+Running the ASCII program on your Intcode computer will provide the current view of the scaffolds.
+This is output, purely coincidentally, as ASCII code: 35 means #, 46 means ., 10 starts a new line
+of output below the current one, and so on. (Within a line, characters are drawn left-to-right.)
+
+In the camera output, # represents a scaffold and . represents open space. The vacuum robot is
+visible as ^, v, <, or > depending on whether it is facing up, down, left, or right respectively.
+When drawn like this, the vacuum robot is always on a scaffold; if the vacuum robot ever walks off
+of a scaffold and begins tumbling through space uncontrollably, it will instead be visible as X.
+
+In general, the scaffold forms a path, but it sometimes loops back onto itself. For example,
+suppose you can see the following view from the cameras:
+
+..#..........
+..#..........
+#######...###
+#.#...#...#.#
+#############
+..#...#...#..
+..#####...^..
+
+Here, the vacuum robot, ^ is facing up and sitting at one end of the scaffold near the bottom-right
+of the image. The scaffold continues up, loops across itself several times, and ends at the top-left
+of the image.
+
+The first step is to calibrate the cameras by getting the alignment parameters of some well-defined
+points. Locate all scaffold intersections; for each, its alignment parameter is the distance
+between its left edge and the left edge of the view multiplied by the distance between its top edge
+and the top edge of the view. Here, the intersections from the above image are marked O:
+
+..#..........
+..#..........
+##O####...###
+#.#...#...#.#
+##O###O###O##
+..#...#...#..
+..#####...^..
+
+For these intersections:
+
+
+ - The top-left intersection is 2 units from the left of the image and 2 units from the top of the
+image, so its alignment parameter is 2 * 2 = 4.
+
+ - The bottom-left intersection is 2 units from the left and 4 units from the top, so its alignment
+parameter is 2 * 4 = 8.
+
+ - The bottom-middle intersection is 6 from the left and 4 from the top, so its alignment parameter
+is 24.
+
+ - The bottom-right intersection's alignment parameter is 40.
+
+
+To calibrate the cameras, you need the sum of the alignment parameters. In the above example, this
+is 76.
+
+Run your ASCII program. What is the sum of the alignment parameters for the scaffold intersections?
+
+
diff --git a/17/part2 b/17/part2
@@ -0,0 +1,105 @@
+--- Part Two ---
+
+Now for the tricky part: notifying all the other robots about the solar flare. The vacuum robot can
+do this automatically if it gets into range of a robot. However, you can't see the other robots on
+the camera, so you need to be thorough instead: you need to make the vacuum robot visit every part
+of the scaffold at least once.
+
+The vacuum robot normally wanders randomly, but there isn't time for that today. Instead, you can
+override its movement logic with new rules.
+
+Force the vacuum robot to wake up by changing the value in your ASCII program at address 0 from 1 to
+2. When you do this, you will be automatically prompted for the new movement rules that the vacuum
+robot should use. The ASCII program will use input instructions to receive them, but they need to be
+provided as ASCII code; end each line of logic with a single newline, ASCII code 10.
+
+First, you will be prompted for the main movement routine. The main routine may only call the
+movement functions: A, B, or C. Supply the movement functions to use as ASCII text, separating them
+with commas (,, ASCII code 44), and ending the list with a newline (ASCII code 10). For example, to
+call A twice, then alternate between B and C three times, provide the string A,A,B,C,B,C,B,C and
+then a newline.
+
+Then, you will be prompted for each movement function. Movement functions may use L to turn left, R
+to turn right, or a number to move forward that many units. Movement functions may not call other
+movement functions. Again, separate the actions with commas and end the list with a newline. For
+example, to move forward 10 units, turn left, move forward 8 units, turn right, and finally move
+forward 6 units, provide the string 10,L,8,R,6 and then a newline.
+
+Finally, you will be asked whether you want to see a continuous video feed; provide either y or n
+and a newline. Enabling the continuous video feed can help you see what's going on, but it also
+requires a significant amount of processing power, and may even cause your Intcode computer to
+overheat.
+
+Due to the limited amount of memory in the vacuum robot, the ASCII definitions of the main routine
+and the movement functions may each contain at most 20 characters, not counting the newline.
+
+For example, consider the following camera feed:
+
+#######...#####
+#.....#...#...#
+#.....#...#...#
+......#...#...#
+......#...###.#
+......#.....#.#
+^########...#.#
+......#.#...#.#
+......#########
+........#...#..
+....#########..
+....#...#......
+....#...#......
+....#...#......
+....#####......
+
+In order for the vacuum robot to visit every part of the scaffold at least once, one path it could
+take is:
+
+R,8,R,8,R,4,R,4,R,8,L,6,L,2,R,4,R,4,R,8,R,8,R,8,L,6,L,2
+Without the memory limit, you could just supply this whole string to function A and have the main
+routine call A once. However, you'll need to split it into smaller parts.
+
+One approach is:
+
+
+ - Main routine: A,B,C,B,A,C(ASCII input: 65, 44, 66, 44, 67, 44, 66, 44, 65, 44, 67, 10)
+
+ - Function A: R,8,R,8(ASCII input: 82, 44, 56, 44, 82, 44, 56, 10)
+
+ - Function B: R,4,R,4,R,8(ASCII input: 82, 44, 52, 44, 82, 44, 52, 44, 82, 44, 56, 10)
+
+ - Function C: L,6,L,2(ASCII input: 76, 44, 54, 44, 76, 44, 50, 10)
+
+
+Visually, this would break the desired path into the following parts:
+
+A, B, C, B, A, C
+R,8,R,8, R,4,R,4,R,8, L,6,L,2, R,4,R,4,R,8, R,8,R,8, L,6,L,2
+
+CCCCCCA...BBBBB
+C.....A...B...B
+C.....A...B...B
+......A...B...B
+......A...CCC.B
+......A.....C.B
+^AAAAAAAA...C.B
+......A.A...C.B
+......AAAAAA#AB
+........A...C..
+....BBBB#BBBB..
+....B...A......
+....B...A......
+....B...A......
+....BBBBA......
+
+Of course, the scaffolding outside your ship is much more complex.
+
+As the vacuum robot finds other robots and notifies them of the impending solar flare, it also can't
+help but leave them squeaky clean, collecting any space dust it finds. Once it finishes the
+programmed set of movements, assuming it hasn't drifted off into space, the cleaning robot will
+return to its docking station and report the amount of space dust it collected as a large, non-ASCII
+value in a single output instruction.
+
+After visiting every part of the scaffold at least once, how much dust does the vacuum robot report
+it has collected?
+
+
diff --git a/common/iccmp.c b/common/iccmp.c
@@ -322,9 +322,10 @@ icc_inst_store(struct icc *icc)
{
int rc;
- if (icc->state != ICC_INPUT) {
+ if (icc->state != ICC_INPUT || !icc->in.size) {
icc_debug_op(icc, &icc->tmp, "INPUT", 0);
icc->state = ICC_INPUT;
+ icc->in.size = 0;
} else {
icc_debug_op_main(icc, &icc->tmp, "STORE", 1);
diff --git a/common/main.c b/common/main.c
@@ -46,10 +46,12 @@ main(int argc, const char **argv)
/* check answer if given */
if (aoc.answer) {
printf("%s\n", aoc.answer);
- if (aoc.solution && strcmp(aoc.answer, aoc.solution))
- errx(1, "Incorrect solution!");
- else if (!aoc.solution)
- errx(1, "Solution missing!");
+ if (!strcmp(aoc.inputfile, "input")) {
+ if (aoc.solution && strcmp(aoc.answer, aoc.solution))
+ errx(1, "Incorrect solution!");
+ else if (!aoc.solution)
+ errx(1, "Solution missing!");
+ }
}
free(aoc.answer);
diff --git a/common/util.c b/common/util.c
@@ -79,6 +79,32 @@ aprintf(const char *fmtstr, ...)
return str;
}
+char *
+apprintf(char *str, const char *fmtstr, ...)
+{
+ va_list ap, cpy;
+ ssize_t nb;
+ size_t len;
+
+ len = str ? strlen(str) : 0;
+
+ va_copy(cpy, ap);
+
+ va_start(cpy, fmtstr);
+ nb = vsnprintf(NULL, 0, fmtstr, cpy);
+ if (nb < 0) die("util: aprintf: invalid fmtstr: %s", fmtstr);
+ va_end(cpy);
+
+ str = realloc(str, len + (size_t) nb + 1);
+ if (!str) die("util: aprintf: realloc %lu", nb + 1);
+
+ va_start(ap, fmtstr);
+ nb = vsnprintf(str + len, (size_t) nb + 1, fmtstr, ap);
+ va_end(ap);
+
+ return str;
+}
+
void *
memdup(void *data, size_t size)
{
diff --git a/common/util.h b/common/util.h
@@ -7,7 +7,7 @@
#include <stdio.h>
#include <stdlib.h>
-#define ASSERT(expr) assert(expr, __FILE__, __LINE__, #expr)
+#define ARRLEN(x) (sizeof(x) / sizeof(*(x)))
#define ABS(a) ((a) > 0 ? (a) : -(a))
@@ -25,6 +25,7 @@ bool readtok(char *buf, size_t buflen,
int64_t parsei64(const char *str);
char *aprintf(const char *fmtstr, ...);
+char *apprintf(char *alloc, const char *fmtstr, ...);
void *memdup(void *data, size_t size);
void readall(FILE *f, void **data, size_t *read);
diff --git a/common/vec.h b/common/vec.h
@@ -1,6 +1,9 @@
#include <string.h>
+#include <stdbool.h>
#include <stdlib.h>
+#define VEC_ABS(x) ((x) > 0 ? (x) : -(x))
+
struct vec2i {
union {
struct {
@@ -38,7 +41,7 @@ struct vec3f {
};
#define DEFINE_VEC_SET(name, type, dims) \
- static inline void name(type *dst, type *src) { \
+ static inline void name(type *dst, const type *src) { \
memcpy(dst, src, sizeof(type)); \
}
@@ -60,10 +63,18 @@ struct vec3f {
dst->dims[i] = a->dims[i] * b; \
}
+#define DEFINE_VEC_EQL(name, type, n) \
+ static inline bool name(const type *a, const type *b) { \
+ for (int i = 0; i < n; i++) \
+ if (a->dims[i] != b->dims[i]) return false; \
+ return true; \
+ }
+
DEFINE_VEC_SET(vec2i_set, struct vec2i, 2);
DEFINE_VEC_ADD(vec2i_add, struct vec2i, 2);
DEFINE_VEC_SUB(vec2i_sub, struct vec2i, 2);
DEFINE_VEC_MUL(vec2i_mul, struct vec2i, ssize_t, 2);
+DEFINE_VEC_EQL(vec2i_eql, struct vec2i, 2);
static inline void
vec2i_setv(struct vec2i *dst, ssize_t x, ssize_t y)
@@ -72,10 +83,17 @@ vec2i_setv(struct vec2i *dst, ssize_t x, ssize_t y)
dst->y = y;
}
+static inline ssize_t
+vec2i_len(struct vec2i *a)
+{
+ return VEC_ABS(a->x) + VEC_ABS(a->y);
+}
+
DEFINE_VEC_SET(vec3i_set, struct vec3i, 3);
DEFINE_VEC_ADD(vec3i_add, struct vec3i, 3);
DEFINE_VEC_SUB(vec3i_sub, struct vec3i, 3);
DEFINE_VEC_MUL(vec3i_mul, struct vec3i, ssize_t, 3);
+DEFINE_VEC_EQL(vec3i_eql, struct vec3i, 3);
static inline void
vec3i_setv(struct vec3i *dst, ssize_t x, ssize_t y, ssize_t z)
