Advent of Code 2015 - Day 16

Day 16: Aunt Sue

Useful Links

‹›

Concepts and Packages Demonstrated

dataclass list comprehension

Problem Intro
Part 1
Part 2
Results

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:

Sue List

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:
        data = f.read().splitlines()

    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

‹›

Learning Python with Advent of Code Walkthroughs