Expand description
§Allergen Assessment
The rules can be expressed as:
- If an ingredient is on a line, then it may contain the listed allergens.
- If an ingredient is not on a line, then it definitely does not contain the listed allergens, as some other food on the line must instead contain the allergen.
§Part One
To find the safe foods we build two sets, then subtract them to find out the remaining possible
allergens. It’s important to only subtract the sets at the very end in order to prevent
re-adding a previously excluded allergen. Using kfcds from the example:
| Line | Possible | Impossible |
|---|---|---|
| 1 | Dairy, Fish | Ø |
| 2 | Dairy, Fish | Dairy |
| 3 | Dairy, Fish | Dairy, Soy |
| 4 | Dairy, Fish | Dairy, Soy, Fish |
Final result: Ø (the empty set)
§Part Two
This is a constraint satisfaction problem,
similar to day 16. Using fvjkl from the example:
| Line | Possible | Impossible |
|---|---|---|
| 1 | Ø | Dairy, Fish |
| 2 | Dairy | Dairy, Fish |
| 3 | Dairy, Soy | Dairy, Fish |
| 4 | Dairy, Soy | Dairy, Fish |
Final result: Soy
To solve there must be at least one ingredient with only one allergen remaining. As this allergen can only belong to this ingredient, we eliminate it from other ingredients. This causes a chain reaction where a second ingredient will reduce to only one allergen, continuing until all allergens have been resolved.
As there are less than 64 lines and allergens we can speed things up by using bitwise logic
on a usize to compute set addition and subtraction. To add to a set use OR |,
to remove use AND & and to calculate the size use count_ones.