# 2023 Day 19: Aplenty

Today’s puzzle is cute:

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

* `x`: E*x*tremely cool looking
* `m`: *M*usical (it makes a noise when you hit it)
* `a`: *A*erodynamic
* `s`: *S*hiny
``````

Kind of embarrassed how I didn’t notice what the categories “spelled out” at first.

I solved it in a manner similar to Day 5: interval splitting. Only this time, you have 4 simultaneous intervals to keep in mind, which makes it slightly more challenging. Given a location and a group of intervals (one for each category), examine the location’s rule. If none of its criteria apply, move the group to the default and re-enqueue it. If a criterion applies, then either reassign the intervals to the new location (if they all satisfy the criterion) or enqueue two new groups, one for the subinterval that satisfies the criterion (which has a new location), and one for the one that doesn’t (which is still in the same location).

Using the original example:

• Start at `in` with intervals (1,4000),(1,4000),(1,4000),(1,4000).
• The rule `s < 1351` applies, so enqueue two new groups by splutting this one: the first group is at `px`, with intervals (1,4000),(1,4000),(1,4000),(1,1350); the other remains at `in` with intervals (1,4000),(1,4000),(1,4000),(1351,4000).

…and so forth. When a group visits `A`, add the group’s number of intervals to the running total; when a group visits `R`, discard the group altogether.

Since the puzzle’s data’s first section (the list of workflows) is actually a program, I have turned it into an Ada program, so the Ada compiler’s parser (be it HAC, GNAT or another Ada compiler) does the job of parsing and doing something meaningful with that program. Advantage: no need to write a parser. Disadvantage: the solution work with only one set of input data…
For Part 2,
I’ve done something similar to Day 18: grab all numeric data for say `x` (but add 1 to a value when the operator is “>”), sort it, insert 1 and 4001: you get intervals. Same for the `m`, `a`, `s` dimensions. Then you browse all possible combination of intervals.
For each combination, you run the program of Part 1 with a point (x, m, a, s) within the 4D thing formed by the intervals and add the volume of that 4D thing when the result is Accepted.

2 Likes

I was wondering about that. Was it a lot of work to transform the workflows into an ada program?

I like your approach to part 2!

Search & replace using an editor which can use regular expressions.
It was quick.

For Part 2, I have thrown the rules into a spreadsheet program and massaged them there!
It was less quick.
The most time lost was due to a copy-paste bug: I have used the example’s “in” procedure instead of the input data’s “in”.

1 Like

I forgot to mention it earlier, but the hardest part for me was parsing the input data. I spent wayyyyy too long on that, unusually long. Your approach circumvents that!

This was probably my favorite puzzle of the year. I solved it by walking up the tree from each accept node and applying or inverting conditions to narrow the possible range of parts that output could receive.

The example visualized as a tree:

``````       px{a<2006:qkq,m>2090:A,rfg}
/          |         \
/           |          \
a<2006      m>2090        true
/             |            \
/              |             \
qkq{...}        accept(1)    rfg{s<537:gd,x>2440:R,A}
/          |       \
/           |        \
s<537       x>2440      true
/             |          \
/              |           \
gd{...}         reject       accept(2)
``````

In order to reach `accept(1)`, the condition that precedes it (`a<2006`) must be false since conditions are evaluated left-to-right, and if the prior condition were true, the part would have been sent down that prior path. Likewise if the condition is true at the accept node, then it won’t be passed along to accept nodes further down the tree.

This leaves us with a simple set of rules we can apply while walking the tree:

• If there is a node to our left, go there. If there’s no node to our left, go up one node instead. If we can’t do either of these, then we’re done.
• When going up a level, if we arrive at a condition it must be true.
• When going left one node, the condition we arrive at must be false. Inverting this condition yields the condition that makes the input flow to the accept node we started from.

I don’t think this process has to do be done from bottom to top, but it seemed like the most obvious way to go about it at the time since it won’t visit any dead ends.

The whole process for `accept(2)`:

``````start at accept(2) with the intervals (x=[1,4000], m=[1,4000], a=[1,4000], s=[1,4000])

