Welcome back to my series of Advent of Code solutions in MiniScript! For day 12, we have to find a path in a varied terrain. From any point on the terrain, you can only step to neighboring points no more than 1 unit higher than your current point.

So this is a classic path-finding problem, for which A* (also known as best-first search) is the standard solution. I know I've written that a few times in the past, but I didn't have a standard library for it just sitting around. I searched my hard drive for file names containing "path" and ".ms", expecting to find a path-finding module I seem to recall writing for Farmtronics. But instead I found this script from a half-written space trader game called Starfarer.

The script was reasonably clean, though it referenced a "ship" object that obviously doesn't apply in this case. The main thing it was used for was a walkableNeighbors function, which figures out which neighbors can be reached from a given location.

So I copied the findPath function into my working script, and wrote a new walkableNeighbors function based on the data read from the file.

After clean-up, the final code for Part A is:

import "listUtil"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.remove -1

H = lines.len
W = lines[0].len

for y in lines.indexes
    line = lines[y]
    for x in range(0,W-1)
        if line[x] == "S" then startPos = [x,y]
        if line[x] == "E" then endPos = [x,y]
    end for
    lines[y] = line.replace("E", "z").replace("S", "a")
end for
pprint lines
print "Start: " + startPos
print "End: " + endPos

height = function(pos)
    return lines[pos[1]][pos[0]].code - 97
end function
walkableNeighbors = function(pos)
    h = height(pos)
    result = []
    if pos[0] > 0 and height([pos[0]-1, pos[1]]) <= h+1 then result.push [pos[0]-1, pos[1]]
    if pos[1] > 0 and height([pos[0], pos[1]-1]) <= h+1 then result.push [pos[0], pos[1]-1]
    if pos[0] < W-1 and height([pos[0]+1, pos[1]]) <= h+1 then result.push [pos[0]+1, pos[1]]
    if pos[1] < H-1 and height([pos[0], pos[1]+1]) <= h+1 then result.push [pos[0], pos[1]+1]
    return result
end function

findPath = function(startPos, endPos)
    // A* + Heuristics pathfinding implementation
    if startPos isa map then startPos = [startPos.col,startPos.row]
    if endPos isa map then endPos = [endPos.col,endPos.row]
    if startPos == endPos then return [endPos]

    // True distance function for diagnonals
    heuristic = function(endPos, nextPos)
        a = endPos[0] - nextPos[0]
        b = endPos[1] - nextPos[1]
        return sqrt(a^2 + b^2)
    end function

    check = []
    check.push [startPos,0]
    globals.camefrom = {}
    camefrom[startPos] = null
    cellCosts = {}
    cellCosts[startPos] = 0
    while check
        current = check.pull[0]
        if current == endPos then
            print "SUCCESS!"
            break
        end if

        for nextCellPos in walkableNeighbors(current)
            cost = cellCosts[current] + heuristic(nextCellPos, current)
            if not cellCosts.hasIndex(nextCellPos) or cost < cellCosts[nextCellPos] then
                cellCosts[nextCellPos] = cost
                i = 0
                while i < check.len
                    if check[i][1] > cost then break
                    i = i + 1
                end while
                check.insert i, [nextCellPos, cost]
                camefrom[nextCellPos] = current
            end if
        end for
    end while

    current = endPos
    result = []
    if camefrom.hasIndex(current) then
        while current != startPos
            result.push current
            current = camefrom[current]
        end while
        if result then result.reverse
    end if
    return result
end function

path = findPath(startPos, endPos)
print path
print "path len: " + path.len

Unfortunately, it wasn't as easy as I just made it sound. The first time I tried it, it didn't work. It took 10 minutes of debugging to notice that the original findPath method took three parameters, including the ship object, which came first. This was failing in a rather unobvious way, and I checked a lot of other possible failures before catching this one. Oops.

Part B

In the second part of the challenge, we use the same end position, but now have to report the shortest path to any starting position at the lowest terrain elevation.

