diff options
Diffstat (limited to '2023')
| -rw-r--r-- | 2023/21/solve.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/2023/21/solve.py b/2023/21/solve.py index df17878..9aca201 100644 --- a/2023/21/solve.py +++ b/2023/21/solve.py @@ -4,6 +4,9 @@ L = { for (j, c) in enumerate(l.strip()) } +W = max(j for (i, j) in L.keys()) +H = max(i for (i, j) in L.keys()) + def solve1(): LIM = 64 @@ -28,4 +31,29 @@ def solve1(): print(res) +def solve2(): + LIM = 26501365 + + res = 0 + s = [(i, j) for (i, j) in L if L[(i, j)] == "S"][0] + q = [(s, 0)] + v = set() + while q: + p, n = q.pop(0) + if n == LIM + 1: + continue + + for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]: + np = (p[0] + move[0], p[1] + move[1]) + _np = (np[0] % (H + 1), np[1] % (W + 1)) + if _np not in L or np in v or L[_np] == "#": + continue + q.append((np, n + 1)) + v.add(np) + if n % 2: + res += 1 + print(res) + + solve1() +solve2() |