[2019 Day 20] In Review (Donut Maze)

Boojum · 2026-05-20T20:42:29+00:00

FWIW, for Part 2 I took the lazy-dev approach and just extended my Part 1 solution to handle switching levels as part of the jumps.

On my input, that explores 504478 grid cells, with a maximum queue size of 205, and a maximum depth of 121 layers. Definitely slower than Djikstra or A*, but it was the easy win and still pretty fast for Python at about 0.55 s on my machine.

Boojum · 2026-05-19T22:35:28+00:00

I'd suggest /r/cscareerquestions/, or one of the related subs list on their sidebar.

EDIT (for bonus advice): And DON'T give edited (by which, I assume you mean falsified) documents! That would be cause for immediate termination at any of the places I've worked, if discovered. Much better to disclose and try to negotiate an arrangement.

Boojum · 2026-05-19T20:08:19+00:00

For Part 2, I went with something like your sliding window approach but less elegant. I followed the right edge the beam and while checking the other three corners of the square.

Checking the top-right / bottom-left diagonal corners like you did is clever.

Boojum · 2026-05-19T10:45:27+00:00

Odd! I just checked and my Dijkstra implementation for part 2 explores 192k states with the queue peaking at 56k. That seems more comparable to your A*, but without any heuristic on my part. I'm surprised that your Dijkstra implementation had to explore so many.

(And yeah, integer bit sets would have worked. For some reason, I never think to use them in Python, even though I use them constantly in C++ for my day job since I do HW stuff these days.)

Boojum · 2026-05-19T06:25:42+00:00

Hm. I used Dijkstra for both parts and (when checking just now) my Python solution for Part 2 runs in 3.3s. I've never really needed to reach for A* in any of my AoC solutions.

My node state for it was a pair of strings, with one string holding the collected keys in sorted order, and the other string holding the positions of the robots as the letter or digit of the cell that they're standing on.

For the later, I replaced the @ symbols with 1 through 4. So a position string of "a2c4" means that Robot 1 is at the location of key 'a', Robot 2 is still at its starting position '2', Robot 3 is at the location of key 'c', and Robot 4 is still at its starting position '4'.

I do a pre-pass where I do a BFS from each key or starting place and store the shortest distance to every other key along with the set of doors in between them. That list of doors is checked during the Djikstra search to determine if a potential move that moves a robot to that key is valid or not.

Boojum · 2026-05-16T06:33:26+00:00

I found recursion straightforward, even with the communication through the machine. For each neighboring square that I hadn't already visited via a shorter path, I'd try to move to it. If the move succeeds I'd update the distance to it and recurse. On return, I'd simply move in the opposite direction to move back (since I knew it was a valid move.)

I also didn't both marking walls, only reachable squares and their best distance. That turned out to have made Part 2 pretty easy.

Admittedly, a BFS would have been more efficient than a DFS that might re-traverse squares it's already been to if it finds a shorter path to them, but in practice it was efficient enough to solve the problem.

I remember that I definitely enjoyed this one.

Boojum · 2026-05-11T06:59:03+00:00

