Advent of Code (in MiniScript), Day 13

Welcome back to my series of Advent of Code solutions in MiniScript! The challenge on day 13 is a classic sorting problem. We're given little trees (nested lists of integers), and in Part A, just need to compare pairs of these, figure out which ones are in the correct order, and compute a sum based on that.

The inputs look like [[1],[2,3,4]], which happens to be valid MiniScript syntax. But I didn't want to do my Day 11 trick and convert the input files into code. Instead, I noticed that these inputs are also valid JSON syntax, and Mini Micro has a JSON parser in /sys/lib. So I used that, parsing each input line as I read it, so that I have a MiniScript list or number. Then, to compare two such things, I wrote this function:

// return >0 if lhs and rhs are in the right order;
// <0 if in the wrong order;
// 0 if unknown
compare = function(lhs, rhs)
    if lhs isa number and rhs isa number then
        return rhs - lhs
    end if
    if lhs isa number then lhs = [lhs]
    if rhs isa number then rhs = [rhs]
    i = 0
    while true
        if i >= lhs.len then return i < rhs.len
        if i >= rhs.len then return -1
        result = compare(lhs[i], rhs[i])
        if result != 0 then return result
        i = i + 1
    end while
end function

This is a direct implementation of the rules in the challenge, though I had to choose how to represent the three possible results of any comparison, i.e. "right order", "wrong order," or "undefined." I chose to represent these with a numeric return value that's > 0 if they're in the right order, < 0 if they're in the wrong order, and exactly 0 if undefined. This is a convention that's common in comparison functions in many languages and libraries.

import "json"

if 1 then fname = "input.txt" else fname = "example.txt"

f = file.open(fname)
resultA = []

// return >0 if lhs and rhs are in the right order;
// <0 if in the wrong order;
// 0 if unknown
compare = function(lhs, rhs)
    if lhs isa number and rhs isa number then
        return rhs - lhs
    end if
    if lhs isa number then lhs = [lhs]
    if rhs isa number then rhs = [rhs]
    i = 0
    while true
        if i >= lhs.len then return i < rhs.len
        if i >= rhs.len then return -1
        result = compare(lhs[i], rhs[i])
        if result != 0 then return result
        i = i + 1
    end while
end function

index = 1
while not f.atEnd
    p1 = f.readLine
    if p1 == null then break
    p1 = json.parse(p1)
    p2 = json.parse(f.readLine)
    f.readLine  // skip

    print "Compare: " + p1
    print "     to: " + p2
    result = compare(p1, p2)
    if result > 0 then resultA.push index

    index = index + 1
end while
f.close

print "final answer (part A): " + resultA.sum

Part B

The second part of this challenge was to sort all the inputs, plus two additional little trees. The final positions of the two extra trees, multiplied together, was the value needed to complete the task.

This was the first time all month that I said "DOH!" with regard to my MiniScript environment. Many modern programming languages have a sort function that takes a comparison function, like this one in .NET. MiniScript, however, does not. Its sort method can optionally take a key to sort by, which in 99% of real-world cases is all you need and much easier to use than defining a comparison function. But it doesn't help in this case. Nor did I have anything in /sys/lib or my custom Advent of Code module which could do it.

So, I had to write a sort algorithm, and do it fast! I chose Bubble Sort because it's dead simple. You just zip through the list, swapping any neighboring pair that is out of order, and keep doing thus until none need to be swapped. The code came out like this:

while true
    swappedAny = false
    for i in range(0, packets.len-2)
        if compare(packets[i], packets[i+1]) < 0 then
            packets.swap i, i+1
            swappedAny = true
        end if
    end for
    if not swappedAny then break
end while

import "stringUtil"
import "aoc"
import "json"

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

// return >0 if lhs and rhs are in the right order;
// <0 if in the wrong order;
// 0 if unknown
compare = function(lhs, rhs)
    if lhs isa number and rhs isa number then
        return rhs - lhs
    end if
    if lhs isa number then lhs = [lhs]
    if rhs isa number then rhs = [rhs]
    i = 0
    while true
        if i >= lhs.len then
            if i >= rhs.len then return 0
            return 1
        end if
        if i >= rhs.len then return -1
        result = compare(lhs[i], rhs[i])
        if result != 0 then return result
        i = i + 1
    end while
end function

packets = []
packets.push [[2]]
packets.push [[6]]

index = 1
while not f.atEnd
    p1 = f.readLine
    if p1 == null then break
    p1 = json.parse(p1)
    p2 = json.parse(f.readLine)
    f.readLine  // skip

    packets.push p1
    packets.push p2
end while
f.close

print "Sorting"
while true
    swappedAny = false
    for i in range(0, packets.len-2)
        if compare(packets[i], packets[i+1]) < 0 then
            packets.swap i, i+1
            swappedAny = true
        end if
    end for
    if not swappedAny then break
end while

idx1 = packets.indexOf( [[2]] ) + 1
idx2 = packets.indexOf( [[6]] ) + 1
print "divider packets at " + idx1 + " and " + idx2 + ", so: " + (idx1*idx2)

Results & Conclusion

The first part took 11.5 minutes, placing me 226th — my best yet! But the second part took an additional 7 minutes, most of which was in coding up that bubble sort. Meanwhile, many others in the competition were simply passing their comparison function to a standard system-library sort function. So my final rank was 315. Not terrible, but it could have been better.

So as usual, I come away with a realization for something that really ought to exist in MiniScript: an efficient sort algorithm that takes a comparison function as an argument. I'll code this up soon, and who knows, it might even find its way into a future version of /sys/lib/listUtil.