I’m a bit confused reading through the rules, it seems impossible to determine when allergens may not always be listed. I probably just need to read through it again, but for now I’ll move on to today’s problem.

four hours later, afer getting stuck on 22.2…

I think this is the key that I didn’t fully appreciate on first read: “Each allergen is found in exactly one ingredient.” Let’s walk through the example:

``````mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)
``````
1. The first two both contain dairy, and the only common ingredient is `mxmxvkd`, so that must be the dairy ingredient.
2. The first and last both contain fish, and have `mxmxvkd` and `sqjhc` in common. Since we know `mxmvkd` is dairy, then `sqjhc` must be fish.
3. The third only contains two ingredients: we know `sqjhc` contains fish, which isn’t indicated, so `fvjkl` must be soy.
4. So now we know the three ingredients for the three listed allergens, so the remaining ingredients cannot have them: `kfcds`, `nhms`, `trh`, and `sbzzf`.

Oh good, that agrees with the problem statement! So as with day 16 we can generalize these into several rules, that we’ll then be able to apply via set operations:

1. If two foods contains the same allergen and only have one ingredient in common (that doesn’t have a known allergen), the allergen must be in that ingredient.
2. If a food only contains one ingredient that is not a known allergen, and has one unknown allergen listed, the allergen must be in that ingredient.

Start with reading the food list into a data structure, using `Set` for the ingredients and allergens.

``````struct Food
ingredients::Set{AbstractString}
allergens::Set{AbstractString}
end
Foods = Vector{Food}
``````

We’ll then combine all foods into supersets of all ingredients and allergens, which we’ll pull from (and stick into a `Dict`) as things are solved:

``````    for f in foods
ingredients = union!(ingredients, f.ingredients)
allergens = union!(allergens, f.allergens)
end
# map allergen to the ingredient that contains it
known = Dict{AbstractString,AbstractString}()
``````

Implementing the above rules is straightforward. For number one: for each allergen, collect the set of ingredients that are common to all foods with that allergen; if there is only one ingredient then it must contain that allergen.

``````        for a in allergens
common = copy(ingredients)
for f in foods
if a in f.allergens
intersect!(common, f.ingredients)
end
end
if length(common) == 1
known[a] = first(common)
delete!(allergens,a)
delete!(ingredients,known[a])
end
end
``````

For number 2: for each food, build a set of its ingredients that are not known to be allergens, and a set of its allergens with unknown ingredients; if both of those only contain one item then that ingredient is the allergen.

``````        for f in foods
ui = setdiff(f.ingredients, values(known))
ua = setdiff(f.allergens, keys(known))
if length(ui) == length(ua) == 1
known[first(ua)] = first(ui)
delete!(allergens,first(ua))
delete!(ingredients,first(ui))
end
end
``````

We repeat these steps until there are no more unknown allergens (or we were unable to deduce any more allergens after applying these rules). Then we count up the non-allergenic ingredients in the foods:

``````    sum([length(setdiff(f.ingredients, values(known))) for f in foods])
``````

## Part 2

Well this is an unusually simple part 2 - or was there a simpler way to do part 1? In any case, now we just need to sort the known allergens and combine their respective ingredients into a list:

``````    l = join([known[k] for k in sort(collect(keys(known)))], ",")
``````