advent2021

puzzle.c (7631B)

---

 #define _DEFAULT_SOURCE
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <assert.h>
 #include <ctype.h>
 #include <limits.h>
 #include <stdbool.h>
 
 #include "util.h"
 
 #define STR_LEN 32
 
 struct rule_t {
 	char name[3];
 	char child;
 	struct rule_t *children[2];
 	long long score;
 };
 
 struct count_t {
 	struct rule_t *section;
 	char symbol;
 	unsigned long long count;
 };
 
 long long parse_rule(struct array_t *rules, const char *str);
 void process_rules(struct array_t *rules);
 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 make_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_char_counts(struct array_t counts);
 
 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));
 		return;
 	}
 
 	char buf[STR_LEN] = {0};
 	unsigned int line_num = 0;
 
 	bool rules_started = false;
 	char *str = NULL;
 	struct array_t rules = { .data = NULL };
 	array_init(&rules, sizeof(struct rule_t), 10);
 	while (fgets(buf, STR_LEN, infile) != NULL) {
 		if (strlen(buf) == 1) {
 			rules_started = true;
 			continue;
 		}
 		if (rules_started) {
 			parse_rule(&rules, buf);
 		} else {
 			assert(str == NULL);
 			size_t len = strlen(buf);
 			str = malloc(len);
 			bzero(str, len);
 			strncpy(str, buf, len-1); // losing last symbol \n
 		}
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
 	process_rules(&rules);
 	struct array_t sections = make_sections(&rules, str);
 	struct array_t sections_count = make_sections_count(&sections);
 
 	for (int i = 0; i < 40; ++i) {
 		struct array_t sections_count1 = iterate_sections_count(&rules, sections_count);
 		free(sections_count.data);
 		sections_count = sections_count1;
 
 		if (i == 9) {
 			*result1 = get_char_counts(sections_count);
 		}
 	}
 
 	*result2 = get_char_counts(sections_count);
 
 	free(str);
 	free(sections.data);
 	free(sections_count.data);
 	free(rules.data);
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
 struct array_t iterate_sections_count(struct array_t *rules, struct array_t counts) {
 	assert(rules != NULL);
 	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) {
 			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;
 }
 
 struct array_t make_sections_count(struct array_t *sections) {
 	struct array_t counts = { .data = NULL };
 	array_init(&counts, sizeof(struct count_t), 10);
 	struct rule_t **data = sections->data;
 	for (size_t i = 0; i < sections->count; ++i) {
 		add_section_count(&counts, data[i], 1);
 	}
 
 	return counts;
 }
 
 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) {
 		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);
 	}
 
 	unsigned long long count_min = get_min_count(&char_counts);
 	unsigned long long count_max = get_max_count(&char_counts);
 
 	return count_max - count_min;
 }
 
 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].section == section) {
 			data[i].count += count;
 			return;
 		}
 	}
 
 	if (counts->count >= counts->cap) {
 		array_expand(counts);
 	}
 	data = counts->data;
 	data[counts->count++] = (struct count_t){ .section = section, .count = count };
 }
 
 void add_symbol_count(struct array_t *counts, char symbol, unsigned long long multiplier) {
 	assert(counts != NULL);
 	struct count_t *data = counts->data;
 	for (size_t i = 0; i < counts->count; ++i) {
 		if (data[i].symbol == symbol) {
 			data[i].count += multiplier;
 			return;
 		}
 	}
 
 	if (counts->count >= counts->cap) {
 		array_expand(counts);
 	}
 	data = counts->data;
 	data[counts->count++] = (struct count_t){ .symbol = symbol, .count = multiplier };
 }
 
 
 unsigned long long get_max_count(const struct array_t *counts) {
 	assert(counts != NULL);
 	struct count_t *data = counts->data;
 	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;
 }
 
 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);
 	assert(tmp != NULL);
 	char *token = NULL;
 
 	int n = 0;
 	struct rule_t rule = {0};
 	while ((token = strsep(&tmp, " ->\n")) != NULL) {
 		if (*token != '\0') {
 			assert(n < 2);
 			if (n == 0) {
 				assert(strlen(token) == 2);
 				strncpy(rule.name, token, 3);
 				rule.score = rule.name[0] * 1000 + rule.name[1];
 			} else {
 				assert(strlen(token) == 1);
 				rule.child = token[0];
 			}
 			n++;
 		}
 	}
 
 	if (rules->count >= rules->cap) {
 		array_expand(rules);
 	}
 
 	struct rule_t *data = rules->data;
 	data[rules->count++] = rule;
 	free(tmp);
 	return rule.score;
 }
 
 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 make_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(&sections, 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(&sections);
 		}
 		struct rule_t **data = sections.data;
 		struct rule_t *rule = get_rule(rules, name);
 		assert(rule != NULL);
 		data[sections.count++] = rule;
 	}
 
 	return sections;
 }