# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

# Advent of Code 2015 - Day 16

## Problem Intro

Apparently, we have received a present from one of our 500 aunts named “Sue”. We need to find out which one to thank.

The present she sent us as a MFCSAM: My First Crime Scene Analysis Machine. We use it to detect a bunch of attributes abotut the Sue we need to write to:

``````children: 3
cats: 7
samoyeds: 2
pomeranians: 3
akitas: 0
vizslas: 0
goldfish: 5
trees: 3
cars: 2
perfumes: 1
``````

You’ve created a list of attributes that you can remember about each Sue. If properties are missing from any given Sue, it means we simply can’t remember that detail. The data looks something like this…

``````Sue 1: cars: 9, akitas: 3, goldfish: 0
Sue 2: akitas: 9, children: 3, samoyeds: 9
Sue 3: trees: 6, cars: 6, children: 4
Sue 4: trees: 4, vizslas: 4, goldfish: 9
Sue 5: akitas: 9, vizslas: 7, cars: 5
Sue 6: vizslas: 6, goldfish: 6, akitas: 3
...

So, we know Sue 1 has 9 cars, 3 akitas, and 0 goldfish.  She might also have any number of trees; we just don't remember.
``````

## Part 1

What is the number of the Sue that got you the gift?

Here’s my strategy:

• Iterate through each key:value pair from the known attributes from the MFCSAM.
• For each:
• If the key is present, and the value matches what the MFCSAM told us, then this Sue is a candidate.
• If the key is not present, then this Sue could also be a candidate.

And I hope that by the time I’ve processed the full list of MFCSAM attributes, there will only be one Sue left.

First, let’s create a `dictionary` to contain all the attributes that we know about, from the MFCSAM:

``````known_attribs = {
'children': 3,
'cats': 7,
'samoyeds': 2,
'pomeranians': 3,
'akitas': 0,
'vizslas': 0,
'goldfish': 5,
'trees': 3,
'cars': 2,
'perfumes': 1
}
``````

Next, let’s create a dataclass so that we store all our instances of `Sue`:

``````@dataclass
class Sue:
""" A Sue has a unique number and a set of properties that look like...
{'pomeranians': 3, 'perfumes': 1, 'vizslas': 0}
"""
num: int
properties: dict
``````

Now we can process the input data:

``````def process_input(data) -> list[Sue]:
# Input looks like:
# Sue 1: cars: 9, akitas: 3, goldfish: 0
# Return list of Sue objects.
sue_list = []

for line in data:
sue_num, attribs = line[4:].split(":", 1)
properties = [x.strip().split(":") for x in attribs.split(",")]
props_dict = {prop[0]: int(prop[1]) for prop in properties}
sue_list.append(Sue(int(sue_num), props_dict))

return sue_list
``````

How does this work?

• We create an empty `list` to store all our `Sue` objects.
• We process each “Sue” line. Imagine we have this line:
`Sue 1: cars: 9, akitas: 3, goldfish: 0`
• We split the line at the first `:`, but ignoring the first four characters, i.e. ignoring `Sue `. This returns two values:
• The number of the Sue.
• All the attributes, in a format that looks like this:
` cars: 9, akitas: 3, goldfish: 0`
• We then have a list comprehension whcih splits this line at the commas, and for each `property: count` returned, further splits at the `:`. So, with our example, we end up with this list:
`[['cars', ' 9'], ['akitas', ' 3'], ['goldfish', ' 0']]`
• We then turn this list into a `dictionary`, using a dictionary comprehension. So now we have this:
`{'cars': 9, 'akitas': 3, 'goldfish': 0}`
• Now we can create a `Sue` object from the Sue number, and this `dict` of attributes.
• And add the `Sue` object to our `list`.

If I look at the resulting Sue `list` in my IDE debugger, it looks like this:

Now we’re ready to implement the strategy described above:

``````    # we need to find any Sue where k:v is an exact match
# but also consider any Sue where the k is not present as we don't know the v
for known_attrib, known_attrib_value in known_attribs.items():
sues_matching_attrib = [sue for sue in sue_candidates
if known_attrib in sue.properties
and known_attrib_value == sue.properties[known_attrib]]
sues_missing_attrib = [sue for sue in sue_candidates if known_attrib not in sue.properties]

