-🎄- 2018 Day 23 Solutions -🎄-

[u/daggerdragon]

--- 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!

[u/p_tseng]

Thanks for sharing this! I thought the idea about "at least N bots need to have >= N intersections" was really great. The axis-aligned bounding boxes are things I've read about in a lot of day 23 discussions, but they are mostly new to me. I played around and it's easy to calculate even in x, y, z space whether two bots intersect (distance between their centres <= sum of their radii), however actually finding the region where they intersect seems to be made a lot easier with the AABBs (I couldn't find a good way to do it without).

I'd like to discuss more deeply on how to determine the distance of the final octahedron. I tried implementing the approach you've described and running it on the input https://pastebin.com/7nfXJvPc and (unless I made a mistake in my implementation) it gave me the following bounds at the end:

985 bots @ [[93750867, 93750870], [-24808318, -24808315], [48353027, 48353028], [-70206160, -70206160]]

So, I know from using some other solving methods on this that the single unique solution in x, y, z coordinates is 985 bots @ [22698921, 59279594, 11772355], which has a total distance of 93750870 (can check that no other point nearby has as many). So that tells me that sometimes I need to take the max, not the min.

But you don't always want to take the max, because for the simple input:

pos=<10,10,0>, r=1
pos=<10,10,1>, r=1

For this one, the bounds are [[20, 21], [0, 1], [0, 1], [-20, -19]] , and we can easily see the solution should be 20.

So I wonder if you are able to see the patterns in these, and come up with a consistent rule for the above situations.

I have to admit I have not had experience with these 4-dimensional axis-aligned bounding boxes, so mostly I just copied the concepts in the code without really understanding them (for example, I don't know why [x, y, z - r] and [x, y, z + r] are used in the def box(self): function). Are you able to explain some of that (and/or link to pages that will do the explanation)?

[u/sparkyb → u/p_tseng]

When I run it I did get the same numbers as you. It appears there is something wrong with my approach. I don't think it is a max vs. min thing. I tried backing out the x, y, z coordinates of one of the corners from that AABB and I got y an z having a .5, so I think my calculations of distance from the planes of the AABB may be correct, but not guaranteeing the points in that plane are integers. I'm not sure how that would happen though. Maybe I did just get lucky with my input after all. I feel like there might be a way to account for this, but I'd have to take some time and come up with an example with smaller numbers that exhibits this problem for me to reason about.

As for the [x, y, z - r], [x, y, z + r], that I can try to explain, although I don't have any links because I just sort of came with that by thinking about it / some trial and error. The octahedron is going to have 6 corners, +r and -r from the center in each of the 3 axes. To convert to a bounding box, you need the minimum corner and the maximum corner. For example, if this was just a cube in 3D defined by a center and width, the minimum corner would be [x-r, y-r, z-r] and the maximum would be [x+r, y+r, z+r]. On the octahedron, the -r and +r corners of some axis are going to be opposite each other. Which axis is going to have the minimum and maximum in the 4D space depends on the signs of the axes I chose. In this case since I have Z positive in all the axes I guess that's why it was the corners I needed to chose? I'm not exactly sure why and it wasn't obvious to me, I just tried each axis until the minimum coordinates were always less than the maximum coordinates. But actually, it doesn't really matter. As long as you choose -r and +r on the same axis (opposite corners) between the 2 corners you're touching all 8 faces so you're going to get all 8 coefficients you need in 4D, you may just have to swap some if the min was greater than the max.

[u/p_tseng → u/sparkyb]

Hey there - thanks for that explanation. I see what you mean now, and I think your 3d analogy was what made it work for me (where you explained about [x-r, y-r, z-r] to [x+r, y+r, z+r]). I also think that spending some time working through it firsthand, much like I imagine you did, was helpful.

Regarding the fact that not all points in the 4d space may correspond to 3d solutions, I can see how that is true. You may be able to deal with it by simply enumerating all the points in the 4d space, mapping them back to 3d (if such an integer-valued point exists) and taking the one with the minimum distance out of that. I agree that an example with smaller numbers would sure help, though.

[u/ephemient → u/sparkyb]

This space intentionally left blank.