advent2021

commit 2a6c6f6869f2fecc7e160716e9bb5be8057c72ba
parent 6b31037dba861e5afcf1e7246a6ba4a32aa65675
Author: bsandro <[email protected]>
Date:   Fri, 10 Dec 2021 22:18:20 +0200

Day 10, puzzle 2

Diffstat:
M
common/quicksort.h
 | 
10
+++++-----
M
common/util.h
 | 
2
+-
M
day10/puzzle.c
 | 
96
++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------

3 files changed, 72 insertions(+), 36 deletions(-)
diff --git a/common/quicksort.h b/common/quicksort.h
@@ -2,14 +2,14 @@
 
 /* ******************* quicksort ***********************/
 
-static void qs_swap(int *a, int *b) {
-	int tmp = *a;
+static void qs_swap(long long *a, long long *b) {
+	long long tmp = *a;
 	*a = *b;
 	*b = tmp;
 }
 
-static long long qs_partition(int *numbers, long long low, long long high) {
-	int pivot = numbers[high];
+static long long qs_partition(long long *numbers, long long low, long long high) {
+	long long pivot = numbers[high];
 	long long i = low - 1;
 	for (long long j = low; j <= high - 1; ++j) {
 		if (numbers[j] < pivot) {
@@ -21,7 +21,7 @@ static long long qs_partition(int *numbers, long long low, long long high) {
 	return i + 1;
 }
 
-static void qs(int *numbers, long long low, long long high) {
+static void qs(long long *numbers, long long low, long long high) {
 	if (low < high) {
 		long long p = qs_partition(numbers, low, high);
 		qs(numbers, low, p - 1);
diff --git a/common/util.h b/common/util.h
@@ -25,7 +25,7 @@ struct array_t {
 		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("%lld ", data[i]); \
 	} \
 	printf("\n"); \
 } while (0);
diff --git a/day10/puzzle.c b/day10/puzzle.c
@@ -5,13 +5,10 @@
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
-#include <stdbool.h>
 #include <assert.h>
-#include <time.h>
-#include <inttypes.h>
-#include <ctype.h>
 
 #include "util.h"
+#include "quicksort.h"
 
 #define STR_LEN 1024
 
@@ -19,7 +16,10 @@
 void array_push(struct array_t *array, char bracket);
 char array_pop(struct array_t *array);
 
-char validate_string(const char *str);
+char validate_string(struct array_t *brackets, const char *str);
+long long calc_score1(const char illegal);
+long long calc_score2(struct array_t *brackets);
+long long get_score2(const char c);
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
@@ -30,64 +30,61 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 
 	char buf[STR_LEN] = {0};
 	unsigned int line_num = 0;
+	struct array_t scores = { .data = NULL };
+	array_init(&scores, sizeof(long long), 10);
 
 	*result1 = 0;
 	*result2 = 0;
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
-		char illegal = validate_string(buf);
+		struct array_t brackets = { .data = NULL };
+		array_init(&brackets, sizeof(char), 10);
+
+		char illegal = validate_string(&brackets, buf);
 		if (illegal != 0) {
-			switch (illegal) {
-			case ')':
-				*result1 += 3;
-				break;
-			case ']':
-				*result1 += 57;
-				break;
-			case '}':
-				*result1 += 1197;
-				break;
-			case '>':
-				*result1 += 25137;
-				break;
-			}
+			*result1 += calc_score1(illegal);
+		} else {
+			((long long *)scores.data)[scores.count++] = calc_score2(&brackets);
 		}
 
+		free(brackets.data);
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
+	long long *scores_data = (long long *)scores.data;
+	qs(scores_data, 0, scores.count - 1);
+	*result2 = scores_data[scores.count / 2];
+
+	free(scores.data);
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
-char validate_string(const char *str) {
+char validate_string(struct array_t *brackets, const char *str) {
 	size_t len = strlen(str);
 	assert(len > 2); // at least 2 characters + EOL
-	struct array_t brackets = { .data = NULL };
-	array_init(&brackets, sizeof(char), 10);
 
 	for (size_t i = 0; i < len; ++i) {
 		char c = str[i];
 		switch (c) {
 		case '{':
-			array_push(&brackets, '}');
+			array_push(brackets, '}');
 			break;
 		case '(':
-			array_push(&brackets, ')');
+			array_push(brackets, ')');
 			break;
 		case '<':
-			array_push(&brackets, '>');
+			array_push(brackets, '>');
 			break;
 		case '[':
-			array_push(&brackets, ']');
+			array_push(brackets, ']');
 			break;
 		case '}':
 		case ')':
 		case '>':
 		case ']': {
-			char expected = array_pop(&brackets);
-			if (c != expected) {
+			if (array_pop(brackets) != c) {
 				return c;
 			}
 			break;
@@ -100,7 +97,6 @@ char validate_string(const char *str) {
 		}
 	}
 
-	free(brackets.data);
 	return 0;
 }
 
@@ -113,6 +109,46 @@ void array_push(struct array_t *array, char bracket) {
 }
 
 char array_pop(struct array_t *array) {
+	assert(array->count > 0);
 	char *data = (char *)array->data;
 	return data[--array->count];
 }
+
+long long calc_score1(const char illegal) {
+	switch (illegal) {
+	case ')':
+		return 3;
+	case ']':
+		return 57;
+	case '}':
+		return 1197;
+	case '>':
+		return 25137;
+	default:
+		return 0;
+	}
+}
+
+long long calc_score2(struct array_t *brackets) {
+	long long score = 0;
+	while (brackets->count > 0) {
+		char c = array_pop(brackets);
+		score = score * 5 + get_score2(c);
+	}
+	return score;
+}
+
+long long get_score2(const char c) {
+	switch (c) {
+	case ')':
+		return 1;
+	case ']':
+		return 2;
+	case '}':
+		return 3;
+	case '>':
+		return 4;
+	default:
+		return 0;
+	}
+}