73 lines
1.6 KiB
Python
73 lines
1.6 KiB
Python
#!/usr/bin/python3
|
|
|
|
import sys
|
|
import re
|
|
|
|
def find_bags(bags, target):
|
|
seen = []
|
|
queue = []
|
|
ret = {}
|
|
queue.append(target)
|
|
seen.append(target)
|
|
|
|
while len(queue) > 0:
|
|
current = queue.pop()
|
|
if current in bags:
|
|
items = bags[current]
|
|
for item in items:
|
|
if item not in seen:
|
|
count = int(items[item])
|
|
ret[item] = count
|
|
queue.append(item)
|
|
seen.append(current)
|
|
return ret
|
|
|
|
|
|
def find_bags2(bags, target):
|
|
count = 1
|
|
|
|
if target not in bags:
|
|
return 1
|
|
|
|
for item in bags[target]:
|
|
v = find_bags2(bags, item)
|
|
count = count + (v * int(bags[target][item]))
|
|
|
|
return count
|
|
|
|
|
|
bags = {}
|
|
bags2 = {}
|
|
for line in sys.stdin:
|
|
line = line.replace(' bags','')
|
|
line = line.replace(' bag','')
|
|
line = line.replace('.','')
|
|
cont = line.rstrip().split(' contain ')
|
|
outer = cont[0]
|
|
inner = cont[1].split(', ')
|
|
for bag in inner:
|
|
m = re.match(r'^(\d+) (.*)$', bag)
|
|
count = 0
|
|
if m is not None:
|
|
bag = m.group(2)
|
|
count = m.group(1)
|
|
if bag in bags:
|
|
bags[bag][outer] = count
|
|
else:
|
|
t = {}
|
|
t[outer] = count
|
|
bags[bag] = t
|
|
|
|
if bag == "no other":
|
|
continue
|
|
if outer in bags2:
|
|
bags2[outer][bag] = count
|
|
else:
|
|
t = {}
|
|
t[bag] = count
|
|
bags2[outer] = t
|
|
|
|
valid1 = find_bags(bags, 'shiny gold')
|
|
print(1, len(valid1))
|
|
|
|
print(2, find_bags2(bags2, 'shiny gold')-1)
|