Now, this puzzle had an interesting optimisation.
You are given a representation of an arena full of blizzards with the arrows indicating the direction of each blizzard:
#.#################################### #><^.^>v^<><^<>>>^<>><>v>^v<^>>^v<>>.# #>>v^^v^><.<<.^v<v>.><>^<<>^v^<vvv><v# #>>^<^>^^<<>^<<^v^^v^<<<^.<<^v><>.vvv# #>v<v^v<.>^.><<<<v>vv^^<^>v<^^^<<v<<v# #>>^<v>.<^<v>^<v.^^.v<v>>v>.>>.>v^<<<# #<^^^v<<v<.<^.^<<^>^>>><v^^.^v<v^^.vv# #<<v<^^v>^>v><v>v^<<.^vv><>v^v<vv<vvv# #<<<v>^^<^<^v.><>^vv><^>v.v<>.<vv.>><# ####################################.#
You must navigate though the storm from the origin (top left) to the exit (bottom right). Each turn, the blizzards move and you may move. So you essentially want a path-finding algorithm but have to deal with moving obstacles. The illustration in the puzzle shows the interactions.
So, I used A* while updating the position of each storm with every step the pathfinder takes.
If you know how path-finding algorithms are generally implemented, you'll know that the state of the storm has to be copied and held many times to be processed in the queue that the algorithm is working through.
This involves a lot of memory allocation, copying, GC intervention and, updating the position of each storm on every cycle also. So, my initial implementation worked fine and gave the correct answers, but took ~10s for part 1 and ~30s for part 2.
This not only well exceeded the 15 seconds on ten-year-old hardware claim, but also put a big thorn in my Σ < 1s personal challenge.
The Optimisation
The win here is to not have to copy all that state around, and also not to have to move every storm for each step the path-finding algorithm takes.
Fortunately with this puzzle, this is entirely possible.
Since the blizzards' movements are entirely predictable, we can calculate where a particular one will be after 𝑥 cycles of the simulation.
Also, we only need to know at any point whether the expedition can move up, down, left or right.
Consider the following state of the simulation...
#.####################################
#><^.^>v^<><^<>>>^<>><>v>^v<^>>^v<>>.#
#>>v^^v^><.<<.^v<v>.><>^<<>^v^<vvv><v#
#>>^<^>^^<<>^<<^v^^v^<<<^E<<^v><>.vvv#
#>v<v^v<.>^.><<<<v>vv^^<^>v<^^^<<v<<v#
#>>^<v>.<^<v>^<v.^^.v<v>>v>.>>.>v^<<<#
#<^^^v<<v<.<^.^<<^>^>>><v^^.^v<v^^.vv#
#<<v<^^v>^>v><v>v^<<.^vv><>v^v<vv<vvv#
#<<<v>^^<^<^v.><>^vv><^>v.v<>.<vv.>><#
####################################.#
To evaluate the next move, we need to know whether the expedition can move up, down, left or right after the storms have moved one step. So, we care about whether the following locations will be empty after the storms have moved:
#.#################################### #><^.^>v^<><^<>>>^<>><>v>^v<^>>^v<>>.# #>>v^^v^><.<<.^v<v>.><>^<<>^v^<vvv><v# #>>^<^>^^<<>^<<^v^^v^<<<^E<<^v><>.vvv# #>v<v^v<.>^.><<<<v>vv^^<^>v<^^^<<v<<v# #>>^<v>.<^<v>^<v.^^.v<v>>v>.>>.>v^<<<# #<^^^v<<v<.<^.^<<^>^>>><v^^.^v<v^^.vv# #<<v<^^v>^>v><v>v^<<.^vv><>v^v<vv<vvv# #<<<v>^^<^<^v.><>^vv><^>v.v<>.<vv.>><# ####################################.#
Therefore we only need to worry about the position of these blizzards during the next execution cycle, since they are the only ones that can move into blocking positions...
#.#################################### #><^.^>v^<><^<>>>^<>><>v>^v<^>>^v<>>.# #>>v^^v^><.<<.^v<v>.><>^<<>^v^<vvv><v# #>>^<^>^^<<>^<<^v^^v^<<<^E<<^v><>.vvv# #>v<v^v<.>^.><<<<v>vv^^<^>v<^^^<<v<<v# #>>^<v>.<^<v>^<v.^^.v<v>>v>.>>.>v^<<<# #<^^^v<<v<.<^.^<<^>^>>><v^^.^v<v^^.vv# #<<v<^^v>^>v><v>v^<<.^vv><>v^v<vv<vvv# #<<<v>^^<^<^v.><>^vv><^>v.v<>.<vv.>><# ####################################.#
Not only have we removed the need to update all the blizzards every cycle, we have also reduced how many blizzards we need to compute the current position of.
During parsing of the input, I add blizzards to HashSet<T>s containing their initial position. One hashset for each blizzard direction.
This makes it very easy to just pull out, say, left blizzards on row 𝑦 or down blizzards on column 𝑥.
Removing blizzards we don't care about from the board, it looks like this...
# ####################################
# ^ #
# < > #
# < E < #
# ^ v #
# v #
# #
# #
# #
#################################### #
We can pass cycle + 1 to IsOccupied and it will determine the positions of the blizzards after that cycle and return true or false depending on whether a point on the board contains a blizzard.
After a cycle, the state will look like this:
# ####################################
# #
# < > #
# < ^E< #
# #
# v #
# v #
# #
# ^ #
#################################### #
We can see blizzards have moved to block our left and right moves, but up and down are available to be passed as options to the path-finding algorithm.
Pass the IsOccupied method any cycle number and coordinate and it will be able to tell you whether a cell is occupied by a blizzard during that cycle. The computation does not get more expensive as the cycle number grows.
A further final note, in performing this check, I actually move the position of the expedition in relation to the blizzards by the number of cycles. This means only performing the maths on the expedition's position and simply checking it against the blizzards' original coordinates, rather than vice-versa which would be more expensive.