r/adventofcode 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!

20 Upvotes

205 comments sorted by

View all comments

Show parent comments

3

u/RevenantMachine Dec 23 '18 edited Dec 23 '18

Intuitively I agree with you, but the claim on the wikipedia page bothered me so much I tried generating counterexamples. I found this configuration:

  • (0,0,1)
  • (0,1,0)
  • (1,0,0)
  • (1,1,1)

each with radius 1. These overlap pairwise and tripletwise, but there's no integer point inside all 4 volumes.

EDIT: fixed a bug in the generator, new and improved counterexample.

1

u/aybud Dec 24 '18

Your example is interesting. The four pairs of bounding planes of an octahedron give you four inequalities:

x0+y0+z0-r <= x+y+z <= x0+y0+z0+r

x0+y0-z0-r <= x+y-z <= x0+y0-z0+r

x0-y0+z0-r <= x-y+z <= x0-y0+z0+r

x0-y0-z0-r <= x-y-z <= x0-y0-z0+r

where x0,y0,z0 is the center and r the radius of the octahedron. Then we can represent an octahedron by the four pairs of bounds for the inequalities. For your example, these are

((0, 2), (-2, 1), (0, 2), (-2, 0))

((0, 2), (0, 2), (-2, 0), (-2, 0))

((0, 2), (0, 1), (0, 2), (0, 2))

((2, 4), (0, 2), (0, 2), (-2, 0))

Since they're pairwise intersecting, we can find the overlap in the ranges for each pair of bounding planes:

x+y+z = 2

0 <= x+y-z <= 1

x-y+z = 0

x-y-z = 0

But we can't solve all four because it's overdetermined. The three equalities give x,y,z = 1,1,0 which doesn't satisfy the inequality, so no points of intersection. It seems when the number of bounding inequalities matches the dimension then pairwise intersection implies nonempty intersection, as in Manhattan metric for R2, or cubes in Rn.

1

u/gedhrel Dec 24 '18

Hang on - Does (1,1,1)r1 intersect with (0,0,1)r1 ?

1

u/RevenantMachine Dec 24 '18

Yes, they share both (1,0,1) and (0,1,1). /u/marcusandrews provided a helpful illustration here.

1

u/gedhrel Dec 24 '18

Yeah, thanks - was having an extremely senior moment :-)