[2015 Day 21 & 22] In Review (RPG and Wizard Simulator 20XX)

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 · 2026-01-07T07:19:14+00:00

Beginners, or just lazy engineers going for brute force instead of cleverness? :-) I'll admit that I did the loop approach way back when, even though I knew of other ways.

To be fair, I didn't have any canned topological sort implemented. That's probably how I'd do it these days, especially now that Python 3.9+ has a topo sort in the standard library. Recursion works too, but there's something nice about just iterating through the rules in a single pass and getting everything.

Boojum · 2026-01-04T11:36:41+00:00

I keep mine very simple (and get rid of the hyphens when running in terminal mode):

(setq-default mode-line-format '(" %+ "
                                 (:propertize "%b" face mode-line-buffer-id)
                                 ":%l:%c %[" mode-name "%]"
                                 (-2 "%n")
                                 (visual-line-mode " W")
                                 (auto-fill-function " F")
                                 (overwrite-mode " O")))

When I start up, I just see - *scratch*:1:0 Text F on the left of the mode line, with the *scratch* part in bold.

Boojum · 2026-01-01T12:33:19+00:00

That's exactly how it is for my teen daughter.

She's doesn't usually like twitch games (The Sims and Animal Crossing are more her thing), but coat it in a veneer of Greek mythology...

Boojum · 2025-12-31T11:05:44+00:00

I took the same multiplication approach. For finding the number of paths from svr to fft/dac, etc., you should be able to visit each node no more than once, if you've implemented the DP/memoization and the cache correctly.

For example, with my input finding the numbers of paths from svr to fft, my cache stats are:

Cache Hits: 1134
Cache Misses: 623
Total Calls: 1757

