+/AoC
advent of code
git clone https://git.julia.blue/+/AoC
17596f1
master
1from heapq import heappop ,heappush 2from collections import Counter 3 4board = set () 5start = end = (0 ,0 ) 6with open ("input" )as f : 7for y ,line in enumerate (f .readlines ()): 8for x ,c in enumerate (line ): 9pos = (x ,y ) 10match c : 11case "." : 12board .add (pos ) 13case "S" : 14board .add (pos ) 15start = pos 16case "E" : 17board .add (pos ) 18end = pos 19 20dists = {} 21todo = [(0 ,end )] 22while todo : 23n ,pos = heappop (todo ) 24dists [pos ]= n 25x ,y = pos 26for new in [(x - 1 ,y ), (x ,y - 1 ), (x + 1 ,y ), (x ,y + 1 )]: 27if new in board and new not in dists : 28heappush (todo , (n + 1 ,new )) 29 30p1 = Counter () 31p2 = Counter () 32 33dist = lambda a ,b :abs (a [0 ]- b [0 ])+ abs (a [1 ]- b [1 ]) 34manhattan = lambda n : { 35 (x ,y ) 36for x in range (- n ,n + 1 ) 37for y in range (- n ,n + 1 ) 38if 1 < dist ((0 ,0 ), (x ,y ))<= n 39} 40 41m2 = manhattan (2 ) 42m20 = manhattan (20 ) 43for x ,y in board : 44start = (x ,y ) 45for dx ,dy in m2 : 46pos = (x + dx ,y + dy ) 47if pos in board : 48saved = dists [start ]- dists [pos ]- dist (start ,pos ) 49p1 [saved ]+= saved > 0 50for dx ,dy in m20 : 51pos = (x + dx ,y + dy ) 52if pos in board : 53saved = dists [start ]- dists [pos ]- dist (start ,pos ) 54p2 [saved ]+= saved > 0 55 56# for k, v in sorted(((k, v) for k, v in p2.items() if k >= 50)): 57# print(f"• There are {v} cheats that save {k} picoseconds") 58sum ((v for k ,v in p1 .items ()if k >= 100 ))) 59sum ((v for k ,v in p2 .items ()if k >= 100 )))