Zadanie

Dzisiaj przyszedł czas na kolejne zadanie ze znajdywaniem ścieżki w dwuwymiarowej macierzy. Format wejścia jest podobny jak w zadaniu 16. Czyli mamy grida ze ścieżkami oznaczonymi jako . a ścianami oznaczonymi jako #. Start i koniec oznaczone są kolejno jako S i E.

Naszym celem jest znalezienie najkrótszej ścieżki od początku do końca, z tym że mamy możliwość oszukiwania, gracz raz podczas wyścigu może aktywować oszustwo trwające dwa ruchy. Podczas oszustwa może przechodzić przez ściany, ale na końcu trwania oszustwa powinien skończyć na pustym polu. (Czyli efektywnie jesteśmy w stanie przeskoczyć jedną ścianę).

Mamy znaleźć unikalną ilość oszustw, które pozwolą nam zaoszczędzić przynajmniej 100 ruchów. Oszustwo definiuje jego początek i koniec.

Rozwiązanie

Żeby łatwiej móc obliczać oszczędności różnych oszustw, obliczymy sobie najpierw ile zajmuje dotarcie do końca od każdego wolnego pola w gridzie. Od razu na myśli przyszedł mi algorytm Dijkstry którego użyliśmy już 2 razy w tym roku:

  • Dzień 16
  • Dzień 18 Jednak tym razem nie będzie on konieczny, nasz grid bowiem ma tylko jedną możliwą ścieżkę, jest to napisane w treści zadania, ale szybkie spojrzenie w input to potwierdza. Dlatego wystarczy zaimplementować prosty DFS, albo nawet iteracyjnie, jednak dijkstrę mam już zaimplementowaną więć przekleję kod z zadania 18 już zaimplementowaną więc przekleję kod z zadania 18.

Teraz dla każdego wolnego pola, rozważę użycie oszustwa, w tym celu należy przejrzeć sąsiadujące pola w kształcie diamentu, czyli oddalone o 2 według dystansu manhattan.

def cheated_neighbors(cur, dist=2):
    i, j = cur
    for x in range(i - dist, i + dist + 1):
        for y in range(j - dist, j + dist + 1):
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
                continue

            steps = abs(x - i) + abs(y - j)
            if steps <= dist and grid[x][y] != "#":
                yield x, y, steps

Nasza główna funkcja będzie wyglądać w ten sposób:

cheat_count = 0

for i, row in enumerate(grid):
    for j, c in enumerate(row):
        if c == "#":
            continue

        for x, y, steps in cheated_neighbors((i, j), 2):
            # liczymy ilość zaoszczędzonych kroków
            if distances[(x, y)] - distances[(i, j)] - steps >= 100:
                cheat_count += 1

Uruchomienie kodu działa w poprawny sposób.

Część 2

Druga część ma takie utrudnienie że tym razem nasze oszustwo może trwać maksymanie 20 sekund (ale może krócej). Na szczęście nasz kod jest gotowy na taką zmianę, poniżej wstawiam kod rozwiązujący obie części:

import heapq
import sys
from collections import defaultdict


def neighborhood(cur, grid):
    i, j = cur
    N = [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]

    for x, y in N:
        if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
            continue

        if grid[x][y] != "#":
            yield x, y


def dijkstra(grid):
    visited = set()
    distances = defaultdict(lambda: float("inf"))

    pq = [(0, starting)]
    while pq:
        dist, cur = heapq.heappop(pq)

        if dist > distances[cur]:
            continue

        distances[cur] = dist

        if cur in visited:
            continue

        visited.add(cur)

        for n in neighborhood(cur, grid):
            if n in visited:
                continue
            newdist = dist + 1
            heapq.heappush(pq, (newdist, n))
    return distances


def cheated_neighbors(cur, dist=2):
    i, j = cur
    for x in range(i - dist, i + dist + 1):
        for y in range(j - dist, j + dist + 1):
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
                continue

            steps = abs(x - i) + abs(y - j)
            if steps <= dist and grid[x][y] != "#":
                yield x, y, steps


if __name__ == "__main__":
    starting = end = None

    grid = [list(line.strip()) for line in sys.stdin.readlines()]

    for i, row in enumerate(grid):
        for j, c in enumerate(row):
            if c == "S":
                starting = (i, j)
            elif c == "E":
                end = (i, j)

    assert starting is not None
    assert end is not None

    distances = dijkstra(grid)

    for part, CHEAT_STEPS in enumerate([2, 20]):
        cheat_count = 0

        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == "#":
                    continue

                for x, y, steps in cheated_neighbors((i, j), CHEAT_STEPS):
                    if distances[(x, y)] - distances[(i, j)] - steps >= 100:
                        cheat_count += 1

        print(f"Part {part + 1}: {cheat_count}")