[Day 19] Aplenty // Advent of Code 2023 (Python)

Aplenty (via DALL-E 3)

Advent of Code
The Elves of Gear Island are thankful for your help and send you on your way. They even have a hang glider that someone…adventofcode.com

---

Part One

The Elves of Gear Island are thankful for your help and send you on your way. They even have a hang glider that someone stole from Desert Island; since you’re already going that direction, it would help them a lot if you would use it to get down there and return it to them.

As you reach the bottom of the relentless avalanche of machine parts, you discover that they’re already forming a formidable heap. Don’t worry, though — a group of Elves is already here organizing the parts, and they have a system.

To start, each part is rated in each of four categories:

x: Extremely cool looking

m: Musical (it makes a noise when you hit it)

a: Aerodynamic

s: Shiny

Then, each part is sent through a series of workflows that will ultimately accept or reject the part. Each workflow has a name and contains a list of rules; each rule specifies a condition and where to send the part if the condition is true. The first rule that matches the part being considered is applied immediately, and the part moves on to the destination described by the rule. (The last rule in each workflow has no condition and always applies if reached.)

Consider the workflow ex{x>10:one,m<20:two,a>30:R,A}. This workflow is named ex and contains four rules. If workflow ex were considering a specific part, it would perform the following steps in order:

Rule “x>10:one”: If the part’s x is more than 10, send the part to the workflow named one.

Rule “m<20:two”: Otherwise, if the part’s m is less than 20, send the part to the workflow named two.

Rule “a>30:R”: Otherwise, if the part’s a is more than 30, the part is immediately rejected (R).

Rule “A”: Otherwise, because no other rules matched the part, the part is immediately accepted (A).

If a part is sent to another workflow, it immediately switches to the start of that workflow instead and never returns. If a part is accepted (sent to A) or rejected (sent to R), the part immediately stops any further processing.

The system works, but it’s not keeping up with the torrent of weird metal shapes. The Elves ask if you can help sort a few parts and give you the list of workflows and some part ratings (your puzzle input). For example:

px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}

{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}

The workflows are listed first, followed by a blank line, then the ratings of the parts the Elves would like you to sort. All parts begin in the workflow named in. In this example, the five listed parts go through the following workflows:

{x=787,m=2655,a=1222,s=2876}: in -> qqz -> qs -> lnx -> A

{x=1679,m=44,a=2067,s=496}: in -> px -> rfg -> gd -> R

{x=2036,m=264,a=79,s=2244}: in -> qqz -> hdj -> pv -> A

{x=2461,m=1339,a=466,s=291}: in -> px -> qkq -> crn -> R

{x=2127,m=1623,a=2188,s=1013}: in -> px -> rfg -> A

Ultimately, three parts are accepted. Adding up the x, m, a, and s rating for each of the accepted parts gives 7540 for the part with x=787, 4623 for the part with x=2036, and 6951 for the part with x=2127. Adding all of the ratings for all of the accepted parts gives the sum total of 19114.

Sort through all of the parts you’ve been given; what do you get if you add together all of the rating numbers for all of the parts that ultimately get accepted?

---

They even have a hang glider that someone stole from Desert Island.

Ah, well! 👀

So, seems like now we have a relentless avalanche of machine parts that has formed a giant heap. But some elves are trying to organize them based of a system that rates each part in following 4 categories:

• x: Extremely cool looking
• m: Musical (it makes a noise when you hit it)
• a: Aerodynamic
• s: Shiny

Not very scientific, is it?!

Then, each part is sent through a series of workflows that will ultimately accept or reject the part. Each workflow has a name and contains a list of rules; each rule specifies a condition and where to send the part if the condition is true. The first rule that matches the part being considered is applied immediately, and the part moves on to the destination described by the rule. (The last rule in each workflow has no condition and always applies if reached.)

So, seems like each workflow has a series of qualification checks and as soon as a condition is met, we send the part to subsequent workflow.

