day 7

this was the hardest one so far but it was one of the most fun! the main issue is trying to implement a directed tree - i ended up doing this through dicts (technically defaultdicts, so that i could set it to return the empty list [] if the colour wasn't found), where for example the rule "light chartreuse bags contain 1 mirrored yellow bag, 2 vibrant violet bags." would become

'light chartreuse': [(1, 'mirrored yellow'), (2, 'vibrant violet')]

for the first part, the number of bags was irrelevant, so i wrote a small function contains_cols to get just the colours, e.g.

contains_cols('light chartreuse') = ['mirrored yellow', 'vibrant violet']

from here, the next stage was trying to find a bag that contains a shiny gold bag at some level - so you get any descendants, not just children. i implemented this by iterating over the list of colours that has not been checked yet, and splitting these into has_shiny_gold and no_shiny_gold

i went through the list of all of the colours, and while this list was non-empty, i removed the first element as outer_col and checked if this one could eventually contain a shiny gold by going into the colours inside it, in the list cols_inside.

while cols_inside is non-empty, it pops off the first element as inner_col and checks (in the following order) whether each inner_col is:

1. shiny gold, in which case we add outer_col to has_shiny_gold (break)
2. a colour that we already know does NOT contain shiny gold (it is in no_shiny_gold), in which case we go to the next inner_col (continue)
3. a colour that we already know contains shiny gold (it is in has_shiny_gold), in which case we add outer_col to has_shiny_gold (break)

and then it adds all of the colours inside inner_col to cols_inside.

this inner while statement ends when shiny gold, or a colour containing shiny gold, has been found, or we have checked every bag inside and there is no shiny gold, in which case we add the colour to no_shiny_gold (this is my first ever while-else loop, i'm proud of me)

the outer while statement ends when we have gone through every rule in the list. the final step is just to print the length of the list has_shiny_gold.

7a.py:

# many rules (your puzzle input) are being enforced about bags and their contents;
# bags must be color-coded and must contain specific quantities of other color-coded bags
# You have a shiny gold bag. If you wanted to carry it in at least one other bag,
# how many different bag colors would be valid for the outermost bag?
# (In other words: how many colors can, eventually, contain at least one shiny gold bag?)
# grab defaultdict so we can have absent keys as empty lists []
from collections import defaultdict
# input
with open('7.txt', 'r') as file:
    input = file.read()
# turn the input into a list, one element is one rule
input_list = list(input.split('\n'))
# make an empty defaultdict to contain e.g. 'light olive' : [(2, 'drab blue'), (1, 'plaid purple')]
# futureproofing bc part 2 will probably involve the numbers
# if a key is missing, the list of bags it contains is []
rules = defaultdict(list)
# need to split up properly
for rule0 in input_list:
    # rule0 = 'light olive bags contain 2 drab blue bags, 1 plaid purple bag.'
    rule1 = rule0[:-1].split(' bags contain ')
    # ('light olive', '2 drab blue bags, 1 plaid purple bag')
    outer_col = rule1[0]
    # 'light olive'
    rule2 = rule1[1].split(', ')
    # ('2 drab blue bags', '1 plaid purple bag')
    numcol_list = []
    for numcol in rule2:
        if numcol == 'no other bags':
            break # nothing to add to numcol_list
        rule3 = numcol.split(' ')
        # ('2', 'drab', 'blue', 'bags')
        rule4 = (int(rule3[0]), rule3[1] + ' ' + rule3[2])
        # (2, 'drab blue')
        numcol_list.append(rule4)
        # [(2, 'drab blue')]
    # rule3 = [(2, 'drab blue'), (1, 'plaid purple')]
    rules[outer_col] = numcol_list
    # { ... 'light olive': [(2, 'drab blue'), (1, 'plaid purple')], ...}
#    #    #    #    #    #    #    #
# gets list of all colours of bags in the dict
# ['light chartreuse', 'dotted silver', ...]
cols = list(rules)
# will contain list of colours containing shiny gold
has_shiny_gold = []
# will contain list of colours not containing shiny gold
no_shiny_gold = []
# gets colours the next level down
# 'light olive' -> ['drab blue', 'plaid purple']
def contains_cols(col: str):
    numcols = rules[col]
    cols = []
    for numcol in numcols:
        cols.append(numcol[1])
    return cols
# we will gradually remove colours
while len(cols) > 0:
    outer_col = cols.pop(0) # pop off the first col in the list
    cols_inside = contains_cols(outer_col) # get the cols one level down
    while len(cols_inside) > 0: # while we still have cols inside
        if 'shiny gold' in cols_inside: # if we have shiny gold inside
            has_shiny_gold.append(outer_col) # add to output list
            break
        inner_col = cols_inside.pop(0) # pop first element from list
        if inner_col in no_shiny_gold: # if we've already confirmed it has no shiny gold
            continue # go to next element in list
        elif inner_col in has_shiny_gold: # if we've already confirmed it has a shiny gold
            has_shiny_gold.append(outer_col)  # add to output list
            break # don't need to continue the while
        cols_inside = cols_inside + contains_cols(inner_col) # get the cols inside that
    else:
        # no break statement hit, cols_inside = 0
        # => does not contain shiny gold
        no_shiny_gold.append(outer_col)
print(len(has_shiny_gold))

for the second part, we need the number of bags inside a shiny gold bag. 7b.py starts off with some of the same code as 7a.py to create the dict (the segment before the line that's just #s), so i won't paste this again

i wrote a recursive function num_bags_inside for this part - if the bag contains no other bags, it returns 0; else we go through the (num, col) pairs for each bag and add the number of bags of that colour plus the number of bags it contains to the counter. this is assuming that none of the rules would cause infinite recursion (e.g. a yellow bag must contain a red bag, a red bag must contain a yellow bag) so if you keep opening nested bags, you'll always hit an empty one. just a note, i've counted the current bag itself

# get the number of bags inside your current bag
# recursion all the way down
def num_bags_inside(col: str):
    bags_inside = rules[col]
    num = 0
    if bags_inside == []: # no bags inside
        return num
    else: # bags inside
        for numcol in bags_inside:
            # numcol = (2, 'mirrored blue')
            num += numcol[0] + numcol[0] * num_bags_inside(numcol[1])
    return num
# shiny gold bags contain 2 mirrored blue bags, 1 muted brown bag, 3 dim purple bags.
# numcols = [(2, 'mirrored blue'), (1, 'muted brown'), (3, 'dim purple')]
print(num_bags_inside('shiny gold'))

for example, the rule for shiny gold bags in my input was "shiny gold bags contain 2 mirrored blue bags, 1 muted brown bag, 3 dim purple bags". if you have one shiny gold bag, then your total number of bags - num_bags_inside('shiny gold') - can be expanded as follows (which will then expand further as you check how many bags are inside each of these):

1 + 2*num_bags_inside('mirrored blue') + 1*num_bags_inside('muted brown') + 3*num_bags_inside('dim purple')