commit 92624930e87e34891fd11c65a6ca07697aebe7ba
parent 46c71563e0f52a64d3f88cff120701db947383a4
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 11 Nov 2021 02:29:34 +0100
Add day 11
Diffstat:
13 files changed, 396 insertions(+), 13 deletions(-)
diff --git a/data/helper/template/Makefile b/data/helper/template/Makefile
@@ -9,4 +9,5 @@ clean:
lib:
make -C ../../libs
-main: main.c ../../libs/build/libaoc.a
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/libs/Makefile b/libs/Makefile
@@ -1,5 +1,5 @@
CFLAGS = -I include -g -L build
-LDLIBS =
+LDLIBS =
AOC_OBJ_ = wrapper.o aoc.o util.o memvec.o hashmap.o maxint.o
AOC_OBJ = $(addprefix build/, $(AOC_OBJ_))
diff --git a/libs/include/hashmap.h b/libs/include/hashmap.h
@@ -34,7 +34,8 @@ void hashmap_init(struct hashmap *hm, int size, uint32_t (*hasher)(void *key, in
void hashmap_clear(struct hashmap *hm);
void hashmap_free(struct hashmap *hm);
-void hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value);
+int hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value);
+void hashmap_add(struct hashmap *hm, struct hashmap_key key, void *value);
int hashmap_get(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst);
int hashmap_pop(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **dst);
diff --git a/libs/include/iccmp.h b/libs/include/iccmp.h
@@ -35,7 +35,7 @@ enum {
typedef uint64_t inst_t;
struct icc {
- int status;
+ int status, debug;
struct maxint in, out;
struct maxint base;
@@ -63,3 +63,5 @@ void icc_get_inst(struct icc *icc, size_t addr, inst_t *out);
int icc_param_mode(inst_t inst, int param);
void icc_get_param(struct icc *icc, int param, struct maxint *out);
void icc_get_dest(struct icc *icc, int param, struct maxint *out);
+
+void icc_set_debug(struct icc *icc, int debug);
diff --git a/libs/src/hashmap.c b/libs/src/hashmap.c
@@ -75,7 +75,7 @@ hashmap_pop(struct hashmap *hm, struct hashmap_key key, struct hashmap_link **ds
}
void
-hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
+hashmap_add(struct hashmap *hm, struct hashmap_key key, void *value)
{
struct hashmap_link **iter;
@@ -88,6 +88,31 @@ hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
(*iter)->next = NULL;
}
+int
+hashmap_set(struct hashmap *hm, struct hashmap_key key, void *value)
+{
+ struct hashmap_link **iter;
+ struct hashmap_key ckey;
+
+ iter = &hm->buckets[hm->hash(key.key, key.len) % hm->size];
+ while (*iter) {
+ ckey = (*iter)->key;
+ if (ckey.len == key.len && !memcmp(ckey.key, key.key, key.len)) {
+ (*iter)->value = value;
+ return 1;
+ }
+ iter = &((*iter)->next);
+ }
+
+ *iter = CHKP(malloc(sizeof(struct hashmap_link)));
+ // TODO memdup key here using its length instead of in user code!!
+ (*iter)->key = key;
+ (*iter)->value = value;
+ (*iter)->next = NULL;
+
+ return 0;
+}
+
struct hashmap_iter
hashmap_iter(void)
{
@@ -111,8 +136,8 @@ hashmap_next(struct hashmap *hm, struct hashmap_iter *iter)
return 1;
}
}
-
iter->link = NULL;
+
return 0;
}
diff --git a/libs/src/iccmp.c b/libs/src/iccmp.c
@@ -6,6 +6,7 @@ icc_init(struct icc *icc)
icc->instp = 0;
icc->status = ICC_OK;
icc->base = MI_INIT;
+ icc->debug = aoc.debug;
mi_setv(&icc->base, 0, MI_POS);
icc->in = icc->out = MI_INIT;
icc->r1 = icc->r2 = icc->r3 = icc->r4 = MI_INIT;
@@ -15,12 +16,19 @@ icc_init(struct icc *icc)
void
icc_free(struct icc *icc)
{
+ struct maxint *mi;
+ int i;
+
+ mi_free(&icc->base);
mi_free(&icc->in);
mi_free(&icc->out);
mi_free(&icc->r1);
mi_free(&icc->r2);
mi_free(&icc->r3);
mi_free(&icc->r4);
+
+ for (i = 0; i < memvec_len(&icc->instructions); i++)
+ mi_free(memvec_get(&icc->instructions, i));
memvec_free(&icc->instructions);
}
@@ -88,7 +96,7 @@ icc_debug_op(struct icc *icc, const char *opstr, int n, int dst)
char *str;
int i;
- if (!aoc.debug) return;
+ if (!icc->debug) return;
icc_get_inst(icc, icc->instp, &inst);
@@ -422,3 +430,9 @@ icc_get_dest(struct icc *icc, int param, struct maxint *out)
};
}
+void
+icc_set_debug(struct icc *icc, int debug)
+{
+ icc->debug = debug;
+}
+
diff --git a/libs/src/maxint.c b/libs/src/maxint.c
@@ -68,7 +68,7 @@ void
mi_resize(struct maxint *m, int size)
{
if (size > m->cap || size < m->cap - 256) {
- m->cap = size;
+ m->cap = MAX(1, size * 2);
m->data = CHKP(realloc(m->data, m->cap * MI_ULBYTES));
}
if (size > m->size) {
@@ -82,10 +82,11 @@ mi_add_internal(struct maxint *m1, const struct maxint *m2, int m2_sign)
{
int carry, swapped;
mi_ul v;
- int i;
+ int i, mbits;
- if (m2->size >= m1->size)
- mi_resize(m1, m2->size + 1);
+ mbits = m2->data[m2->size - 1] >> (MI_ULBITS - 1);
+ mbits |= m1->data[m1->size - 1] >> (MI_ULBITS - 1);
+ mi_resize(m1, MAX(m1->size, m2->size) + (mbits != 0));
if (m1->sign != m2_sign) {
for (carry = i = 0; i < m1->size; i++) {
@@ -170,8 +171,10 @@ mi_mul(struct maxint *m1, const struct maxint *m2)
mi_setv(&sum, 0, MI_POS);
for (i = m1->size * MI_ULBITS - 1; i >= 0; i--) {
mi_shl(&sum, 1);
- if (MI_BITA(m1->data, MI_ULBITS, i))
- mi_add(&sum, m2);
+ if (MI_BITA(m1->data, MI_ULBITS, i)) {
+ if (m1->sign == MI_POS) mi_add(&sum, m2);
+ else mi_sub(&sum, m2);
+ }
}
mi_swap(&sum, m1);
diff --git a/libs/tests/maxint.c b/libs/tests/maxint.c
@@ -21,6 +21,12 @@ main()
mi_add(&a, &b);
printf("%s\n", (s1 = mi_decstr(s1, &a)));
+ mi_setv(&a, 1, MI_NEG);
+ mi_setv(&b, 1, MI_POS);
+ printf("MUL: %s * %s = ", (s1 = mi_binstr(s1, &a)), (s2 = mi_decstr(s2, &b)));
+ mi_mul(&a, &b);
+ printf("%s\n", (s1 = mi_binstr(s1, &a)));
+
mi_setv(&a, 10000000000000000000ULL, MI_POS);
printf("SHL: %s << 2 = \n", (s1 = mi_binstr(s1, &a)));
mi_shl(&a, 2);
diff --git a/src/11/Makefile b/src/11/Makefile
@@ -0,0 +1,13 @@
+CFLAGS = -g -I ../../libs/include -L ../../libs/build
+LDLIBS = -liccmp -laoc
+
+all: lib main
+
+clean:
+ rm main
+
+lib:
+ make -C ../../libs
+
+main: main.c ../../libs/build/*
+ $(CC) -o $@ $< $(CFLAGS) $(LDLIBS)
diff --git a/src/11/input b/src/11/input
@@ -0,0 +1 @@
+3,8,1005,8,310,1106,0,11,0,0,0,104,1,104,0,3,8,102,-1,8,10,1001,10,1,10,4,10,108,1,8,10,4,10,1002,8,1,28,1,105,11,10,3,8,102,-1,8,10,1001,10,1,10,4,10,1008,8,0,10,4,10,102,1,8,55,3,8,102,-1,8,10,1001,10,1,10,4,10,108,0,8,10,4,10,1001,8,0,76,3,8,1002,8,-1,10,101,1,10,10,4,10,108,0,8,10,4,10,102,1,8,98,1,1004,7,10,1006,0,60,3,8,102,-1,8,10,1001,10,1,10,4,10,108,0,8,10,4,10,1002,8,1,127,2,1102,4,10,1,1108,7,10,2,1102,4,10,2,101,18,10,3,8,1002,8,-1,10,1001,10,1,10,4,10,1008,8,0,10,4,10,102,1,8,166,1006,0,28,3,8,1002,8,-1,10,101,1,10,10,4,10,108,1,8,10,4,10,101,0,8,190,1006,0,91,1,1108,5,10,3,8,1002,8,-1,10,101,1,10,10,4,10,1008,8,1,10,4,10,1002,8,1,220,1,1009,14,10,2,1103,19,10,2,1102,9,10,2,1007,4,10,3,8,1002,8,-1,10,101,1,10,10,4,10,1008,8,1,10,4,10,101,0,8,258,2,3,0,10,1006,0,4,3,8,102,-1,8,10,1001,10,1,10,4,10,108,1,8,10,4,10,1001,8,0,286,1006,0,82,101,1,9,9,1007,9,1057,10,1005,10,15,99,109,632,104,0,104,1,21102,1,838479487636,1,21102,327,1,0,1106,0,431,21102,1,932813579156,1,21102,1,338,0,1106,0,431,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,21101,0,179318033447,1,21101,385,0,0,1105,1,431,21101,248037678275,0,1,21101,0,396,0,1105,1,431,3,10,104,0,104,0,3,10,104,0,104,0,21101,0,709496558348,1,21102,419,1,0,1105,1,431,21101,825544561408,0,1,21101,0,430,0,1106,0,431,99,109,2,22101,0,-1,1,21101,40,0,2,21102,462,1,3,21101,0,452,0,1106,0,495,109,-2,2105,1,0,0,1,0,0,1,109,2,3,10,204,-1,1001,457,458,473,4,0,1001,457,1,457,108,4,457,10,1006,10,489,1101,0,0,457,109,-2,2106,0,0,0,109,4,2101,0,-1,494,1207,-3,0,10,1006,10,512,21101,0,0,-3,22101,0,-3,1,22101,0,-2,2,21101,1,0,3,21102,531,1,0,1105,1,536,109,-4,2105,1,0,109,5,1207,-3,1,10,1006,10,559,2207,-4,-2,10,1006,10,559,22101,0,-4,-4,1106,0,627,21202,-4,1,1,21201,-3,-1,2,21202,-2,2,3,21102,578,1,0,1105,1,536,22101,0,1,-4,21101,1,0,-1,2207,-4,-2,10,1006,10,597,21102,0,1,-1,22202,-2,-1,-2,2107,0,-3,10,1006,10,619,21201,-1,0,1,21102,1,619,0,105,1,494,21202,-2,-1,-2,22201,-4,-2,-4,109,-5,2106,0,0
diff --git a/src/11/main.c b/src/11/main.c
@@ -0,0 +1,205 @@
+#include "aoc.h"
+#include "iccmp.h"
+#include "hashmap.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+struct vec2 {
+ int x, y;
+};
+
+struct panel {
+ struct vec2 pos;
+ int color;
+};
+
+int black = 0, white = 1;
+
+/* counter clockwise dx dy */
+struct vec2 dirs[] = {
+ { 0, -1 }, /* up */
+ { 1, 0 }, /* right */
+ { 0, 1 }, /* down */
+ { -1, 0 } /* left */
+};
+
+const char *solmap = "\
+.............................................\n\
+.............................................\n\
+...#..#.###...##...##..####.#.....##..###....\n\
+...#..#.#..#.#..#.#..#.#....#....#..#.#..#...\n\
+...#..#.#..#.#....#..#.###..#....#....#..#...\n\
+...#..#.###..#....####.#....#....#....###....\n\
+...#..#.#.#..#..#.#..#.#....#....#..#.#......\n\
+....##..#..#..##..#..#.#....####..##..#......\
+";
+
+uint32_t
+pos_hasher(void *p, int len)
+{
+ struct vec2 *d;
+ int hash;
+
+ d = p;
+ hash = (uint16_t) d->x;
+ hash |= ((uint16_t) d->y) << 16;
+
+ return hash;
+}
+
+char *
+gen_map(struct hashmap *panels, struct vec2 *pos, int rot)
+{
+ const char symbol[4] = "^>v<";
+ struct vec2 min, max, dims;
+ struct hashmap_iter iter;
+ struct vec2 *ppos;
+ int i, color;
+ char *map;
+
+ min.x = min.y = -2;
+ max.x = max.y = 2;
+ iter = hashmap_iter();
+ while (hashmap_next(panels, &iter)) {
+ ppos = iter.link->key.key;
+ min.x = MIN(min.x, ppos->x);
+ min.y = MIN(min.y, ppos->y);
+ max.x = MAX(max.x, ppos->x);
+ max.y = MAX(max.y, ppos->y);
+ }
+
+ if (pos) {
+ min.x = MIN(min.x, pos->x);
+ min.y = MIN(min.y, pos->y);
+ max.x = MAX(max.x, pos->x);
+ max.y = MAX(max.y, pos->y);
+ }
+
+ dims.x = max.x - min.x + 1;
+ dims.y = max.y - min.y + 1;
+ map = CHKP(malloc((dims.x + 1) * dims.y));
+ memset(map, '.', (dims.x + 1) * dims.y);
+
+ iter = hashmap_iter();
+ while (hashmap_next(panels, &iter)) {
+ ppos = iter.link->key.key;
+ color = *(int*)iter.link->value;
+ map[(ppos->y - min.y) * (dims.x + 1) + (ppos->x - min.x)] = color ? '#' : '.';
+ }
+
+ if (pos) {
+ map[(pos->y - min.y) * (dims.x + 1) + (pos->x - min.x)] = symbol[rot];
+ }
+
+ for (i = 0; i < dims.y; i++)
+ map[dims.x + i * (dims.x + 1)] = '\n';
+ map[(dims.x + 1) * dims.y - 1] = '\0';
+
+ return map;
+}
+
+void
+panels_init(struct hashmap *panels, int start_color)
+{
+ struct hashmap_link *read_color;
+ struct hashmap_key key;
+ int color, rot, brot;
+ struct vec2 pos;
+ struct icc icc;
+ char *map;
+ enum {
+ STATE_COLOR,
+ STATE_ROT
+ } state;
+
+ ASSERT(icc_init(&icc) == OK);
+ ASSERT(icc_parse_inst(&icc, aoc.input, aoc.input_size) == OK);
+
+ icc_set_debug(&icc, aoc.debug & 0b10);
+
+ pos.x = pos.y = 0;
+ hashmap_set(panels, HASHMAP_KEY(memdup(&pos, sizeof(pos)), sizeof(pos)), &start_color);
+
+ rot = 0;
+ color = 0;
+ state = STATE_COLOR;
+ while (icc.status != ICC_HALT) {
+ icc_step_inst(&icc);
+ switch (icc.status) {
+ case ICC_OUTPUT:
+ if (state == STATE_COLOR) {
+ color = mi_cast_ul(&icc.out);
+ ASSERT(color == 0 || color == 1);
+ key = HASHMAP_KEY(CHKP(memdup(&pos, sizeof(pos))), sizeof(pos));
+ debug("OUTPUT %i %i: %i\n", pos.x, pos.y, color);
+ if (hashmap_set(panels, key, color ? &white : &black))
+ free(key.key);
+ state = STATE_ROT;
+ } else if (state == STATE_ROT) {
+ brot = mi_cast_ul(&icc.out);
+ ASSERT(brot == 0 || brot == 1);
+ debug("ROT %i %i: %i\n", pos.x, pos.y, brot);
+ rot = (rot + (brot ? 1 : -1) + 4) % 4;
+ pos.x += dirs[rot].x;
+ pos.y += dirs[rot].y;
+ if (aoc.debug) {
+ map = gen_map(panels, &pos, rot);
+ debug("%s", map);
+ free(map);
+ }
+ state = STATE_COLOR;
+ }
+ break;
+ case ICC_INPUT:
+ key = HASHMAP_KEY(&pos, sizeof(pos));
+ if (hashmap_get(panels, key, &read_color)) {
+ debug("INPUT %i %i: %i\n", pos.x, pos.y, *((int*)read_color->value));
+ mi_setv(&icc.in, *((int*)read_color->value), MI_POS);
+ } else {
+ debug("INPUT %i %i: 0\n", pos.x, pos.y);
+ mi_setv(&icc.in, 0, MI_POS);
+ }
+ break;
+ }
+ }
+
+ icc_free(&icc);
+}
+
+void
+part1(void)
+{
+ struct hashmap panels;
+ struct hashmap_iter iter;
+ int count;
+
+ hashmap_init(&panels, 100, pos_hasher);
+ panels_init(&panels, black);
+
+ count = 0;
+ iter = hashmap_iter();
+ while (hashmap_next(&panels, &iter))
+ count += 1;
+ aoc.answer = CHKP(aprintf("%i", count));
+ aoc.solution = "2088";
+
+ hashmap_free(&panels);
+}
+
+void
+part2(void)
+{
+ struct hashmap panels;
+ struct hashmap_iter iter;
+ char *map;
+
+ hashmap_init(&panels, 100, pos_hasher);
+ panels_init(&panels, white);
+
+ map = gen_map(&panels, NULL, 0);
+ aoc.answer = CHKP(map);
+ aoc.solution = solmap;
+
+ hashmap_free(&panels);
+}
diff --git a/src/11/part1 b/src/11/part1
@@ -0,0 +1,97 @@
+--- Day 11: Space Police ---
+
+On the way to Jupiter, you're pulled over by the [1m[37mSpace Police[0m.
+
+"Attention, unmarked spacecraft! You are in violation of Space Law! All spacecraft must have a
+clearly visible [1m[37mregistration identifier[0m! You have 24 hours to comply or be sent to
+Space Jail!"
+
+Not wanting to be sent to Space Jail, you radio back to the Elves on Earth for help. Although it
+takes almost three hours for their reply signal to reach you, they send instructions for how to
+power up the [1m[37memergency hull painting robot[0m and even provide a small Intcode program
+(your puzzle input) that will cause it to paint your ship appropriately.
+
+There's just one problem: you don't have an emergency hull painting robot.
+
+You'll need to build a new emergency hull painting robot. The robot needs to be able to move around
+on the grid of square panels on the side of your ship, detect the color of its current panel, and
+paint its current panel [1m[37mblack[0m or [1m[37mwhite[0m. (All of the panels are currently
+[1m[37mblack[0m.)
+
+The Intcode program will serve as the brain of the robot. The program uses input instructions to
+access the robot's camera: provide 0 if the robot is over a [1m[37mblack[0m panel or 1 if the
+robot is over a [1m[37mwhite[0m panel. Then, the program will output two values:
+
+
+ - First, it will output a value indicating the [1m[37mcolor to paint the panel[0m the robot is
+over: 0 means to paint the panel [1m[37mblack[0m, and 1 means to paint the panel
+[1m[37mwhite[0m.
+
+ - Second, it will output a value indicating the [1m[37mdirection the robot should turn[0m: 0
+means it should turn [1m[37mleft 90 degrees[0m, and 1 means it should turn [1m[37mright 90
+degrees[0m.
+
+
+After the robot turns, it should always move [1m[37mforward exactly one panel[0m. The robot
+starts facing [1m[37mup[0m.
+
+The robot will continue running for a while like this and halt when it is finished drawing. Do not
+restart the Intcode computer inside the robot during this process.
+
+For example, suppose the robot is about to start running. Drawing black panels as ., white panels
+as #, and the robot pointing the direction it is facing (< ^ > v), the initial state and region near
+the robot looks like this:
+
+.....
+.....
+..^..
+.....
+.....
+
+The panel under the robot (not visible here because a ^ is shown instead) is also black, and so any
+input instructions at this point should be provided 0. Suppose the robot eventually outputs 1 (paint
+white) and then 0 (turn left). After taking these actions and moving forward one panel, the region
+now looks like this:
+
+.....
+.....
+.<#..
+.....
+.....
+
+Input instructions should still be provided 0. Next, the robot might output 0 (paint black) and then
+0 (turn left):
+
+.....
+.....
+..#..
+.v...
+.....
+
+After more outputs (1,0, 1,0):
+
+.....
+.....
+..^..
+.##..
+.....
+
+The robot is now back where it started, but because it is now on a white panel, input instructions
+should be provided 1. After several more outputs (0,1, 1,0, 1,0), the area looks like this:
+
+.....
+..<#.
+...#.
+.##..
+.....
+
+Before you deploy the robot, you should probably have an estimate of the area it will cover:
+specifically, you need to know the [1m[37mnumber of panels it paints at least once[0m, regardless
+of color. In the example above, the robot painted [1m[37m6 panels[0m at least once. (It painted
+its starting panel twice, but that panel is still only counted once; it also never painted the panel
+it ended on.)
+
+Build a new emergency hull painting robot and run the Intcode program on it. [1m[37mHow many
+panels does it paint at least once?[0m
+
+
diff --git a/src/11/part2 b/src/11/part2
@@ -0,0 +1,15 @@
+--- Part Two ---
+
+You're not sure what it's trying to paint, but it's definitely not a [1m[37mregistration
+identifier[0m. The Space Police are getting impatient.
+
+Checking your external ship cameras again, you notice a white panel marked "emergency hull painting
+robot starting panel". The rest of the panels are [1m[37mstill black[0m, but it looks like the
+robot was expecting to [1m[37mstart on a white panel[0m, not a black one.
+
+Based on the Space Law Space Brochure that the Space Police attached to one of your windows, a valid
+registration identifier is always [1m[37meight capital letters[0m. After starting the robot on a
+single [1m[37mwhite panel[0m instead, [1m[37mwhat registration identifier does it paint[0m on
+your hull?
+
+
