advent2023

Advent of Code 2023 solutions
git clone git://bsandro.tech/advent2023
Log | Files | Refs | LICENSE

commit cd360b8395d441a8a5cff9f379ff63bc14bb5f31
parent 7cb3f5e9385a2e2a359c9b0216d405211b46afe9
Author: bsandro <email@bsandro.tech>
Date:   Sat, 16 Dec 2023 18:21:44 +0200

day 16 p1

Diffstat:
Aday16/Makefile | 28++++++++++++++++++++++++++++
Aday16/input.txt | 110+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday16/main.c | 31+++++++++++++++++++++++++++++++
Aday16/puzzle.c | 292+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday16/test.txt | 10++++++++++
5 files changed, 471 insertions(+), 0 deletions(-)

diff --git a/day16/Makefile b/day16/Makefile @@ -0,0 +1,28 @@ +NAME=$(shell basename ${PWD}) +SRC=$(wildcard *.c) +DEPS:=$(wildcard *.h) +OBJ:=$(SRC:.c=.o) +CFLAGS=-O0 -g -std=c11 -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 + +test2: $(NAME) + @./$(NAME) test2.txt diff --git a/day16/input.txt b/day16/input.txt @@ -0,0 +1,110 @@ +\.....................\.......................|..../......-.........../.|.....\.............|..........|..\... +.../...................\..................../...|.......|........||...................../...........\......... +././....|......./................\............|..\...........-....../............../|........-................ +....\..\...........-/..|......|......\............|............../.................-........./...-...|.......\ +..................................|.\.......|...../.........................-...../......\..|...............\. +.....\.............................................|../.\............../--.......................\............ +|.......-.|........\.................\..............|........./....\.........|...................\-.-...|..... +....\........./....-.........................--.....\..../......................|.\......................\...- +\..-..../.....|..........\......................-|......|...................../...../........./...........-... +........................\.\|......../........../......................\.............|./../.................... +.....\...................|.............................|......-........|.........-./.../.|.................... +..-................./.........................................\..\........-..-........-.......\../............ +-................-............................\................./..--................-............../.|....... +..-.....|.............|................./.......-.-........................-............-...........\......... +..........|..........................-...|..\...............................................\-....\........... +/................../..........|....\..-......................../....\...\..........-....../.........../.....\. +................\....-................-|.\...-...........-.....-........\..........................\.......... +...................................\../..|.../../...........................\.........../.\-......|.........-. +/....|....|..........................\............./.....|/................./....-......................-..... +....-.............../.....|...........|../......\../.............../........................|............./... +......./..............|./../.................-.\.........../.....................|.........../........\....... +...................-...............\/.......|........|....................../.......................-/......\. +................\...../....-/......-.........-.....\/.\...............\....../...-....|......|.........\...... +....-.........-.........................-......................../.......|...............................\.... +......../..................|...../......\..\..-|-..../..............|......../............|.-.......-......... +......./............-..........-............................../.........................|\..-..-\.\......-..\. +.\-.....|......................-..\................/.-................|.\..............\..................|... +-..........................-............../.|.-......\......-..-...../......./................................ +....|.................................................\....|..........\...................-......|........./.. +................../...........-..............\......................................|.-........|.............. +...-............|..............-...........-.\.......................|..|..../......................../.|....- +.......-..-......./...../.........-.......\.....-.../............-./......../.../............-.....|...|...... +...............|.........../..........|/..........|..........-.-...../...../..|..........\.....-./.|./....|... +.........|......................\.|.....|......................-.-........|.............................-...|. +.-...|..\...-...............\..............\......./........-............/.-..\........../...../....-....\.... +...........\.-.......|.......|....-.............|-.|........../..../...\....\............|.|..|\.............. +.....................|.\....|......|../...\......|........................\......|.......-./..../............. +......................\--................................\.................|................-................. +-...............\...-.....................................-.\...../....\...........................|.......... +.....|.......\.......................-/...\..-.........-..../\|..................\........-................... +..|........./....|..-./..\..\................-|..........\../......\...............\............\............| +......-................../.............|.............\................................-..\...../........-..... +....................../......../..\.-.........................|....\..|...\...../../.....|............../..... +...\................................/..............................\........|.........\.-............\........ +/.................../................-...........-.|.............\.................................|.....-.... +.|...-..|/./../.........-./.............................................../..........-.........-.|./.......... +..../..................|......................|../..........\........-......../.........\...|................. +........./..................|..-..........|\............\......-..-..\...|....|.....................|....-.... +.....|/....|........\.........-................../..........|............|...........-.....|......./......//.. +..........\.|../...|........................\.........\.|......||....-...............\\.....|.|..............| +............-................|.....-....||......../.../.......................|..\...........\................ +...............-..../......-..../.......|-.....-.....\..................................../..|................ +/......-...............\/...././..................\..................\..........-......................|...... +...................\.....\.................\...|.................-............/........-..............\./..... +.-.\....\........\........-../.-............../...../..-..|...................../.-.....\.....-........../..\. +|...|...............................|............../.............../....................|...../............... +....../....../...|..............-.-........-..|.../....................\|.....\......................|....../. +...\\.......|...|-............|..........-...........................................\/...../..-.-............ +.........|.............|..|......\............\...............|......\......\.............\...\-.......\.....\ +...........\..-.|.......|\..\..................-........\/...............................-.................... +...\.................\..............................................\...............\.......-.../............. +..\.............\....---....................//.......................................|./.............../\..... +.\...........|..................................\........-......|.........\.................-........-........ +..............-...............-.../....-........|.....-../......................./..../........../../--..\.... +.........-......\......-.........../...\./.|.................\...................--..-........|..\......\....| +....../.........................................|...../........../..............\\...-/.......-......\..\..... +.........../...\.|..................../.\.................|......\.\..|.........../...../.....\.\...........|. +..../\..-...../.............................../..../............................-...-......\...........\...... +..-..\.............................\...........|..........|.........|..........................-......./...... +-..|.................-\.....\...............\/.....|...........................././...\......\.......\...-.... +......\..............|..|..............-............../....................-....\\........\....|.............. +|.............\....\./.....-|-....\.....\..............\/........-.|..|...........-..\......-..../.......|.... +............................-.......................|........................../................|............. +/................|../............\/.....\/....-.....\......\...../|..\..........|............../.............. +.|....../...../....................../..|.....................-................./...../-.........-............ +......................\|........../......./..\........\.........-......../.........../.|/.......\.../......... +...............\......-|............\..\....../.........\.....|...|\............/............\.\..|.......\... +......|...........\....../....\./......./-....\../.......\...-...............\./...\.....-.......-..../....... +...|..|.............................\.....-.|........./......../......................-......./............\.. +.....|........\.........|...-.-.........\..../....../..-.......-...............\..../.....-..../.............. +........./.\/........................-..........\.....................|.......-..............\./.\............ +..../................/................................|.....||..............\........-...............|........ +....\./.........../\-.....-...\............//.\..............\...../................|.....\..-................ +..../|........./............|.....................|......................-..|...............................\. +..................\............................\.......\.........-.............|...../.-.............-......|. +..............|.-...........................\.\./.......\........../...\................/....-................ +.......|................/-............\............/...........-..../...........\......../...\.......\........ +..............|..../......................-...........-..\.................................................-.. +..............................-..-................-.......-.................-..........\.../...............|.. +......-.........-........................./.....................\....|........................................ +.....\........./.....-.................../................|...................|........................|...... +........../.../........................./.|................-...........\...........-....|..................... +.....-.......\././/.......|..............|......../..\...........\.............................-......|../-.-. +........|-....-....................\.....|\...\/.....\........\......./..........|.\-..|...................... +../...-...-...|...../............\.......................-..........\...\.....-...\...............|....../...| +............|..\....|..................\/...................../../....|...................|.............../... +.............-................./............|.......|............\....................................\.-..... +-...../|..............-......\..../..................|..\....-............................................\... +........|.........-........\................/....\..................../.|...................................|. +.....|................./.........-|\...-...................|....-................-......../...............|..- +.|.........|...........|...-.............................\............................|................\...... +....|.....-......|......./.-.|...........\..-........|.........................-....-..-.....|................ +........................................\.....................-.../........................../../..........|.. +-................/....\.......//....-........................../.\.........-......./..|\..........\........... +-............................./......................................../-...........................\|........ +........................................../-.....//......\......\...........\........|./....../.......--...... +../..............-....../......../................../......./....-...........|../.......\.\.......-......./..\ +..............-............../......|.........-...............|................................-..........\... +.....................\..........|..\......|...............................................-................... +...../..|.../.........|.../.......-...................................\.....................................|. diff --git a/day16/main.c b/day16/main.c @@ -0,0 +1,31 @@ +#include <stdio.h> +#include <time.h> +#include <string.h> +#include <threads.h> + +void puzzle(const char *filename, long long *res1, long long *res2); +//void puzzle_test(const char *filename, long long *res1, long long *res2); + +int main(int argc, char *argv[]) { + printf("Advent of Code: day 16\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/day16/puzzle.c b/day16/puzzle.c @@ -0,0 +1,292 @@ +#define _DEFAULT_SOURCE + +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <strings.h> +#include <assert.h> +#include <stdbool.h> +#include <inttypes.h> + +#define STR_LEN 2048 + +typedef enum Dir { + DIR_UP, + DIR_DOWN, + DIR_LEFT, + DIR_RIGHT +} Dir; + +typedef struct Pos { + int x, y; + Dir dir; + struct Pos *next; +} Pos; + +typedef struct Map { + int w, h; + char *area; + size_t size; // essentially width*height*sizeof(char) + Pos start; +} Map; + +typedef struct Pair { + Pos one; + Pos two; +} Pair; + +// standard issue linked list; +typedef struct Visited { + Pos *first; + Pos *last; +} Visited; + +void visited_add(Visited *visited, Pos p) { + Pos *add = malloc(sizeof(Pos)); + memset(add, 0, sizeof(Pos)); + *add = p; + if (visited->first==NULL) visited->first = add; + if (visited->last!=NULL) visited->last->next = add; + visited->last = add; +} + +bool visited_has(Visited *visited, Pos p) { + Pos *cur = visited->first; + while (cur!=NULL) { + if (cur->x==p.x && cur->y==p.y && cur->dir==p.dir) { + return true; + } + cur = cur->next; + } + return false; +} + +Pos get_next_empty(Pos cur) { + Pos p = cur; + switch (cur.dir) { + case DIR_RIGHT: + p.x++; + break; + case DIR_LEFT: + p.x--; + break; + case DIR_UP: + p.y--; + break; + case DIR_DOWN: + p.y++; + break; + } + return p; +} + +Pos get_next_mirror(Pos cur, char sym) { + Pos p = {0}; + if (sym == '\\') { + switch (cur.dir) { + case DIR_RIGHT: + p.dir = DIR_DOWN; + p.x = cur.x; + p.y = cur.y + 1; + break; + case DIR_LEFT: + p.dir = DIR_UP; + p.x = cur.x; + p.y = cur.y - 1; + break; + case DIR_UP: + p.dir = DIR_LEFT; + p.x = cur.x - 1; + p.y = cur.y; + break; + case DIR_DOWN: + p.dir = DIR_RIGHT; + p.x = cur.x + 1; + p.y = cur.y; + break; + } + } else if (sym == '/') { + switch (cur.dir) { + case DIR_RIGHT: + p.dir = DIR_UP; + p.x = cur.x; + p.y = cur.y - 1; + break; + case DIR_LEFT: + p.dir = DIR_DOWN; + p.x = cur.x; + p.y = cur.y + 1; + break; + case DIR_UP: + p.dir = DIR_RIGHT; + p.x = cur.x + 1; + p.y = cur.y; + break; + case DIR_DOWN: + p.dir = DIR_LEFT; + p.x = cur.x - 1; + p.y = cur.y; + break; + } + } + return p; +} + +Pair get_next_splitter(Pos cur, char sym) { + Pair p = {.one={-1},.two={-1}}; + if (sym=='-') { + switch (cur.dir) { + case DIR_RIGHT: + p.one = cur; + p.one.x++; + break; + case DIR_LEFT: + p.one = cur; + p.one.x--; + break; + case DIR_UP: + case DIR_DOWN: + p.one = cur; + p.one.x++; + p.one.dir = DIR_RIGHT; + p.two = cur; + p.two.x--; + p.two.dir = DIR_LEFT; + break; + } + } else if (sym=='|') { + switch (cur.dir) { + case DIR_RIGHT: + case DIR_LEFT: + p.one = cur; + p.one.y--; + p.one.dir = DIR_UP; + p.two = cur; + p.two.y++; + p.two.dir = DIR_DOWN; + break; + case DIR_UP: + p.one = cur; + p.one.y--; + break; + case DIR_DOWN: + p.one = cur; + p.one.y++; + break; + } + } + return p; +} + +bool is_valid(Map *map, Visited *visited, Pos cur) { + return cur.x>=0 && cur.y>=0 && cur.x<map->w && cur.y<map->h && !visited_has(visited, cur); +} + +Pair get_next(Map *map, Pos cur) { + char sym = map->area[map->w*cur.y+cur.x]; + Pair p = {.one={-1},.two={-1}}; + switch (sym) { + case '.': + p.one = get_next_empty(cur); + break; + case '/': + case '\\': + p.one = get_next_mirror(cur, sym); + break; + case '|': + case '-': + p = get_next_splitter(cur, sym); + break; + default: + printf("invalid symbol %c\n", sym); + exit(-1); + } + return p; +} + +void traverse(Map *map, Map *energized, Visited *visited, Pos start) { + if (visited_has(visited, start)) { + return; + } + // mark entry as energized + energized->area[energized->w*start.y+start.x] = '#'; + visited_add(visited, start); + while (1) { + Pair p = get_next(map, start); + bool valid1 = is_valid(map, visited, p.one); + bool valid2 = is_valid(map, visited, p.two); + if (valid1 && valid2) { + visited_add(visited, p.one); + energized->area[energized->w*p.one.y+p.one.x] = '#'; + start = p.one; + //traverse(map, energized, visited, p.one); + traverse(map, energized, visited, p.two); + } else if (valid1) { + visited_add(visited, p.one); + energized->area[energized->w*p.one.y+p.one.x] = '#'; + start = p.one; + } else if (valid2) { + visited_add(visited, p.two); + energized->area[energized->w*p.two.y+p.two.x] = '#'; + start = p.two; + } else { + break; + } + } +} + +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; + Map map = {0}; + + while (fgets(buf, STR_LEN, infile) != NULL) { + int w = strlen(buf)-1; + if (map.w==0) map.w=w; + if (map.w!=w) printf("width mismatch!\n"); + map.size += map.w*sizeof(char); + map.area = realloc(map.area, map.size); + memcpy(map.area+map.w*line_num, buf, w); + + ++line_num; + bzero(buf, STR_LEN); + } + map.h = line_num; + map.start = (Pos){.x=0,.y=0,.dir=DIR_RIGHT}; + + Map energized = {0}; + energized.size = map.size; + energized.w = map.w; + energized.h = map.h; + energized.area = malloc(energized.size); + memset(energized.area, '.', energized.size); + + Visited visited = {0}; + + traverse(&map, &energized, &visited, map.start); + + *result1 = 0; + printf("energized %dx%d:\n", energized.w, energized.h); + for (int y=0; y<energized.h; ++y) { + for (int x=0; x<energized.w; ++x) { + //printf("%c", energized.area[y*energized.w+x]); + if (energized.area[y*energized.w+x]=='#') { + (*result1)++; + } + } + //printf("\n"); + } + + // mutiny! ignoring feof/ferror. + fclose(infile); + (void)result1; + (void)result2; +} diff --git a/day16/test.txt b/day16/test.txt @@ -0,0 +1,10 @@ +.|...\.... +|.-.\..... +.....|-... +........|. +.......... +.........\ +..../.\\.. +.-.-/..|.. +.|....-|.\ +..//.|....