52 lines
1.4 KiB
Python
52 lines
1.4 KiB
Python
from collections import deque
|
|
from fileio import open
|
|
let lines, descriptions, count
|
|
|
|
with open('test/day7.in') as f:
|
|
lines = [l.strip() for l in f.readlines()]
|
|
|
|
descriptions = {}
|
|
|
|
for line in lines:
|
|
let mine, contains = line.split(" bags contain ", 1)
|
|
if contains[:8] == "no other":
|
|
descriptions[mine] = []
|
|
else:
|
|
let contents = deque()
|
|
for bag in contains.split(", "):
|
|
let cnt, rest = bag.split(' ',1)
|
|
let name = rest.strip().split('bag',1)[0]
|
|
for i in range(int(cnt)):
|
|
contents.append(name.strip())
|
|
descriptions[mine] = contents
|
|
|
|
def reaches(bag, target, seen=set()):
|
|
for n in descriptions[bag]:
|
|
if n == target:
|
|
return True
|
|
if n not in seen:
|
|
seen.add(n)
|
|
if reaches(n, target, seen):
|
|
return True
|
|
return False
|
|
|
|
count = 0
|
|
for bag in descriptions.keys():
|
|
if reaches(bag, 'shiny gold'):
|
|
count += 1
|
|
|
|
print("There are", count, "bags that can contain a shiny gold bag, eventually.")
|
|
|
|
def find_depth(bag):
|
|
if not descriptions[bag]:
|
|
return 0
|
|
let to_scan = descriptions[bag]
|
|
let count = 0
|
|
while to_scan:
|
|
let i = to_scan.popleft()
|
|
count += 1
|
|
to_scan.extend(descriptions[i])
|
|
return count
|
|
|
|
print("A shiny gold bag contains", find_depth('shiny gold'), "bags.")
|