commit 915a11e0c7b0a0fd23a1f6f60d6282442aa25a8c
parent 400c6f642ff1542a8969b193d7b017e16d84cd38
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 17 Jan 2021 13:35:38 +0100
Add day 1 and day 2 both parts
Diffstat:
17 files changed, 481 insertions(+), 18 deletions(-)
diff --git a/data/helper/template/Makefile b/data/helper/template/Makefile
@@ -3,6 +3,9 @@ LDLIBS = -laoc
all: lib main
+clean:
+ rm main
+
lib:
make -C ../../libs
diff --git a/libs/Makefile b/libs/Makefile
@@ -1,4 +1,4 @@
-CFLAGS = -I include
+CFLAGS = -I include -g
LDLIBS =
all: build/libaoc.a
diff --git a/libs/include/util.h b/libs/include/util.h
@@ -9,20 +9,25 @@
#define die(...) exitmsg(1, __VA_ARGS__)
#define quit(...) exitmsg(0, __VA_ARGS__)
+#define assert(b, ...) do { if ((__VA_ARGS__) != (b)) \
+ die("Assert at %s:%i failed!\n", __FILE__, __LINE__); } while (0)
enum { OK, FAIL };
+enum { FALSE, TRUE };
+
enum { MID_TOK, LAST_TOK };
void exitmsg(int rv, const char *fmtstr, ...);
void debug(const char *fmtstr, ...);
-int ntoken(const char *start, char **ntok, size_t *len, char sep);
+const char* ntoken(const char *start, const char *end, size_t *len, const char *sep);
int min(int a, int b);
int max(int a, int b);
void* assertp(void *alloc);
+void* memdup(void *data, size_t size);
int readall(int fd, void **data, size_t *read);
diff --git a/libs/src/util.c b/libs/src/util.c
@@ -22,19 +22,18 @@ debug(const char *fmtstr, ...)
va_end(ap);
}
-int
-ntoken(const char *start, char **ntok, size_t *len, char sep)
+const char*
+ntoken(const char *start, const char *end,
+ size_t *len, const char *sep)
{
char *tokp;
- if ((tokp = strchr(start, sep))) {
+ if ((tokp = strpbrk(start, sep))) {
*len = tokp - start;
- *ntok = tokp + 1;
- return MID_TOK;
+ return tokp + 1;
} else {
- *len = strlen(start);
- *ntok = NULL;
- return LAST_TOK;
+ *len = end - start;
+ return NULL;
}
}
@@ -57,6 +56,16 @@ assertp(void *alloc)
return alloc;
}
+void*
+memdup(void *data, size_t size)
+{
+ void *new;
+
+ new = assertp(malloc(size));
+ memcpy(new, data, size);
+ return new;
+}
+
int
readall(int fileno, void **data, size_t *totalread)
{
diff --git a/libs/src/wrapper.c b/libs/src/wrapper.c
@@ -22,8 +22,14 @@ main(int argc, const char **argv)
die("Failed to read from input file\n");
fclose(f);
+ /* add null terminator */
+ info.input = realloc(info.input, info.input_size + 1);
+ info.input[info.input_size] = '\0';
+
info.part = atoi(argv[1]);
if (info.part == 1) part1(&info);
else if (info.part == 2) part2(&info);
else die("Invalid part number\n");
+
+ free(info.input);
}
diff --git a/src/day1/Makefile b/src/day1/Makefile
@@ -3,6 +3,9 @@ LDLIBS = -L ../../libs/build
all: lib main
+clean:
+ rm main
+
lib:
make -C ../../libs
diff --git a/src/day1/main.c b/src/day1/main.c
@@ -8,19 +8,19 @@
void
part1(struct partinfo *p)
{
- char *line = p->input, *nline, *endp = NULL;
+ const char *line = p->input, *end = p->input + p->input_size, *nline;
+ char *endp = NULL;
size_t len;
- int status;
- long long ans;
+ long long ans = 0, fuel;
do {
- status = ntoken(line, &nline, &len, '\n');
+ nline = ntoken(line, end, &len, "\n");
if (!len) continue;
- line[len] = 0;
- ans += strtoul(line, &endp, 10) / 3 - 2;
- if (endp && *endp != 0) die("Failed to parse input '%s' as integer\n", line);
+ fuel = strtoul(line, &endp, 10) / 3 - 2;
+ if (endp && !memchr("\n", *endp, 2)) die("Failed to parse input '%s' as integer\n", line);
+ ans += fuel;
line = nline;
- } while (status != LAST_TOK);
+ } while (nline);
printf("%llu\n", ans);
}
@@ -28,5 +28,21 @@ part1(struct partinfo *p)
void
part2(struct partinfo *p)
{
+ const char *line = p->input, *end = p->input + p->input_size, *nline;
+ char *endp = NULL;
+ size_t len;
+ long long ans = 0, fuel;
+
+ do {
+ nline = ntoken(line, end, &len, "\n");
+ if (!len) continue;
+ fuel = strtoul(line, &endp, 10);
+ if (endp && !memchr("\n", *endp, 2)) die("Failed to parse input '%s' as integer\n", line);
+ while ((fuel = fuel / 3 - 2) > 0) {
+ ans += fuel;
+ }
+ line = nline;
+ } while (nline);
+ printf("%llu\n", ans);
}
diff --git a/src/day1/part2 b/src/day1/part2
@@ -0,0 +1,32 @@
+--- Part Two ---
+
+During the second Go / No Go poll, the Elf in charge of the Rocket Equation Double-Checker stops the
+launch sequence. Apparently, you forgot to include additional fuel for the fuel you just added.
+
+Fuel itself requires fuel just like a module - take its mass, divide by three, round down, and
+subtract 2. However, that fuel [1m[37malso[0m requires fuel, and [1m[37mthat[0m fuel requires
+fuel, and so on. Any mass that would require [1m[37mnegative fuel[0m should instead be treated
+as if it requires [1m[37mzero fuel[0m; the remaining mass, if any, is instead handled by
+[1m[37mwishing really hard[0m, which has no mass and is outside the scope of this calculation.
+
+So, for each module mass, calculate its fuel and add it to the total. Then, treat the fuel amount
+you just calculated as the input mass and repeat the process, continuing until a fuel requirement is
+zero or negative. For example:
+
+
+ - A module of mass 14 requires 2 fuel. This fuel requires no further fuel (2 divided by 3 and
+rounded down is 0, which would call for a negative fuel), so the total fuel required is still just
+2.
+ - At first, a module of mass 1969 requires 654 fuel. Then, this fuel requires 216 more fuel (654 /
+3 - 2). 216 then requires 70 more fuel, which requires 21 fuel, which requires 5 fuel, which
+requires no further fuel. So, the total fuel required for a module of mass 1969 is 654 + 216 + 70 +
+21 + 5 = 966.
+ - The fuel required by a module of mass 100756 and its fuel is: 33583 + 11192 + 3728 + 1240 + 411 +
+135 + 43 + 12 + 2 = 50346.
+
+
+[1m[37mWhat is the sum of the fuel requirements[0m for all of the modules on your spacecraft when
+also taking into account the mass of the added fuel? (Calculate the fuel requirements for each
+module separately, then add them all up at the end.)
+
+
diff --git a/src/day2/Makefile b/src/day2/Makefile
@@ -0,0 +1,13 @@
+CFLAGS = -I ../../libs/include -L ../../libs/build -g
+LDLIBS = -laoc
+
+all: lib main
+
+lib:
+ make -C ../../libs
+
+clean:
+ rm main
+
+main: *.c *.h
+ $(CC) -o $@ *.c $(CFLAGS) $(LDLIBS)
diff --git a/src/day2/icc.c b/src/day2/icc.c
@@ -0,0 +1,95 @@
+#include "icc.h"
+
+int
+icc_init(struct icc *config)
+{
+ config->instp = 0;
+ config->status = ICC_OK;
+ return memvec_init(&config->instructions, 0, sizeof(int));
+}
+
+void
+icc_free(struct icc *config)
+{
+ memvec_free(&config->instructions);
+}
+
+int
+icc_parse_inst(struct icc *config, const char *str, size_t len)
+{
+ const char *line = str, *nline, *end = str + len;
+ char *endptr = NULL;
+ size_t linelen;
+ int val;
+
+ do {
+ nline = ntoken(line, end, &linelen, ",\n");
+ val = strtoul(line, &endptr, 10);
+ if (endptr && !memchr(",\n", *endptr, 3)) return FAIL;
+ if (memvec_add(&config->instructions, &val) == FAIL) return FAIL;
+ line = nline;
+ } while (nline);
+
+ return OK;
+}
+
+void
+icc_step_inst(struct icc *config)
+{
+ int inst = icc_get_inst(config, config->instp);
+
+ switch (inst) {
+ case ICC_INST_ADD:
+ {
+ int a, b, res, dst;
+ a = icc_get_inst(config, config->instp + 1);
+ b = icc_get_inst(config, config->instp + 2);
+ res = icc_get_inst(config, a)
+ + icc_get_inst(config, b);
+ dst = icc_get_inst(config, config->instp + 3);
+ debug("%i <= %i + %i\n", dst, a, b);
+ memvec_set(&config->instructions, dst, &res);
+ config->instp += 4;
+ break;
+ }
+ case ICC_INST_MULT:
+ {
+ int a, b, res, dst;
+ a = icc_get_inst(config, config->instp + 1);
+ b = icc_get_inst(config, config->instp + 2);
+ res = icc_get_inst(config, a)
+ * icc_get_inst(config, b);
+ dst = icc_get_inst(config, config->instp + 3);
+ debug("%i <= %i * %i\n", dst, a, b);
+ memvec_set(&config->instructions, dst, &res);
+ config->instp += 4;
+ break;
+ }
+ case ICC_INST_HALT:
+ config->status = ICC_HALT;
+ break;
+ default:
+ die("Hit unknown instruction: '%i'\n", inst);
+ }
+}
+
+void
+icc_set_inst(struct icc *config, size_t index, int val)
+{
+ memvec_set(&config->instructions, index, &val);
+}
+
+void*
+icc_inst_copy(struct icc *config)
+{
+ return memdup(config->instructions.data, config->instructions.len);
+}
+
+void
+icc_reset(struct icc *config, void *instcopy)
+{
+ config->status = ICC_OK;
+ config->instp = 0;
+ if (instcopy)
+ memcpy(config->instructions.data, instcopy, config->instructions.len);
+}
diff --git a/src/day2/icc.h b/src/day2/icc.h
@@ -0,0 +1,31 @@
+#include <stdlib.h>
+
+#include "util.h"
+#include "memvec.h"
+
+#define icc_get_inst(conf, addr) (*(int*)memvec_get(&(conf)->instructions, addr))
+
+enum {
+ ICC_INST_ADD = 1,
+ ICC_INST_MULT = 2,
+ ICC_INST_HALT = 99
+};
+
+enum {
+ ICC_OK,
+ ICC_HALT
+};
+
+struct icc {
+ int status;
+ size_t instp;
+ struct memvec instructions;
+};
+
+int icc_init(struct icc *config);
+void icc_free(struct icc *config);
+int icc_parse_inst(struct icc *config, const char *str, size_t len);
+void icc_step_inst(struct icc *config);
+void icc_set_inst(struct icc *config, size_t index, int val);
+void* icc_inst_copy(struct icc *config);
+void icc_reset(struct icc *config, void *instcopy);
diff --git a/src/day2/input b/src/day2/input
@@ -0,0 +1 @@
+1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,1,10,19,2,6,19,23,1,23,5,27,1,27,13,31,2,6,31,35,1,5,35,39,1,39,10,43,2,6,43,47,1,47,5,51,1,51,9,55,2,55,6,59,1,59,10,63,2,63,9,67,1,67,5,71,1,71,5,75,2,75,6,79,1,5,79,83,1,10,83,87,2,13,87,91,1,10,91,95,2,13,95,99,1,99,9,103,1,5,103,107,1,107,10,111,1,111,5,115,1,115,6,119,1,119,10,123,1,123,10,127,2,127,13,131,1,13,131,135,1,135,10,139,2,139,6,143,1,143,9,147,2,147,6,151,1,5,151,155,1,9,155,159,2,159,6,163,1,163,2,167,1,10,167,0,99,2,14,0,0
diff --git a/src/day2/main.c b/src/day2/main.c
@@ -0,0 +1,61 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "partinfo.h"
+#include "util.h"
+#include "icc.h"
+
+void
+part1(struct partinfo *p)
+{
+ struct icc config;
+
+ assert(OK, icc_init(&config));
+ assert(OK, icc_parse_inst(&config, p->input, p->input_size));
+
+ icc_set_inst(&config, 1, 12);
+ icc_set_inst(&config, 2, 02);
+
+ while (config.status != ICC_HALT) {
+ icc_step_inst(&config);
+ }
+
+ printf("%i\n", icc_get_inst(&config, 0));
+
+ icc_free(&config);
+}
+
+void
+part2(struct partinfo *p)
+{
+ struct icc config;
+ void *instcopy;
+ int a, b;
+
+ assert(OK, icc_init(&config));
+ assert(OK, icc_parse_inst(&config, p->input, p->input_size));
+ instcopy = icc_inst_copy(&config);
+
+ for (a = 0; a < 100; a++) {
+ for (b = 0; b < 100; b++) {
+ icc_set_inst(&config, 1, a);
+ icc_set_inst(&config, 2, b);
+
+ debug("\nTrying a:%i b:%i\n\n", a, b);
+ while (config.status != ICC_HALT) {
+ icc_step_inst(&config);
+ }
+
+ if (icc_get_inst(&config, 0) == 19690720) {
+ printf("%i%i\n", a, b);
+ goto cleanup;
+ } else {
+ icc_reset(&config, instcopy);
+ }
+ }
+ }
+
+cleanup:
+ free(instcopy);
+ icc_free(&config);
+}
diff --git a/src/day2/memvec.c b/src/day2/memvec.c
@@ -0,0 +1,52 @@
+#include "memvec.h"
+
+int
+memvec_init(struct memvec *v, size_t cap, size_t itemsize)
+{
+ v->cap = cap ? cap : 10 * itemsize;
+ v->itemsize = itemsize;
+ v->len = 0;
+ v->data = malloc(v->cap);
+ return v->data ? OK : FAIL;
+}
+
+void
+memvec_free(struct memvec *v)
+{
+ free(v->data);
+}
+
+int
+memvec_add(struct memvec *v, void *item)
+{
+ void *tmp;
+
+ if (v->len == v->cap) {
+ v->cap *= 2;
+ tmp = realloc(v->data, v->cap);
+ if (!tmp) return FAIL;
+ v->data = tmp;
+ }
+ memcpy(v->data + v->len, item, v->itemsize);
+ v->len += v->itemsize;
+ return OK;
+}
+
+void*
+memvec_get(struct memvec *v, size_t index)
+{
+ return v->data + v->itemsize * index;
+}
+
+void
+memvec_set(struct memvec *v, size_t index, void *item)
+{
+ if (!memvec_in_range(v, index)) die("Index out of range '%i'\n", index);
+ memcpy(v->data + v->itemsize * index, item, v->itemsize);
+}
+
+int
+memvec_in_range(struct memvec *v, size_t index)
+{
+ return (index >= v->len / v->itemsize) ? FALSE : TRUE;
+}
diff --git a/src/day2/memvec.h b/src/day2/memvec.h
@@ -0,0 +1,16 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "util.h"
+
+struct memvec {
+ void *data;
+ size_t cap, len, itemsize;
+};
+
+int memvec_init(struct memvec *v, size_t cap, size_t itemsize);
+void memvec_free(struct memvec *v);
+int memvec_add(struct memvec *v, void *item);
+void* memvec_get(struct memvec *v, size_t index);
+void memvec_set(struct memvec *v, size_t index, void *item);
+int memvec_in_range(struct memvec *v, size_t index);
diff --git a/src/day2/part1 b/src/day2/part1
@@ -0,0 +1,78 @@
+--- Day 2: 1202 Program Alarm ---
+
+On the way to your gravity assist around the Moon, your ship computer beeps angrily about a "1202
+program alarm". On the radio, an Elf is already explaining how to handle the situation: "Don't
+worry, that's perfectly norma--" The ship computer bursts into flames.
+
+You notify the Elves that the computer's magic smoke seems to have escaped. "That computer ran
+[1m[37mIntcode[0m programs like the gravity assist program it was working on; surely there are
+enough spare parts up there to build a new Intcode computer!"
+
+An Intcode program is a list of integers separated by commas (like 1,0,0,3,99). To run one, start
+by looking at the first integer (called position 0). Here, you will find an [1m[37mopcode[0m -
+either 1, 2, or 99. The opcode indicates what to do; for example, 99 means that the program is
+finished and should immediately halt. Encountering an unknown opcode means something went wrong.
+
+Opcode 1 [1m[37madds[0m together numbers read from two positions and stores the result in a third
+position. The three integers [1m[37mimmediately after[0m the opcode tell you these three
+positions - the first two indicate the [1m[37mpositions[0m from which you should read the input
+values, and the third indicates the [1m[37mposition[0m at which the output should be stored.
+
+For example, if your Intcode computer encounters 1,10,20,30, it should read the values at positions
+10 and 20, add those values, and then overwrite the value at position 30 with their sum.
+
+Opcode 2 works exactly like opcode 1, except it [1m[37mmultiplies[0m the two inputs instead of
+adding them. Again, the three integers after the opcode indicate [1m[37mwhere[0m the inputs and
+outputs are, not their values.
+
+Once you're done processing an opcode, [1m[37mmove to the next one[0m by stepping forward 4
+positions.
+
+For example, suppose you have the following program:
+
+1,9,10,3,2,3,11,0,99,30,40,50
+For the purposes of illustration, here is the same program split into multiple lines:
+
+1,9,10,3,
+2,3,11,0,
+99,
+30,40,50
+
+The first four integers, 1,9,10,3, are at positions 0, 1, 2, and 3. Together, they represent the
+first opcode (1, addition), the positions of the two inputs (9 and 10), and the position of the
+output (3). To handle this opcode, you first need to get the values at the input positions:
+position 9 contains 30, and position 10 contains 40. [1m[37mAdd[0m these numbers together to get
+70. Then, store this value at the output position; here, the output position (3) is [1m[37mat[0m
+position 3, so it overwrites itself. Afterward, the program looks like this:
+
+1,9,10,[1m[37m70[0m,
+2,3,11,0,
+99,
+30,40,50
+
+Step forward 4 positions to reach the next opcode, 2. This opcode works just like the previous, but
+it multiplies instead of adding. The inputs are at positions 3 and 11; these positions contain 70
+and 50 respectively. Multiplying these produces 3500; this is stored at position 0:
+
+[1m[37m3500[0m,9,10,70,
+2,3,11,0,
+99,
+30,40,50
+
+Stepping forward 4 more positions arrives at opcode 99, halting the program.
+
+Here are the initial and final states of a few more small programs:
+
+
+ - 1,0,0,0,99 becomes [1m[37m2[0m,0,0,0,99 (1 + 1 = 2).
+ - 2,3,0,3,99 becomes 2,3,0,[1m[37m6[0m,99 (3 * 2 = 6).
+ - 2,4,4,5,99,0 becomes 2,4,4,5,99,[1m[37m9801[0m (99 * 99 = 9801).
+ - 1,1,1,4,99,5,6,0,99 becomes [1m[37m30[0m,1,1,4,[1m[37m2[0m,5,6,0,99.
+
+
+Once you have a working computer, the first step is to restore the gravity assist program (your
+puzzle input) to the "1202 program alarm" state it had just before the last computer caught fire. To
+do this, [1m[37mbefore running the program[0m, replace position 1 with the value 12 and replace
+position 2 with the value 2. [1m[37mWhat value is left at position 0[0m after the program halts?
+
+
diff --git a/src/day2/part2 b/src/day2/part2
@@ -0,0 +1,42 @@
+--- Part Two ---
+
+"Good, the new computer seems to be working correctly! [1m[37mKeep it nearby[0m during this
+mission - you'll probably use it again. Real Intcode computers support many more features than your
+new one, but we'll let you know what they are as you need them."
+
+"However, your current priority should be to complete your gravity assist around the Moon. For this
+mission to succeed, we should settle on some terminology for the parts you've already built."
+
+Intcode programs are given as a list of integers; these values are used as the initial state for the
+computer's [1m[37mmemory[0m. When you run an Intcode program, make sure to start by initializing
+memory to the program's values. A position in memory is called an [1m[37maddress[0m (for example,
+the first value in memory is at "address 0").
+
+Opcodes (like 1, 2, or 99) mark the beginning of an [1m[37minstruction[0m. The values used
+immediately after an opcode, if any, are called the instruction's [1m[37mparameters[0m. For
+example, in the instruction 1,2,3,4, 1 is the opcode; 2, 3, and 4 are the parameters. The
+instruction 99 contains only an opcode and has no parameters.
+
+The address of the current instruction is called the [1m[37minstruction pointer[0m; it starts at
+0. After an instruction finishes, the instruction pointer increases by [1m[37mthe number of
+values in the instruction[0m; until you add more instructions to the computer, this is always 4 (1
+opcode + 3 parameters) for the add and multiply instructions. (The halt instruction would increase
+the instruction pointer by 1, but it halts the program instead.)
+
+"With terminology out of the way, we're ready to proceed. To complete the gravity assist, you need
+to [1m[37mdetermine what pair of inputs produces the output 19690720[0m."
+
+The inputs should still be provided to the program by replacing the values at addresses 1 and 2,
+just like before. In this program, the value placed in address 1 is called the [1m[37mnoun[0m,
+and the value placed in address 2 is called the [1m[37mverb[0m. Each of the two input values
+will be between 0 and 99, inclusive.
+
+Once the program has halted, its output is available at address 0, also just like before. Each time
+you try a pair of inputs, make sure you first [1m[37mreset the computer's memory to the values in
+the program[0m (your puzzle input) - in other words, don't reuse memory from a previous attempt.
+
+Find the input [1m[37mnoun[0m and [1m[37mverb[0m that cause the program to produce the output
+19690720. [1m[37mWhat is 100 * noun + verb?[0m (For example, if noun=12 and verb=2, the answer
+would be 1202.)
+
+
