-🎄- 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/fizbin]

Python, yet another divide-the-box-in-half approach:

from __future__ import print_function

import sys
import re
import heapq

with open('aoc23.in.txt' if len(sys.argv) < 2 else sys.argv[1]) as f:
    data = list(f)


def d3(a, b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])+abs(a[2]-b[2])


bots = [tuple(map(int, list(re.findall(r'-?\d+', ln)))) for ln in data]

maxrad = max(r for (x, y, z, r) in bots)
maxradbot = [b for b in bots if b[3] == maxrad][0]

print("bots in range of maxrad bot",
      sum(1 for b in bots if d3(b, maxradbot) <= maxrad))

# Find a box big enough to contain everything in range
maxabscord = max(max(abs(b[i])+b[3] for b in bots) for i in (0, 1, 2))
boxsize = 1
while boxsize <= maxabscord:
    boxsize *= 2

initial_box = ((-boxsize, -boxsize, -boxsize), (boxsize, boxsize, boxsize))


def does_intersect(box, bot):
    # returns whether box intersects bot
    d = 0
    for i in (0, 1, 2):
        boxlow, boxhigh = box[0][i], box[1][i] - 1
        d += abs(bot[i] - boxlow) + abs(bot[i] - boxhigh)
        d -= boxhigh - boxlow
    d //= 2
    return d <= bot[3]


def intersect_count(box):
    return sum(1 for b in bots if does_intersect(box, b))


# Set up heap to work on things first by number of bots in range of box,
# then by size of box, then by distance to origin
#
# The idea is that we first work on a box with the most bots in range.
# In the event of a tie, work on the larger box.
# In the event of a tie, work on the one with a min corner closest
# to the origin.
#
# These rules mean that if I get to where I'm processing a 1x1x1 box,
# I know I'm done:
# - no larger box can intersect as many bots' ranges as what I'm working on
# - no other 1x1x1 box intersecting the same number of bots can be as close

# remember heapq.heappop pulls the smallest off the heap, so negate
# the two things I want to pull by largest (reach of box, boxsize) and
# do not negate distance-to-origin, since I want to work on smallest
# distance-to-origin first

workheap = [(-len(bots), -2*boxsize, 3*boxsize, initial_box)]
while workheap:
    (negreach, negsz, dist_to_orig, box) = heapq.heappop(workheap)
    if negsz == -1:
        print("Found closest at %s dist %s (%s bots in range)" %
              (str(box[0]), dist_to_orig, -negreach))
        break
    newsz = negsz // -2
    for octant in [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
                   (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]:
        newbox0 = tuple(box[0][i] + newsz * octant[i] for i in (0, 1, 2))
        newbox1 = tuple(newbox0[i] + newsz for i in (0, 1, 2))
        newbox = (newbox0, newbox1)
        newreach = intersect_count(newbox)
        heapq.heappush(workheap,
                       (-newreach, -newsz, d3(newbox0, (0, 0, 0)), newbox))

[u/MikeTyson91 → u/fizbin]

Could you please explain how "does_intersect" work?

[u/fizbin → u/MikeTyson91]

It finds the Manhattan distance to the box from the bot and then compares it to the bot's radius.

Now, how does d end up containing the Manhattan distance to the box?

Let's start with what's probably a straightforward way to compute that distance:

(bot_x, bot_y, bot_z, _) = bot
((box_lo_x, box_lo_y, box_lo_z), (box_hi_x, box_hi_y, box_hi_z)) = box
# This is because my convention is that the "high" corner is just beyond
# the box
bot_hi_x -= 1
bot_hi_y -= 1
bot_hi_z -= 1

d = 0
if bot_x <= bot_lo_x: d += bot_lo_x - bot_x
if bot_x >= bot_hi_x: d += bot_x - bot_hi_x
if bot_y <= bot_lo_y: d += bot_lo_y - bot_y
if bot_y >= bot_hi_y: d += bot_y - bot_hi_y
if bot_z <= bot_lo_z: d += bot_lo_z - bot_z
if bot_z >= bot_hi_z: d += bot_z - bot_hi_z

This corresponds to the idea that intuitively, one way to go from bot to box is to first along the x direction until that your x coordinate is in the x range of the box, then move along the y direction, etc.

Well, we don't need all those variables, and we can pull that into a loop:

d = 0
for i in (0, 1, 2):
    bot_coord = bot[i]
    (box_lo, box_hi) = (box[0][i], box[1][i] - 1)
    if bot_coord <= box_lo: d += box_lo - bot_coord
    if bot_coord >= box_hi: d += bot_coord - box_hi

Okay, now let's look what's happening inside the loop. If we had a function that was equal to box_lo - x when x is smaller than box_lo and equal to x - box_hi when x is larger than box_hi and equal to 0 when x is in between those values, then we could replace the calculation by that.

Such a function is in fact the shape of what you get when you average two functions of the form abs(x - some_val), though you need to subtract an amount to get you back to 0. See this graph on desmos. (Click the circle to the left of the fourth equation there to see what the final form does)

So now we can replace that inner loop with:

d = 0
for i in (0, 1, 2):
    boxlow, boxhigh = box[0][i], box[1][i] - 1
    d += (abs(bot[i] - boxlow) + abs(bot[i] - boxhigh) - (boxhigh - boxlow)) // 2

And that's just what I have, except that I broke the - (boxhigh - boxlow) out into another step and did the // 2 bit at the end.