| 32 | return i, (RegexType.LIST, r) |
| 33 | |
| 34 | def apply_regex(m: Graph, regex: Regex, coords: set[tuple[int,int]]) -> set[tuple[int,int]]: |
| 35 | match regex[0]: |
| 36 | case RegexType.SIMPLE: |
| 37 | newcoords = set() |
| 38 | for r,c in coords: |
| 39 | for d in regex[1]: |
| 40 | rr,cc = r,c |
| 41 | match d: |
| 42 | case 'N': r -= 1 |
| 43 | case 'S': r += 1 |
| 44 | case 'E': c += 1 |
| 45 | case 'W': c -= 1 |
| 46 | m[rr,cc].add((r,c)) |
| 47 | m[r,c].add((rr,cc)) |
| 48 | newcoords.add((r,c)) |
| 49 | return newcoords |
| 50 | case RegexType.OR: |
| 51 | return set.union(*(apply_regex(m,re,coords) for re in regex[1])) |
| 52 | case RegexType.LIST: |
| 53 | for re in regex[1]: |
| 54 | coords = apply_regex(m,re,coords) |
| 55 | return coords |
| 56 | |
| 57 | def bfs_distances(m: Graph) -> list[int]: |
| 58 | q, dist = deque([(0,0)]), {(0,0): 0} |