#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>
typedef struct {
bool departure;
unsigned min1;
unsigned max1;
unsigned min2;
unsigned max2;
bool may_fit_field[25];
} rule_t;
bool is_between(unsigned min, unsigned i, unsigned max) {
return (min <= i) && (i <= max);
}
bool rule_applies_to_field(rule_t *r, unsigned field) {
return is_between(r->min1, field, r->max1) || is_between(r->min2, field, r->max2);
}
bool any_rule_applies(rule_t *r, size_t n, unsigned f) {
for (size_t i = 0; i < n; ++i) {
if (rule_applies_to_field(r + i, f)) {
return true;
}
}
return false;
}
int main(void) {
rule_t rules[25] = { 0, };
unsigned my_ticket[25] = { 0, };
/* read rules */
char buf[100] = { 0, };
size_t n_rules = 0;
for (; fgets(buf, sizeof buf, stdin) != 0 && buf[0] && buf[0] != '\n'; ++n_rules) {
if (n_rules >= sizeof rules / sizeof *rules) {
fprintf(stderr, "Error: Too many rules.\n");
return 1;
}
rule_t *r = rules + n_rules;
const char *departure = "departure";
if (strncmp(buf, departure, (sizeof departure) - 1) == 0) {
r->departure = true;
}
else {
r->departure = false;
}
char *b = buf;
for (; *b && *b != ':'; ++b);
if (sscanf(b, ": %u-%u or %u-%u\n", &r->min1, &r->max1, &r->min2, &r->max2) != 4) {
fprintf(stderr, "Error parsing rule:\n%s", buf);
return 1;
}
memset(r->may_fit_field, 1, sizeof r->may_fit_field);
}
/* read my ticket */
(void) fgets(buf, sizeof buf, stdin); /* "your ticket:\n" */
for (size_t i_f = 0; i_f < n_rules; ++i_f) {
(void) scanf("%u", my_ticket + i_f); /* error? meh. */
(void) getchar(); /* ',' or line feed */
}
/* read other tickets, validate them, check which rules may correspond to which fields */
(void) getchar(); /* line feed */
(void) fgets(buf, sizeof buf, stdin); /* "nearby tickets:\n" */
int sum_of_invalid_fields = 0;
unsigned fields[25] = { 0, };
size_t i_f = 0;
while (scanf("%u", fields + i_f) > 0) {
++i_f;
if (getchar() != ',') {
/* part 1 filter */
bool is_valid = true;
for (size_t i_f = 0; i_f < n_rules; ++i_f) {
if (!any_rule_applies(rules, n_rules, fields[i_f])) {
is_valid = false;
sum_of_invalid_fields += fields[i_f];
}
}
/* part 2 filter */
if (is_valid) {
for (size_t i_f = 0; i_f < n_rules; ++i_f) {
unsigned f = fields[i_f];
for (size_t i_r = 0; i_r < n_rules; ++i_r) {
rule_t *r = rules + i_r;
if (!rule_applies_to_field(r, f)) {
r->may_fit_field[i_f] = false;
}
}
}
}
i_f = 0;
}
if (i_f > n_rules) {
fprintf(stderr, "Too many fields.\n");
return 1;
}
}
if (ferror(stdin)) {
fprintf(stderr, "Input error: %s\n", strerror(errno));
return 1;
}
printf("%lld\n", (long long) sum_of_invalid_fields);
/* part 2 solution */
unsigned assigned_fields[25] = { 0, }; /* given a rule index, get the assigned field */
for (size_t k = 0; k < n_rules; ++k) {
/* find a rule for which only one field fits */
for (size_t i_r = 0; i_r < n_rules; ++i_r) {
unsigned number_of_possible_fields = 0;
size_t field = 0;
for (size_t i_f = 0; i_f < n_rules && number_of_possible_fields < 2; ++i_f) {
if (rules[i_r].may_fit_field[i_f]) {
++number_of_possible_fields;
field = i_f;
}
}
if (number_of_possible_fields == 1) {
assigned_fields[i_r] = field;
for (size_t i_r = 0; i_r < n_rules; ++i_r) {
rules[i_r].may_fit_field[field] = false;
}
break;
}
}
}
unsigned long long prod = 1;
for (size_t i = 0; i < n_rules; ++i) {
if (rules[i].departure) {
prod *= (unsigned long long) my_ticket[assigned_fields[i]];
}
}
printf("%llu\n", prod);
return 0;
}