Day 19: Aplenty

Completed in ~1 hours, 21 minutes.

1,528ᵗʰ worldwide.

2023-12-19

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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?

Create a map of each key to each workflow, and walk each part through the workflows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import json
from dataclasses import dataclass
from pathlib import Path

import pytest

Result = str


@dataclass
class Part:
    x: int
    m: int
    a: int
    s: int
    raw: dict[str, int]

    result: Result | None = None

    @property
    def total(self) -> int:
        return self.x + self.m + self.a + self.s

    def __repr__(self) -> str:
        return f"{self.x} | {self.m} | {self.a} | {self.s}"


@dataclass
class Step:
    field: str | None
    operator: str | None
    value: int | None

    result: Result

    @property
    def does_math(self) -> bool:
        return (
            self.field is not None
            and self.operator is not None
            and self.value is not None
        )

    def __repr__(self) -> str:
        if self.field and self.operator and self.value:
            return f"{self.field} {self.operator} {self.value} => {self.result}"

        return self.result

    def result_for_part(self, part: Part) -> Result | None:
        # Returns self.result if passes
        if self.field is None or self.operator is None or self.value is None:
            return self.result

        if self.operator == ">" and part.raw[self.field] > self.value:
            return self.result

        if self.operator == "<" and part.raw[self.field] < self.value:
            return self.result

        # Returns None if fails
        return None

    @classmethod
    def from_str(cls, raw_value: str) -> "Step":
        if ":" in raw_value:
            condition, result = raw_value.split(":")
            field = condition[0]
            operator = condition[1]
            value = condition[2:]

            return cls(field=field, operator=operator, value=int(value), result=result)

        else:
            return cls(field=None, operator=None, value=None, result=raw_value)


@dataclass
class Workflow:
    steps: list[Step]

    def __repr__(self) -> str:
        return f"{self.steps}"

    def result_for_part(self, part: Part) -> Result:
        for step in self.steps:
            result = step.result_for_part(part)

            if isinstance(result, str):
                return result


def runner(document: list[str]) -> int:
    reading_workflows = True
    workflows: dict[str, Workflow] = {}
    parts: list[Part] = []

    for line in document:
        # Switch modes
        if line == "":
            reading_workflows = False
            continue

        if reading_workflows:
            key, rest = line.split("{")
            step_strings = rest.replace("}", "").split(",")

            steps = [Step.from_str(value) for value in step_strings]

            workflows[key] = Workflow(steps=steps)

        else:
            json_line = (
                line.replace("x", '"x"')
                .replace("m", '"m"')
                .replace("a", '"a"')
                .replace("s", '"s"')
                .replace("=", ":")
            )
            data = json.loads(json_line)
            parts.append(
                Part(
                    **data,
                    raw=data,
                ),
            )

    for part in parts:
        next_workflow: Workflow | None = workflows["in"]

        while part.result not in ["A", "R"]:
            part.result = next_workflow.result_for_part(part)

            if part.result not in ["A", "R"]:
                next_workflow = workflows[part.result]

    return sum([part.total for part in parts if part.result == "A"])


@pytest.mark.parametrize(
    "filename,output",
    [
        ("example-1.txt", 19114),
        ("example-2.txt", 348378),
    ],
)
def test_runner(filename: str, output: int) -> None:
    with open(Path(__file__).with_name(filename)) as file:
        result = runner(file.read().splitlines())

        assert result == output

Answer: 348,378

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?

Same start as Part 1, but we ignore the back-half of the input. Instead, we calculate the number of possible ranges for each step.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
from copy import deepcopy
from dataclasses import dataclass
from pathlib import Path

import pytest

Result = str


@dataclass
class Part:
    x: int
    m: int
    a: int
    s: int
    raw: dict[str, int]

    result: Result | None = None

    @property
    def total(self) -> int:
        return self.x + self.m + self.a + self.s

    def __repr__(self) -> str:
        return f"{self.x} | {self.m} | {self.a} | {self.s}"