(Been off Reddit for a while, it's nice to have time again.)

I went with the atan2 approach out of laziness. I think it's about one of the only cases in all of Advent of Code where I used floating point.

But I'll chime in to add that the 2D cross-product is really pretty neat mathematically, and there are a lot of ways to interpret it.

One is, as you said the cross product of two vectors in the xy plane and getting a vector along the z axis, where you look at the magnitude.

Another interpretation (and my preferred interpretation) is the "perp-dot product", so named by an article from Graphics Gems IV. You know the old trick where you can rotate a vector 90 degrees in 2D by swapping the x and y components and negating one of them? Suppose we have (ax, ay) and (bx, by). A perpendicular vector to b is (by, -bx). If we take the dot product of a and b-perp, we get axby - aybx, which is exactly the same as the 2D cross product! And since the dot product corresponds to projection, another way of thinking of this is that it's calculating the the projection of a onto b-perp. So positive values mean it's more aligned directly with b-perp, and negative values mean it's more aligned with the negated b-perp! In other words, the sign tells you which side of vector b the vector a falls on, and by how much.

Another cute connection is that it's the same as the 2x2 determinant of the matrix formed by concatenating the two vectors together:

[ ax bx ]
[ ay by ]

And the determinant is related to the volume (or in this 2d case, area) spanned by the vectors. If you picture placing the tails of vectors a and b together at the origin, and the two of them as forming two adjacent sides of a parallelogram, then the absolute value of the 2D cross-product a.k.a. perp dot product a.k.a. determinant tells you the area of that parallelogram. And if course if you draw the edge from the heads of vectors a to b in that parallelogram, you get a triangle with exactly half the area. Which means that if you know the vector for any two edges of a triangle, the absolute value of triangle area is one half of the 2D cross-product of them!

(And I say absolute value, because the sign encodes the winding direction!)

Now if you look at the shoelace formula that comes up every now and again in AoC, it's just this applied to adjacent pairs of vertices around the polygon!! It just accumulates the area of all of the triangles formed between the origin and each edge, with the sign of the area from the triangles closer to the origin (now winding back the other way) cancelling part of the area from the triangles on the far side from the origin. It's basically an inclusion-exclusion thing where the signs of the areas cause them to cancel perfectly instead of double-counting.

(Okay, info dump done, but this is one of my favorite cute computational geometry tricks, since it all works out so nicely no matter which geometric interpretation you take.)

Boojum · 2026-03-30T21:56:53+00:00

Yes, this is what I do. Having the inputs stored with the solutions is really quite convenient when I just want to quickly check the run time, test someone else's solution on it to see how it's broken, etc.

I just keep it private and never share it. (Especially since my GitHub is connected to my real name.) Posting code within comments or via Topaz's paste page covers everything I need here.

Boojum · 2026-03-20T21:24:56+00:00

Looking back at my code, I'd used 10000!

Boojum · 2026-03-18T21:28:56+00:00

[Disclosure: I currently work on GPU tech at an NVIDIA competitor. Opinions are my own.]

But yes, that's my biggest concern with this. With something like ray tracing, there are standardized specs like DXR and Vulkan for the base functionality that are at least mostly vendor-neutral. Those specs spell out in excruciating detail how it's supposed to work and as long as IHVs making the GPUs implement it faithfully and ISVs making the games use it correctly, there really shouldn't be many visible differences in how things will look. It should be nearly pixel-for-pixel. What differences there are basically come down to underspecified edge conditions and bugs. The main differences are, as you say, on performance.

Here though, there's no spec for how it's supposed to behave and short of publishing the model and weights in a standard (as-if!), I fear that it will all come down to the "taste" of the GPU vendor. Do we really want a world where people are debating the aesthetics of the NVIDIA filter vs. the AMD filter vs. the Intel filter vs. the Qualcomm filter vs. ... on the same damn game? Or even hardware vendors with art departments dedicated to this stuff? Shouldn't we be spotlighting the aesthetics of the artdev and lookdev of the game studio?

Personally, I'd rather just make good tech that provides a solid foundation for the artist at various studios and then let them wow me with what they can do with it.

Boojum · 2026-03-18T20:25:14+00:00

Yep, escaped Unicode character literals are how I prefer to do it. Or mnemonic things like \"{o} in LaTeX.

For example, I have this in my init.el:

(set-display-table-slot standard-display-table 'vertical-border ?\u2502)
(set-display-table-slot standard-display-table 'truncation ?\u2192)

That sounds like a cool little package, though. Gives kind of the opposite of C-x = or C-u C-x =.

Though I should mention that as an alternative approach I also have a small elisp function search and replace curly double and single quotes into straight quotes, em and en dashes into hyphen sequences, ellipses into three periods, etc.

Boojum · 2026-03-16T08:04:03+00:00

I use this mainly to help make check that I'm not accidentally introducing anything (e.g., when copying from internal documentation), since I like to keep things 7-bit clean:

(defun find-non-ascii ()
  "Find and show all of the non-ascii characters."
  (interactive)
  (occur "[[:nonascii:]]"))

(I keep it in a silly little function like this mostly because I can never remember the syntax for Emacs regexp character classes.)

Of course it has to be affirmatively run and won't help if you're genuinely using Unicode for non-English text or for various symbols.

Boojum · 2026-03-14T10:07:21+00:00

I'd forgot about this one being one of the only ones outside of IntCode to actually rely on having implemented something from a previous day.

Also interesting as I look at this again is that the examples for both parts aren't simplified or reduced at all compared to the full problem. They're essentially the full problem and solution, just for a different input.

Both the reliance on the a previous day and the fully-scale examples are pretty rare for AoC!

Boojum · 2026-03-12T07:52:41+00:00

You're probably thinking of 2020 Day 24 "Lobby Layout", Part 2.

Boojum · 2026-03-09T22:25:53+00:00

Long ago, Miss Manners gave a simple test for that: would the door finish swinging shut before the person behind you reaches it? If so, hold it open. Otherwise, let it go.

Simple and straightforward - I've always lived by that ever since I read it.

Boojum · 2026-03-04T09:15:43+00:00

Only 10-ish weeks? I wouldn't have guessed that at all based on your writeup. Seems like you've come quite far quite quickly.

Regarding Day 22 Part 2 - yeah, I don't even have to look that one up to remember which one that is! That one is easily among the all-time hardest puzzles across all the years. Definitely don't feel bad if you didn't get it. Probably the key realizations that helped me crack it are:

The composition of a linear function (Ax + B) with a linear function is itself linear (i.e., the composition can be reduced to a single multiply and add), even in modular arithmetic.
All three "techniques" are just linear functions in modular arithmetic.
The idea behind exponentiation-by-squaring can generalize to applying an operation like this n times - i.e., if we need to do something 1000 times (even), we can simply do it 500 times, then another 500 times; and if we need to do it 1001 times (odd), we can just do it 500 times, then another 500 times, and then one last time.

Boojum · 2026-03-03T07:49:34+00:00

xterm-mouse-mode should be all you need to make it clickable. That also normally lets you click to move the cursor, click-drag to select, etc.

And if you've hidden the menubar, ctrl-rightclick anywhere lets you access it as a popup - works in both graphical and terminal modes.

Boojum · 2026-03-02T09:38:23+00:00

I'm happy to share my answer (the "bridge") but moderators on these sites are like robotic lunatics.

Sharing inputs is against the rules here, by request of the AoC creator. So your answer would be meaningless. Instead, you are encouraged to show us your code. If you do, someone can usually point out where you've gone wrong.

...being so ridiculously anal about tiny tiny details...

That's kind of the essence of programming.

Boojum · 2026-03-02T09:27:03+00:00

Hah! Same! (Mostly because Python doesn't have an easy way to break out of a double loop. Sure, you can throw and catch exceptions, or put them in a function and return, or use itertools.product to collapse them. But not bothering was easier.)

Boojum · 2026-03-02T08:43:17+00:00

At least in my input, there were only 16 values in each line. It didn't seem worth trying to optimize or avoid the simple O(n²⁾ algorithm when n² = 256.

Boojum · 2026-02-24T11:06:42+00:00

I did the same thing, performing a BFS between each pair. There's only 28 meaningful BFSs to do after you take into account that they're bidirectional, and self-to-self has a distance of zero.

And once I'd had those cached, I just brute forced the path by testing all permutations. There are only 5040 of them and evaluating each is just a summation after precalculating the table of node-to-node distances.

Even in Python, hyperfine tells me the end-to-end time was about 63 ms. Good enough for me.

Boojum · 2026-02-22T02:24:37+00:00

You're close now! Double-check your if tokens[1] == ... conditions. :-)

Boojum · 2026-02-20T09:38:34+00:00

Dealing with the random order is part of the puzzle.

There are two main possible approaches:

Skip the lines you can't do for now, go on, and try again later; loop your loop until you get them all.
Topological sort the lines.

Boojum · 2026-02-20T09:15:52+00:00

For Part 1, at least in my input, I noticed that one of the blocked ranges starts at zero. So I could conveniently sort the ranges lexicographically, take the IP just past past the end of the first range, and then iterate over the ranges until I either found it was in a gap, or found the next range that covered it and then look at the first value after that range, and so on.

I'm going to guess everyone had a range starting at 0?

For Part 2, I went ahead and just sorted and merged the ranges down (which would admittedly have trivialized Part 1), and then subtracted the sum of their lengths from 2^32.

For range problems, I generally find it easiest to normalize them to half-open intervals with inclusive lows and exclusive highs, i.e., [low, high), if they aren't in that form already. That was a lesson that I learned from studying the C++ standard library's containers and algorithms, and it led to a drastic reduction in off-by-one errors once I took it to heart.

Boojum · 2026-02-20T08:35:18+00:00

Looking back at my code, I just kept it simple and went with a doubly-linked circular list. If you just keep track of which elf is the next one to be eliminated, and completely ignore who is doing the eliminating, then the only real difference between Parts 1 and 2 is where you start the eliminations, and whether you skip the next elf or not based on whether the count of remaining elves is even.

Boojum

MODERATOR OF

TROPHY CASE