commit aecd7a94862d9b346bfef2e0e247c4b0ec43cd9f
parent 6eaa7994d753e265e3c67e9890db44f5ddbf0ee8
Author: bsandro <[email protected]>
Date: Sat, 4 Dec 2021 21:40:32 +0200
Day 04, puzzle 1
Diffstat:
5 files changed, 913 insertions(+), 0 deletions(-)
diff --git a/day04/Makefile b/day04/Makefile
@@ -0,0 +1,26 @@
+NAME=$(shell basename ${PWD})
+CC=cc
+SRC=$(wildcard *.c)
+DEPS:=$(wildcard *.h)
+OBJ:=$(SRC:.c=.o)
+
+CFLAGS=-O0 -std=c99 -g -Werror -Wall -Wextra -I.
+
+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/day04/input.txt b/day04/input.txt
@@ -0,0 +1,601 @@
+72,86,73,66,37,76,19,40,77,42,48,62,46,3,95,17,97,41,10,14,83,90,12,23,81,98,11,57,13,69,28,63,5,78,79,58,54,67,60,34,39,84,94,29,20,0,24,38,43,51,64,18,27,52,47,74,59,22,85,65,80,2,99,70,33,91,53,93,9,82,8,50,7,56,30,36,89,71,21,49,31,88,26,96,16,1,75,87,6,61,4,68,32,25,55,44,15,45,92,35
+
+58 60 65 4 91
+73 31 80 83 44
+98 47 33 21 25
+76 6 41 94 50
+55 30 52 11 36
+
+ 8 27 21 18 94
+59 3 47 1 64
+67 16 90 20 83
+26 43 87 82 4
+19 93 89 48 72
+
+28 31 21 56 35
+63 98 25 65 61
+46 11 91 24 34
+76 22 15 0 87
+83 80 39 12 71
+
+48 9 95 18 12
+67 20 40 29 51
+ 0 85 21 69 89
+71 81 97 64 13
+75 24 65 50 56
+
+ 1 27 24 93 42
+47 71 21 91 88
+39 7 65 64 51
+28 16 15 25 56
+48 23 32 20 22
+
+26 37 62 13 82
+53 54 16 50 75
+42 18 51 64 60
+25 47 71 38 77
+27 57 29 76 40
+
+97 20 68 90 70
+42 96 62 49 27
+56 67 12 13 94
+71 35 31 54 17
+73 3 5 23 19
+
+43 93 19 7 80
+88 37 51 49 58
+29 97 17 94 65
+61 22 75 98 85
+28 73 84 47 1
+
+96 99 82 7 91
+43 32 48 39 60
+49 51 15 30 11
+16 72 52 69 18
+79 95 41 68 59
+
+90 3 81 44 99
+ 9 40 94 19 37
+41 52 43 83 46
+ 2 42 26 24 70
+49 74 34 66 77
+
+59 83 91 44 0
+62 85 69 18 8
+74 5 94 48 32
+50 46 25 6 96
+87 41 75 22 31
+
+36 61 69 96 87
+77 60 49 32 45
+92 97 34 21 70
+31 62 6 63 2
+56 93 26 54 85
+
+30 96 54 85 82
+29 92 1 74 42
+63 26 65 34 98
+87 91 6 53 64
+62 45 13 50 56
+
+ 3 67 61 56 23
+34 48 39 76 37
+44 83 35 72 29
+70 45 55 47 4
+31 92 6 99 59
+
+ 9 42 99 80 14
+81 57 72 63 18
+19 67 25 90 58
+ 0 4 51 52 69
+93 60 73 28 23
+
+ 5 27 68 24 35
+69 67 49 1 79
+73 64 4 42 32
+55 74 44 90 45
+92 43 33 2 3
+
+ 7 45 24 51 33
+71 66 6 13 23
+77 55 76 48 44
+39 70 43 36 32
+88 5 69 47 92
+
+45 40 5 93 80
+64 37 10 35 4
+11 6 75 30 38
+74 44 26 90 99
+ 1 81 8 50 32
+
+92 71 59 47 32
+45 65 68 55 28
+99 88 17 36 82
+16 22 61 48 93
+29 5 69 24 51
+
+88 85 54 41 92
+10 67 40 4 30
+29 45 32 47 51
+96 81 94 58 34
+39 72 7 46 98
+
+52 33 11 60 69
+19 9 88 93 75
+82 45 72 48 44
+85 61 87 79 26
+71 80 21 0 3
+
+60 1 57 93 81
+17 32 61 21 4
+76 24 46 98 33
+ 9 84 91 6 23
+ 5 59 52 96 54
+
+22 35 20 41 4
+57 8 9 97 10
+19 25 12 65 53
+ 5 50 91 32 23
+58 96 15 7 78
+
+90 78 31 47 88
+81 56 55 95 10
+60 42 68 34 57
+53 64 85 50 35
+48 16 89 93 77
+
+64 4 0 7 16
+58 50 37 98 34
+85 71 75 22 57
+81 91 6 86 19
+61 63 95 40 3
+
+66 88 55 0 32
+68 9 98 73 36
+15 45 39 67 6
+91 11 79 23 84
+12 80 62 14 17
+
+79 31 43 75 97
+54 78 87 60 99
+41 34 32 61 26
+44 37 20 12 18
+16 73 10 71 22
+
+92 83 15 36 27
+28 21 35 42 18
+60 87 41 38 95
+45 10 70 5 80
+11 30 56 17 61
+
+63 25 57 42 14
+24 71 2 11 93
+56 73 16 47 28
+87 64 8 27 83
+21 50 78 48 62
+
+18 29 90 1 16
+39 72 21 88 55
+19 13 69 83 71
+ 7 97 43 58 61
+23 96 9 33 81
+
+36 13 32 1 11
+57 17 91 76 72
+29 83 35 68 90
+87 12 39 19 0
+99 31 16 25 43
+
+ 5 52 64 73 40
+ 0 1 51 3 14
+61 91 55 30 88
+33 83 31 13 71
+24 97 36 19 53
+
+81 15 67 72 78
+20 21 40 96 37
+13 5 33 83 66
+22 61 91 56 84
+35 86 75 41 46
+
+28 29 73 84 26
+42 54 3 15 12
+34 16 62 91 30
+53 13 5 46 55
+67 18 1 59 24
+
+16 39 26 11 67
+36 20 62 27 78
+85 25 9 87 66
+ 6 70 60 98 59
+94 46 17 81 10
+
+35 86 49 59 38
+88 54 68 17 87
+10 9 90 30 62
+82 20 32 77 76
+81 83 79 0 67
+
+26 9 63 23 45
+22 44 36 60 4
+84 91 54 6 78
+94 2 62 61 31
+52 88 42 21 29
+
+ 1 32 44 0 9
+13 36 26 6 17
+50 74 14 51 88
+25 10 73 43 16
+47 68 34 2 81
+
+74 67 38 24 32
+46 53 63 18 82
+33 41 48 90 5
+56 3 20 99 17
+96 94 59 21 87
+
+49 72 39 25 62
+59 99 27 53 98
+33 46 92 38 8
+18 82 90 70 20
+ 3 2 54 0 75
+
+54 34 45 0 19
+95 11 27 62 50
+ 3 77 79 17 81
+74 57 40 83 47
+88 72 39 92 16
+
+65 1 91 71 67
+81 23 34 48 90
+28 92 84 11 3
+ 5 8 61 16 76
+83 46 24 55 82
+
+42 87 55 23 59
+79 54 81 48 95
+61 16 44 13 91
+53 98 72 30 88
+65 69 83 36 64
+
+45 80 47 27 78
+54 36 16 75 1
+17 26 68 28 39
+43 87 49 0 89
+56 24 7 85 92
+
+18 50 95 70 49
+44 47 69 92 54
+96 28 79 67 16
+13 31 29 98 14
+53 20 5 66 25
+
+88 33 27 97 67
+20 69 22 35 0
+50 73 70 52 91
+71 32 48 21 65
+ 3 5 15 30 86
+
+77 85 98 6 11
+15 53 21 89 67
+51 40 62 8 36
+37 69 47 24 29
+39 63 64 72 44
+
+13 7 80 86 29
+45 91 82 41 42
+69 74 12 68 38
+84 51 6 10 14
+57 26 62 17 24
+
+31 88 98 2 11
+33 40 23 30 43
+25 16 50 41 22
+12 51 99 6 89
+91 66 90 97 32
+
+22 74 70 98 54
+25 20 76 40 38
+21 99 69 10 41
+11 59 46 61 36
+87 50 49 84 78
+
+57 25 39 22 86
+37 8 61 78 73
+49 30 95 3 44
+18 1 58 91 46
+24 64 17 13 60
+
+61 10 14 53 83
+32 28 66 65 40
+63 86 48 76 6
+92 69 95 24 55
+59 71 72 30 33
+
+47 76 18 53 56
+37 42 9 28 2
+ 0 80 99 48 27
+79 20 15 5 54
+ 3 7 71 89 87
+
+31 8 16 28 79
+56 77 66 59 36
+ 9 99 85 57 6
+67 82 73 87 91
+37 52 43 58 81
+
+ 9 2 96 51 64
+68 30 36 3 66
+33 57 41 83 52
+90 84 54 20 56
+14 88 62 76 38
+
+17 86 75 54 5
+13 59 68 87 74
+44 62 31 57 98
+ 7 24 36 71 76
+69 23 19 70 73
+
+55 40 1 98 24
+85 29 39 72 3
+80 28 94 67 65
+14 70 49 97 90
+11 2 74 44 48
+
+49 91 63 99 67
+ 1 69 29 22 81
+58 77 62 74 16
+ 9 68 38 6 78
+72 24 94 64 76
+
+94 98 58 41 63
+77 76 73 62 49
+74 38 87 92 46
+83 89 48 5 15
+26 19 8 44 56
+
+72 21 44 61 99
+84 8 66 69 32
+12 38 57 86 37
+87 74 41 3 91
+90 78 45 89 49
+
+22 85 17 59 8
+99 43 79 65 84
+56 36 66 78 57
+50 10 39 67 69
+12 14 34 68 23
+
+ 2 8 58 29 89
+53 54 69 19 48
+22 52 35 36 6
+26 46 44 15 61
+21 71 63 83 99
+
+84 25 24 59 95
+49 29 26 17 58
+39 51 15 72 21
+ 1 13 35 85 11
+ 4 91 18 89 53
+
+49 76 48 58 19
+32 11 53 24 67
+64 12 3 45 31
+ 6 75 44 46 80
+59 90 42 39 83
+
+71 25 59 18 12
+54 10 77 52 13
+42 68 28 17 37
+33 82 47 22 24
+38 14 79 41 84
+
+81 56 34 28 71
+83 27 14 16 30
+63 26 6 45 29
+86 53 60 50 15
+ 8 43 7 44 91
+
+32 30 59 58 55
+76 24 8 79 0
+35 14 46 16 99
+20 19 98 4 94
+74 85 51 31 17
+
+32 37 22 91 52
+ 1 20 88 17 86
+64 61 34 23 79
+28 42 5 67 72
+ 4 94 13 74 14
+
+11 62 72 23 45
+60 65 56 81 29
+83 64 73 61 1
+57 77 2 30 9
+10 39 50 28 88
+
+50 17 65 72 16
+24 86 42 39 68
+20 84 27 98 12
+57 41 1 63 32
+94 22 38 81 18
+
+45 51 38 88 94
+21 24 44 74 63
+29 19 26 57 32
+40 31 56 80 53
+36 70 33 22 93
+
+99 86 22 85 17
+74 45 78 67 39
+18 42 77 46 27
+20 31 40 8 81
+73 47 19 96 15
+
+92 54 10 73 24
+44 18 74 32 19
+69 8 14 46 33
+63 57 97 65 3
+62 34 4 36 35
+
+71 7 5 3 88
+94 79 47 41 28
+51 31 91 23 52
+99 42 39 87 54
+48 59 97 68 4
+
+ 9 93 86 99 26
+14 83 45 43 48
+84 23 17 28 4
+35 79 47 75 61
+54 65 59 81 42
+
+89 99 27 58 96
+23 52 50 24 70
+47 83 61 5 65
+40 19 66 21 0
+55 10 13 81 51
+
+26 30 33 1 57
+41 60 44 96 70
+72 29 24 0 62
+76 69 16 21 93
+52 48 79 84 14
+
+65 36 74 22 80
+21 69 47 31 61
+42 50 92 27 18
+12 24 91 29 6
+28 73 70 76 11
+
+60 79 47 8 30
+65 50 54 56 23
+14 98 33 25 76
+74 71 86 37 66
+72 77 85 39 53
+
+71 56 53 3 19
+88 99 40 61 37
+95 87 8 78 34
+54 75 57 96 12
+50 98 69 58 94
+
+16 9 85 2 87
+88 98 37 13 1
+27 42 15 18 22
+29 58 25 99 72
+38 86 78 91 92
+
+ 3 21 39 81 76
+66 47 80 44 13
+59 2 96 17 62
+35 51 8 37 41
+88 74 14 92 18
+
+71 15 74 60 32
+17 67 69 62 80
+19 1 78 89 85
+22 96 11 8 13
+ 4 86 48 0 61
+
+22 29 68 36 55
+73 62 86 31 90
+ 7 75 49 81 46
+ 9 41 83 67 51
+32 24 59 5 99
+
+84 94 25 18 57
+76 6 98 79 29
+42 10 71 89 5
+74 78 53 85 51
+64 20 49 47 37
+
+95 22 29 37 87
+13 54 0 28 74
+21 50 49 8 92
+81 58 34 2 43
+65 19 63 52 76
+
+15 69 67 23 21
+82 84 20 83 53
+49 59 86 2 31
+71 89 68 40 79
+76 25 42 22 13
+
+82 11 88 77 92
+48 8 61 13 64
+32 72 80 67 3
+52 4 25 75 94
+53 20 33 6 16
+
+41 95 57 46 17
+50 3 99 74 28
+97 39 73 58 70
+75 35 94 51 87
+12 44 43 21 71
+
+74 0 85 48 21
+42 28 16 6 53
+51 25 18 72 47
+83 4 37 79 29
+96 39 78 44 56
+
+45 60 35 49 4
+25 94 68 34 56
+54 17 61 74 50
+70 48 98 5 14
+15 85 21 8 22
+
+29 33 86 96 62
+ 2 43 61 10 46
+11 12 76 31 80
+88 78 37 92 14
+53 57 90 74 1
+
+32 56 43 50 60
+ 0 77 72 51 37
+71 40 69 97 38
+65 2 67 47 81
+54 79 82 84 90
+
+82 26 28 87 93
+61 33 38 89 12
+25 13 5 37 35
+15 67 8 94 16
+95 59 64 41 70
+
+85 22 43 18 13
+64 73 96 16 84
+61 44 12 37 11
+47 35 80 32 14
+ 2 41 60 29 86
+
+52 87 78 6 61
+50 21 54 4 2
+91 1 35 48 72
+99 43 69 44 40
+30 41 19 29 27
+
+10 20 95 69 22
+66 53 77 37 28
+51 89 85 48 21
+16 14 60 73 43
+96 86 12 97 90
+
+48 7 67 47 96
+71 61 60 64 18
+13 15 57 86 93
+46 41 53 88 32
+82 65 26 34 10
+
+80 92 2 54 5
+ 0 17 78 81 43
+33 15 51 73 61
+71 31 47 38 11
+52 29 23 97 14
+
+76 52 54 92 80
+74 50 11 27 78
+63 9 25 38 20
+ 3 90 39 37 15
+87 45 17 93 62
diff --git a/day04/main.c b/day04/main.c
@@ -0,0 +1,25 @@
+#include <stdio.h>
+
+int puzzle1(const char *filename);
+//int puzzle2(const char *filename);
+
+int main(int argc, char *argv[]) {
+ printf("Advent of Code: day 04\n");
+
+ if (argc <= 0) {
+ return -1;
+ }
+ if (argc <= 1) {
+ printf("Usage: %s inputfile.txt\n", argv[0]);
+ return -1;
+ }
+
+ const char *filename = argv[1];
+
+ int counter1 = puzzle1(filename);
+ printf("Puzzle #1: %d\n", counter1);
+ //int counter2 = puzzle2(filename);
+ //printf("Puzzle #2: %d\n", counter2);
+
+ return 0;
+}
diff --git a/day04/puzzle1.c b/day04/puzzle1.c
@@ -0,0 +1,242 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <strings.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#define PRINT_ERR(func) fprintf(stderr, #func "() error: %s\n", strerror(errno));
+
+#define ARRAY_PUSH
+
+#define FMT_(l) #l
+#define FMT(l) FMT_(l)
+
+#define STR_LEN 16384
+#define FMT_STRING "%" FMT(STR_LEN) "s"
+
+#define BOARD_SIZE 5
+
+struct board_t {
+ int tiles[BOARD_SIZE][BOARD_SIZE]; // 0-99 base, -1 marks drawn tiles
+ int rows_sig[BOARD_SIZE]; // sum of numbers that works as a "signature"
+ int cols_sig[BOARD_SIZE]; // once it goes down to -5 it means r/k are done
+ int sum;
+};
+
+struct array_t {
+ void *data;
+ size_t elem_size;
+ size_t count;
+ size_t cap;
+};
+
+bool array_init(struct array_t *array, size_t elem_size, size_t cap);
+bool array_expand(struct array_t *array);
+
+#define PRINT_ARRAY(array, type) do { \
+ printf("array count %zu, cap %zu, elem size %zu, data %p\n", \
+ array.count, array.cap, array.elem_size, &array); \
+ for (size_t i = 0; i < array.count; ++i) { \
+ type *data = (type *)array.data; \
+ printf("%d ", data[i]); \
+ } \
+ printf("\n"); \
+} while (0);
+
+bool make_numbers_array(struct array_t *numbers, const char *str);
+bool fill_board(struct board_t *board, int row, const char *str);
+
+void print_boards(const struct array_t *boards);
+
+/* ****************************************************************** */
+
+int puzzle1(const char *filename) {
+ FILE *infile = fopen(filename, "r");
+ if (infile == NULL) {
+ fprintf(stderr, "fopen() error: %s\n", strerror(errno));
+ return -1;
+ }
+
+ char buf[STR_LEN] = {0};
+ unsigned int line_num = 0;
+ int result = -1;
+
+ struct array_t numbers = { .data = NULL };
+ struct array_t boards = { .data = NULL };
+
+ if (!array_init(&numbers, sizeof(int), 100)) {
+ fprintf(stderr, "array_init() failed\n");
+ goto finish; // @todo assert?
+ }
+
+ if (!array_init(&boards, sizeof(struct board_t), 10)) {
+ fprintf(stderr, "array_init() failed");
+ goto finish; // @todo assert?
+ }
+
+ struct board_t *current_board = NULL;
+ int current_row = -1;
+
+ while (fgets(buf, STR_LEN, infile) != NULL) {
+ // first line is always random numbers sequence
+ if (line_num == 0) {
+ if (!make_numbers_array(&numbers, buf)) {
+ fprintf(stderr, "make_numbers_array() failed\n");
+ goto finish;
+ }
+
+ } else if (strlen(buf) == 1) { // line sized 1 is a separator before boards
+ if (boards.count >= boards.cap && !array_expand(&boards)) {
+ fprintf(stderr, "array_expand() failed\n");
+ goto finish;
+ }
+
+ struct board_t *data = (struct board_t *)boards.data;
+ current_board = &data[boards.count++];
+ current_row = 0;
+
+ } else { // filling the board
+ assert(current_board != NULL);
+ assert(current_row != -1);
+ if (!fill_board(current_board, current_row++, buf)) {
+ fprintf(stderr, "fill_board() failed\n");
+ goto finish;
+ }
+ }
+
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+
+ //print_boards(&boards);
+
+ // rolling
+ for (size_t i = 0; i < numbers.count; ++i) {
+ int num = ((int *)numbers.data)[i];
+
+ for (size_t j = 0; j < boards.count; ++j) {
+ struct board_t *board = &((struct board_t *)boards.data)[j];
+
+ for (int r = 0; r < BOARD_SIZE; ++r) {
+ for (int k = 0; k < BOARD_SIZE; ++k) {
+ if (board->tiles[r][k] == num) {
+ board->tiles[r][k] = -1;
+ board->rows_sig[r] -= num + 1;
+ board->cols_sig[k] -= num + 1;
+ board->sum -= num;
+
+ if (board->rows_sig[r] == -BOARD_SIZE || board->cols_sig[k] == -BOARD_SIZE) {
+ result = board->sum * num;
+ goto out;
+ }
+ }
+ }
+ }
+ }
+ }
+
+out:
+ //print_boards(&boards);
+
+ // mutiny! ignoring feof/ferror.
+finish:
+ free(numbers.data);
+ free(boards.data);
+ fclose(infile);
+ return result;
+}
+
+/* ************************* BOILERPLATE ************************* */
+
+void print_boards(const struct array_t *boards) {
+ for (size_t i = 0; i < boards->count; ++i) {
+ const struct board_t *brd = (const struct board_t *)boards->data;
+ brd += i;
+ printf("\n----------- board %2zu ------------\n", i);
+ for (int r = 0; r < BOARD_SIZE; ++r) {
+ for (int k = 0; k < BOARD_SIZE; ++k) {
+ printf("[%3d]", brd->tiles[r][k]);
+ }
+ printf(" = [%3d]\n", brd->rows_sig[r]);
+ }
+ printf("=================================\n");
+ for (int k = 0; k < BOARD_SIZE; ++k) {
+ printf("[%3d]", brd->cols_sig[k]);
+ }
+ printf("\n");
+ }
+}
+
+bool make_numbers_array(struct array_t *numbers, const char *str) {
+ char *tmp = strndup(str, STR_LEN);
+ char *token = NULL;
+
+ assert(tmp != NULL);
+
+ while ((token = strsep(&tmp, ",")) != NULL) {
+ int num = atoi(token);
+
+ if (numbers->count >= numbers->cap && !array_expand(numbers)) {
+ fprintf(stderr, "array_expand() failed\n");
+ return false;
+ }
+
+ int *data = (int *)numbers->data;
+ data[numbers->count++] = num;
+ }
+
+ free(tmp);
+ return true;
+}
+
+bool fill_board(struct board_t *board, int row, const char *str) {
+ char *tmp = strndup(str, STR_LEN);
+ assert(tmp != NULL);
+ char *token = NULL;
+ int col = 0;
+ while ((token = strsep(&tmp, " ")) != NULL) {
+ if (*token != '\0') { // WOWZA
+ int num = atoi(token);
+ board->tiles[row][col] = num;
+ board->rows_sig[row] += num;
+ board->cols_sig[col] += num;
+ board->sum += num;
+ ++col;
+ }
+ }
+ assert(col == BOARD_SIZE);
+ return true;
+}
+
+// @todo move generic service stuff to some kind of shared header?
+
+bool array_init(struct array_t *array, size_t elem_size, size_t cap) {
+ if (array->data != NULL)
+ return false;
+
+ array->cap = cap;
+ array->elem_size = elem_size;
+ array->data = calloc(cap, elem_size);
+
+ if (array->data == NULL) {
+ PRINT_ERR(calloc)
+ return false;
+ }
+
+ return true;
+}
+
+bool array_expand(struct array_t *array) {
+ size_t new_cap = array->cap * 2;
+ array->data = realloc(array->data, array->elem_size * new_cap);
+
+ if (array->data == NULL) {
+ PRINT_ERR(realloc)
+ return false;
+ }
+
+ array->cap = new_cap;
+ return true;
+}
diff --git a/day04/test.txt b/day04/test.txt
@@ -0,0 +1,19 @@
+7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1
+
+22 13 17 11 0
+ 8 2 23 4 24
+21 9 14 16 7
+ 6 10 3 18 5
+ 1 12 20 15 19
+
+ 3 15 0 2 22
+ 9 18 13 17 5
+19 8 7 25 23
+20 11 10 24 4
+14 21 16 12 6
+
+14 21 17 24 4
+10 16 15 9 19
+18 8 23 26 20
+22 11 13 6 5
+ 2 0 12 3 7
