Когда пули сталкиваются

Эта проблема основана на загадке, которую я прочитал в какой-то книге некоторое время назад, которую я снова нашел здесь . Речь идет о пулях, выпущенных из пистолета один раз в секунду на разных скоростях, которые движутся по прямой навсегда. Когда одна пуля попадает в другую, обе полностью уничтожаются. (Не стесняйтесь заменить все экземпляры «пули» на «ракеты».)

Задание

Учитывая список скоростей пули в том порядке, в котором они выпущены, определите, все ли пули уничтожены.

Правила

• Ввод - это список неотрицательных целых чисел, разделенных любым разделителем и с одним необязательным символом до и после. Это действительные данные: 1 2 3 4 5 6и [1,2,3,4,5,6]. Программист делает выбор.
• Выведите истинное значение, если хотя бы одна пуля выживет навсегда, а в противном случае - ложное значение.
• Скорости пули приведены в единицах в секунду.
• Пули движутся одновременно и непрерывно.
• Пули могут сталкиваться с небольшим смещением.
• Несколько пуль, которые одновременно достигают одной и той же позиции, с интегральным или дробным смещением от начала координат, сталкиваются друг с другом.

Примеры

На этих диаграммах Gизображены пистолет, >пули и *времена, когда пули сталкиваются и взрываются.

Truthy

Входные данные: 0

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

Выход: 1

Входные данные: 0 0 0

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

Выход: 1

Входные данные: 1

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

Выход: 1

Входные данные: 2 1

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

Выход: 1

Входные данные: 2 3 1

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

Выход: 1

Falsy

Входные данные: 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

Выход: 0

Входные данные: 1 0 0 3

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

(Второе столкновение происходит в момент времени 4.5).
Вывод:0

Входные данные: 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

Выход: 0

Входные данные: 2 3 6

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

Выход: 0

Python 2, 388 392 388 346 342 336 331 байт

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

Боже мой, эта вещь огромна, но я верю, что она действительно работает. После того, как вы увидите все его тонкости, это нелепо сложно.

Я не уверен, смогу ли я объяснить, как это работает подробно, не печатая часами, поэтому я просто дам резюме.

Большой основной цикл while цикличен до тех пор, пока входной список не сжимается.

Вложенный цикл for (можете ли вы верить, что вложенный цикл for здесь на самом деле самый короткий?) Зацикливается на каждой скорости пули и использует numpy.rootsдля вычисления вычислений, в какое время эта пуля столкнется с каждой следующей пули. Здесь ""используется для обозначения бесконечности (без пересечения). Необходимо добавить дополнительное условие, чтобы гарантировать, что остановленные пули отмечены как сталкивающиеся в момент их появления, а не в нулевой момент времени.

Для каждого номера мы отслеживаем, какая пуля попадет быстрее всего, если таковая имеется, а затем oобновляется с минимальным временем столкновения для задействованных пуль.

После завершения этого двойного цикла мы перебираем входной список и удаляем любую пулю, которая будет сталкиваться как минимум за все время столкновения, если таковые имеются. Это позволяет нам одновременно удалять большое количество пуль, если все они сталкиваются в один и тот же момент.

Затем мы повторяем весь процесс с оставшимися пулями, так как они уже могут получить, что пули, с которыми они столкнулись, были уничтожены.

Как только маркеры не будут удалены (на что указывает список, не сужающийся), мы выходим из цикла while и печатаем длину оставшегося списка. Таким образом, эта программа не только печатает правдиво, если пули выживают, она на самом деле печатает ровно количество выживших пуль.

РЕДАКТИРОВАТЬ: Отдельное спасибо feersum за создание контрольных примеров, чтобы помочь мне найти ошибки.

РЕДАКТИРОВАТЬ 2: Сохранить 42 байта, решая линейное уравнение вручную, вместо того, чтобы использовать NumPy, и разделить начальные времена в отдельный список и реструктурировать условное.

РЕДАКТИРОВАТЬ 3: Сохранено 4 байта путем переименования диапазона

РЕДАКТИРОВАТЬ 4: Сохранено еще 6 байтов, заменив двойные пробелы с вкладками. Также feersum был достаточно любезен, чтобы предоставить свою реализацию, используя для сравнения дроби и множества. Я немного поиграл в гольф, и он достигает 331 байта, связывая мое решение.

РЕДАКТИРОВАТЬ 5: сэкономил 5 байтов, удалив ненужную инициализацию и переписав условную