advent2021

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

puzzle.c (3252B)


      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 <assert.h>
      9 
     10 #include "util.h"
     11 
     12 #define STR_LEN 1024
     13 
     14 // simple stack operations on array_t
     15 void array_push(struct array_t *array, char bracket);
     16 char array_pop(struct array_t *array);
     17 
     18 char validate_string(struct array_t *brackets, const char *str);
     19 long long calc_score1(const char illegal);
     20 long long calc_score2(struct array_t *brackets);
     21 long long get_score2(const char c);
     22 
     23 static int compare(const void *l, const void *r) {
     24 	long long d = *(long long *)l - *(long long *)r;
     25 	if (d > 0) return 1;
     26 	if (d < 0) return -1;
     27 	return 0;
     28 }
     29 
     30 void puzzle(const char *filename, long long *result1, long long *result2) {
     31 	FILE *infile = fopen(filename, "r");
     32 	if (infile == NULL) {
     33 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     34 		return;
     35 	}
     36 
     37 	char buf[STR_LEN] = {0};
     38 	unsigned int line_num = 0;
     39 	struct array_t scores = { .data = NULL };
     40 	array_init(&scores, sizeof(long long), 10);
     41 
     42 	*result1 = 0;
     43 
     44 	while (fgets(buf, STR_LEN, infile) != NULL) {
     45 		struct array_t brackets = { .data = NULL };
     46 		array_init(&brackets, sizeof(char), 10);
     47 
     48 		char illegal = validate_string(&brackets, buf);
     49 		if (illegal != 0) {
     50 			*result1 += calc_score1(illegal);
     51 		} else {
     52 			if (scores.count >= scores.cap) array_expand(&scores);
     53 			((long long *)scores.data)[scores.count++] = calc_score2(&brackets);
     54 		}
     55 
     56 		free(brackets.data);
     57 		++line_num;
     58 		bzero(buf, STR_LEN);
     59 	}
     60 
     61 	long long *scores_data = scores.data;
     62 	qsort(scores_data, scores.count, scores.elem_size, compare);
     63 	*result2 = scores_data[scores.count / 2];
     64 
     65 	free(scores.data);
     66 	// mutiny! ignoring feof/ferror.
     67 	fclose(infile);
     68 }
     69 
     70 char validate_string(struct array_t *brackets, const char *str) {
     71 	size_t len = strlen(str);
     72 	assert(len > 2); // at least 2 characters + EOL
     73 
     74 	for (size_t i = 0; i < len; ++i) {
     75 		char c = str[i];
     76 		switch (c) {
     77 		case '{':
     78 			array_push(brackets, '}');
     79 			break;
     80 		case '(':
     81 			array_push(brackets, ')');
     82 			break;
     83 		case '<':
     84 			array_push(brackets, '>');
     85 			break;
     86 		case '[':
     87 			array_push(brackets, ']');
     88 			break;
     89 		case '}':
     90 		case ')':
     91 		case '>':
     92 		case ']': {
     93 			if (array_pop(brackets) != c) {
     94 				return c;
     95 			}
     96 			break;
     97 		}
     98 		case '\n':
     99 			// do nothing
    100 			break;
    101 		default:
    102 			printf("invalid symbol: %c (#%d)\n", c, c);
    103 		}
    104 	}
    105 
    106 	return 0;
    107 }
    108 
    109 void array_push(struct array_t *array, char bracket) {
    110 	if (array->count >= array->cap) {
    111 		array_expand(array);
    112 	}
    113 	char *data = (char *)array->data;
    114 	data[array->count++] = bracket;
    115 }
    116 
    117 char array_pop(struct array_t *array) {
    118 	assert(array->count > 0);
    119 	char *data = (char *)array->data;
    120 	return data[--array->count];
    121 }
    122 
    123 long long calc_score1(const char illegal) {
    124 	switch (illegal) {
    125 	case ')':
    126 		return 3;
    127 	case ']':
    128 		return 57;
    129 	case '}':
    130 		return 1197;
    131 	case '>':
    132 		return 25137;
    133 	default:
    134 		return 0;
    135 	}
    136 }
    137 
    138 long long calc_score2(struct array_t *brackets) {
    139 	long long score = 0;
    140 	while (brackets->count > 0) {
    141 		char c = array_pop(brackets);
    142 		score = score * 5 + get_score2(c);
    143 	}
    144 	return score;
    145 }
    146 
    147 long long get_score2(const char c) {
    148 	switch (c) {
    149 	case ')':
    150 		return 1;
    151 	case ']':
    152 		return 2;
    153 	case '}':
    154 		return 3;
    155 	case '>':
    156 		return 4;
    157 	default:
    158 		return 0;
    159 	}
    160 }