+/AoC
advent of code
git clone https://git.julia.blue/+/AoC
6e46de2
master
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 ): 12x ,y = new 13overlapping = {new } 14for r in ranges : 15a ,b = r 16if a <= x and b >= y : 17return 18if y < a - 1 or x > b + 1 : 19continue 20overlapping .add (r ) 21ranges -= overlapping 22new = reduce (combine ,overlapping ) 23ranges .add (new ) 24 25 26target = 4_000_000 27rows = [set ()for _ in range (target + 1 )] 28beacons = set () 29for line in open ("input" ): 30a ,b ,x ,y = map (int ,p .match (line ).groups ()) 31size = abs (a - x )+ abs (b - y ) 32vert = intersect ((b - size ,b + size ), (0 ,target )) 33for i in range (vert [0 ],vert [1 ]+ 1 ): 34diff = abs (size - abs (b - i )) 35add ((a - diff ,a + diff ),rows [i ]) 36if y == target // 2 : 37beacons .add (y ) 38 39sum ((b - a + 1 for a ,b in rows [target // 2 ]))- len (beacons )) 40for i in range (target + 1 ): 41inside = sorted (filter (lambda r :overlap (r , (0 ,target )),rows [i ])) 42if len (inside )> 1 : 43i + (inside [0 ][1 ]+ 1 )* target )