Witaj na moim blogu! W tym roku postanowiłem udokumentować swoje zmagania z Advent of Code.

O co w tym wszystkim chodzi?

Zasady tej zabawy są proste:

  • każdego dnia od 1 do 25 grudnia na stronie pojawia się zadanie, które składa się z dwóch związanych ze sobą części (z czym drugą część widzimy dopiero po rozwiązaniu pierwszej)
  • Zadania możemy rozwiązywać w dowolnym języku programowania (właściwie to dowolnym narzędziu, są ludzie którzy zadania rozwiązują w Excelu, lub macrach vima).

Plany na ten rok

W tym roku planuję wprowadzić lekką dywersyfikację co do narzędzi których używam, prawie zawsze moje rozwiązania pisałem w Pythonie, gdyż znam go bardzo dobrze. Będę używał go kiedy będzie to wskazane, ale postaram się dobierać narzędzie najbardziej stosowne do danego zadania. Zaczynajmy…

Dzień 1

Pierwsze zadanie zazwyczaj jest bardzo proste i można je potraktować rozgrzewkowo, postaram się w każdym poście krótko opisać treści zadań, choć zdecydowanie polecam, wczytać się w treść na oryginalnej stronie, gdyż autor zadań co roku dopisuje też zabawną otoczkę fabularną.

Część 1

Jako wejśćie otrzymujemy dwie kolumny liczb: (podaję przykład z oryginalnej strony)

3   4
4   3
2   5
1   3
3   9
3   3

Naszym zadaniem jest obliczenie całkowitego dystansu pomiędzy tymi listami, który jest zdefiniowany jako suma różnic pomiędzy wartościami w odpowiadających sobie pozycjach jeśli posortujemy obie te listy.

Jako że zadania jeszcze nie zrobiły się trudne, rozwiązanie postaram się dostarczyć jako skrypt bashowy, używająć standardowych unixowych narzędzi. Pierwszym krokiem będzie posortowanie tych list, od razu narzuca się na myśl narzędzie sort z coreutils. Flaga -n sygnalizuje że sortujemy wartości numerycznie a nie leksykograficznie. (zobacz co wydarzy się jak zrobisz echo "10\n2" | sort)

Po przeczytaniu manpage niestety nie jestem w stanie znaleźć opcji posortowania kolumn niezależnie od siebie, dlatego następnym narzędziem które się nam przyda będzie cut. By wyciągnąć poszczególne kolumny i przekierować je do sorta.

Niestety spotkałem się z kolejnym zawodem, input jest podzielony przez 3 spacje a cut wspiera podawanie tylko jednego znaku jako znak podziału. Na ratunek przychodzi tr, którego użyjemy do usunięcia nadmiarowych spacji, za pomocą flagi -s (squeeze).

tr -s " " < input > tmp                  # usuń nadmiarowe spacje
cut -d " " -f1 tmp | sort -n > sorted_1  # posortuj pierwszą kolumnę
cut -d " " -f2 tmp | sort -n > sorted_2  # posortuje drugą kolumnę
paste sorted_1 sorted_2 | preprocessed   # połącz dwie kolumny

W wyniku w pliku preprocessed znajduje się taki output:

1       3
2       3
3       3
3       4
3       5
4       9

Ostatnim krokiem będzie odpowiednia agregacja danych:

  • dla każdego wiersza obliczamy wartość bezględną różnicy pomiędzy pierwszą a drugą kolumną
  • sumujemy wszystkie dystanse

Do tego celu użyję języka programowania AWK, który został stworzony właśnie do operowania na plikach podzielonych na linie. Stwórzmy program w pliku agg.awk:

{ # dla każdej linijki
    x = $1 - $2;
    if (x < 0) {x = -x}  # wartość bezwzględna
    sum += x
}
END { # po przeanalizowaniu całego pliku
    print sum
}

Uruchamiamy go za pomocą: awk -f agg.awk preprocessed. Otrzymujemy poprawny wynik dla danych testowych11. Dla prawdziwych danych pobranych ze strony także działa więc, otrzymujemy pierwszą gwiazdę!

