Move all Advent of Codes into one repo

5 files changed, 315 insertions, 0 deletions

diff --git a/2020/05/part1.c b/2020/05/part1.c
new file mode 100644
index 0000000..ca726b7
--- /dev/null
+++ b/2020/05/part1.c
@@ -0,0 +1,82 @@
+#include <stdio.h>
+
+#define COLUMNS 8
+#define ROWS 128
+
+int seat_id(const char *seat)
+{
+    int row = 0;
+    int row_lower = 0;
+    int row_upper = ROWS - 1;
+    int column = 0;
+    int column_lower = 0;
+    int column_upper = COLUMNS - 1;
+    int i = 0;
+    for (; i < 6; i++) {
+        switch (seat[i]) {
+            case 'F':
+                row_upper -= (row_upper - row_lower + 1) / 2;
+                break;
+            case 'B':
+                row_lower += (row_upper - row_lower + 1) / 2;
+                break;
+        }
+    }
+
+    switch (seat[i++]) {
+        case 'F':
+            row = row_lower;
+            break;
+        case 'B':
+            row = row_upper;
+            break;
+    }
+
+    for (; i < 9; i++) {
+        switch (seat[i]) {
+            case 'L':
+                column_upper -= (column_upper - column_lower + 1) / 2;
+                break;
+            case 'R':
+                column_lower += (column_upper - column_lower + 1) / 2;
+                break;
+        }
+    }
+
+    switch (seat[i++]) {
+        case 'L':
+            column = column_lower;
+            break;
+        case 'R':
+            column = column_upper;
+            break;
+    }
+
+    return row * COLUMNS + column;
+}
+
+int highest_seat_id(const char *filename)
+{
+    FILE *file = fopen(filename, "r");
+
+    // Include space for newline and string terminator
+    char buffer[16] = { 0 };
+
+    int max = 0;
+
+    while (fgets(buffer, 16, file)) {
+        int tmp = seat_id(buffer);
+        if (tmp > max) {
+            max = tmp;
+        }
+    }
+
+    fclose(file);
+
+    return max;
+}
+
+int main(int argc, char *argv[])
+{
+    printf("%i\n", highest_seat_id(argv[argc - 1]));
+}
diff --git a/2020/05/part2.c b/2020/05/part2.c
new file mode 100644
index 0000000..396ea76
--- /dev/null
+++ b/2020/05/part2.c
@@ -0,0 +1,95 @@
+#include <stdio.h>
+
+#define COLUMNS 8
+#define ROWS 128
+
+int seat_id(const char *seat)
+{
+    int row = 0;
+    int row_lower = 0;
+    int row_upper = ROWS - 1;
+    int column = 0;
+    int column_lower = 0;
+    int column_upper = COLUMNS - 1;
+    int i = 0;
+    for (; i < 6; i++) {
+        switch (seat[i]) {
+            case 'F':
+                row_upper -= (row_upper - row_lower + 1) / 2;
+                break;
+            case 'B':
+                row_lower += (row_upper - row_lower + 1) / 2;
+                break;
+        }
+    }
+
+    switch (seat[i++]) {
+        case 'F':
+            row = row_lower;
+            break;
+        case 'B':
+            row = row_upper;
+            break;
+    }
+
+    for (; i < 9; i++) {
+        switch (seat[i]) {
+            case 'L':
+                column_upper -= (column_upper - column_lower + 1) / 2;
+                break;
+            case 'R':
+                column_lower += (column_upper - column_lower + 1) / 2;
+                break;
+        }
+    }
+
+    switch (seat[i++]) {
+        case 'L':
+            column = column_lower;
+            break;
+        case 'R':
+            column = column_upper;
+            break;
+    }
+
+    return row * COLUMNS + column;
+}
+
+int missing_seat_id(const char *filename)
+{
+    FILE *file = fopen(filename, "r");
+
+    char table[COLUMNS * ROWS] = { 0 };
+
+    // Include space for newline and string terminator
+    char buffer[16] = { 0 };
+
+    int min = __INT_MAX__;
+    int max = 0;
+    while (fgets(buffer, 16, file)) {
+        int tmp = seat_id(buffer);
+        if (tmp < min) {
+            min = tmp;
+        }
+        else if (tmp > max) {
+            max = tmp;
+        }
+
+        table[tmp] = 1;
+    }
+
+    fclose(file);
+
+    for (int i = min + 1; i < max; i++) {
+        if (table[i] == 0) {
+            return i;
+        }
+    }
+
+    return 0;
+}
+
+int main(int argc, char *argv[])
+{
+    printf("%i", missing_seat_id(argv[argc - 1]));
+}
diff --git a/2020/05/part2_fast.c b/2020/05/part2_fast.c
new file mode 100644
index 0000000..483dd8f
--- /dev/null
+++ b/2020/05/part2_fast.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+
+#define COLUMNS 8
+#define ROWS 128
+
+int row(const char *seat)
+{
+    int end_res = 0;
+    for (int i = 0; i < 7; i++) {
+        if (seat[i] == 'B') {
+            end_res |= 0x40 >> i;
+        }
+    }
+
+    return end_res;
+}
+
+int column(const char *seat)
+{
+    int end_res = 0;
+    for (int i = 7; i < 10; i++) {
+        if (seat[i] == 'R') {
+            end_res |= 0x200 >> i;
+        }
+    }
+
+    return end_res;
+}
+
+#ifdef USE_ASM
+int seat_id(const char *seat);
+#else
+int seat_id(const char *seat)
+{
+    int end_res = 0;
+    int i = 0;
+    for (; i < 7; i++) {
+        if (seat[i] == 'B') {
+            end_res |= 0x200 >> i;
+        }
+    }
+
+    for (; i < 10; i++) {
+        if (seat[i] == 'R') {
+            end_res |= 0x200 >> i;
+        }
+    }
+
+    return end_res;
+}
+#endif
+
+int missing_seat_id(const char *filename)
+{
+    FILE *file = fopen(filename, "r");
+
+    char table[COLUMNS * ROWS] = { 0 };
+
+    // Include space for newline and string terminator
+    char buffer[16] = { 0 };
+
+    int min = __INT_MAX__;
+    int max = 0;
+    while (fgets(buffer, 16, file)) {
+        int tmp = seat_id(buffer);
+        if (tmp < min) {
+            min = tmp;
+        }
+        else if (tmp > max) {
+            max = tmp;
+        }
+
+        table[tmp] = 1;
+    }
+
+    for (int i = min + 1; i < max; i++) {
+        if (table[i] == 0) {
+            return i;
+        }
+    }
+
+    fclose(file);
+
+    return 0;
+}
+
+int main(int argc, char *argv[])
+{
+    printf("%i", missing_seat_id(argv[argc - 1]));
+}
diff --git a/2020/05/seat_id.asm b/2020/05/seat_id.asm
new file mode 100644
index 0000000..a372a9a
--- /dev/null
+++ b/2020/05/seat_id.asm
@@ -0,0 +1,25 @@
+global seat_id
+
+section .text
+
+seat_id:
+    xor         eax, eax            ; set up return value
+    cmp         BYTE [rdi], 'B'
+    sete        al
+    xor         ecx, ecx
+%assign i 1
+%rep    6
+    shl         eax, 1
+    cmp         BYTE [rdi + i], 'B'
+    sete        cl
+    or          eax, ecx
+%assign i i+1
+%endrep
+%rep    3
+    shl         eax, 1
+    cmp         BYTE [rdi + i], 'R'
+    sete        cl
+    or          eax, ecx
+%assign i i+1
+%endrep
+    ret
diff --git a/2020/05/seat_id_ssse3.asm b/2020/05/seat_id_ssse3.asm
new file mode 100644
index 0000000..4d51cbe
--- /dev/null
+++ b/2020/05/seat_id_ssse3.asm
@@ -0,0 +1,23 @@
+global seat_id
+
+section .rodata
+    align 16
+    xmm_shuf:   db 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 10, 11, 12, 13, 14, 15
+    xmm_cmp:    db 1, 'RBBBBBBB', 1, 1, 1, 1, 1, 1, 1
+
+section .text
+
+seat_id:
+    movq        xmm0, qword [rdi]       ; load first 8 bytes
+    pshufb      xmm0, [rel xmm_shuf]    ; reverse byte order and already shift left once
+    pcmpeqb     xmm0, [rel xmm_cmp]
+    pmovmskb    eax, xmm0               ; store mask in return value
+    xor         ecx, ecx
+    cmp         byte [rdi + 8], 'R'
+    sete        cl
+    or          eax, ecx
+    shl         eax, 1
+    cmp         byte [rdi + 9], 'R'
+    sete        cl
+    or          eax, ecx
+    ret