Dzisiaj nadal obyło się bez większych problemów, choć zacząłem czuć że używanie AWKa zaczyna mi bardziej przeszkadzać niż pomagać.

Zadanie

Dzisiaj musimy zliczyć wystąpienia słowa XMAS w dwuwymiarowej tablicy liter. Słowa mogą występować w liniach pionowych, poziomych i ukośnych, w poniższym przykładzie słwo występuje 3 razy. (kropki są dodane dla ułatwienia ale w ostatecznie w inpucie będą tam inne losowe litery).

Rozwiązanie

Jeśli wypiszemy sobie wszystkie wiersze, kolumny i linie ukośne, mógłbym za pomocą grepa znaleźć wystąpienia słowa XMAS i jego odwrotności SAMX.

Wypisanie lini

Do tego celu użyję języka AWK. O ile wypisanie liń poziomych jest banalnie proste (w każdej lini wypisujemy $0), to będzie to trudniejsze dla kolumn i przekątnych. Będziemy mieć dwuwymiarowe listy trzymające dla każdej lini litery w niej występujące.

W awku możemy wygodnie iterować po znakach w linijce jeśli ustawimy sobie separator fieldów na pustego stringa (""), w ten sposób poszczególne fieldy ($1, $2, ..., $NF), będą kolejnymi znakami, można to ustawić w command linie jako argument -F, ale ja ustawię go w naszym programie w kodzie od BEGIN żeby użytkownik nie musiał o tym pamiętać:

BEGIN {FS = ""}

Nasz dalszy kod będzie wyglądał w ten sposób:

{
    for (i = 1; i <= NF; i++) {
        cols[i][NR] = $i    # dodaj aktualny znak do kolumny
        diags[i - NR][NR] = $i   # dodaj znak do przekątnej (prawo-dół)
        diags2[NF - i - NR + 1][NR] = $i   # dodaj znak do przekątnej (lewo-dół)
    }
    print $0               # wypisz linię poziomą
}
END {
    print_2d_arr(cols);    # wypisz linie pionowe
    print_2d_arr(diags);   # wypisz przekątne (prawo-dół)
    print_2d_arr(diags2);  # wypisz przekątne (lewo-dół)
}

Funkcja print_2d została zdefiniowana wcześniej jako funkcja pomocnicza:

function print_arr(arr) { 
    for (i in arr) { printf arr[i] } 
    printf "\n"
}
function print_2d_arr(arr) { for (i in arr) print_arr(arr[i]) }

Po uruchomieniu kodu otrzmujemy taki output:

$ awk -f part1.awk input.txt > lines
$ cat lines
XMAS
..AA
# ... celowo obcięte
SAMX
A..
M.
X

Zauważmy że nie wszystkie przekątne mają tyle znaków co linie poziome czy pionowe.

Zliczanie wystąpień XMAS

Kolejny raz przyda nam się grep -o "pattern" [plik], szukałem jak złapać wystąpienia słowa XMAS do przodu i do tyłu, ale nie udało mi się to. Niestety poniższy kod nie działa:

Z tego powodu że nie łapie on obu słów jeśli nachodzą na siebie XMASAMX, wypisze tylko raz.

Żeby to naprawić użyję po prostu komendy dwa razy. Połączę wyniki obu komend narzędziem cat (które służy do konkatenacji dwóch plików), i policzę liczbę lini poleceniem wc -l

Wynik jest poprawny!

Cały kod

# part1.awk
function print_arr(arr) { 
    for (i in arr) { printf arr[i] } 
    printf "\n"
}
function print_2d_arr(arr) { for (i in arr) print_arr(arr[i]) }
BEGIN {FS = ""}
{
    for (i = 1; i <= NF; i++) {
        cols[i][NR] = $i
        diags[i - NR][NR] = $i
        diags2[NF - i - NR + 1][NR] = $i
    }
    print $0
}
END {
    print_2d_arr(cols);
    print_2d_arr(diags);
    print_2d_arr(diags2);
}

Uruchamiamy całość komendą:

awk -f part1.awk input.txt > lines; cat <(grep -o "XMAS" lines) <(grep -o "SAMX" lines) | wc -l

Część 2

Żeby zdobyć drugą gwiazdę musimy się jeszcze trochę namęczyć, okazuje się że nie mamy szukać wystąpień słowa XMAS a X-MAS, a zapisane jest ono w taki sposób że dwa słowa MAS się ze sobą przecinają w taki sposób że tworzą dużego X.

Rozwiązanie

Podejdziemy do rozwiązania podobnie, tym razem jednak zamiast wypisywać linie wypiszemy wszystkie możliwe kwadraty 3x3 z pliku (każdy we własnej lini). I użyjemy grepa do wyfiltrowania tylko tych kwadratów które spełniają jedno z czterech możliwych wzorców. każde MAS ma dwie możliwości kierunku co daje w sumie cztery.

Kod wypisujący kwadraty

Nie jestem szczególnie dumny z tego kodu i nie będę tłumaczył co robi każda linijka, powiem tylko że zarówno w tej jak i poprzedniej części bardzo przydatna okazała się asocjacyjna natura macierzy w AWK, nie ma żadnych problemów z przypisaniem liczby do negatywnego indeksu w macierzy, więc nie muszę się tu przejmować edge case’ami. W końcowej pętli po prostu ignoruję kwadraty które wychodzą poza nasz obszar (negatywne indeksy, albo zaczynające się dwa lub jeden od końca macierzy).

# part2.awk
BEGIN {FS = ""}
{
    offset = NF * (NR - 1)
    for (i = 1; i <= NF; i++) {
        si = offset + i - 1
        for (x = 0; x < 3; x++) {
            for (y = 0; y < 3; y++) {
                pos = si - (x + NF * y)
                squares[pos][x + 3 * y] = $i
            }
        }
    }
} END {
    for (i = 0; i < NR - 2; i++) {
        for (j = 0; j < NF - 2; j++) {
            pos = i * NF + j
            for (v in squares[pos]) {
                printf squares[pos][v]
            }
            printf "\n"
        }
    }
}

Output dla wcześniejszego przykładu:

Jak widać zwracam nasze kwadraty w spłaszczonej formie, gdzie pierwsze trzy znaki odpowiadają za pierwszą linię, drugie trzy znaki za drugą linię i tak dalej.

Liczenie wysąpień X-MAS

Stworzyłem 4 wzorce które obejmują wszystkie możliwości wystąpienia X-MAS, zamiast kropki w regexie może wejść jaki kolwiek inny znak

Końcowy kod:

awk -f part2.awk input.txt | grep -e "M.S.A.M.S" -e "M.M.A.S.S" -e "S.M.A.S.M" -e "S.S.A.M.M" | wc -l

Podsumowanie

Cieszę się że kolejny raz udało się zadanie rozwiązać w AWKu, jednak powoli wchodzimy w terytorium gdzie mam wrażenie że będziemy potrzebować bardziej wydajnych metod, wypisywanie wszystkich kwadratów 3x3 brzmi bardzo redundantnie, no ale póki co wydajnościowo i tak nieźle sobie radzimy. Porównałem później parę rozwiązań z reddita r/adventofcode i nadal biję czasowo większość rozwiązań w pythonie.