JoeStroutWelcome back to my series of Advent of Code solutions in MiniScript! 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. 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!
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
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.
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!
