https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 15> :thread:
# advent-of-code
a
j
I think I'm messing up my row indecies, it should be a minimum? Or is it that size on Collections is an Int?
Yeah I messed up that I have to go to the left by the max distance, which was not needed for the example
s
I wonder what comes first, my dummy algorithm for part 2 finishes, or I come up with a more performant algorithm...
j
@Sergei Petunin you could filter with solutions for part1, but I'm not sure if that really helps
s
For part 1, I only check a single row, column by column, sensor by sensor, if the point is within the range. This approach unfortunately doesn't scale for 4 million rows.
j
my input only has 33 sensors so it should not be to bad
s
Mine too, but the main complexity driver in the naive approach is not the number of sensors, but the number of points you need to check
m
first day that I couldn't immediately write a solution and had to really think about how I wouldn't brute force it
j
not sure if brute force even works, since the search space is to huge
m
well apparantly for part 1 a brute force solution can work according to @Sergei Petunin
I could just bruteforce my first solution in part 2 tbf
s
I think for the second part my brute force solution should also complete in a couple of hours :D
m
Finally got part 2 done. Tried brute force at first but it would take forever.
k
I tried using part 1 to brute force part 2 (so checking all 4,000,001 y positions) and it took my machine around three minutes. I am using Python this year, Kotlin should be even faster. An idea: diagonal coordinate transform ((x - y), (x + y)) and use range arithmetic to rule out regions
s
Then your part 1 is probably already written in a clever and optimal way...
As I'm still clueless
t
Finally found a decent solution for part 2 by scanning all y positions but skipping along the x axis to quickly get outside of the "exclusion zone" of any sensor. Worst case is still n^2, but it was fast enough (couple of seconds). Wondering if a none n^2 solution even exists... I'm sure there will be some clever solutions for this one! Edith: Not actually n^2
j
@Sergei Petunin think about which ranges per line are already covered by the sensors
d
Got part 1, on to part 2…
j
Oh man part2 took me nearly an hour
m
My part 2. My idea was that the solution point must lie at a circle of radius one more than the beacon’s distance from each sensor. So I find all the points on a circle around each sensor and then only check these.
s
Damn that was clever
d
The beacons form a skip list
snippet
Copy code
val beaconMax = 4000000
fun findBeacon(): Point? {
    for (x in 0..beaconMax) {
        var y = 0
        while (y <= beaconMax) {
            val sensor = sensors.find { it.inRange(x, y) }
            if (sensor == null) return Point(x, y)
            y = sensor.loc.y + sensor.distance - abs(x - sensor.loc.x) + 1
        }
    }
    return null
}
m
Optimized my solution a little, now it only takes about 200ms, as opposed to the 6s before.
s
Used the idea from @Marcin Wisniowski and finally got it, not super fast, but within half a second, so I'm happy: https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day15.kt
d
takes ~1s
finally used a regex for parsing
@Timmy skip list solution isn’t O(n^2) in the worst case — it’s O(n) * O(k) where n = #rows, k = #sensors, the latter of which is effectively a small constant
when traversing a given row, in the worst case you use each sensor to skip once
checking only the diamond outside the range of each sensor is the same complexity
well sort of, it depends on the sensor ranges
the number of diamond points is at most #sensors * 4 * (n / 2)
e
took me a while to get my interval merging right, but I came up with something relatively elegant I think
this is really a 1-D solution applied repeatedly; having done https://adventofcode.com/2018/day/23 I'm pretty sure there's a better solution but I'll think about that later
as it is, this is about 6µs for part 1 and 2s for part 2
j
Similar, maybe not that elegant, but also around 2-3s for part2, also brute force raster scan through 1..4000000
d
How is it 6 micros for part 2? Aren't you also doing a scan of each column?
j
@Dan Fingal-Surma it’s “6µs for part 1” AND “2s for part 2" 😆
d
Misread
Advent of learning to read
j
I’m thinking about walking on outlines of each scan ranges, but it will be a large amount of steps as well. There must be some nice < 0.1s solution. There always is 🙂 I’ll have something to think about in the evening 🙂
e
the current direction of my thoughts: coordinate transform to (x + y, x - y), then quadtrees. gonna take a fair bit more planning to get there though
d
Yeah I just noticed you could transform to square bounding boxes
m
The solution must be on the intersection of two sensor ranges (I think?), so it should be possible to just take every pair of sensors and check the intersection, that’s much less points to check.
I’ll probably stay with my 0.2s solution though.
d
What do you mean on the intersection?
m
I mean exactly between two sensors, both being just 1 short of reaching it.
d
Oh I see yeah
j
Hi, while beautifying today's solution I've come across strange thing. How can I invoke the correct version of 
plus
that would preserve the type? I.e. I need the argument to be treated as one element not as 
Iterable
so that the result is not 
Set<Any>
d
It must be in the intersection of 4 bounding boxes I think
It's clearer if you imagine it transformed to square bounding boxes
m
Not necessarily if it’s on the edge of the search space.
d
True
m
On the edge it’s two, and it could be on the 4 corners with just 1 sensor barely reaching it.
d
On the corner it would need three I think
Same on the edge?
Each box can draw one straight line
s
@Jan Durovec probably 
x.plus((1..4))
d
Anywhere in the edge you need 3 lines, corner 2
s
Or 
x + setOf(1..4)
d
Oh but the space isn't oriented the same way as the boxes
j
@Sergei Petunin doesn't help
d
I rotated the boxes in my head but not the space boundary
So you're right
Intersection point should be O(1) to compute?
So kC4 + kC2 + 4 points to check?
Where k is num sensors
Sleepy and not necessarily reasoning straight. You can check the 4 corners and the k choose 2 intersection points (actually 2 points per intersecting squares)
If intersection is a line discard
Yeah for squares the intersection is like (xMax1, yMin2) and (xMin2, yMax1) if the second square is up and to the right of the first. Different combinations depending on relative position
If they intersect at points of course
Ignore intersections outside the bounding box also
e
I think that fails if you have a cluster of sensors that are sitting directly on top of their beacons, e.g.
Copy code
##S##
#S.S#
##S##
(with the additional 
#
coming from outside)
d
I don't think collisions are allowed?
e
I thought the only restriction is that there aren't ties on which beacon is closer
d
But actually doesn't matter
That beacon is at an intersection
e
doesn't it? their intersections are lines
d
No the bounding boxes are the 8 points around each S
e
ah, I did not understand your intention. that still doesn't really make sense to me but anyhow…
d
Hmm maybe not let me go back to diamond space
Ah they aren't squares when rotated
In your example the diamond is 4 points
Maybe it just doesn't transform to a square for Manhattan distance = 1?
May try this later
j
anyways I’m happy as today was my first time for a loooong time, when I used a tailrec. It was not needed, but fun anyway.
splitting_longRange.kt
j
I'm still not happy about the language today. Is there really no way how to specify which overloaded 
plus
function to invoke in Kotlin? I.e. if I have a collection/set of iterables, how do I add next element? Having to wrap the arg in extra set just to have the method unwrap it and add the element I need seems like an unnecessary overhead. I must be missing something as I find it hard to believe that this is how it should work 🤔
m
You can do 
val k = x.plus((1..1) as Any) as Set<IntRange>
😛
j
that's not really nice and I end up with unchecked cast in code that should be perfectly Ok :(
e
use 
.plusElement()
if need to add an iterable as a single element
c
You can get around having to to check the entire L1 - circle if you take advantage of geometry. This code runs both part 1 and 2 in 136.243400ms (including reading input file):
Day15.kt
n
The past three days' challenges have been undertaken while travelling internationally across 8 time zones while taking care of two kids by myself and doing stuff with family. So let's just say I'm grateful for how easy the past couple days' challenges have been. Part 2 gave me a scare today though. I had visions of that brutal set theory challenge from last year. But it turns out my Part 1 algo was efficient enough to stick it in a sequence and have it pop out an answer on my 2011 laptop in 4 seconds. And no, I'm not optimizing it any time soon!
c
Basic idea: since the point is unique, it must be surrounded on all sides by blocked squares, and must therefore have 4 sensors on each side blocking all its neighbours. Each two diagonal sensors pairs must create two lines either side of the distress beacon, flanking it, and therefore, the distance between each diagonal pair's points must be the sum of the taxicab radius of each sensor. These 'opposing pairs' are the candidate points for either the top-left -> bottom-right diagonal axis (leaning left) or top-right -> bottom-left diagonal axis (leaning right), with the intersection of them being the distress beacon. Taking the different radius values into account, you get a set of short lines, that you can use y = mx + c to find intercepts between, and then filter.
Properly optimized it would be O (sensor^2) as you had to do lots of double iterations.
e
to be "correct", that should have a scan around the perimeter as well, since it wouldn't be by a 4-way intersection
c
That's true, I didn't take the (0,4million) boundary conditions into account, but the basic algorithm wouldn't change, you'd simply have to add those extra lines at the boundary and then find any intersections.
m
m
Optimized mine a little more. Since the point is touching the sensor ranges on both sides, I only had to check half of the perimeter on each sensor, since it would be found anyway (1/4th would be probably enough, but that wouldn’t shorten the code). Now runs in 77ms.
d
Finally solved it, took me quite a while and it was quite a journey...
I started with a very naive approach which worked for part 1, not so much for part 2, silly me tried to iterate over a gazillion points in the 4M by 4M grid to find the right one... Even trying to cheat with parallelism / coroutines didn't work so I definitely needed a new approach. Then I took a closer look at the example and saw the nice diamond shape that was formed by the sensor and the beacon at its edge, hmmm So I thought: "what if I generate a sequence of points just outside the range for each sensor?" The reason I thought this would work was that we were only looking for exactly 1 point, so it had to be just outside of a boundary, otherwise there would have been many such points. After I wrote some crummy code which did just that, it was relatively straightforward. At that point I just needed the first point which was not inside another's region (the check for that was pretty simple). Finally, after narrowing the search space down from a gazillion to only those points right outside the boundaries, it finally worked. :)
I ended up with mathematically not the most elegant solution, but a pretty straightforward one, one that is easy to visualize in any case 🙂
e
well good job me. I took several hours to write a rotated 2-D quadtree, and it turns out to be about twice as slow as my 1-D interval tracking
j
I just finished with 45-rotation and it works flawlessly under a few millis 🙂 anyway, it’s independent of the grid size, just a number of sensors, squared (I think) https://github.com/jakubgwozdz/advent-of-code-2022/blob/main/src/main/kotlin/day15/Day15.kt
(Silent assumption is that the broken beacon is somewhere between all the sensors and not on the outside)
e
I was stubbornly going with approaches that find all the interior points even if there's more than one. but I think I am am losing hope on making it go fast
a shame, it was kind of a slog to get right but I like how the code worked out… https://github.com/ephemient/aoc2022/commit/448b586ad2c5555be990725734d8e5ceb1007384
o
ç
k
This is the probably the most confusing coding description yet. Could someone explain how we can find the non-beacon spots for "row where y=2000000" when the test data only describes positions for sensors/grids that goes only up to row 22? (trying not to look at answers for clues yet) Seems like there would be no sensor/beacon info, so you it's just the width of a row? 🤔
k
d
@kenkyee your actual input should cover rows up to 2000000, the test data looks at row y=10
k
Has anyone benchmarked ⏱️ this task? I would be interested if you share.
o
My second solution ran in about 3 seconds. I looped for all 0..4000000 rows and stored start and end coordinate that cannot have a beacon.
j
Not sure how to compare benchmarks but 
measureTimeMillis
(on my old i5-750) returns 2 for for part 1 and 3105 for part 2
m
77ms for my part 2
d
My measureTimeMillis took about a second fort part 2, after initialization, there was no elegant math, only getting the outlines of each region and finding the first point among those outlines that wasn't in another's region
c
Yeah I didn’t think it was gonna work for part 2… Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
Still, gotta try, eh? 🙂
l
Finally got a working solution for part 2 that I'm mostly happy with. Takes ~10ms now. https://github.com/TheMrMilchmann/AdventOfCode2022/blob/502fa1c74a2115b06a3379a4bac2fc05eedb3f99/src/main/kotlin/days/Day15.kt#L84
The approach is similar to something that has been mentioned earlier in this thread: I'm using the "outlines" of the sensors and the search box and search pairwise for intersections. Unfortunately, I had to resort to floating point arithmetic when calculating the intersection because I couldn't find the bug in my integral approach. This doesn't seem to be a problem with my input though. 🙂
d
@Leon Linhart instead of using find with !!, you can use first {} 😉
k
Unfortunately, I only thought about the outer contour late after seeing such quick solutions. I used brute force with good optimization. Congratulations to those who have found the best solution!
r
I spent a long time trying to figure out why my solution (part 1) would work perfectly for the example but would give a too low answer for the input... Until I ultimately figured out that the input also has negative coordinates which were filtered out by my regex matching... (that'll teach me to not accidentally accept bad input by trying to be defensive in a bad way using 
mapNotNull { lineRegex.matchEntire(it)?.destructured }
instead of just 
map { lineRegex.matchEntire(it)!!.destructured }
...) 🤦
m
Puzzle inputs are always well-formed, so your code should fail fast, and in a bad way, if something’s not as expected. Use assertions liberally if in doubt, to confirm assumptions you make about what’s happening.
r
yeah usually I don't let this happen, but this one caught me off guard 😅
m
@Karloti When the puzzle unlocked, I managed to implement part 1 rather quickly (rank ~500). Then my daughter woke up, and there was no time for part 2. When I finally resumed working on part 2 two hours later, I had found the solution by thinking it through while doing other things. So the forced break spared me the usual trial and error 😉
j
First time I got emotional
I stumbled on the finish line with overflow on int
Luckily we already had that lesson..
Using outlines was very smart, I didnt do that, and I didnt brute force either , thinking that the numbers would be too big for that
I constructed intranges for each row and checked if there was a gap anywhere
Writing these was half the work of part 2
a
Impressive thinking @Leon Linhart, compare to other solution its a factor 100 of performance 😂 Nice job 👍
t
I thought that one was difficult, especially part two. My solution isn’t the fastest, but I can understand and explain it and that’s what counts for me. Basically, we’re trying to find a spot that is out of range of every sensor. So for every sensor, generate all of the spots just outside its visible range. Test all those against every other sensor and if none of them can see it either, that’s the answer. • Blog • Code
p
I tried a solution similar to @Leon Linhart’s but managed to get some integer line intersection working (at least it solves my part2 correctly). Speed differences between the three solutions I have now are entertaining (after 3 iterations warmup):
Copy code
year 2022 day 15 part 2
	 BorderIntersection took 480.014us: 10553942650264
	 Scanning took 519.397499ms: 10553942650264
	 Default took 2.831743944s: 10553942650264
