day20/solution_gemini-1.5-pro.py

from collections import deque

def solve():
    file = "input.txt"
    grid = []
    with open(file, 'r') as f:
        for line in f:
            grid.append(list(line.strip()))

    rows = len(grid)
    cols = len(grid[0])

    start = None
    end = None
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 'S':
                start = (r, c)
            elif grid[r][c] == 'E':
                end = (r, c)

    def bfs(start, end, max_cheat=0):
        q = deque([(start, 0, 0)])
        visited = set()
        while q:
            (r, c), steps, cheat_used = q.popleft()
            if (r, c) == end:
                return steps
            if ((r, c), cheat_used) in visited:
                continue
            visited.add(((r, c), cheat_used))

            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if grid[nr][nc] != '#':
                        q.append(((nr, nc), steps + 1, cheat_used))
                    elif cheat_used < max_cheat:
                        q.append(((nr, nc), steps + 1, cheat_used + 1))
        return float('inf')

    baseline = bfs(start, end)

    count1 = 0
    count2 = 0
    for sr in range(rows):
        for sc in range(cols):
            for er in range(rows):
                for ec in range(cols):
                    if grid[sr][sc] != '#' and grid[er][sc] != '#':
                        time1 = bfs(start, (sr, sc), 0) + bfs((sr, sc), (er, ec), 2) + bfs((er, ec), end, 0)
                        saved1 = baseline - time1
                        if saved1 >= 100:
                            count1 += 1
                        time2 = bfs(start, (sr, sc), 0) + bfs((sr, sc), (er, ec), 20) + bfs((er, ec), end, 0)
                        saved2 = baseline - time2
                        if saved2 >= 100:
                            count2 += 1

    print(count1)
    print(count2)

solve()