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.
The rest of the code is pretty trivial, but here's the complete program for the curious.
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
Here's the complete program for Part Two.
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.
Top comments (0)