#advent of code 2020
#day 21
#part 2 very similar to ticket problem from the same year

ingredients = [];
AllergyDict = dict();
PossibleAllergens = set();
AssignedAllergens = dict();

PuzzleInput = open("21.in","r");
for line in PuzzleInput:
	line = line.replace("\n","");
	FoodIngr, FoodAllr = line[:-1].split(" (contains ");
	FoodIngr = FoodIngr.split(" ");
	FoodAllr = FoodAllr.split(", ");
	ingredients.extend(FoodIngr);	
	for a in FoodAllr:
		if a in AllergyDict:
			AllergyDict[a].intersection_update(set(FoodIngr));
		else:
			AllergyDict[a] = set(FoodIngr);
PuzzleInput.close();

for al in AllergyDict:
	print(al, AllergyDict[al]);
	PossibleAllergens.update(AllergyDict[al]);

p1 = len([i for i in ingredients if i not in PossibleAllergens]);
print("part 1 =",p1);

while len(AssignedAllergens) != len(AllergyDict):
	#print(len(AssignedAllergens),"/", len(AllergyDict)); #in case it takes long
	for al in AllergyDict:
		if len(AllergyDict[al]) == 1:
			found = AllergyDict[al].pop();
			AssignedAllergens[al] = found;
		else:
			AllergyDict[al].difference_update( AssignedAllergens.values() );

p2 = ",".join([AssignedAllergens[allergen] for allergen in sorted(AssignedAllergens.keys())]);
print("part 2 =",p2);