Quand les balles entrent en collision

Ce défi est basé sur une énigme que j'ai lue dans un livre il y a quelque temps, que j'ai retrouvée ici . Il s'agit de balles tirées à partir d'une arme à feu une fois par seconde à des vitesses variables qui se déplacent en ligne droite pour toujours. Lorsqu'une balle frappe une autre, les deux sont complètement détruites. (N'hésitez pas à remplacer toutes les instances de "balle" par "missile".)

La tâche

Étant donné la liste des vitesses des balles dans l'ordre dans lequel elles sont tirées, déterminez si toutes les balles sont détruites.

Les règles

• L'entrée est une liste d'entiers non négatifs, séparés par un délimiteur et avec un caractère facultatif avant et après. Ce sont des entrées valides: 1 2 3 4 5 6et [1,2,3,4,5,6]. Le programmeur fait le choix.
• Sortez une valeur véridique si au moins une balle survit éternellement et une valeur fausse sinon.
• Les vitesses des balles sont données en unités par seconde.
• Les balles se déplacent simultanément et en continu.
• Les balles peuvent entrer en collision avec des décalages fractionnaires.
• Plusieurs balles qui atteignent simultanément la même position exacte, que ce soit à un décalage intégral ou fractionné par rapport à l'origine, entrent en collision les unes avec les autres.

Exemples

Dans ces diagrammes, Greprésente l'arme, >les balles et *les moments où les balles entrent en collision et explosent.

Truthy

Contribution: 0

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

Production: 1

Contribution: 0 0 0

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

Production: 1

Contribution: 1

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

Production: 1

Contribution: 2 1

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

Production: 1

Contribution: 2 3 1

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

Production: 1

Falsy

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

Production: 0

Contribution: 1 0 0 3

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

(La deuxième collision est à l'instant 4.5)
Sortie:0

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

Production: 0

Contribution: 2 3 6

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

Production: 0

Python 2, 388 392 388 346 342 336 331 octets

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

Mon dieu, ce truc est énorme, mais je crois que ça marche vraiment. Une fois que vous en voyez toutes les subtilités, ce défi est ridiculement difficile.

Je ne sais pas si je peux expliquer comment cela fonctionne en détail sans taper pendant des heures, je vais donc donner un résumé.

La grande boucle while principale est en boucle jusqu'à ce que la liste d'entrée ne rétrécisse pas.

La boucle imbriquée pour (pouvez-vous croire qu'une boucle imbriquée est en fait la plus courte ici?) Boucle sur chaque vitesse de balle et utilise numpy.rootspour calculer calcule à quel moment cette balle entrera en collision avec chaque puce suivante. Ici, ""est utilisé pour signifier l'infini (pas d'intersection). Une condition supplémentaire doit être incluse pour garantir que les balles arrêtées sont marquées comme entrant en collision au moment où elles apparaissent plutôt qu'au moment zéro.

Pour chaque numéro, nous gardons une trace de la balle qu'elle touchera le plus tôt, le cas échéant, puis nous mettons à ojour les temps de collision minimum pour les balles impliquées.

Une fois cette double boucle terminée, nous parcourons la liste d'entrée et supprimons toute puce qui entrera en collision au minimum de tous les temps de collision, le cas échéant. Cela nous permet de supprimer simultanément un grand nombre de balles si elles entrent toutes en collision au même moment.

Ensuite, nous répétons tout le processus sur les balles restantes, car ils peuvent peut-être maintenant que les balles avec lesquelles ils seraient entrés en collision ont été détruites.

Dès qu'aucune puce n'est supprimée (indiquée par la liste ne rétrécissant pas), nous échappons à la boucle while et imprimons la longueur de la liste restante. Ainsi, ce programme imprime non seulement vrai si les balles survivent, il imprime en fait exactement le nombre de balles qui survivent.

EDIT: Un merci spécial à feersum pour avoir généré des cas de test pour m'aider à trouver des bogues.

EDIT 2: économisé 42 octets en résolvant l'équation linéaire à la main au lieu d'utiliser numpy, et en divisant les heures de début dans une liste séparée et en restructurant un conditionnel.

EDIT 3: 4 octets enregistrés en renommant la plage

EDIT 4: économisé 6 octets supplémentaires en remplaçant les espaces doubles par des tabulations. De plus, feersum a eu la gentillesse de fournir son implémentation en utilisant des fractions et des ensembles pour comparaison. Je l'ai un peu joué au golf et cela fait 331 octets, liant ma solution.

EDIT 5: économisé 5 octets en supprimant une initialisation inutile et en réécrivant un conditionnel