Advent of Code (in MiniScript), Day 15
Tags: miniscript, adventofcode, programming
Published: 2022-12-15 16:05:27

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  [Day 15](https://adventofcode.com/2022/day/15) was a real challenge.  Not so much because the code was difficult, but because the problem was huge!  Unless there is some clever solution I still haven't seen, it required searching a very large problem space, which took quite a while.

The basic setup is: we have a (large) 2D area which is pretty densely covered with sensors.  Each sensor covers a diamond-shaped area, defined as all points within a certain Manhattan distance of the sensor position.  These sensor areas overlap densely, and almost cover the entire field.

![Diagram of sensor areas](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r132qjhv8ns191shqpfy.png)

The diagram above shows the setup from my full input file.  Each yellow diamond represents the area of one sensor; and the blue square defines the full field of interest (which doesn't actually come into play until Part 2).

For the first part of the challenge, we have to find the total area covered by all sensors for a particular row.

This presented an opportunity to use the new `Span` class I created after [Day 4](https://dev.to/joestrout/advent-of-code-in-miniscript-day-4-2kpj)!  For each sensor, I could figure out whether it covered the row of interest at all, and if so, how wide its diamond would be at that point.  From this I define a Span that represents the range of the sensor in that row.  My Span class has methods to test whether two spans overlap, and find the union of two spans; so I use this to combine spans where possible as I loop over the sensors.

At the end, it's still possible that we have overlapping spans, so I do a final check and combination of them afterwards.

```
import "stringUtil"
import "listUtil"
import "aoc"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

if fname == "example.txt" then yOfInterest = 10 else yOfInterest = 2000000

// Loop over sensors (one per line), and build spans representing
// the coverage on the row of interest.
spans = []
for line in lines
	m = line.match("Sensor at x={sx}, y={sy}: closest beacon is at x={bx}, y={by}")
	if not m then
		print "Pattern did not match on line: " + line
		continue
	end if
	m.applyToValues @val
	m.stuffInto @locals
	distToSensor = abs(bx-sx) + abs(by-sy)
	ydiff = abs(sy - yOfInterest)
	if ydiff > distToSensor then continue
	radiusAtY = distToSensor - ydiff
	span = Span.make(sx - radiusAtY, sx + radiusAtY)
	
	found = false
	for i in spans.indexes
		if spans[i].overlaps(span) then
			spans[i] = spans[i].union(span)
			found = true
			break
		end if
	end for
	if not found then spans.push span
end for

// Further combine any spans that can be combined.
while spans.len > 1
	didAny = false
	for i in range(spans.len-1, 1)
		for j in range(i-1)
			if spans[j].overlaps(spans[i]) then
				spans[j] = spans[j].union(spans[i])
				spans.remove i
				didAny = true
				break
			end if
		end for
		if didAny then break
	end for
	if not didAny then break
end while

// Find the total area covered by the remaining span(s).
resultA = []
for s in spans
	resultA.push s.endVal - s.startVal
end for

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

## Part B

The second part was a bigger challenge.  In this one, the field of interest is defined: a 4 million by 4 million square (as shown in the image at the top of this post).  Somewhere in that square, there is _one_ integer position not covered by any sensor.  We have to find it.

I couldn't (and still can't) think of any way to do that other than to check each row.  Using the code from part 1, we get a span (or set of spans) that represent the coverage for any particular row.  It's easy then to see whether those spans cover the whole field of interest.  But I found I could only check about 1000 rows per second.  At that rate, it would take well over an hour to check 4 million rows.

I refactored my code a bit so that the parsing of the input data only happens once; each line is turned turned into a little map of numeric values, and saved onto an "observations" list.  This helped a little.  Then I launched a second copy of Mini Micro, starting its search at y = 2000000.  Then, still not satisfied, I set up a run in command-line MiniScript, and a second of the same, each starting at a different row.  So at this point I had four processes searching at once, in two different environments.

![Screen shot of four search programs running at once](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dgo6mhc2fxoeqrfdflg3.gif)

It took about 15 minutes to find the answer (which in my case, was ultimately at Y = 3230812).  This is by far the longest I've had to watch my code run in the whole Advent of Code.

{% spoiler Here's the code for the search program. %}
```
import "stringUtil"
import "listUtil"
import "aoc"

resultB = []

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

if fname == "example.txt" then maxY = 20 else maxY = 4000000

compareSpans = function(a,b)
	if a.startVal == b.startVal then
		return a.endVal - b.endVal
	else
		return a.startVal - b.startVal
	end if
end function

observations = []
for line in lines
	m = line.match("Sensor at x={sx}, y={sy}: closest beacon is at x={bx}, y={by}")
	if not m then
		print "Pattern did not match on line: " + line
		continue
	end if
	m.applyToValues @val
	observations.push m
end for

for yOfInterest in range(0,maxY)
	if yOfInterest % 1000 == 0 then print yOfInterest + "..."
	spans = []
	for m in observations
		m.stuffInto @locals
		distToSensor = abs(bx-sx) + abs(by-sy)
		ydiff = abs(sy - yOfInterest)
		if ydiff > distToSensor then continue
		radiusAtY = distToSensor - ydiff
		span = Span.make(sx - radiusAtY, sx + radiusAtY)
		
		found = false
		for i in spans.indexes
			if spans[i].overlaps(span) then
				spans[i] = spans[i].union(span)
				found = true
				break
			end if
		end for
		if not found then spans.push span
	end for
	
	while spans.len > 1
		didAny = false
		for i in range(spans.len-1, 1)
			for j in range(i-1)
				if spans[j].overlaps(spans[i]) then
					spans[j] = spans[j].union(spans[i])
					spans.remove i
					didAny = true
					break
				end if
			end for
			if didAny then break
		end for
		if not didAny then break
	end while
	
	if spans.len > 1 then spans.sortWithFunction @compareSpans
	spanStrs = []
	for s in spans
		spanStrs.push s.str
	end for
	if spans[0].startVal > 0 then
		print "y:" + yOfInterest + "  spans: " + spanStrs.join("; ")
		exit
	end if
	if spans.len == 1 then
		if spans[0].endVal < maxY then
			print "y:" + yOfInterest + "  spans: " + spanStrs.join("; ")
			exit
		end if
	else
		x = spans[0].endVal
		for i in range(1, spans.len-1)
			if spans[i].startVal > x+1 then
				print "y:" + yOfInterest + "  spans: " + spanStrs.join("; ")
				exit
			end if
			x = spans[i].endVal
		end for
	end if
end for
```
{% endspoiler %}

## Results and Reflection

Part 1 of this challenge took me about 20 minutes to code, which placed me 580th worldwide.  Both parts together took 47 minutes (by far my longest yet), for a rank of 620.

Given how long my code took to run, I'm actually not too dissatisfied with dropping 40 places on Part 2; I was expecting much worse.  I still wonder if there is some more clever solution that lets me avoid checking row by row.  If you know of one, please leave a comment below!

I'm a little disappointed that Part 1 didn't go faster, especially considering that I already had this handy Span class.  I now see how useful it is to sort & combine spans; perhaps that's something Span should be able to do out of the box.  With that it would have gone _much_ faster.  Perhaps that's locking the barn door after the cows already got out, as my mother might say.  But I don't think so.

In any case, I remain quite happy with how [MiniScript](https://miniscript.org) is holding up to whatever Advent of Code throws at it, and I'm looking forward to the final 10 challenges!