commit 3f99a98deed57aeaeb6a6cb01bef15591dfc6f1b
parent a56db3ca197612211365480617a15d3c14b5a680
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 31 Oct 2021 19:52:34 +0100
Add day 3 and ingegrated solution checks
Diffstat:
21 files changed, 604 insertions(+), 147 deletions(-)
diff --git a/libs/Makefile b/libs/Makefile
@@ -12,7 +12,10 @@ build:
build/%.o: src/%.c include/%.h | build
$(CC) -c -o $@ $< $(CFLAGS) $(LDLIBS)
-build/libaoc.a: build/util.o build/wrapper.o
+build/wrapper.o: src/wrapper.c
+ $(CC) -c -o $@ $< $(CFLAGS) $(LDLIBS)
+
+build/libaoc.a: build/util.o build/aoc.o build/wrapper.o
ar rcs $@ $^
build/test_%: tests/%.c
diff --git a/libs/include/aoc.h b/libs/include/aoc.h
@@ -1,5 +1,28 @@
+#ifndef AOC_AOC_H
+#define AOC_AOC_H
+
#include "util.h"
-#include "partinfo.h"
-void part1(struct partinfo *p);
-void part2(struct partinfo *p);
+struct aoc {
+ int debug;
+ int part;
+
+ char *answer;
+ const char *solution;
+
+ const char *inputfile;
+ char *input;
+ size_t input_size;
+
+ const char **args;
+};
+
+extern struct aoc aoc;
+
+void aoc_check(const char *sol, const char *fmtstr, ...);
+void debug(const char *fmtstr, ...);
+
+void part1();
+void part2();
+
+#endif
diff --git a/libs/include/partinfo.h b/libs/include/partinfo.h
@@ -1,17 +0,0 @@
-#ifndef AOC_PARTINFO_H
-#define AOC_PARTINFO_H
-
-#include <stdlib.h>
-
-struct partinfo {
- int debug;
- int part;
-
- const char *inputfile;
- char *input;
- size_t input_size;
-
- const char **args;
-};
-
-#endif // AOC_PARTINFO_H
diff --git a/libs/include/util.h b/libs/include/util.h
@@ -7,28 +7,40 @@
#include <unistd.h>
#include <string.h>
-#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)
+#define _STR(v) #v
+#define STR(v) _STR(v)
+#define LOC() __FILE__ ":" STR(__LINE__)
-enum { OK, FAIL };
+#define ASSERT(expr) assert(expr, \
+ "Assert '" #expr "' at " LOC() " failed\n")
-enum { FALSE, TRUE };
+#define CHKP(ptr) chkp(ptr, \
+ "Unexpected NULL pointer '" #ptr "' at " LOC() "\n")
-enum { MID_TOK, LAST_TOK };
+#define ABS(a) ((a) > 0 ? (a) : -(a))
+
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#define MIN(a, b) ((a) > (b) ? (b) : (a))
+
+#define MAXA(a, b) (ABS(a) > ABS(b) ? (a) : (b))
+#define MINA(a, b) (ABS(a) > ABS(b) ? (b) : (a))
-void exitmsg(int rv, const char *fmtstr, ...);
-void debug(const char *fmtstr, ...);
+#define ISWAP(a, b) (a ^= b ^= a)
+
+enum { OK, FAIL };
+
+enum { MID_TOK, LAST_TOK };
-const char* ntoken(const char *start, const char *end, size_t *len, const char *sep);
+void die(const char *fmtstr, ...);
+void assert(int res, const char *fmtstr, ...);
+void * chkp(void *alloc, const char *fmtstr, ...);
+char * aprintf(const char *fmtstr, ...);
-int min(int a, int b);
-int max(int a, int b);
+const char * ntoken(const char *start, const char *end,
+ size_t *len, const char *sep);
-void* chkp(void *alloc);
-void* memdup(void *data, size_t size);
+void * memdup(void *data, size_t size);
int readall(int fd, void **data, size_t *read);
-#endif // AOC_UTIL_H
+#endif
diff --git a/libs/src/aoc.c b/libs/src/aoc.c
@@ -0,0 +1,27 @@
+#include "aoc.h"
+
+void
+aoc_check(const char *sol, const char *fmtstr, ...)
+{
+ char buf[256];
+ va_list ap;
+
+ va_start(ap, fmtstr);
+ vsnprintf(buf, 256, fmtstr, ap);
+ va_end(ap);
+
+ assert(!strcmp(sol, buf), "AOC solution check failed");
+}
+
+void
+debug(const char *fmtstr, ...)
+{
+ va_list ap;
+
+ if (!aoc.debug) return;
+
+ va_start(ap, fmtstr);
+ vfprintf(stderr, fmtstr, ap);
+ va_end(ap);
+}
+
diff --git a/libs/src/maxint.c b/libs/src/maxint.c
@@ -175,7 +175,7 @@ void
mi_setv(struct maxint *m1, mi_ul v, int sign)
{
if (m1->size < 1) {
- m1->data = chkp(malloc(MI_ULBYTES));
+ m1->data = CHKP(malloc(MI_ULBYTES));
m1->size = 1;
}
m1->data[0] = v;
@@ -194,7 +194,7 @@ mi_swap(struct maxint *m1, struct maxint *m2)
void
mi_resize(struct maxint *m1, size_t size)
{
- m1->data = chkp(realloc(m1->data, size * MI_ULBYTES));
+ m1->data = CHKP(realloc(m1->data, size * MI_ULBYTES));
if (size > m1->size)
memset(&m1->data[m1->size], 0, (size - m1->size) * MI_ULBYTES);
m1->size = size;
@@ -242,7 +242,7 @@ mi_convstr(const struct maxint *m1, int base, const char *alph)
char *strbuf;
int carry;
- if (base <= 1) return chkp(strdup(""));
+ if (base <= 1) return CHKP(strdup(""));
mi_set(&num, m1);
mi_setv(&rem, 0, MI_POS);
diff --git a/libs/src/util.c b/libs/src/util.c
@@ -1,7 +1,8 @@
#include "util.h"
+#include "aoc.h"
void
-exitmsg(int rv, const char *fmtstr, ...)
+die(const char *fmtstr, ...)
{
va_list ap;
@@ -9,20 +10,64 @@ exitmsg(int rv, const char *fmtstr, ...)
vprintf(fmtstr, ap);
va_end(ap);
- exit(rv);
+ exit(1);
}
void
-debug(const char *fmtstr, ...)
+assert(int res, const char *fmtstr, ...)
{
va_list ap;
+ if (!res) {
+ va_start(ap, fmtstr);
+ vfprintf(stderr, fmtstr, ap);
+ va_end(ap);
+
+ exit(1);
+ }
+}
+
+void *
+chkp(void *ptr, const char *fmtstr, ...)
+{
+ va_list ap;
+
+ if (ptr == NULL) {
+ va_start(ap, fmtstr);
+ vfprintf(stderr, fmtstr, ap);
+ va_end(ap);
+
+ exit(1);
+ }
+
+ return ptr;
+}
+
+char *
+aprintf(const char *fmtstr, ...)
+{
+ va_list ap, cpy;
+ size_t nb;
+ char *str;
+
+ va_copy(cpy, ap);
+
+ va_start(cpy, fmtstr);
+ nb = vsnprintf(NULL, 0, fmtstr, cpy);
+ va_end(cpy);
+
+ assert(nb >= 0, "Invalid fmtstr: %s\n");
+ str = malloc(nb+1);
+ if (!str) return NULL;
+
va_start(ap, fmtstr);
- vfprintf(stderr, fmtstr, ap);
+ nb = vsnprintf(str, nb+1, fmtstr, ap);
va_end(ap);
+
+ return str;
}
-const char*
+const char *
ntoken(const char *start, const char *end,
size_t *len, const char *sep)
{
@@ -37,31 +82,12 @@ ntoken(const char *start, const char *end,
}
}
-int
-min(int a, int b)
-{
- return a < b ? a : b;
-}
-
-int
-max(int a, int b)
-{
- return a > b ? a : b;
-}
-
-void*
-chkp(void *alloc)
-{
- if (!alloc) die("Out of Memory\n");
- return alloc;
-}
-
-void*
+void *
memdup(void *data, size_t size)
{
void *new;
-
- new = chkp(malloc(size));
+
+ new = CHKP(malloc(size));
memcpy(new, data, size);
return new;
}
@@ -71,14 +97,14 @@ readall(int fileno, void **data, size_t *totalread)
{
size_t allocsize = 10, want = allocsize, got;
- *data = chkp(malloc(allocsize));
+ *data = CHKP(malloc(allocsize));
*totalread = 0;
while ((got = read(fileno, *data + *totalread, want)) > 0) {
if (got == want) {
allocsize *= 2;
*totalread += got;
- *data = chkp(realloc(*data, allocsize));
+ *data = CHKP(realloc(*data, allocsize));
} else {
*totalread += got;
}
diff --git a/libs/src/wrapper.c b/libs/src/wrapper.c
@@ -1,35 +1,50 @@
-#include "wrapper.h"
+#include "aoc.h"
+
+struct aoc aoc;
int
main(int argc, const char **argv)
{
- struct partinfo info;
const char *envvar;
FILE *f;
if (argc <= 1) die("Supply the part number to solve\n");
- info.args = &argv[2];
-
- info.inputfile = getenv("AOCINPUT");
- if (!info.inputfile) info.inputfile = "input";
- else debug("Using input file: '%s'\n", info.inputfile);
+ aoc.args = &argv[2];
+ /* parse user input */
envvar = getenv("AOCDEBUG");
- info.debug = envvar ? atoi(envvar) : 0;
+ aoc.debug = envvar ? atoi(envvar) : 0;
+
+ aoc.inputfile = getenv("AOCINPUT");
+ if (!aoc.inputfile) aoc.inputfile = "input";
+ else debug("Using input file: '%s'\n", aoc.inputfile);
- if (!(f = fopen("input", "r"))) die("Failed to open input file\n");
- if (readall(fileno(f), (void**) &info.input, &info.input_size) == FAIL)
+ aoc.part = atoi(argv[1]);
+
+ /* read input file */
+ if (!(f = fopen(aoc.inputfile, "r")))
+ die("Failed to open input file\n");
+ if (readall(fileno(f), (void**) &aoc.input, &aoc.input_size) == FAIL)
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);
+ aoc.input = CHKP(realloc(aoc.input, aoc.input_size + 1));
+ aoc.input[aoc.input_size] = '\0';
+
+ /* call solution */
+ aoc.answer = NULL;
+ aoc.solution = NULL;
+ if (aoc.part == 1) part1(&aoc);
+ else if (aoc.part == 2) part2(&aoc);
else die("Invalid part number\n");
- free(info.input);
+ /* check answer if given */
+ if (aoc.answer) {
+ printf("%s\n", aoc.answer);
+ if (aoc.solution && strcmp(aoc.answer, aoc.solution))
+ die("\nIncorrect solution!\n");
+ }
+
+ free(aoc.input);
}
diff --git a/libs/src/wrapper.o b/libs/src/wrapper.o
Binary files differ.
diff --git a/src/day1/main.c b/src/day1/main.c
@@ -5,43 +5,57 @@
#include "aoc.h"
void
-part1(struct partinfo *p)
+part1()
{
- const char *line = p->input, *end = p->input + p->input_size, *nline;
- char *endp = NULL;
+ const char *line, *end, *nline;
+ char *endp;
size_t len;
- long long ans = 0, fuel;
+ long long ans, fuel;
+ line = aoc.input;
+ end = aoc.input + aoc.input_size;
+
+ endp = NULL;
+ ans = 0;
do {
nline = ntoken(line, end, &len, "\n");
if (!len) continue;
fuel = strtoul(line, &endp, 10) / 3 - 2;
- if (endp && !memchr("\n", *endp, 2)) die("Failed to parse input '%s' as integer\n", line);
+ if (endp && !memchr("\n", *endp, 2))
+ die("Failed to parse input '%s' as integer\n", line);
ans += fuel;
line = nline;
} while (nline);
- printf("%llu\n", ans);
+ aoc.answer = aprintf("%llu", ans);
+ aoc.solution = "3286680";
}
void
-part2(struct partinfo *p)
+part2()
{
- const char *line = p->input, *end = p->input + p->input_size, *nline;
- char *endp = NULL;
+ const char *line, *end, *nline;
+ char *endp;
size_t len;
- long long ans = 0, fuel;
+ long long ans, fuel;
+
+ line = aoc.input;
+ end = aoc.input + aoc.input_size;
+ endp = NULL;
+ ans = 0;
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);
+ 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);
+ aoc.answer = aprintf("%llu", ans);
+ aoc.solution = "4927158";
}
diff --git a/src/day2/icc.c b/src/day2/icc.c
@@ -25,8 +25,10 @@ icc_parse_inst(struct icc *config, const char *str, size_t len)
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;
+ if (endptr && !memchr(",\n", *endptr, 3))
+ return FAIL;
+ if (memvec_add(&config->instructions, &val) == FAIL)
+ return FAIL;
line = nline;
} while (nline);
@@ -34,37 +36,47 @@ icc_parse_inst(struct icc *config, const char *str, size_t len)
}
void
+icc_inst_add(struct icc *config)
+{
+ 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;
+}
+
+void
+icc_inst_mul(struct icc *config)
+{
+ 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;
+}
+
+void
icc_step_inst(struct icc *config)
{
- int inst = icc_get_inst(config, config->instp);
+ int inst;
+
+ 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;
- }
+ icc_inst_add(config);
+ 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;
- }
+ icc_inst_mul(config);
+ break;
case ICC_INST_HALT:
config->status = ICC_HALT;
break;
@@ -93,3 +105,4 @@ icc_reset(struct icc *config, void *instcopy)
if (instcopy)
memcpy(config->instructions.data, instcopy, config->instructions.len);
}
+
diff --git a/src/day2/icc.h b/src/day2/icc.h
@@ -1,9 +1,10 @@
-#include <stdlib.h>
-
+#include "aoc.h"
#include "util.h"
#include "memvec.h"
-#define icc_get_inst(conf, addr) (*(int*)memvec_get(&(conf)->instructions, addr))
+#include <stdlib.h>
+
+#define ICC_GET_INST(conf, addr) (*(int*)memvec_get(&(conf)->instructions, addr))
enum {
ICC_INST_ADD = 1,
@@ -29,3 +30,4 @@ 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/main.c b/src/day2/main.c
@@ -1,38 +1,38 @@
-#include <stdlib.h>
-#include <stdio.h>
-
#include "aoc.h"
#include "icc.h"
+#include <stdlib.h>
+#include <stdio.h>
+
void
-part1(struct partinfo *p)
+part1()
{
struct icc config;
- assert(OK, icc_init(&config));
- assert(OK, icc_parse_inst(&config, p->input, p->input_size));
+ ASSERT(icc_init(&config) == OK);
+ ASSERT(icc_parse_inst(&config, aoc.input, aoc.input_size) == OK);
icc_set_inst(&config, 1, 12);
icc_set_inst(&config, 2, 2);
- while (config.status != ICC_HALT) {
+ while (config.status != ICC_HALT)
icc_step_inst(&config);
- }
- printf("%i\n", icc_get_inst(&config, 0));
+ aoc.answer = CHKP(aprintf("%i", ICC_GET_INST(&config, 0)));
+ aoc.solution = "5098658";
icc_free(&config);
}
void
-part2(struct partinfo *p)
+part2()
{
struct icc config;
void *instcopy;
int a, b;
- assert(OK, icc_init(&config));
- assert(OK, icc_parse_inst(&config, p->input, p->input_size));
+ ASSERT(icc_init(&config) == OK);
+ ASSERT(icc_parse_inst(&config, aoc.input, aoc.input_size) == OK);
instcopy = icc_inst_copy(&config);
for (a = 0; a < 100; a++) {
@@ -41,20 +41,20 @@ part2(struct partinfo *p)
icc_set_inst(&config, 2, b);
debug("\nTrying a:%i b:%i\n\n", a, b);
- while (config.status != ICC_HALT) {
+ while (config.status != ICC_HALT)
icc_step_inst(&config);
- }
- if (icc_get_inst(&config, 0) == 19690720) {
- printf("%i%i\n", a, b);
- goto cleanup;
+ if (ICC_GET_INST(&config, 0) == 19690720) {
+ aoc.answer = CHKP(aprintf("%02i%02i", a, b));
+ aoc.solution = "5064";
+ goto exit;
} else {
icc_reset(&config, instcopy);
}
}
}
-cleanup:
+exit:
free(instcopy);
icc_free(&config);
}
diff --git a/src/day2/memvec.c b/src/day2/memvec.c
@@ -7,6 +7,7 @@ memvec_init(struct memvec *v, size_t cap, size_t itemsize)
v->itemsize = itemsize;
v->len = 0;
v->data = malloc(v->cap);
+
return v->data ? OK : FAIL;
}
@@ -29,6 +30,7 @@ memvec_add(struct memvec *v, void *item)
}
memcpy(v->data + v->len, item, v->itemsize);
v->len += v->itemsize;
+
return OK;
}
@@ -41,12 +43,13 @@ memvec_get(struct memvec *v, size_t 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);
+ 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;
+ return index < v->len / v->itemsize;
}
diff --git a/src/day3/Makefile b/src/day3/Makefile
@@ -0,0 +1,12 @@
+CFLAGS = -g -I ../../libs/include -L ../../libs/build
+LDLIBS = -laoc
+
+all: lib main
+
+clean:
+ rm main
+
+lib:
+ make -C ../../libs
+
+main: main.c
diff --git a/src/day3/input b/src/day3/input
@@ -0,0 +1,2 @@
+R997,U849,R349,U641,R581,D39,R285,U139,R455,D346,L965,D707,R393,D302,L263,U58,R950,U731,R858,D748,R302,U211,R588,D441,L153,D417,R861,U775,R777,U204,R929,U868,L62,U163,R841,D214,L648,U626,R501,D751,L641,D961,L23,D430,L73,D692,R49,U334,L601,U996,R444,D658,R633,D30,L861,D811,R10,D394,R9,U227,L848,U420,L378,D622,L501,U397,R855,U369,R615,U591,L674,D166,L181,U61,L224,U463,L203,U594,R93,U614,L959,U198,L689,D229,L674,U255,R843,D382,R538,U923,L960,D775,L879,U97,R137,U665,L340,D941,L775,D57,R852,D167,R980,U704,L843,U989,L611,D32,L724,D790,L32,U984,L39,U671,L994,U399,R475,D85,L322,D936,R117,D261,R705,D696,L523,D433,L239,U477,L247,D465,R560,D902,L589,U682,R645,U376,L989,D121,L215,U514,R519,U407,L218,D444,R704,D436,L680,U759,R937,U400,R533,D860,R782,D233,R840,D549,L508,U380,L992,U406,L213,D403,L413,D532,L429,U186,R262,U313,L913,U873,L838,D882,R851,U70,R185,D131,R945,D595,L330,U446,R88,D243,L561,D952,R982,D395,L708,U459,L82,D885,L996,U955,L406,U697,L183,U266,L878,D839,R843,D891,R118,U772,R590,D376,L500,U370,R607,D12,L310,D436,L602,D365,R886,U239,L471,D418,L122,U18,R879,D693,R856,U848,L657,D911,L63,U431,R41,U752,R919,U323,L61,D263,L370,D85,R929,D213,R350,U818,R458,D912,R509,U394,L734,U49,R810,D87,L870,U658,R499,U550,L402,U244,L112,U859,R836,U951,R222,D944,L691,D731,R742,D52,R984,D453,L514,U692,R812,U35,L844,D177,L110,D22,R61,U253,R618,D51,R163,U835,R704,U148,R766,U297,R457,D170,L104,D441,R330,D330,R989,D538,R668,D811,R62,D67,L470,D526,R788,U376,R708,U3,R961
+L1009,D381,R970,U429,L230,D909,R516,D957,R981,U609,L480,D139,L861,U168,L48,U620,R531,D466,L726,D380,R977,D454,L318,D397,R994,U402,L77,U93,L359,D72,R968,D956,L174,D22,R218,U619,R593,U32,L154,U55,L169,U415,L171,U666,R617,U109,L265,U773,R541,D808,L797,U478,R731,U379,R311,D137,L806,U298,R362,D458,L254,D539,R700,U853,R246,D588,L28,U203,L432,U946,R663,D408,R974,U59,L683,D36,L139,U738,L780,U414,L401,D93,R212,D973,L710,U892,L357,D177,R823,D4,R46,D924,L235,D898,R67,U220,L592,U87,R94,U584,R979,D843,L299,D648,L491,U360,R824,D245,L944,D24,R616,U975,L4,U42,L984,U181,R902,D835,L687,D413,L767,U632,L754,U270,R413,U51,L825,D377,L596,U960,L378,U706,L859,D708,L156,D991,L814,U351,R923,D749,L16,D651,R20,D86,R801,U811,L228,U161,L871,U129,R215,U235,L784,U896,R94,U145,R822,U494,R248,D98,R494,U156,L495,U311,R66,D873,L294,D620,L885,U395,R778,D227,R966,U756,L694,D707,R983,D950,R706,D730,R415,U886,L465,D622,L13,D938,R324,D464,R723,U804,R942,D635,L729,D317,L522,U469,R550,D141,R302,U999,L642,U509,R431,D380,R18,D676,R449,D759,L495,U901,R1,D745,L655,U449,L439,D818,R55,D541,R420,U764,L426,D176,L520,U3,L663,D221,L80,D449,L987,U349,L71,U632,L887,D231,R655,D208,R698,D639,R804,U616,R532,U846,R363,D141,R659,U470,L798,U144,L675,U483,L944,U380,L329,U72,L894,D130,R53,U109,R610,U770,R778,U493,R972,D340,L866,U980,L305,D812,R130,D954,R253,D33,L912,U950,L438,D680,R891,U725,R171,D587,R549,D367,L4,U313,R522,D128,L711,D405,L769,D496,L527,U373,R725,D261,L268,D939,L902,D58,L858,D190,L442
diff --git a/src/day3/main.c b/src/day3/main.c
@@ -0,0 +1,215 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "aoc.h"
+
+struct line {
+ int sx, sy;
+ int ex, ey;
+
+ struct line *next;
+};
+
+struct line *
+read_lines(char **input)
+{
+ struct line *lines, **iter;
+ char *tok, *next, *end;
+ int x, y, val;
+
+ debug("START\n");
+
+ end = CHKP(strchr(*input, '\n'));
+
+ x = y = 0;
+ tok = *input;
+ lines = NULL;
+ iter = &lines;
+ while (next != end) {
+ next = strchr(tok, ',');
+ if (next > end || !next) next = end;
+ *iter = CHKP(malloc(sizeof(struct line)));
+ (*iter)->next = NULL;
+
+ *next = '\0';
+ val = atoi(tok+1);
+
+ (*iter)->sx = x;
+ (*iter)->sy = y;
+
+ switch (*tok) {
+ case 'L':
+ x -= val;
+ break;
+ case 'R':
+ x += val;
+ break;
+ case 'D':
+ y -= val;
+ break;
+ case 'U':
+ y += val;
+ break;
+ default:
+ die("Invalid move: %s\n", tok);
+ }
+
+ debug("%i %i\n", x, y);
+
+ (*iter)->ex = x;
+ (*iter)->ey = y;
+
+ iter = &(*iter)->next;
+ tok = next + 1;
+ }
+
+ debug("END\n");
+
+ *input = end + 1;
+ return lines;
+}
+
+int
+do_intersect(struct line *l1, struct line *l2)
+{
+ int inx, iny;
+
+ inx = MAX(l1->sx, l1->ex) >= MIN(l2->sx, l2->ex)
+ && MAX(l2->sx, l2->ex) >= MIN(l1->sx, l1->ex);
+ iny = MAX(l1->sy, l1->ey) >= MIN(l2->sy, l2->ey)
+ && MAX(l2->sy, l2->ey) >= MIN(l1->sy, l1->ey);
+
+ return inx && iny;
+}
+
+void
+intersection_near_origin(struct line *l1, struct line *l2, int *x, int *y)
+{
+ if (l1->sx == l1->ex && l2->sx == l2->ex) {
+ *x = l1->sx;
+ *y = MAXA(
+ MINA(l1->sy, l1->ey),
+ MINA(l2->sy, l2->ey)
+ );
+ } else if (l1->sy == l1->ey && l2->sy == l2->ey) {
+ *y = l1->sy;
+ *x = MAXA(
+ MINA(l1->sx, l1->ex),
+ MINA(l2->sy, l2->ey)
+ );
+ } else {
+ *x = (l1->sx == l1->ex) ? l1->sx : l2->sx;
+ *y = (l1->sy == l1->ey) ? l1->sy : l2->sy;
+ }
+}
+
+void
+intersection_least_steps(struct line *l1, struct line *l2, int *x, int *y)
+{
+ int in1, in2;
+
+ if (l1->sx == l1->ex && l2->sx == l2->ex) {
+ /* if both ends or both starts of lines are part of the intersection,
+ * any one of them will give the same best dist,
+ * otherwise the start that intersects is the best fit */
+ *x = l1->sx;
+ in1 = l1->sy <= MAX(l2->sy, l2->ey) && l1->sy >= MIN(l2->sy, l2->ey);
+ in2 = l2->sy <= MAX(l1->sy, l1->ey) && l2->sy >= MIN(l1->sy, l1->ey);
+ *y = in1 ? l1->sy : (in2 ? l2->sy : l2->ey);
+ } else if (l1->sy == l1->ey && l2->sy == l2->ey) {
+ /* same for x-axis */
+ *y = l1->sy;
+ in1 = l1->sx <= MAX(l2->sx, l2->ex) && l1->sx >= MIN(l2->sx, l2->ex);
+ in2 = l2->sx <= MAX(l1->sx, l1->ex) && l2->sx >= MIN(l1->sx, l1->ex);
+ *x = in1 ? l1->sx : (in2 ? l2->sx : l2->ex);
+ } else {
+ *x = (l1->sx == l1->ex) ? l1->sx : l2->sx;
+ *y = (l1->sy == l1->ey) ? l1->sy : l2->sy;
+ }
+}
+
+int
+calc_dist(struct line *lines, struct line *end, int x, int y)
+{
+ struct line *iter;
+ int dist;
+
+ dist = 0;
+ for (iter = lines; iter != end; iter = iter->next) {
+ dist += ABS(iter->ex - iter->sx);
+ dist += ABS(iter->ey - iter->sy);
+ debug("D: %i\n", dist);
+ }
+
+ dist += ABS(x - iter->sx);
+ dist += ABS(y - iter->sy);
+ debug("D: %i\n", dist);
+
+ return dist;
+}
+
+void
+part1()
+{
+ struct line *lines1, *lines2;
+ struct line *iter1, *iter2;
+ int nx, ny, hit;
+ char *pos;
+ int x, y;
+
+ pos = aoc.input;
+ lines1 = read_lines(&pos);
+ lines2 = read_lines(&pos);
+
+ x = y = 0;
+ for (iter1 = lines1; iter1; iter1 = iter1->next) {
+ for (iter2 = lines2; iter2; iter2 = iter2->next) {
+ hit = do_intersect(iter1, iter2);
+ if (!hit) continue;
+ intersection_near_origin(iter1, iter2, &nx, &ny);
+ if (!x && !y || ABS(nx) + ABS(ny) < ABS(x) + ABS(y)) {
+ x = nx;
+ y = ny;
+ }
+ }
+ }
+
+ printf("dist(%i, %i) = %i\n", x, y, ABS(x) + ABS(y));
+ aoc.answer = aprintf("%i", ABS(x) + ABS(y));
+ aoc.solution = "209";
+}
+
+void
+part2()
+{
+ struct line *lines1, *lines2;
+ struct line *iter1, *iter2;
+ int nx, ny, nd, hit;
+ int x, y, d;
+ char *pos;
+
+ pos = aoc.input;
+ lines1 = read_lines(&pos);
+ lines2 = read_lines(&pos);
+
+ x = y = 0;
+ for (iter1 = lines1; iter1; iter1 = iter1->next) {
+ for (iter2 = lines2; iter2; iter2 = iter2->next) {
+ hit = do_intersect(iter1, iter2);
+ if (!hit) continue;
+ intersection_least_steps(iter1, iter2, &nx, &ny);
+ nd = calc_dist(lines1, iter1, nx, ny);
+ nd += calc_dist(lines2, iter2, nx, ny);
+ if (!x && !y || nd < d) {
+ d = nd;
+ x = nx;
+ y = ny;
+ }
+ }
+ }
+
+ printf("steps(%i, %i) = %i\n", x, y, d);
+ aoc.answer = aprintf("%i", d);
+ aoc.solution = "43258";
+}
diff --git a/src/day3/part1 b/src/day3/part1
@@ -0,0 +1,59 @@
+--- Day 3: Crossed Wires ---
+
+The gravity assist was successful, and you're well on your way to the Venus refuelling station.
+During the rush back on Earth, the fuel management system wasn't completely installed, so that's
+next on the priority list.
+
+Opening the front panel reveals a jumble of wires. Specifically, [1m[37mtwo wires[0m are
+connected to a central port and extend outward on a grid. You trace the path each wire takes as it
+leaves the central port, one wire per line of text (your puzzle input).
+
+The wires twist and turn, but the two wires occasionally cross paths. To fix the circuit, you need
+to [1m[37mfind the intersection point closest to the central port[0m. Because the wires are on a
+grid, use the Manhattan distance for this measurement. While the wires do technically cross right at
+the central port where they both start, this point does not count, nor does a wire count as crossing
+with itself.
+
+For example, if the first wire's path is R8,U5,L5,D3, then starting from the central port (o), it
+goes right 8, up 5, left 5, and finally down 3:
+
+...........
+...........
+...........
+....+----+.
+....|....|.
+....|....|.
+....|....|.
+.........|.
+.o-------+.
+...........
+
+Then, if the second wire's path is U7,R6,D4,L4, it goes up 7, right 6, down 4, and left 4:
+
+...........
+.+-----+...
+.|.....|...
+.|..+--X-+.
+.|..|..|.|.
+.|.-[1m[37mX[0m--+.|.
+.|..|....|.
+.|.......|.
+.o-------+.
+...........
+
+These wires cross at two locations (marked X), but the lower-left one is closer to the central port:
+its distance is 3 + 3 = 6.
+
+Here are a few more examples:
+
+
+ - R75,D30,R83,U83,L12,D49,R71,U7,L72
+U62,R66,U55,R34,D71,R55,D58,R83 = distance 159
+
+ - R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
+U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = distance 135
+
+
+[1m[37mWhat is the Manhattan distance[0m from the central port to the closest intersection?
+
+
diff --git a/src/day3/part2 b/src/day3/part2
@@ -0,0 +1,44 @@
+--- Part Two ---
+
+It turns out that this circuit is very timing-sensitive; you actually need to [1m[37mminimize the
+signal delay[0m.
+
+To do this, calculate the [1m[37mnumber of steps[0m each wire takes to reach each intersection;
+choose the intersection where the [1m[37msum of both wires' steps[0m is lowest. If a wire visits
+a position on the grid multiple times, use the steps value from the [1m[37mfirst[0m time it
+visits that position when calculating the total value of a specific intersection.
+
+The number of steps a wire takes is the total number of grid squares the wire has entered to get to
+that location, including the intersection being considered. Again consider the example from above:
+
+...........
+.+-----+...
+.|.....|...
+.|..+--X-+.
+.|..|..|.|.
+.|.-X--+.|.
+.|..|....|.
+.|.......|.
+.o-------+.
+...........
+
+In the above example, the intersection closest to the central port is reached after 8+5+5+2 =
+[1m[37m20[0m steps by the first wire and 7+6+4+3 = [1m[37m20[0m steps by the second wire for a
+total of 20+20 = [1m[37m40[0m steps.
+
+However, the top-right intersection is better: the first wire takes only 8+5+2 = [1m[37m15[0m and
+the second wire takes only 7+6+2 = [1m[37m15[0m, a total of 15+15 = [1m[37m30[0m steps.
+
+Here are the best steps for the extra examples from above:
+
+
+ - R75,D30,R83,U83,L12,D49,R71,U7,L72
+U62,R66,U55,R34,D71,R55,D58,R83 = 610 steps
+
+ - R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
+U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = 410 steps
+
+
+[1m[37mWhat is the fewest combined steps the wires must take to reach an intersection?[0m
+
+
diff --git a/src/day3/test1 b/src/day3/test1
@@ -0,0 +1,2 @@
+R75,D30,R83,U83,L12,D49,R71,U7,L72
+U62,R66,U55,R34,D71,R55,D58,R83
diff --git a/src/day3/test2 b/src/day3/test2
@@ -0,0 +1,2 @@
+R8,U5,L5,D3
+U7,R6,D4,L4
