Advent of Code - 2023
This is a solution to Day 19 of Advent of Code 2023.
Day 19: Aplenty
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 lookingm
: Musical (it makes a noise when you hit it)a
: Aerodynamics
: ShinyThen, 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 -> AUltimately, 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?
Read input
Today's input required quite a few steps to parse but those steps were rather straight-forward to me at least. In the first section, I parse the workflows by separating rules that have a condition and ones that don't (and create a custom condition of *
for them. Having uniform structure for all rules makes the logic itself bit simpler.
For ratings, I remove the curly braces and split to pairs and store them in a list of dictionaries.
from utils import read_multisection_input
import re
def workflows(section):
rules = {}
for line in section.split('\n'):
key, rest = line.split('{')
rest = rest.split('}')[0].split(',')
tests = []
for rule in rest:
if ':' in rule:
condition, target = rule.split(':')
attribute, operator, value = re.findall(r'(x|m|a|s)(<|>)(\d+)', condition)[0]
condition = (attribute, operator, int(value))
else:
condition = '*'
target = rule
tests.append((condition, target))
rules[key] = tests
return rules
def ratings(section):
ratings_output = []
for line in section.split('\n'):
line = line.replace('{', '').replace('}', '')
ratings = line.split(',')
r = {}
for rating in ratings:
key, value = rating.split('=')
value = int(value)
r[key] = value
ratings_output.append(r.copy())
return ratings_output
workflows, ratings = read_multisection_input(19, [workflows, ratings])
To sort the matchines, I run each one against a loop of conditions, following the path it leads them in the workflows.
Once we hit one where the target is 'A' or 'R', we store them in the final bucket and move to the next machine. This will result with a dictionary of two lists: one for accepted and one for rejected machines.
from collections import defaultdict
FINAL_TARGETS = ('A', 'R')
def sort_machines(workflows, machines):
BEGIN = 'in'
buckets = defaultdict(list)
for machine in machines:
current = workflows[BEGIN]
i = 0
while True:
condition, target = current[i]
match condition:
case '*':
if target in FINAL_TARGETS:
buckets[target].append(machine)
break
else:
current = workflows[target]
i = 0
continue
case (attribute, '<', value):
if machine[attribute] < value:
if target in FINAL_TARGETS:
buckets[target].append(machine)
break
else:
current = workflows[target]
i = 0
continue
case (attribute, '>', value):
if machine[attribute] > value:
if target in FINAL_TARGETS:
buckets[target].append(machine)
break
else:
current = workflows[target]
i = 0
continue
i+=1
return buckets
To calculate the final result, sum all the values of all the machines in the 'A' bucket.
def calculate_accepted_score(buckets):
return sum(sum(machine.values()) for machine in buckets['A'])
buckets = sort_machines(workflows, ratings)
part_1 = calculate_accepted_score(buckets)
print(f'Solution: {part_1}')
assert part_1 == 280909
Solution: 280909
One star today
I'm leaving today to one star for now. I had a busy day today with my local communities (wrapping up one and kickstarting another) and there's hockey on TV so I'm gonna chill for the night. At the time of writing, my total count is 35 stars (missing both stars of day 17 and today's 2nd star out of possible 38).