sue_candidates = sues_matching_attrib + sues_missing_attrib

print(f"Part 1: Aunt Sue candidates matching MFCSAM attributes: {sue_candidates[0].num}")
``````

How does it work?

• We iterate through our list of known properties and values from the MFCSAM.
• We use list comprehension to return a `list` of all the `Sue` objects, where the key and value match what the MFCSAM told us.
• We use list comprehension to return a `list` of all the `Sue` objects, where the key is not specified our the `Sue` objects.
• We add these two lists together, to get our overall `list` of remaining candidates.
• With each iteration, the candidate list gets shorter and shorter.

Eventually, there’s only one left.

## Part 2

We’re told that some of the readings from the MFCSAM are not accurate. Specifically:

• `cats` and `trees` values indicate that there are at more that many.
• `pomeranians` and `goldfish` values indicate that there are fewer than that many.

So we just need to modify our logic accordingly:

``````    for known_attrib, known_attrib_value in known_attribs.items():
sues_missing_attrib = [sue for sue in sue_candidates if known_attrib not in sue.properties]
sues_matching_attrib = []

if known_attrib in ['cats', 'trees']:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value < sue.properties[known_attrib]]
elif known_attrib in ['pomeranians', 'goldfish']:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value > sue.properties[known_attrib]]
else:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value == sue.properties[known_attrib]]

sue_candidates = sues_matching_attrib + sues_missing_attrib

print(f"Part 2: Aunt Sue candidates matching MFCSAM attributes: {sue_candidates[0].num}")
``````

## Results

Here is the final code:

``````from dataclasses import dataclass
import os
import time

SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"

known_attribs = {
'children': 3,
'cats': 7,
'samoyeds': 2,
'pomeranians': 3,
'akitas': 0,
'vizslas': 0,
'goldfish': 5,
'trees': 3,
'cars': 2,
'perfumes': 1
}

@dataclass
class Sue:
""" A Sue has a unique number and a set of properties that look like...
{'pomeranians': 3, 'perfumes': 1, 'vizslas': 0}
"""
num: int
properties: dict

def main():
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:

sue_list = process_input(data)

# Part 1
sue_candidates = sue_list.copy()

# we need to find any Sue where k:v is an exact match
# but also consider any Sue where the k is not present as we don't know the v
for known_attrib, known_attrib_value in known_attribs.items():
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value == sue.properties[known_attrib]]
sues_missing_attrib = [sue for sue in sue_candidates if known_attrib not in sue.properties]

sue_candidates = sues_matching_attrib + sues_missing_attrib

print(f"Part 1: Aunt Sue candidates matching MFCSAM attributes: {sue_candidates[0].num}")

# Part 2
sue_candidates = sue_list.copy()
for known_attrib, known_attrib_value in known_attribs.items():
sues_missing_attrib = [sue for sue in sue_candidates if known_attrib not in sue.properties]
sues_matching_attrib = []

if known_attrib in ['cats', 'trees']:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value < sue.properties[known_attrib]]
elif known_attrib in ['pomeranians', 'goldfish']:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value > sue.properties[known_attrib]]
else:
sues_matching_attrib = [sue for sue in sue_candidates if known_attrib in sue.properties
and known_attrib_value == sue.properties[known_attrib]]

sue_candidates = sues_matching_attrib + sues_missing_attrib

print(f"Part 2: Aunt Sue candidates matching MFCSAM attributes: {sue_candidates[0].num}")

def process_input(data) -> list[Sue]:
# Input looks like:
# Sue 1: cars: 9, akitas: 3, goldfish: 0
# Return list of Sue objects.
sue_list = []

for line in data:
sue_num, attribs = line[4:].split(":", 1)
properties = [x.strip().split(":") for x in attribs.split(",")]
props_dict = {prop[0]: int(prop[1]) for prop in properties}
sue_list.append(Sue(int(sue_num), props_dict))

return sue_list

if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
``````

The output looks like this:

``````Part 1: Aunt Sue candidates matching MFCSAM attributes: 373
Part 2: Aunt Sue candidates matching MFCSAM attributes: 260
Execution time: 0.0025 seconds
``````