Advent of Code (in MiniScript), Day 24

Welcome back to my series of Advent of Code solutions in MiniScript! Day 24 was a classic path-finding problem, but with a twist: the obstacles move on every step.

To tackle this, I decided that my "state" would be a three-element list containing X position, Y position, and the time (i.e. how many steps we are from the start). Using the time, I can calculate what the obstacle map looks like, and use that to figure out which neighboring steps are valid.

(This required a minor modification of my search module: I can't know ahead of time what the end state will be, because I don't know how many steps it takes to get there. So I had to detect success by looking at only the X and Y values, ignoring the time.)

The obstacles in this challenge are called "blizzards," and each one moves in a straight line in one of the four directions, wrapping around when it reaches the edges of the map. Blizzards can overlap and pass through each other. So I chose to represent the map using a 2D array of integers, with a value for each direction of blizzard: 1 for east-moving blizzards, 2 for blizzards moving south, 4 for west, and 8 for north. This way, the sum uniquely identifies the combination of blizzards in any cell, and I can break a sum into individual blizzards using bitAnd.

So, one key bit of this solution is the function that returns the map for any point in time. It looks like this:

blizMapForMinute = function(minute)
    if _blizMapForMinute.hasIndex(minute) then return _blizMapForMinute[minute]
    m = newBlizMap
    p = blizMapForMinute(minute - 1)
    for y in range(0, mapH-1)
        for x in range(0, mapW-1)
            sum = 0
            if bitAnd(p[y][(x+mapW-1)%mapW], 1) then sum = sum + 1
            if bitAnd(p[(y+mapH-1)%mapH][x], 2) then sum = sum + 2
            if bitAnd(p[y][(x+1)%mapW], 4) then sum = sum + 4
            if bitAnd(p[(y+1)%mapH][x], 8) then sum = sum + 8
            m[y][x] = sum
        end for
    end for 
    _blizMapForMinute[minute] = m
    return m
end function

It relies on a _blizMapForMinute map, which stores a map for each minute; this way, we never have to compute that more than once. So the first thing this function does is check whether we've already computed it, and if so, just return that previous result.

Otherwise, it calls itself to get the map for the previous minute, and then zips through, looks at the neighbors of each cell, and adds up the corresponding numbers.

With that in hand, and the (slightly modified) search module I created after Day 12, all I had to do was set up a best-first search.

pathFinder = new search.Search
pathFinder.heuristic = @search.heuristic2DDistance
pathFinder.neighbors = function(state)
    result = {}
    x = state[0]; y = state[1]
    nextMinute = state[-1] + 1
    // wait (if clear of blizzard)
    m = blizMapForMinute(nextMinute)
    if y < 0 or y >= mapH or not m[y][x] then result.push [x, y, nextMinute]
    // move in each direction, but only if clear of blizzards
    if y < mapH-1 and not m[y+1][x] then result.push [x, y+1, nextMinute]
    if y > 0 and not m[y-1][x] then result.push [x, y-1, nextMinute]
    if y < 0 or y >= mapH then return result
    if x > 0 and not m[y][x-1] then result.push [x-1, y, nextMinute]
    if x < mapW-1 and not m[y][x+1] then result.push [x+1, y, nextMinute]
    return result
end function

As you can see above, this involves (1) creating a new Search object; (2) assigning the heuristic, which in this case is standard 2D distance; and (3) defining the neighbors of any given state, which in this case relies on that blizMapForMinute function we defined before.

I did have two bugs, both in this neighbors function. First, I had an off-by-one error that did not let my poor searcher reach the right-most column or bottom-most row of the map. Which, by the way, is exactly where the goal is. At first I thought the search was taking a long time, but I didn't have any progress output (another mistake, in retrospect), so I waited much too long before giving up and finding my error.

The other bug was that I failed to appreciate that the elves can't stay where they are if a blizzard is about to move into that cell on the next step. Leaving out that rule caused it to find an invalid solution.

However, with both of those bugs finally fixed, it cranked through the problem and found a great solution. As usual, I went back today and added some visualization code, so you can see what it does:

import "stringUtil"
import "mapUtil"
import "listUtil"
import "mathUtil"
import "aoc"
import "search"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if lines == null then
    print "Unable to read: " + fname
    exit
end if
if not lines[-1] then lines.pop

mapW = lines[0].len-2
mapH = lines.len-2
print mapW + "x" + mapH

// State: [x,y,minute]

// blizzardMap: represents which blizzards are at each spot
// with a sum of 1, 2, 4, 8 for >, v, <, and ^ respectively.
// Indexed as [y][x], INTERIOR only.
newBlizMap = function
    return list.init2d(mapH, mapW, 0)
