Part 1 is another breadth-first search algorithm for the win. I wasted too much time getting the blizzard logic wrong. I knew what to do; I just kept getting the math wrong! I did at least have the presence of mind to separate the blizzard state from the expedition state, though I didn’t realize that there’s no need to cache the blizzard..
Part 2 was also pretty straightforward, once Part 1 is done. Interesting that the result is not three times the value of Part 1, but not especially surprising, given how the blizzards move around.
Glancing over at the Reddit Solutions Megathread, some commenters have noticed that the blizzards repeat after lcm(w,h) minutes, where w and h are the width and height of the valley (not including the walls), but it’s apparently useless to try and exploit it. (It certainly would be in my case.)
Spent an embarrassing amount of time tuning the Dijkstra algorithm for this space-time problem. Perhaps I should stop trying to build everything with HAC and use elegant generic containers instead. Or, implement generics in the HAC compiler .
Anyway, if you remember that time is just another dimension, all is fine.
I have implemented the blizzards as (to give you a “real world” image) four different transparent superposed sheets (one with the leftward blizzards, on with the rightward, etc.) whose movements can be tracked by subtracting the time t and which are made periodic via modulo arithmetic.
The blizzard data is set when reading the input and never changed, nor duplicated later!
The test for determining a blizzard-free cell (x, y, t) becomes:
not (leftward_blizzard ((x + t) mod (highest.x + 1), y)
or else rightward_blizzard ((x - t) mod (highest.x + 1), y)
or else upward_blizzard (x, (y + t) mod (highest.y + 1))
or else downward_blizzard (x, (y - t) mod (highest.y + 1)))
Total run time: 0.12 second with GNAT (could be probably less if the sorting for Dijkstra’s algorithm was not by insertion).
I saw several comments to this effect in that Reddit thread I mentioned, and I didn’t quite understand what it meant. Does it just mean that you need to include time in the stored state of explored positions? (depending on algorithm)
If so, maybe I’m finally getting the hang of this breadth-first search business, as it somehow felt natural to do that. I didn’t even think about it.
I also notice that you used mod, while I used rem. I really need to look into the difference between those, as I think it contributed to my issues with the logic.
I forgot to mention this after looking at that Reddit megathread of solutions: a number of people left comments to the effect that they had neglected to set up their logic in such a way as to avoid moving to the goal around the walls, rather than through the valley.
It doesn’t even seem worth blurring as a spoiler here, because if you use Ada’s ranges to define the map boundaries – something I’ve been doing throughout this competition – then at the very least you’ll be thinking about these things, and even if you slip up, the runtime calls a foul when you exceed the range. For all the issues I had, at least I didn’t waste time on that!
I could reuse a lot of Day 19 for the breadth first search.
Although, I replaced the Queues with Vectors for part 2, because you can’t seem to clear an existing Queue.
From the beginning, I exploited the fact that the blizzards cycle. So I calculate all possible map states of the blizzards, and then I can simply use (Step_Count mod All_Maps.Length) as index to my 0-based vector to get the blizzard map for the step.
At first, I implemented that you couldn’t move “through” a blizzard, i.e. moving like this: E< → <E - but after studying the requirements again, it never said this was forbidden. After loosening my logic, I got the correct results.
Another tricky part is that you can’t stand still while a blizzard is moving onto your tile.
For the map data type, I simply use a 2d array of record containing and array of Booleans to indicate if there is a blizzard on the tile that is moving into the given direction.
I expected something else for part 2, like blizzards changing direction when hitting a wall, or two opposing blizzards eliminating each other if they clash together…
I just duplicated a little code for part B. For part A, I defined a 2-D array of boolean with enough rows and columns to represent the map. I also made an array of blizzards that has the blizzard’s current position and direction. For each turn, I set booleans in a grid to true for each position a blizzard is in, and then compute the blizzard positions for the following turn. I also have a grid of booleans representing all the places I could have been at the end of the previous turn. I compute a new grid of where I could be, by setting bits in a new grid to true if there is no blizzard there, and it is adjacent to a place I could have been last turn. Also, each turn if there isn’t a blizzard there, I set the bit for the square next to the entrance to represent the case that I just stayed at the entrance all this time and just now decided to enter. Then I just keep doing this until I set the bit adjacent to the entrance.
My first visualization was 15-16MB, because I rescaled it to something that lets you see what’s going on. That’s too large, though! and GIMP’s Optimize (for GIF) made the file size worse this time!
So here’s the original, unscaled animation, roughly 1MB, again hidden in case anyone has issues with dots moving around:
Legend
Black: walls
White: empty space
3: Green: expedition
Shades of gray: blizzards
Suggestions on viewing
Load it into a browser and scale it up.
Firefox interpolates to “improve” the image. In this case it makes the image worse.
Konqueror does not interpolate, so you get a very good view.
Konqueror is built on WebKit, so maybe Chrome and Safari will likewise not interpolate.
Load it into Gimp or some other capable program. Scale the image up 800% or more. Then export it anew as a gif. You’ll get a 16MB gif, or larger.
** Observations**
With my input:
The expedition stays put for several minutes before stepping out into the valley. I didn’t expect that.
I saw another visualization where someone remained at the opposite end of the valley a few minutes before beginning the return trip, but mine seems to set off right away.
Once the expedition makes it back to the beginning, mine stays put a few minutes again.
The blizzards can be a little hard to follow.
Blizzards moving up seem to be the easiest, perhaps because they’re darkest.
Blizzards moving in other directions can be identified, but it’s often easiest to view clumps of them moving in the appropriate direction.
I’ve seen some text-based animations that work well, so you may want to look up Advent of Code 2022 Day 24 visualization. Some of them are really nice.
On my input data, only around 47% of cell visits are first visits and 53% land into the same location and the same time modulo the blizzard cycle. I have implemented that in order to give a limit in time: perhaps on some data the queue is jammed by pathes that dont move a lot location-wise, but go through the same location and (time modulo the blizzard cycle) many times.
Anyway, the author was kind enough to limit strongly the number of possible pathes while ensuring there is a solution — must have been fun to generate such data!
.
and GIMP’s 
