[2023 Day 19] In Review (Aplenty)

[u/musifter]

The Elves thank us and give us the hang glider they've found and we "borrowed" to get up here, so we can return it. At the bottom of the parts-fall we find Elves sorting them with an unusual system based on how extremely cool, musical, aerodynamic, and shiny they are. There's a big list of workflows with conditional rules to follow that will either direct a part to another workflow or (ultimately) accept or reject it. Naturally, we're here to help.

The input is two sections. Section #1 contains a little less than 600 workflows in my input... other than the start state of 'in', the workflow names contain no vowels (including y and w). Section #2 is the stats for 200 parts.

The workflow is essentially a big state machine... you can think of the workflows as multiple states if you want to think of it in a more formal/simple way:

px{a<2006:qkq,m>2090:A,rfg}

          a>=2006        m<=2090
      px0 --------> px1 ---------> rfg0
       |             |
a<2006 |      m>2090 |
       v             v
      qkq0        ACCEPT

That's not really needed in the code though. That's more of conforming things to more standard FSMs. But for part 2, that visualization was useful for me.

I did my normal approaches here... a quick solution to see part 2, where I turned codelike stuff into actual code to evaluate, and just followed the rules.

FLOW:
while ($flow ne 'A' and $flow ne 'R') {
    foreach my $rule ($Rules{$flow}->@*) {
        my $result = eval( $rule ) // '';
        if ($result) {
            $flow = $result;
            next FLOW;
        }
    }
}

Part 2 tasks us with finding the set of valid ranges that the rules accept. This is very much like day 5... we have 4 ranges instead of 1 (but only on [1,4000], but 4000⁴ is much larger than 2³² ) and in day 5, the order of the rules tables was fixed. So unlike day 5 where I iterated over the tables, here I went to recursion (the simple way to nest iterations an arbitrary number of times).

One nice thing about this problem in comparison to day 5, is that the ranges all go from the middle to the edge. So there's only one valid range for any variable at a time (you can't have anything accepted with x < 1000 and x > 3000). And so the basic idea was that after calculating what the intersection of the rule is with the current success range, we recurse to the next state if that's valid (ie doesn't have negative length) with that category set to the new success range. Otherwise we just proceed to set the range for that variable to the fail range (because we must fail), and iterate to the next substate in the diagram. The last arrow on the right is just a forced recursion for the non-conditional rules.

Part 2 for this one did take me a while to actually get right. In the end, I really think that drawing diagrams like the above are what helped finally get it right. It was probably good that there was a warm up with day 5 for this.

[u/TheZigerionScammer]

I think I did a similar approach to yours in the end (although I didn't use recursion, I used a queue where I added the range of values which were sliced off by the condition statement and handled them later in a DFS like way), but looking back at my megathread submission for the day apparently I tried to brute force it by preemptively splitting ranges by the values found in any of the processes and evaluating all of the part ranges individually like in part 1 but that still would have meant evaluating over a billion individual parts so it never finished.

[u/musifter → u/TheZigerionScammer]

Yeah, it sounds pretty much the same. The base case for my recursion is reject/accept, otherwise it iterates over the workflow, slicing things up. If a run has no condition, it recurses straight (that's a goto... I noted that at least some workflows end with one of these and that's the only use of that workflow, so you could just substitute and discard those). Otherwise, I break the current valid range for the rule's category in (potentially) two parts:

my $less  = intersect( $ranges->{$cat}, [1, $val - ($op eq '<')] );
my $great = intersect( $ranges->{$cat}, [$val + ($op eq '>'), 4000] );

my $succ = ($op eq '<') ? $less : $great;
my $fail = ($op eq '<') ? $great : $less;

And then I alias the correct sides as the success and fail range (I was clearly focused on being clear at that point). If the success range is a valid range, I recurse on that cut. Otherwise, I've taken the "fail arrow", make it that range and go on to the next rule. We've kind of got a state machine of state machines (2D state machine) going on, where one axis is done with recursion, and the other is iteration. There is an assumption in there that loops will not be a problem.

[u/DelightfulCodeWeasel]

I noticed for my input there are quite a few stages where all options pass on to an accept state or all pass on to a reject state, so before running the logic I do 3 optimisation passes eliminating all such states. That reduces my workflow stages from 584 starting stages down to 468 stages. I'll most likely eliminate that in my revisit, because it looks like it costs more than it saves. Part 1 is 3ms with optimisation passes, 2ms without. Part 2 is 4ms with optimisation passes, 3ms without.

The solution itself is a fairly standard recursive approach, albeit split between two mutually recursive functions so that the calls actually go Evaluate -> ApplyRule -> Evaluate -> ApplyRule ->...

When I do come to revisit it and need to eliminate recursion I think I'll go with more of a task queue approach, adding stages into an active set when I queue work against them.

I quite liked this one; the ones which are almost pure software engineering give me a chance to catch up with a lot of the people who have a much wider (and deeper) set of maths knowledge to draw on than I do.

[u/terje_wiig_mathisen]

I did not remember this problem when I ran my original Perl code yesterday, but when it started a very long-running process I decided to not make a Rust port! Instead I looked at the rules and found quite a few where the last condition was either A or R, followed by a final default which was identical!

[u/musifter → u/terje_wiig_mathisen]

What were you doing that was taking so long? My code returned instantly so I never really looked at things further. So I didn't even notice that some final conditions were like that.

[u/terje_wiig_mathisen → u/musifter]

When it ran for 6+ minutes I refused to look at the mess! :-)