Jednolinijkowiec

Powyższe komendy pisałem oddzielnie i zapisywałem wyniki kolejnych kroków w plikach, żeby w bardziej przejżysty sposób zaprezentować mój tok myślenia, ale rozumiem że niektórych może denerwować to że muszą przeklejać kilka komend po sobie dlatego załączam też rozwiązanie w jednej linijce :)

paste <(tr -s " " < input.txt | cut -d " " -f1 | sort -n) <(tr -s " " < input.txt | cut -d " " -f2 | sort -n) | awk '{x=$1-$2;if(x<0){x=-x}sum+=x}END{print sum}'

Część 2

W drugiej części musimy obliczyć wyznacznik podobieństwa. Który obliczamy mnożąć każdą wartość z pierwszej listy przez ilość powtórzeń tej wartości w drugiej liście.

Na początku myślałem że zadanie to będzie dość trudne do zrobienia w shellu. Ale po krótkim googlowaniu doszedłem do tego że polecenie uniq którego zazwyczaj używa się do wyciągnięcia unikalnych lini z posortowanego pliku, ma też flagę -c która pozwala nam policzyć ilość wystąpień danej linijki. A więc komenda: uniq -c sorted_2 > counts_2, stworzy nam plik counts_2 z poniższą zawartością:

3 3
1 4
1 5
1 9

Gdzie pierwsza kolumna oznacza ilość wystąpień wartości w drugiej kolumnie.

W coreutils jest też narzędzie join, które bardzo nam się przyda, jest to odpowiednik JOINa z SQLa, czyli pozwoli nam połączyć plik sorted_1 z plikiem counts_2. Pominie on każdą linijkę która nie ma odpowiednika w obu plikach. (tak jak to robi INNER JOIN, ale możliwa jest też emulacja LEFT albo RIGHT joina przez flagę -a) A więc wpisujemy: join -11 -22 sorted_1 counts_2 > joined i otrzymujemy plik joined:

3 3
3 3
3 3
4 1

Teraz wystarczy napisać prosty program part2.awk podobny do pierwszego zadania, ale tym razem z mnożeniem dla każdej linijki:

{res += $1 * $2} 
END {print res}

Uruchamiamy go: awk -f part2.awk joined i otrzymujemy poprawnie drugą gwiazdkę!

Jednolinijkowiec

Podobnie jak w części pierwszej załączam jednolinijkowca:

join -11 -22 <(tr -s " " < input.txt  | cut -d " " -f1 | sort -n) <(tr -s " " < input.txt | cut -d " " -f2 | sort -n | uniq -c) | awk '{x+=$1*$2}END{print x}'

Podsumowanie

Pomimo tego, że wiem że zadanie rozwiązałbym w Pythonie pewnie 10 razy szybciej, to i tak cieszę się że udało się zrobić to korzystająć tylko z coreutilsów i awka bo przypomniałem sobie kilka ciekawych komend których na codzień się nie używa.

Dzisiaj postarałem się żeby opis był dość dokładny, dzisiaj jest niedziela, podejrzewam, że w tygodniu nie będę miał tyle czasu więc kolejne opisy mogą mieć dużo mniej szczegółów, gdyż opisywanie tak swojego rozwiązania jest dość czasochłonne.

Edit - nauczyć się AWKa!

Po zrobieniu swojego rozwiązania, zawsze warto zajrzeć na r/adventofcode, okazuje się, że moja wiedza na temat AWKa jest bardzo ograniczona, całą część drugą można rozwiązać dużo prościej (dziękuję u/tav_stuff, nie przypsuję sobie zasług za to rozwiązanie)

{
    xs[++i] = $1
    ys[$2]++
}
END {
    for (i in xs)
        d += xs[i] * ys[xs[i]]
    print d
}

Ponoć warto przeczytać książkę AWK Programming Language od twórców tego języka