aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

commit e76280252fb8a5648f3ce2f85fac714a6d574f75
parent 912df267a6367396fa0f8ed1fa3700e0948a40cc
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Tue, 19 Dec 2023 15:54:12 +0100

Added solutions for 15, 16, 17, 18 and 19

Diffstat:
A2023/15/15a.c | 21+++++++++++++++++++++
A2023/15/15b.c | 48++++++++++++++++++++++++++++++++++++++++++++++++
A2023/16/16a.c | 37+++++++++++++++++++++++++++++++++++++
A2023/16/16b.c | 51+++++++++++++++++++++++++++++++++++++++++++++++++++
A2023/17/17a.c | 73+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A2023/17/17b.c | 74++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A2023/18/18b.c | 92+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A2023/19/19a.c | 87+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A2023/19/19b.c | 98+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
9 files changed, 581 insertions(+), 0 deletions(-)

diff --git a/2023/15/15a.c b/2023/15/15a.c @@ -0,0 +1,21 @@ +#include <stdio.h> + +#define N 100000 + +char *b, line[N]; +int c, s; + +int main() { + fgets(line, N, stdin); + + for (b = line, c = 0, s = 0; *b; b++) { + if (*b == ',' || *b == '\n') { + s += c; + c = 0; + } else + c = (c + (int)*b) * 17 % 256; + } + + printf("%d\n", s); + return 0; +} diff --git a/2023/15/15b.c b/2023/15/15b.c @@ -0,0 +1,48 @@ +#include <inttypes.h> +#include <stdio.h> + +#define N 100000 + +char *b, line[N]; +int64_t c, l, s, n[256], box[256][N]; + +int main() { + fgets(line, N, stdin); + + for (b = line, c = 0; *b != '\n'; b++) { + switch (*b) { + case ',': + c = 0; + l = 0; + break; + case '=': + int64_t i; + for (i = 0; i < n[c]; i++) + if (box[c][i] / 10 == l) + break; + if (i == n[c]) n[c]++; + box[c][i] = l * 10 + (int)(*(++b)-'0'); + break; + case '-': + for (int64_t i = 0; i < n[c]; i++) { + if (box[c][i] / 10 == l) { + for (int j = i+1; j < n[c]; j++) + box[c][j-1] = box[c][j]; + n[c]--; + } + } + break; + default: + c = (c + (int)*b) * 17 % 256; + l = l*256 + (int)*b; + break; + } + } + + for (int64_t i = 0; i < 256; i++) + for (int64_t j = 0; j < n[i]; j++) + s += (i+1) * (j+1) * (box[i][j]%10); + + printf("%" PRId64 "\n", s); + return 0; +} diff --git a/2023/16/16a.c b/2023/16/16a.c @@ -0,0 +1,37 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define M 200 + +char map[M][M]; +int s, n, nb, b[M][2], entered[M][M]; + +#define E 1 +#define N 2 +#define W 4 +#define S 8 +int turn[9][255] = { + [E] = { ['.'] = E, ['-'] = E, ['/'] = N, ['\\'] = S, ['|'] = N|S }, + [N] = { ['.'] = N, ['-'] = E|W, ['/'] = E, ['\\'] = W, ['|'] = N }, + [W] = { ['.'] = W, ['-'] = W, ['/'] = S, ['\\'] = N, ['|'] = N|S }, + [S] = { ['.'] = S, ['-'] = E|W, ['/'] = W, ['\\'] = E, ['|'] = S }, +}; +int go[9][2] = { [E] = {0, 1}, [N] = {-1, 0}, [W] = {0, -1}, [S] = {1, 0} }; + +void walk(int i, int j, int d) { + if (i < 0 || j < 0 || i >= n || j >= n || (entered[i][j] & d)) return; + if (!entered[i][j]) s++; + entered[i][j] |= d; + for (int k = 1; k <= 8; k <<= 1) + if (k & turn[d][map[i][j]]) + walk(i+go[k][0], j+go[k][1], k); +} + +int main() { + for (n = 0; fgets(map[n], M, stdin) != NULL; n++) ; + walk(0, 0, E); + printf("%d\n", s); + return 0; +} diff --git a/2023/16/16b.c b/2023/16/16b.c @@ -0,0 +1,51 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define M 200 +#define MAX(x,y) ((x)>(y)?(x):(y)) + +char map[M][M]; +int s, t, n, nb, b[M][2], entered[M][M]; + +#define E 1 +#define N 2 +#define W 4 +#define S 8 +int turn[9][255] = { + [E] = { ['.'] = E, ['-'] = E, ['/'] = N, ['\\'] = S, ['|'] = N|S }, + [N] = { ['.'] = N, ['-'] = E|W, ['/'] = E, ['\\'] = W, ['|'] = N }, + [W] = { ['.'] = W, ['-'] = W, ['/'] = S, ['\\'] = N, ['|'] = N|S }, + [S] = { ['.'] = S, ['-'] = E|W, ['/'] = W, ['\\'] = E, ['|'] = S }, +}; +int go[9][2] = { [E] = {0, 1}, [N] = {-1, 0}, [W] = {0, -1}, [S] = {1, 0} }; + +void walk(int i, int j, int d) { + if (i < 0 || j < 0 || i >= n || j >= n || (entered[i][j] & d)) return; + if (!entered[i][j]) s++; + entered[i][j] |= d; + for (int k = 1; k <= 8; k <<= 1) + if (k & turn[d][map[i][j]]) + walk(i+go[k][0], j+go[k][1], k); +} + +void clear(void) { + s = 0; + for (int i = 0; i < n; i++) + memset(entered[i], 0, n * sizeof(int)); +} + +int main() { + for (n = 0; fgets(map[n], M, stdin) != NULL; n++) ; + + for (int i = 0; i < n; i++) { + clear(); walk(i, 0, E); t = MAX(s, t); + clear(); walk(i, n-1, W); t = MAX(s, t); + clear(); walk(0, i, S); t = MAX(s, t); + clear(); walk(n-1, i, N); t = MAX(s, t); + } + + printf("%d\n", t); + return 0; +} diff --git a/2023/17/17a.c b/2023/17/17a.c @@ -0,0 +1,73 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define M 150 +#define MAXE 1000000 +#define INF 999999999 + +#define E 0 +#define N 1 +#define W 2 +#define S 3 + +int go[4][2] = { [E] = {0, 1}, [N] = {-1, 0}, [W] = {0, -1}, [S] = {1, 0} }; + +typedef struct { int i, j, k, s, d; } node_t; + +char map[M][M]; +int n, nq, d[M][M][4][4]; +node_t heap[MAXE]; + +void swap(int i, int j) { + node_t aux = heap[i]; + heap[i] = heap[j]; + heap[j] = aux; +} + +void push(node_t node) { + heap[nq] = node; + for (int k = nq++; k > 0 && heap[k].d < heap[(k-1)/2].d; k = (k-1)/2) + swap(k, (k-1)/2); +} + +node_t pop(void) { + node_t ret = heap[0]; + heap[0] = heap[--nq]; + for (int k = 0, j = 0; 2*k+1 < nq; k = j) { + j = 2*k+1; + if (j+1 < nq && heap[j].d > heap[j+1].d) j++; + if (heap[k].d > heap[j].d) swap(k, j); + } + return ret; +} + +int main() { + for (n = 0; fgets(map[n], M, stdin) != NULL; n++) ; + + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + for (int k = 0; k < 4; k++) + for (int s = 0; s < 4; s++) + d[i][j][k][s] = INF; + + push((node_t){.i = 0, .j = 0, .k = -1, .s = 0}); + node_t v; + for (v = pop(); v.i != n-1 || v.j != n-1; v = pop()) { + for (int k = 0; k < 4; k++) { + if (k == v.k + 2 || k == v.k - 2) continue; + int ii = v.i+go[k][0]; + int jj = v.j+go[k][1]; + if (ii < 0 || jj < 0 || ii >= n || jj >= n) continue; + int ss = k == v.k ? v.s + 1 : 1; + int dd = v.d + map[ii][jj] - '0'; + if (d[ii][jj][k][ss] <= dd || ss > 3) continue; + d[ii][jj][k][ss] = dd; + push((node_t){.i=ii, .j=jj, .k=k, .s=ss, .d=dd}); + } + } + + printf("%d\n", v.d); + return 0; +} diff --git a/2023/17/17b.c b/2023/17/17b.c @@ -0,0 +1,74 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define M 150 +#define MAXE 1000000 +#define INF 999999999 + +#define E 0 +#define N 1 +#define W 2 +#define S 3 + +int go[4][2] = { [E] = {0, 1}, [N] = {-1, 0}, [W] = {0, -1}, [S] = {1, 0} }; + +typedef struct { int i, j, k, s, d; } node_t; + +char map[M][M]; +int n, nq, d[M][M][4][11]; +node_t heap[MAXE]; + +void swap(int i, int j) { + node_t aux = heap[i]; + heap[i] = heap[j]; + heap[j] = aux; +} + +void push(node_t node) { + heap[nq] = node; + for (int k = nq++; k > 0 && heap[k].d < heap[(k-1)/2].d; k = (k-1)/2) + swap(k, (k-1)/2); +} + +node_t pop(void) { + node_t ret = heap[0]; + heap[0] = heap[--nq]; + for (int k = 0, j = 0; 2*k+1 < nq; k = j) { + j = 2*k+1; + if (j+1 < nq && heap[j].d > heap[j+1].d) j++; + if (heap[k].d > heap[j].d) swap(k, j); + } + return ret; +} + +int main() { + for (n = 0; fgets(map[n], M, stdin) != NULL; n++) ; + + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + for (int k = 0; k < 4; k++) + for (int s = 0; s < 11; s++) + d[i][j][k][s] = INF; + + push((node_t){.i = 0, .j = 0, .k = -1, .s = 0}); + node_t v; + for (v = pop(); v.i != n-1 || v.j != n-1; v = pop()) { + for (int k = 0; k < 4; k++) { + if (k == v.k + 2 || k == v.k - 2) continue; + if (v.s < 4 && v.k != -1 && v.k != k) continue; + int ii = v.i+go[k][0]; + int jj = v.j+go[k][1]; + if (ii < 0 || jj < 0 || ii >= n || jj >= n) continue; + int ss = k == v.k ? v.s + 1 : 1; + int dd = v.d + map[ii][jj] - '0'; + if (d[ii][jj][k][ss] <= dd || ss > 10) continue; + d[ii][jj][k][ss] = dd; + push((node_t){.i=ii, .j=jj, .k=k, .s=ss, .d=dd}); + } + } + + printf("%d\n", v.d); + return 0; +} diff --git a/2023/18/18b.c b/2023/18/18b.c @@ -0,0 +1,92 @@ +/* +I have lost my code for part one. It reused some stuff from day 10. +This code can be adjusted to work for part one, just change the input reading. +*/ + +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define N 1000 +#define MAX(x,y) ((x)>(y)?(x):(y)) +#define MIN(x,y) ((x)<(y)?(x):(y)) + +typedef struct { int64_t i, j; } point_t; + +char *buf, in[50]; +int64_t k, l, oldl, n, r, t, nolda, nb, a[N], olda[N], b[N]; +point_t p[N]; +point_t go[] = {{.i=0, .j=1}, {.i=1, .j=0}, {.i=0, .j=-1}, {.i=-1, .j=0}}; + +int cmp_int64(const void *x, const void *y) { + const int64_t *a = x, *b = y; + return *a > *b ? 1 : (*a < *b) ? -1 : 0; +} + +int cmp_point(const void *x, const void *y) { + const point_t *p = x, *q = y; + int a = cmp_int64(&p->i, &q->i); + int b = cmp_int64(&p->j, &q->j); + return a ? a : b; +} + +int64_t val(char c) { + if (c >= '0' && c <= '9') return c - '0'; + return c - 'a' + 10; +} + +int64_t removedoubles(int64_t a[], int64_t n) { + int64_t i, j = 0; + for (i = 0; i < n; i++) { + a[j] = a[i]; + if (i+1 < n && a[j] == a[i+1]) + i++; + else + j++; + } + return j; +} + +int64_t overlaplen(int64_t a[], int64_t na, int64_t b[], int64_t nb) { + int64_t ret = 0; + for (int64_t i = 0; 2*i+1 < na; i++) + for (int64_t j = 0; 2*j+1 < nb; j++) + ret += MAX(0, + MIN(a[2*i+1], b[2*j+1]) - MAX(a[2*i], b[2*j]) + 1); + return ret; +} + +int64_t linelen(int64_t a[], int64_t n) { + return overlaplen(a, n, a, n); +} + +int main() { + p[n++] = (point_t) {0}; + while ((buf = fgets(in, 50, stdin)) != NULL) { + while (*buf != '#') buf++; + k = 0; + for (int i = 1; i < 6; i++) + k = 16*k + val(*(buf+i)); + point_t d = go[*(buf+6) - '0']; + p[n] = (point_t){.i = p[n-1].i+d.i*k, .j = p[n-1].j+d.j*k}; + n++; + } + + qsort(p, --n, sizeof(point_t), &cmp_point); + + for (int64_t i = 0, ia = 0; i < n-1; i++) { + a[ia++] = p[i].j; + if (p[i].i != p[i+1].i) { + qsort(a, ia, sizeof(int64_t), &cmp_int64); + ia = removedoubles(a, ia); + t += linelen(a, ia) * (p[i+1].i - p[i].i + 1) - + overlaplen(a, ia, olda, nolda); + nolda = ia; + memcpy(olda, a, nolda * sizeof(int64_t)); + } + } + + printf("%" PRId64 "\n", t); + return 0; +} diff --git a/2023/19/19a.c b/2023/19/19a.c @@ -0,0 +1,87 @@ +#include <inttypes.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define N 1000 + +typedef struct { int64_t val[26]; } part_t; +typedef struct { char v, comp, wnext[10]; int64_t b; } rule_t; +typedef struct { char name[50]; int64_t n; rule_t r[100]; } workflow_t; + +int64_t nw, np, A; +workflow_t w[N]; +part_t p[N]; + +workflow_t readw(char *buf) { + workflow_t ret = {0}; + for (int i = 0; *buf != '{'; buf++, i++) + ret.name[i] = *buf; + for (rule_t r; *buf != '}'; ret.r[ret.n++] = r) { + buf++; + memset(&r, 0, sizeof(r)); + if (*(buf+1) == '<' || *(buf+1) == '>') { + r.v = *buf; + r.comp = *(buf+1); + r.b = atoll(buf+2); + while (*buf != ':') buf++; + buf++; + } + for (int i = 0; *buf != ',' && *buf != '}'; buf++, i++) + r.wnext[i] = *buf; + } + return ret; +} + +part_t readp(char *buf) { + part_t p = {0}; + while (*buf != '}') { + buf++; + p.val[*buf-'a'] = atoll(buf+2); + while(*buf != ',' && *buf != '}') buf++; + } + return p; +} + +int64_t value(part_t p) { + return p.val['x'-'a'] + p.val['m'-'a'] + p.val['a'-'a'] + p.val['s'-'a']; +} + +bool satisfy(part_t p, rule_t r) { + if (r.v == 0) return true; + int64_t val = p.val[r.v-'a']; + return r.comp == '<' ? (val < r.b) : (val > r.b); +} + +workflow_t findw(char *name) { + for (int i = 0; i < nw; i++) + if (!strcmp(name, w[i].name)) + return w[i]; + printf("Error: workflow %s not found\n", name); + exit(1); +} + +int main() { + char *buf, line[N]; + + for (nw = 0; *(buf = fgets(line, N, stdin)) != '\n'; nw++) + w[nw] = readw(buf); + + for (np = 0; (buf = fgets(line, N, stdin)) != NULL; np++) + p[np] = readp(buf); + + for (int i = 0; i < np; i++) { + workflow_t ww = findw("in"); + for (rule_t r; ; ww = findw(r.wnext)) { + for (int64_t j = 0; !satisfy(p[i], r = ww.r[j]); j++) ; + if (!strcmp("A", r.wnext) || !strcmp("R", r.wnext)) { + A += value(p[i]) * (r.wnext[0] == 'A'); + break; + } + } + } + + printf("%" PRId64 "\n", A); + return 0; +} diff --git a/2023/19/19b.c b/2023/19/19b.c @@ -0,0 +1,98 @@ +#include <inttypes.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define N 1000 +#define MAX(x,y) ((x)>(y)?(x):(y)) + +typedef struct { int64_t val[26]; } part_t; +typedef struct { char v, comp, wnext[10]; int64_t b; } rule_t; +typedef struct { char name[50]; int64_t n; rule_t r[100]; } workflow_t; + +int64_t nw, A; +workflow_t w[N]; +part_t p[N]; + +workflow_t readw(char *buf) { + workflow_t ret = {0}; + for (int i = 0; *buf != '{'; buf++, i++) + ret.name[i] = *buf; + for (rule_t r; *buf != '}'; ret.r[ret.n++] = r) { + buf++; + memset(&r, 0, sizeof(r)); + if (*(buf+1) == '<' || *(buf+1) == '>') { + r.v = *buf; + r.comp = *(buf+1); + r.b = atoll(buf+2); + while (*buf != ':') buf++; + buf++; + } + for (int i = 0; *buf != ',' && *buf != '}'; buf++, i++) + r.wnext[i] = *buf; + } + return ret; +} + +workflow_t findw(char *name) { + for (int i = 0; i < nw; i++) + if (!strcmp(name, w[i].name)) + return w[i]; + printf("Error: workflow %s not found\n", name); + exit(1); +} + +int64_t work(workflow_t ww, int64_t lox, int64_t hix, int64_t lom, int64_t him, + int64_t loa, int64_t hia, int64_t los, int64_t his) { + if (lox > hix || lom > him || loa > hia || los > his) + return 0; + + int64_t ret = 0; + for (int j = 0; j < ww.n; j++) { + int64_t lox1 = lox, hix1 = hix, lom1 = lom, him1 = him, + loa1 = loa, hia1 = hia, los1 = los, his1 = his; + rule_t r = ww.r[j]; + switch (r.v) { + case 'x': + if (r.comp == '<') { hix1 = r.b-1; lox = r.b; } + else { lox1 = r.b+1, hix = r.b; } + break; + case 'm': + if (r.comp == '<') { him1 = r.b-1; lom = r.b; } + else { lom1 = r.b+1, him = r.b; } + break; + case 'a': + if (r.comp == '<') { hia1 = r.b-1; loa = r.b; } + else { loa1 = r.b+1, hia = r.b; } + break; + case 's': + if (r.comp == '<') { his1 = r.b-1; los = r.b; } + else { los1 = r.b+1, his = r.b; } + break; + default: + break; + } + ret += (r.wnext[0] == 'A' || r.wnext[0] == 'R') ? + MAX(0, hix1-lox1+1) * MAX(0, him1-lom1+1) * + MAX(0, hia1-loa1+1) * MAX(0, his1-los1+1) * + (r.wnext[0] == 'A') + : + work(findw(r.wnext), lox1, hix1, + lom1, him1, loa1, hia1, los1, his1); + } + + return ret; +} + +int main() { + char *buf, line[N]; + + for (nw = 0; *(buf = fgets(line, N, stdin)) != '\n'; nw++) + w[nw] = readw(buf); + + int64_t s = work(findw("in"), 1, 4000, 1, 4000, 1, 4000, 1, 4000); + + printf("%" PRId64 "\n", s); + return 0; +}