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.
The code is almost the same as for part 1, but here it is if you want to see it anyway.
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!
Top comments (0)