Welcome back to my series of Advent of Code solutions in MiniScript! 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.
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! 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.
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.
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
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 is holding up to whatever Advent of Code throws at it, and I'm looking forward to the final 10 challenges!
Top comments (0)