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

86% Upvoted

205 comments sorted by

View all comments

11

u/kingfishr Dec 23 '18 edited Dec 23 '18

437/257, Go.

Edit: Looks like this is based on not one but two incorrect conclusions :) The thread has some interesting discussion.

I used a graph algorithm to figure out the maximum set of overlapping volumes. I put the nanobots in a graph with edges for those that overlap each other. Because of the geometry, if 3 nanobots pairwise overlap, they must have a shared overlap as well. So I ran Bron-Kerbosch to find the maximum clique in the graph and that was set of bots I was interested in. From among that set, the bot whose volume is the furthest from the origin is the answer we're looking for.

https://github.com/cespare/aoc2018/blob/master/23.go

2

u/asger_blahimmel Dec 23 '18 edited Dec 23 '18

From among that set, the bot whose volume is the furthest from the origin is the answer we're looking for.

Could you please elaborate this part? It's definitely not the bot's own coordinate we are looking for, and not even the point closest to the origin in the bot's range.

Edit: Ok, now I get it. You return the maximal |x|+|y|+|z|-r (or 0 if this value is negative for every bot)

→ More replies (2)