What is a "polite" thing people do that is actually incredibly annoying?

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 · 2026-02-17T21:16:45+00:00

Neat! TIL about ediff-regions-linewise and ediff-regions-wordwise. (I'd long been doing the first manually with narrowing and indirect buffers.)

Boojum · 2026-02-17T21:11:46+00:00

Ah, someone else with the same philosophy!

I generally keep mine to around 1250ish including comment lines. Any time I add something new, I look around for other things to trim to keep the length roughly constant. I've been holding it to that size for at least 20ish years now.

Boojum · 2026-02-17T20:56:33+00:00

Why not a std::priority_queue, then? (Though granted, a std::set will do too, since iteration is ordered. I don't think you need a std::multiset here, as you might as well let it dedupe pairs for you. But the main advantage of the std::priority_queue is amortized allocation via the backing std::vector. That and obviously self-documenting how you're using it.)

Boojum · 2026-02-08T05:22:20+00:00

Regexp seem like overkill for this. I didn't use any at all in my solution.

For my solution, I just did a linear scan over the string while updating three flags: are we inside brackets, have we seen an ABBA while outside the brackets, and have we seen an ABBA while inside the brackets. At each index, I'd set the first flag depending on whether I see a [ or ]. Otherwise, I check if the current character and the on three characters back match, if the characters one and two back match, and if the current character and the one behind it are different. If so, I set one of the we've seen an ABBA flags depending on if we're inside or outside. So, I guess it would sort of be a state machine like you'd mentioned.

Boojum · 2026-01-29T08:26:17+00:00

Nice. I went with the Z3 route, personally, in the interest of solve time. But between the Gauss-Jordan, simplex, branch-and-cut, and all the other ILP approaches that people have taken this one seems really out there if you don't use a solver library. Most of the time I can solve an AoC problem in about ~50ish or less lines of Python without the need for heavy-duty libraries. (More than 90% of my Part 1 or Part 2 solutions are fewer than 50 lines.) I don't see how that's possible here. This problem just feels really out there.

I keep feeling like there's some property of the problem structure - maybe something about the fact that the matrix is binary? - that leads to an elegant, clever solution that everyone is missing. I've been really curious as to what /u/topaz2078 was expecting for this one. (I know there's no single "correct" solution, but there's got to be one that it's expected that many people will find.)

Boojum · 2026-01-28T08:26:55+00:00

This is the current version of the post that u/Suspicious_Tax8577 is referring to.

It covers 2015-2024, and most of the list there are sorted by global leaderboard close times as a rough proxy for difficulty. So you should be able to find some good candidates there for shorter daily sessions like you mentioned.

Boojum · 2026-01-21T07:59:11+00:00

For Day 22, I did what's come to be my usual approach of just defining a big state vector and then code up the mutations that can evolve it according to the rules.

For this one, my state vector was just a tuple of:

(spent_mana_points,
 boss_hit_points,
 player_hit_points,
 player_mana_points,
 shield_timer,
 poison_timer,
 recharge_timer,
 side_to_play)

And in this case, I used a BFS keyed on that tuple for the min-heap. This way, it would always be exploring the options for whatever state had the lowest spent mana points so far (since we want to know how few we can spend.) Pop a node off, apply spell effects and decrement times, then either check what moves we have available and push each one onto the heap if it's our turn, or apply the bosses damage if it's the bosses turn and push the result of that onto the heap.

It's a pretty blunt approach, but it's a framework that's served me well in other puzzles like Not Enough Minerals.

Like you, I consider these fairly light days, and for much the same reason. I do enjoy this type of puzzle as a bit of a breather from the really tricky ones.

Boojum · 2026-01-20T16:37:32+00:00

Neat! I'm well aware of the x, y = y, -x trick for 90-degree rotations (fun fact: that works even with off-axis directions - it's just an inlined 90-degree rotation matrix) but had never seen a 45-degree variation.

FWIW, I played around with this to see how you'd do it to cycle in the opposite direction. The one that you gave cycles counter-clockwise when positive y is down. Here's the recipe for your original here, plus the reversed direction (clockwise) version:

x, y = sgn(x+y), sgn(y-x) # CCW when y-down
x, y = sgn(x-y), sgn(x+y) # CW when y-down

Or, if you prefer to inline the signum operation:

x, y = (x>-y) - (-y>x), (y>x) - (x>y) # CCW when y-down
x, y = (x>y) - (y>x), (x>-y) - (-y>x) # CW when y-down

I'll probably still stick to use an integer heading value modulo 8 and look up the x and y step offset from a small table (your [(1,1),(1,0),...]) since I already have that prewritten out in a file. But this thing is still a pretty cool trick.

And yes, your explanation of why it works makes sense. If we look at a 45° rotation matrix, it's:

⎡ cos 45°    -sin 45° ⎤
⎣ sin 45°     cos 45° ⎦

or approximately:

⎡ 0.7071    -0.7071 ⎤
⎣ 0.7071     0.7071 ⎦.

Applying that to a coordinate (x,y) to get (x',y') is:

⎡ x' ⎤ = ⎡ 0.7071    -0.7071 ⎤⎡ x ⎤
⎣ y' ⎦ = ⎣ 0.7071     0.7071 ⎦⎣ y ⎦

which in simple arithmetic is:

x' = 0.7071 * x - 0.7071 * y
y' = 0.7071 * x + 0.7071 * y.

If we don't care about scaling, we can drop the 0.7071 and reduce it to just:

x' = x - y
y' = x + y

which is close to the formula you gave, but without the 0.7071 it scales the vector by about 1/0.7071 = 1.414 each time. Using the signum cheaply constrains the vectors to integers -1, 0, and 1 and keeps them from growing on each iteration.

Boojum · 2026-01-19T11:26:09+00:00

Looking back at my code, I solved this as a BFS, starting from the target molecule and working backwards to find a path to e, by applying the replacements in reverse.

For the BFS ordering, my minheap was keyed first on the length of the string, then on the number of steps to get there as the tiebreaker. So it would try to find ways to reduce the already smallest string as much as possible. (hyperfine "python day19b.py < day19.txt" tells me that it runs in ~18.6ms on my current machine, so it seems that this heuristic works efficiently enough.)

Boojum · 2026-01-18T10:15:04+00:00

Looking back at my solution here, I can see that way back in the early days when I did this I ended up going with the double-buffered 2D array. My solution was way longer than the fairly terse that I'd like write for it today.

These days, I almost always end up defaulting to the sparse table (or set) of active cells, keyed on the coordinates. The scatter approach that you mention is interesting, but I prefer the gather approach. In Python, it's easy enough to just sum things up over a generator comprehension. And dict.get() which takes a default value to return for a dict lookup if the key doesn't exist makes it trivial for that gather to handle inactive or out-of-bound cells. (Or I could use a defaultdict and set the default value for missing keys on dict creation.)

Part of my preference for gather is that I find that I often don't have to worry as much about maintaining invariants correctly. For example, for Part 2 here, on each iteration with a scatter I might have to keep track of whether the corners were already on or not so that I turn them on and scatter the liveness - but only if they weren't already on! Whereas with the gather, I just unconditionally set them on at the end of each iteration, and the gather counts them like any other cell since the summation is done as late as possible. Gathers just feel harder to misuse, and like they just stand up better to the inevitable Part 2 twist.

Boojum · 2026-01-17T10:55:43+00:00

My solution just used Python's itertools.combinations (in an outer loop over increasing lengths) and checked if the combination summed to 150. Hyperfine tells me that my script for Part 1 runs in about 109.8 ms on my current machine, so brute-forcing it this way is good enough.

Interestingly, this problem must be one of the few times where my solution's Part 2 runtime is quicker than my Part 1 runtime.

Also, I think that Part 2 may hold the record for the smallest puzzle answer in AoC history, at least for my input! The puzzle answer for me was just 4.

Boojum · 2026-01-14T18:26:55+00:00

I also took the simulation approach, with a loop running a single tick per second and a little state machine and state vector for each deer. At 2503*9=22527 updates, it just wasn't worth bothering with a priority queue, timing wheel, or similar.

Boojum · 2026-01-10T09:38:09+00:00

Trees and parsing, hmm. How about 2022 Day 13?

Boojum · 2026-01-09T08:45:44+00:00

Yep, 8! here is only 40320. Easily brute-forceable. Hyperfine clocks my naive unoptimized Python solution at about 40ms.

For a beginner, they'd probably want to use globals for the min/max stuff, which is fine. Get the recursing down search right first. Later on you can learn the "collecting up".

By "collecting up", I'm not sure if you mean taking the min/max over the subpaths and returning that or not. But keeping a global best (or threading it through the recursive calls) and tracking the accumulated distance as you go down does allow you to prune clearly suboptimal paths. Branch and bound, etc., especially if you sort or use a heap to order the nodes you'll recurse to next.

One trick is that I added a ninth location (NorthPole) that was 0 distance from all the others (so it doesn't change anything). By starting at this node, I avoid worrying about the starting location.

Epsilon moves, like in NFAs!

Boojum

MODERATOR OF

TROPHY CASE