Advent of Code (in MiniScript), Day 13
Tags: miniscript, adventofcode, programming
Published: 2022-12-13 15:52:41

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20#adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  The challenge on [day 13](https://adventofcode.com/2022/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](https://dev.to/joestrout/advent-of-code-day-11-in-miniscript-i5h) trick and convert the input files into code.  Instead, I noticed that these inputs are _also_ valid JSON syntax, and [Mini Micro](https://miniscript.org/MiniMicro/) 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](https://adventofcode.com/2022/day/13) 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.

{% spoiler 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
```
{% endspoiler %}

## 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](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=net-7.0#system-collections-generic-list-1-sort(system-comparison((-0)))) in .NET.  MiniScript, however, does not.  Its [sort](https://miniscript.org/wiki/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
```
{% spoiler 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)
```
{% endspoiler %}

## 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](https://github.com/JoeStrout/minimicro-sysdisk/blob/master/sys/lib/listUtil.ms).