Advent of Code (in MiniScript), Day 22
Tags: miniscript, adventofcode, programming
Published: 2022-12-22 17:15:59

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  [Day 22](https://adventofcode.com/2022/day/22) was an interesting one.  Part 1 was relatively easy, but Part 2 was troublesome — not conceptually difficult or performance-intensive, but easy to mess up and hard to debug.

First, Part 1.  We are given an ASCII map that contains places you can walk and places that are blocked, and a series of instructions to either move forward so-many spaces, or turn left/right.  If, while moving forward, you go off the edge of the walkable area, you are to wrap around to the other side of the map (and advance to the nearest walkable spot).

I used `file.readLines` to read the map into a list of strings, and just pulled off the last couple of lines for my instructions (and discarded the extra blank line).  I chose to represent my position on the map as an [x,y] list.  To make the rest of the code easier, I added a `gridAt` function that looks up the contents of the map, given such a position:

```
gridAt = function(pos)
	if pos[1] < 0 or pos[1] >= grid.len then return " "
	line = grid[pos[1]]
	if pos[0] < 0 or pos[0] >= line.len then return " "
	return line[pos[0]]
end function
```

This function does bounds-checking, returning the space character (the same thing used in the ASCII map to indicate off-map areas) when out of bounds, so the rest of my code doesn't need to worry about it.

I also need to represent directions; I keep these as a simple number, as given in the instructions, but defined a `dpos` list with the values to add to a position for a movement in each of the four directions.

```
dir = 0		// 0-3 = right, down, left, up
dpos = [[1,0], [0,1], [-1,0], [0,-1]]
```

With that, the rest was just looping over the instructions, alternately moving forward (with wrap-around, and watching out for "#" obstacles) and turning as directed.

Here's the complete program for Part 1.
```
import "mapUtil"
import "aoc"
import "qa"

resultA = []
resultB = []

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

instruction = grid.pop
grid.pop

//pprint grid

gridAt = function(pos)
	if pos[1] < 0 or pos[1] >= grid.len then return " "
	line = grid[pos[1]]
	if pos[0] < 0 or pos[0] >= line.len then return " "
	return line[pos[0]]
end function

pos = [0,0]	// column, row
dir = 0		// 0-3 = right, down, left, up
dpos = [[1,0], [0,1], [-1,0], [0,-1]]

advanceToMap = function(pos)
	while gridAt(pos) == " "
		pos.add dpos[dir]
	end while
end function
advanceToMap pos
print "Starting pos: " + pos

i = 0
while i < instruction.len
	// get a number
	d = instruction[i]
	i = i + 1
	while i < instruction.len and instruction[i] >= "0" and instruction[i] <= "9"
		d = d + instruction[i]
		i = i + 1
	end while
	d = d.val
	//print "Move " + d + " at " + pos

	// move forward
	for j in range(1, d)
		prevPos = pos[:]
		pos.add dpos[dir]
		if gridAt(pos) == " " then
			// wrap around!
			if dir == 0 then
				pos[0] = 0
			else if dir == 1 then
				pos[1] = 0
			else if dir == 2 then
				pos[0] = grid[pos[1]].len - 1
			else if dir == 3 then
				pos[1] = grid.len - 1
			end if
			advanceToMap pos
			if gridAt(pos) == "#" then
				pos = prevPos
				break
			end if
		else if gridAt(pos) == "#" then
			// hit wall
			pos = prevPos
			break
		end if
	end for
	if i >= instruction.len then break
	
	// now turn
	//print "Turn " + instruction[i]
	if instruction[i] == "R" then
		dir = (dir + 1) % 4
	else if instruction[i] == "L" then
		dir = (dir + 3) % 4
	else
		print "WTF?!?"
		exit
	end if
	i = i + 1
end while
	
pwd = 1000 * (pos[1]+1) + 4 * (pos[0]+1) + dir
print "Password: " + pwd
```

## Part Two

In Part 2, the odd shape of the map is revealed: it's actually meant to be folded into a cube.  Walking around within any face of the cube is exactly as it was before; but now when you go off the walkable area of the map, you have to change your position and direction as it would be if you crossed over the edge of a cube.

This part give me a hard time last night.  I see no automatic way to figure out where to go when you walk off an edge; we have to simply code for every case.  To make it worse, the shape of the map in the real input file is different from the map in the example data; so you can't fully test your code except by running it on the input file, and pasting the result into the challenge page.  And then when it's wrong, you have no way to know where and how it went wrong.

My first attempt separated the "wrap around" functionality into its own method, computed which section of the map we're in (dividing position by 50 because in the real data, each face of the cube is 50x50 in size), and then using an if/else tree to figure out where to go.  It looked (after a few iterations) like this:

```
wrapAround = function
	// first, determine what face we're on
	faceRow = mathUtil.clamp(floor(pos[1] / 50), 0, 3)
	faceCol = mathUtil.clamp(floor(pos[0] / 50), 0, 2)
	s = "Wrap dir " + dir + " at " + pos + " (face " + faceCol + "," + faceRow + ")"
	testkey = faceCol + "," + faceRow + "," + dir
	if dir == RIGHT then	// move right
		if faceRow == 0 then
			pos[1] = 3*50 - pos[1]
			globals.dir = LEFT
		else if faceRow == 1 then
			pos[0] = 2*50 + (pos[1] - 50)
			pos[1] = 50
			globals.dir = UP
		else if faceRow == 2 then
			pos[0] = 3*50
			pos[1] = 50 - (pos[1] - 2*50)
			globals.dir = LEFT
		else
			pos[0] = 50 + (pos[1] - 3*50)
			pos[1] = 3*50
			globals.dir = UP
		end if
	else if dir == LEFT then 	// move left
		if faceRow == 0 then
			pos[0] = 0
			pos[1] = 3*50 - pos[1]
			globals.dir = RIGHT
		else if faceRow == 1 then
			pos[0] = pos[1] - 50
			pos[1] = 2*50
			globals.dir = DOWN
		else if faceRow == 2 then
			pos[1] = 3*50 - pos[1]
			globals.dir = RIGHT
		else
			pos[0] = 2*50 - (4*50 - pos[1])
			pos[1] = 0
			globals.dir = DOWN
		end if
	else if dir == DOWN then	// move down
		if faceCol == 0 then
			pos[0] = 2*50 + pos[0]
			pos[1] = 0
		else if faceCol == 1 then
			pos[1] = 3*50 + (pos[0] - 50)
			pos[0] = 50
			globals.dir = LEFT
		else
			pos[1] = 50 + (pos[0] - 2*50)
			pos[0] = 2*50
			globals.dir = LEFT
		end if
	else if dir == UP then	// move up
		if faceCol == 0 then
			pos[1] = 50 + pos[0]
			pos[0] = 50
			globals.dir = RIGHT
		else if faceCol == 1 then
			pos[1] = 4*50 - (2*50 - pos[0])
			pos[0] = 0
			globals.dir = RIGHT
		else
			pos[0] = pos[0] - 2*50
			pos[1] = 4*50
		end if
	end if
	
	advanceToMap pos
	s = s + " --> dir " + globals.dir + " at " + pos + "(" + gridAt(pos) + ")"
	if not tested.hasIndex(testkey) then
		print s
		tested.push testkey
	end if
	if gridAt(pos) == "#" then return false
	return true
end function
```

I ran this, it produced an answer, I pasted it in, and it was wrong.  Originally I didn't have constants defined for LEFT, RIGHT, UP, and DOWN, but was just using magic numbers for the directions; so I gave them names (as you see above), hoping that would make some mistake clear.  It didn't.  I added the test output (also shown above) on every unique combination of cube face + direction, and manually compared what it was doing to what I expected.  That was tedious, and unhelpful, because it all matched up.

I'm actually simplifying a bit; there was lots of code inspection, trying this and that, and several times where I did get a different final answer — but those were also wrong.  At this point it was past midnight, and I had to get up at six this morning, so I went to bed.

So today, I decided a different approach was needed.  The code above is complex and hard to verify, and there was no hope of using the sample data; I'd have needed to rewrite it entirely, and correctness on that wouldn't help me with correctness on the real data.  So I essentially started over (with Part 2).

This time, I decided that what I need is a map from any point/direction on the edge of a face, to the corresponding point/direction on the neighboring face.  I would be able to define this an entire edge at a time, and automatically fill in the reverse motion — i.e., if I define how to get from face A to face B, I can automatically map how to get from B back to A.  And doing it this way, the map-specific code would be short and clear enough that I could do it for the sample data as well as the real data.

I started by imagining I had a "connect" function that would handle the details, and writing code to connect up the faces of the sample cube:

```
if fname == "example.txt" then
	connect 11,4, 11,7, RIGHT,		15,8, 12,8,  DOWN		// 4-6
	connect 11,3, 11,0, RIGHT,		15,8, 15,11, LEFT		// 1-6
	connect 8,8,  8,11, LEFT,		7,7,  4,7,   UP			// 3-5
	connect 7,4,  4,4,  UP,			8,3,  8,0,   RIGHT		// 1-3
	connect 3,4,  0,4,  UP,			8,0,  11,0,  DOWN		// 1-2
	connect 3,7,  0,7,  DOWN,		8,11, 11,11, UP			// 2-5
	connect 12,15, 15,15, DOWN,		0,7,  0,4,   RIGHT		// 2-6
```

The numbers in comments refer to the face numbers as shown in the [problem description](https://adventofcode.com/2022/day/22).  The left part (first 5 arguments) on each line defines one edge, traversed in a certain direction; the second half (last 5 arguments) defines the corresponding edge, traversed in the corresponding direction.

After I'd laid these connections out as well as I could, I actually implemented that "connect" function.  It builds a map, where the keys and values are [x, y, direction] triplets.

```
connect = function(fromX0, fromY0, fromX1, fromY1, fromDir, toX0, toY0, toX1, toY1, toDir)
	steps = abs(fromX1-fromX0) + abs(fromY1-fromY0)
	qa.assert abs(toX1-toX0) + abs(toY1-toY0) == steps
	dFrom = [sign(fromX1-fromX0), sign(fromY1-fromY0)]
	dTo = [sign(toX1-toX0), sign(toY1-toY0)]
	fromPos = [fromX0, fromY0]
	toPos = [toX0, toY0]
	for step in range(0, steps)
		connectMap[fromPos + [fromDir]] = toPos + [toDir]
		print (fromPos + [fromDir]) + " --> " + (toPos + [toDir])
		connectMap[toPos + [(toDir+2)%4]] = fromPos + [(fromDir+2)%4]
		fromPos.add dFrom
		toPos.add dTo
	end for
end function
```

There's a lot going on there, but conceptually it's fairly simple: we figure out how to step along the "from" edge and the "to" edge, and then we do so, mapping each "from" point and direction to the corresrponding "to" point and direction, and vice versa (`(dir+2)%4` computes the inverse direction).

I ran this on the sample data, and caught a couple of initial bugs -- I'd made a typo on one of the numbers (quickly caught by the `qa.assert` call above), and initially forgot the `fromPos.add dFrom` and `toPos.add dTo` lines, but these were easy bugs to catch.  After that, it ran and produced the right answer for the sample data.  Huzzah!

Then I implemented the same sort of connections for the real data:

```
else
	connect 149,49, 149,0, RIGHT,	99,100, 99,149, LEFT	// F-C
	connect 99,50, 99,99, RIGHT,	100,49, 149,49, UP		// D-F
	connect 49,150, 49,199, RIGHT,	50,149, 99,149, UP		// A-C
	connect 0,199, 49,199, DOWN,	100,0, 149,0, DOWN		// A-F
	connect 50,0, 50,49, LEFT,		0,149, 0,100, RIGHT		// E-B
	connect 50,50, 50,99, LEFT,		0,100, 49,100, DOWN		// D-B
	connect 0,150, 0,199, LEFT,		50,0, 99,0, DOWN		// A-E
```

Note that if you're following along at home, your input may may well be a different shape than mine.  In that case, this code won't work for you; you'll need to define where the connecting edges are on _your_ map.

After coding this up, I ran it on the input file, but it produced yet another wrong answer.  So I did another test that occurred to me this morning: I cleared all the obstacles from the map, and ran 200 steps in one direction.  Since each face is 50 steps across, this should run all the way around the cube and end up back where you started.  But right away, it failed to do this.  It was easy to see where I had made a mistake, and connected one of the edges in the wrong direction.

I fixed that mistake, then verified that the 200-steps test worked in all four directions from several starting positions.  It did, so I took my test hack out, and ran it on the input file again.  Finally, I got a right answer!

{% spoiler Here's the complete program for Part 2. %}
```
import "mapUtil"
import "aoc"
import "qa"

resultA = []
resultB = []

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

instruction = grid.pop
grid.pop

gridAt = function(pos)
	if pos[1] < 0 or pos[1] >= grid.len then return " "
	line = grid[pos[1]]
	if pos[0] < 0 or pos[0] >= line.len then return " "
	return line[pos[0]]
end function

RIGHT=0; DOWN=1; LEFT=2; UP=3
dpos = [[1,0], [0,1], [-1,0], [0,-1]]

pos = [0,0]	// column, row
dir = RIGHT

while gridAt(pos) == " "
	pos.add dpos[dir]
end while

tested = {}

connectMap = {}	// key: [x,y,dir] triplet; value: new [x,y,dir] triplet

connect = function(fromX0, fromY0, fromX1, fromY1, fromDir, toX0, toY0, toX1, toY1, toDir)
	steps = abs(fromX1-fromX0) + abs(fromY1-fromY0)
	qa.assert abs(toX1-toX0) + abs(toY1-toY0) == steps
	dFrom = [sign(fromX1-fromX0), sign(fromY1-fromY0)]
	dTo = [sign(toX1-toX0), sign(toY1-toY0)]
	fromPos = [fromX0, fromY0]
	toPos = [toX0, toY0]
	for step in range(0, steps)
		connectMap[fromPos + [fromDir]] = toPos + [toDir]
		print (fromPos + [fromDir]) + " --> " + (toPos + [toDir])
		connectMap[toPos + [(toDir+2)%4]] = fromPos + [(fromDir+2)%4]
		fromPos.add dFrom
		toPos.add dTo
	end for
end function

// connect the edges of the cube
if fname == "example.txt" then
	connect 11,4, 11,7, RIGHT,		15,8, 12,8,  DOWN		// 4-6
	connect 11,3, 11,0, RIGHT,		15,8, 15,11, LEFT		// 1-6
	connect 8,8,  8,11, LEFT,		7,7,  4,7,   UP			// 3-5
	connect 7,4,  4,4,  UP,			8,3,  8,0,   RIGHT		// 1-3
	connect 3,4,  0,4,  UP,			8,0,  11,0,  DOWN		// 1-2
	connect 3,7,  0,7,  DOWN,		8,11, 11,11, UP			// 2-5
	connect 12,15, 15,15, DOWN,		0,7,  0,4,   RIGHT		// 2-6
else
	connect 149,49, 149,0, RIGHT,	99,100, 99,149, LEFT	// F-C
	connect 99,50, 99,99, RIGHT,	100,49, 149,49, UP		// D-F
	connect 49,150, 49,199, RIGHT,	50,149, 99,149, UP		// A-C
	connect 0,199, 49,199, DOWN,	100,0, 149,0, DOWN		// A-F
	connect 50,0, 50,49, LEFT,		0,149, 0,100, RIGHT		// E-B
	connect 50,50, 50,99, LEFT,		0,100, 49,100, DOWN		// D-B
	connect 0,150, 0,199, LEFT,		50,0, 99,0, DOWN		// A-E
end if

i = 0
while i < instruction.len
	// get a number
	d = instruction[i]
	i = i + 1
	while i < instruction.len and instruction[i] >= "0" and instruction[i] <= "9"
		d = d + instruction[i]
		i = i + 1
	end while
	d = d.val

	// move forward
	for j in range(1, d)
		prevPos = pos[:]
		prevDir = dir
		pos.add dpos[dir]
		if gridAt(pos) == " " then
			// wrap around!
			newPos = connectMap[prevPos + [dir]]
			if gridAt(newPos) == "#" then
				// hit wall
				pos = prevPos
				dir = prevDir
				break
			end if
			pos = newPos[:2]
			dir = newPos[2]
		else if gridAt(pos) == "#" then
			// hit wall
			pos = prevPos
			dir = prevDir
			break
		end if
	end for
	if i >= instruction.len then break
	
	// now turn
	if instruction[i] == "R" then
		dir = (dir + 1) % 4
	else
		dir = (dir + 3) % 4
	end if
	i = i + 1
end while
	
print "Final position: " + pos + " with dir " + dir
pwd = 1000 * (pos[1]+1) + 4 * (pos[0]+1) + dir
print "Password: " + pwd
```
{% endspoiler %}

Then, since I'd put so much time into this already, I spent a few more minutes to make a fun visualization for you.  This shows the path taken through my map with the real input data.

![Image of complex path in blue, taken through a cubical map of light gray with brown obstacles.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2y20pazzjbgtfwl9d6lw.gif)

## Final Thoughts

I did well on Part 1, placing 255th worldwide.  But Part 2 defeated me last night.  The complexity of the code, combined with very little opportunity to see where it was going wrong, made it a very thorny problem.

Today, though, it fell to my efforts pretty quickly.  Maybe it's instructive to consider why (apart from simply being smarter in the morning than at night, which is certainly the case for me).  I found a way to replace complex, ugly code, with relatively simple code, one line per edge.  This was much easier to write, inspect, and correct.  I also took the time to make it work on the sample data; this was possible both because the new approach made it much easier, and because I was no longer feeling rushed.  It's amazing how trying to rush often ends up wasting time.

So there we go.  22 days down, three to go!