+/AoC

advent of code

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

Julia RyanDay 2017596f1

master
1.6 KiB59 linesraw
1from heapq import heappop, heappush
2from collections import Counter
3
4board = set()
5start = end = (0, 0)
6with open("input") as f:
7    for y, line in enumerate(f.readlines()):
8        for x, c in enumerate(line):
9            pos = (x, y)
10            match c:
11                case ".":
12                    board.add(pos)
13                case "S":
14                    board.add(pos)
15                    start = pos
16                case "E":
17                    board.add(pos)
18                    end = pos
19
20dists = {}
21todo = [(0, end)]
22while todo:
23    n, pos = heappop(todo)
24    dists[pos] = n
25    x, y = pos
26    for new in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
27        if new in board and new not in dists:
28            heappush(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)
36    for x in range(-n, n + 1)
37    for y in range(-n, n + 1)
38    if 1 < dist((0, 0), (x, y)) <= n
39}
40
41m2 = manhattan(2)
42m20 = manhattan(20)
43for x, y in board:
44    start = (x, y)
45    for dx, dy in m2:
46        pos = (x + dx, y + dy)
47        if pos in board:
48            saved = dists[start] - dists[pos] - dist(start, pos)
49            p1[saved] += saved > 0
50    for dx, dy in m20:
51        pos = (x + dx, y + dy)
52        if pos in board:
53            saved = dists[start] - dists[pos] - dist(start, pos)
54            p2[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")
58print(sum((v for k, v in p1.items() if k >= 100)))
59print(sum((v for k, v in p2.items() if k >= 100)))