From baf4910870a6e8999802b9a4a22eabd4142a34e3 Mon Sep 17 00:00:00 2001 From: Bond_009 Date: Thu, 1 Dec 2022 22:30:22 +0100 Subject: Move all Advent of Codes into one repo --- 2020/05/part1.c | 82 ++++++++++++++++++++++++++++++++++++++++ 2020/05/part2.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++ 2020/05/part2_fast.c | 90 ++++++++++++++++++++++++++++++++++++++++++++ 2020/05/seat_id.asm | 25 +++++++++++++ 2020/05/seat_id_ssse3.asm | 23 ++++++++++++ 5 files changed, 315 insertions(+) create mode 100644 2020/05/part1.c create mode 100644 2020/05/part2.c create mode 100644 2020/05/part2_fast.c create mode 100644 2020/05/seat_id.asm create mode 100644 2020/05/seat_id_ssse3.asm (limited to '2020/05') 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 + +#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 + +#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 + +#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 -- cgit v1.2.3