commit 8c79cf09b68ad7bc23efb3b93abf60e36fa0d28e
parent e584643b1730db34a12cc42cc47f34b48aa9de36
Author: bsandro <email@bsandro.tech>
Date: Mon, 11 Dec 2023 22:59:23 +0200
day 11 p1 with me hopelessly behind on everything
Diffstat:
5 files changed, 444 insertions(+), 0 deletions(-)
diff --git a/day11/Makefile b/day11/Makefile
@@ -0,0 +1,25 @@
+NAME=$(shell basename ${PWD})
+SRC=$(wildcard *.c)
+DEPS:=$(wildcard *.h)
+OBJ:=$(SRC:.c=.o)
+CFLAGS=-O2 -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
diff --git a/day11/input.txt b/day11/input.txt
@@ -0,0 +1,140 @@
+......#.....#.........................#...........#..........#.....#.......#..............#.................................................
+.....................#....................................................................................#........#........#.......#.......
+.........................................................#............................#..................................................#..
+.........................#.......#..............................#............................#.................#............................
+..................#...................................................................................#.....................................
+...........................................#....................................#.................................................#.........
+...........................................................#..........#..........................#..........................................
+............#...............#..............................................................#................................................
+...#.................#.............................................................................................#........................
+........#..........................#.................#....................#.................................................................
+.................#............................#..................................#..................#...........................#...........
+........................................#.................#............................#...................#...............................#
+...............................#..................#..................................................................................#......
+..............#.........#...................................................................................................................
+......................................................#....................................#.....#....................#.....................
+#..................#........#.............#......................#.................#.....................#.....................#............
+............................................................................................................................................
+........#....................................................................................................#......................#.....#.
+................................#............#...............#...........#............#.....................................................
+.................................................................................................................#..........................
+................#..........................................................................#................................................
+.....................#.................#..........#............................#.............................................#..............
+......#................................................#....................................................................................
+...................................#................................#..................#............#.........#........................#....
+..........................................#.................................................................................................
+............................................................................................#.........................#.....................
+.............................#..............................................................................................................
+#...............#......#.................................#..........................#.............................#.........................
+.................................#.......................................................................#...................#..............
+....#.....................................................................#....................#..........................................#.
+............................................#.........#..........................#...............................................#..........
+............................................................................................................................................
+.........................#....................................#........................................#................#...................
+.......#...........................#..................................................#.....#...............................................
+.................................................................................................................#...................#......
+.............#...............................................................#..................#...........................#...............
+..................#.........................................................................................................................
+.........#............................#........#.........#.........#................................................#...................#...
+............................................................................................................................................
+......................#..................................................................................#.......................#..........
+...........................................................................#........#............#..........................................
+............#..............#.........................................#......................................................................
+.....#............#.................................#......................................#...............................#...............#
+............................................................................................................................................
+#.........................................#.................................................................................................
+........................#..........#...........#..............#...................................#.........................................
+........................................................#..........................#.......................#....................#...........
+...........................................................................#................................................................
+..#....................................#...........................#...................#....................................................
+.......#............................................#................................................................#......................
+..............#............#...............................................................#..................#.............................
+......................................................................#.........#....................................................#......
+............................................................................................................................................
+..........#..........#.........................#............#...........................#........#..........................................
+...........................................................................#............................#....................#...........#..
+.............................#..................................................................................#...........................
+..........................................#.................................................................................................
+.....#..........#................#..................................................#......#.............................#......#...........
+............................................................................................................................................
+.#.........#..............#..................#........#..........#.....................................#....................................
+........................................#.....................................................#..........................................#..
+..............................#...........................................#................................#.........#......................
+............................................................................................................................................
+............................................................................................................................................
+......#...........................#.................#...........................#.......................#................#.............#....
+..........................#.............................................#...................................................................
+................................................................#...........................................................................
+........................................#...............#.............................#.....#......................................#........
+......................#...........................................................................#..............#..........................
+..................................................#.........#......#...........................................................#........#...
+..#..............#..........................#................................#.....#........................................................
+............................................................................................................................................
+....................................#.................................#........................#.......#......#..........#..................
+.......#...............................................................................#...................................................#
+...............#.......................................#........................................................................#...........
+...........................................#................................................................................................
+.......................#..............#............................................#................................................#.......
+............................................................................................................................................
+.#..........................#............................#..................................#..........#......#.............................
+............................................................................................................................................
+............................................................................................................................................
+............#......#.....#.......................#...............................................#..........................................
+..........................................................................................#..............#..................................
+.....................................................................#............................................#.........................
+................................................................................#.........................................#.................
+....#..........#..................................................................................................................#.....#...
+........................................................#...................................#......#........................................
+........#...........#......#......................#.....................#............#......................................................
+...................................#..............................#...........................................................#.............
+.................................................................................................................#..........................
+.........................................#............#....................#..................#......................................#......
+........................#.....................#...........................................................................................#.
+...................................................................................................#.....#..................................
+............................................................................................................................................
+.....................................#...................#...............................................................#.....#............
+.....................#........................................#.......................#.....................................................
+.............#............#.....#...........................................#......................................................#.......#
+.......#...................................................................................#..............#.................................
+#.......................................#.............................#.............................................#.......................
+...................................#............................#..............................#......................................#.....
+..............................................................................................................#.............#...............
+........................................................................................#..........#........................................
+...............#..........................#..............#..........#.......................................................................
+......#..................................................................#.......................................#.................#........
+................................................#...........................................................#.................#.............
+#...................#........#...................................................................#..........................................
+............................................#...................................#...........#.......................#.......................
+........#...................................................................................................................................
+.....................................#............#.........#......#................................................................#.......
+.................#....................................................................#..............#......................................
+................................................................................................#.........................#.................
+...........................#..............#.................................................................................................
+..........#.................................................................................................................................
+................................................#.......#...........................#........#....................#................#........
+.......................................#.........................#..................................#......#................................
+..................................#.................#....................................#.................................#...............#
+...........................................#................................................................................................
+......#.....................................................................................................................................
+......................#.......#......................................#......#...............................................................
+................................................#......#...............................................................#................#...
+..............#................................................................................#.............................#..............
+..........................................#.............................#........................................#..........................
+.........................#...........................................................................#..............................#.......
+....................................#.......................................................................................................
+....#...............#..............................................#....................#...........................#.......................
+..........................................................#.................................................................................
+..........................................................................#.......................#.........................................
+..............#.............................................................................................#...................#.........#.
+.......................#.....................#.......................#............................................#.........................
+...............................#...................................................#........................................................
+.................#......................................................................#............................................#......
+.......#...................................................#................#........................#..................#...................
+.#...........#..............#...............................................................................................................
+.....................#............................#.................#............#..............#...........................................
+...........................................#...........#.................#.................................#................................
+...............................#......................................................#....................................................#
+.............................................................................#..............................................................
+.................................................................................................................................#..........
+.......................#...........#..........#............#.....#........................#.............................................#...
+.#..........#...............#......................................................#......................#......#..........................
diff --git a/day11/main.c b/day11/main.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <time.h>
+#include <string.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 11\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/day11/puzzle.c b/day11/puzzle.c
@@ -0,0 +1,239 @@
+#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>
+
+#define MAX(a,b) (((a)>(b))?(a):(b))
+#define MIN(a,b) (((a)<(b))?(a):(b))
+
+#define STR_LEN 2048
+
+// either row or column
+typedef struct Line {
+ char *tiles;
+ size_t tiles_size;
+ struct Line *next;
+} Line;
+
+Line * make_line() {
+ Line *l = malloc(sizeof(Line));
+ memset(l, 0, sizeof(Line));
+ return l;
+}
+void print_lines(Line *first) {
+ Line *l = first;
+ while (l!=NULL) {
+ for (size_t i=0; i<l->tiles_size; ++i) {
+ printf("%c", l->tiles[i]);
+ }
+ printf("(%zu)\n", l->tiles_size);
+ l = l->next;
+ }
+}
+void free_lines(Line *first) {
+ Line *l = first;
+ while (l!=NULL) {
+ Line *l1 = l->next;
+ free(l);
+ l = l1;
+ }
+}
+bool is_line_empty(Line *line) {
+ for (size_t i=0; i<line->tiles_size; ++i) {
+ if (line->tiles[i]!='.') return false;
+ }
+ return true;
+}
+
+typedef struct Vec2 {
+ int x, y;
+ struct Vec2 *next;
+} Vec2;
+Vec2 * make_vec2(int x, int y) {
+ Vec2 *v = malloc(sizeof(Vec2));
+ v->x = x;
+ v->y = y;
+ v->next = NULL;
+ return v;
+}
+void print_vec2(Vec2 *v) {
+ Vec2 *v1 = v;
+ while (v1!=NULL) {
+ printf("x:%2d,y:%2d (%p)\n",v1->x, v1->y, v1);
+ v1 = v1->next;
+ }
+}
+int calc_dist(Vec2 *v1, Vec2 *v2) {
+ int dx = MAX(v1->x, v2->x) - MIN(v1->x, v2->x);
+ int dy = MAX(v1->y, v2->y) - MIN(v1->y, v2->y);
+ return dx+dy;
+}
+
+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;
+ int cols = 0;
+ int rows = 0;
+ Line *rows_list = NULL;
+ Line *rows_last = NULL;
+
+ while (fgets(buf, STR_LEN, infile) != NULL) {
+ int len = strlen(buf)-1; // ignore \n
+ if (cols==0) cols = len;
+ if (cols!=len) printf("width mismatch\n");
+
+ // filling and expanding rows
+ Line *row = make_line();
+ row->tiles = malloc(len*sizeof(char));
+ row->tiles_size = len;
+ memcpy(row->tiles, buf, len*sizeof(char));
+ if (rows_list==NULL) rows_list=row;
+ if (rows_last!=NULL) rows_last->next = row;
+ rows_last = row;
+
+ // dupe if needed (also meh copypasta)
+ if (is_line_empty(row)) {
+ Line *row = make_line();
+ row->tiles = malloc(len*sizeof(char));
+ row->tiles_size = len;
+ memcpy(row->tiles, buf, len*sizeof(char));
+ if (rows_list==NULL) rows_list=row;
+ if (rows_last!=NULL) rows_last->next = row;
+ rows_last = row;
+ ++line_num;
+ }
+
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+ rows = line_num;
+
+ //printf("field: %dx%d\n", rows, cols);
+ //print_lines(rows_list);
+
+ // make some 2d area
+ size_t map_size = rows*cols*sizeof(char);
+ //printf("map_size: %zu\n", map_size);
+ char *map = malloc(map_size);
+ memset(map, 0, map_size);
+ Line *l = rows_list;
+ int cur_row = 0;
+ while (l!=NULL) {
+ for (size_t i=0; i<l->tiles_size; ++i) {
+ map[cur_row*l->tiles_size+i] = l->tiles[i];
+ }
+ l = l->next;
+ ++cur_row;
+ }
+
+ // fill cols_list and expand
+ Line *cols_list = NULL;
+ Line *cols_last = NULL;
+ int cols_new = 0;
+ for (int x=0; x<cols; ++x) {
+ Line *col = make_line();
+ col->tiles = malloc(rows*sizeof(char));
+ col->tiles_size = rows;
+ for (int y=0; y<rows; ++y) {
+ if (y*cols+x>=(int)map_size) {
+ printf("x:%d,y:%d,offset:%d invalid\n", x, y, y*cols+x);
+ }
+ col->tiles[y] = map[y*cols+x];
+ }
+ if (cols_list==NULL) cols_list = col;
+ if (cols_last!=NULL) cols_last->next = col;
+ cols_last = col;
+ ++cols_new;
+
+ // dupe if needed (also meh copypasta)
+ if (is_line_empty(col)) {
+ Line *col1 = make_line();
+ col1->tiles = malloc(rows*sizeof(char));
+ col1->tiles_size = rows;
+ memcpy(col1->tiles, col->tiles, rows*sizeof(char));
+ if (cols_list==NULL) cols_list=col1;
+ if (cols_last!=NULL) cols_last->next = col1;
+ cols_last = col1;
+ ++cols_new;
+ }
+ }
+ cols = cols_new;
+ //printf("field: %dx%d\n", rows, cols);
+
+ map_size = rows*cols*sizeof(char);
+ map = realloc(map, map_size);
+ memset(map, 0, map_size);
+
+ //printf("------\n");
+ //print_lines(cols_list);
+
+ l = cols_list;
+ int cur_col = 0;
+ while (l!=NULL) {
+ for (size_t y=0; y<l->tiles_size; ++y) {
+ assert(y*cols+cur_col<map_size);
+ map[y*cols+cur_col] = l->tiles[y];
+ }
+ l = l->next;
+ ++cur_col;
+ }
+
+ Vec2 *galaxies = NULL;
+ Vec2 *galaxies_last = NULL;
+
+ // print map
+ // collect galaxies
+ //printf("map:\n");
+ for (int y=0;y<rows;++y) {
+ for (int x=0;x<cols;++x) {
+ //printf("%c", map[y*cols+x]);
+ if (map[y*cols+x]=='#') {
+ Vec2 *g = make_vec2(x, y);
+ if (galaxies==NULL) galaxies = g;
+ if (galaxies_last!=NULL) galaxies_last->next = g;
+ galaxies_last = g;
+ }
+ }
+ //printf("\n");
+ }
+ // clean stuff
+ free_lines(rows_list);
+ free_lines(cols_list);
+ rows_list = NULL;
+ rows_last = NULL;
+ cols_list = NULL;
+ cols_last = NULL;
+
+ //print_vec2(galaxies);
+
+ *result1 = 0;
+ Vec2 *g1 = galaxies;
+ while (g1!=NULL) {
+ Vec2 *g2 = g1;
+ while (g2!=NULL) {
+ if (g1!=g2) {
+ *result1 += calc_dist(g1, g2);
+ }
+ g2 = g2->next;
+ }
+ g1 = g1->next;
+ }
+
+ // mutiny! ignoring feof/ferror.
+ fclose(infile);
+
+ (void)result1;
+ (void)result2;
+}
diff --git a/day11/test.txt b/day11/test.txt
@@ -0,0 +1,10 @@
+...#......
+.......#..
+#.........
+..........
+......#...
+.#........
+.........#
+..........
+.......#..
+#...#.....
