Kiedy zderzają się kule

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 6i [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 Greprezentuje 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

Python 2, 388 392 388 346 342 336 331 bajtów

z=k=input();l=len(k);v=range;u=v(l)
while l<z:
 r="";o=[r]*l;z=l
 for h in v(l):
    if r:o[h-1]=o[m]=r;m=h;r=""
    for j in v(h+1,l):
     p=k[h];q=k[j];t=u[j];n=(1.0*q*t-p*u[h])/(q-p)if q-p else""if p>0 else t
     if t<=n<r<()>o[j]>=n<=o[h]:r=n;m=j
 i=0;s=o and min(o)
 while i<l:
    if o[i]==s!="":del k[i],o[i],u[i];l-=1
    else:i+=1
print l

Mó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żywa numpy.rootsdo obliczania obliczeń, w którym momencie ta kula zderzy się z każdą kolejną pociskiem. Tutaj ""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 ojest 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