## DEV Community is a community of 601,801 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks

Harshavardhan
``````import re

visited = {}
with open("Problem-7/Day 7: Handy Haversacks.txt") as file:
for line in file:
# Every line in the input was in the format outerbags contain x innerbags, y innerbags, so on..
# So we can split every line into two parts using the word "contain " as separator.
# As split funtion returns a list, we now have outerbag name as first element and it's dependencies as second element. Unpacked them into two variables as shown below.
outer_bag, innerbags = line.split("contain ")
# Now the outer_bag variable has outerbagname with suffix bags in it. We can just slice the string to remove the suffix
# Similarly, innerbags will now has a string in the format x innerbags, y innerbags, so on..
# We can extract the count and the innerbag name using regex and grouping as shown below
innerbags = re.findall(r"(\d{1,}) ([a-z ]+) bag|bags", innerbags)
# visited list is useful when we are exploring the graph to avoid cycles. Initially we should mark every bag as not visited
visited[outer_bag[:-6]] = False
# Adding edges from outer bag to each inner bag
for count, bag in innerbags:
if count and bag:
# Now we have our adjacency list ready for our directed graph

# dfs of a graph
if not visited[edge]:
visited[edge] = True
count = dfs(adj, visited, edge, count + 1)
return count

# reverse the graph
for key, count in inner.items():
else:
# Now as the graph is reversed, we can find the vertices that previously had a directed edge towards the shiny gold bag now in new adjacency list at shiny gold vertex.
# Simply exploring and counting the number of vertices explored from shiny gold bag vertex will be the result