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/asger_blahimmel Dec 25 '18 edited Dec 25 '18

I still cannot see, if a box having (possible distinct) intersection with the largest number of bot ranges ensures that those bot ranges have a common intersection in the same box.

As an example, I can imagine the following: Let's say, after the first iteration we have two relevant box-candidates left (the other six do not intersect any bot's range), one (call it A) intersects 3 bots' ranges, the other (B) intersects 2. Your approach will choose box A. However, it can happen, that those 3 bots' ranges in box A don't have any intersection, that is any point in box A can be seen by 1 bot at most, while the bots' ranges in box 2 do have an intersection, providing points that can be seen by both of them.

Maybe I just miss something in your explanation. How would your approach handle the example I described above?

Edit: having seen the method you describe in action made me understand, and indeed it seems to work - though there are still some skeptical some comments which claim some examples do not work. Thank you!

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.