advent2021

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

commit 92f03e4de6d97806719d0d9601ac993ed0f9dde3
parent 3242b5e61240e528891c546de4d860133caf7d9d
Author: bsandro <brian.drosan@gmail.com>
Date:   Thu,  9 Dec 2021 09:11:33 +0200

Day 08 puzzle 2 + rework of 1

Diffstat:
Mcommon/util.c | 1-
Mday08/puzzle.c | 246+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
2 files changed, 234 insertions(+), 13 deletions(-)

diff --git a/common/util.c b/common/util.c @@ -39,4 +39,3 @@ void parse_numbers_array(struct array_t *numbers, const char *str, const char *d free(tmp); } - diff --git a/day08/puzzle.c b/day08/puzzle.c @@ -9,7 +9,39 @@ #include <assert.h> #include <time.h> -#define STR_LEN 16384 +#include "util.h" + +#define STR_LEN 1024 +#define DIGITS_NUM 10 +#define SEGMENTS_NUM 8 // technically 7 but we need additional space for '\0' +#define PUZZLE_NUMBERS 4 // the amount of puzzle numbers in 2nd part of each string + +#define SEGMENT_A 0b00000001 +#define SEGMENT_B 0b00000010 +#define SEGMENT_C 0b00000100 +#define SEGMENT_D 0b00001000 +#define SEGMENT_E 0b00010000 +#define SEGMENT_F 0b00100000 +#define SEGMENT_G 0b01000000 + +struct digit_t { + unsigned short segments; // bit mask + size_t len; // cached strlen(str) + int digit; // deduced digit, -1 is "not known" +}; + +struct digit_t make_digit(const char *str); +unsigned short make_segments(const char *str); +struct digit_t *get_by_digit(struct digit_t *digits, int digit); +struct digit_t *get_by_segments(struct digit_t *digits, unsigned short segments); +void deduce_digits(struct digit_t *digits); +void deduce_simple_digits(struct digit_t *digits); +void deduce_three(struct digit_t *digits); +void deduce_zero(struct digit_t *digits); +void deduce_six(struct digit_t *digits); +void deduce_five(struct digit_t *digits); +void deduce_nine(struct digit_t *digits); +void deduce_two(struct digit_t *digits); void puzzle(const char *filename, long long *result1, long long *result2) { FILE *infile = fopen(filename, "r"); @@ -24,31 +56,221 @@ void puzzle(const char *filename, long long *result1, long long *result2) { *result1 = 0; *result2 = 0; - // dirty hacky straightforward stuff, probably won't work on part2 in any shape + // lets parse it like it's 19.99 (IQ) while (fgets(buf, STR_LEN, infile) != NULL) { + // first 10 strings are encoded digits, last 4 after | are puzzle numbers char *tmp = strndup(buf, STR_LEN); - char *token = NULL; assert(tmp != NULL); - int counter = 42; + char *token = NULL; + int digits_num = 0; + int puzzle_num = 0; + + struct digit_t digits[DIGITS_NUM]; + unsigned short puzzles[PUZZLE_NUMBERS]; + while ((token = strsep(&tmp, " \n")) != NULL) { - if (*token == '|') { - counter = 0; - } else if (counter < 4) { - counter++; + if (*token == '|') continue; + + if (digits_num < DIGITS_NUM) { + digits[digits_num++] = make_digit(token); + } else if (puzzle_num < PUZZLE_NUMBERS) { size_t len = strlen(token); + assert(len > 0 && len < SEGMENTS_NUM); + puzzles[puzzle_num++] = make_segments(token); + } + } - if (len == 2 || len == 3 || len == 4 || len == 7) { - (*result1)++; - } + deduce_digits(digits); + + unsigned short answers[PUZZLE_NUMBERS]; + char answers_str[PUZZLE_NUMBERS + 1]; + for (int i = 0; i < PUZZLE_NUMBERS; ++i) { + struct digit_t *digit = get_by_segments(digits, puzzles[i]); + assert(digit != NULL); + answers[i] = digit->digit; + if (digit->digit == 1 || digit->digit == 4 || digit->digit == 7 || digit->digit == 8) { + (*result1)++; } } + snprintf(answers_str, PUZZLE_NUMBERS + 1, "%d%d%d%d", answers[0], answers[1], answers[2], answers[3]); + unsigned long solution = atol(answers_str); - free(tmp); + *result2 += solution; ++line_num; bzero(buf, STR_LEN); + free(tmp); } // mutiny! ignoring feof/ferror. fclose(infile); } + +struct digit_t make_digit(const char *str) { + assert(str != NULL); + size_t len = strlen(str); + assert(len > 0 && len < SEGMENTS_NUM); + struct digit_t digit = { .segments = 0, .len = len, .digit = -1 }; + digit.segments = make_segments(str); + return digit; +} + +unsigned short make_segments(const char *str) { + assert(str != NULL); + size_t len = strlen(str); + assert(len > 0 && len < SEGMENTS_NUM); + unsigned short segments = 0; + for (size_t i = 0; i < len; ++i) { + switch (str[i]) { + case 'a': + segments |= SEGMENT_A; + break; + case 'b': + segments |= SEGMENT_B; + break; + case 'c': + segments |= SEGMENT_C; + break; + case 'd': + segments |= SEGMENT_D; + break; + case 'e': + segments |= SEGMENT_E; + break; + case 'f': + segments |= SEGMENT_F; + break; + case 'g': + segments |= SEGMENT_G; + break; + } + } + return segments; +} + +//@todo caching or hashtable +struct digit_t *get_by_digit(struct digit_t *digits, int digit) { + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].digit == digit) return &digits[i]; + } + return NULL; +} + +struct digit_t *get_by_segments(struct digit_t *digits, unsigned short segments) { + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].segments == segments) return &digits[i]; + } + return NULL; +} + +void deduce_digits(struct digit_t *digits) { + assert(digits != NULL); + + // 1) simple digits + deduce_simple_digits(digits); + + // 2) 6sym string that misses any 2sym segments is 6 + deduce_six(digits); + + // 3) 5sym string that has all segments from 7 is 3 + deduce_three(digits); + + // 4) 6sym that doesn't have all segments from 3 is 0 + deduce_zero(digits); + + // 5) remaining 6sym is 9 + deduce_nine(digits); + + // 6) 5sym that has all segments from 9 is 5 + deduce_five(digits); + + // 7) remaining 5sym one is 2 + deduce_two(digits); + + // 8) profit! +} + +void deduce_simple_digits(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 2) digits[i].digit = 1; + else if (digits[i].len == 3) digits[i].digit = 7; + else if (digits[i].len == 4) digits[i].digit = 4; + else if (digits[i].len == 7) digits[i].digit = 8; + } +} + +//@todo unify? + +void deduce_six(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 6 && digits[i].digit == -1) { + struct digit_t *one = get_by_digit(digits, 1); + assert(one != NULL); + if ((one->segments & digits[i].segments) != one->segments) { + digits[i].digit = 6; + break; + } + } + } +} + +void deduce_three(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 5 && digits[i].digit == -1) { + struct digit_t *seven = get_by_digit(digits, 7); + if ((digits[i].segments | seven->segments) == digits[i].segments) { + digits[i].digit = 3; + break; + } + } + } +} + +void deduce_zero(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 6 && digits[i].digit == -1) { + struct digit_t *three = get_by_digit(digits, 3); + if ((digits[i].segments & three->segments) != three->segments) { + digits[i].digit = 0; + break; + } + } + } +} + +void deduce_nine(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 6 && digits[i].digit == -1) { + digits[i].digit = 9; + break; + } + } +} + +void deduce_five(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 5 && digits[i].digit == -1) { + struct digit_t *nine = get_by_digit(digits, 9); + if ((nine->segments | digits[i].segments) == nine->segments) { + digits[i].digit = 5; + break; + } + } + } +} + +void deduce_two(struct digit_t *digits) { + assert(digits != NULL); + for (int i = 0; i < DIGITS_NUM; ++i) { + if (digits[i].len == 5 && digits[i].digit == -1) { + digits[i].digit = 2; + break; + } + } +}