day19.py

from advent import get_data, mkparse
from collections import defaultdict
from itertools import combinations, permutations, product

# these helpers are also in advent but copying them here because they're small
def sub_pos3(x, y):
  a, b, c = x
  d, e, f = y
  return (a - d, b - e, c - f)

def sum_pos3(x, y):
  a, b, c = x
  d, e, f = y
  return (a + d, b + e, c + f)

def manhattan_dist(pos1, pos2=None):
  if pos2 is None:
    pos2 = [0] * len(pos1)
  return sum(abs(a - b) for (a, b) in zip(pos1, pos2))

data = get_data(19, year=2021, sep='\n\n')

with open("2021/day19_test.txt", "r") as f:
  test_data = f.read().strip().split('\n\n')

import sys
if "--test" in sys.argv:
  data = test_data

scanner_inputs = []
for inp in data:
  scanner_inputs.append(
    list(map(mkparse("{:d},{:d},{:d}"), inp.split('\n')[1:]))
  )

scanners = {
  0: (0, 0, 0)
}

beacons = set(scanner_inputs[0])

already_tried = defaultdict(set)
from itertools import permutations, product 
def try_to_assign(sidx):
  global beacons
  for perm in permutations(range(3)):
    for muls in product([-1, 1], [-1, 1], [-1, 1]):
      new_candidates = []
      for b in scanner_inputs[sidx]:
        new_candidates.append((
          b[perm[0]] * muls[0],
          b[perm[1]] * muls[1],
          b[perm[2]] * muls[2]
        ))

      possibles = beacons - already_tried[sidx]
      for c in new_candidates:
        for b in possibles:
          shift_amt = sub_pos3(b, c)
          tried = set(map(lambda z: sum_pos3(z, shift_amt), new_candidates))
          if len(tried & beacons) >= 12:
            beacons |= tried
            scanners[sidx] = shift_amt
            return True

  already_tried[sidx] |= possibles

  return False

unassigned_scanners = set(i for i in range(len(scanner_inputs)) if i not in scanners)

# My successful run did them in this order, save this in case it becomes faster to run it later
# elim_order = [1, 25, 19, 3, 16, 8, 5, 7, 14, 12, 18, 15, 17, 20, 21, 22, 23, 9, 26, 29, 31, 28, 10, 24, 36, 30, 4, 27, 2, 13, 33, 6, 11, 35, 32, 34, 37, 38, 39]
while unassigned_scanners:
  print(unassigned_scanners)
  for scanner in unassigned_scanners:
    did_it = try_to_assign(scanner)
    if did_it:
      unassigned_scanners.remove(scanner)
      break
  else:
    print("uh-oh...", unassigned_scanners)
    assert False

print(len(beacons))

# when I realized how long this took to run, I decided to cache the result.
# Sadly I had a bug in my position computation so it ended up not being useful anyway :|
# import json
# with open("2021/beacons.json", "w") as f:
#   f.write(json.dumps({"scanners": scanners, "beacons": list(beacons)}))

print(max(
  manhattan_dist(a, b) for (a, b) in combinations(scanners.values(), 2)
))