The proper way to do this would be a breadth-first search, starting at the end point and working backwards. Or, you could do a sort of flood-fill, where you keep (in a separate 2D array) the distance from each point to the goal, and for any unknown point, set its distance to one plus the smallest of its reachable neighbors.

But I didn't want to spend the time to code (or dig up) a different search algorithm. So I took the easy way out: I first make a list of all possible starting points, then find a path for each of those to the goal and throw the path length onto a list. Finally, at the end I use list.min to report the shortest such length.

import "listUtil"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.remove -1

H = lines.len
W = lines[0].len

resultB = []
startPositions = []

for y in lines.indexes
    line = lines[y]
    for x in range(0,W-1)
        if line[x] == "S" or line[x] == "a" then startPositions.push [x,y]
        if line[x] == "E" then endPos = [x,y]
    end for
    lines[y] = line.replace("E", "z").replace("S", "a")
end for
pprint lines
print "Start: " + startPos
print "End: " + endPos


height = function(pos)
    return lines[pos[1]][pos[0]].code - 97
end function
walkableNeighbors = function(pos)
    h = height(pos)
    result = []
    if pos[0] > 0 and height([pos[0]-1, pos[1]]) <= h+1 then result.push [pos[0]-1, pos[1]]
    if pos[1] > 0 and height([pos[0], pos[1]-1]) <= h+1 then result.push [pos[0], pos[1]-1]
    if pos[0] < W-1 and height([pos[0]+1, pos[1]]) <= h+1 then result.push [pos[0]+1, pos[1]]
    if pos[1] < H-1 and height([pos[0], pos[1]+1]) <= h+1 then result.push [pos[0], pos[1]+1]
    return result
end function

findPath = function(startPos, endPos)
    // A* + Heuristics pathfinding implementation
    if startPos isa map then startPos = [startPos.col,startPos.row]
    if endPos isa map then endPos = [endPos.col,endPos.row]
    if startPos == endPos then return [endPos]

    // True distance function for diagnonals
    heuristic = function(endPos, nextPos)
        a = endPos[0] - nextPos[0]
        b = endPos[1] - nextPos[1]
        return sqrt(a^2 + b^2)
    end function

    check = []
    check.push [startPos,0]
    globals.camefrom = {}
    camefrom[startPos] = null
    cellCosts = {}
    cellCosts[startPos] = 0
    while check
        current = check.pull[0]
        if current == endPos then
            break
        end if

        for nextCellPos in walkableNeighbors(current)
            cost = cellCosts[current] + heuristic(nextCellPos, current)
            if not cellCosts.hasIndex(nextCellPos) or cost < cellCosts[nextCellPos] then
                cellCosts[nextCellPos] = cost
                i = 0
                while i < check.len
                    if check[i][1] > cost then break
                    i = i + 1
                end while
                check.insert i, [nextCellPos, cost]
                camefrom[nextCellPos] = current
            end if
        end for
    end while

    current = endPos
    result = []
    if camefrom.hasIndex(current) then
        while current != startPos
            result.push current
            current = camefrom[current]
        end while
        if result then result.reverse
    end if
    return result
end function

for startPos in startPositions
    path = findPath(startPos, endPos)
    print "path len from " + startPos + ": " + path.len
    if path.len > 0 then resultB.push path.len
end for

print "Min: " + resultB.min

Results and Final Thoughts

Because of all that debugging, Part 1 took 22 minutes, placing me 1250th in the competition. Part 2 went much better, with a combined time of almost 26 minutes, but my rank only improved to 1168.

One lesson learned is that I should always validate my function inputs. Had my findPath function simply checked that it was being passed two 2-element lists, I would have caught my error right away and fared much better. Grabbing code from somewhere else is no excuse; the first thing I should have done is examined the parameters, and added a quick qa.assert to me sure I call it correctly.

I also realize now that I should probably have a clean, ready-to-use general purpose search algorithm ready to go. Give it something that represents the state, a function to find neighboring states, and an optional heuristic function, and it'll find the best path from start state to end state. This will be useful for all sorts of problems, from 15-puzzle to N-queens to word ladders. With 13 challenges still to go this year, I'll be surprised if something like that doesn't come up!