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/09/part1.c | 54 +++++++++++++++++++++++++++++ 2020/09/part1.f90 | 45 ++++++++++++++++++++++++ 2020/09/part2.c | 78 +++++++++++++++++++++++++++++++++++++++++ 2020/09/part2.f90 | 60 ++++++++++++++++++++++++++++++++ 2020/09/part2_fast.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 335 insertions(+) create mode 100644 2020/09/part1.c create mode 100644 2020/09/part1.f90 create mode 100644 2020/09/part2.c create mode 100644 2020/09/part2.f90 create mode 100644 2020/09/part2_fast.c (limited to '2020/09') 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 +#include +#include +#include + +#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 +#include +#include +#include + +#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 +#include +#include +#include + +#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])); +} -- cgit v1.2.3