#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define LENGTH(arr) (sizeof (arr) / sizeof *(arr))
#define MAX_NAME_LENGTH 15
#define MAX_NAME_LENGTH_S "14"
#define MAX_INGREDIENTS 250
#define MAX_ALLERGENS 10
typedef struct {
bool set[MAX_INGREDIENTS];
} int_set_t;
typedef struct {
bool set[MAX_ALLERGENS];
} small_int_set_t;
typedef struct {
char buf[MAX_NAME_LENGTH];
} name_t;
typedef struct {
size_t allergen;
size_t ingredient;
} match_t;
size_t findindex(const name_t *t, const name_t *table, size_t n) {
for (size_t i = 0; i < n; ++i) {
if (strcmp(table[i].buf, t->buf) == 0) {
return i;
}
}
return n;
}
void set_intersect(int_set_t *set1, const int_set_t *set2) {
for (size_t i = 0; i < MAX_INGREDIENTS; ++i) {
set1->set[i] &= set2->set[i];
}
}
void set_union(int_set_t *set1, const int_set_t *set2) {
for (size_t i = 0; i < MAX_INGREDIENTS; ++i) {
set1->set[i] |= set2->set[i];
}
}
int main(void) {
int_set_t food_ingredients[40];
small_int_set_t food_allergens[40];
size_t n_foods = 0;
name_t all_allergens[MAX_ALLERGENS];
size_t n_allergens = 0;
name_t all_ingredients[MAX_INGREDIENTS];
size_t n_ingredients = 0;
/* read input */
char buf[1000];
while (fgets(buf, sizeof buf, stdin) != NULL) {
if (n_foods >= LENGTH(food_ingredients)) {
fprintf(stderr, "Error: Too many foods.\n");
return 1;
}
memset(food_ingredients + n_foods, 0, sizeof food_ingredients[n_foods]);
memset(food_allergens + n_foods, 0, sizeof food_allergens[n_foods]);
++n_foods;
if ((!buf[0]) || buf[0] == '\n') {
break;
}
/* read ingredients */
char *b = buf;
name_t name;
int consumed = 0;
while (sscanf(b, "%"MAX_NAME_LENGTH_S"s %n", name.buf, &consumed) > 0 && name.buf[0]) {
b += consumed;
size_t i = findindex(&name, all_ingredients, n_ingredients);
if (name.buf[0] == '(') {
break; /* must be "contains" */
}
if (i >= n_ingredients) {
/* if we have not seen this ingredient before, remember its name */
if (n_ingredients < MAX_INGREDIENTS) {
all_ingredients[n_ingredients++] = name;
}
else {
fprintf(stderr, "Error: Too many ingredients.\n");
return 1;
}
}
food_ingredients[n_foods-1].set[i] = true;
}
/* read allergens */
while (sscanf(b, "%"MAX_NAME_LENGTH_S"s %n", name.buf, &consumed) > 0 && name.buf[0]) {
b += consumed;
size_t fi = strlen(name.buf) - 1;
if (fi == 0) {
break;
}
if (name.buf[fi] == ')' || name.buf[fi] == ',') {
name.buf[fi] = '\0';
}
size_t i = findindex(&name, all_allergens, n_allergens);
if (i >= n_allergens) {
/* if we have not seen this ingredient before, remember its name */
if (n_allergens < MAX_ALLERGENS) {
all_allergens[n_allergens++] = name;
}
else {
fprintf(stderr, "Error: Too many allergens.\n");
return 1;
}
}
food_allergens[n_foods-1].set[i] = true;
}
}
/* for each allergen, see which ingredients it may be contained in (assuming that there is exactly one); also mark ingredients which cannot correspond to any allergen */
int_set_t potential_ingredients[MAX_ALLERGENS];
memset(&potential_ingredients, 0, sizeof potential_ingredients);
int_set_t unsafe;
memset(&unsafe, 0, sizeof unsafe);
for (size_t i_all = 0; i_all < n_allergens; ++i_all) {
for (size_t i_ingr = 0; i_ingr < n_ingredients; ++i_ingr) {
potential_ingredients[i_all].set[i_ingr] = true;
}
for (size_t i_food = 0; i_food < n_foods; ++i_food) {
if (food_allergens[i_food].set[i_all]) {
set_intersect(potential_ingredients + i_all, food_ingredients + i_food);
}
}
set_union(&unsafe, potential_ingredients + i_all);
}
/* part1: count occurrences of "definitely" safe foods (... safe as per the description) */
size_t safe_count = 0;
for (size_t i = 0; i < n_ingredients; ++i) {
if (!unsafe.set[i]) {
for (size_t j = 0; j < n_foods; ++j) {
safe_count += food_ingredients[j].set[i];
}
}
}
printf("%zu\n", safe_count);
/* part 2: repeatedly match ingredients to allergens for those with just one possibility */
match_t matches[MAX_ALLERGENS];
size_t n_matched = 0;
bool already_matched[MAX_ALLERGENS] = { 0, };
bool found_unassigned = false;
do {
found_unassigned = false;
for (size_t i_allergen = 0; i_allergen < n_allergens; ++i_allergen) {
if (already_matched[i_allergen]) {
continue;
}
found_unassigned = true;
/* is there exactly one possible ingredient for the current allergen? */
size_t i_ingredient = 0;
size_t n_possibilities = 0;
for (size_t i = 0; i < n_ingredients; ++i) {
if (potential_ingredients[i_allergen].set[i]) {
i_ingredient = i;
++n_possibilities;
}
}
if (n_possibilities == 1) {
/* assign it, then remove the ingredient from other potential matches */
matches[n_matched].allergen = i_allergen;
matches[n_matched].ingredient = i_ingredient;
already_matched[i_allergen] = true;
for (size_t j = 0; j < n_allergens; ++j) {
potential_ingredients[j].set[i_ingredient] = false;
}
++n_matched;
break;
}
}
} while (found_unassigned);
/* sort the matches in-place by allergen name. Selection sort works fine because there are only 8 allergens */
for (size_t i = 0; i < n_allergens; ++i) {
for (size_t j = i+1; j < n_allergens; ++j) {
if (strcmp(all_allergens[matches[i].allergen].buf, all_allergens[matches[j].allergen].buf) > 0) {
match_t m = matches[i];
matches[i] = matches[j];
matches[j] = m;
}
}
}
/* output matched ingredient names */
for (size_t i = 0; i < n_allergens; ++i) {
size_t i_ingredient = matches[i].ingredient;
printf("%s%c", all_ingredients[i_ingredient].buf, (i + 1 < n_allergens)? ',' : '\n');
}
return 0;
}