Zadanie

W dzisiejszym zadaniu należy prześledzić ścieżkę strażnika w 2 wymiarowej przestrzeni, wyglądającej tak:

..#..
.#..#
.....
#.^..

Początkowa pozycja strażnika oznaczona jest jako ^, z kolei # oznaczają przeszkody, ścieżka strażnika wygląda tak, że idzie on cały czas do przodu, aż stanie bezpośrednio przed przeszkodą, wtedy skręca w prawo o 90 stopni.

Naszym zadaniem jest prześledzić jego ścieżę aż do momentu kiedy wyjdzie on poza znaną nam przestrzeń, wtedy należy policzyć ilość unikalnych pól na których stanął on przec całą swoją podróż. Dla powyższego przykładu ścieżka wygląda tak:

..#..
.#oo#
..||.
#.^|.

A wynik wynosi 6.

Rozwiązanie

Parsowanie

Zaczniemy od parsowania wejścia, na pewno potrzebne będą nam pozycja początkowa strażnika jak i pozycje wszystkich przeszków. Dobrze też otrzymać wielkośc planszy żebyśmy mogli stwierdzić w którym momencie strażnik ją opuścił.

Poniższy kod wyciąga wszystkie te wartości:

# part1.awk
BEGIN {FS = ""}
{
    for (i = 1; i <= NF; i++) {
        if ($i == "#") {
            obstacles[NR][i] = 1
        }
        if ($i == "^") {
            guardx = i
            guardy = NR
        }
    }
} END {
    printf "Guard pos: (%d, %d)\n", guardx, guardy
    print "Obstacles: "
    for (row in obstacles) {
        for (col in obstacles[row]) {
            print row, col 
        }
    }
    print "Max row: ", NR
    print "Max col: ", NF

Śledzenie ścieżki

zmienne dx, dy są wystarczające by trzymać aktualny kierunek w który zwrócony jest strażnik:

    dx = 0; dy = -1  # zwrócony w górę
    while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
        visited[guardy][guardx] = 1
        newx = guardx + dx
        newy = guardy + dy
        if (obstacles[newy][newx]) { # napotkano przeszkodę
            # zmiana kierunku (aktualizacja dx, dy)
            ...
        } else {
            # zmiana pozycji (aktualizacja guardx, guardy)
            guardx = newx
            guardy = newy
        }
    }

Aktualizacja kierunku

Kiedy napotkamy przeszkodę zmieniamy kierunek żeby iśc w prawo poniższy kod to osiąga:

...
        # zmiana kierunku (aktualizacja dx, dy)
        if (dx == 0) {
            if (dy == -1) dx = 1
            else dx = -1   
            dy = 0
        } else {
            if (dx == 1) dy = 1
            else dy = -1
            dx = 0
        }
...

Liczenie odwiedzonych pól

Na końcu bez problemu możemy zliczyć ilość odwiedzonych pól

...
    # count number of visited tiles
    for (row in visited) {
        for (col in visited[row]) {
            res += visited[row][col]
        }
    }
    print res

Ostateczny kod

# part1.awk
BEGIN {FS = ""}
{
    for (i = 1; i <= NF; i++) {
        if ($i == "#") obstacles[NR][i] = 1
        if ($i == "^") { guardx = i; guardy = NR }
    }
} END {
    dx = 0; dy = -1  # zwrócony w górę
    while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
        visited[guardy][guardx] = 1
        newx = guardx + dx; newy = guardy + dy
        if (obstacles[newy][newx]) { # napotkano przeszkodę
            if (dx == 0) {
                if (dy == -1) dx = 1
                else dx = -1   
                dy = 0
            } else {
                if (dx == 1) dy = 1
                else dy = -1
                dx = 0
            }
        } else { guardx = newx; guardy = newy }
    }

    # count number of visited tiles
    for (row in visited) {
        for (col in visited[row]) res += visited[row][col]
    }
    print res
}

Uruchamiamy:

awk -f part1.awk input.txt

I widzimy poprawny wynik!

Część druga

Żeby zrobić drugą gwiazdkę musimyt się bardziej postarać. Tym razem możemy dołożyć jedną swoją przeszkodę na dowolne pole (oprócz pola startowego strażnika), mamy wykryć czy strażnik wpadnie w nieskończoną pętle z której nigdy nie wyjdzie. Naszym zadaniem jest policzyć ile jest możliwych pozycji na nową przeszkodę które doprowadzą do takiej sytuacji.

Pomysł

Na początku po przeczytaniu treści zadania, wydawało mi się ono dosyć trudne, ale wydaje mi się że wiem jak to rozwiązać w miarę wydajnie. Kluczem jest znaleźć sposób na wykrycie czy jesteśmy już w pętli.

