+/AoC

advent of code

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

Joseph RyanDays 7-14 (in python for now)a7718a0

master
1.4 KiB50 linesraw
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:
7    if grid[y][x] == "S":
8        end = (y, x)
9        grid[y] = grid[y][:x] + "a" + grid[y][x + 1 :]
10    elif grid[y][x] == "E":
11        start = (y, x)
12        grid[y] = grid[y][:x] + "z" + grid[y][x + 1 :]
13
14adj = {}
15for y, x in nodes:
16    neighbors = set()
17    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
18        a = y + dy
19        b = x + dx
20        if (a, b) in nodes and ord(grid[y][x]) - 1 <= ord(grid[a][b]):
21            neighbors.add((a, b))
22    adj[(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):
33    visited = {start: None}
34    q = deque([(start, 0)])
35    while q:
36        cur, dist = q.popleft()
37        if cond(cur):
38            # path = [cur]
39            # while cur := visited[cur]:
40            #     path.append(cur)
41            # showpath(path)
42            return dist
43        for n in adj[cur]:
44            if n not in visited:
45                visited[n] = cur
46                q.append((n, dist + 1))
47
48
49print(bfs(adj, lambda x: x == end))
50print(bfs(adj, lambda x: grid[x[0]][x[1]] == "a"))