We are given an example workflow: ex{x>10:one,m<20:two,a>30:R,A} which is named ex and has 4 rules:

• Rule “x>10:one”: If the part’s x is more than 10, send the part to the workflow named one.
• Rule “m<20:two”: Otherwise, if the part’s m is less than 20, send the part to the workflow named two.
• Rule “a>30:R”: Otherwise, if the part’s a is more than 30, the part is immediately rejected (R).
• Rule “A”: Otherwise, because no other rules matched the part, the part is immediately accepted (A).

If a part is sent to another workflow, it immediately switches to the start of that workflow instead and never returns. If a part is accepted (sent to A) or rejected (sent to R), the part immediately stops any further processing.

Got it! So, we can clearly see that each part seems to be an object with 4 properties and then we have a rule engine which is navigating through a series of workflows to finally reach either: A Accepted or R Rejected.

We then go on to calculate the sum of all rating numbers for all the accepted parts and that’s our answer!

❗️ All parts begin in the workflow named in.

We are given a base case, that looks something like:

Base case walkthrough

So, let’s write some code for our base test case?

Skelton code to get started

So, as per the visualization above, I am structuring my code to first process workflows and parts and then using the accepted_parts_list , calculate the sum .

Let’s play around with our input_str to parse our workflows and part_list in a quick REPL:

I think we can encapsulate part data nicely by creating a class MachinePart like:

Might be overkill, but what YOLO

And our parse_input() looks something like this:

Our workflows are still stored as a list of string rules, as I will be dealing with them during our process() flow, let’s do that! As always, we will start from a spagheti code to just build the logic and then refactor for brownee points:

Debugging is fun!

And our sum function can be as simple as:

Everthing looks good! Let’s run it?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_19/aplenty.py"
✅ sum_of_rating_of_accepted_parts() tests passed
🎉 All tests passed

[Done] exited with code=0 in 0.248 seconds

I think we can do away with the ENUM, just makes the code little bloated, I will move the state into our MachinePart class and simplify some of the nesting as well:

MachinePart

And hence, our process() gets broken into 2 classes, where we can take out common condition logic into evaluate_condition() :

process -> evaluate_condition for each valid condition!

I still see a lot of nesting we can simplify and we can save an iteration we are doing in sum_of_rating_of_accepted_parts, by directly doing that in process() but will leave that for part 2!

Let’s load up our puzzle input and run this one?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_19/aplenty.py"
❗️ Sum of ratings of accepted parts: XXXXXX

[Done] exited with code=0 in 0.207 seconds

And we have an answer in just 0.207 seconds ! Pretty good, considering we had 593 workflows and 200 parts in our puzzle input.

Let’s see if this is the correct answer? And yes it is! 🙌

⭐️

Here’s our code till now:

# Day 19 - Aplenty

class MachinePart:
    ACCEPTED = "A"
    REJECTED = "R"

    VALID_STATES = [ACCEPTED, REJECTED]

    def __init__(self, x: int, m: int, a: int, s: int):
        self.ratings = {"x": x, "m": m, "a": a, "s": s}
        self.state = None

    def set_state(self, state: str) -> None:
        if state in [self.ACCEPTED, self.REJECTED]:
            self.state = state
        else:
            raise ValueError(f"Invalid state: {state}")

    def is_unprocessed(self) -> bool:
        return self.state is None

    def __str__(self) -> str:
        ratings_str = ",".join(
            [f"{key}={value}" for key, value in self.ratings.items()]
        )
        return ratings_str

def evaluate_condition(part, condition):
    if "<" in condition:
        variable, value = condition.split("<")
        return part.ratings[variable] < int(value)
    elif ">" in condition:
        variable, value = condition.split(">")
        return part.ratings[variable] > int(value)
    else:
        raise ValueError(f"Invalid condition: {condition}")

