commit 0cb07f7525c02b174048f0e3c5698314af318979
parent 2c3ad918011007019947390ec0af469075f9d779
Author: bsandro <[email protected]>
Date: Wed, 15 Dec 2021 02:22:11 +0200
Day 14, puzzle 2 (non-cleaned version)
Diffstat:
2 files changed, 225 insertions(+), 70 deletions(-)
diff --git a/day14/main.c b/day14/main.c
@@ -2,7 +2,7 @@
#include <time.h>
#include <string.h>
-void puzzle(const char *filename, long long *res1, long long *res2);
+void puzzle(const char *filename, unsigned long long *res1, unsigned long long *res2);
int main(int argc, char *argv[]) {
printf("Advent of Code: day 14\n");
@@ -14,13 +14,13 @@ int main(int argc, char *argv[]) {
}
const char *filename = argv[1];
- long long counter1 = -1;
- long long counter2 = -1;
+ unsigned long long counter1 = -1;
+ unsigned long long counter2 = -1;
puzzle(filename, &counter1, &counter2);
- printf("Puzzle #1: %lld\n", counter1);
- printf("Puzzle #2: %lld\n", counter2);
+ printf("Puzzle #1: %llu\n", counter1);
+ printf("Puzzle #2: %llu\n", counter2);
double elapsed = clock() - time_start;
printf("Elapsed: %f\n", elapsed / CLOCKS_PER_SEC);
diff --git a/day14/puzzle.c b/day14/puzzle.c
@@ -15,24 +15,35 @@
#define STR_LEN 32
struct rule_t {
- char search[3];
- char replace[4];
+ char name[3];
+ char child;
+ struct rule_t *children[2];
+ long long score;
};
struct count_t {
+ struct rule_t *section;
char symbol;
- long long count;
+ unsigned long long count;
};
-void parse_rule(struct array_t *rules, const char *str);
+long long parse_rule(struct array_t *rules, const char *str);
+void process_rules(struct array_t *rules);
void print_rules(struct array_t *rules);
-bool apply_rules(const struct array_t *rules, const char s1, const char s2, char **str_new);
-long long count_result1(const char *str);
-void add_count(struct array_t *counts, const char symbol);
-long long get_min_count(const struct array_t *counts);
-long long get_max_count(const struct array_t *counts);
+struct rule_t * get_rule(struct array_t *rules, const char name[3]);
+struct array_t make_sections_count(struct array_t *sections);
+void add_section_count(struct array_t *counts, struct rule_t *section, unsigned long long count);
+void add_symbol_count(struct array_t *counts, char symbol, unsigned long long multiplier);
+unsigned long long get_min_count(const struct array_t *counts);
+unsigned long long get_max_count(const struct array_t *counts);
+struct array_t get_sections(struct array_t *orig_rules, const char *str);
+struct array_t iterate_sections_count(struct array_t *rules, struct array_t counts);
+unsigned long long get_count(struct array_t *counts, struct rule_t *section);
+void print_sections(struct array_t *sections);
+void print_sections_count(struct array_t *rules, struct array_t *sections);
+unsigned long long get_char_counts(struct array_t counts);
-void puzzle(const char *filename, long long *result1, long long *result2) {
+void puzzle(const char *filename, unsigned long long *result1, unsigned long long *result2) {
FILE *infile = fopen(filename, "r");
if (infile == NULL) {
fprintf(stderr, "fopen() error: %s\n", strerror(errno));
@@ -42,9 +53,6 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
char buf[STR_LEN] = {0};
unsigned int line_num = 0;
- *result1 = 0;
- *result2 = 0;
-
bool rules_started = false;
char *str = NULL;
struct array_t rules = { .data = NULL };
@@ -66,69 +74,151 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
bzero(buf, STR_LEN);
}
+ process_rules(&rules);
//printf("input str: %s\n", str);
//print_rules(&rules);
- for (int i = 0; i < 10; ++i) {
- char *str_new = NULL;
- size_t str_len = strlen(str);
- //printf("iter %d, str len: %zu\n", i, str_len);
- for (size_t s = 0; s < str_len; ++s) {
- if (!apply_rules(&rules, str[s], str[s+1], &str_new)) {
- size_t str_new_len = strlen(str_new);
- str_new = realloc(str_new, str_new_len+1);
- str_new[str_new_len] = str[s];
- }
+ struct array_t sections = get_sections(&rules, str);
+ //print_sections(§ions);
+
+ struct array_t sections_count = make_sections_count(§ions);
+ //print_sections_count(&rules, §ions_count);
+
+ for (int i = 0; i < 40; ++i) {
+ struct array_t sections_count1 = iterate_sections_count(&rules, sections_count);
+ //print_sections_count(&rules, §ions_count1);
+ free(sections_count.data);
+ sections_count = sections_count1;
+
+ if (i == 9) {
+ *result1 = get_char_counts(sections_count);
}
- //printf("new str: %s\n", str_new);
- free(str);
- str = str_new;
}
- *result1 = count_result1(str);
+ *result2 = get_char_counts(sections_count);
free(str);
+ free(sections.data);
+ free(sections_count.data);
free(rules.data);
// mutiny! ignoring feof/ferror.
fclose(infile);
}
-bool apply_rules(const struct array_t *rules, const char s1, const char s2, char **str_new) {
+struct array_t iterate_sections_count(struct array_t *rules, struct array_t counts) {
assert(rules != NULL);
- const struct rule_t *data = rules->data;
- for (size_t j = 0; j < rules->count; ++j) {
- struct rule_t rule = data[j];
- if (rule.search[0] == s1 && rule.search[1] == s2) {
- size_t str_new_len = 4;
- if (*str_new != NULL) {
- str_new_len = strlen(*str_new) + 4;
- }
- *str_new = realloc(*str_new, str_new_len);
- strlcat(*str_new, rule.replace, str_new_len);
- return true;
+ struct array_t new_counts = { .data = NULL };
+ array_init(&new_counts, sizeof(struct count_t), counts.cap);
+
+ struct count_t *counts_data = counts.data;
+ for (size_t i = 0; i < counts.count; ++i) {
+ struct rule_t *rule = counts_data[i].section;
+ if (counts_data[i].count > 0) {
+ //printf("\n%s spawning %s+%s\n", rule->name, rule->children[0]->name, rule->children[1]->name);
+ //long long c1 = get_count(&counts, rule->children[0]);
+ //long long c2 = get_count(&counts, rule->children[1]);
+ //printf("%s count %lld x %lld and %lld\n", rule->name, counts_data[i].count, c1, c2);
+ add_section_count(&new_counts, rule->children[0], counts_data[i].count);
+ add_section_count(&new_counts, rule->children[1], counts_data[i].count);
+ }
+ }
+
+ return new_counts;
+}
+
+unsigned long long get_count(struct array_t *counts, struct rule_t *section) {
+ struct count_t *counts_data = counts->data;
+ for (size_t i = 0; i < counts->count; ++i) {
+ if (counts_data[i].section == section) {
+ //printf("\nSECTION FOUND: %lld\n", counts_data[i].count);
+ return counts_data[i].count;
+ }
+ }
+
+ return 0;
+}
+
+void print_sections(struct array_t *sections) {
+ assert(sections != NULL);
+ struct rule_t **data = sections->data;
+ for (size_t i = 0; i < sections->count; ++i) {
+ if (i == 0) {
+ printf("%s", data[i]->name);
+ } else {
+ printf("%c", data[i]->name[1]);
}
}
- return false;
+ printf("\n");
}
-long long count_result1(const char *str) {
+struct array_t make_sections_count(struct array_t *sections) {
struct array_t counts = { .data = NULL };
array_init(&counts, sizeof(struct count_t), 10);
- size_t len = strlen(str);
- for (size_t i = 0; i < len; ++i) {
- add_count(&counts, str[i]);
+ struct rule_t **data = sections->data;
+ for (size_t i = 0; i < sections->count; ++i) {
+ add_section_count(&counts, data[i], 1);
}
- free(counts.data);
- return get_max_count(&counts) - get_min_count(&counts);
+ return counts;
}
-void add_count(struct array_t *counts, const char symbol) {
+unsigned long long get_char_counts(struct array_t counts) {
+ struct array_t char_counts = { .data = NULL };
+ array_init(&char_counts, sizeof(struct count_t), 10);
+
+ struct count_t *counts_data = counts.data;
+ for (size_t i = 0; i < counts.count; ++i) {
+ //printf("%s: %lld\n", counts_data[i].section->name, counts_data[i].count);
+ if (i == 0) {
+ add_symbol_count(&char_counts, counts_data[i].section->name[0], 1);
+ }
+ add_symbol_count(&char_counts, counts_data[i].section->name[1], counts_data[i].count);
+ }
+ //printf("\n");
+
+ struct count_t *char_counts_data = char_counts.data;
+ unsigned long long total_count = 0;
+ for (size_t i = 0; i < char_counts.count; ++i) {
+ //printf("%c: %lld\n", char_counts_data[i].symbol, char_counts_data[i].count);
+ total_count += char_counts_data[i].count;
+ }
+
+ unsigned long long count_min = get_min_count(&char_counts);
+ unsigned long long count_max = get_max_count(&char_counts);
+
+ //printf("\nmin: %llu, max: %llu, total: %llu\n", count_min, count_max, total_count);
+
+ return count_max - count_min;
+}
+
+void print_sections_count(struct array_t *rules, struct array_t *counts) {
+ struct count_t *counts_data = counts->data;
+ struct rule_t *rules_data = rules->data;
+ for (size_t r = 0; r < rules->count; ++r) {
+ bool section_found = false;
+ for (size_t i = 0; i < counts->count; ++i) {
+ if (counts_data[i].section == &rules_data[r]) {
+ printf("%s: %3llu ", counts_data[i].section->name, counts_data[i].count);
+ //printf("%5lld", counts_data[i].count);
+ section_found = true;
+ break;
+ }
+ }
+ if (!section_found) {
+ printf("%s: %3d ", rules_data[r].name, 0);
+ //printf("%5d", 0);
+ }
+ }
+ printf("\n");
+}
+
+void add_section_count(struct array_t *counts, struct rule_t *section, unsigned long long count) {
assert(counts != NULL);
+ assert(section != NULL);
struct count_t *data = counts->data;
for (size_t i = 0; i < counts->count; ++i) {
- if (data[i].symbol == symbol) {
- data[i].count++;
+ if (data[i].section == section) {
+ data[i].count += count;
return;
}
}
@@ -137,34 +227,48 @@ void add_count(struct array_t *counts, const char symbol) {
array_expand(counts);
}
data = counts->data;
- data[counts->count++] = (struct count_t){ .symbol = symbol, .count = 1 };
+ data[counts->count++] = (struct count_t){ .section = section, .count = count };
}
-long long get_min_count(const struct array_t *counts) {
+void add_symbol_count(struct array_t *counts, char symbol, unsigned long long multiplier) {
assert(counts != NULL);
struct count_t *data = counts->data;
- long long min = -1;
for (size_t i = 0; i < counts->count; ++i) {
- if (min == -1) {
- min = data[i].count;
- } else {
- min = data[i].count < min ? data[i].count : min;
+ if (data[i].symbol == symbol) {
+ data[i].count += multiplier;
+ return;
}
}
- return min;
+
+ if (counts->count >= counts->cap) {
+ array_expand(counts);
+ }
+ data = counts->data;
+ data[counts->count++] = (struct count_t){ .symbol = symbol, .count = multiplier };
}
-long long get_max_count(const struct array_t *counts) {
+
+unsigned long long get_max_count(const struct array_t *counts) {
assert(counts != NULL);
struct count_t *data = counts->data;
- long long max = 0;
+ unsigned long long max = 0;
for (size_t i = 0; i < counts->count; ++i) {
max = data[i].count > max ? data[i].count : max;
}
return max;
}
-void parse_rule(struct array_t *rules, const char *str) {
+unsigned long long get_min_count(const struct array_t *counts) {
+ assert(counts != NULL);
+ struct count_t *data = counts->data;
+ unsigned long long min = ULLONG_MAX;
+ for (size_t i = 0; i < counts->count; ++i) {
+ min = data[i].count < min ? data[i].count : min;
+ }
+ return min;
+}
+
+long long parse_rule(struct array_t *rules, const char *str) {
assert(rules != NULL);
assert(str != NULL);
char *tmp = strndup(str, STR_LEN);
@@ -178,12 +282,11 @@ void parse_rule(struct array_t *rules, const char *str) {
assert(n < 2);
if (n == 0) {
assert(strlen(token) == 2);
- strlcpy(rule.search, token, 3);
- rule.replace[0] = token[0];
- //rule.replace[2] = token[1];
+ strlcpy(rule.name, token, 3);
+ rule.score = rule.name[0] * 1000 + rule.name[1];
} else {
assert(strlen(token) == 1);
- rule.replace[1] = token[0];
+ rule.child = token[0];
}
n++;
}
@@ -196,12 +299,64 @@ void parse_rule(struct array_t *rules, const char *str) {
struct rule_t *data = rules->data;
data[rules->count++] = rule;
free(tmp);
+ return rule.score;
}
void print_rules(struct array_t *rules) {
assert(rules != NULL);
struct rule_t *data = rules->data;
for (size_t i = 0; i < rules->count; ++i) {
- printf("%s -> %s\n", data[i].search, data[i].replace);
+ printf("(%lld) %s -> %c", data[i].score, data[i].name, data[i].child);
+ printf(" (%s, %s)\n", data[i].children[0]->name, data[i].children[1]->name);
}
}
+
+void process_rules(struct array_t *rules) {
+ assert(rules != NULL);
+ struct rule_t *data = rules->data;
+ for (size_t i = 0; i < rules->count; ++i) {
+ char name1[3] = {0};
+ char name2[3] = {0};
+ name1[0] = data[i].name[0];
+ name1[1] = data[i].child;
+ name2[0] = data[i].child;
+ name2[1] = data[i].name[1];
+ struct rule_t *child1 = get_rule(rules, name1);
+ struct rule_t *child2 = get_rule(rules, name2);
+ assert(child1 != NULL);
+ assert(child2 != NULL);
+ data[i].children[0] = child1;
+ data[i].children[1] = child2;
+ }
+}
+
+struct rule_t * get_rule(struct array_t *rules, const char name[3]) {
+ assert(rules != NULL);
+ struct rule_t *data = rules->data;
+ for (size_t i = 0; i < rules->count; ++i) {
+ if (data[i].name[0] == name[0] && data[i].name[1] == name[1]) {
+ return &data[i];
+ }
+ }
+ return NULL;
+}
+
+struct array_t get_sections(struct array_t *rules, const char *str) {
+ assert(str != NULL);
+ assert(rules != NULL);
+ size_t len = strlen(str);
+ struct array_t sections = { .data = NULL };
+ array_init(§ions, sizeof(void *), 10);
+ for (size_t i = 0; i < len - 1; ++i) {
+ char name[3] = { str[i], str[i+1], 0};
+ if (sections.count >= sections.cap) {
+ array_expand(§ions);
+ }
+ struct rule_t **data = sections.data;
+ struct rule_t *rule = get_rule(rules, name);
+ assert(rule != NULL);
+ data[sections.count++] = rule;
+ }
+
+ return sections;
+}
