commit bc0efbf0c64482d673e34dee30e498dbe4dec2a8
parent cb154b48b5a9417462d411c14e4d6c442e2a334e
Author: bsandro <[email protected]>
Date: Sat, 4 Dec 2021 22:47:12 +0200
Day 04, puzzle 2 + some rework
Diffstat:
4 files changed, 240 insertions(+), 250 deletions(-)
diff --git a/day04/Makefile b/day04/Makefile
@@ -4,7 +4,7 @@ SRC=$(wildcard *.c)
DEPS:=$(wildcard *.h)
OBJ:=$(SRC:.c=.o)
-CFLAGS=-O0 -std=c99 -g -Werror -Wall -Wextra -I.
+CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I.
all: $(NAME)
diff --git a/day04/main.c b/day04/main.c
@@ -1,7 +1,6 @@
#include <stdio.h>
-int puzzle1(const char *filename);
-//int puzzle2(const char *filename);
+void puzzle(const char *filename, int *res1, int *res2);
int main(int argc, char *argv[]) {
printf("Advent of Code: day 04\n");
@@ -16,10 +15,13 @@ int main(int argc, char *argv[]) {
const char *filename = argv[1];
- int counter1 = puzzle1(filename);
+ int counter1 = -1;
+ int counter2 = -1;
+
+ puzzle(filename, &counter1, &counter2);
+
printf("Puzzle #1: %d\n", counter1);
- //int counter2 = puzzle2(filename);
- //printf("Puzzle #2: %d\n", counter2);
+ printf("Puzzle #2: %d\n", counter2);
return 0;
}
diff --git a/day04/puzzle1.c b/day04/puzzle1.c
@@ -1,244 +0,0 @@
-#define _DEFAULT_SOURCE
-
-#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/puzzle12.c b/day04/puzzle12.c
@@ -0,0 +1,232 @@
+#define _DEFAULT_SOURCE
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+#include <strings.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <time.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;
+ bool won;
+};
+
+struct array_t {
+ void *data;
+ size_t elem_size;
+ size_t count;
+ size_t cap;
+};
+
+void array_init(struct array_t *array, size_t elem_size, size_t cap);
+void 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);
+
+void make_numbers_array(struct array_t *numbers, const char *str);
+void fill_board(struct board_t *board, int row, const char *str);
+int check_board(struct board_t *board, int num);
+void print_boards(const struct array_t *boards);
+
+/* ****************************************************************** */
+
+void puzzle(const char *filename, int *result1, int *result2) {
+ double time_start = clock();
+
+ 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;
+
+ struct array_t numbers = { .data = NULL };
+ struct array_t boards = { .data = NULL };
+
+ array_init(&numbers, sizeof(int), 100);
+ array_init(&boards, sizeof(struct board_t), 10);
+
+ 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) {
+ make_numbers_array(&numbers, buf);
+
+ } else if (strlen(buf) == 1) { // line sized 1 is a separator before boards
+ if (boards.count >= boards.cap) {
+ array_expand(&boards);
+ }
+
+ 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);
+ fill_board(current_board, current_row++, buf);
+ }
+
+ ++line_num;
+ bzero(buf, STR_LEN);
+ }
+
+ size_t active_boards = boards.count;
+
+ //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];
+ if (board->won) continue;
+
+ int result = check_board(board, num);
+ if (result > 0) {
+ if (active_boards == boards.count) {
+ *result1 = result; // first winning board
+ } else {
+ *result2 = result; // last winning board
+ }
+ --active_boards;
+ }
+ }
+ }
+
+ //print_boards(&boards);
+
+ // mutiny! ignoring feof/ferror.
+ free(numbers.data);
+ free(boards.data);
+ fclose(infile);
+
+ double elapsed = clock() - time_start;
+ printf("elapsed: %f\n", elapsed / CLOCKS_PER_SEC);
+}
+
+/* ************************* BOILERPLATE ************************* */
+
+int check_board(struct board_t *board, int num) {
+ 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) {
+ board->won = true;
+ return board->sum * num;
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+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");
+ }
+}
+
+void 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);
+ }
+
+ int *data = (int *)numbers->data;
+ data[numbers->count++] = num;
+ }
+
+ free(tmp);
+}
+
+void 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);
+}
+
+// @todo move generic service stuff to some kind of shared header?
+
+void array_init(struct array_t *array, size_t elem_size, size_t cap) {
+ assert(array->data == NULL);
+ array->cap = cap;
+ array->elem_size = elem_size;
+ array->data = calloc(cap, elem_size);
+ assert(array->data != NULL);
+}
+
+void array_expand(struct array_t *array) {
+ size_t new_cap = array->cap * 2;
+ array->data = realloc(array->data, array->elem_size * new_cap);
+ assert(array->data != NULL);
+ array->cap = new_cap;
+}