go up to rfg            use the condition                 (here, true for all values so interval doesn't change)
go left to x>2440:R     invert the condition so x<=2440   (x=[1,2440], m=[1,4000], a=[1,4000], s=[1,4000])
go left to s<537:gd     invert the condition so s>=538    (x=[1,2440], m=[1,4000], a=[1,4000], s=[538,4000])
go up to px             use the condition                 (here, true for all values so interval doesn't change)
go left to m>2090:A     invert the condition so m<=2090   (x=[1,2440], m=[1,2090], a=[1,4000], s=[538,4000])
go left to a<2006:qkq   invert the condition so a>=2006   (x=[1,2440], m=[1,2090], a=[2006,4000], s=[538,4000])

no nodes left to visit so we're done
``````

Then the total number of valid inputs that reach `accept(2)` is the length of each interval multiplied together `2440*2090*1995*3463`. Repeat for all ‘A’ nodes and sum the results and that’s the solution.

I was somewhat surprised to find out that this wasn’t the “standard” solution and lots of people used interval splitting, something I hadn’t considered until checking the solutions megathread.

Yeah the input was really annoying to parse in Ada. I made do with string splitting which is fine I guess…just a lot of code to write before you can get to the fun part.

2 Likes

I didn’t find this difficult to parse. It did require some thought about how to represent the parsed data, but once I decided on that, the parsing was straightforward.

To start, my input features:

``````3342:A
``````

Can’t use Ada’s `Integer_IO` package to read `3342` because the `:` raises a data error. This stung someone last year, too.

I had other issues, but I can’t remember them all.

I had a similar issue with an earlier day where the input was numbers separated by commas. I ended up making a generic procedure with a nearly identical signature to Integer_IO.Get so I could just use it the same way. It was pretty useful in various days.

``````    generic
type Element_Type is (<>);
Delimiter : String;
procedure Get
(From : in     String;
Item :    out Element_Type;
Last :    out Positive);

procedure Get
(From : in     String;
Item :    out Element_Type;
Last :    out Positive)
is
Index : constant Positive := Ada.Strings.Fixed.Index
(Source  => From,
Pattern => Delimiter);
begin
Last := Index - 1;
Item := Element_Type'Value(From(From'First..Last));
end Get;

procedure Get_Integer is new Get(Integer, ":");
``````
1 Like

Sure. You have to know where the colon is, so you can evaluate the value. Finding the colon tells you whether its a conditional or unconditional rule, too. And there are other ways to convert a string to an Integer than Integer_IO.

The data are a node ID followed by a comma-separated list of rules enclosed in braces. A rule can be unconditional, in which case it is simply a destination ID, or conditional, in which case it is a category letter followed by an operator symbol followed by a colon followed by a destination ID.

My approach was

``````   Read_Workflows : loop
One_Flow : declare
Line : constant String := Ada.Text_IO.Get_Line (Input);

Brace : Natural;
List  : PragmARC.Line_Fields.Line_Field_Info;
Colon : Natural;
Rule  : Rule_Lists.Vector;
begin -- One_Flow
exit Read_Workflows when Line = "";

List := PragmARC.Line_Fields.Parsed (Line (Brace + 1 .. Line'Last - 1), ',');

All_Rules : for I in 1 .. List.Field.Last_Index loop
One_Rule : declare
Field : constant String := +List.Field.Element (I);
begin -- One_Rule

if Colon = 0 then
Rule.Append (New_Item => (Test => False, Next_Rule => +Field) );
else
Rule.Append (New_Item => (Test      => True,
Next_Rule => +Field (Colon + 1 .. Field'Last),
Category  => To_Category (Field (1) ),
Operator  => Field (2),
Value     => Integer'Value (Field (3 .. Colon - 1) ) ) );
end if;
end One_Rule;
end loop All_Rules;

Map.Insert (Key => Line (1 .. Brace - 1), New_Item => Rule);
end One_Flow;
I have `To_String` and `To_Unbounded_String` renamed as unary `+`, and `To_Category` is a simple expression function to convert the category letter into the corresponding enumeration value. The rest seems pretty clear.