Na grupie dla początkujących programistów natknęłam się na prośbę z gatunku: coś jest nie tak z moim kodem. Czy ktoś mógłby mi pomóc go ogarnąć? Program miał rozwiązywać zadanie z jednych z popularnych puzzli programistycznych – Advent of Code 2016 -> Day 4.
Przyjrzyjmy się temu 🙂
Treść zadania tu.
Zadanie w skrócie – jest podany ciąg znaków aaaaa-bbb-z-y-x-123[abxyz]
. Litery tworzą zakodowaną nazwę pokoju, liczby to ID, a w nawiasach kwadratowych podana jest suma kontrolna. Suma kontrolna jest wyliczana następująco: pięć najczęściej występujących liter z zakodowanej nazwy, posortowanych alfabetycznie. Rozwiązaniem jest suma ID z ciągów, które mają poprawnie wyliczoną sumę kontrolną.
Pierwotna wersja kodu o tu. Będę wrzucać komity po każdej zmianie do tego repozytorium (o tu) żeby można było prześledzić spokojnie kolejne zmiany albo po prostu zobaczyć jak to wygląda ostatecznie 😉
Wciągnęłam kod do IDE, popatrzyłam, sformatowałam kod, IDE uzupełniło brakujące średniki na końcach linii. I czytam. Dorzuciłam wypisywanie sumy końcowej na konsolę. Dopisałam też instrukcję, która wyrzuci mi na konsolę błędne sumy kontrolne.
https://gist.github.com/jezinka/ef09e25757c0b6e502cece2c203bd06e
Pierwszym problemem, który został poprawnie zdiagnozowany przez autorkę kodu, było sortowanie: w momencie kiedy dwie litery pojawiły się w nazwie taką samą liczbę razy, niekoniecznie były posortowane alfabetycznie. Dla ciągu molgbzqfib-bdd-mrozexpfkd-289[bdfmo]
program wyliczał sumę kontrolną jako bdofm
.
To jest pierwsza rzecz, którą poprawiłam wychodząc z założenia, że moim zadaniem nie jest tworzenie kodu za Autorkę, bo to nie jest problemem zaorać wszystko i zacząć na nowo, ale raczej nikt z tego nic nie wyciągnie.
https://gist.github.com/jezinka/b7f348f36ed98318500b72503676f902
Do sortowania dodałam sprawdzanie, czy częstotliwość występowania liter jest różna. Jeśli jest różna, sortuj tak jak było. W przeciwnym wypadku sortuj alfabetycznie (przez porównywanie kodów ASCII).
Myślałam, że to załatwi sprawę, ale wieczorem otrzymałam feedback, że dalej nie działa. Rano skontaktowałam się z Autorką i otrzymałam zgodę na tą zabawę kodem, którą chcę tu przedstawić 🙂 Dziecko uśpione, lecimy z koksem 😉
Na początku wyciągnę kod js z HTML-a, w którym go na szybko osadziłam, i wsadzę go w funkcję. Stworzyłam folder o nazwie js
, w którym umieściłam plik main.js
. W pliku main.js stworzyłam funkcję solution()
, do której przeniosłam cały kod javaScriptowy. Dzięki temu plik HTML wygląda teraz tak:
https://gist.github.com/jezinka/9133aee88d759644566b1261a6a877b5
W zadaniu mamy podany mniejszy przykład, który możemy wykorzystać jako nasz „test jednostkowy”. Wiemy, że dla takich danych
aaaaa-bbb-z-y-x-123[abxyz] a-b-c-d-e-f-g-h-987[abcde] not-a-real-room-404[oarel] totally-real-room-200[decoy]
suma ID poprawnych pokoi wynosi 1514.
Żebym mogła stworzyć taki test potrzebowałam wyciągnąć z funkcji solution kod odpowiedzialny za wyliczenie sumy dla podanych danych. Nowa funkcja powinna przyjmować jeden argument, którym są dane wejściowe i zwracać sumę ID dla poprawnych pokoi. Stworzyłam funkcję countSum(dane)
, do której przeniosłam prawie cały kod funkcji solution
. Po tej operacji solution
wygląda tak:
https://gist.github.com/jezinka/8624f297fc0d20f874ff4ab2103a714d
Funkcja countSum(dane)
do podglądu tu. Poza tym, że przyjmuje argument ,to na końcu zwraca sumę za pomocą instrukcji return sumId;
Teraz mogę stworzyć funkcję test(dane)
https://gist.github.com/jezinka/5c84bed34cfc5424f04b0a7a2262af2b
Do funkcji countSum
przekazuję dane testowe i potem sprawdzam, czy wynik jest równy 1514. Wywołanie funkcji test dorzuciłam do HTML-a analogicznie do wywołania funkcji solution()
https://gist.github.com/jezinka/85a2440bf76b7fb4d5eee0ae9192709c
Otworzyłam plik html w przeglądarce i odpaliłam konsolę developerską w Chromie (klawisz F12), żeby zobaczyć czy test wyszedł poprawny i jest ok 😉
W tym miejscu mogłabym sobie przygotować jeszcze więcej testów, które będą sprawdzać dane dla kłopotliwych przypadków jak na przykład ten z sortowaniem alfabetycznym.
https://gist.github.com/jezinka/df2a8f2afa6dee6fa82155428bc2f90d
Wiemy, że ten ciąg jest prawidłowy, więc suma powinna być równa 289.
Gdybym robiła to w metodyce TDD powinnam pisać takie testy do momentu aż znajdę przypadek, dla którego wynik testu będzie nieprawidłowy. Chcę się jednak skupić na tym co w kodzie można by było poprawić i liczę na to, że w toku refaktoryzacji znajdę ukryty błąd.
Więc, czym można się teraz zająć? Może na warsztat wezmę kawałek kodu:
https://gist.github.com/jezinka/66fdbca4537de04920fadb35e018cdbc
Ten kawałek odpowiada za to, że z instructions[i]
, który przedstawia pojedynczą instrukcję wyciągamy poszczególne części odpowiedzialne za zakodowaną nazwę, id i sumę kontrolną. Jednak jedyną stałą długością jaką mamy podaną w zadaniu jest długość sumy kontrolnej. Co by było gdyby ID różną długość? Możemy się przed tym zabezpieczyć wykorzystując wyrażenia regularne, które potrafią więcej niż tylko usuwać znaki ze stringa.
https://gist.github.com/jezinka/d4c364af9fbb90d085d2269688f62e28
Na początek tworzę sobie zmienną instruction
, do której przypisuję wartość z instructions[i]
– lepiej się czyta taki kod i zajmuje mniej miejsca 😉 Teraz za pomocą wyrażeń regularnych z funkcją match
wyciągam poszczególne części:
instruction.match(/^[a-z]+/)[0]
-> można to tłumaczyć jako „zacznij wyszukiwać od początku łańcucha (^), wyszukuj dopóki znajdujesz litery[a-z], tych liter będzie jedna lub więcej (+)”. Funkcja match zwraca w odpowiedzi tablicę, w pierwszym elemencie ([0]) jest to czego szukamy, czyli nasza zakodowana nazwa pokoju.- <
span class="pl-smi">instruction.match(/\d+/)[0]
-> „wyszukuj liczby (\d), będzie ich jedna lub więcej (+)” instruction.match(/\[([a-z]{5})\]/)[1]
-> „znajdź [, później będą litery, będzie ich 5, a potem znowu ]. Tutaj korzystamy z () w celu zaznaczenia, że te [] nie są brane pod uwagę w końcowym wyniku. Teraz pierwszym elementem wyniku będzie ciąg razem z nawiasami klamrowymi [abcde], a dopiero drugim elementem będzie nasza szukana grupka abcde.
Do zabawy wyrażeniami regularnymi polecam różne kompilatory online np. http://refiddle.com/. Można tam na żywo dopasowywać różne wyrażenia i sprawdzać co się dopasuje w każdym wypadku.
Teraz wezmę na warsztat kolejny kawałek kodu:
https://gist.github.com/jezinka/012caa530e9e7d06cf153f89fd8b2bc5
Ten kod bierze zakodowany ciąg znaków, zamienia go na tablicę – elementem tablicy jest pojedyncza litera. Później sortujemy tablicę alfabetycznie. Metoda byCount
zlicza wystąpienia poszczególnych liter i zwraca tablicę, w której litery są posortowane po ilości wystąpień. Slice (0,5)
bierze 5 pierwszych elementów z tablicy. Metoda toString
łączy nam elementy w stringa rozdzielając każdy element za pomocą przecinka. Tworzymy wyrażenie regularne wyszukujące wszystkie przecinki i usuwamy je ze stringa. Wynik odkładamy do tablicy finall
.
Zacznijmy poprawiać kod od końca. Jeśli zamiast metody toString
na tablicy użyjemy join('')
dostaniemy od razu litery w oczekiwanej formie – bez ’,’ pomiędzy literami.
https://gist.github.com/jezinka/ad0eb2f01826d5f7f0ca215494e3c04d
Jako że na samym początku poprawiony został błąd z sortowaniem, to tutaj już to sortowanie nam się nie przyda i może zostać usunięte 🙂
https://gist.github.com/jezinka/8cac4c29b3a82f36d36e3aa3a76baef5
Na razie zostawię to tak jak jest i przejdę do metody byCount();
https://gist.github.com/jezinka/9e9f2aff58c4879372092231a2bec6a4
Na pierwszy rzut oka – dzieje się tutaj dużo.
- deklarujemy i initializujemy różne zmienne
- tworzymy słownik (dictionary) zawierający pary klucz-wartość, gdzie kluczem jest litera, a liczba wystąpień to wartość
- wyciągamy litery ze słownika
- sortujemy tablicę w zależności od częstotliwości występowania danej litery + alfabetycznie jeśli występują tak samo często.
Step-by-step. Deklaracja zmiennej powinna być przypisana jak najbliżej miejsca jej pierwszego użycia.
https://gist.github.com/jezinka/f52e266a80ea42a652ef8664c34e43bf
Metoda troszkę się rozciągnęła, bo ja lubię mieć klamerki – lepiej wtedy widzę co się dzieje w kodzie 🙂
Punkt 3. wyciągamy litery ze słownika – linie 16:19, to nic innego jak wyciągnięcie kluczy ze słownika, które można by zamienić na Object.keys(o)
, od razu zmienna a może dostać bardziej adekwatną nazwę.
https://gist.github.com/jezinka/14eb9d60e013e2876f233778e60dede5
Jeszcze pozmieniam nazwy zmiennych żeby były bardziej czytelne co w nich siedzi i idziemy dalej:
https://gist.github.com/jezinka/14bc822671350b4006afc92d8fe70afc
Wróćmy jeszcze na chwilkę do poprzedniego fragmentu:
https://gist.github.com/jezinka/4a54564b0467b55c3f9737b4ae20d5a3
zmienimy tu nazwy zmiennych i połączymy slice z join w jedną linijkę:
https://gist.github.com/jezinka/c745e6b2c1b181d1aeb54adb52810f93
Teraz możemy popatrzeć na kod całościowo. Możemy zauważyć, że wykonujemy 3 pętle po całości zbioru. Zbiór ma około 1000 elementów. Sprawdźmy, czy można by było to połączyć i zrobić wszystko podczas jednej pętli, bo tak naprawdę nie potrzebujemy przechowywać wszystkich pośrednich wyników parsowania i wyciągania nazw, sum kontrolnych i id. Potrzebujemy tylko sumy ID jeśli pokój jest prawidłowy. Innymi słowy, tylko sumId jest nam potrzebne poza pętlą 😉
https://gist.github.com/jezinka/8e345f9d3269e1921c900461573d2687
Jeszcze wyjmę z tej funkcji funkcję byCount
na zewnątrz, bo w tym miejscu tylko mi to zaciemnia. Dodatkowo przeniosę dane do osobnego pliku, bo są one mi tutaj wcale nie potrzebne 🙂
Co jeszcze można tu zrobić – można poprawiać i poprawiać, jakby się człowiek uparł, to nigdy może nie skończyć. Ja bym zrobiła jeszcze tylko jedno – zamiast 3 wyrażeń regularnych użyję tylko jednego, połączonego:
https://gist.github.com/jezinka/ef30caaf0ad7e10a7d8be5332c388282
Zerowy element tablicy to dane wejściowe, a potem po kolei wszystkie dopasowane elementy z nawiasów okrągłych.
A gdzie był błąd? błąd był w danych wejściowych 😀