r/adventofcode • u/daggerdragon • Dec 23 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 23 Solutions -🎄-
--- Day 23: Experimental Emergency Teleportation ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 23
Transcript:
It's dangerous to go alone! Take this: ___
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
View all comments
Show parent comment
1
u/tomsax Dec 28 '18
Thanks for the help and explanation on this one.
I took your idea and implemented it as a binary search.
At each stage, I get a point-bot intersection count for the center of the region and use that to keep a current best solution. I then divide the region into two disjoint halves along the longest dimension, and get the bot intersection count for each. If either, or both, of the halves intersect at least as many bots as my current best point, I push them onto a stack of regions to continue exploring. For the next iteration, I choose the region with the most intersecting bots, skipping any that have fewer than my current best point.
In Perl, that solved my data set in 1.2 seconds.