advent2021

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

commit 2c3ad918011007019947390ec0af469075f9d779
parent 5a036344c64394553c3a3383fc09808ba02aa44b
Author: bsandro <brian.drosan@gmail.com>
Date:   Tue, 14 Dec 2021 09:13:37 +0200

Day 14, puzzle 1 (dumb solution)

Diffstat:
Aday14/Makefile | 25+++++++++++++++++++++++++
Aday14/input.txt | 102+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday14/main.c | 29+++++++++++++++++++++++++++++
Aday14/puzzle.c | 207+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday14/test.txt | 18++++++++++++++++++
5 files changed, 381 insertions(+), 0 deletions(-)

diff --git a/day14/Makefile b/day14/Makefile @@ -0,0 +1,25 @@ +NAME=$(shell basename ${PWD}) +SRC=$(wildcard *.c ../common/*.c) +DEPS:=$(wildcard *.h ../common/*.h) +OBJ:=$(SRC:.c=.o) +CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common +LDFLAGS=-lc + +all: $(NAME) + +.PHONY: clean run + +clean: + rm -f $(OBJ) $(NAME) + +%.o : %.c $(DEPS) + @$(CC) $(CFLAGS) -c $< -o $@ + +$(NAME): $(OBJ) + @$(CC) $(OBJ) -o $@ $(LDFLAGS) + +run: $(NAME) + @./$(NAME) input.txt + +test: $(NAME) + @./$(NAME) test.txt diff --git a/day14/input.txt b/day14/input.txt @@ -0,0 +1,102 @@ +SVKVKCCBNHNSOSCCOPOC + +KK -> B +CS -> P +VV -> O +KO -> S +PO -> N +PH -> K +BV -> O +VH -> V +PF -> P +HB -> B +OB -> V +FC -> F +OS -> H +NB -> P +SH -> S +KV -> K +SO -> C +NP -> B +NV -> F +CP -> O +KS -> N +FP -> B +VN -> V +NC -> S +FH -> N +CB -> V +PV -> B +NH -> B +NF -> H +PC -> B +NO -> N +CN -> P +KF -> B +VF -> S +CC -> K +CF -> N +PS -> S +NK -> N +PB -> H +BP -> O +FK -> N +BO -> S +OH -> C +VB -> S +VP -> F +FO -> V +KB -> C +SK -> H +CO -> H +HV -> H +SV -> B +BF -> O +SS -> K +VK -> S +HS -> B +HF -> P +PK -> F +BS -> O +BB -> O +VC -> P +OP -> F +NS -> P +SB -> C +NN -> K +HC -> S +HH -> B +FN -> P +OO -> V +VO -> N +ON -> P +FV -> K +HK -> S +FS -> V +HO -> V +PN -> B +KH -> B +CH -> C +KP -> S +BH -> O +BK -> B +FB -> H +VS -> S +HP -> O +SP -> P +OV -> F +OF -> H +OC -> V +KN -> H +BC -> F +BN -> F +CK -> K +SN -> P +SF -> K +KC -> C +SC -> C +HN -> V +OK -> O +FF -> V +CV -> V +PP -> V diff --git a/day14/main.c b/day14/main.c @@ -0,0 +1,29 @@ +#include <stdio.h> +#include <time.h> +#include <string.h> + +void puzzle(const char *filename, long long *res1, long long *res2); + +int main(int argc, char *argv[]) { + printf("Advent of Code: day 14\n"); + double time_start = clock(); + + if (argc <= 1) { + printf("Usage: %s inputfile.txt\n", argv[0]); + return -1; + } + + const char *filename = argv[1]; + long long counter1 = -1; + long long counter2 = -1; + + puzzle(filename, &counter1, &counter2); + + printf("Puzzle #1: %lld\n", counter1); + printf("Puzzle #2: %lld\n", counter2); + + double elapsed = clock() - time_start; + printf("Elapsed: %f\n", elapsed / CLOCKS_PER_SEC); + + return 0; +} diff --git a/day14/puzzle.c b/day14/puzzle.c @@ -0,0 +1,207 @@ +#define _DEFAULT_SOURCE + +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <strings.h> +#include <assert.h> +#include <ctype.h> +#include <limits.h> +#include <stdbool.h> + +#include "util.h" + +#define STR_LEN 32 + +struct rule_t { + char search[3]; + char replace[4]; +}; + +struct count_t { + char symbol; + long long count; +}; + +void parse_rule(struct array_t *rules, const char *str); +void print_rules(struct array_t *rules); +bool apply_rules(const struct array_t *rules, const char s1, const char s2, char **str_new); +long long count_result1(const char *str); +void add_count(struct array_t *counts, const char symbol); +long long get_min_count(const struct array_t *counts); +long long get_max_count(const struct array_t *counts); + +void puzzle(const char *filename, long long *result1, long long *result2) { + FILE *infile = fopen(filename, "r"); + if (infile == NULL) { + fprintf(stderr, "fopen() error: %s\n", strerror(errno)); + return; + } + + char buf[STR_LEN] = {0}; + unsigned int line_num = 0; + + *result1 = 0; + *result2 = 0; + + bool rules_started = false; + char *str = NULL; + struct array_t rules = { .data = NULL }; + array_init(&rules, sizeof(struct rule_t), 10); + while (fgets(buf, STR_LEN, infile) != NULL) { + if (strlen(buf) == 1) { + rules_started = true; + continue; + } + if (rules_started) { + parse_rule(&rules, buf); + } else { + assert(str == NULL); + size_t len = strlen(buf); + str = malloc(len); + strlcat(str, buf, len); // losing last symbol \n + } + ++line_num; + bzero(buf, STR_LEN); + } + + //printf("input str: %s\n", str); + //print_rules(&rules); + + for (int i = 0; i < 10; ++i) { + char *str_new = NULL; + size_t str_len = strlen(str); + //printf("iter %d, str len: %zu\n", i, str_len); + for (size_t s = 0; s < str_len; ++s) { + if (!apply_rules(&rules, str[s], str[s+1], &str_new)) { + size_t str_new_len = strlen(str_new); + str_new = realloc(str_new, str_new_len+1); + str_new[str_new_len] = str[s]; + } + } + //printf("new str: %s\n", str_new); + free(str); + str = str_new; + } + + *result1 = count_result1(str); + + free(str); + free(rules.data); + // mutiny! ignoring feof/ferror. + fclose(infile); +} + +bool apply_rules(const struct array_t *rules, const char s1, const char s2, char **str_new) { + assert(rules != NULL); + const struct rule_t *data = rules->data; + for (size_t j = 0; j < rules->count; ++j) { + struct rule_t rule = data[j]; + if (rule.search[0] == s1 && rule.search[1] == s2) { + size_t str_new_len = 4; + if (*str_new != NULL) { + str_new_len = strlen(*str_new) + 4; + } + *str_new = realloc(*str_new, str_new_len); + strlcat(*str_new, rule.replace, str_new_len); + return true; + } + } + return false; +} + +long long count_result1(const char *str) { + struct array_t counts = { .data = NULL }; + array_init(&counts, sizeof(struct count_t), 10); + size_t len = strlen(str); + for (size_t i = 0; i < len; ++i) { + add_count(&counts, str[i]); + } + free(counts.data); + + return get_max_count(&counts) - get_min_count(&counts); +} + +void add_count(struct array_t *counts, const char symbol) { + assert(counts != NULL); + struct count_t *data = counts->data; + for (size_t i = 0; i < counts->count; ++i) { + if (data[i].symbol == symbol) { + data[i].count++; + return; + } + } + + if (counts->count >= counts->cap) { + array_expand(counts); + } + data = counts->data; + data[counts->count++] = (struct count_t){ .symbol = symbol, .count = 1 }; +} + +long long get_min_count(const struct array_t *counts) { + assert(counts != NULL); + struct count_t *data = counts->data; + long long min = -1; + for (size_t i = 0; i < counts->count; ++i) { + if (min == -1) { + min = data[i].count; + } else { + min = data[i].count < min ? data[i].count : min; + } + } + return min; +} + +long long get_max_count(const struct array_t *counts) { + assert(counts != NULL); + struct count_t *data = counts->data; + long long max = 0; + for (size_t i = 0; i < counts->count; ++i) { + max = data[i].count > max ? data[i].count : max; + } + return max; +} + +void parse_rule(struct array_t *rules, const char *str) { + assert(rules != NULL); + assert(str != NULL); + char *tmp = strndup(str, STR_LEN); + assert(tmp != NULL); + char *token = NULL; + + int n = 0; + struct rule_t rule = {0}; + while ((token = strsep(&tmp, " ->\n")) != NULL) { + if (*token != '\0') { + assert(n < 2); + if (n == 0) { + assert(strlen(token) == 2); + strlcpy(rule.search, token, 3); + rule.replace[0] = token[0]; + //rule.replace[2] = token[1]; + } else { + assert(strlen(token) == 1); + rule.replace[1] = token[0]; + } + n++; + } + } + + if (rules->count >= rules->cap) { + array_expand(rules); + } + + struct rule_t *data = rules->data; + data[rules->count++] = rule; + free(tmp); +} + +void print_rules(struct array_t *rules) { + assert(rules != NULL); + struct rule_t *data = rules->data; + for (size_t i = 0; i < rules->count; ++i) { + printf("%s -> %s\n", data[i].search, data[i].replace); + } +} diff --git a/day14/test.txt b/day14/test.txt @@ -0,0 +1,18 @@ +NNCB + +CH -> B +HH -> N +CB -> H +NH -> C +HB -> C +HC -> B +HN -> C +NN -> C +BH -> H +NC -> B +NB -> B +BN -> B +BB -> N +BC -> B +CC -> N +CN -> C