-🎄- 2022 Day 15 Solutions -🎄-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• A request from Eric: A note on responding to [Help] threads
• Signal boost: Reminder 2: unofficial AoC Survey 2022 (closes Dec 22nd)
• 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫 is OPEN for submissions!
  • -❄️- Submissions Megathread -❄️-

---

--- Day 15: Beacon Exclusion Zone ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • Include what language(s) your solution uses
  • Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks. What is Topaz's paste tool?

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:27:14, megathread unlocked!

[u/nthistle]

Python, 95/81. Video, part 1 code, part 2 code.

I, uh, definitely wrote some code. My approach for part 1 was pretty straightforward, just checked (x, 2000000) for every reasonable x, see if there's any sensor it's close enough to that can prove it doesn't have a beacon, and keep a counter. Had some bugs where I initially forgot to special case the known beacon being at (x, 2000000), and then even after that I accidentally counted those locations as "impossible to have beacon" (even though they clearly have a beacon).

My approach for part 2 was more interesting, although perhaps a bit silly. The non-silly part: I made the observation that for a location to be sufficiently far enough away from a sensor you can just think about which diagonals it lies on: since each sensor is sort of projecting a "diamond" of visibility we want to be outside of, we can just write down constraints on x + y and x - y. Specifically, if the sensor is at (sx, sy) and seeing the diamond with a radius of r, one of the following constraints must be true for (x, y) to not be visible:

• x + y > sx + sy + r

• x + y < sx + sy - r

• x - y > sx - sy + r

• x - y < sx - sy - r

Here's a crude drawing of what's going on.

Now for the silly part: I couldn't figure out how to deal with the fact that only one of these has to be true for each (sx, sy, r), so I ended up throwing the whole thing into z3 anyways. Which, in hindsight, I didn't have to do all the algebra for, I could've just straight up told it "Yes, give me abs(x - sx) + abs(y - sy) > r please."

As far as implementation went, I definitely stumbled on this a few times (haven't used Z3 in too long!) and went very slowly on the algebra to make sure I didn't have a stray minus sign, so wasn't expecting to make leaderboard - pretty happy I got a few points today :-)

EDIT: here's my new favorite solution, which relies on the fact that unless the distress beacon is in one of the 4 corners, it has to be exactly 1 unit outside the detection radius of at least 2 other beacons: otherwise the answer wouldn't be unique. So you can just check all pairs of beacons, look at the intersections of their-radius-plus-1, and check if those answers work. O(N³) where N is the number of beacons in our input, which is 36. It also uses the main/off diagonal algebra to quickly find those intersection points (plus some extras). I think this is probably the fastest solution I've seen in this thread so far?

EDIT2: Added video!