commit 97089615314bbf37377e8a1bd02dd591fbdf8c4d
parent d836c1292cf2a87c207c2d40388826bbf81c6195
Author: bsandro <[email protected]>
Date: Sun, 19 Dec 2021 17:32:52 +0200
Day 18, puzzles 1+2
Diffstat:
4 files changed, 223 insertions(+), 77 deletions(-)
diff --git a/common/util.c b/common/util.c
@@ -12,6 +12,19 @@ void array_init(struct array_t *array, size_t elem_size, size_t cap) {
assert(array->data != NULL);
}
+struct array_t array_copy(struct array_t *array) {
+ assert(array != NULL);
+ assert(array->data != NULL);
+ struct array_t ar_copy = { .data = NULL };
+ array_init(&ar_copy, array->elem_size, array->count);
+ assert(ar_copy.data != NULL);
+ memcpy(ar_copy.data, array->data, array->count * array->elem_size);
+ ar_copy.count = array->count;
+ ar_copy.cap = ar_copy.count;
+ ar_copy.elem_size = ar_copy.elem_size;
+ return ar_copy;
+}
+
void array_expand(struct array_t *array) {
size_t new_cap = array->cap * 2;
array->data = realloc(array->data, array->elem_size * new_cap);
@@ -19,6 +32,13 @@ void array_expand(struct array_t *array) {
array->cap = new_cap;
}
+void array_expand1(struct array_t *array, size_t incr) {
+ size_t new_cap = array->cap + incr;
+ array->data = realloc(array->data, array->elem_size * new_cap);
+ assert(array->data != NULL);
+ array->cap = new_cap;
+}
+
/* ******************* parse plain numbers array *******************/
void parse_numbers_array(struct array_t *numbers, const char *str, const char *delim) {
assert(numbers != NULL);
diff --git a/common/util.h b/common/util.h
@@ -32,6 +32,8 @@ struct array_t {
void array_init(struct array_t *array, size_t elem_size, size_t cap);
void array_expand(struct array_t *array);
+void array_expand1(struct array_t *array, size_t incr);
+struct array_t array_copy(struct array_t *array);
/* ******************* parse plain numbers array *******************/
void parse_numbers_array(struct array_t *numbers, const char *str, const char *delim);
diff --git a/day18/Makefile b/day18/Makefile
@@ -3,7 +3,7 @@ SRC=$(wildcard *.c ../common/*.c)
DEPS:=$(wildcard *.h ../common/*.h)
OBJ:=$(SRC:.c=.o)
CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common
-LDFLAGS=-lc
+LDFLAGS=-lc -lm
all: $(NAME)
diff --git a/day18/puzzle.c b/day18/puzzle.c
@@ -8,23 +8,28 @@
#include <assert.h>
#include <stdbool.h>
#include <unistd.h>
+#include <math.h>
#include "util.h"
#define STR_LEN 1024
-struct pair_t {
- int *left;
- int *right;
- struct pair_t *pleft;
- struct pair_t *pright;
- int **leftmost;
- int **rightmost;
- struct pair_t *parent;
+struct num_t {
+ int value;
+ int depth;
};
-size_t make_pair(const char *str, struct pair_t *parent, struct pair_t **pair_ptr);
-void print_pair(struct pair_t *pair);
+void parse(const char *str, struct array_t *array);
+void print_nums(struct array_t *array);
+void array_remove(struct array_t *nums, size_t index);
+void array_insert(struct array_t *nums, size_t index, struct num_t num);
+void array_add(struct array_t *nums, struct num_t num);
+bool explode(struct array_t *nums);
+bool split(struct array_t *nums);
+void add(struct array_t *to, struct array_t *from);
+int magnitude(struct array_t *nums);
+int max_magnitude(struct array_t *all_nums);
+int compare(const void *l, const void *r);
void puzzle(const char *filename, long long *result1, long long *result2) {
FILE *infile = fopen(filename, "r");
@@ -39,93 +44,212 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
*result1 = 0;
*result2 = 0;
- struct array_t pairs = { .data = NULL };
- array_init(&pairs, sizeof(void *), 10);
+ struct array_t nums = { .data = NULL };
+ array_init(&nums, sizeof(struct num_t), 10);
+
+ struct array_t all_nums = { .data = NULL };
+ array_init(&all_nums, sizeof(struct array_t), 10);
while (fgets(buf, STR_LEN, infile) != NULL) {
- size_t len = strlen(buf);
- assert(len != 0);
- struct pair_t *pair = NULL;
- size_t processed = make_pair(buf, NULL, &pair);
- printf("len:%zu, processed:%zu\n", len, processed);
- if (pairs.count >= pairs.cap) array_expand(&pairs);
- ((struct pair_t **)pairs.data)[pairs.count++] = pair;
-
- printf("str: %s", buf);
- printf("pair: ");
- print_pair(pair);
- printf("\n");
-
- break;
+ if (all_nums.count >= all_nums.cap) array_expand(&all_nums);
+
+ struct array_t nums_add = { .data = NULL };
+ array_init(&nums_add, sizeof(struct num_t), 10);
+ parse(buf, &nums_add);
+
+ ((struct array_t *)all_nums.data)[all_nums.count++] = array_copy(&nums_add);
+ if (nums.count == 0) { // first line
+ nums = nums_add;
+ continue;
+ }
+ add(&nums, &nums_add);
+ while (explode(&nums) || split(&nums)) {
+ //
+ }
++line_num;
bzero(buf, STR_LEN);
}
+ *result1 = magnitude(&nums);
+ *result2 = max_magnitude(&all_nums);
+
+ free(nums.data);
// mutiny! ignoring feof/ferror.
fclose(infile);
}
-size_t make_pair(const char *str, struct pair_t *parent, struct pair_t **pair_ptr) {
- printf("pair start\n");
+int compare(const void *l, const void *r) {
+ return *(int *)r - *(int *)l;
+}
+
+int max_magnitude(struct array_t *all_nums) {
+ struct array_t magnitudes = { .data = NULL };
+ array_init(&magnitudes, sizeof(int), all_nums->count * all_nums->count);
+ int *magnitudes_data = magnitudes.data;
+ assert(magnitudes_data != NULL);
+
+ struct array_t *all_nums_data = all_nums->data;
+ for (size_t i = 0; i < all_nums->count; ++i) {
+ for (size_t j = 0; j < all_nums->count; ++j) {
+ if (i == j) continue;
+ struct array_t nums_copy = array_copy(&all_nums_data[i]);
+ add(&nums_copy, &all_nums_data[j]);
+ while (explode(&nums_copy) || split(&nums_copy)) {
+ //
+ }
+ magnitudes_data[magnitudes.count++] = magnitude(&nums_copy);
+ free(nums_copy.data);
+ }
+ }
- assert(str != NULL);
- struct pair_t *pair = malloc(sizeof(struct pair_t));
- bzero(pair, sizeof(struct pair_t));
- printf("pair_ptr: %p, *pair_ptr: %p\n", pair_ptr, *pair_ptr);
- *pair_ptr = pair;
+ qsort(magnitudes_data, magnitudes.count, magnitudes.elem_size, compare);
+ int max_mag = magnitudes_data[0];
+ free(magnitudes.data);
+ return max_mag;
+}
- pair->parent = parent;
- if (parent != NULL) {
- pair->leftmost = parent->leftmost;
- pair->rightmost = parent->rightmost;
+int magnitude(struct array_t *nums) {
+ assert(nums != NULL);
+ while (nums->count > 1) {
+ struct num_t *data = nums->data;
+ for (size_t i = 0; i < nums->count-1; ++i) {
+ if (data[i].depth == data[i+1].depth) {
+ int mag = data[i].value*3 + data[i+1].value*2;
+ struct num_t mul = {.value=mag, .depth=data[i].depth-1};
+ data[i] = mul;
+ array_remove(nums, i+1);
+ break;
+ }
+ }
}
+ struct num_t *data = nums->data;
+ return data[0].value;
+}
- assert(str[0] == '[');
- size_t processed = 1;
-
- if (str[processed] == '[') {
- printf("making left pair...\n");
- processed += make_pair(str+processed, pair, &pair->pleft);
- } else if (str[processed] >= '0' && str[processed] <= '9') {
- pair->left = malloc(sizeof(int));
- *pair->left = str[processed] - '0';
- pair->leftmost = &pair->left;
- printf("left num %d\n", *pair->left);
+void add(struct array_t *to, struct array_t *from) {
+ assert(to != NULL);
+ assert(from != NULL);
+ assert(to->elem_size == from->elem_size);
+ array_expand1(to, to->cap + from->cap);
+ assert(to->data != NULL);
+ struct num_t *to_data = to->data;
+ struct num_t *from_data = from->data;
+ for (size_t i = 0; i < to->count; ++i) {
+ to_data[i].depth++;
+ }
+ for (size_t i = 0; i < from->count; ++i) {
+ struct num_t num = from_data[i];
+ num.depth++;
+ to_data[to->count++] = num;
}
+}
- processed++;
- assert(str[processed] == ',');
- processed++;
-
- if (str[processed] == '[') {
- printf("making right pair...\n");
- processed += make_pair(str+processed, pair, &pair->pright);
- } else if (str[processed] >= '0' && str[processed] <= '9') {
- pair->right = malloc(sizeof(int));
- *pair->right = str[processed] - '0';
- pair->rightmost = &pair->right;
- printf("right num %d\n", *pair->right);
+bool explode(struct array_t *nums) {
+ assert(nums->count > 1);
+ struct num_t *array = nums->data;
+ for (size_t i = 0; i < nums->count-1; ++i) {
+ if (array[i].depth > 4 && array[i].depth == array[i+1].depth) {
+ if (i > 0) {
+ array[i-1].value += array[i].value;
+ }
+ if (i < nums->count-2) {
+ array[i+2].value += array[i+1].value;
+ }
+ array[i].depth--;
+ array[i].value = 0;
+ array_remove(nums, i+1);
+ return true;
+ }
}
+ return false;
+}
- processed++;
- assert(str[processed] == ']');
- printf("pair end\n");
+bool split(struct array_t *nums) {
+ assert(nums->count > 1);
+ struct num_t *array = nums->data;
+ for (size_t i = 0; i < nums->count; ++i) {
+ if (array[i].value > 9) {
+ double l = floor((double)array[i].value / 2.0);
+ double r = ceil((double)array[i].value / 2.0);
+ int depth = array[i].depth;
+ array_remove(nums, i);
+ array = nums->data;
+ if (i >= nums->count) {
+ array_add(nums, (struct num_t){.value=l, .depth=depth+1});
+ array_add(nums, (struct num_t){.value=r, .depth=depth+1});
+ } else {
+ array_insert(nums, i, (struct num_t){.value=r, .depth=depth+1});
+ array_insert(nums, i, (struct num_t){.value=l, .depth=depth+1});
+ }
+ return true;
+ }
+ }
+ return false;
+}
- return processed;
+void parse(const char *str, struct array_t *array) {
+ size_t len = strlen(str);
+ int depth = 0;
+ for (size_t i = 0; i < len-1; ++i) {
+ if (str[i] == '[') {
+ depth++;
+ } else if (str[i] == ']') {
+ depth--;
+ } else if (str[i] >= '0' && str[i] <= '9') {
+ if (array->count >= array->cap) array_expand(array);
+ ((struct num_t *)array->data)[array->count++] = (struct num_t){.value=str[i]-'0', .depth=depth};
+ }
+ }
+}
+
+void print_nums(struct array_t *array) {
+ struct num_t *nums = array->data;
+ for (size_t i = 0; i < array->count; ++i) {
+ printf("%2d,", nums[i].value);
+ }
+ printf("\n");
}
-void print_pair(struct pair_t *pair) {
- printf("[");
- if (pair->pleft != NULL) {
- print_pair(pair->pleft);
- } else {
- printf("%d", *pair->left);
+void array_remove(struct array_t *nums, size_t index) {
+ assert(index < nums->count);
+ struct num_t *data = nums->data;
+ struct num_t *new_data = calloc(nums->count-1, nums->elem_size);
+ assert(new_data != NULL);
+ size_t new_count = 0;
+ for (size_t i = 0; i < nums->count; ++i) {
+ if (i != index) {
+ new_data[new_count++] = data[i];
+ }
}
- printf(",");
- if (pair->pright != NULL) {
- print_pair(pair->pright);
- } else {
- printf("%d", *pair->right);
+ free(data);
+ nums->data = new_data;
+ nums->count = new_count;
+ nums->cap = new_count;
+}
+
+void array_insert(struct array_t *nums, size_t index, struct num_t num) {
+ assert(index < nums->count);
+ struct num_t *data = nums->data;
+ struct num_t *new_data = calloc(nums->count + 1, nums->elem_size);
+ assert(new_data != NULL);
+ size_t new_count = 0;
+ for (size_t i = 0; i < nums->count; ++i) {
+ if (i == index) {
+ new_data[new_count++] = num;
+ new_data[new_count++] = data[i];
+ } else {
+ new_data[new_count++] = data[i];
+ }
}
- printf("]");
+ nums->data = new_data;
+ nums->count = new_count;
+ nums->cap = new_count;
+}
+
+
+void array_add(struct array_t *nums, struct num_t num) {
+ assert(nums != NULL);
+ if (nums->count >= nums->cap) array_expand(nums);
+ struct num_t *data = nums->data;
+ data[nums->count++] = num;
}
