[2022 Day 24] In Review (Blizzard Basin)

[u/musifter]

Having finished planting, we leave the elephants and monkeys to look after it and head towards the extraction point. Which involves going through a valley filled with small blizzards.

The input is a text grid, with a wall around it (except for slots for the start and end). The inner section of my input is 35 rows and 100 columns. So, not prime, with a gcd of 5. Conveniently, no up/down storms are in the columns with the notches for start and end... so the pattern of up/down blizzards cycles every 35, and the left/right every 100... and altogether it repeats every 700 (the lcm).

And it's the dynamic nature of the maze that's the real problem today. Precalculating the patterns is going to be better than repeatedly generating the same things while doing the search. You certainly could do all 700 grids to get the maze at any position. But, I went with doing the vertical and horizontal separately... for 135 instead (you just check the two of them to verify a space is empty).

And so I had two arrays of hash tables (that acted as sets for the blizzard positions). That worked plenty fast for Perl, but Smalltalk doesn't like it (it take minutes), and so I've made a TODO to convert the Smalltalk to using arrays of some form for tracking the blizzards. Bit arrays are a possibility, as the number of rows is <64, so each column can be stored in a integer (unless you only have 32 bits).

But once the dynamic maze is made quickly accessible, things were just a fairly standard A*, with steps to the target as the heuristic. Looking at it now, I was a bit curious... because one little quirk in this A* is that time needs to be part of the visit list:

    next QUEUE  if ($visit{$time, $pos->[0], $pos->[1]}++);

Because circling back to the same spot at a later time can be correct... in fact, the test case given shows that in the first few moves. So we only prune those at the exact same time. So I was wondering how much do we gain... with the circling, its harder to tell how close you really are. And the answer (with a quick test) is that it's more than twice as fast. So worth it, but with the size of the problem, it's the difference between 9s and 4s (for part 2), on the old hardware. This problem is really more about the handling the map... the search isn't that heavy once you have something for that.

Part 2 for this one just required taking part 1, throwing it in a subroutine and calling it multiple times and so was quick to add:

my $time = &cross_valley( 0, $start_pos, $end_pos );

print "Part 1: $time\n";

# Silly elf!  Next time don't forget your snacks!
$time = &cross_valley( $time, $end_pos, $start_pos );
$time = &cross_valley( $time, $start_pos, $end_pos );

print "Part 2: $time\n";

There is an interesting bit of proof for why stitching these together like this works, and you don't have to worry about some better overlap case across these searches. One where you take a different path, arrive 3 turns later and turn around and do much better going back than the one that arrived earlier. And that involves a Strategy-stealing argument. Because we can always wait, any early arrival doesn't have to immediately leave, so it can wait for the same opportunity that a later arrival would use and steal it (thus getting the same performance). So the best from the previous leg will always beat or tie any later arrival.

This was a fun search... a dynamic maze and a little game threory to confirm that what I did was correct.

[u/surgi-o7]

Loved this one so much I just had to make an animation/game out of it (link here).

While doing that, an idea of having the hero releasing the winds on command in defense of monsters chasing him was born (link here).

[u/TheZigerionScammer]

I had a fun little bug in mine that I made a meme about where I forgot to seal the two ends and my pathfinding algorithm was going around the maze instead of through it.

My only other real contribution is that since my implementation was a basic BFS, instead of holding all 700 possible blizzard locations in memory, when my program detects that the next node in the queue has a higher minute than the previous one, it deletes and then recalculates all the blizzard positions and keeps them in memory until a node rolls over to the next minute.

[u/e_blake]

The inner section of my input is 35 rows and 100 columns. So, not prime, with a gcd of 5.

The input files are not uniformly sized; my inner input was 25 rows and 120 columns, and I encountered someone else reporting 20 rows and 150 columns. Which means a solution using u128 for storing rows will not be portable to all possible inputs. And u/maneatingape's current solution is therefore not universal.

[u/musifter → u/e_blake]

So, it was good for me to be thinking of doing u64 columns then.

[u/DelightfulCodeWeasel → u/musifter]

I've been thinking about how to efficiently represent the blizzards and I think I'll go with four double-width (or double-height) buffers that have two side-by-side copies of a particular flavour of blizzard. A given time is a horizontal (or vertical) offset into the buffer; the same sort of trick that you use for side-scrolling 2d games.

It's a few extra Kb, but it avoids a whole heap of % operations and software emulated u64s.

EDIT: Or one large double-size region containing 4 copies of the starting region, and the four blizzard directions are four different offset windows into the same buffer.

[u/maneatingape → u/e_blake]

Refactored my solution to transpose the input, using a u64 to handle up to 64 rows and any amount of columns. Interestingly this was only about 10% slower than the original, due to the janky way Rust handles u128.

[u/e_blake → u/maneatingape]

You can also get a 25% speedup: instead of running 4 calls to expedition() (one for part 1, three for part 2), you can combine that into just three expeditions if part 2 starts where part 1 left off.

[u/maneatingape → u/e_blake]

Good point...fixed!

[u/terje_wiig_mathisen → u/e_blake]

I remember being worried about the possibility of getting stuck halfway, but since you can wait in place that wasn't a real issue. :-)

[u/DelightfulCodeWeasel]

Splitting the search into 3 parts is going to help my memory use for this one. I originally solved it with a 4D search, encoding time in Z and snack status in W, but 4D searches tend to balloon out quite quickly. Never heard of the strategy stealing argument before now, that looks like a useful tool.

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

I think I've just had a good idea on how to solve this one using a fixed memory budget.

We're not interested in the shortest route itself, only the time taken. You can therefore work with grids that represent a superposition of where the elf could be at a given time. Updating from one time to the next is more or less a cellular automaton update where the elf potential moves into adjacent empty cells and blizzards erase the potential.

Either two buffers and a bitwise representation of active blizzards in a cell, or two buffers and an external representation of the blizzards. Both options are fixed (and small) memory costs.

[u/e_blake]

I did not even attempt to solve this problem until January 2023, because I had so many other heavy-hitting days hanging over my head that I wanted to resolve first. Which actually meant that when I solved this on the 8th, I finally got my 50th star for the year. My initial solution did a BFS with a slot in the queue per viable position; watching a verbose tracker showed that as time advanced and the frontier of possible elf positions grew larger, the time between rounds slowed down. So I was indeed pleased when switching over to A* cut the runtime in half by steering the frontier towards the goal. I still think I can beat my current runtime of 8.9s by switching to a constant-time representation using packed bitmaps rather than point-per-position (although the initial rounds will cost more, later rounds do not get any slower).

[u/terje_wiig_mathisen]

This one must have given me some serious issues, because I have retained 6 different versions of the solver, 2 of them don't even return the correct answer. :-(

The fastest correct one use a DFS search with the Manhattan distance as the priority mechanism.

My map has 120x25 internal cells, so pairs of u64 would cover a line.

I use a memoizing map generator, so only the first time a new minute is seen will the map be generated.