+/AoC
advent of code
git clone https://git.julia.blue/+/AoC
a7718a0
master
1from itertools import product ,count 2from collections import deque 3 4grid = open ("input" ).read ().splitlines () 5nodes = set (product (range (len (grid )),range (len (grid [0 ])))) 6for y ,x in nodes : 7if grid [y ][x ]== "S" : 8end = (y ,x ) 9grid [y ]= grid [y ][:x ]+ "a" + grid [y ][x + 1 :] 10elif grid [y ][x ]== "E" : 11start = (y ,x ) 12grid [y ]= grid [y ][:x ]+ "z" + grid [y ][x + 1 :] 13 14adj = {} 15for y ,x in nodes : 16neighbors = set () 17for dy ,dx in ((- 1 ,0 ), (1 ,0 ), (0 ,- 1 ), (0 ,1 )): 18a = y + dy 19b = x + dx 20if (a ,b )in nodes and ord (grid [y ][x ])- 1 <= ord (grid [a ][b ]): 21neighbors .add ((a ,b )) 22adj [(y ,x )]= neighbors 23 24# def showpath(path): 25# for y in range(len(grid)): 26# for x in range(len(grid[0])): 27# c = f"\x1b[1m{grid[y][x].upper()}\x1b[0m" if (y, x) in path else grid[y][x] 28# print(c, end="") 29# print() 30 31 32def bfs (adj ,cond ): 33visited = {start :None } 34q = deque ([(start ,0 )]) 35while q : 36cur ,dist = q .popleft () 37if cond (cur ): 38# path = [cur] 39# while cur := visited[cur]: 40# path.append(cur) 41# showpath(path) 42return dist 43for n in adj [cur ]: 44if n not in visited : 45visited [n ]= cur 46q .append ((n ,dist + 1 )) 47 48 49bfs (adj ,lambda x :x == end )) 50bfs (adj ,lambda x :grid [x [0 ]][x [1 ]]== "a" ))