Рой частиц

Адвент кода 2017 День 20

Часть 1

1. Объекты движутся… в пространстве… снова!
2. Создание структуры данных частиц
3. Выполнение каждого движения частицы
4. Определение победителя
5. Сколько тиков для выявления неизменного победителя?

Объекты движутся… в пространстве… снова!

Суть этой задачи заключается в следующем:

• Некоторые объекты могут начать движение вблизи центральной точки, а затем, в конечном итоге, удаляться от нее.
• Другие объекты могут двигаться по кругу с разной длиной радиуса вокруг центральной точки
• Другие объекты могут двигаться к центральной точке, но в конечном итоге удаляться от нее.

Задача состоит в следующем:
Решите задачу X, где X =…

Частица, которая будет находиться ближе всего к позиции <0,0,0> в долгосрочной перспективе.

Оценка моей уверенности:

• Я могу разобрать входные данные для девяти значений каждой частицы.
• Я могу выполнить необходимые вычисления, которые корректируют положение и скорость каждой частицы на каждой итерации
• Я могу отслеживать манхэттенское расстояние каждой частицы от <0,0,0> после каждой итерации.
• Но сколько итераций мне нужно обработать, чтобы определить правильную частицу?
• И как я буду определять эту частицу? Ту, у которой наименьшее среднее Манхэттенское расстояние?

На данный момент я:

• Воодушевлен написанием необходимых алгоритмов для создания программы движения частиц
• Ожидаю, что не смогу сгенерировать правильный ответ для части 1

Создание структуры данных частицы

Каждая частица имеет девять атрибутов:

Мне нужно будет отслеживать и манхэттенское расстояние от положения частицы.

Эта структура данных должна работать:

{
  p: [X,Y,Z],
  a: [X,Y,Z],
  v: [X,Y,Z],
  md: [
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    ...
  ]
}

Чтобы создать ее, я использую следующее регулярное выражение:

/-?d+/g

• Оно извлекает из строки каждое целое число — положительное или отрицательное.
• Я могу быть уверен, что оно всегда будет соответствовать девяти целым числам.
• И что эти целые числа всегда будут в одном и том же порядке.

Выполнение каждого движения частицы

Как указано в инструкции, каждый тик:

Increase the X velocity by the X acceleration.
Increase the Y velocity by the Y acceleration.
Increase the Z velocity by the Z acceleration.
Increase the X position by the X velocity.
Increase the Y position by the Y velocity.
Increase the Z position by the Z velocity.

• Я делаю это алгоритмически, используя map() на моем массиве объектов частиц
• Обновление соответствующего индекса списка, связанного с соответствующим ключом на каждом объекте частицы

Кроме того, я вставляю новое расстояние Манхэттена в конец массива md каждого объекта.

Определение победителя

В конце некоторого произвольного количества тиков:

Generate an identically-ordered list of particles
  But where each element is a single floating-point number:
    The average of each of that element's Manhattan Distances
Return the index of the item with the lowest average Manhattan Distance

Сколько тиков для выявления неизменного победителя?

Методом проб и ошибок:

• 10 тиков?
• 100 тиков?
• 1000 тиков?
• 10000 тиков?

Смотрите сами!

Что я видел, когда мой алгоритм работал над правильным ответом:

Часть 2

1. Обнаружение столкновений? Это усложняет ситуацию… но на сколько?
2. Сколько тиков нужно сделать, чтобы найти оставшиеся неизменные частицы?

Обнаружение столкновений? Это усложняет ситуацию… но на сколько?

В первой части моей функции map() было достаточно для симуляции одновременного движения.

Но в этот раз мне придется пойти на шаг дальше:

Throughout the use of map()
  Flag any positions that appear twice within a tick
  As long as at least one position appears twice
    For each position at which point a collision occurred
      Filter the list of particles to include any at the current position
        For each identified particle
          Remove that particle from the original, working list
  Print the length of the working list of particles

Сколько тиков нужно сделать, чтобы найти оставшиеся неизменными частицы?

Снова победа методом проб и ошибок:

• 10 тиков?
• 100 тиков?
• 1000 тиков?
• 10000 тиков?

Что я видел, когда мой алгоритм работал над правильным ответом:

Я сделал это!!!

• Я решил обе части!…
• головоломки с объектами, движущимися в трех измерениях!…
• За, как мне показалось, рекордное время!
• И очень мало кода!

В самом начале работы над этой головоломкой я сомневался, что решу первую часть.

И вот, спустя всего несколько часов я здесь, с еще двумя золотыми звездами!

Либо эта головоломка относится к числу более легких головоломок Дня 20, либо у меня получается решать эти головоломки лучше.

Как бы то ни было, сегодняшняя головоломка была освежающим отступлением от кошмара предыдущего дня с нарезкой и объединением массивов.