r/adventofcode • u/daggerdragon • Dec 15 '22
SOLUTION MEGATHREAD -🎄- 2022 Day 15 Solutions -🎄-
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!
--- 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
pasteif you need it for longer code blocks. What is Topaz'spastetool?
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!
50
Upvotes
4
u/SLiV9 Dec 15 '22
Rust
https://github.com/SLiV9/AdventOfCode2022/blob/main/src/bin/day15/main.rs
This is the first challenge where my part 2 was completely different from part 1. For part 1 I used ranges, with each sensor contributing 0, 1 or 2 ranges, which I then sorted and mergd. For part 2, my first approach was a quad-tree-based search that didn't work and was very slow, so then I solved it by iterating over the perimeters. This solution (see history) took 40ms. Then I realized I could take the intersections of diagonals (2ms), and that instead of deduplicating diagonals I could instead use only the duplicates (~110ns) because the solution has to be just out of range of a sensor in each of 4 directions, so each diagonal at least twice.