Wprowadzenie

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

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

W końcu udało Ci się przezwyciężyć klawiaturę z sejfu. Dzięki dokumentom, które tam znalazłeś dotarłeś do drzwi prowadzących na dach. Niestety są zamknięte na głucho, nie możesz się nawet to nich dostać, widzisz je za szybą kuloodporną. Jednak, robot, który czyści kanały wentylacyjne może.

Niestety nie jest to szybki robot, możesz go przekonfigurować tak, że będzie mógł połączyć się z kablami prowadzonymi z sytemu HVAC (ogrzewanie, wentylacja, klimatyzacja). Jeśli będziesz w stanie pokierować go tak, żeby dotarł do kilku miejsc będziesz mógł ominąć system bezpieczeństwa chroniący drzwi.

Udało Ci się zdobyć plany kanałów wentylacyjnych, na których zaznaczone są istotne miejsca na mapie (wejście do programu). 0 to Twoja aktualna pozycja, z której robot czyszczący zaczyna się poruszać. Pozostałe numery (kolejność nie ma znaczenia) oznaczają miejsca, które robot musi odwiedzić co najmniej raz. Mury oznaczone są # a kanały, po których może się poruszać robot .. Numery oznaczające miejsca to także miejsca dostępne dla robota.

Na przykład, zakładając, że mapa kanałów wentylacyjnych wygląda następująco:

###########
#0.1.....2#
#.#######.#
#4.......3#
###########

Aby dotrzeć do wszystkich istotnych miejsc tak szybko jak to możliwe robot wybrał następującą ścieżkę:

  • od miejsca startowego do 4 (2 kroki),
  • od miejsca 4 do 1 (4 kroki, robot nie może poruszać się na ukos),
  • od miejsca 1 do miejsca 2 (6 kroków),
  • od miejsca 2 do miejsca 3 (2 kroki).

Z racji tego, że robot jest raczej powolny musisz znaleźć najkrótszą drogę. Przykład pokazuje najkrótszą możliwą drogę (14 kroków) wymaganych do odwiedzenia wszystkich istotnych punktów co najmniej raz.

Zakładając, że mapa kanałów wentylacyjnych znajduje się w tym pliku i że robot zaczyna z pozycji 0, jaka jest najmniejsza liczba kroków potrzebna aby odwiedzić wszystkie miejsca oznaczone numerami co najmniej raz?

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