advent2021

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

puzzle1.c (5859B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <errno.h>
      6 #include <string.h>
      7 #include <strings.h>
      8 #include <stdbool.h>
      9 #include <assert.h>
     10 
     11 #define PRINT_ERR(func) fprintf(stderr, #func "() error: %s\n", strerror(errno));
     12 
     13 #define ARRAY_PUSH
     14 
     15 #define FMT_(l) #l
     16 #define FMT(l) FMT_(l)
     17 
     18 #define STR_LEN 16384
     19 #define FMT_STRING "%" FMT(STR_LEN) "s"
     20 
     21 #define BOARD_SIZE 5
     22 
     23 struct board_t {
     24 	int tiles[BOARD_SIZE][BOARD_SIZE]; // 0-99 base, -1 marks drawn tiles
     25 	int rows_sig[BOARD_SIZE]; // sum of numbers that works as a "signature"
     26 	int cols_sig[BOARD_SIZE]; // once it goes down to -5 it means r/k are done
     27 	int sum;
     28 };
     29 
     30 struct array_t {
     31 	void *data;
     32 	size_t elem_size;
     33 	size_t count;
     34 	size_t cap;
     35 };
     36 
     37 bool array_init(struct array_t *array, size_t elem_size, size_t cap);
     38 bool array_expand(struct array_t *array);
     39 
     40 #define PRINT_ARRAY(array, type) do { \
     41 	printf("array count %zu, cap %zu, elem size %zu, data %p\n", \
     42 		array.count, array.cap, array.elem_size, &array); \
     43 	for (size_t i = 0; i < array.count; ++i) { \
     44 		type *data = (type *)array.data; \
     45 		printf("%d ", data[i]); \
     46 	} \
     47 	printf("\n"); \
     48 } while (0);
     49 
     50 bool make_numbers_array(struct array_t *numbers, const char *str);
     51 bool fill_board(struct board_t *board, int row, const char *str);
     52 
     53 void print_boards(const struct array_t *boards);
     54 
     55 /* ****************************************************************** */
     56 
     57 int puzzle1(const char *filename) {
     58 	FILE *infile = fopen(filename, "r");
     59 	if (infile == NULL) {
     60 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     61 		return -1;
     62 	}
     63 
     64 	char buf[STR_LEN] = {0};
     65 	unsigned int line_num = 0;
     66 	int result = -1;
     67 
     68 	struct array_t numbers = { .data = NULL };
     69 	struct array_t boards = { .data = NULL };
     70 
     71 	if (!array_init(&numbers, sizeof(int), 100)) {
     72 		fprintf(stderr, "array_init() failed\n");
     73 		goto finish; // @todo assert?
     74 	}
     75 
     76 	if (!array_init(&boards, sizeof(struct board_t), 10)) {
     77 		fprintf(stderr, "array_init() failed");
     78 		goto finish; // @todo assert?
     79 	}
     80 
     81 	struct board_t *current_board = NULL;
     82 	int current_row = -1;
     83 
     84 	while (fgets(buf, STR_LEN, infile) != NULL) {
     85 		// first line is always random numbers sequence
     86 		if (line_num == 0) {
     87 			if (!make_numbers_array(&numbers, buf)) {
     88 				fprintf(stderr, "make_numbers_array() failed\n");
     89 				goto finish;
     90 			}
     91 
     92 		} else if (strlen(buf) == 1) { // line sized 1 is a separator before boards
     93 			if (boards.count >= boards.cap && !array_expand(&boards)) {
     94 				fprintf(stderr, "array_expand() failed\n");
     95 				goto finish;
     96 			}
     97 
     98 			struct board_t *data = (struct board_t *)boards.data;
     99 			current_board = &data[boards.count++];
    100 			current_row = 0;
    101 
    102 		} else { // filling the board
    103 			assert(current_board != NULL);
    104 			assert(current_row != -1);
    105 			if (!fill_board(current_board, current_row++, buf)) {
    106 				fprintf(stderr, "fill_board() failed\n");
    107 				goto finish;
    108 			}
    109 		}
    110 
    111 		++line_num;
    112 		bzero(buf, STR_LEN);
    113 	}
    114 
    115 	//print_boards(&boards);
    116 
    117 	// rolling
    118 	for (size_t i = 0; i < numbers.count; ++i) {
    119 		int num = ((int *)numbers.data)[i];
    120 
    121 		for (size_t j = 0; j < boards.count; ++j) {
    122 			struct board_t *board = &((struct board_t *)boards.data)[j];
    123 
    124 			for (int r = 0; r < BOARD_SIZE; ++r) {
    125 				for (int k = 0; k < BOARD_SIZE; ++k) {
    126 					if (board->tiles[r][k] == num) {
    127 						board->tiles[r][k] = -1;
    128 						board->rows_sig[r] -= num + 1;
    129 						board->cols_sig[k] -= num + 1;
    130 						board->sum -= num;
    131 
    132 						if (board->rows_sig[r] == -BOARD_SIZE || board->cols_sig[k] == -BOARD_SIZE) {
    133 							result = board->sum * num;
    134 							goto out;
    135 						}
    136 					}
    137 				}
    138 			}
    139 		}
    140 	}
    141 
    142 out:
    143 	//print_boards(&boards);
    144 
    145 	// mutiny! ignoring feof/ferror.
    146 finish:
    147 	free(numbers.data);
    148 	free(boards.data);
    149 	fclose(infile);
    150 	return result;
    151 }
    152 
    153 /* ************************* BOILERPLATE ************************* */
    154 
    155 void print_boards(const struct array_t *boards) {
    156 	for (size_t i = 0; i < boards->count; ++i) {
    157 		const struct board_t *brd = (const struct board_t *)boards->data;
    158 		brd += i;
    159 		printf("\n----------- board %2zu ------------\n", i);
    160 		for (int r = 0; r < BOARD_SIZE; ++r) {
    161 			for (int k = 0; k < BOARD_SIZE; ++k) {
    162 				printf("[%3d]", brd->tiles[r][k]);
    163 			}
    164 			printf(" = [%3d]\n", brd->rows_sig[r]);
    165 		}
    166 		printf("=================================\n");
    167 		for (int k = 0; k < BOARD_SIZE; ++k) {
    168 			printf("[%3d]", brd->cols_sig[k]);
    169 		}
    170 		printf("\n");
    171 	}
    172 }
    173 
    174 bool make_numbers_array(struct array_t *numbers, const char *str) {
    175 	char *tmp = strndup(str, STR_LEN);
    176 	char *token = NULL;
    177 
    178 	assert(tmp != NULL);
    179 
    180 	while ((token = strsep(&tmp, ",")) != NULL) {
    181 		int num = atoi(token);
    182 
    183 		if (numbers->count >= numbers->cap && !array_expand(numbers)) {
    184 			fprintf(stderr, "array_expand() failed\n");
    185 			return false;
    186 		}
    187 
    188 		int *data = (int *)numbers->data;
    189 		data[numbers->count++] = num;
    190 	}
    191 
    192 	free(tmp);
    193 	return true;
    194 }
    195 
    196 bool fill_board(struct board_t *board, int row, const char *str) {
    197 	char *tmp = strndup(str, STR_LEN);
    198 	assert(tmp != NULL);
    199 	char *token = NULL;
    200 	int col = 0;
    201 	while ((token = strsep(&tmp, " ")) != NULL) {
    202 		if (*token != '\0') { // WOWZA
    203 			int num = atoi(token);
    204 			board->tiles[row][col] = num;
    205 			board->rows_sig[row] += num;
    206 			board->cols_sig[col] += num;
    207 			board->sum += num;
    208 			++col;
    209 		}
    210 	}
    211 	assert(col == BOARD_SIZE);
    212 	return true;
    213 }
    214 
    215 // @todo move generic service stuff to some kind of shared header?
    216 
    217 bool array_init(struct array_t *array, size_t elem_size, size_t cap) {
    218 	if (array->data != NULL)
    219 		return false;
    220 
    221 	array->cap = cap;
    222 	array->elem_size = elem_size;
    223 	array->data = calloc(cap, elem_size);
    224 
    225 	if (array->data == NULL) {
    226 		PRINT_ERR(calloc)
    227 		return false;
    228 	}
    229 
    230 	return true;
    231 }
    232 
    233 bool array_expand(struct array_t *array) {
    234 	size_t new_cap = array->cap * 2;
    235 	array->data = realloc(array->data, array->elem_size * new_cap);
    236 
    237 	if (array->data == NULL) {
    238 		PRINT_ERR(realloc)
    239 		return false;
    240 	}
    241 
    242 	array->cap = new_cap;
    243 	return true;
    244 }