Advent of Code 2023, Day 19
❄️ Back to Advent of Code 2023 solutions homepage ❄️
# Imports
from aoc23.utils import read_input
from dataclasses import dataclass, field
import operator
from copy import deepcopy
from itertools import combinations
input_19 = read_input(19)
Part 1
In the first part of the day 19 puzzle, we are given a collection of workflows, describing how to sort through a collection of parts. Here is how the puzzle describes these workflows:
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.)
Each part has a value assigned to each of the four attributes x, m, a and s, which are referenced by the rules in the workflows (I will call these xmas attributes). Here is the example set of workflows provided to us:
test_input = [
'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 final steps of the workflows are always either an A (accepted) or R (rejected) - by following taking a part and moving from workflow to workflow, we will always end up in one of these two states.
In order to represent the objects of interest better, let’s define some classes of objects; firstly, a Part object which encapsulates all the properties of a part:
@dataclass(frozen=True)
class Part:
x: int
m: int
a: int
s: int
@classmethod
def create(cls, def_string):
# Create a part from the string provided in the input
attributes = def_string.strip('{}').split(',')
attributes = [a.split('=') for a in attributes]
attribute_dict = {a[0]: int(a[1]) for a in attributes}
return cls(**attribute_dict)
@property
def part_sum(self):
# Part value = sum of xmas attributes
return self.x + self.m + self.a + self.s
# Demonstration
Part.create('{x=787,m=2655,a=1222,s=2876}')
Part(x=787, m=2655, a=1222, s=2876)
Also, define a Condition, which represents each specific condition:
@dataclass
class Condition:
variable: str # e.g. x
relation: str # e.g. <
value: int # e.g. 101
def __repr__(self):
return f'{self.variable}{self.relation}{self.value}'
# Demonstration
Condition('x', '<', 101)
x<101
The first job is the process the puzzle inputs:
def process_workflow_string(workflow_string: str):
# input = string of form:
# 'px{a<2006:qkq,m>2090:A,rfg}'
# name: 'px'
# rules_string: 'a<2006:qkq,m>2090:A,rfg'
name, rules_string = workflow_string[:-1].split('{')
# processed_rules: [[a<2006, 'qkq'], [m>2090, 'A'], ['rfg']]
processed_rules = []
for rule_string in rules_string.split(','):
# rule_string of form:
# 'a<2006:qkq' or 'rfg'
rule = rule_string.split(':')
if len(rule) == 1:
# final rule in workflow
processed_rules.append(rule)
elif len(rule) == 2:
# Convert condition to Condition
condition_string, new_name = rule
# condition_string: 'a<2006'
processed_rules.append([
Condition(condition_string[0],
condition_string[1],
int(condition_string[2:])),
new_name
])
return name, processed_rules
def process_input(input_list: list[str]):
# Split input_list at the empty line
workflows = {}
parts = []
gap_index = input_list.index('')
input_workflows = input_list[:gap_index]
input_parts = input_list[gap_index+1:]
# Process rules and parts separately
workflows = {name: processed_rules
for name, processed_rules
in map(process_workflow_string, input_workflows)}
parts = [Part.create(line) for line in input_parts]
return workflows, parts
The workflows and parts are now represented in a much more useful form, as can be seen here:
test_workflows, test_parts = process_input(test_input)
test_parts
[Part(x=787, m=2655, a=1222, s=2876),
Part(x=1679, m=44, a=2067, s=496),
Part(x=2036, m=264, a=79, s=2244),
Part(x=2461, m=1339, a=466, s=291),
Part(x=2127, m=1623, a=2188, s=1013)]
test_workflows
{'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']]}
It is useful to define a helper function which, when given a part and a wokflow, finds the string which is outputted by following the part down the workflow (either a new workflow name, or the terminal A or R state):
# The operator module helps with this:
OPERATORS = {
'<': operator.lt,
'>': operator.gt
}
def evaluate_workflow(part: Part, workflow: list[list[Condition, str]]) -> str:
# Follow the part along the tree, until an output string is found
# (either a new workflow to move to, or 'A' or 'R')
for rule in workflow:
if len(rule) == 1:
# At end of workflow
return rule[0]
else:
# Check if condition is satisfied
condition, name = rule
operator = OPERATORS[condition.relation]
if operator(getattr(part, condition.variable), condition.value):
return name
# Demonstration
part = Part(x=787, m=2655, a=1222, s=2876)
rule = test_workflows['in']
print(f'''
Part: {part}
Rule: {rule}
Output: {evaluate_workflow(part, rule)}
''')
Part: Part(x=787, m=2655, a=1222, s=2876)
Rule: [[s<1351, 'px'], ['qqz']]
Output: qqz
Each part can repeatedly fed into the workflows (starting with the in workflow), until one of the terminal states is obtained:
def is_part_accepted(part: Part, workflows):
# Start at `in`
key = 'in'
# Continue until termination
while key not in ['A', 'R']:
key = evaluate_workflow(part, workflows[key])
return key == 'A'
For the first part, we are asked only to look at the parts which are accepted, and find the sum of the part attributes - let’s check that the value found for the test case matches the expected sum of part sums:
sum([part.part_sum for part in test_parts if is_part_accepted(part, test_workflows)]) == 19114
print('Success!')
Success!
Repeating this for the full set of parts and workflows:
workflows, parts = process_input(input_19)
sum([part.part_sum for part in parts if is_part_accepted(part, workflows)])
368523
So the answer to part 1 is: 368523.
Part 2
Now, we are told to consider all parts with xmas attributes in the range $[1, 4000]$ - this gives a total of $4000^4=2.56\times10^{14}$ different possible parts, far more than can be considered one at a time using the method from part 1. So we need to be a bit smarter. Instead of considering each part individually, start by considering all of the parts simultaneously, and working out how many are ruled out by each rule that is applied. Specifically, we will track a Region, which records the minimum and maximum xmas attributes considered along a particular path through the workflows. First lets define the region as a Region class:
@dataclass
class Region:
accepted: bool = None
# Each range starts with the full set of possible values
x: tuple[int] = field(default_factory=lambda: [1, 4000])
m: tuple[int] = field(default_factory=lambda: [1, 4000])
a: tuple[int] = field(default_factory=lambda: [1, 4000])
s: tuple[int] = field(default_factory=lambda: [1, 4000])
def set_upper_limit(self, variable: str, value: int):
limits = getattr(self, variable)
if value < limits[1]:
limits[1] = value
# Check that lower limit < upper limit
assert limits[0] <= limits[1]
def set_lower_limit(self, variable: str, value: int):
limits = getattr(self, variable)
if value > limits[0]:
limits[0] = value
# Check that lower limit < upper limit
assert limits[0] <= limits[1]
def count_parts(self):
if len(self.x)*len(self.m)*len(self.a)*len(self.s) == 0:
return 0
else:
return (self.x[1] - self.x[0] + 1) * \
(self.m[1] - self.m[0] + 1) * \
(self.a[1] - self.a[0] + 1) * \
(self.s[1] - self.s[0] + 1)
As well as the ranges for the xmas attributes, the Region class also knows if the region is accepted or rejected via the accepted attribute (which will be None until a terminal state of the workflows is found). It has methods for updating the attribute ranges, when given new upper or lower limits for the attributes (e.g. by the application of a specific workflow condition), and also a method for computing the total number of parts that have attribute values in the allowed ranges.
Now, in order to follow all of the possible paths through the workflows, set up a stack which will track the (workflow_name, region) states that still need to be processed. We follow a depth first search (DFS) approch: at each step, take the most recent state, and compute the change to the region’s xmas attribute ranges when the workflow rules are followed. Specifically, after each rule two states are created - one which considers the path where the condition is satisfied, and another which considers the condition not satisfied. The region ranges are updated accordingly for each of these states, before being added to the stack, unless a terminal state is found (one with name A or R).
def compute_regions(workflows: dict[str, list[list[Condition, str]]]) -> list[Region]:
regions = []
# Start with a single, maximal range at the 'in' workflow
states = [('in', Region())]
while len(states) != 0:
# Take the most recently added state
state = states.pop()
name, region = state
workflow = workflows[name]
for rule in workflow:
if len(rule) == 2:
condition, name = rule
# There are 2 cases - the rule is/is not satified
# Make a copy for later
skip_region = deepcopy(region)
# Case 1 - condition satisfied
# Reset the limits of the region, based on the condition
if condition.relation == '<':
region.set_upper_limit(condition.variable, condition.value-1)
elif condition.relation == '>':
region.set_lower_limit(condition.variable, condition.value+1)
# Add the completed region to regions,
# or add new state to stack
if name in ['A', 'R']:
region.accepted = name
regions.append(region)
else:
states.append((name, region))
# Case 2 - condition not satisfied
if condition.relation == '>':
skip_region.set_upper_limit(condition.variable, condition.value)
elif condition.relation == '<':
skip_region.set_lower_limit(condition.variable, condition.value)
# Redefine region, to use as input for next rule in loop
region = skip_region
else:
# End of workflow
# Either terminate or add new state to stack
name = rule[0]
if name in ['A', 'R']:
region.accepted = name
regions.append(region)
else:
states.append((name, region))
return regions
Let’s test this on the test workflows, and see what regions are produced:
test_regions = compute_regions(test_workflows)
test_regions
[Region(accepted='R', x=[1, 4000], m=[1801, 4000], a=[1, 4000], s=[1351, 2770]),
Region(accepted='A', x=[1, 4000], m=[839, 1800], a=[1, 4000], s=[1351, 2770]),
Region(accepted='R', x=[1, 4000], m=[1, 838], a=[1717, 4000], s=[1351, 2770]),
Region(accepted='A', x=[1, 4000], m=[1, 838], a=[1, 1716], s=[1351, 2770]),
Region(accepted='A', x=[1, 4000], m=[1, 4000], a=[1, 4000], s=[3449, 4000]),
Region(accepted='A', x=[1, 4000], m=[1549, 4000], a=[1, 4000], s=[2771, 3448]),
Region(accepted='A', x=[1, 4000], m=[1, 1548], a=[1, 4000], s=[2771, 3448]),
Region(accepted='A', x=[1, 4000], m=[2091, 4000], a=[2006, 4000], s=[1, 1350]),
Region(accepted='R', x=[2441, 4000], m=[1, 2090], a=[2006, 4000], s=[537, 1350]),
Region(accepted='A', x=[1, 2440], m=[1, 2090], a=[2006, 4000], s=[537, 1350]),
Region(accepted='R', x=[1, 4000], m=[1, 2090], a=[3334, 4000], s=[1, 536]),
Region(accepted='R', x=[1, 4000], m=[1, 2090], a=[2006, 3333], s=[1, 536]),
Region(accepted='A', x=[1, 1415], m=[1, 4000], a=[1, 2005], s=[1, 1350]),
Region(accepted='A', x=[2663, 4000], m=[1, 4000], a=[1, 2005], s=[1, 1350]),
Region(accepted='R', x=[1416, 2662], m=[1, 4000], a=[1, 2005], s=[1, 1350])]
Assuming that the workflows are well-defined, each region will have A or R as its accepted attribute. Also, regions should form a partition of the full set of possible parts - in other words:
- Each possible part belongs to one of the regions (either accepted or rejected)
- No part belongs to more than one region.
Therefore, to compute the total number of accepted parts, we just need to add the number of parts in each accepted component of the partition. Within each partition, the number of parts is the product of the widths of each of the attribute ranges (plus 1, to account for the endpoints) - this is implemented on the
Regionclass directly.
We can verify that the regions do in fact form a partition - first, check that the total number of parts (either accepted or rejected) is equal to the the full number of possible parts:
def count_parts(regions: list[Region], state: str):
regions = [region for region in regions if region.accepted == state]
return sum([region.count_parts() for region in regions])
assert count_parts(test_regions, 'A') + count_parts(test_regions, 'R') \
== 4000**4
print('Correct number of parts!')
Correct number of parts!
Second, check that each of the the regions has an empty intersection. Usefully, as each of the regions defines a rectangular region in 4-dimension xmas-space, the intersection will also be a 4-dimensional rectangular region:
def _intersect_intervals(interval_1: list[int], interval_2: list[int]) -> list[int]:
a_1, b_1 = interval_1
a_2, b_2 = interval_2
if b_1 < a_2 or b_2 < a_1:
return []
else:
return [max(a_1, a_2), min(b_1, b_2)]
def intersect_regions(region_1: Region, region_2: Region) -> Region:
return Region(
x=_intersect_intervals(region_1.x, region_2.x),
m=_intersect_intervals(region_1.m, region_2.m),
a=_intersect_intervals(region_1.a, region_2.a),
s=_intersect_intervals(region_1.s, region_2.s),
)
We can consider all combinations of two distinct regions from the full collection of regions:
for region_1, region_2 in combinations(regions, 2):
intersection = intersect_regions(regions[0], regions[1])
assert intersection.count_parts() == 0
print('All intersections are empty!')
All intersections are empty!
This proves that the regions have indeed partitioned the set of all possible parts. Therefore, we can use the sum of the sizes of the individual components of the partitions to give the total number of accepted parts.
We are told how many acceptable parts to expect for the provided test workflows:
assert count_parts(test_regions, 'A') == 167409079868000
print('Success!')
Success!
Finally, let’s apply this method to the actual workflows, and find the total number of acceptable parts:
regions = compute_regions(workflows)
count_parts(regions, 'A')
124167549767307
So the answer to part 2 is: 124167549767307.
Comments