end function

_blizMapForMinute = {}

// load the initial blizzard map from the data
m = newBlizMap
for y in range(0, mapH-1)
    for x in range(0, mapW-1)
        c = lines[y+1][x+1]
        if c == "." then continue
        if c == ">" then m[y][x] = 1
        if c == "v" then m[y][x] = 2
        if c == "<" then m[y][x] = 4
        if c == "^" then m[y][x] = 8
    end for
end for
_blizMapForMinute[0] = m

blizMapForMinute = function(minute)
    if _blizMapForMinute.hasIndex(minute) then return _blizMapForMinute[minute]
    m = newBlizMap
    p = blizMapForMinute(minute - 1)
    for y in range(0, mapH-1)
        for x in range(0, mapW-1)
            sum = 0
            if bitAnd(p[y][(x+mapW-1)%mapW], 1) then sum = sum + 1
            if bitAnd(p[(y+mapH-1)%mapH][x], 2) then sum = sum + 2
            if bitAnd(p[y][(x+1)%mapW], 4) then sum = sum + 4
            if bitAnd(p[(y+1)%mapH][x], 8) then sum = sum + 8
            m[y][x] = sum
        end for
    end for 
    _blizMapForMinute[minute] = m
    return m
end function

pathFinder = new search.Search
pathFinder.heuristic = @search.heuristic2DDistance
pathFinder.neighbors = function(state)
    result = {}
    x = state[0]; y = state[1]
    nextMinute = state[-1] + 1
    // wait (if clear of blizzard)
    m = blizMapForMinute(nextMinute)
    if y < 0 or y >= mapH or not m[y][x] then result.push [x, y, nextMinute]
    // move in each direction, but only if clear of blizzards
    if y < mapH-1 and not m[y+1][x] then result.push [x, y+1, nextMinute]
    if y > 0 and not m[y-1][x] then result.push [x, y-1, nextMinute]
    if y < 0 or y >= mapH then return result
    if x > 0 and not m[y][x-1] then result.push [x-1, y, nextMinute]
    if x < mapW-1 and not m[y][x+1] then result.push [x+1, y, nextMinute]
    return result
end function

goal = [mapW-1, mapH-1]
path = pathFinder.findPath([0, -1, 0], goal)
minutes = path[-1][-1] + 1
print "Time to goal: " + minutes

Part Two

Part 2 of this challenge was a trivial addition to part 1, at least the way I had done it. We just need to calculate the optimal time to get from the start to the goal, then back to the start, then back to the goal again. (Apparently the elves forgot something and had to go back for it.) So the main program simply changed to:

// go to goal
goal = [mapW-1, mapH-1]
path = pathFinder.findPath([0, -1, 0], goal)
minutes = path[-1][-1] + 1
print "From start to goal: " + minutes

// go back to start
goal = [0, 0]
path = pathFinder.findPath([mapW-1, mapH, minutes], goal)
minutes = path[-1][-1] + 1
print "Back to start: " + minutes

// and back to goal
goal = [mapW-1, mapH-1]
path = pathFinder.findPath([0, -1, minutes], goal)
minutes = path[-1][-1] + 1
print "Back to goal again: " + minutes

Incidentally, the + 1 on each of the minutes calculations is because I'm actually only path-finding to the corner spot next to the goal; it takes one more step to actually step into the goal spot. I do this to simplify the neighbors method, as I can disallow any out-of-bounds motion and not make a special case for the exit point.

Results and Conclusions

Because of those two bugs, Part 1 took me an hour and 15 minutes, for a rank of 1408; with Part 2, it came to an hour and a half, and a rank of 1393.

Bugs happen, and my off-by-one error, which seems so obvious this morning, is just the sort of thing a tired brain does sometimes. Same for the neglected rule detail, for that matter. I don't really see any way better preparation could have avoided those.

However, I do now see how valuable it is to have progress feedback during a search. I'm going to update my search module with two new features:

1. An optional method to detect success. This will default to curState == endState, but when you need to do something fancier (as in this case), there will be a clean and simple way to do that.

2. An option to get progress feedback, for example, a function invoked whenever we have a new best estimated distance to the goal.

Having these would have saved some implementation time last night, and the second one might have helped me discover the bugs faster -- at the very least, it would have made me realize sooner that something was actually wrong, rather than the search just taking a long time.

And that's it for day 24. Only one more day to go! What a fun adventure it's been. I can't wait to see what the last challenge is tonight!