diff options
Diffstat (limited to '2020')
37 files changed, 2550 insertions, 0 deletions
diff --git a/2020/01/part1.c b/2020/01/part1.c new file mode 100644 index 0000000..1b825df --- /dev/null +++ b/2020/01/part1.c @@ -0,0 +1,38 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define INPUT_LEN 200 + +int repair(const int * arr) +{ + for (int i = 0; i < INPUT_LEN; i++) { + for (int j = 0; j < INPUT_LEN; j++) { + if (arr[i] + arr[j] == 2020) { + return arr[i] * arr[j]; + } + } + } + + return 0; +} + +int main(int argc, char *argv[]) +{ + FILE *file = fopen(argv[argc - 1], "r"); + if (!file) { + return 1; + } + + char buffer[8] = { 0 }; + int input[INPUT_LEN] = { 0 }; + for (int i = 0; i < 200; i++) { + fgets(buffer, 8, file); + input[i] = atoi(buffer); + } + + fclose(file); + + printf("%i", repair(input)); +} diff --git a/2020/01/part1.f90 b/2020/01/part1.f90 new file mode 100644 index 0000000..a7c09c8 --- /dev/null +++ b/2020/01/part1.f90 @@ -0,0 +1,25 @@ +program day1 + implicit none + + integer, parameter :: input_len = 200 + integer, parameter :: search = 2020 + + integer :: i, j + integer, dimension(input_len) :: input + + open(10, file='input', status='old') + do i = 1, input_len + read(10, *) input(i) + end do + close(10) + + do i = 1, input_len + do j = 1, input_len + if (input(i) + input(j) == search) then + print *, input(i) * input(j) + stop + end if + end do + end do + +end program day1 diff --git a/2020/01/part2.c b/2020/01/part2.c new file mode 100644 index 0000000..9c10b61 --- /dev/null +++ b/2020/01/part2.c @@ -0,0 +1,40 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define INPUT_LEN 200 + +int repair(const int *arr) +{ + for (int i = 0; i < INPUT_LEN; i++) { + for (int j = 0; j < INPUT_LEN; j++) { + for (int k = 0; k < INPUT_LEN; k++) { + if (arr[i] + arr[j] + arr[k] == 2020) { + return arr[i] * arr[j] * arr[k]; + } + } + } + } + + return 0; +} + +int main(int argc, char *argv[]) +{ + FILE *file = fopen(argv[argc - 1], "r"); + if (!file) { + return 1; + } + + char buffer[8] = { 0 }; + int input[INPUT_LEN] = { 0 }; + for (int i = 0; i < 200; i++) { + fgets(buffer, 8, file); + input[i] = atoi(buffer); + } + + fclose(file); + + printf("%i", repair(input)); +} diff --git a/2020/01/part2.f90 b/2020/01/part2.f90 new file mode 100644 index 0000000..b3d6bd2 --- /dev/null +++ b/2020/01/part2.f90 @@ -0,0 +1,27 @@ +program day1 + implicit none + + integer, parameter :: input_len = 200 + integer, parameter :: search = 2020 + + integer :: i, j, k + integer, dimension(input_len) :: input + + open(10, file='input', status='old') + do i = 1, input_len + read(10, *) input(i) + end do + close(10) + + do i = 1, input_len + do j = 1, input_len + do k = 1, input_len + if (input(i) + input(j) + input(k) == search) then + print *, input(i) * input(j) * input(k) + stop + end if + end do + end do + end do + +end program day1 diff --git a/2020/01/part2_fast.c b/2020/01/part2_fast.c new file mode 100644 index 0000000..c32f881 --- /dev/null +++ b/2020/01/part2_fast.c @@ -0,0 +1,127 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <immintrin.h> + +#define INPUT_LEN 200 +#define SEARCH 2020 + +#ifdef USE_ASM +int repair_avx_inner(const int *arr, __m256i search); +#else +int repair_avx_inner(const int *arr, __m256i search) +{ + for (int k = 0; k < INPUT_LEN; k += 8) { + __m256i new = _mm256_loadu_si256((__m256i *)(&arr[k])); + if (_mm256_movemask_epi8(_mm256_cmpeq_epi32(new, search))) { + return _mm256_extract_epi32(search, 0); + } + } + + return 0; +} +#endif + +int repair_avx(const int *arr) +{ + __m256i search = _mm256_set1_epi32(SEARCH); + for (int i = 0; i < INPUT_LEN; i++) { + __m256i start = _mm256_set1_epi32(arr[i]); + for (int j = 0; j < INPUT_LEN; j += 8) { + __m256i new = _mm256_loadu_si256((__m256i *)(&arr[j])); + new = _mm256_add_epi32(start, new); + unsigned int mask = (unsigned int)_mm256_movemask_epi8(_mm256_cmpgt_epi32(new, search)); + if (mask == 0xffffffff) { + continue; + } + + switch (__lzcnt32(mask) / 4) { + case 0: + { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(7))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 7]; + } + } + case 1: + if ((mask & 0x0f000000) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(6))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 6]; + } + } + case 2: + if ((mask & 0x00f00000) == 0 ){ + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(5))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 5]; + } + } + case 3: + if ((mask & 0x000f0000) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(4))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 4]; + } + } + case 4: + if ((mask & 0x0000f000) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(3))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 3]; + } + } + case 5: + if ((mask & 0x00000f00) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(2))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 2]; + } + } + case 6: + if ((mask & 0x000000f0) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_set1_epi32(1))); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j + 1]; + } + } + case 7: + if ((mask & 0x0000000f) == 0) { + __m256i cmp = _mm256_sub_epi32(search, _mm256_permutevar8x32_epi32(new, _mm256_setzero_si256())); + int tmp = repair_avx_inner(arr, cmp); + if (tmp) { + return tmp * arr[i] * arr[j]; + } + } + } + } + } + + return 0; +} + +int main(int argc, char *argv[]) +{ + FILE *file = fopen(argv[argc - 1], "r"); + if (!file) { + return 1; + } + + char buffer[8] = { 0 }; + int input[INPUT_LEN] = { 0 }; + for (int i = 0; i < 200; i++) { + fgets(buffer, 8, file); + input[i] = atoi(buffer); + } + + fclose(file); + + printf("%i\n", repair_avx(input)); +} diff --git a/2020/01/repair_avx.asm b/2020/01/repair_avx.asm new file mode 100644 index 0000000..4f128f6 --- /dev/null +++ b/2020/01/repair_avx.asm @@ -0,0 +1,21 @@ +global repair_avx_inner + +section .text + +repair_avx_inner: +%assign i 0 +%rep 25 + vpcmpeqd ymm1, ymm0, [rdi + i] +; vptest ymm1, ymm1 ; slower then vpmovmskb + test + vpmovmskb eax, ymm1 + test eax, eax + jne .found +%assign i i+32 +%endrep + xor eax, eax ; not found, return 0 + vzeroupper ; eliminate performance penalties caused by false dependencies when transitioning between AVX and legacy SSE instructions + ret +.found: + vzeroupper ; eliminate performance penalties caused by false dependencies when transitioning between AVX and legacy SSE instructions + movd eax, xmm0 ; smaller then putting a vmovd before the vzeroupper and no measurable performance difference + ret diff --git a/2020/02/part1.c b/2020/02/part1.c new file mode 100644 index 0000000..11d955b --- /dev/null +++ b/2020/02/part1.c @@ -0,0 +1,41 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +bool is_valid_password(char *pass, char *policy) +{ + int min = atoi(policy); + char *minP = strchr(policy, '-'); + int max = atoi(++minP); + char c = *(strchr(minP, ' ') + 1); + char *p = pass; + int occ = 0; + do { + if (*p == c) { + occ++; + } + } while (*++p); + + return occ >= min && occ <= max; +} + +int main(int argc, char *argv[]) +{ + FILE *file = fopen(argv[argc - 1], "r"); + if (!file) { + return 1; + } + + char buffer[128] = { 0 }; + int valid = 0; + while (fgets(buffer, 128, file)) { + if (is_valid_password(strchr(buffer, ':') + 2, buffer)) { + valid++; + } + } + + fclose(file); + + printf("%i", valid); +} diff --git a/2020/02/part2.c b/2020/02/part2.c new file mode 100644 index 0000000..7a2e16e --- /dev/null +++ b/2020/02/part2.c @@ -0,0 +1,34 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +bool is_valid_password(char *pass, char *policy) +{ + int pos1 = atoi(policy) - 1; + char *minP = strchr(policy, '-'); + int pos2 = atoi(++minP) - 1; + char c = *(strchr(minP, ' ') + 1); + + return (pass[pos1] == c) != (pass[pos2] == c); +} + +int main(int argc, char *argv[]) +{ + FILE *file = fopen(argv[argc - 1], "r"); + if (!file) { + return 1; + } + + char buffer[128] = { 0 }; + int valid = 0; + while (fgets(buffer, 128, file)) { + if (is_valid_password(strchr(buffer, ':') + 2, buffer)) { + valid++; + } + } + + fclose(file); + + printf("%i", valid); +} diff --git a/2020/03/part1.c b/2020/03/part1.c new file mode 100644 index 0000000..b664b7d --- /dev/null +++ b/2020/03/part1.c @@ -0,0 +1,37 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define INC_RIGHT 3 + +int count_trees(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[64] = { 0 }; + // Start is always safe + fgets(buffer, 64, file); + // strlen includes the newline + int width = strchr(buffer, '\n') - buffer; + + int pos = INC_RIGHT; + int hit = 0; + while (fgets(buffer, 64, file)) { + if (buffer[pos] == '#') { + hit++; + } + + pos = (pos + INC_RIGHT) % width; + } + + fclose(file); + + return hit; +} + +int main(int argc, char *argv[]) +{ + printf("%i", count_trees(argv[argc - 1])); +} diff --git a/2020/03/part2.c b/2020/03/part2.c new file mode 100644 index 0000000..bae8654 --- /dev/null +++ b/2020/03/part2.c @@ -0,0 +1,41 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int count_trees(int inc_right, int inc_down, const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[64] = { 0 }; + // Start is always safe + fgets(buffer, 64, file); + // strlen includes the newline + int width = strchr(buffer, '\n') - buffer; + + int pos = inc_right; + int hit = 0; + for (int i = 1; fgets(buffer, 64, file); i++) { + if (inc_down != 1 && i % inc_down != 0) { + continue; + } + + if (buffer[pos] == '#') { + hit++; + } + + pos = (pos + inc_right) % width; + } + + fclose(file); + + return hit; +} + +int main(int argc, char *argv[]) +{ + char *arg = argv[argc - 1]; + long mul = (long)count_trees(1, 1, arg) * count_trees(3, 1, arg) * count_trees(5, 1, arg) * count_trees(7, 1, arg) * count_trees(1, 2, arg); + printf("%li\n", mul); +} diff --git a/2020/04/part1.c b/2020/04/part1.c new file mode 100644 index 0000000..b4a3b8e --- /dev/null +++ b/2020/04/part1.c @@ -0,0 +1,68 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +bool is_valid_passport(const char *pass) +{ + return strstr(pass, "byr:") + && strstr(pass, "iyr:") + && strstr(pass, "eyr:") + && strstr(pass, "hgt:") + && strstr(pass, "hcl:") + && strstr(pass, "ecl:") + && strstr(pass, "pid:"); +} + +int count_valid_passports(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + bool has_byr = false; + bool has_iyr = false; + bool has_eyr = false; + bool has_hgt = false; + bool has_hcl = false; + bool has_ecl = false; + bool has_pid = false; + int correct = 0; + while (fgets(buffer, 128, file)) { + if (buffer[0] == '\n') { + if (has_byr && has_iyr && has_eyr && has_hgt && has_hcl && has_ecl && has_pid) { + correct++; + } + + has_byr = false; + has_iyr = false; + has_eyr = false; + has_hgt = false; + has_hcl = false; + has_ecl = false; + has_pid = false; + } + + has_byr = has_byr || strstr(buffer, "byr:"); + has_iyr = has_iyr || strstr(buffer, "iyr:"); + has_eyr = has_eyr || strstr(buffer, "eyr:"); + has_hgt = has_hgt || strstr(buffer, "hgt:"); + has_hcl = has_hcl || strstr(buffer, "hcl:"); + has_ecl = has_ecl || strstr(buffer, "ecl:"); + has_pid = has_pid || strstr(buffer, "pid:"); + } + + if (has_byr && has_iyr && has_eyr && has_hgt && has_hcl && has_ecl && has_pid) { + correct++; + } + + fclose(file); + + return correct; +} + +int main(int argc, char *argv[]) +{ + printf("%i", count_valid_passports(argv[argc - 1])); +} diff --git a/2020/04/part2.c b/2020/04/part2.c new file mode 100644 index 0000000..5aac219 --- /dev/null +++ b/2020/04/part2.c @@ -0,0 +1,135 @@ +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define KEYS_LEN 7 +const char* const keys[] = { "byr:", "iyr:", "eyr:", "hgt:", "hcl:", "ecl:", "pid:" }; + +bool is_valid_field(const char *key, const char *value) +{ + if (strncmp(key, "byr", 3) == 0) { + int v = atoi(value); + return v >= 1920 && v <= 2002; + } + + if (strncmp(key, "iyr", 3) == 0) { + int v = atoi(value); + return v >= 2010 && v <= 2020; + } + + if (strncmp(key, "eyr", 3) == 0) { + int v = atoi(value); + return v >= 2020 && v <= 2030; + } + + if (strncmp(key, "hgt", 3) == 0) { + int v = atoi(value); + if (strncmp(value + 3, "cm", 2) == 0) { + return v >= 150 && v <= 193; + } + + if (strncmp(value + 2, "in", 2) == 0) { + return v >= 59 && v <= 76; + } + + return false; + } + + if (strncmp(key, "hcl", 3) == 0) { + if (value[0] != '#') { + return false; + } + + for (int i = 1; i < 7; i++) { + if (!(value[i] >= 48 && value[i] <= 57) && !(value[i] >= 97 && value[i] <= 102)) { + return false; + } + } + + return true; + } + + if (strncmp(key, "ecl", 3) == 0) { + return strncmp(value, "amb", 3) == 0 + || strncmp(value, "blu", 3) == 0 + || strncmp(value, "brn", 3) == 0 + || strncmp(value, "gry", 3) == 0 + || strncmp(value, "grn", 3) == 0 + || strncmp(value, "hzl", 3) == 0 + || strncmp(value, "oth", 3) == 0; + } + + if (strncmp(key, "pid", 3) == 0) { + for (int i = 0; i < 9; i++) { + if (!(value[i] >= 48 && value[i] <= 57)) { + return false; + } + } + + return !(value[9] >= 48 && value[9] <= 57); + } + + return false; +} + +bool is_valid_passport(const char *pass) +{ + for (int i = 0; i < KEYS_LEN; i++) { + const char *p = strstr(pass, keys[i]); + if (!p) { + return false; + } + + if (!is_valid_field(p, p + 4)) { + return false; + } + } + + return true; +} + +int count_valid_passports(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + uint8_t values = 0; + int correct = 0; + while (fgets(buffer, 128, file)) { + if (buffer[0] == '\n') { + if (values == 0x7f) { + correct++; + } + + values = 0; + } + + for (int i = 0; i < KEYS_LEN; i++) { + const char *p = strstr(buffer, keys[i]); + if (!p) { + continue; + } + + if (is_valid_field(p, p + 4)) { + values = values | (0x1 << i); + } + } + } + + if (values == 0x7f) { + correct++; + } + + fclose(file); + + return correct; +} + +int main(int argc, char *argv[]) +{ + printf("%i", count_valid_passports(argv[argc - 1])); +} 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 diff --git a/2020/06/part1.c b/2020/06/part1.c new file mode 100644 index 0000000..1b38192 --- /dev/null +++ b/2020/06/part1.c @@ -0,0 +1,37 @@ +#include <stdio.h> + +int plane_count(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[32] = { 0 }; + + int tot = 0; + unsigned int current = 0; + + while (fgets(buffer, 32, file)) { + if (buffer[0] == '\n') { + tot += __builtin_popcount(current); + current = 0; + + continue; + } + + char *p = buffer; + do { + current |= 1 << (*p - 97); + } while (*++p != '\n'); + } + + tot += __builtin_popcount(current); + + fclose(file); + + return tot; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", plane_count(argv[argc - 1])); +} diff --git a/2020/06/part2.c b/2020/06/part2.c new file mode 100644 index 0000000..11c8469 --- /dev/null +++ b/2020/06/part2.c @@ -0,0 +1,44 @@ +#include <stdio.h> + +int plane_count(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[32] = { 0 }; + + int tot = 0; + unsigned int current = 0xffffffff; + + while (fgets(buffer, 32, file)) { + if (buffer[0] == '\n') { + if (current != 0xffffffff) { + tot += __builtin_popcount(current); + current = 0xffffffff; + } + + continue; + } + + unsigned int tmp = 0; + char *p = buffer; + do { + tmp |= 1 << (*p - 97); + } while (*++p != '\n'); + + current &= tmp; + } + + fclose(file); + + if (current != 0xffffffff) { + tot += __builtin_popcount(current); + } + + return tot; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", plane_count(argv[argc - 1])); +} diff --git a/2020/07/part1.c b/2020/07/part1.c new file mode 100644 index 0000000..7e04278 --- /dev/null +++ b/2020/07/part1.c @@ -0,0 +1,158 @@ +#include <stdio.h> +#include <stdint.h> +#include <malloc.h> +#include <string.h> + +#define SEARCH_NAME "shiny gold" +#define MAX_NAMES 1024 +#define MAX_SIZE 600 +#define MAX_INNER_BAGS 4 + +struct Bag +{ + size_t inner_bags_size; + char *inner_bags[MAX_INNER_BAGS]; + char *bag_color; +}; + +char *insert_name(char **names, size_t *names_size, char *new_name) +{ + long long low = 0, high = *names_size; + while (low < high) { + int m = low + (high - low) / 2; + int c = strcmp(names[m], new_name); + if (c == 0) { + /* Name already exists, + return pointer to the already existsing string and free the new one. + */ + free(new_name); + return names[m]; + } + else if (c < 0) { + low = m + 1; + } + else { + high = m; + } + } + + for (long long i = *names_size - 1; i >= low; i--) { + names[i + 1] = names[i]; + } + + (*names_size)++; + return names[low] = new_name; +} + +void insert_name2(char **names, size_t *names_size, char *new_name) +{ + long long low = 0, high = *names_size; + while (low < high) { + int m = low + (high - low) / 2; + int c = strcmp(names[m], new_name); + if (c == 0) { + return; + } + else if (c < 0) { + low = m + 1; + } + else { + high = m; + } + } + + for (long long i = *names_size - 1; i >= low; i--) { + names[i + 1] = names[i]; + } + + (*names_size)++; + names[low] = new_name; + return; +} + +char *get_and_insert_name(char *bufstart, char *bufend, char **names, size_t *names_size) +{ + size_t bag_name_len = bufend - bufstart; + char *new_name = malloc((bag_name_len + 1) * sizeof(char)); + memcpy(new_name, bufstart, bag_name_len); + new_name[bag_name_len] = 0; // null terminate string + return insert_name(names, names_size, new_name); +} + +int bags_count(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + struct Bag *bags = malloc(MAX_SIZE * sizeof(struct Bag)); + struct Bag *cur_bag = bags; + char **names = malloc(MAX_NAMES * sizeof(char *)); + + // Already add the name we're searching + char *search_name = names[0] = SEARCH_NAME; + size_t names_size = 1; + + while (fgets(buffer, 128, file)) { + char *end_bag_name = strstr(buffer, " bags"); + if (!end_bag_name) { + break; + } + + char* new_name = get_and_insert_name(buffer, end_bag_name, names, &names_size); + + cur_bag++; + cur_bag->bag_color = new_name; + if (strncmp(end_bag_name, " bags contain no", 16) == 0) { + cur_bag->inner_bags_size = 0; + continue; + } + + char *string_end = strchr(end_bag_name, '.'); + char *start_bag_name = end_bag_name + 16; + while ((end_bag_name = strstr(start_bag_name, " bag"))) { + new_name = get_and_insert_name(start_bag_name, end_bag_name, names, &names_size); + cur_bag->inner_bags[cur_bag->inner_bags_size++] = new_name; + start_bag_name = end_bag_name + (strncmp(end_bag_name, " bags", 5) ? 8 : 9); + if (start_bag_name > string_end) { + // We're outside the buffer, stop + break; + } + } + } + + fclose(file); + + char **outer_bags = malloc(MAX_SIZE * sizeof(char *)); + + // Start search with SEARCH_NAME + outer_bags[0] = search_name; + size_t outer_bags_size = 1; + + size_t old_size = 0; + while (old_size != outer_bags_size) { + old_size = outer_bags_size; + for (size_t i = 0; i < outer_bags_size; i++) { + struct Bag *p = bags; + while (p <= cur_bag) { + for (size_t j = 0; j < p->inner_bags_size; j++) { + if (p->inner_bags[j] == outer_bags[i]) { + insert_name2(outer_bags, &outer_bags_size, p->bag_color); + break; + } + } + + p++; + } + } + } + + // Don't count SEARCH_NAME + return outer_bags_size - 1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", bags_count(argv[argc - 1])); +} diff --git a/2020/07/part2.c b/2020/07/part2.c new file mode 100644 index 0000000..f4214f5 --- /dev/null +++ b/2020/07/part2.c @@ -0,0 +1,129 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#define SEARCH_NAME "shiny gold" +#define MAX_NAMES 1024 +#define MAX_SIZE 600 +#define MAX_INNER_BAGS 4 + +struct Bag +{ + size_t inner_bags_size; + char *inner_bags[MAX_INNER_BAGS]; + int inner_bags_count[MAX_INNER_BAGS]; + char *bag_color; +}; + +char *insert_name(char **names, size_t *names_size, char *new_name) +{ + long long low = 0, high = *names_size; + while (low < high) { + int m = low + (high - low) / 2; + int c = strcmp(names[m], new_name); + if (c == 0) { + /* Name already exists, + return pointer to the already existsing string and free the new one. + */ + free(new_name); + return names[m]; + } + else if (c < 0) { + low = m + 1; + } + else { + high = m; + } + } + + for (long long i = *names_size - 1; i >= low; i--) { + names[i + 1] = names[i]; + } + + (*names_size)++; + return names[low] = new_name; +} + +char *get_and_insert_name(char *bufstart, char *bufend, char **names, size_t *names_size) +{ + size_t bag_name_len = bufend - bufstart; + char *new_name = malloc((bag_name_len + 1) * sizeof(char)); + memcpy(new_name, bufstart, bag_name_len); + new_name[bag_name_len] = 0; // null terminate string + return insert_name(names, names_size, new_name); +} + +size_t get_num_bags(struct Bag *bags, size_t bags_size, char *bag_color) +{ + for (size_t i = 0; i < bags_size; i++) { + if (bags[i].bag_color == bag_color) { + struct Bag bag = bags[i]; + size_t total = 1; + for (size_t j = 0; j < bag.inner_bags_size; j++) { + total += get_num_bags(bags, bags_size, bag.inner_bags[j]) * bag.inner_bags_count[j]; + } + + return total; + } + } + + return 0; +} + +int bags_count(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + struct Bag *bags = malloc(MAX_SIZE * sizeof(struct Bag)); + struct Bag *cur_bag = bags; + char **names = malloc(MAX_NAMES * sizeof(char *)); + + // Already add the name we're searching + char *search_name = names[0] = SEARCH_NAME; + size_t names_size = 1; + + while (fgets(buffer, 128, file)) { + char *end_bag_name = strstr(buffer, " bags"); + if (!end_bag_name) { + break; + } + + char* new_name = get_and_insert_name(buffer, end_bag_name, names, &names_size); + + cur_bag++; + cur_bag->bag_color = new_name; + if (strncmp(end_bag_name, " bags contain no", 16) == 0) { + cur_bag->inner_bags_size = 0; + continue; + } + + char *string_end = strchr(end_bag_name, '.'); + char *start_bag_name = end_bag_name + 14; + while ((end_bag_name = strstr(start_bag_name, " bag"))) { + int num_bags = atoi(start_bag_name); + start_bag_name += 2; + new_name = get_and_insert_name(start_bag_name, end_bag_name, names, &names_size); + cur_bag->inner_bags[cur_bag->inner_bags_size] = new_name; + cur_bag->inner_bags_count[cur_bag->inner_bags_size++] = num_bags; + start_bag_name = end_bag_name + (strncmp(end_bag_name, " bags", 5) ? 6 : 7); + if (start_bag_name > string_end) { + // We're outside the buffer, stop + break; + } + } + } + + fclose(file); + + return get_num_bags(bags, cur_bag - bags + 1, search_name) - 1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", bags_count(argv[argc - 1])); +} diff --git a/2020/08/part1.c b/2020/08/part1.c new file mode 100644 index 0000000..d4261be --- /dev/null +++ b/2020/08/part1.c @@ -0,0 +1,74 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +#define INPUT_LEN 650 + +struct Operation +{ + char opcode; + int arg; + char has_been_executed; +}; + +int exe_program(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[16] = { 0 }; + + struct Operation ops[INPUT_LEN]; + size_t opcount = 0; + + while (fgets(buffer, 16, file)) { + struct Operation *op = &ops[opcount++]; + op->has_been_executed = 0; + switch (buffer[0]) + { + // nop + case 'n': + op->opcode = 0; + break; + // acc + case 'a': + op->opcode = 1; + break; + // jmp + case 'j': + op->opcode = 2; + break; + } + + op->arg = atoi(&buffer[4]); + } + + fclose(file); + + struct Operation *cur_op = ops; + int acc = 0; + while (!cur_op->has_been_executed) + { + cur_op->has_been_executed = 1; + switch (cur_op->opcode) + { + case 0: + cur_op++; + break; + case 1: + acc += cur_op->arg; + cur_op++; + break; + case 2: + cur_op += cur_op->arg; + break; + } + } + + return acc; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", exe_program(argv[argc - 1])); +} diff --git a/2020/08/part2.c b/2020/08/part2.c new file mode 100644 index 0000000..44ebdec --- /dev/null +++ b/2020/08/part2.c @@ -0,0 +1,109 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +#define INPUT_LEN 650 + +struct Operation +{ + char opcode; + int arg; + char has_been_executed; +}; + +int execute(struct Operation *ops, size_t opcount) +{ + struct Operation *cur_op = ops; + int acc = 0; + do { + if (cur_op->has_been_executed) { + return -1; + } + + cur_op->has_been_executed = 1; + switch (cur_op->opcode) + { + case 0: + cur_op++; + break; + case 1: + acc += cur_op->arg; + cur_op++; + break; + case 2: + cur_op += cur_op->arg; + break; + } + } while (cur_op < ops + opcount); + + return acc; +} + +int exe_program(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[16] = { 0 }; + + struct Operation ops[INPUT_LEN]; + size_t opcount = 0; + + while (fgets(buffer, 16, file)) { + struct Operation *op = &ops[opcount++]; + op->has_been_executed = 0; + switch (buffer[0]) + { + // nop + case 'n': + op->opcode = 0; + break; + // acc + case 'a': + op->opcode = 1; + break; + // jmp + case 'j': + op->opcode = 2; + break; + } + + op->arg = atoi(&buffer[4]); + } + + fclose(file); + + struct Operation *cur_op = ops; + int flip_previous = 0; + do { + if (flip_previous) { + (cur_op - 1)->opcode ^= 2; + flip_previous = 0; + } + + if (cur_op->opcode == 1 + || (cur_op->opcode == 0 && cur_op->arg <= 0) + || (cur_op->opcode == 2 && cur_op->arg >= 0)) { + continue; + } + + cur_op->opcode ^= 2; + flip_previous = 1; + + for (size_t i = 0; i < opcount; i++) { + ops[i].has_been_executed = 0; + } + + int acc = execute(ops, opcount); + if (acc != -1) { + return acc; + } + } while (++cur_op < ops + opcount); + + return -1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", exe_program(argv[argc - 1])); +} diff --git a/2020/09/part1.c b/2020/09/part1.c new file mode 100644 index 0000000..d17fb2b --- /dev/null +++ b/2020/09/part1.c @@ -0,0 +1,54 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +#define INPUT_LEN 1000 +#define SEARCH_LEN 25 + +bool has_sum(uint64_t *cur_num) +{ + uint64_t search = *cur_num; + uint64_t *p1 = cur_num - SEARCH_LEN; + do { + uint64_t *p2 = cur_num - SEARCH_LEN; + do { + if (*p1 + *p2 == search) { + return true; + } + } while (++p2 < cur_num); + } while (++p1 < cur_num); + + return false; +} + +int exe_program(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[24] = { 0 }; + + uint64_t nums[INPUT_LEN]; + size_t num_size = 0; + + while (fgets(buffer, 24, file)) { + nums[num_size++] = strtoull(buffer, NULL, 10); + } + + fclose(file); + + uint64_t *cur_num = nums + SEARCH_LEN; + do { + if (!has_sum(cur_num)) { + return *cur_num; + } + } while (++cur_num < nums + num_size); + + return -1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", exe_program(argv[argc - 1])); +} diff --git a/2020/09/part1.f90 b/2020/09/part1.f90 new file mode 100644 index 0000000..a89ee41 --- /dev/null +++ b/2020/09/part1.f90 @@ -0,0 +1,45 @@ +integer function has_sum(arg, arr) + implicit none + + integer, parameter :: arr_len = 25 + + integer (kind=8) :: arg + integer (kind=8), dimension(25) :: arr + integer :: i, j + + do i = 1, arr_len + do j = 1, arr_len + if (arr(i) + arr(j) == arg) then + has_sum = 1 + return + end if + end do + end do + + has_sum = 0 + return +end function has_sum + +program day9 + implicit none + + integer, parameter :: input_len = 1000 + + integer :: has_sum, i, tmp + integer (kind=8), dimension(input_len) :: input + + open(10, file='input', status='old') + do i = 1, input_len + read(10, *) input(i) + end do + close(10) + + do i = 26, input_len + tmp = has_sum(input(i), input(i - 25)) + if (tmp == 0) then + print *, input(i) + stop + end if + end do + +end program day9 diff --git a/2020/09/part2.c b/2020/09/part2.c new file mode 100644 index 0000000..28c335e --- /dev/null +++ b/2020/09/part2.c @@ -0,0 +1,78 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +#define INPUT_LEN 1000 +#define SEARCH_LEN 25 + +bool has_sum(uint64_t *cur_num) +{ + uint64_t search = *cur_num; + uint64_t *p1 = cur_num - SEARCH_LEN; + do { + uint64_t *p2 = cur_num - SEARCH_LEN; + do { + if (*p1 + *p2 == search) { + return true; + } + } while (++p2 < cur_num); + } while (++p1 < cur_num); + + return false; +} + +int exe_program(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[24] = { 0 }; + + uint64_t nums[INPUT_LEN] = { 0 }; + size_t num_size = 0; + + while (fgets(buffer, 24, file)) { + nums[num_size++] = strtoull(buffer, NULL, 10); + } + + fclose(file); + + uint64_t *cur_num = nums + SEARCH_LEN; + uint64_t search = -1; + do { + if (!has_sum(cur_num)) { + search = *cur_num; + break; + } + } while (++cur_num < nums + num_size); + + cur_num = nums; + do { + uint64_t min = __UINT64_MAX__; + uint64_t max = 0; + uint64_t sum = 0; + uint64_t *p1 = cur_num; + do { + if (*p1 < min) { + min = *p1; + } + else if (*p1 > max) { + max = *p1; + } + + sum += *p1; + + if (sum == search) { + return min + max; + } + } while (++p1 < nums + num_size); + } while (++cur_num < nums + num_size); + + return -1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", exe_program(argv[argc - 1])); +} diff --git a/2020/09/part2.f90 b/2020/09/part2.f90 new file mode 100644 index 0000000..b7e65de --- /dev/null +++ b/2020/09/part2.f90 @@ -0,0 +1,60 @@ +integer function has_sum(arg, arr) + implicit none + + integer, parameter :: arr_len = 25 + + integer (kind=8) :: arg + integer (kind=8), dimension(25) :: arr + integer :: i, j + + do i = 1, arr_len + do j = 1, arr_len + if (arr(i) + arr(j) == arg) then + has_sum = 1 + return + end if + end do + end do + + has_sum = 0 + return +end function has_sum + +program day9 + implicit none + + integer, parameter :: input_len = 1000 + + integer :: has_sum, i, j, tmp + integer (kind=8), dimension(input_len) :: input + integer (kind=8) :: search = -1, sum + + open(10, file='input', status='old') + do i = 1, input_len + read(10, *) input(i) + end do + close(10) + + do i = 26, input_len + tmp = has_sum(input(i), input(i - 25)) + if (tmp == 0) then + search = input(i) + exit + end if + end do + + do i = 1, input_len + sum = 0 + do j = i, input_len + sum = sum + input(j) + if (sum >= search) then + exit + end if + end do + if (sum == search) then + print *, minval(input(i:j)) + maxval(input(i:j)) + stop + end if + end do + +end program day9 diff --git a/2020/09/part2_fast.c b/2020/09/part2_fast.c new file mode 100644 index 0000000..cf06bbd --- /dev/null +++ b/2020/09/part2_fast.c @@ -0,0 +1,98 @@ +#include <stdbool.h> +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +#define INPUT_LEN 1000 +#define SEARCH_LEN 25 + +uint64_t min_uint64(const uint64_t *start, const uint64_t *stop) +{ + uint64_t min = *start; + while (++start <= stop) { + if (*start < min) { + min = *start; + } + } + + return min; +} + +uint64_t max_uint64(const uint64_t *start, const uint64_t *stop) +{ + uint64_t max = *start; + while (++start <= stop) { + if (*start > max) { + max = *start; + } + } + + return max; +} + +bool has_sum(uint64_t *cur_num) +{ + uint64_t search = *cur_num; + uint64_t *p1 = cur_num - SEARCH_LEN; + do { + if (*p1 >= search) + { + continue; + } + + uint64_t *p2 = cur_num - SEARCH_LEN; + do { + if (*p1 + *p2 == search) { + return true; + } + } while (++p2 < cur_num); + } while (++p1 < cur_num); + + return false; +} + +int exe_program(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[24] = { 0 }; + + uint64_t nums[INPUT_LEN] = { 0 }; + size_t num_size = 0; + + while (fgets(buffer, 24, file)) { + nums[num_size++] = strtoull(buffer, NULL, 10); + } + + fclose(file); + + uint64_t *cur_num = nums + SEARCH_LEN; + uint64_t search = -1; + do { + if (!has_sum(cur_num)) { + search = *cur_num; + break; + } + } while (++cur_num < nums + num_size); + + cur_num = nums; + do { + uint64_t sum = 0; + uint64_t *p1 = cur_num; + do { + sum += *p1; + } while (++p1 < nums + num_size && sum < search); + + if (sum == search) { + return min_uint64(cur_num, p1) + max_uint64(cur_num, p1); + } + } while (++cur_num < nums + num_size); + + return -1; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", exe_program(argv[argc - 1])); +} diff --git a/2020/10/part1.c b/2020/10/part1.c new file mode 100644 index 0000000..f5a700e --- /dev/null +++ b/2020/10/part1.c @@ -0,0 +1,70 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#define MAX_INPUT_LEN 128 + +void insert_value_sorted(int *list, size_t *size, int value) +{ + long long low = 0, high = *size; + while (low < high) { + int m = low + (high - low) / 2; + if (list[m] < value) { + low = m + 1; + } + else if (list[m] > value) { + high = m; + } + else { + // Value already exists in the list + return; + } + } + + for (long long i = *size - 1; i >= low; i--) { + list[i + 1] = list[i]; + } + + (*size)++; + list[low] = value; +} + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + int input[MAX_INPUT_LEN] = { 0 }; + size_t input_size = 1; // 0 is our start value + + while (fgets(buffer, 128, file)) { + insert_value_sorted(input, &input_size, atoi(buffer)); + } + + fclose(file); + + int diff1 = 0; + int diff3 = 1; // Diff with adapter + + for (size_t i = 1; i < input_size; i++) + { + int diff = input[i] - input[i - 1]; + if (diff == 1) { + diff1++; + } + else if (diff == 3) { + diff3++; + } + } + + return diff1 * diff3; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/10/part2.c b/2020/10/part2.c new file mode 100644 index 0000000..5e766d4 --- /dev/null +++ b/2020/10/part2.c @@ -0,0 +1,87 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#include "../utils.h" + +#define MAX_INPUT_LEN 128 + +void insert_value_sorted(int *list, size_t *size, int value) +{ + long long low = 0, high = *size; + while (low < high) { + int m = low + (high - low) / 2; + if (list[m] < value) { + low = m + 1; + } + else if (list[m] > value) { + high = m; + } + else { + // Value already exists in the list + return; + } + } + + for (long long i = *size - 1; i >= low; i--) { + list[i + 1] = list[i]; + } + + (*size)++; + list[low] = value; +} + +#ifdef USE_ASM +uint64_t possible_seq(const int *input, size_t input_size); +#else +uint64_t possible_seq(const int *input, size_t input_size) +{ + // Use char to optimize for size + const static char TRIB[] = { 1, 1, 2, 4, 7 }; + int con = 0; + uint64_t res = 1; + const int *prev = input; + const int *cur = input + 1; + do { + if (likely(*cur - *prev == 1)) { + con++; + } + else { + res *= TRIB[con]; + con = 0; + } + } while (++prev && ++cur < input + input_size); + + return res; +} +#endif + +uint64_t solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[16] = { 0 }; + + int input[MAX_INPUT_LEN] = { 0 }; + size_t input_size = 1; // 0 is our start value + + while (fgets(buffer, 16, file)) { + insert_value_sorted(input, &input_size, atoi(buffer)); + } + + // Add our device's built-in joltage adapter + input[input_size] = input[input_size - 1] + 3; + input_size++; + + fclose(file); + + return possible_seq(input, input_size); +} + +int main(int argc, char *argv[]) +{ + printf("%lu\n", solve(argv[argc - 1])); +} diff --git a/2020/10/possible_seq.asm b/2020/10/possible_seq.asm new file mode 100644 index 0000000..b737d13 --- /dev/null +++ b/2020/10/possible_seq.asm @@ -0,0 +1,30 @@ +global possible_seq + +section .rodata + TRIB: dq 1, 1, 2, 4, 7 ; tribonacci sequence (without first 2 zeroes) + +section .text + +possible_seq: + mov eax, 1 ; set up return value + xor ecx, ecx ; # of connected elements counter + lea rdx, [rdi + 4 * rsi - 4] ; pointer to the last element + lea r8, [rel TRIB] + jmp .loop +.ncon: + imul rax, qword [r8 + 8 * rcx] + xor ecx, ecx + add rdi, 4 + cmp rdi, rdx + jae .return +.loop: + mov esi, dword [rdi + 4] + sub esi, dword [rdi] + cmp esi, 1 + jne .ncon + inc ecx + add rdi, 4 + cmp rdi, rdx + jb .loop +.return: + ret diff --git a/2020/11/part1.c b/2020/11/part1.c new file mode 100644 index 0000000..459befe --- /dev/null +++ b/2020/11/part1.c @@ -0,0 +1,123 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#define MAX_INPUT_WIDTH 128 +#define MAX_INPUT_HEIGTH 128 +#define MAX_INPUT MAX_INPUT_WIDTH * MAX_INPUT_HEIGTH + +int count_char(const char *source, char search) +{ + int oc = 0; + do { + oc += *source == search; + } while (*++source); + + return oc; +} + +void replace_char(char *destination, const char *source, char original, char replace) +{ + do { + if (*source == original) { + *destination = replace; + } + else { + *destination = *source; + } + } while (++destination && *++source); + *destination = 0; +} + +int sur_oc_seats(const char *source, size_t width, size_t height, size_t index_y, size_t index_x) +{ + int num = 0; + // Check 3 seats on the line above + if (index_y > 0) { + size_t x = index_x == 0 ? index_x : index_x - 1; + size_t end_x = index_x < width - 1 ? index_x + 2 : index_x + 1; + for (; x < end_x; x++) { + num += source[(index_y - 1) * width + x] == '#'; + } + } + + // Check sides + if (index_x > 0) { + num += source[index_y * width + index_x - 1] == '#'; + } + + if (index_x < width - 1) { + num += source[index_y * width + index_x + 1] == '#'; + } + + // Check 3 seats on the line above + if (index_y < height - 1) { + size_t x = index_x == 0 ? index_x : index_x - 1; + size_t end_x = index_x < width - 1 ? index_x + 2 : index_x + 1; + for (; x < end_x; x++) { + num += source[(index_y + 1) * width + x] == '#'; + } + } + + return num; +} + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + char input[MAX_INPUT] = { 0 }; + size_t height = 1; + fgets(buffer, 128, file); + size_t width = strchr(buffer, '\n') - buffer; + replace_char(input, buffer, 'L', '#'); + + while (fgets(buffer, 128, file)) { + // Round 1 + replace_char(&input[height++ * width], buffer, 'L', '#'); + } + + fclose(file); + + size_t size = height * width; + + // Zero terminate + input[size] = 0; + + char input2[MAX_INPUT] = { 0 }; + do { + for (size_t i = 0; i < size; i++) { + if (input[i] == '.') { + input2[i] = '.'; + } + else if (input[i] == 'L') { + if (sur_oc_seats(input, width, height, i / width, i % width) == 0) { + input2[i] = '#'; + } + else { + input2[i] = 'L'; + } + } + else if (input[i] == '#') { + if (sur_oc_seats(input, width, height, i / width, i % width) >= 4) { + input2[i] = 'L'; + } + else { + input2[i] = '#'; + } + } + } + } while (memcmp(input, input2, size) && memcpy(input, input2, size)); + + return count_char(input, '#'); +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/11/part2.c b/2020/11/part2.c new file mode 100644 index 0000000..2443ddd --- /dev/null +++ b/2020/11/part2.c @@ -0,0 +1,202 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#define MAX_INPUT_WIDTH 128 +#define MAX_INPUT_HEIGTH 128 +#define MAX_INPUT MAX_INPUT_WIDTH * MAX_INPUT_HEIGTH + +int count_char(const char *source, char search) +{ + int oc = 0; + do { + oc += *source == search; + } while (*++source); + + return oc; +} + +void replace_char(char *destination, const char *source, char original, char replace) +{ + do { + if (*source == original) { + *destination = replace; + } + else { + *destination = *source; + } + } while (++destination && *++source); + *destination = 0; +} + +char get_char(const char *source, size_t width, size_t y, size_t x) { + return source[y * width + x]; +} + +int sur_oc_seats(const char *source, size_t width, size_t height, size_t index_y, size_t index_x) +{ + int num = 0; + // Check upwards + size_t y = index_y; + size_t x = index_x; + while (--y < height) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check downwards + y = index_y; + while (++y < height) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check left + y = index_y; + x = index_x; + while (--x < width) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check right + x = index_x; + while (++x < width) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check left upwards + y = index_y; + x = index_x; + while (--y < height && --x < width) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check left downwards + y = index_y; + x = index_x; + while (++y < height && --x < width) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check right upwards + y = index_y; + x = index_x; + while (--y < height && ++x < width) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + // Check right downwards + y = index_y; + x = index_x; + while (++y < height && ++x < width ) { + char c = get_char(source, width, y, x); + if (c == '.') { + continue; + } + + num += c == '#'; + break; + } + + return num; +} + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[128] = { 0 }; + + char input[MAX_INPUT] = { 0 }; + size_t height = 1; + fgets(buffer, 128, file); + size_t width = strchr(buffer, '\n') - buffer; + replace_char(input, buffer, 'L', '#'); + + while (fgets(buffer, 128, file)) { + // Round 1 + replace_char(&input[height++ * width], buffer, 'L', '#'); + } + + fclose(file); + + size_t size = height * width; + + // Zero terminate + input[size] = 0; + + char input2[MAX_INPUT] = { 0 }; + do { + for (size_t i = 0; i < size; i++) { + if (input[i] == '.') { + input2[i] = '.'; + } + else if (input[i] == 'L') { + if (sur_oc_seats(input, width, height, i / width, i % width) == 0) { + input2[i] = '#'; + } + else { + input2[i] = 'L'; + } + } + else if (input[i] == '#') { + if (sur_oc_seats(input, width, height, i / width, i % width) >= 5) { + input2[i] = 'L'; + } + else { + input2[i] = '#'; + } + } + } + } while (memcmp(input, input2, size) && memcpy(input, input2, size)); + + return count_char(input, '#'); +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/12/part1.c b/2020/12/part1.c new file mode 100644 index 0000000..7ee0f4a --- /dev/null +++ b/2020/12/part1.c @@ -0,0 +1,78 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#define MAX_INPUT_WIDTH 128 +#define MAX_INPUT_HEIGTH 128 +#define MAX_INPUT MAX_INPUT_WIDTH * MAX_INPUT_HEIGTH + +enum direction { + North, + East, + South, + West +}; + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[8] = { 0 }; + + enum direction dir = East; + int hor = 0; + int ver = 0; + while (fgets(buffer, 8, file)) { + int n = atoi(buffer + 1); + switch (buffer[0]) { + case 'N': + ver += n; + break; + case 'E': + hor += n; + break; + case 'S': + ver -= n; + break; + case 'W': + hor -= n; + break; + case 'F': + switch (dir) { + case North: + ver += n; + break; + case East: + hor += n; + break; + case South: + ver -= n; + break; + case West: + hor -= n; + break; + } + break; + case 'R': + dir = (enum direction)(((int)dir + (n / 90)) % 4); + break; + case 'L': + dir = (enum direction)((abs(4 + ((int)dir - (n / 90))) % 4)); + break; + default: + break; + } + } + + fclose(file); + + return abs(ver) + abs(hor); +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/12/part2.c b/2020/12/part2.c new file mode 100644 index 0000000..745b56c --- /dev/null +++ b/2020/12/part2.c @@ -0,0 +1,66 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + +#include "../utils.h" + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + // Include space for newline and string terminator + char buffer[8] = { 0 }; + + int w_x = 10; + int w_y = 1; + int y = 0; + int x = 0; + while (fgets(buffer, 8, file)) { + int n = atoi(buffer + 1); + switch (buffer[0]) { + case 'N': + w_y += n; + break; + case 'E': + w_x += n; + break; + case 'S': + w_y -= n; + break; + case 'W': + w_x -= n; + break; + case 'F': + for (int i = 0; i < n; i++) { + x += w_y; + y += w_x; + } + break; + case 'R': + for (int i = 0; i < n / 90; i++) { + SWAP(w_y, w_x); + w_y = -w_y; + } + break; + case 'L': + for (int i = 0; i < n / 90; i++) { + SWAP(w_y, w_x); + w_x = -w_x; + } + break; + default: + break; + } + } + + fclose(file); + + return abs(x) + abs(y); +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/13/part1.c b/2020/13/part1.c new file mode 100644 index 0000000..b62d007 --- /dev/null +++ b/2020/13/part1.c @@ -0,0 +1,48 @@ +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#define BUFFER_SIZE 256 +#define MAX_INPUT_LEN 128 + +int solve(const char *filename) +{ + FILE *file = fopen(filename, "r"); + + char buffer[BUFFER_SIZE] = { 0 }; + fgets(buffer, BUFFER_SIZE, file); + int depart = atoi(buffer); + fgets(buffer, BUFFER_SIZE, file); + int bus_ids[MAX_INPUT_LEN] = { 0 }; + bus_ids[0] = atoi(buffer); + int i = 1; + char *p = buffer; + while ((p = strchr(p, ','))) { + // x is never the last value, just keep looping we find a valid input + while (*++p == 'x') { + p += 1; + } + + bus_ids[i++] = atoi(p); + } + + int bus_id = 0; + int wait = INT32_MAX; + for (int j = 0; j < i; j++) { + int id = bus_ids[j]; + int tmprem = id - (depart % id); + if (tmprem < wait) { + bus_id = id; + wait = tmprem; + } + } + + fclose(file); + return bus_id * wait; +} + +int main(int argc, char *argv[]) +{ + printf("%i\n", solve(argv[argc - 1])); +} diff --git a/2020/prepare b/2020/prepare new file mode 100755 index 0000000..7e4f9e5 --- /dev/null +++ b/2020/prepare @@ -0,0 +1,11 @@ +#!/usr/bin/env bash + +set -ef + +day="$(printf '%02d' "$1")" +file="part$2.c" +if test -f "part$2_fast.c" +then + file="part$2_fast.c" +fi +clang -Wall -pedantic -O3 -march=native -mtune=native -flto -s -o run "$day/$file" |