opis problemu
Wszyscy uwielbiamy Twix (ponieważ jest to najlepszy cukierek), ale to jest pierwsze Halloween dla dzieci - musimy zdobyć dla nich przynajmniej jeden z każdego rodzaju cukierków. Każdego Halloween wszyscy mieszkańcy alei Numberline wysyłają e-mail z informacją, jakie rodzaje cukierków rozdadzą w tym roku.
O! I żyjemy w świecie 1D.
Będąc pod pewnymi względami wyjątkowo leniwymi, a nie innymi, stworzyliśmy mapę domów, podając ich pozycje wzdłuż ulicy. Zauważyliśmy również, jakie mają rodzaje cukierków. Oto mapa, którą stworzyliśmy na ten rok:
[(-2, {"Kisses", "KitKats"}),
(1, {"KitKats", "Peanut Butter Cups"}),
(6, {"Kisses", "Twix"}),
(9, {"Skittles"}),
(10, {"Twix"})]
Ze względu na małe nogi dzieci musimy znaleźć najkrótszy spacer rozpoczynający się w dowolnym domu w okolicy, aby zebrać przynajmniej jeden z każdego rodzaju cukierków.
Przykłady
Na prośbę kilku użytkowników (w tym Kudłatego) podrzucę kilka sprawdzonych przykładów. Mam nadzieję, że to wszystko wyjaśni. :) Wejście:
[(-2, {"Kisses", "KitKats"}),
(1, {"KitKats", "Peanut Butter Cups"}),
(6, {"Kisses", "Twix"}),
(9, {"Skittles"}),
(10, {"Twix"})]
Wynik:
[1, 2, 3]
Kolejna mapa i rozwiązanie ...
Wejście:
[(-3, {"KitKats", "Twix"}),
(-1, {"Hundred Grands"}),
(3, {"Kisses"}),
(12, {"Hundred Grands", "Twix", "KitKats"})]
Wyjście :
[0, 1, 2]
Możemy zacząć od współrzędnych 9 domów zbierających cukierki w domach 6 i 1. To wypełnia limit cukierków, przechodząc 8 jednostek, ale czy jest to najkrótsze rozwiązanie?
Zasady
Wpisy muszą przyjmować podobnie ustrukturyzowany pojedynczy argument jak w przykładzie i generować wskaźniki domów do odwiedzenia w najkrótszym rozwiązaniu.
Obowiązują typowe zasady gry w golfa: wygrywa najkrótsze prawidłowe rozwiązanie w bajtach!
PS To było pytanie do wywiadu udzielone mi przez jedną z największych firm technologicznych na świecie. Jeśli nie lubisz golfa, spróbuj znaleźć rozwiązanie czasowe O (k * n), w którym k jest liczbą rodzajów cukierków, a n jest liczbą domów.
Edytować
Jak zauważył Jonathon Allan, istnieje pewne zamieszanie wokół tego, co w tym przypadku oznaczają „wskaźniki”. Chcemy wyprowadzić pozycje domów na liście argumentów, a nie ich współrzędne na linii.
Odpowiedzi:
Galaretka , 16 bajtów
Monadyczny link akceptujący dane wejściowe, zgodnie z opisem na liście posortowanej od domów od najniższej do najwyższej Numberline Avenue (jeśli musimy zaakceptować dowolne zamówienie, możemy dodać an
Ṣ
), który daje najkrótszą ścieżkę, zaczynając od domu o najniższym numerze i idąc w górę alei.Wypróbuj online!
Jeżeli chcemy znaleźć wszystkie te najkrótsze ścieżki zastąpi bajtów spływu,
ÞḢ
zÐṂ
; to także 16 bajtów.W jaki sposób?
źródło
Python 2 ,
133130127 bajtówWypróbuj online!
źródło
05AB1E , 22 bajty
Zakłada, że liczby na liście wprowadzania są posortowane od najniższej do najwyższej.
Jeśli zostanie znalezione więcej niż jedno rozwiązanie, wygeneruje je wszystkie.
Wypróbuj online.
Wyjaśnienie:
źródło
Perl 6 , 70 bajtów
Wypróbuj online!
źródło
Haskell ,
343372 bajtówDzięki @ ASCII tylko dla ulepszeń, istnieje również wariant 271 bajtów, który zaproponował w komentarzach :)
Wypróbuj online!
Nie golfił
Pierwsze podejscie
źródło
Rozwiązanie czasowe O (k * n) z przestrzenią O (k * n)
Zatem naszym algorytmem jest:
źródło