Wenn Kugeln kollidieren

Diese Herausforderung basiert auf einem Rätsel, das ich vor einiger Zeit in einem Buch gelesen habe und das ich hier wiedergefunden habe . Es geht um Kugeln, die einmal pro Sekunde mit unterschiedlichen Geschwindigkeiten abgefeuert werden und sich für immer in einer geraden Linie bewegen. Wenn eine Kugel eine andere trifft, werden beide vollständig zerstört. (Fühlen Sie sich frei, alle Instanzen von "Kugel" durch "Rakete" zu ersetzen.)

Die Aufgabe

Bestimmen Sie anhand einer Liste der Geschwindigkeiten der Kugeln in der Reihenfolge, in der sie abgefeuert wurden, ob alle Kugeln zerstört wurden.

Die Regeln

• Die Eingabe ist eine Liste nicht negativer Ganzzahlen, die durch ein Trennzeichen und ein optionales Zeichen davor und danach getrennt sind. Dies sind gültige Eingaben: 1 2 3 4 5 6und [1,2,3,4,5,6]. Der Programmierer trifft die Wahl.
• Geben Sie einen Wahrheitswert aus, wenn mindestens eine Kugel für immer überlebt, andernfalls einen falschen Wert.
• Geschossgeschwindigkeiten werden in Einheiten pro Sekunde angegeben.
• Kugeln bewegen sich gleichzeitig und kontinuierlich.
• Aufzählungszeichen können bei Teilversätzen kollidieren.
• Mehrere Kugeln, die gleichzeitig genau die gleiche Position erreichen, entweder mit einem integralen oder einem gebrochenen Versatz vom Ursprung, kollidieren alle miteinander.

Beispiele

Stellt in diesen Diagrammen Gdie Waffe und >die Kugeln dar und ist *die Zeit, in der Kugeln kollidieren und explodieren.

Wahrheit

Eingang: 0

        0123456789
Time 0 G>
     1 G>
     2 G>
   ...

Ausgabe: 1

Eingang: 0 0 0

        0123456789
Time 0 G>
     1 G*
     2 G>
     3 G>
     4 G>
   ...

Ausgabe: 1

Eingang: 1

        0123456789
Time 0 G>
     1 G >
     2 G  >
     3 G   >
   ...

Ausgabe: 1

Eingang: 2 1

        0123456789
Time 0 G>
     1 G> >
     2 G >  >
     3 G  >   >
     4 G   >    >
   ...

Ausgabe: 1

Eingang: 2 3 1

        0123456789
Time 0 G>
     1 G> >
     2 G>  >>
     3 G >    *
     4 G  >
     5 G   >
   ...

Ausgabe: 1

Falsch

Eingang: 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

Ausgabe: 0

Eingang: 1 0 0 3

        Unit
        0123456789
Time 0 G>
     1 G>>
     2 G* >
     3 G>  >
     4 G   >>
     5 G     *

(Die zweite Kollision zum Zeitpunkt 4.5)
Ausgang:0

Eingang: 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

Ausgabe: 0

Eingang: 2 3 6

        Unit
        0123456789
Time 0 G>
     1 G> >
     2 G>  >>
     3 G      *

Ausgabe: 0

Python 2, 388 392 388 346 342 336 331 Bytes

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

Mein Gott, dieses Ding ist riesig, aber ich glaube, es funktioniert tatsächlich. Wenn Sie erst einmal alle Feinheiten gesehen haben, ist diese Herausforderung lächerlich schwer.

Ich bin mir nicht sicher, ob ich erklären kann, wie es im Detail funktioniert, ohne stundenlang zu tippen. Ich gebe nur eine Zusammenfassung.

Die große Haupt-While-Schleife wird so lange wiederholt, bis die Eingabeliste nicht mehr kleiner wird.

Die for - Schleife verschachtelt (können Sie eine verschachtelte for - Schleife glauben ist eigentlich die kürzeste hier?) In einer Schleife über jede Kugel Geschwindigkeit und Verwendungen numpy.rootszu berechnen berechnet , zu welchem Zeitpunkt die Kugel mit jeder Kugel kollidiert , die nach kommt. Hier ""wird Unendlich (keine Kreuzung) gemeint. Es muss eine zusätzliche Bedingung eingefügt werden, um sicherzustellen, dass angehaltene Aufzählungszeichen in dem Moment als kollidierend markiert werden, in dem sie erscheinen, und nicht zum Zeitpunkt Null.

Für jede Zahl verfolgen wir, welche Kugel am schnellsten getroffen wird, und oaktualisieren sie dann mit den minimalen Kollisionszeiten für die beteiligten Kugeln.

Nach Beendigung dieser Doppelschleife durchlaufen wir die Eingabeliste und löschen alle Aufzählungszeichen, die mindestens alle Kollisionszeiten (sofern vorhanden) kollidieren. Auf diese Weise können wir eine große Anzahl von Aufzählungszeichen gleichzeitig löschen, wenn alle gleichzeitig kollidieren.

Dann wiederholen wir den gesamten Vorgang für die verbleibenden Kugeln, da sie möglicherweise inzwischen in der Lage sind, festzustellen, dass die Kugeln, mit denen sie zusammengestoßen wären, zerstört wurden.

Sobald keine Aufzählungszeichen gelöscht sind (angezeigt durch die nicht verkleinernde Liste), verlassen wir die while-Schleife und geben die Länge der verbleibenden Liste aus. Somit druckt dieses Programm nicht nur die Wahrheit, wenn Aufzählungszeichen überleben, sondern tatsächlich genau die Anzahl der überlebenden Aufzählungszeichen.

EDIT: Besonderer Dank geht an feersum für die Generierung von Testfällen, die mir bei der Suche nach Fehlern helfen.

EDIT 2: 42 Bytes wurden gespeichert, indem die lineare Gleichung manuell gelöst wurde, anstatt numpy zu verwenden, und die Startzeiten in eine separate Liste aufgeteilt und eine Bedingung neu strukturiert wurden.

EDIT 3: 4 Bytes durch Umbenennen des Bereichs gespeichert

EDIT 4: 6 weitere Bytes wurden gespeichert, indem doppelte Leerzeichen durch Tabulatoren ersetzt wurden. Außerdem war feersum so freundlich, seine Implementierung mit Brüchen und Mengen zum Vergleich bereitzustellen. Ich habe ein bisschen Golf gespielt und es sind 331 Bytes, die meine Lösung binden.

BEARBEITEN 5: 5 Bytes wurden gespart, indem eine unnötige Initialisierung entfernt und eine Bedingung neu geschrieben wurde