x
Was stuck for the longest time in part 2. I think i would be stuck forever if it wasn't for the clue from @Marcin Wisniowski. Checking only the borders made so much sense.
Copy code
.........@#@......................... -10
........@###@........................ -9
.......@#####@....................... -8
......@#######@.............@........ -7
.....@#########@...........@#@....... -6
....@###########@.........@###@...... -5
...@#############@.......@#####@..... -4
..@###############@.....@#######@.... -3
.@#################@.@.@#########@... -2
@###################@#@###########@.. -1
##########S########################@. 0
@###########################S#######@ 1
.@###################S#############@. 2
..@###################SB##########@.. 3
...@#############################@... 4
....@###########################@.... 5
.....@#########################@..... 6
......@#########S#######S#####@...... 7
.......@#######################@..... 8
......@#########################@.... 9
.....@####B######################@... 10
....@###S#############@###########@.. 11
.....@#############################@. 12
......@#############################@ 13
......@#############S#######S######## 14
.....@B#############################@ 15
....@############SB################@. 16
...@##################S##########B@.. 17
..@#######S######################@... 18
...@############################@.... 19
....@#############S######S######@.... 20
.....@#########################@..... 21
......@#######@@#############B@...... 22
.......@#####@..@###@@#######@....... 23
........@###@....@#@..@#####@........ 24
.........@#@......@....@###@......... 25
..........@.............@#@.......... 26
13 Views
Open in Slack
PreviousNext
Powered by