advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs

commit 4406f03bfb6726439fa6aa60c7e93ac62b5b5878
parent e2888de02e7e27fedeb2262cdae8ef67f27c188e
Author: bsandro <brian.drosan@gmail.com>
Date:   Sat,  4 Dec 2021 07:16:33 +0200

Day 03, puzzle 2

Diffstat:
Mday03/main.c | 4++--
Mday03/puzzle1.c | 3++-
Aday03/puzzle2.c | 181+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 185 insertions(+), 3 deletions(-)

diff --git a/day03/main.c b/day03/main.c @@ -18,8 +18,8 @@ int main(int argc, char *argv[]) { int counter1 = puzzle1(filename); printf("Puzzle #1: %d\n", counter1); - //int counter2 = puzzle2(filename); - //printf("Puzzle #2: %d\n", counter2); + int counter2 = puzzle2(filename); + printf("Puzzle #2: %d\n", counter2); return 0; } diff --git a/day03/puzzle1.c b/day03/puzzle1.c @@ -13,7 +13,8 @@ #define STR_LEN 13 // BITS_COUNT + 1 #define FMT_STRING "%" FMT(STR_LEN) "s" -// No idea about the case when number (1/0) counts are equal, it is not described in the task. +// No idea about the case when number (1/0) counts are equal, +// it is not described in the task. int puzzle1(const char *filename) { FILE *infile = fopen(filename, "r"); diff --git a/day03/puzzle2.c b/day03/puzzle2.c @@ -0,0 +1,181 @@ +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <strings.h> +#include <stdbool.h> +#include <sys/stat.h> + +#define PRINT_ERR(func) fprintf(stderr, #func "() error: %s\n", strerror(errno)); + +#define FMT_(l) #l +#define FMT(l) FMT_(l) + +#define MAX_LEN 16 +#define BITS_COUNT 12 +#define STR_LEN 13 // BITS_COUNT + 1 (EOL/EOF or terminating byte) +#define FMT_STRING "%" FMT(STR_LEN) "s" + +struct numbers_t { + long *data; + size_t limit; + size_t count; +}; + +bool init_numbers(struct numbers_t *numbers, size_t limit); +bool copy_numbers(const struct numbers_t *src, struct numbers_t *dst); +void move_numbers(struct numbers_t *src, struct numbers_t *dst); +bool filter_numbers_by_bit(struct numbers_t *numbers, int bit_num, bool (cmp)(size_t, size_t)); + +bool compare_oxygen(size_t zeroes, size_t ones) { + return zeroes > ones; +} + +bool compare_scrubber(size_t zeroes, size_t ones) { + return zeroes <= ones; +} + +int puzzle2(const char *filename) { + FILE *infile = fopen(filename, "r"); + if (infile == NULL) { + PRINT_ERR(fopen) + return -1; + } + + struct numbers_t numbers; + init_numbers(&numbers, 0); + + // deducing the approx numbers array size from the filesize + struct stat filestats = {0}; + if (stat(filename, &filestats) == -1) { + PRINT_ERR(stat) + return -1; + } else { + numbers.limit = filestats.st_size / STR_LEN; + numbers.data = calloc(numbers.limit, sizeof(long)); + if (numbers.data == NULL) { + PRINT_ERR(calloc) + return -1; + } + } + + char buf[MAX_LEN] = {0}; + char str[STR_LEN] = {0}; + + while (fgets(buf, MAX_LEN, infile) != NULL) { + if (sscanf(buf, FMT_STRING, str) == 1) { + // just a precaution, good 'ole "allocate x2 if it doesn't fit anymore" + if (numbers.count >= numbers.limit) { + numbers.limit *= 2; + numbers.data = reallocf(numbers.data, numbers.limit * sizeof(long)); + if (numbers.data == NULL) { + PRINT_ERR(reallocf) + return -1; + } + } + numbers.data[numbers.count++] = strtol(str, NULL, 2); + bzero(buf, MAX_LEN); + bzero(str, STR_LEN); + } + } + + long oxygen_number = 0; + long scrubber_number = 0; + struct numbers_t oxygen; + struct numbers_t scrubber; + init_numbers(&oxygen, 0); + init_numbers(&scrubber, 0); + if (!copy_numbers(&numbers, &oxygen) || !copy_numbers(&numbers, &scrubber)) { + fprintf(stderr, "copy_numbers() error\n"); + return false; + } + + for (int bit = BITS_COUNT - 1; bit >= 0; --bit) { + filter_numbers_by_bit(&oxygen, bit, compare_oxygen); + filter_numbers_by_bit(&scrubber, bit, compare_scrubber); + } + + if (oxygen.count != 1 || scrubber.count != 1) { + fprintf(stderr, "Filter failed :C"); + goto finish; + } + + oxygen_number = oxygen.data[0]; + scrubber_number = scrubber.data[0]; + + // mutiny! ignoring feof/ferror. +finish: + free(numbers.data); + free(oxygen.data); + free(scrubber.data); + fclose(infile); + + return oxygen_number * scrubber_number; +} + +bool init_numbers(struct numbers_t *numbers, size_t limit) { + numbers->data = NULL; + numbers->count = 0; + numbers->limit = limit; + + if (limit > 0) { + numbers->data = calloc(limit, sizeof(long)); + if (numbers->data == NULL) { + PRINT_ERR(calloc) + return false; + } + } + + return true; +} + +bool copy_numbers(const struct numbers_t *src, struct numbers_t *dst) { + if (src->data == NULL || src->count == 0 || src->limit == 0) + return false; + + size_t dst_size = src->count * sizeof(long); + dst->data = realloc(dst->data, dst_size); + dst->count = src->count; + dst->limit = src->limit; + memcpy(dst->data, src->data, dst_size); + + return true; +} + +void move_numbers(struct numbers_t *src, struct numbers_t *dst) { + free(dst->data); + dst->data = src->data; + dst->count = src->count; + dst->limit = src->limit; +} + +bool filter_numbers_by_bit(struct numbers_t *numbers, int bit_num, bool (cmp)(size_t, size_t)) { + if (numbers->count == 1) + return false; + + struct numbers_t filtered_0; + if (!init_numbers(&filtered_0, numbers->count)) + return false; + + struct numbers_t filtered_1; + if (!init_numbers(&filtered_1, numbers->count)) + return false; + + for (size_t i = 0; i < numbers->count; ++i) { + if (numbers->data[i] & (1 << bit_num)) { + filtered_1.data[filtered_1.count++] = numbers->data[i]; + } else { + filtered_0.data[filtered_0.count++] = numbers->data[i]; + } + } + + if (cmp(filtered_0.count, filtered_1.count)) { + move_numbers(&filtered_0, numbers); + free(filtered_1.data); + } else { + move_numbers(&filtered_1, numbers); + free(filtered_0.data); + } + + return true; +}