Unable to load image

day 15 thread of aoc i guess lol: diamonds are forever

see leaderboard on geeses post

33
Jump in the discussion.

No email address required.

Pseudo brute force solution :marseybrainlet: (runtime: 5 minutes)

On the X axis i jump to the edge of the beacon i detect

![](/images/1671107429901418.webp)

Jump in the discussion.

No email address required.

is there even a more clever way to do this that would guarantee much faster? searching the edges maybe? but like isn't that basically what ur doing already?

though mine only took 1.5s to run with this optimized brute force, i can't imaging waiting 5 mins for an answer.

Jump in the discussion.

No email address required.

You can use algebra if you are clever :marseyangel:

C:\dev\personal\aoc> python .\15-clean.py
(3446137, 3204480)
TIME: 0.0009992122650146484s
Jump in the discussion.

No email address required.

i think you can get the borders of each diamond, expand them by one, then find a spot where 4 exapanded borders of different diamonds intersect and then check if that point is contained by any other diamond.

If it is not contained, this is the point you want. Should be like O(m^4) with m being the amount of sensors in the input

Alternative you could define a rectangle. Then you check if the entire rectangle is fully contained by diamonds (e.g. are the 4 corners contained by one diamond), if yes you can discard the rectangle, if no you split the rectangle into 4 smaller rectangle and repeat the procedure.

You should be left with one 1x1 rectangle of your point.

Jump in the discussion.

No email address required.

I considered the border of two diamonds a line, and then found all intersections of all the lines. There were only four borders (because only four diamonds were separated by a thin strip) so that ended up being four total intersections.

https://stupidpol.site/h/programming/post/131561/day-15-thread-of-aoc-i/3250317?context=8#context

Jump in the discussion.

No email address required.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.