Problem

Dzisiaj znajdujemy się na planszy 2d o wielkości 71 na 71, zaczynamy w narożniku o koordynatach (0,0) musimy dojść do pola (70, 70). Na wejściu dostajemy listę koordynatów w takiej formie:

5,4
4,2
4,5
3,0
2,1
6,3
...

Koordynaty te wskazują na których polach znajduje się przeszkoda. Naszym zadaniem jest znaleźć najkrótszą ścieżkę (omijając przeszkody) z punktu startowego do końcowego, ale mamy brać pod uwagę tylko 1024 pierwszych linijek z koordynatami przeszkód. Zakładam że pozostałe przeszkody będą potrzebne do części 2.

Rozwiązanie

Zadanie brzmi znajomo? Powinno, bo najlepszym sposobem na rozwiązanie go będzie użycie tego samego algorytmu co dwa dni temu, algorytmu Dijkstry.

Nie ma tu wiele do tłumaczenia, ten wariant jest nawet prostszy niż w dniu 16, gdyż nie musimy rozważać różnych kierunków w jakich się poruszamy.

import heapq
import sys
from collections import defaultdict

NUM_LINES = 1024
SIZE = 71


def neighborhood(i, j, byte_positions):
    N = [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]
    for x, y in N:
        if (x, y) in byte_positions or x < 0 or y < 0 or x >= SIZE or y >= SIZE:
            continue
        yield (x, y)


if __name__ == "__main__":
    byte_positions = set()
    for _ in range(NUM_LINES):
        line = sys.stdin.readline()
        if not line:
            break
        byte_positions.add(tuple(map(int, line.split(","))))

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

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

        if dist > distances[cur]:
            continue

        distances[cur] = dist

        if cur in visited:
            continue

        visited.add(cur)

        for n in neighborhood(cur_i, cur_j, byte_positions):
            if n in visited:
                continue
            x, y = n
            newdist = dist + 1
            heapq.heappush(pq, (newdist, n))

    print(distances[(SIZE - 1, SIZE - 1)])

Część 2

Żeby zdobyć drugą gwiazdkę musimy znaleźć pierwszą przeszkodę po której dodaniu, niemożliwym będzie dotarcie do celu. Jako że plik ma tylko mniej więcej 3000 linijki, to brute-force powinien tu wystarczyć, jednak możliwa jest optymalizacja z użyciem przeszukiwania binarnego.

Jak to działa?

1. Jeśli wiemy że nie jesteśmy w stanie dotrzeć do celu, to dodanie większej ilości przeszkód na pewno tego nie zmieni. Więc na pewno przeszkoda która jako pierwsza uniemożliwiła przejście trasy była wcześniej w pliku.
2. Jeśli wiemy że trasa jest możliwa do przejścia, to na pewno usunięcie przeszkody tego nie zmieni, więc wiemy że przeszkoda uniemożliwiająca przejście musi być dalej w pliku. Możemy zmniejszać nasz obszar przeszukiwania dwukrotnie z każdą iteracją.

Poniżej wklejam zmiany które trzeba wprowadzić w kodzie żeby to działało:

if __name__ == "__main__":
    byte_list = list()
    for line in sys.stdin.readlines():
        byte_list.append(tuple(map(int, line.split(","))))

    l = 0
    r = len(byte_list) - 1
    while l < r:
        m = (l + r) // 2
        byte_positions = set(byte_list[: m + 1])

            # Algorytm Dijkstry
            # visited = set()
            # ...

        if distances[(SIZE - 1, SIZE - 1)] == float("inf"):
            r = m - 1
        else:
            l = m

    print("Part 2: ", byte_list[m])

Podsumowanie

Dzisiejsze zadanie było dużo prostsze niż wczorajsze, więc na szczęście zajęło mi dużo mniej czasu żeby je rozwiązać. Nawet przeszukiwanie brute forcem w części drugiej wykonuje mi się mniej niż 30 sekund, ale był to ciekawy przykład na użycie przeszukiwania binarnego, żeby znacznie zoptymalizować wykonywanie programu. (do 0.027 sekundy)