When Bullets Collide

Question

This challenge is based off a riddle I read in some book a while ago, which I found again here. It is about bullets fired from a gun once per second at varying speeds that travel in a straight line forever. When one bullet hits another, both are destroyed completely. (Feel free to replace all instances of "bullet" with "missile".)

The Task

Given a list of bullet speeds in the order they're fired in, determine whether all bullets are destroyed.

The Rules

• Input is a list of non-negative integers, separated by any delimiter and with one optional character before and after. These are valid inputs: 1 2 3 4 5 6 and [1,2,3,4,5,6]. The programmer makes the choice.
• Output a truthy value if at least one bullet survives forever and a falsy value otherwise.
• Bullet speeds are given in units per second.
• Bullets move simultaneously and continuously.
• Bullets may collide at fractional offsets.
• Multiple bullets which simultaneously reach the exact same position, whether at an integral or fractional offset from the origin, all collide with each other.

Examples

In these diagrams, G represents the gun, > the bullets, and * are times when bullets collide and explode.

Truthy

Input: 0

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

Output: 1

---

Input: 0 0 0

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

Output: 1

---

Input: 1

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

Output: 1

---

Input: 2 1

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

Output: 1

---

Input: 2 3 1

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

Output: 1

---

Falsy

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

Output: 0

---

Input: 1 0 0 3

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

(The second collision is at time 4.5)
Output: 0

---

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

Output: 0

---

Input: 2 3 6

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

Output: 0

Answer 1

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

My god this thing is huge, but I believe it actually does work. Once you see all the intricacies of it, this challenge is ridiculously hard.

I'm not sure if I can explain how it works in detail without typing for hours, so I'll just give an executive summary.

The big main while loop is looping until the input list does not shrink.

The nested for loop (can you believe a nested for loop is actually the shortest here?) loops over each bullet speed and uses numpy.roots to calculate calculates at which time that bullet will collide with each bullet that comes after. Here, "" is being used to mean infinity (no intersection). An extra conditional has to be included to ensure that stopped bullets are marked as colliding the moment they appear rather than at time zero.

For each number we keep track of which bullet it will hit soonest, if any, and then o is updated with the minimum collision times for the involved bullets.

After this double loop terminates, we iterate over the input list and delete any bullet that will collide at the minimum of all collision times, if any. This allows us to simultaneously delete large numbers of bullets if they all happen to collide at the same moment.

Then we repeat the entire process on the remaining bullets, since they may be able to get by now that the bullets that they would have collided with have been destroyed.

As soon as no bullets are deleted (indicated by the list not shrinking), we escape the while loop and print the length of the remaining list. Thus, this program not only prints truthy if bullets survive, it actually prints exactly the number of bullets that survive.

EDIT: Special thanks to feersum for generating test cases to help me find bugs.

EDIT 2: Saved 42 bytes by solving the linear equation by hand instead of using numpy, and splitting out the starting times into a separate list and restructuring a conditional.

EDIT 3: Saved 4 bytes by renaming range

EDIT 4: Saved 6 more bytes by replacing double spaces with tabs. Also, feersum was kind enough to provide his implementation using fractions and sets for comparison. I've golfed it a bit and it comes out to 331 bytes, tying my solution.

EDIT 5: saved 5 bytes by removing an unnecessary initialization and rewriting a conditional