Wprowadzenie

Oryginalna strona z zadaniami z Advent of Code 2016. Zadanie z artykułu dostępne jest pod adresem http://adventofcode.com/2016/day/9

Advent of Code to inicjatywa, w której codziennie w trakcie adwentu publikowane są zadania dla programistów. Ich rozwiązywanie pomaga rozwijać umiejętności nie tyko początkującym programistom. W tej serii artykułów pokazuję zadania opublikowane w ramach Advent of Code 2016 wraz z przykładowym rozwiązaniem.

Pobierz opracowania zadań z rozmów kwalifikacyjnych

Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.

Dzień 9 zadanie 1

Wczoraj, dzięki Twojej pomocy udało odczytać to co powinno być wyświetlone na zniszczonym wyświetlaczu. Dzięki temu dostałeś się do chronionej części Kwatery Głównej. Przechadzając się po korytarzach natknąłeś się na port, dzięki któremu możesz dostać się do pozostałej części sieci. Pobieżnie przeskanowałeś interesujące pliki, jeden z nich szczególnie przykuł Twoją uwagę. Plik ten jest skompresowany w pewnym eksperymentalnym formacie. Na szczęście dokumentacja tego formatu znajdowała się niedaleko.

Format kompresuje sekwencje znaków. Białe znaki (spacje, znaki nowej linii itp.) są ignorowane. Aby zaznaczyć, że jakaś sekwencja powinna być powtórzona, umieszcza się przed nią odpowiedni znacznik, na przykład (10x2). Aby zdekompresować następującą po nim sekwencję należy wziąć kolejne 10 znaków i powtórzyć je dwa razy. Następnie należy kontynuować czytanie skompresowanej zawartości po powtórzonej sekwencji. Sam znacznik nie jest dołączany do zdekompresowanego wyjścia.

Jeśli nawiasy, czy inne znaki wystąpią wewnątrz sekwencji, która powinna być powtórzona – wszystko jest w porządku. Należy traktować je jak normalne dane, nie znacznik i kontynuować poszukiwanie znaczników po sekcji, która została powtórzona.

Dla przykładu:

  • ADVENT nie zawiera żadnych znaczników, więc po dekompresji otrzymamy ADVENT bez żadnych zmian, wynik po dekompresji ma długość 6,
  • A(1x5)BC powtarza tylko B pięć razy, finalnie otrzymujemy ABBBBBC o długości 7,
  • (3x3)XYZ po dekompresji otrzymujemy XYZXYZXYZ o długości 9,
  • A(2x2)BCD(2x2)EFG, powtarzamy znaki BC i EF, otrzymujemy ABCBCDEFEFG o długości 11 znaków,
  • (6xa)(1x3)A po dekompresji otrzymujemy (1x3)A, chociaż (1x3) wygląda jak znacznik nie jest przetwarzany bo znajdował się wewnątrz zakresu obsługiwanego przez (6x1), podobnie jak A nie jest traktowany specjalnie. Finalnie otrzymujemy łańcuch o długości 6,
  • X(8x2)(3x3)ABCY po dekompresji otrzymujemy X(3x3)ABC(3x3)ABCY o długości 18 znaków.

Jaka jest długość zdekompresowanej sekwencji jeśli skompresowane dane zapisane są w tym pliku?

Podsumowanie

Zachęcam do dalszej zabawy z drugim zadaniem, jego treść pokaże się na stronie AoC2016 po rozwiązaniu pierwszego. Takie zadania pomagają w rozwijaniu umiejętności nie tylko początkujących programistów. Jeśli będziesz miał jakikolwiek problem z rozwiązaniem zadania możesz rzucić okiem do przykładowego rozwiązania, jednak zrób to raczej w ostateczności.

Na koniec mam do Ciebie prośbę – podziel się linkiem do artykułu ze znajomymi, może Oni także będą chcieli pomóc Świętemu Mikołajowi ;) ? Jeśli nie chcesz ominąć kolejnych artykułów proszę zapisz się do mojego newslettera i polub stronę na Facebooku. Do następnego razu!

Pobierz opracowania zadań z rozmów kwalifikacyjnych

Przygotowałem rozwiązania kilku zadań algorytmicznych z rozmów kwalifikacyjnych. Rozkładam je na czynniki pierwsze i pokazuję różne sposoby ich rozwiązania. Dołącz do grupy ponad 6147 Samouków, którzy jako pierwsi dowiadują się o nowych treściach na blogu, a prześlę je na Twój e-mail.

Kategorie:

Ostatnia aktualizacja:

Autor: Marcin Pietraszek


Nie popełnia błędów tylko ten, kto nic nie robi ;). Bardzo możliwe, że znajdziesz błąd, literówkę, coś co wymaga poprawy. Jeśli chcesz możesz samodzielnie poprawić tę stronę. Jeśli nie chcesz poprawiać błędu, który udało Ci się znaleźć będę wdzięczny jeśli go zgłosisz. Z góry dziękuję!

Zostaw komentarz