def process(workflows: dict, parts_list: list) -> list:
    INITIAL_WORKFLOW_ID = "in"
    CONDITION_SEPARATOR = ":"

    for i, part in enumerate(parts_list):
        # print(f"{i+1}/{len(parts_list)}\n Processing part {part}\n\n")
        worflow_id = INITIAL_WORKFLOW_ID
        while part.is_unprocessed():
            for rule in workflows[worflow_id]:
                if CONDITION_SEPARATOR in rule:
                    condition, worflow_id = rule.split(CONDITION_SEPARATOR)
                    if evaluate_condition(part, condition):
                        if worflow_id in MachinePart.VALID_STATES:
                            part.set_state(worflow_id)
                        break # Break out of for loop and move to new workflow
                elif rule in MachinePart.VALID_STATES:
                    part.set_state(rule)
                else:
                    worflow_id = rule
    return parts_list

def sum_of_rating_of_accepted_parts(parts_list: list) -> int:
    sum = 0
    for part in parts_list:
        if part.state == MachinePart.ACCEPTED:
            sum += (
                part.ratings["x"]
                + part.ratings["m"]
                + part.ratings["a"]
                + part.ratings["s"]
            )
    return sum

def parse_input(input_str: str) -> tuple:
    workflow_str, parts_str = input_str.split("\n\n")
    workflows = {}
    for workflow in workflow_str.split("\n"):
        workflow_name, workflow_rules = workflow.split("{")  # Split on first '{'
        workflow_rules = workflow_rules[:-1]  # Remove trailing '}'
        workflows[workflow_name] = workflow_rules.split(",")

    parts_list = []
    for part in parts_str.split("\n"):
        x, m, a, s = part[1:-1].split(",")
        x = int(x.split("=")[1])
        m = int(m.split("=")[1])
        a = int(a.split("=")[1])
        s = int(s.split("=")[1])
        parts_list.append(MachinePart(x, m, a, s))

    return workflows, parts_list

def part_one():
    with open("day_19/input.txt") as f:
        input_str = f.read()
    workflows, parts_list = parse_input(input_str)
    parts_list = process(workflows, parts_list)
    sum = sum_of_rating_of_accepted_parts(parts_list)
    print(f"❗️ Sum of ratings of accepted parts: {sum}")

def test_sum_of_rating_of_accepted_parts():
    input_str = """px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}

{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}"""

    workflows, parts_list = parse_input(input_str)
    parts_list = process(workflows, parts_list)
    sum = sum_of_rating_of_accepted_parts(parts_list)
    assert sum == 19114, f"Expected 19114, got {sum}"
    print("✅ sum_of_rating_of_accepted_parts() tests passed")

if __name__ == "__main__":
    test_sum_of_rating_of_accepted_parts()
    print("🎉 All tests passed")

    part_one()

---

Part Two

Even with your help, the sorting process still isn’t fast enough.

One of the Elves comes up with a new plan: rather than sort parts individually through all of these workflows, maybe you can figure out in advance which combinations of ratings will be accepted or rejected.

Each of the four ratings (x, m, a, s) can have an integer value ranging from a minimum of 1 to a maximum of 4000. Of all possible distinct combinations of ratings, your job is to figure out which ones will be accepted.

In the above example, there are 167409079868000 distinct combinations of ratings that will be accepted.

Consider only your list of workflows; the list of part ratings that the Elves wanted you to sort is no longer relevant. How many distinct combinations of ratings will be accepted by the Elves’ workflows?

---

Even with your help, the sorting process still isn’t fast enough.

Well, excuse me?!

So, one of the Elves comes up with a new plan: rather than sort parts individually through all of these workflows, maybe we can figure out in advance which combinations of ratings will be accepted or rejected. 🤔

Interesting! We are given that:

• Each of the four ratings (x, m, a, s) can have an integer value ranging from a minimum of 1 to a maximum of 4000.
• Of all possible distinct combinations of ratings, your job is to figure out which ones will be accepted.

Well, now we can ignore parts in our puzzle input and we have to share that how many distinct combinations of ratings will be accepted by the Elves’ workflows?

💭 Now, looking at the question, it may seem pretty easy as we are scoping our rating values between 1 to 4000, but let me blow up your brain:

