Advent of Code (in MiniScript), Day 12
Tags: miniscript, adventofcode, programming
Published: 2022-12-12 16:47:50

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20#adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  For [day 12](https://adventofcode.com/2022/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](https://github.com/JoeStrout/Farmtronics).  But instead I found [this script](https://github.com/shellrider-games/Starfarer/blob/main/user/src/pathfinding.ms) 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.

{% spoiler 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
```
{% endspoiler %}

## 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](https://github.com/JoeStrout/minimicro-sysdisk/blob/master/sys/lib/qa.ms) 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](https://en.wikipedia.org/wiki/15_puzzle) to [N-queens](https://en.wikipedia.org/wiki/Eight_queens_puzzle) to [word ladders](https://en.wikipedia.org/wiki/Word_ladder).  With 13 challenges still to go this year, I'll be surprised if something like that doesn't come up!