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

9 files changed, 581 insertions, 0 deletions

diff --git a/2023/15/15a.c b/2023/15/15a.c
new file mode 100644
index 0000000..16a8fec
--- /dev/null
+++ 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
new file mode 100644
index 0000000..15b97f9
--- /dev/null
+++ 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
new file mode 100644
index 0000000..0f95553
--- /dev/null
+++ 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
new file mode 100644
index 0000000..ce42c31
--- /dev/null
+++ 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
new file mode 100644
index 0000000..0b02f45
--- /dev/null
+++ 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
new file mode 100644
index 0000000..10fad81
--- /dev/null
+++ 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
new file mode 100644
index 0000000..d79d4cb
--- /dev/null
+++ 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
new file mode 100644
index 0000000..81ee535
--- /dev/null
+++ 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
new file mode 100644
index 0000000..c7cecb6
--- /dev/null
+++ 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;
+}