For each of the four ratings (X, M, A, S), which can each take on values from 1 to 4000, there are a total of 256 trillion (256,000,000,000,000) possible combinations! 🤯

❗️ So, brute force approach is out of question here!

Now, we need to basically find the upper bound and lower bound of values for each X, M, A, S that will lead us to A — Accepted state for our rules!

So, let’s visualize our base test case workflow rules? We can basically simplify this:

into this:

where, starting from in we have all these conditional paths to reach A or R . Let’s take the top left A in above visualization, now to reach there, we need to have a Part with value for each rating between the following inclusive ranges:

x: (1, 4000), m: (1, 2090), a: (2006, 4000), s: (1, 1350)

so that we can go from in[0] --> px[0] --> px[1] --> A

Now similarly, to reach the mid top A in above visualiation, the following ranges will fulfill the criteria:

x: (1, 1415), m: (1, 4000), a: (1, 2005), s: (1, 1350)

⬆️ This is important, if you didn’t understand how we reached these values, please read again!

Once we can calculate these ranges for each entry of A in our rules, we just need to do a sum of all possible combinations per range criteria!

First things first, let’s create a new function find_acceptable_range() which will iterate through our workflow and its’ rules to find a list of ranges as we disucssed above:

I can’t help but think that this is a backtracking problem, where we will iterate through the workflows dict of rules and will push each path to a stack and then we encounter A we save that state of ranges and if we encounter R we just ignore that and backtrack else we keep going!

This is just a hunch, but let’s explore that!

Ah! Let’s see how to fix this!

Ok!

So, we are able to get all the valid ranges that will get us to A :

But the problem is, they all don’t seem distinct and our test case only has 9 A nodes but our range_list has 14 combinations! 🤔

It seems like we have a lot of overlapping ranges!

.

.

back to drawing board

.

.

After couple of hours of debugging! I was able to simplify our code a lot!

💭 The key caveat was that everytime we evaluate a condition < > for a range, for example:

range = {"x": (1, 4000), "m": (1, 4000), "a": (1, 4000), "s": (1, 4000)}

and given condition is a<2006 , our range will split into 2 parts:

true_range = {.........., "a": (1, 2005),.......}

false_range = {.........., "a": (2006, 4000),.......}

wheretrue_range will go on to evaluate the next_workflow_id and the false_range will move on to the next rule in list!

Here’s what we had to change in code:

Introduced a new class MachinePartRanges to store range for each rating! I also had to implement a copy() function for deep copy of our object while spliting into true_range and false_range

Here’s our modified evaluate_condition method:

And here’s our creme la de creme methodnum_of_combinations_possible that calculate the distinct combinations of ratings will be accepted by the workflows!

“This function 👇 broke my brain!

I spent over 2 hours debugging this as it started with a full on spagetti code with a lot of nesting! Only when I was able to clean it with early returns in my code was when I was able to make some progress!”

Moral of story: Always write clean code so you can debug it later!

We use the same DFS with Backtracking approach to find all accepted_ranges

Let’s test our code for the base test case?

We are still using the same input_str as part_one, but we will discard parts info while parse_input()

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_19/aplenty_2.py"
✅ sum_of_rating_of_accepted_parts() tests passed

[Done] exited with code=0 in 0.317 seconds

Perfect! Let’s load up our puzzle input and check if we can get the answer?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_19/aplenty_2.py"
❗️❗️ Number of combinations possible: XXXXXXXXXXXXXXX

[Done] exited with code=0 in 0.345 seconds

Let’s see if this is the correct answer? 🤞

🌟

Here’s our code for Part 2, I am very proud of this code! 🥲

# Day 19 - Aplenty
# Part Two

