2023 Day 19: Aplenty

Advent of Code
1

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.

2

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
3

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

I like your approach to part 2!

4

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”.

image

1 Like
5

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!

6

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
7

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.

8

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.

9

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
10

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 = "";

         Brace := Ada.Strings.Fixed.Index (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
               Colon := Ada.Strings.Fixed.Index (Field, ":");

               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;
   end loop Read_Workflows;

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.

11

But how did you know there was a delimiter in your input?

12

The inputs were given. Every number in that context was followed by a delimiter. Note that I didn’t do part 2’s, so only had part 1’s to go off of. I used different versions based off of the current context. Essentially I broke the parsing down into: parse specific values, then parse lines, then parse sections, then parse the file. It lead to pretty simple code and was nice and readable.

13

Right. You were doing a single pass over the line, I take it. I figure that compared to reading the line from the file, scanning the String in memory is essentially free, so I did multiple passes.

14

I generally read a line from the file at a time, then submitted that to my Parse_Line operations as a string, which called the individual element parse operations. Their “last” parameter would help keep my position in the string as I went through it. It was definitely single pass though.

For AoC I didn’t spend a lot of time buffing up the input validation and just kept it simple. For real world apps, I would be more thorough and clever. But luckily with Ada if I added the input incorrectly it catches all that and generates an exception, so simple was sufficient for AoC.