Advent of Code

Advent of Code 2020 – Day 7

By Ramen Junkie #Advent of Code 2020, #Coding, #Python

The challenge for Day 7 is the first that really tripped me up. The basic concept wasn’t too hard, but I had a lot of stabs in the dark trying to massage the code into working properly. Part of the problem in my case is that it really needed to use recursion, which I really hate. When you have a small error, and it’s recursive, it just snowballs into a huge error.

Part 1 wasn’t too hard, you have a bunch of different colored bags, and they contain some number of other colored bags. Here is the sample data set:

light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.

The task was to count how many bags will eventually contains a shiny gold bag. The hardest part was processing the input, because it’s all text based, so there is some string searching and manipulating to check for bag types.

My other minor issue was, I had a brain fart, and started working off the sample data set instead of the actual data set, which is considerably larger. I had written up 4 or 5 if style statements, because “there’s like ten bags here, easy”, before realizing my mistake and checking the actual data set, which has, many many more bags. Too many to build simple if based counting statements for.

Anyway, my code for part 1:


with open('day7data.txt') as f:
    lines = [line.rstrip() for line in f]

bags=0
check=["shiny gold"]
checked=[]

while(check):
  #print check[0]
  for line in lines:
    endloc = line.find("contain")
    if check[0] in line[endloc:]:
      bags+=1
      #print endloc
      container=line[:endloc-1]
      if container[-1:] == "s":
        container = container[:-1]


      if container not in checked:
        check.append(container)
        checked.append(container)
      #print line[endloc:]
      #print check[0]
      #print line[:endloc-1]
  #print bags
  check.pop(0)
  #print check

print len(checked)

#print checked
print bags

Fairy simple, start with anything that contains a “Shiny Gold Bag”, then check for anything containing those bags, and check for anything containing those bags, until there is nothing left to check.

Part 2 was trickier, because it went the other direction. It’s also where the recursion came into play. For those who don’t know what recursion is, it’s essentially when a function, references itself, within a function.

Say you want to check bags for bags and count them, so you have a function that says “open a bag, and count how many are inside, then open any bags inside and count those bags, then open any bags inside and count those bags, then open any bags inside and count those bags….

And so on. Until you open a bag and it contains no bags, then you just return 1, for the empty bag itself. Then the recursion will sort of rubber-band back on itself in this case, and multiply the bag counts in each bag by how many of each bag there existed.

Anyway, here is the code:


def sum(arr):
    result = sum(arr)
    return result

def bagcheck(quantity, current):
  total=int(quantity)
  #print checked  
  for line in lines:
    endloc = line.find("contain")
    if current in line[:endloc]:
      content = line[endloc+7:-1].split(',')
      #print content
      for i in content:
        if i != ' no other bags':
          #print total
          if i[-1] == "s":
            i=i[:-1]
          #print i[1]
          #print i[3:]
          if i not in checked:
            check.append(i)
            checked.append(i)
          #total += int(i[1])
          total += int(quantity) * bagcheck(i[1], i[3:])
        else: total=quantity
       
  print current+" has inside "+str(total)+" and there are "+quantity+" of them, total of "+str(total)
  return int(total)

with open('day7data.txt') as f:
    lines = [line.rstrip() for line in f]

bags=0
check=[" 1 shiny gold"]
checked=[]
total=0

if check[0] != ' no other bags':
  bags=(bagcheck(check[0][1],check[0][3:]))
    #print bags

print bags-1

It worked out, I am not entirely sure how, because I spent so many times moving and adjusting +1s and multiplying this by that, or that by that other thing, until it worked.

Both parts gave my some initial trip ups because of bags versus bag, which is why there are places that check for and remove the s on the end of a bag type. Because when you check for “bags” and there is only one “bag”, you won’t see the singular bag. But if you search for “bag”, you will find “bags”.