class MachinePartRanges:
    ACCEPTED = "A"
    REJECTED = "R"

    def __init__(self):
        self.rating_ranges = {
            "x": (1, 4000),
            "m": (1, 4000),
            "a": (1, 4000),
            "s": (1, 4000),
        }
        self.state = None

    def __repr__(self) -> str:
        return str(self.rating_ranges)

    def copy(self):
        # deep copy
        new_mpr = MachinePartRanges()
        new_mpr.rating_ranges = self.rating_ranges.copy()
        return new_mpr

def evaluate_condition(ranges: MachinePartRanges, condition: str) -> (MachinePartRanges, MachinePartRanges):
    true_range, false_range = ranges.copy(), ranges.copy()

    variable, value = condition.split("<" if "<" in condition else ">")

    if "<" in condition:
        true_range.rating_ranges[variable] = (true_range.rating_ranges[variable][0], int(value) - 1)
        false_range.rating_ranges[variable] = (int(value), false_range.rating_ranges[variable][1])
    elif ">" in condition:
        true_range.rating_ranges[variable] = (int(value) + 1, true_range.rating_ranges[variable][1])
        false_range.rating_ranges[variable] = (false_range.rating_ranges[variable][0], int(value))

    return true_range, false_range

def num_of_combinations_possible(workflows) -> int:
    INITIAL_WORKFLOW_ID = "in"
    accepted_ranges_list = []

    stack = [(MachinePartRanges(), INITIAL_WORKFLOW_ID)]

    while stack:
        ranges, workflow_id = stack.pop()

        if workflow_id == MachinePartRanges.ACCEPTED: 
            accepted_ranges_list.append(ranges)
            continue

        if workflow_id == MachinePartRanges.REJECTED:
            continue

        for rule in workflows[workflow_id]:
            if rule == MachinePartRanges.ACCEPTED:
                accepted_ranges_list.append(ranges)
                break

            if rule == MachinePartRanges.REJECTED:
                break

            if ":" not in rule:
                workflow_id = rule
                stack.append((ranges, workflow_id))
                continue
            
            # rule must be a condition
            condition, new_worflow_id = rule.split(":")
            true_range, false_range = evaluate_condition(ranges, condition) 
            stack.append((true_range, new_worflow_id)) # Add true range to stack to explore new_workflow_id
            ranges = false_range # Update ranges for next iteration in rules loop

    # now we have a list of accepted ranges, we can calculate the number of combinations possible
    num_of_combinations = 0
    for ranges in accepted_ranges_list:
        num_of_combinations += (
            (ranges.rating_ranges["x"][1] - ranges.rating_ranges["x"][0] + 1)
            * (ranges.rating_ranges["m"][1] - ranges.rating_ranges["m"][0] + 1)
            * (ranges.rating_ranges["a"][1] - ranges.rating_ranges["a"][0] + 1)
            * (ranges.rating_ranges["s"][1] - ranges.rating_ranges["s"][0] + 1)
        )

    return num_of_combinations

def parse_input(input_str: str) -> tuple:
    workflow_str, _ = input_str.split("\n\n")
    workflows = {}
    for workflow in workflow_str.split("\n"):
        workflow_name, workflow_rules = workflow.split("{")  # Split on first '{'
        workflow_rules = workflow_rules[:-1]  # Remove trailing '}'
        workflows[workflow_name] = workflow_rules.split(",")

    return workflows

def part_two():
    with open("day_19/input.txt") as f:
        input_str = f.read()
    workflows = parse_input(input_str)
    num = num_of_combinations_possible(workflows)
    print(f"❗️❗️ Number of combinations possible: {num}")

def test_num_of_combinations_possible():
    input_str = """px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}

{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}"""

    workflows = parse_input(input_str)
    num = num_of_combinations_possible(workflows)
    assert num == 167409079868000, f"Expected 167409079868000, got {num}"
    print("✅ sum_of_rating_of_accepted_parts() tests passed")

if __name__ == "__main__":
    test_num_of_combinations_possible()
    part_two()

---

I am keeping Part 1 and Part 2 seperate in our code base as both parts are actually pretty different in terms of processing, might come back to merge them later. Too tired for now!

Feel free to raise a PR?!

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com