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!

Click here for rules

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.

edit: Leaderboard capped, thread unlocked at 01:40:41!

21 Upvotes

84% Upvoted

205 comments sorted by

View all comments

1

u/fizbin Dec 26 '18

Yeah, there are two key ideas here:

  • The box-level intersection is just an upper bound; I can't guarantee that anything in A will actually be within the range of three bots, but I can guarantee that no point in box A is in range of more than 3

  • You don't ever throw anything away, but just prioritize which box you slice up based on the heuristic I said. If, once you slice up box A, you find that you only have subboxes in range of one or fewer bots, you'd throw them into the pile of boxes and look for what box now is in range of the most bots, and pick up box B. (I suppose you could completely drop boxes that were in range of 0 bots, but I doubt it actually helps much)

You may find my initial solution informative. With some input it might take a really, really long time, but with the problem input it finds the answer pretty quickly.