summaryrefslogtreecommitdiff
path: root/23_2023.py
blob: 8607554c41dc1aa885bcec0a9a2debdc763a047d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
import heapq
import math

D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])

sys.setrecursionlimit(10**6)


def solve(part1):
    V = set()
    for r in range(R):
        for c in range(C):
            nbr = 0
            for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
                if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
                    nbr += 1
            if nbr > 2 and G[r][c] != "#":
                V.add((r, c))

    for c in range(C):
        if G[0][c] == ".":
            V.add((0, c))
            start = (0, c)
        if G[R - 1][c] == ".":
            V.add((R - 1, c))
            end = (R - 1, c)

    E = {}
    for rv, cv in V:
        E[(rv, cv)] = []
        Q = deque([(rv, cv, 0)])
        SEEN = set()
        while Q:
            r, c, d = Q.popleft()
            if (r, c) in SEEN:
                continue
            SEEN.add((r, c))
            if (r, c) in V and (r, c) != (rv, cv):
                E[(rv, cv)].append(((r, c), d))
                continue
            for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
                if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
                    if part1 and G[r][c] in ["<", ">", "^", "v"] and G[r][c] != ch:
                        continue
                    Q.append((r + dr, c + dc, d + 1))

    count = 0
    ans = 0
    SEEN = [[False for _ in range(C)] for _ in range(R)]
    seen = set()

    def dfs(v, d):
        nonlocal count
        nonlocal ans
        count += 1
        r, c = v
        if SEEN[r][c]:
            return
        SEEN[r][c] = True
        if r == R - 1:
            ans = max(ans, d)
        for y, yd in E[v]:
            dfs(y, d + yd)
        SEEN[r][c] = False

    dfs(start, 0)
    return ans


print(solve(True))
print(solve(False))