@dataclass
class Step:
    field: str | None
    operator: str | None
    value: int | None

    result: Result

    @property
    def does_math(self) -> bool:
        return (
            self.field is not None
            and self.operator is not None
            and self.value is not None
        )

    def __repr__(self) -> str:
        if self.field and self.operator and self.value:
            return f"{self.field} {self.operator} {self.value} => {self.result}"

        return self.result

    def result_for_part(self, part: Part) -> Result | None:
        # Returns self.result if passes
        if self.field is None or self.operator is None or self.value is None:
            return self.result

        if self.operator == ">" and part.raw[self.field] > self.value:
            return self.result

        if self.operator == "<" and part.raw[self.field] < self.value:
            return self.result

        # Returns None if fails
        return None

    @classmethod
    def from_str(cls, raw_value: str) -> "Step":
        if ":" in raw_value:
            condition, result = raw_value.split(":")
            field = condition[0]
            operator = condition[1]
            value = condition[2:]

            return cls(field=field, operator=operator, value=int(value), result=result)

        else:
            return cls(field=None, operator=None, value=None, result=raw_value)


@dataclass
class Workflow:
    steps: list[Step]

    def __repr__(self) -> str:
        return f"{self.steps}"

    def result_for_part(self, part: Part) -> Result:
        for step in self.steps:
            result = step.result_for_part(part)

            if isinstance(result, str):
                return result


@dataclass
class Range:
    lower: int
    upper: int


Ranges = dict[str, Range]


def range_combos(ranges: Ranges) -> int:
    count = 1

    for _range in ranges.values():
        count *= _range.upper - _range.lower + 1

    return count


def runner(document: list[str]) -> int:
    reading_workflows = True
    workflows: dict[str, Workflow] = {}

    for line in document:
        # Switch modes
        if line == "":
            reading_workflows = False
            continue

        if reading_workflows:
            key, rest = line.split("{")
            step_strings = rest.replace("}", "").split(",")

            steps = [Step.from_str(value) for value in step_strings]

            workflows[key] = Workflow(steps=steps)

    def calculate_combos(ranges: Ranges, workflow_id: str) -> int:
        combos = 0

        for step in workflows[workflow_id].steps:
            if step.does_math:
                new_ranges = deepcopy(ranges)

                if step.operator == ">":
                    if new_ranges[step.field].upper > step.value:
                        new_ranges[step.field].lower = max(
                            new_ranges[step.field].lower, step.value + 1
                        )

                        # Step results in accept, get all combos for the new ranges
                        if step.result == "A":
                            combos += range_combos(new_ranges)

                        # We're not counting the rejects
                        elif step.result == "R":
                            pass

                        # Everything else refers to another workflow
                        else:
                            combos += calculate_combos(new_ranges, step.result)

                        # Update base ranges for next steps
                        ranges[step.field].upper = min(
                            ranges[step.field].upper, step.value
                        )

                elif step.operator == "<" and new_ranges[step.field].lower < step.value:
                    new_ranges[step.field].upper = min(
                        new_ranges[step.field].upper, step.value - 1
                    )

                    # Step results in accept, get all combos for the new ranges
                    if step.result == "A":
                        combos += range_combos(new_ranges)

                    # We're not counting the rejects
                    elif step.result == "R":
                        pass

                    # Everything else refers to another workflow
                    else:
                        combos += calculate_combos(new_ranges, step.result)

                    # Update base ranges for next steps
                    ranges[step.field].lower = max(ranges[step.field].lower, step.value)

            else:
                # Base case, our step results in accept
                if step.result == "A":
                    combos += range_combos(ranges)

                # We're not counting the rejects
                elif step.result == "R":
                    pass

                # Everything else refers to another workflow
                else:
                    combos += calculate_combos(ranges, step.result)

        return combos

    return calculate_combos(
        {
            "x": Range(lower=1, upper=4000),
            "m": Range(lower=1, upper=4000),
            "a": Range(lower=1, upper=4000),
            "s": Range(lower=1, upper=4000),
        },
        "in",
    )


@pytest.mark.parametrize(
    "filename,output",
    [
        ("example-1.txt", 167409079868000),
        ("example-2.txt", 121158073425385),
    ],
)
def test_runner(filename: str, output: int) -> None:
    with open(Path(__file__).with_name(filename)) as file:
        result = runner(file.read().splitlines())

        assert result == output

Answer: 121,158,073,425,385

Day	Part 1 Time	Part 1 Rank	Part 2 Time	Part 2 Rank
19	00:31:38	1,809	01:21:18	1,528

I hate range problems 😖.

Fletcher Easton

Day 19: Aplenty

Part 1 – Prompt #

Part 1 – Solution #

Part 2 – Prompt #

Part 2 – Solution #

Recap #