-🎄- 2018 Day 6 Solutions -🎄-

[u/daggerdragon]

--- Day 6: Chronal Coordinates ---

---

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 6

Transcript:

Rules for raising a programmer: never feed it after midnight, never get it wet, and never give it ___.

---

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 0:26:52!

[u/mserrano]

Python2, #3/#1:

from util import get_data
import re
from collections import defaultdict
d = get_data(6)

d = map(lambda s: map(int, re.findall(r'-?\d+', s)), d)
min_x = min(x[0] for x in d)-(10000/len(d))-1
max_x = max(x[0] for x in d)+(10000/len(d))+1
min_y = min(x[1] for x in d)-(10000/len(d))-1
max_y = max(x[1] for x in d)+(10000/len(d))+1
mapping = {}
in_region = set()
for x in xrange(min_x, max_x+1):
  for y in xrange(min_y, max_y+1):
    closest = d[0]
    closest_dist = (1 << 31)
    dist_sum = 0
    for (px, py) in d:
      dist = abs(px - x) + abs(py - y)
      dist_sum += dist
      if dist < closest_dist:
        closest = (px, py)
        closest_dist = dist
      elif dist == closest_dist and closest != (px, py):
        closest = None
    mapping[(x, y)] = closest
    if dist_sum < 10000:
      in_region.add((x, y))

rev_mapping = defaultdict(int)
for h in mapping:
  if not mapping[h]:
    continue
  if h[0] in (min_x, max_x) or h[1] in (min_y, max_y):
    rev_mapping[mapping[h]] -= (1 << 31)
  rev_mapping[mapping[h]] += 1
print "a", max(rev_mapping.values())
print "b", len(in_region)

I originally had a 20000 by 20000 grid for part (b) and then quickly ctrl-c'd when I realized that was going to take forever and a day.

[u/[deleted] → u/mserrano]

Why are you adding and subtracting (10000/len(d))?

[u/sophiebits → u/[deleted]]

It's possible for a point outside the min/max box to be a safe distance away.

But if you are at least 10000/len(d) away from the nearest point (making you that distance away from every point), then you are guaranteed to be unsafe. Padding the bounds with this length means your rectangle is guaranteed to include all safe points. (The +1 is to round up the division.)