+/AoC

advent of code

git clone https://git.julia.blue/+/AoC

Joseph RyanDays 15-186e46de2

master
1.2 KiB43 linesraw
1import re
2from functools import reduce
3from collections import defaultdict
4
5p = re.compile(".*x=(.+), y=(.+):.*x=(.+), y=(.+)")
6combine = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
7intersect = lambda a, b: (max(a[0], b[0]), min(a[1], b[1]))
8overlap = lambda a, b: a[1] >= b[0] and a[0] <= b[1]
9
10
11def add(new, ranges):
12    x, y = new
13    overlapping = {new}
14    for r in ranges:
15        a, b = r
16        if a <= x and b >= y:
17            return
18        if y < a - 1 or x > b + 1:
19            continue
20        overlapping.add(r)
21    ranges -= overlapping
22    new = reduce(combine, overlapping)
23    ranges.add(new)
24
25
26target = 4_000_000
27rows = [set() for _ in range(target + 1)]
28beacons = set()
29for line in open("input"):
30    a, b, x, y = map(int, p.match(line).groups())
31    size = abs(a - x) + abs(b - y)
32    vert = intersect((b - size, b + size), (0, target))
33    for i in range(vert[0], vert[1] + 1):
34        diff = abs(size - abs(b - i))
35        add((a - diff, a + diff), rows[i])
36    if y == target // 2:
37        beacons.add(y)
38
39print(sum((b - a + 1 for a, b in rows[target // 2])) - len(beacons))
40for i in range(target + 1):
41    inside = sorted(filter(lambda r: overlap(r, (0, target)), rows[i]))
42    if len(inside) > 1:
43        print(i + (inside[0][1] + 1) * target)