It just shows that even though I have been optimizing low-level code for 40-50 years, I can still make stupid mistakes...

[u/e_blake]

This was a fairly fast solve day for me, although I did trip over an issue in part 2 where my initial attempt tried to compile a range against an entire line at once, rather than one condition at a time as the row advances. It didn't matter on the example (where none of the lines have more than one condition on the same letter), but on my actual input, using the initial range of x rather than the reduced range after the first condition on x meant the second condition on x was acting on too large of a range before I patched that bug to get the star. Runtime of 120ms is not bad for the 64-bit math required (unlike day 5 which fit entire in 32-bit math).

[u/Boojum]

I'm late to this one, but argue strongly that while the puzzle presents itself as a state machine, it's actually not. Instead, what we have here is a cleverly disguised kd-tree, masquerading as a state machine!

The key to seeing this is:

1. to treat each A or R as its own unique leaf node of the tree, rather than treating them the same and getting a dag,
2. to realize that the tree description is slightly compressed with anonymous nodes (here, in your example px{a<2006:qkq,m>2090:A,rfg}, the m>2090 test is just an anonymous node that's a child of the "px" node), and finally
3. to realize that the left and right children of each node can be out of order (typically you'd just store the number and maybe the dimension you're testing on if it's not implicit; and then you'd typically have the convention that the less thans are always the left child and the greater than or equals are always the right child).

As a concrete example, suppose that we modify a subset of the example rules to only use x and y as our variables, instead of x, m, a, and s like in the puzzle. And we'll modify some numbers as well. So take this as that example:

in{x<2006:qkq,y>2090:A,rfg}
qkq{y<1416:A,crn}
crn{x>1662:A,R}
rfg{y<537:gd,x>2440:R,A}
gd{x>3333:R,R}

If we expand that out into tree form (using asterisks for the anonymous nodes) and canonicalize the left and right children (left is the lower-valued half, right is the upper-valued half), we get:

      ___ in ___
     /          \
    /            \
  qkq             *
 /   \           / \
A    crn       rfg  A
    /   \     /   \
   R     A  gd     *
           /  \   / \
          R    R A   R

Now, a k-d tree is a spatial subdivision tree. You start off with a big rectangular volume, and each node of the k-d tree recursively cuts that volume in two, subdividing the space into smaller and smaller rectangular volumes until you get down to the leaves, which form rectangular cells of irregular size.

If we plot out the above tree with spatial splits, we get something like the following (not to scale):

┌─────────────────────────┬───────────┬──────────┐
│░░░░░░░░░░░░░░░░░░░░░░░░░│           │          │
│░░░░░░░░░░░░░░░░░░░░░░░░░i           g          │
│░░░░░░░░░░░░░░░░░░░░░░░░░n           d          │
│░░░░░░░░░░░░░░░░░░░░░░░░░│           │          │
│░░░░░░░░░░░░░░░░░░░░░░░░░├──┬────────┴──────rfg─┤
│░░░░░░░░░░░░░░░░░░░░░░░░░│░░│                   │
├─qkq────────────┬────────┤░░a                   │
│                │░░░░░░░░│░░n                   │
│                c░░░░░░░░│░░o                   │
│                r░░░░░░░░│░░n                   │
│                n░░░░░░░░│░░│                   │
│                │░░░░░░░░├──┴──────────────anon─┤
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
│                │░░░░░░░░│░░░░░░░░░░░░░░░░░░░░░░│
└────────────────┴────────┴──────────────────────┘

Here, you can see that the initial "in" node cuts the entire space roughly in half along x. The left child, "qkq" then cuts that left half in two in y, with an accepted leaf in the top part, and the lower left rectangle in the diagram cut in two by node "crn" in the x dimension, leading to a rejection on the left part and an acceptance on the right. The right half of the tree after the root node, "in", follows similar rules. In each case, we eventually bottom out at leaf that we either accept (shaded rectangles) or reject (clear rectangles).

So really, this puzzle comes down to decoding a somewhat esoterically encoded 4-dimensional (k=4) k-d tree and walking it. Part 1 is asking us, for each in a set of points, to do a classic log(N) traversal of the tree to see which leaf it's in. And Part 2 is asking us to walk the entire tree, tracking the rectangles (4-d hyperrectangles) that each node covers, and total up the volume that some of the leaves cover.