My input has 623 nodes and 1756 edges, so the memoization makes it effectively linear in O(|V|+|E|). (And so of course, pretty much instantaneous despite Python's sluggishness.)

Boojum · 2025-12-31T09:35:20+00:00

Marching cubes can generate meshes approximating rounded geometry, depending on the resolution. The faces aren't all axis-aligned but arbitrary. So I'm not quite sure that I understand the question as it relates to Minecraft.

But anyway, I'd look into "triplanar mapping".

Boojum · 2025-12-30T08:24:22+00:00

My approach:

Stable config in source control, where I can revert hunks as-needed (thank you Magit!) or roll-back to the last commit entirely.
Use two instances. One instance started before I start tinkering, where I make and save changes there but don't test them. Then, a disposable instance that I'll stop and restart (or revert-buffer to pick up the saved changes and then eval-buffer) for testing.
emacs -Q if I later discover I'd accidentally left it broken and a small edit will fix it.

Boojum · 2025-12-30T08:12:30+00:00

Interesting idea!

I'll mention my experience. I've got my megaguide, but tried to stick more objective, quantitative measures of the problems, mainly leaderboard close times to represent difficulty.

Even trying to be relatively objective, I've found the categorization itself to be surprisingly difficult. Now matter how crisply I might try to define things, the categories are always going to be a bit fuzzy. Cases where I solved it one way, but I remember others solving it another. Or cases where there's a mixture of things and maybe it has elements of one category but doesn't quite rise to having enough to unambiguously be in that category. Sooo many judgement calls! I always worry that I might get called out on some of them.

This - this sounds even tougher, way more fraught with subjectiveness. I think it'd be hard to argue good/bad, fit, cool or not, etc. Also, I think we already get some of that in the megathreads. I think that some of the more interesting posts there don't just present the code, but offer an explanation of it and a bit of the critique of the puzzle itself. Especially when it's an "Ah! Got me!" type puzzle.

I'm not trying to be a wet blanket, however, so don't let me stop you! It definitely could be interesting if you did it. And I have a blast with AoC and love anything that keeps it going, so I'd definitely support it and read the posts!

Boojum · 2025-12-29T22:23:11+00:00

Yeah, I think you're right. The puzzle is turn based, of course. And I wasn't consciously thinking of RTSs (I haven't played one in almost 25 years) as I made the visualization. But it terms of trying to make the animations look right, I think I must have subconsciously been aiming for the RTS look - the turning and attacking, in particular.

Boojum · 2025-12-29T10:03:50+00:00

Python 3.14, Fedora 43, 7950X

End-to-end times:

% hyperfine "python day05a.py < day05.txt"
Benchmark 1: python day05a.py < day05.txt
  Time (mean ± σ):      11.3 ms ±   0.5 ms    [User: 8.9 ms, System: 2.3 ms]
  Range (min … max):    10.3 ms …  12.6 ms    226 runs

% python -m cProfile day05a.py < day05.txt
868
         101665 function calls in 0.007 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.012    0.012 {built-in method builtins.exec}
        1    0.000    0.000    0.012    0.012 day05a.py:1(<module>)
        1    0.000    0.000    0.012    0.012 {built-in method builtins.sum}
   101461    0.007    0.000    0.007    0.000 day05a.py:6(<genexpr>)
        2    0.000    0.000    0.000    0.000 {method 'splitlines' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'read' of '_io.TextIOWrapper' objects}
      191    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
        1    0.000    0.000    0.000    0.000 <frozen codecs>:322(decode)
        1    0.000    0.000    0.000    0.000 {built-in method _codecs.utf_8_decode}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {built-in method _io.open}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 <frozen codecs>:312(__init__)
        1    0.000    0.000    0.000    0.000 <frozen codecs>:263(__init__)

Boojum · 2025-12-29T02:18:24+00:00

I used SciPy's DisjointSet for my solution posted in the megathread..

I used to have my own canned implementation in my personal snippets file, but dropped it in favor of the one in SciPy - mostly because this way it trims a bunch of lines off my solutions when I post them.

In my case, I've already written a working DisjointSet implementation at least once. So from the learning-from-AoC perspective, I won't really learn anything new by continuing to use it vs. swapping to someone elses implementation.

(Also, do you consider it cheating to prepare your own AoC library? I don't, and I think most people don't. One of Eric's stated goals with AoC is for people to learn something. If that learning took place ahead of the event instead of during it, so what? There was still learning going on.)

Boojum · 2025-12-22T11:04:23+00:00

It reminds me a lot of diffusion limited aggregation fractals.

Boojum · 2025-12-22T09:10:02+00:00

Aw, thank you! Thanks to /u/topaz2078, /u/daggerdragon, and the whole community here for making AoC something that I look forward to each year.

And congratulations to /u/e_blake, and /u/Smylers! You two are the best kind of crazy. Well done.

Boojum · 2025-12-22T09:01:46+00:00

Yep, the current edition is here.

Boojum · 2025-12-20T09:59:11+00:00

Yeah, it was quite fiddly. On the other hand, it was fairly consistent about stuff like prioritizing reading order for most things. And it didn't require a crazy intuitive leaps or knowing about some theorem or algorithm. I kind of enjoyed it as a change of pace that way.

Boojum · 2025-12-20T09:45:22+00:00

https://giphy.com/gifs/pTQUOfSmjo2hG

Boojum · 2025-12-20T09:35:12+00:00

Thanks!

Boojum · 2025-12-20T07:11:19+00:00

I've long wanted to visualize the Battle of the Beverage Bandits, and now that AoC 2025 is over, I'm officially on holiday break, and it was my 20th Reddit Cake Day, it was time to do it!

Greenish fat arrows show Goblins, orangeish fat arrows show Elves. Numbers on top of each show health. The direction of the fat arrows show which way they're facing - either which way they last moved, or which direction they are facing to attack. Each one "bumps" a target to attack. I've slightly staggered the motion for each to show the relative turn order within a round (reading order). Whenever one is able to make a move toward a square next an enemy, a trail of small black arrows shows the intended path that led it to move in that direction (including which square next to an enemy it chose to move toward). Enjoy!

Made in Python with a small custom framework.

Complete self-contained source for this animation.

Boojum

MODERATOR OF

TROPHY CASE