Wyzwanie to opiera się na zagadce, którą czytałem jakiś czas temu w książce, którą znalazłem tutaj ponownie . Chodzi o pociski wystrzeliwane z pistoletu raz na sekundę z różnymi prędkościami, które na zawsze przemieszczają się w linii prostej. Kiedy jedna kula trafi w drugą, obie zostają całkowicie zniszczone. (Zachęcamy do zastąpienia wszystkich przypadków „pocisku” słowem „pocisk”).
Zadanie
Biorąc pod uwagę listę prędkości pocisków w kolejności, w jakiej zostały wystrzelone, określ, czy wszystkie pociski są zniszczone.
Zasady
- Dane wejściowe to lista nieujemnych liczb całkowitych oddzielonych dowolnym separatorem i jednym opcjonalnym znakiem przed i po. Są to prawidłowe dane wejściowe:
1 2 3 4 5 6
i[1,2,3,4,5,6]
. Programista dokonuje wyboru. - Podaj wartość prawdy, jeśli przynajmniej jedna kula przeżyje na zawsze, a wartość fałszowania w przeciwnym razie.
- Prędkości pocisków są podawane w jednostkach na sekundę.
- Pociski poruszają się jednocześnie i ciągle.
- Pociski mogą zderzać się z przesunięciem ułamkowym.
- Wiele pocisków, które jednocześnie osiągają dokładnie to samo położenie, niezależnie od tego, czy są to integralne, czy ułamkowe przesunięcia względem początku, wszystkie zderzają się ze sobą.
Przykłady
Na tych schematach G
reprezentuje broń, >
pociski i *
czasy, w których pociski zderzają się i wybuchają.
Prawda
Wejście: 0
0123456789
Time 0 G>
1 G>
2 G>
...
Wynik: 1
Wejście: 0 0 0
0123456789
Time 0 G>
1 G*
2 G>
3 G>
4 G>
...
Wynik: 1
Wejście: 1
0123456789
Time 0 G>
1 G >
2 G >
3 G >
...
Wynik: 1
Wejście: 2 1
0123456789
Time 0 G>
1 G> >
2 G > >
3 G > >
4 G > >
...
Wynik: 1
Wejście: 2 3 1
0123456789
Time 0 G>
1 G> >
2 G> >>
3 G > *
4 G >
5 G >
...
Wynik: 1
Falsy
Wejście: 1 2 3 4 5 6
Unit 1111111111
01234567890123456789
Time 0 G>
1 G>>
2 G> *
3 G> >
4 G> > >
5 G> > >>
6 G > > *
7 G > >
8 G > >
9 G >>
10 G *
111111111122222222223
0123456789012345678901234567890
Wynik: 0
Wejście: 1 0 0 3
Unit
0123456789
Time 0 G>
1 G>>
2 G* >
3 G> >
4 G >>
5 G *
(Drugie zderzenie ma miejsce 4.5)
Wyjście:0
Wejście: 2 1 2 3 6 5
Unit 1111111111
01234567890123456789
Time 0 G>
1 G> >
2 G>> >
3 G> * >
4 G> > >
5 G> * >
6 G > >
7 G > >
8 G >>
9 G *
1111111111
01234567890123456789
Wynik: 0
Wejście: 2 3 6
Unit
0123456789
Time 0 G>
1 G> >
2 G> >>
3 G *
Wynik: 0
źródło
1<enter>2<enter>3...
?Odpowiedzi:
Python 2,
388392388346342336331 bajtówMój Boże, ta rzecz jest ogromna, ale wierzę, że to naprawdę działa. Gdy zobaczysz wszystkie zawiłości tego wyzwania, to wyzwanie jest absurdalnie trudne.
Nie jestem pewien, czy potrafię wyjaśnić szczegółowo, jak to działa bez pisania godzinami, dlatego przedstawię streszczenie.
Duża główna pętla while zapętla się, dopóki lista wejściowa się nie zmniejszy.
Pętla zagnieżdżona dla (czy uważasz, że zagnieżdżona dla pętli jest w rzeczywistości tutaj najkrótsza?) Zapętla się przy każdej prędkości pocisku i
używaobliczeń, w którym momencie ta kula zderzy się z każdą kolejną pociskiem. Tutajnumpy.roots
do obliczania""
jest używane w znaczeniu nieskończoności (bez przecięcia). Należy uwzględnić dodatkowy warunek, aby upewnić się, że zatrzymane pociski są oznaczone jako zderzające się w momencie ich pojawienia się, a nie w momencie zero.Dla każdej liczby śledzimy, który pocisk trafi najszybciej, jeśli w ogóle, a następnie
o
jest aktualizowany o minimalne czasy kolizji dla zaangażowanych pocisków.Po zakończeniu tej podwójnej pętli iterujemy listę danych wejściowych i usuwamy wszelkie pociski, które zderzą się z minimalnym czasem kolizji, jeśli taki istnieje. To pozwala nam jednocześnie usuwać dużą liczbę pocisków, jeśli wszystkie zderzą się w tym samym momencie.
Następnie powtarzamy cały proces dla pozostałych pocisków, ponieważ mogą one już być w stanie uzyskać, że pociski, z którymi by się zderzyły, zostały zniszczone.
Jak tylko żadne pociski nie zostaną usunięte (wskazane przez listę, która się nie zmniejsza), uciekamy z pętli while i wypisujemy długość pozostałej listy. Zatem ten program nie tylko drukuje prawdę, jeśli pociski przetrwają, ale w rzeczywistości drukuje dokładnie taką liczbę pocisków, które przetrwały.
EDYCJA: Specjalne podziękowania dla feersum za generowanie przypadków testowych, aby pomóc mi znaleźć błędy.
EDYCJA 2: Zaoszczędzono 42 bajty, rozwiązując równanie liniowe ręcznie zamiast używania numpy, i dzieląc czasy początkowe na osobną listę i przekształcając warunek.
EDYCJA 3: Zapisano 4 bajty, zmieniając nazwę zakresu
EDYCJA 4: Oszczędź 6 dodatkowych bajtów, zastępując podwójne spacje tabulatorami. Feersum był także na tyle uprzejmy, że zapewnił jego implementację przy użyciu ułamków i zestawów do porównania. Grałem trochę w golfa i wychodzi z 331 bajtów, wiążąc moje rozwiązanie.
EDYCJA 5: zapisano 5 bajtów, usuwając niepotrzebną inicjalizację i przepisując warunkowo
źródło