Advent of Code (in MiniScript), Day 5

Last night was the 5th night of the Advent of Code challenge. This one was quite different from previous challenges, both in the form of its input, and in the sort of code required to produce an answer. The input looked like this:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

This was the sample input; the real input was of similar form but much larger. The first part, before the blank line, represents a series of stacks. The second part is a set of commands to move some quantity of boxes from one stack to another.

My code for this one came out considerably longer than in previous days, despite havng a separate (prepared ahead of time) aoc module and all the other modules in Mini Micro's /sys/lib folder to lean on. So I'll present it in sections.

Setup and Loading Stacks

I knew I would represent each stack in MiniScript as a list, which would allow me to easily move items from one to another. (Though I realized afterwards I could have used strings instead.) The first obstacle was: how to initialize my stacks from the essentially graphical diagram in the input file? I came up with this code:

import "stringUtil"
import "mapUtil"
import "listUtil"
import "mathUtil"
import "aoc"

f = file.open("input.txt")

stacks = []
result = []

// Load initial stack configuration
while not f.atEnd
    line = f.readLine   
    if line[:3] == " 1 " then break  // got to numbers
    if not stacks then
        stacks = []
        for i in range(1, ceil(line.len/4))
            stacks.push []
        end for
    end if
    for i in stacks.indexes
        item = line[i*4+1]
        if item == " " then continue
        stacks[i].insert 0, item
    end for
end while

The imports at the top were all part of my starter program; I figure, just import everything that might be useful. Then I have a loop that reads the file until we see a line that starts with " 1 ", which indicates we've reached the end of the stack data. I initialize my stacks based on the length of the line (I verified in a text editor that all the stack-diagram lines are padded with spaces). Then I find the letter for each stack i, by simply indexing into the line as i*4+1, and insert it into the front of the list, so that at the end, each stack is stored bottom to top.

Applying the moves

Next, we need to apply all the moves specified in the file. Here all those import libs came in handy, because I could use string.match to easily parse each line, plus applyToValues to convert strings to numbers, and stuffInto to make the three fields into local variables (just so I could type qty instead of m.qty). Much of that was already in my starter program, so it was quick.

Then it was just a matter of moving items from stack to stack as specified.

// apply all the specified moves
while not f.atEnd
    line = f.readLine.trim
    if not line then continue
    m = line.match("move {qty} from {src} to {dst}")
    if not m then
        print "Pattern did not match on line: " + line
        continue
    end if
    m.applyToValues @val
    print m
    m.stuffInto locals
    for i in range(1, qty)
        item = stacks[src-1].pop
        stacks[dst-1].push item
    end for
end while
f.close

Getting the Final Answer

The final answer required in this challenge was a string formed by taking the top letter from each stack, in order. The problem did not specify what to do if a stack was empty, so I chose to include a space character at that point. (In retrospect, given the high quality of the problem statements in this challenge, the lack of such a specification probably means we could assume no stack should be empty at the end.)

// find result (top item of each stack)
for i in stacks.indexes
    if stacks[i] then
        result.push stacks[i][-1]
    else
        result.push " "
    end if
end for

print "final : " + result.join("")

The three sections of code above constitute the complete program for Part A of the challenge. For me, the output was TWSGQHNHL, which was the right answer.

Part B

Part B made one small change: instead of moving items one at a time, they now have to be moved all at once, preserving their original order. This changes only the middle section of code, to:

// apply all the specified moves
while not f.atEnd
    line = f.readLine.trim
    if not line then continue
    m = line.match("move {qty} from {src} to {dst}")
    if not m then
        print "Pattern did not match on line: " + line
        continue
    end if
    m.applyToValues @val
    print m
    m.stuffInto locals
    items = stacks[src-1][-qty:]
    stacks[src-1] = stacks[src-1][:-qty]
    stacks[dst-1] = stacks[dst-1] + items
end while
f.close

However, I didn't arrive at this correct code right away — first I (incorrectly) kept the three changed lines (starting with items = stacks[src-1][-qty:]) inside the previous for loop. So if it said to move three boxes, I moved three boxes three times. Oops. This cost me quite a bit of time on part 2.

Results and Reflection

I was feeling pretty good about Part A; it was a complex program, but I proceeded methodically, validated my results on the sample data first, and got the right answer on the real data on my first try. But it still took me 14 minutes, ending up with a Part A rank of 1221.

Part B involved some debugging, as I didn't see my mistake (keeping the for loop) right away. Total time for both parts came to 23 minutes, for a rank of 2552.

The debugging is what it is; particularly since these challenges happen (for me) at night, and I'm a morning person, I'm pleased it only took me 8 minutes. But I was surprised that so many people finished Part A so quickly. Was there some better way I could have loaded the initial stacks?

Given the libraries I had, I don't see how. However, I may add some new tricks to my aoc module. Maybe I should have a "select" method that grabs a subset of a sequence (string or list) given a list of indexes. I could use this on each line to convert the raw input, like [Z] [M] [P], into just the letters, like ZMP (by doing line = line.select(range(1, line.len, 4))). Then I'd have a list of strings like:

 D 
NC 
ZMP

Then, what if I had a "rotate" method that could turn such a list of equal-length strings on its side, changing columns into rows? (This is a little like a matrix transpose, but not quite the same; for a complete library I'd need to be able to rotate and flip in various ways.) Then I would have a list of strings like:

ZN 
MCD
P  

...which would be my list of stacks, with each stack as a string. Then I could do the required manipulations directly in string form, which would have been nearly as easy as using lists. (Instead of push and pop, I would have had to use slicing, but that might have led me to do Part A in a manner more similar to Part B, saving me time overall.)

So, I guess I'll be adding some new functions to my aoc module! Who knows if a problem like this will come up again, but if it does, I want to be prepared.