Wygląda na to że jedyny stan jaki musimy śledzić to pozycja i kierunek naszego strażnika, kolejne ruchy są zależne jedynie od tych wartości, więc jeśli drugi raz znajdziemy się w tym samym stanie, wiemy że jesteśmy w pętli.

Kod

Do naszej pętli ścieżki musimy dodać kilka linijek

while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
    visited[guardy][guardx] = 1

    # sprawdź czy byliśmy już w tej sytuacji
    if (dxs[guardy][guardx][dx] && dys[guardy][guardx][dy]) {
        cycles += 1
        break
    }

    # Zapisz że w tym polu byliśmy już skierowani w tym kierunku
    dxs[guardy][guardx][dx] = 1
    dys[guardy][guardx][dy] = 1
    ...

To wystarczy żeby wykryć cykl i go podliczyć

Główna pętla

W głównej pętli będziemy iterować po wszystkich możliwych nowych pozycjach przeszkód:

    for (ox = 1; ox <= NF; ox++) {
        for (oy = 1; oy <= NR; oy++) {
#           # pomińmy pola na których już jest przeszkoda
            if (obstacles[oy][ox]) continue

            obstacles[oy][ox] = 1

            dx = 0; dy = -1
            guardx = original_guardx
            guardy = original_guardy
            delete visited
            delete dxs
            delete dys

            while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
                ...

Po złączeniu tego wszystkiego w całość odpalamy, kod i…

Czekamy…
…
….
Czekamy …..

2 i pół minuty później

Otrzymujemy poprawny wynik! Już myślałem że nasz program się zawiesił. Normalnie zaliczyłbym moje rozwiązanie ale czuję że jesteśmy w stanie poprawić ten czas.

Pomysł na optymalizację

Wydaje mi się że wiele pól nie musi zostać sprawdzonych gdyż strażnik nigdy ich nie odwiedza w oryginalnej ścieżce. Dlatego spróbujemy rozważać tylko te pola które zostały odwiedzone w częsci pierwszej zadania.

Końcowy kod

# solution.awk
BEGIN {FS = ""}
{
    for (i = 1; i <= NF; i++) {
        if ($i == "#") {
            obstacles[NR][i] = 1
        }
        if ($i == "^") {
            original_guardx = i
            original_guardy = NR
        }
    }
}
END {
    dx = 0; dy = -1
    guardx = original_guardx
    guardy = original_guardy
    while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
        visited_p1[guardy][guardx] = 1
        newx = guardx + dx; newy = guardy + dy
        if (obstacles[newy][newx]) {
            if (dx == 0) {
                if (dy == -1) dx = 1
                else dx = -1   
                dy = 0
            } else {
                if (dx == 1) dy = 1
                else dy = -1
                dx = 0
            }
        } else { guardx = newx; guardy = newy }
    }

    for (row in visited_p1) {
        for (col in visited_p1[row]) res += visited_p1[row][col]
    }
    print "part 1", res

    for (ox = 1; ox <= NF; ox++) {
        for (oy = 1; oy <= NR; oy++) {
            if (!visited_p1[oy][ox]) continue

            obstacles[oy][ox] = 1

            dx = 0; dy = -1
            guardx = original_guardx
            guardy = original_guardy
            delete visited
            delete dxs
            delete dys

            while(guardx >= 1 && guardy >= 1 && guardx <= NF && guardy <= NR) {
                visited[guardy][guardx] = 1

                if (dxs[guardy][guardx][dx] && dys[guardy][guardx][dy]) {
                    cycles += 1
                    break
                }

                dxs[guardy][guardx][dx] = 1
                dys[guardy][guardx][dy] = 1

                newx = guardx + dx
                newy = guardy + dy
                if (obstacles[newy][newx]) {
                    if (dx == 0) {
                        if (dy == -1) dx = 1
                        else dx = -1   
                        dy = 0
                    } else {
                        if (dx == 1) dy = 1
                        else dy = -1
                        dx = 0
                    }
                } else {
                    guardx = newx
                    guardy = newy
                }
            }
            obstacles[oy][ox] = 0
        }
    }

    print "Part 2", cycles
}

Ostatecznie otrzymujemy te same, poprawne rozwiązania w 28 sekund, więc pięciokrotnie przyśpieszyliśmy działanie programu.

Podsumowanie

Rozwiązanie dzisiejszego zadania nie sprawiło dużych problemów, jednak nie mam pomysłu jak zoptymalizować go do bardziej akceptowalnego czasu. Na pewno rozważamy dużo redundantnych ścieżek.

Kod dzisiejszego rozwiązania też jest już dużo mniej czytelny niż w poprzednich dniach, powoli używanie awk, może stawać się większym problemem niż plusem. Mimo wszystko nawet dzisiaj używanie tego narzędzia nie było złym doświadczeniem.