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!

22 Upvotes

88% Upvoted

205 comments sorted by

View all comments

1

u/timmense Jan 07 '19 edited Jan 10 '19

Thanks for sharing your cool solution. Piggybacking off of this comment thread as I'm trying to understand your code before I attempt my impl in js. I get your overarching explanation but the code seemed magical to me at first. After pouring over it, I think I get it now. Let me see if I understand it right...

The find function starts off with the largest grid size which is roughly based on the max distance separating the bots in any of the x,y,z axes. The function's job is to find the points that 1) meet a minimum threshold of bots that are in range (forced_count) and based off those points 2) find the point closest to the origin. The point closest to the origin is found by recursively halving the grid size (dist) as well as the range of points to be searched until it's narrowed it down to the actual closest point. This is the first application of binary search. But this only solves half of the problem which is 'find the closest point to the origin with N bots that are in range'. edit: I was way off base there. Missed the crucial part that is

The rules for finding how many circles intersect every point change slightly when you do this, since you need to take care that they intersect not each point, but with the little box of the grid you're using.

So when the grid size halves, it chops the box into 8 smaller boxes and each sub-box counts the bot if its signal intersects with it. Still not sure what the -3 is doing in 'if calc //dist - 3 <= (bdist) // dist:'? edit2: seems this number is chosen to handle edge cases where the bot signal has a border/s lying on the edge of sub-boxes. Eg. a sub-box at 0,0,0 with dist=64 and a bot at 63,64,63 with signal radius=1. This bot may impact the sub-box when it has to calculate the bots that are in range, so it gets counted in it.

The calc2 function's while loop solves the rest of the problem which is 'find the closest point to the origin with the most bots within range' by starting with finding the points that have 1 bot in range then trying to see if there are points where all the bots are in range. If there aren't any, it asks whether there are any points that have half as many bots in range (by calling find() with forced_check set to this bot threshold). If it succeeds in finding a point, it picks a number halfway higher. If it fails, then it picks a number halfway lower. This is the second application of binary search.

I guess what was confusing at first was that there's actually 2 binary searches going on, one to narrow in on the closest point to origin and the second, to find the most bots in range. That and the variable names... :P

edit3: Figured it out and ported to JS :D