advent2021

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

commit c264ecb29c6f47ba1fb60a17914a2ba8958c7fd1
parent 35c67ee884ea91515df3545b91677acfd48b4f2c
Author: bsandro <brian.drosan@gmail.com>
Date:   Tue, 21 Dec 2021 04:08:00 +0200

Day 20, puzzles 1 and 2

Diffstat:
Aday20/Makefile | 25+++++++++++++++++++++++++
Aday20/Makefile.debug | 25+++++++++++++++++++++++++
Aday20/input.txt | 102+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday20/main.c | 29+++++++++++++++++++++++++++++
Aday20/puzzle.c | 186+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday20/test.txt | 7+++++++
6 files changed, 374 insertions(+), 0 deletions(-)

diff --git a/day20/Makefile b/day20/Makefile @@ -0,0 +1,25 @@ +NAME=$(shell basename ${PWD}) +SRC=$(wildcard *.c ../common/*.c) +DEPS:=$(wildcard *.h ../common/*.h) +OBJ:=$(SRC:.c=.o) +CFLAGS=-O2 -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/day20/Makefile.debug b/day20/Makefile.debug @@ -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 -fsanitize=address -fno-omit-frame-pointer -std=c99 -Werror -Wall -Wextra -I. -I../common +LDFLAGS=-g -lc -fsanitize=address + +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/day20/input.txt b/day20/input.txt @@ -0,0 +1,102 @@ +########..#..#.##.##.#.#..#.#.###.######.##..##.##..#...#....##.##...##.#.#...#.#.##.###.#.##.#.##.#...#.#.###.#.##.#.####.###..#.####.##..#.#####..####.#.#.#....##.#.#.##...#.####.#....#.##..##...#...#.##..#...#.#..#..#.#.#..##..#.##.##..##...#..###...##..#..###.###.##..#..#####...#.#..###..##....##...#####.#####...##.#.##.#....#.##.#.###.#.##.#.##...######.#...##.#..#.#.#...###.#..#.##.####..##.#..#.##.#.##.######.#.....#.#....####.####.###...#....#..###..###.#...#.#.#.##..#..##.#.#..#..###.#.###..#...... + +##..##.#.#.###.##...##..#...#..##...##.#.####.##..#.#.##.###.#.#...#.#.....#.#..##.#.########....##. +#.#.#.###..###.#..#.#...#..#....#.....#.##.#.#..#####.##.###.#...#...#.#.##.#...##.###..#..##.#.###. +.####......#..#..##..#.##..##.#####.##.#...#.#.#.#.#.#.#.####.#....##...#....##..####...####.#.###.. +##.#....###.###.###..###..##.###..#.#####..#..#.#..#.#..#.####..##.#..#..##...##.##.##.##.##....#.## +.#..####..#####.##...#.#.#..###.#.##...#...#..##.##.#.##..#....#.#.#....##.#.....#########.#.###.... +.######..#....#.#....##...#..#.#######.....#..#....###.##.#.##.#...#.####..####..######..#....#..### +..######...#....###.##..#.#.#.####..#...##.###..##.###.#..#.#######...#....####.########.#.##..###.. +#.#.####...#.#.##.#..#..###.......#.....##.#..#.###.#..#.#.#.#.##.###.#..##..#.#...##..###...#..#..# +#####.#####...#.....##......#...###..###..#.#.#.####.##.#.##...#.#.##.#.###.....#........###....#... +.#..###.#...#.###...#.##..#.##...#####.####.##.#.#.###..##.##....#..#...#..#..##.#.#.#.#.....##.#..# +..#.####.#...###...###..#..#.#...##.#.###..##.#.##.##.###..#.###.#.##.....#.#.#...###.##...####.##.. +###.....#.###..###.#.###...#.#.##..#..##.###.#.#####.###.##.#######.#.#.#####.#.#.#.....#......##... +###.#.#.....#.#.#..#..###.###..#.#....#####.###.##..#.##..#..##.#.##...##.##..##.#....##.#####.....# +###...######.#.##.#.#..####..##.#.#.#..#.#.##..####..#.#####..#..#..#####.#....#.##.##..##...###.### +#...###.....#..#..###.....######.#.#.###.#.#####..###.#..#..#..#.#.#..####.#####.#....##.#....##..## +.##..###..###....#......#.###...##......#.#..##.#..#######.##.########.#...#.###..##.##.#....#...### +....##..#..##..###..#.#####..####.###.###.####........###.#..#.##..#......#.##.###.##.######.#.##.## +#.##########...###.##.####.....#####..###.....##.##.#..###.##.##.#..##..##....#.###.##.##.######...# +##.#..#.#.#...###.####...#..##..##.#.#.#.#....#.#..##.#..##.#.#..#####.#..##.#..###.#.######..###.#. +.#.#.##.#...####.##..##.##.#..##.##.##..#....###....#..####.#....###.#...#..##....##.#..######.####. +.#...#..#.####.##.#..#.#...##...###.#...##....#...##...#....#..##.###.####..######..##.###.#.....#.. +#..#...###..#..#####.#....#..####.#.###..###.####...#...#.#..#...###.#.######.#.#..#.###....####..## +#.##.##.##..##..#.#..##...##.....#####.#.#..#.#.#.#.#.#.####..##....#####.#...###..#.#..#....##...## +###..#..#.###.##.##.#######.#..##.#..#.#.###..#.#.##..#.##..#..#.#.##.####..#.#####.#.##.#..###.###. +#.##.........###.##...####..#.#..###.###...#....#....#.#.#....#.##.#.....##...##........######.##... +##.#.#.###.####...###..#.....##.##...##.##..###..###..###..#.#..#..##.#########.#####..#####.#####.# +....#..##....#....#....#.###.#.......#..##.#.##..###....#.#####.#.##..#####.#..####.#...##....#.#... +.##.##...#..###...#.##..#.###.#...#.#..#.#.#..#.#..#.###.#..###..#.#.#####..#########..#####.##.#.#. +###..##..#.#..###.#.###.#.#..##.#.....###.#...#....#...#.#.#..##..##..##.#..#.#.####..##...#.#..#.#. +#..#.####.###..#....#########..#..#.#.####..#.#.....#.##......####..####....#.#..#......#...##.###.# +....##...#...####...#.#.###..####..####..##.###.##.#.##.###.#####.#.#...#......##.#..###..#....###.. +.##.##..##.###........##..#.###..#.#.#..##......#.......#.#.#........#..#.##..####.####....#####..#. +..##.#.#......#...##..#..###..#..#..#...###.#.####.#.#.##..#.#.#.#.##..#....######.##.#.#...#.##.... +....##..#..#..##.....#.#.#...####....#...##..#.#.#...#..###...#...#.#.....#####..###.##.#........##. +##.#......#.#..####...###.....#......#.#.###.###..##.#.#....##.##.....#.#.......##..#...#.#..##....# +#..##.....#####..#.....#.###..#.#..#.#...###.#.####...####.#.##.####..###.#.#..####.#....#.##.#.##.. +.#.#.####.##..#.##.#..###.#.###..####.#.#..#.#.##...##...#...#.###..##..#...#........##.#.##..#..### +....#...#..###.#....#..##.....##.####...####.##..#.#.#.###...#..####.###..##...###.#.#.##....#...... +##....##.##..#.......##.#...#..#.####...#..##.#.###.#.#....####.####.##.###.##.#..##..#.#.###.#..#.# +#...#....#.####.##....#...##.##.#..##.#...######...#.#.#..#.#.#..#.#.###.###..#.#.#.#.##.#...#.#.... +......#...##.###..##.#####..#..#..#...##.####.##...#.###...#.##...###.############..##..###.###.##.# +..#..##.....##..#.##.#.#....#.....##.....#.#..##...##..#.#...#..#..........####..#.####.#.#.....###. +.#..#..#########.#.#.#.###..###.#.##.#.#...#......######..#.#.###.##.#...#.##.###..#.#.#..#...#.#.#. +.#..#.#.#.#.#..######.#.....#.####....#..#.#..###.#..##.#.#...#.###...#....###...#.#...#.##...#..##. +#.##.##.#..#######.##..#...#.###............###.#..##.###.###....####.#..#####...###..#.####....##.# +...###.#...##..#.#########..#.###.##...#...##.##...#........###..######..##....#.....####.##....###. +.#..#..##...#######.#.##...#.#......#.##.#..#.#...##..######.#####..#..#..#...#..#........#.##.##..# +#.#..####.#.#.###...#...#.#.#.#..#.##....###...#.#...##...##.#####.#.#.#.##.##..####.#.##.##.##..... +####.###..........#.#.##.#..###.#..#....#.##.#.##.###.######......#.##...#..#..#..###..##.########.# +##...##.#.###..#...#.###......#######......#.#.###..#.##..####.#.####..#.#....#.#.#.##..#..###..#.#. +#.###.##..##.#.......###...##.##.###.##.####.##..###..##.#.###.#...#...#.#...##..##..#....#.#.#..### +.###..##...#....##...#...#.###..#.#####.##..####.##..###.##.#...##.##..########..#.#.##..#.#.#.....# +###.....#...#...#....###..#...#....#.#....#...#...##.#...##.#...##...#...#..#.#.##...#.###....##.##. +.#.##.###...#..###.##....##..##..#.#.##..#.#..###..#.##...#..##...##..#...#....#..#..####..#...#..#. +#..#.#.#..##.#.##.#..####.##..#....#.#.#.#.##...#.#.#...#.#.#.#.#.##.##....#####.#.###.###..#.####.. +.#.#....#####..#.#.###.#....#.#.#.##..##.##....##..#..#..#....####..#.###.....#..###.#.##.#.#.##.#.# +#..#..###..#...###...##.#.#.##....#..#.#.#.###...#....#...##..###.##.#.##..####.######..#.####..#### +##.##.###.###.#.###.#..#.###.....#..##.#..###.####.#.#.##.#..#.#...#....#.###.#####.##.#.#.##....### +...#.#.###..#..#.#.#..###...#.#..###.#.####..#..##.##..#.##.###...##.##..#.##.####.##..##..##.###..# +##.#...#..#.##..#####..#....##....####....###.##......#..#..#.##.######.##....#.#.###...#.###.....#. +###.######.#...##...##.#...##..#.#....#......#..#.#.#.####.#######..#...#...##.#.#.#.#.##.#.#..#..## +....####...##.#...#.###..#.......#####.#.#.#.##.#.##..#....######.##..#..#..#....#.#.#.#..#..#.##..# +#..##.#....#.##.##..#.#..#.##.##.#..#.##.#...##..###..###.#.##########.....##.#...##..##.##....#.### +###.#..#.###.##..#.#.#..#..#..#...##.#.#..#..#..###..#.#.#..###..##.#...##.#.....#.#####..##.#.###.# +...#.#.#..#.#...##..###...#.##.#.#.#....##..#####.#.##.####..##.##.#.##...###..#####..#...#.#...#... +..##.###....#...#####.#..#...#.##...####.##...##...#####......#####.....#..#..####.###.###..##..###. +#####.##.#.#.#.###.##.#.....#..##..#..##.#..#..#..#.##..#..#.#..#...#.###..#..####....#.###..##.#.#. +#.#.##.#...##.#.####....#....#...#.#..##....#.##....##..#..#.#.##.#.##.#.###..####.#######.#...#.#.. +#####..#.##.....####..#..#.####.##..##.#....#..#..#......#.###..#......#...##.....#..###.#.#...##.#. +#.#.#######.###....###...#.#...#...###.#...#.######..#.######..###...##....#..##..##.##..#.#.##..#.# +.##....#..##..###....##.###....####...#..#.#..###...##.#.##...#....#...#.#.###..#....#.###...##....# +..##..#.....##..##....#..###.##.#...######.#...#.#.#.##...#...#.##.#.....##.###.###..#.###..##..##.. +##...##.#.#..##.#.#.##.###.#.##...#......#.#..#.####.###.#....#...#..###.#.#..#.##.#.####....##.##.. +#.#.....#...#..#####....#.....#.#.#.....##.##.#########.#..#..##..#...#..###...##..#..##.....#.#.#.. +#......#..##..#.###..##.#..#.#.###.#....#...#......##.....###..#..###.........#.##.#.##.##.#...#..#. +#.#.##....##.#.###.####.##...####....#####.##.#....#.#.#.#.#..#.#...#.....########.##.#.#..#....#.#. +.#..##.#...##.#.######.#.#.##..####...#..#..##.###..####.##.#.#...##.#...##.###..##...####.#...##... +.###.#..#.##..#.##.##.#.#..######..#....#.###.#..######.#..#...####.........#.#.##.###.##.#.#.#.###. +..#...###.####....###.######.##.#...##.#...###..#########....#.#..##..##...#...#..##.##.#########..# +.#..#...##..#..##.#.#..#.#.......##..##.#.#..#..#.....#...##.#.###..#.#.#...###.#####.##.##.#...##.. +#....#.#.......##.#####......###.##....#...#.......###....#.####..##.##.#.#.#.#..####.#...#....#..#. +.........#.###.#.#####.#...#.#.#.###....###..#.###...##..#....##.#.###.#.##.#.#.##..#.#.###.#.#.##.# +.##.######.#..#.###.#...#######.#.##.##....###.#####..###.#...###.#..###.#.#.##.#..#.#.#..#..##..### +#....#..###..#.....#..####.#.##....####.#.###......###..##.##..#..#.#..#.#.######.#..#.##..##.###..# +..#.#..#.#.##.#..##.#.#.##.##..#.#.#...#.##.##.#.#.####.###.###..######..#..#..##.#..###..#.##...### +.......#..####....#..###..####.#..##..#..#.....#.##.##.#..##.#.##...#.###......#.#..#..#.##.#.#.#..# +..#..#.#..##########...##..#..##.##...#...#..#.##..###..#.#...##.##.#####..#....###...##.#.#..#..##. +#.###..#..#..#.#.##.#####.#.....#....##.#.#...#.##...####.##....##..###..#.##.##..#...##...##...#### +#####..#..#....####.##..#.#######..#....#########...##....#....#..#.#.##...########..#.#...##..##... +######.##.##.#.##########.####.#.#.#...##.##..#.#..##..#.##.....#.###...###...#.#.#.##.....###.##..# +..###....#..##...#.#...##..#..####.#.#.####.#.#......##.#..###.######.#.#....##.##...##.##..#.##.### +##..####..####.#####....#..##.#.#####.#..###..####.#......##.###....#...#..#....#..#.####.####...### +..#..###.#.##..#.#...#.##..#.#########..#..###..#..####.#....#.#..###...#.#..#.....#..###.####..###. +.##...####..#.###..#.#..#.##.#...####...#.#.#.........##..#.....#.##......#####.#.###..#####.###.#.. +###.##.##.#..#..##.####...###.#.#...#######.###.#..###.#.##.#...##..##..#...#...####.#.###....#..#.. +..###...###..#.....#..##.##.#.#..#..#.######.#....#.##..#.#.####...#..##.#....#...###.###.##.#..#.## +..#....###.#.#.#.#...#...#...##.#...#...###..#.###..##.#.....#.####...#.##.####.#....###.#..#...#.## +####..#...#.####...#####.#####....###.#.....##..#...##..#.#.####..#######.#.###..###..##.###...#.### +######.##.######..#.##.#.#..#...######.#.##.....####.###.#..#.#..##....#...##..#.#.##..#....#......# +.#.##..##.###.#..##.#...####..##...##..#.#.####.##..#.######....#####..##.#.#####...#.#...#.###..... diff --git a/day20/main.c b/day20/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 20\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/day20/puzzle.c b/day20/puzzle.c @@ -0,0 +1,186 @@ +#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 <stdbool.h> +#include <math.h> + +#include "util.h" + +#define STR_LEN 1024 +#define PATTERNS_LEN 512 +#define PATTERN_SIZE 9 +#define PATTERN_WIDTH 3 + +struct pic_t { + char *pic; + int w, h; + int def; +}; + +char * parse_patterns(const char *str); +void parse_pic(struct pic_t *pic, const char *str); +void print_pic(struct pic_t *pic); +struct pic_t * enhance(struct pic_t *pic, const char *patterns); +int make_pattern(const char pixels[PATTERN_SIZE]); +int get_pattern(struct pic_t *pic, int x, int y, int def); +int count_pixels(struct pic_t *pic); + +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; + char *patterns = NULL; + struct pic_t *pic = malloc(sizeof(struct pic_t)); + bzero(pic, sizeof(struct pic_t)); + + while (fgets(buf, STR_LEN, infile) != NULL) { + if (line_num == 0) { + // first line is always patterns + patterns = parse_patterns(buf); + } else if (line_num > 1) { + // initial picture is square + assert(buf[0] != '\n'); + parse_pic(pic, buf); + pic->h = line_num-1; + } + ++line_num; + bzero(buf, STR_LEN); + } + + assert(pic->w == pic->h); + + for (int i = 0; i < 50; ++i) { + pic = enhance(pic, patterns); + if (i == 1) { + *result1 = count_pixels(pic); + } + } + + *result2 = count_pixels(pic); + + free(patterns); + free(pic); + // mutiny! ignoring feof/ferror. + fclose(infile); +} + +int count_pixels(struct pic_t *pic) { + int cnt = 0; + for (int i = 0; i < pic->w * pic->h; ++i) { + cnt += pic->pic[i]; + } + return cnt; +} + +int make_pattern(const char pixels[PATTERN_SIZE]) { + int p = 0; + for (int i = 0; i < PATTERN_SIZE; ++i) { + int ind = PATTERN_SIZE-i-1; + assert(ind >= 0 && ind < PATTERN_SIZE); + p |= (pixels[ind] << i); + //printf("bit %d = %d, ind=%d, p=%d\n", i, pixels[ind], ind, p); + } + return p; +} + +struct pic_t * enhance(struct pic_t *pic, const char *patterns) { + assert(patterns != NULL); + assert(pic != NULL); + + struct pic_t *pic1 = malloc(sizeof(struct pic_t)); + assert(pic1 != NULL); + bzero(pic1, sizeof(struct pic_t)); + static const int growth = 1; + pic1->w = pic->w + growth*2; + pic1->h = pic->h + growth*2; + pic1->pic = calloc(pic1->w * pic1->h, sizeof(char)); + assert(pic1->pic != NULL); + + for (int y1 = 0; y1 < pic1->h; ++y1) { + for (int x1 = 0; x1 < pic1->w; ++x1) { + int p = get_pattern(pic, x1 - growth, y1 - growth, pic->def); + assert(p < PATTERNS_LEN); + pic1->pic[y1 * pic1->w + x1] = patterns[p]; + } + } + if (patterns[0] == 1 && patterns[511] == 0) { + pic1->def = !pic->def; + } + + free(pic->pic); + free(pic); + + return pic1; +} + +int get_pattern(struct pic_t *pic, int x, int y, int def) { + assert(pic != NULL); + assert(pic->pic != NULL); + char p[PATTERN_SIZE] = {0}; + memset(&p, def, PATTERN_SIZE); + + for (int dy = -1; dy <= 1; ++dy) { + for (int dx = -1; dx <= 1; ++dx) { + int index = 3*(dy+1) + (dx+1); + int x1 = x+dx; + int y1 = y+dy; + if (x1 >= 0 && y1 >= 0 && x1 < pic->w && y1 < pic->h) { + p[index] = pic->pic[y1 * pic->h + x1]; + } + } + } + return make_pattern(p); +} + +char * parse_patterns(const char *str) { + int len = strlen(str); + assert(len-1 == PATTERNS_LEN); + char *patterns = calloc(len, sizeof(char)); + assert(patterns != NULL); + for (int i = 0; i < PATTERNS_LEN; ++i) { + if (str[i] == '.') patterns[i] = 0; + else if (str[i] == '#') patterns[i] = 1; + else break; + } + return patterns; +} + +void parse_pic(struct pic_t *pic, const char *str) { + assert(pic != NULL); + assert(str != NULL); + int len = strlen(str) - 1; + assert(len > 0); + + if (pic->pic == NULL) { + pic->pic = calloc(len*len, sizeof(char)); + assert(pic->pic != NULL); + pic->w = len; + } + + assert(len == pic->w); + + for (int i = 0; i < len; ++i) { + if (str[i] == '.') pic->pic[pic->h * len+i] = 0; + else if (str[i] == '#') pic->pic[pic->h * len+i] = 1; + } +} + +void print_pic(struct pic_t *pic) { + for (int y = 0; y < pic->h; ++y) { + for (int x = 0; x < pic->w; ++x) { + printf("%c", pic->pic[y * pic->h + x] == 1 ? '#' : '.'); + } + printf("\n"); + } +} diff --git a/day20/test.txt b/day20/test.txt @@ -0,0 +1,7 @@ +..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..# + +#..#. +#.... +##..# +..#.. +..###