Advent of Code (in MiniScript), Day 9

Last night was Day 9 of the Advent of Code challenge, which I once again tackled with MiniScript. This was a fun and somewhat tricky problem. I did decently on Part A, but made a mistake that cost me a lot of time on Part B.

But, for the first time in this year's series, we have a problem that lends itself to a cool graphical display!

Part A

In the first part, we are to imagine a short rope with a "head" and a "tail". The head is moved in a series of up, down, left, or right steps, and the tail needs to follow it according to certain rules. Then at the end, we have to report how many unique spaces the tail passed through. I implemented this like so:

if 1 then fname = "input.txt" else fname = "example.txt"
f = file.open(fname)

head = [0,0]
tail = [0,0]

tailSet = {}

while not f.atEnd
    line = f.readLine
    if line == null then break // end of file
    print line
    dir = line[0]
    dx = 0
    dy = 0
    if dir == "R" then dx = 1
    if dir == "L" then dx = -1
    if dir == "U" then dy = 1
    if dir == "D" then dy = -1
    for i in range(1, val(line[2:]))
        head[0] = head[0] + dx
        head[1] = head[1] + dy
        if head[0] > tail[0]+1 then
            tail[0] = tail[0]+1
            tail[1] = head[1]
        end if
        if head[0] < tail[0]-1 then
            tail[0] = tail[0]-1
            tail[1] = head[1]
        end if
        if head[1] > tail[1]+1 then
            tail[1] = tail[1]+1
            tail[0] = head[0]
        end if
        if head[1] < tail[1]-1 then
            tail[1] = tail[1]-1
            tail[0] = head[0]
        end if
        //print "head: " + head + "  tail: " + tail
        tailSet.push tail[:]
    end for
end while

print tailSet.len

Notice my implementation of the rule for following: if the head was more than 1 unit away in either X or Y, then I moved the tail towards the head in that dimension, and moved the other dimension to match the head exactly.

Part B

For the second part of the challenge, we had to now imagine a rope with 10 knots (including head and tail) instead of only two. No problem, I thought; I'll just put my tail-following code into a function, make a list of the knot positions, and call the follow function on each pair in turn.

I quickly implemented that, tried it on both the original sample problem and on the new example given in part B, and it produced the right answer for both. So I confidently hooked up the real input set, got an answer, and pasted it into the Advent of Code answer field.

And it was wrong.

Unfazed, I cooly engaged in calm, methodical debugging... only kidding. I panicked. How could it be right on both examples, and wrong on the real code?! I thrashed about for several minutes, looking for some dumb mistake that might make it fail to read the whole input file, or treat the blank line at the end of the file as some bogus input, etc.

Finally, I went back to the second input example, and made the code print my complete rope list (i.e. the coordinates of all 10 knots) and wait for a keypress after each step. Then I compared what I was seeing to the step-by-step example in the problem description. After only a couple of steps, the coordinates didn't match. I realized then that my follow function was wrong — though it had to be wrong in a way that happened to produce the right answer in some cases.

So I went back to the problem description and studied the rules for following more carefully. I then re-implemented the follow function as literally as I could, not trying to be clever and simplify it in any way.

if 1 then fname = "input.txt" else fname = "example2.txt"
f = file.open(fname)

rope = []
for i in range(9)
    rope.push [0,0]
end for

follow = function(head, tail)
    dx = head[0] - tail[0]
    dy = head[1] - tail[1]
    if abs(dx) <= 1 and abs(dy) <= 1 then return
    if dx == 0 then
        tail[1] = tail[1] + sign(dy)
    else if dy == 0 then
        tail[0] = tail[0] + sign(dx)
    else
        tail[0] = tail[0] + sign(dx)
        tail[1] = tail[1] + sign(dy)
    end if
end function

tailSet = {}

while not f.atEnd
    line = f.readLine
    if line == null then break // end of file
    dir = line[0]
    dx = 0
    dy = 0
    if dir == "R" then dx = 1
    if dir == "L" then dx = -1
    if dir == "U" then dy = 1
    if dir == "D" then dy = -1
    for i in range(1, val(line[2:]))
        rope[0][0] = rope[0][0] + dx
        rope[0][1] = rope[0][1] + dy
        for j in range(1, 9)
            follow rope[j-1], rope[j]
        end for
        tailSet.push rope[-1][:]
    end for
    //print rope; key.get
end while

print tailSet.len

This produced the same answer on the example problems, but a different answer on the real input. So I pasted that in, and this time it was right. Whew!

I realized afterwards that my original "follow" idea worked when the lead knot only moves orthogonally (never diagonally). That was the case in Part A. But in Part B, even though the head of the rope still moves orthogonally, the subsequent knots can move diagonally — and then the knots that follow them did the wrong thing.

The new code (above) just checks for the three cases spelled out in the problem description: the lead knot is either in line with the following knot horizontally, or vertically, or neither. In the latter case, the following knot takes a diagonal step (but does not necessarily end up in line with the lead knot).

Had I implemented it that way in the first place, I probably would have done quite well. As it was, I ended up 496th for Part A, but only 1254th for Part B. All that debugging cost me a ton of time.

The moral of the story? Read the problem carefully! And just do what it says; don't try to be too clever.

Oh, but I promised some pretty graphics, didn't I? Since I'm doing all this in Mini Micro, those are easy to add (you can see the code here). The GIF at the top of this post shows the movement of the rope for the Part B example. And here's the start of its motion for my real input file... though the full input makes it wander much longer, and much further from the origin. Enjoy!