Advent of Code 2016 dzień 23

Wprowadzenie

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

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ń 23 zadanie 1

Dzięki Twojej pomocy wczoraj udało się znaleźć odpowiednie pary maszyn w klastrze. Znajdujesz się na jednym z górnych pięter najwyższego budynku w Kwaterze Głównej Króliczka Wielkanocnego. Prywatne biuro Króliczka znajduje się właśnie tutaj, wraz z sejfem ukrytym za obrazem. Kto nie schowałby cennych dokumentów w sejfie ukrytym właśnie tam?

Sejf ma wyświetlacz cyfrowy i klawiaturę, na której trzeba wpisać odpowiedni kod. Żółta karteczka przyczepiona do sejfu daje wskazówkę dotyczącą hasła: “jajka”. Na obrazie z dużym królikiem malującym jajka, doliczyłeś się 7 jajek.

Kiedy próbujesz wpisać kod nic nie pojawia się na ekranie. Zamiast tego klawiatura rozpada się w Twoich rękach. Najwyraźniej została wcześniej zniszczona. Pod spodem ma swego rodzaju gniazdo, takie do którego pasuje Twój prototypowy komputer. Rozmontowując roztrzaskaną klawiaturę wyciągasz układ logiczny ze środka, podłączasz go do swojego komputera, który następie podłączasz do sejfu.

Teraz musisz tylko dowiedzieć się jakie wyjście wyprodukowałaby klawiatura po naciśnięciu odpowiedniego klawisza. Wyciągasz kod assembunny z chipa (wejście do programu).

Kod wygląda, prawie dokładnie jak ten, który użyty był poprzednio do sterowania kolejką! Powinieneś być w stanie użyć tego samego interpretera, którego użyłeś poprzednio. Wymagał on będzie jednak drobnego rozszerzenia o jedną nową instrukcję:

• tgl x przełącza instrukcję znajdującą się x pozycji dalej, x wskazuje na instrukcje podobnie jak jnz. Dodatnia wartość oznacza instrukcję z przodu, ujemna z tyłu.

Instrukcja tgl działa w następujący sposób:

• dla jednoargumentowych instrukcji, inc staje się dec, każda inna jednoargumentowa instrukcja staje się inc,
• dla dwuargumentowych instrukcji, jnz staje się cpy, każda inna dwuargumentowa instrukcja staje się jnz,
• argumenty przełączanej instrukcji nie są zmieniane,
• jeśli tgl próbuje przełączyć instrukcję znajdującą się poza programem, nic się nie dzieje,
• jeśli tgl wyprodukuje niepoprawną instrukcje (na przykład cpy 1 2) i później interpreter spróbuje wywołać taką instrukcję, powinien ją ominąć,
• jeśli tgl przełącza samą siebie (na przykład jeśli a ma wartość 0, tgl a przełączy się na inc a), wynikowa instrukcja nie jest wywołana dopóki interpreter nie dotrze do niej po raz kolejny.

Na przykład jeśli pod uwagę weźmiesz taki program:

cpy 2 a
tgl a
tgl a
tgl a
cpy 1 a
dec a
dec a

1. cpy 2 a inicjalizuje rejestr a wartością 2,
2. pierwsza instrukcja tgl a przełącza instrukcję odległą o wartość rejestru a (2), w wyniku czego zmienia trzecią instrukcję tgl a na inc a,
3. druga instrukcja tgl a także zmienia instrukcje oddaloną o 2, co zmienia cpy 1 a na jnz 1 a,
4. czwarta linia, która teraz jest inc a zwiększa o jeden a do wartości 3,
5. ostatecznie piąta linia, która jest teraz jnz 1 a skacze o a (3) instrukcji do przodu przeskakując obie instrukcje dec a.

W tym przykładzie ostateczna wartość rejestru a to 3.

Pozostała część układu scalonego zdaje się ustawiać wartość rejestru a na wejście z klawiatury (liczbę jajek z obrazu, 7), uruchamia kod i przesyła wynikową wartość rejestru a do sejfu.

Zakładając, że lista poleceń znajduje się w tym pliku, jaka wartość zostanie przesłana do sejfu?

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.