Cuando las balas chocan

Este desafío se basa en un acertijo que leí en algún libro hace un tiempo, que encontré nuevamente aquí . Se trata de balas disparadas desde un arma una vez por segundo a velocidades variables que viajan en línea recta para siempre. Cuando una bala golpea a otra, ambas se destruyen por completo. (Siéntase libre de reemplazar todas las instancias de "bala" con "misil").

La tarea

Dada una lista de velocidades de bala en el orden en que se disparan, determina si todas las balas se destruyen.

Las normas

• La entrada es una lista de enteros no negativos, separados por cualquier delimitador y con un carácter opcional antes y después. Estas son entradas válidas: 1 2 3 4 5 6y [1,2,3,4,5,6]. El programador hace la elección.
• Produzca un valor verdadero si al menos una bala sobrevive para siempre y un valor falso de lo contrario.
• Las velocidades de bala se dan en unidades por segundo.
• Las balas se mueven simultáneamente y continuamente.
• Las balas pueden colisionar en compensaciones fraccionales.
• Múltiples balas que simultáneamente alcanzan exactamente la misma posición, ya sea en un desplazamiento integral o fraccional desde el origen, todas chocan entre sí.

Ejemplos

En estos diagramas, Grepresenta el arma, >las balas, y *son momentos en que las balas chocan y explotan.

Verdad

Entrada: 0

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

Salida: 1

Entrada: 0 0 0

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

Salida: 1

Entrada: 1

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

Salida: 1

Entrada: 2 1

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

Salida: 1

Entrada: 2 3 1

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

Salida: 1

Falsa

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

Salida: 0

Entrada: 1 0 0 3

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

(La segunda colisión es en el momento 4.5)
Salida:0

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

Salida: 0

Entrada: 2 3 6

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

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

Dios mío, esto es enorme, pero creo que realmente funciona. Una vez que veas todas sus complejidades, este desafío es ridículamente difícil.

No estoy seguro si puedo explicar cómo funciona en detalle sin escribir durante horas, así que solo daré un resumen ejecutivo.

El gran bucle while principal se repite hasta que la lista de entrada no se contrae.

El bucle anidado (¿puedes creer que un bucle anidado es en realidad el más corto aquí?) Recorre cada velocidad de viñeta y se usa numpy.rootspara calcular los cálculos en qué momento esa viñeta colisionará con cada viñeta que viene después. Aquí,"" se está utilizando para significar infinito (sin intersección). Se debe incluir un condicional adicional para garantizar que las viñetas detenidas se marquen como colisionantes en el momento en que aparecen en lugar de en el momento cero.

Para cada número, hacemos un seguimiento de la bala que golpeará más pronto, si corresponde, y luego ose actualiza con los tiempos mínimos de colisión para las balas involucradas.

Después de que este doble ciclo termina, iteramos sobre la lista de entrada y eliminamos cualquier viñeta que colisionará al mínimo de todos los tiempos de colisión, si corresponde. Esto nos permite eliminar simultáneamente grandes cantidades de viñetas si todas chocan en el mismo momento.

Luego, repetimos todo el proceso en las balas restantes, ya que pueden ser capaces de obtener ahora que las balas con las que habrían chocado se han destruido.

Tan pronto como no se eliminen las viñetas (lo que indica que la lista no se reduce), escapamos del ciclo while e imprimimos la longitud de la lista restante. Por lo tanto, este programa no solo imprime la verdad si las balas sobreviven, sino que imprime exactamente la cantidad de balas que sobreviven.

EDITAR: Un agradecimiento especial a feersum por generar casos de prueba para ayudarme a encontrar errores.

EDIT 2: ahorró 42 bytes resolviendo la ecuación lineal a mano en lugar de usar numpy y dividiendo los tiempos de inicio en una lista separada y reestructurando un condicional.

EDIT 3: 4 bytes guardados al cambiar el nombre del rango

EDIT 4: ahorró 6 bytes más al reemplazar los espacios dobles con pestañas. Además, feersum tuvo la amabilidad de proporcionar su implementación utilizando fracciones y conjuntos para la comparación. Lo he jugado un poco y llega a 331 bytes, uniendo mi solución.

EDITAR 5: ahorró 5 bytes eliminando una inicialización innecesaria y reescribiendo un condicional