Dzisiejsze zadanie nie było moim zdaniem trudniejsze od wczorajszego, dzięki temu że na szybko przejrzałem dokumentację do awk udało mi się napisać rozwiązanie w całkiem elegancki sposób.

Opis zadania

Dzisiaj otrzymujemy dane w formie macierzy, gdzie każda linijka zawiera listę liczb, będącą raportem elfów który musimy sprawdzić pod kątem bezpieczeństwa. Raport jest uznany za bezpieczny jeśli:

  • jest w całości rosnący lub malejący
  • kolejne wartości różnią się maksymalnie o 3. Przykład ze strony:
7 6 4 2 1  # bezpieczny raport  (malejący)
1 2 7 8 9  # niebezpieczny raport  (2->7 - skok o 5)
9 7 6 2 1  # niebezpieczny raport  (6->2 - skok o 4)
8 6 4 4 1  # niebezpieczny raport  (4->4 - ani rosnący ani malejący)

Rozwiązanie

Jako że każda linijka jest niezależna od siebie, użycie awk wydaje się naturalne, od razu widać że kod będzie miał formę typu:

{
    if (is_safe()) count++
} 
END {print count}

Funkcje pomocnicze

Odrobiłem lekcję po wczoraj i sprawdziłem jak definiuje się funkcje pomocnicze w awk, jest to bardzo proste, zdefiniuję dwie funkcje które nam się przydadzą:

function abs(x) { return x < 0 ? -x : x }   # wartość bezwzględna
function sign(x) { return x < 0 ? -1 : 1 }  # znak liczby

Następnie obliczymy znak różnicy pierwszych dwóch liczb:

cur_sign = sign($2 - $1)

Wartość ta przyda nam się do sprawdzenia czy cała lista jest tej samej odmiany monotoniczności. (rosnąca czy malejąca).

Sprawdzenie bezpieczeństwa

Następnie będziemy iterować po wszystkich parach liczb, w awk indeksujemy od 1 a zmienna NF przechowuje ilość kolumn w linijce. Dla każdej pary liczymy różnicę i jej znak. Znak powinien być taki sam jak dla pierwszej pary, a wartość absolutna różnicy (dystans) powinna być w przedziale [1,3].

for (i = 1; i < NF; i++) {
    diff = $(i+1) - $(i)
    dist = abs(diff)
    if (sign(diff) != cur_sign || dist < 1 || dist > 3)
        next
}

Łącząc to wszystko w całość

Po zintegrowaniu wszystkich kawałków kodu otrzymujemy całkiem kompaktowy program:

# Part 1
function abs(x) { return x < 0 ? -x : x }
function sign(x) { return x < 0 ? -1 : 1 }
{
    cur_sign = sign($2 - $1)
    for (i = 1; i < NF; i++) {
        diff = $(i+1) - $(i)
        dist = abs(diff)
        if (sign(diff) != cur_sign || dist < 1 || dist > 3)
            next
    }
    count++
}
END {print count}

Część 2

W drugiej części spotykamy się z lekkim twistem, jeżeli usunięcie maksymalnie jednej liczby z listy sprawia że jest ona bezpieczna, to traktujemy ją jako bezpieczną.

Najbardziej sensownym rozwiązaniem wydaje mi się po prostu wygenerowanie, każdej możliwej podlisty, z usuniętym jednym elementem i sprawdzenie czy chociaż jedna z nich jest bezpieczna (według definicji z części 1).

Czuję że najłatwiej będzie jeśli podzielimy sobie ten pipeline na dwa skrypty w awk:

  1. Generowanie podlist (aux.awk)
  2. Agregacja danych (second.awk)

1. Generowanie podlist

Plan jest żeby wypisać wszystkie możliwe podlisty linijka po linijce, ale musimy też dopisać do nich klucz po którym będziemy w stanie połączyć listy dotyczące tej samej listy początkowej.

Przykład: input

a b c
d e f g

Output do przykładu (literki dla czytelności)

1 b c     # 1 lista,  1 podlista
1 a b     # 1 lista,  2 podlista
2 e f g   # 2 lista,  1 podlista
2 d e g   # 2 lista,  2 podlista
2 d e f   # 2 lista,  2 podlista

Skrypt pomocniczy

Będziemy iterować po wszystkich wartościach od $1 do $NF, żeby wybrać który index usunąć z listy. Następnie żeby skonstruować podlisty potrzebna jest kolejna pętla. Ich tworzenie dokonałem akumulując kolejne wartości stringa za pomocą konkatenacji.

# aux.awk
{
    for (i = 1; i <= NF; i++) {
        new_list = ""  # akumulator na początku pusty
        for (j = 1; j <= NF; j++) {
            if (i == j) continue   # pomiń element
            new_list = new_list " " $j
        }
        print NR new_list  # zwracamy numer linijki (NR) i podlistę
    }
}

2. Agregacja danych

Agregacja danych wygląda bardzo podobnie do części 1, z tą różnicą że w asocjacyjnej liście done, zapisujemy, które linijki (z oryginalnej listy), zostały już przeanalizowane, gdyż tylko jedna podlista z każdej listy jest potrzebna.

function abs(x) { return x < 0 ? -x : x }
function sign(x) { return x < 0 ? -1 : 1 }
{
    if (done[$1]) next
    cur_sign = sign($(3) - $(2))
    for (i = 2; i < NF; i++) {
        diff = $(i+1) - $(i)
        dist = abs(diff)
        if (sign(diff) != cur_sign || dist < 1 || dist > 3)
            next
    }
    count++
    done[$1] = 1
}
END {print count}

Czyli całe zadanie drugie rozwiązujemy za pomocą tej komendy:

awk -f aux.awk input.txt | awk -f second.awk

Podsumowanie

Dzisiejsze zadanie było bardzo przyjemne. Ostateczny kod jest według mnie dośc czytelny, możnaby się przyczepić do jego wydajności. Na przkład jeśli znajdziemy jakąś bezpieczną podlistę, to niepotrzebne jest generowanie kolejnych. Więc podzielenie problemu na dwie części uprościło go konceptualnie, ale utrudniło lub nawet uniemożliwiło wprowadzanie pewnych optymalizacji.