Проблема N-тела

Адвент кода 2019 День 12

Попробуйте симулятор из части 1 с вводом головоломки!

Задача: Решите задачу для X, где…

Часть 1

X = the total energy in the system after simulating 1000 steps of the four moons' motion given in my scan

Часть 2

X = the step where all four moons repeat their initial state for the first time

Пример ввода

<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>

Представляет:

• x,y,z положения четырех лун Юпитера.

Часть 1

1. Простая часть (я надеюсь?): извлечение позиций
2. Понимание того, как вычисляется скорость и обновляются позиции
3. Еще одна легкая часть: вычисление полной энергии системы.
4. Письменный набросок моего рабочего алгоритма

Простая часть (я надеюсь?): извлечение позиций

Без регулярного выражения:

<x=2, y=-10, z=-7>

Trim off both ends
'x=2, y=-10, z=-7'

Split at ', '
['x=2','y=-10','z=-7']

Trim off the first two characters in each
['2','-10','-7']

Coerce to numbers
[2,-10,-7]

С регулярным выражением:

/w=(-?d+),?s?/g

Совпадения <x=2, y=-10, z=-7>:

Для каждого положения луны я затем получаю тот же список из трех совпадений, связанных с положениями x,y,z.

Понимание того, как вычисляется скорость и обновляются позиции

Факты:

• Каждая луна имеет 3-мерную позицию (x, y и z) — она задана в моих входных данных.
• Каждая луна имеет 3-мерную скорость (x, y и z) — все начинается с 0.

Движение моделируется за временные шаги.

Во время каждого из них:

1. Обновите скорость каждой луны, применив гравитацию
2. Обновите положение каждой луны, применив скорость

Обновите скорость каждой луны, применив гравитацию.

Чтобы применить гравитацию, рассмотрим каждую пару лун.

Лун четыре, поэтому

1,2
1,3
1,4
2,3
2,4
3,4

For i from 1 to (1 less than the number of moons):
  For j from i + 1 to (the number of moons):
    Compare moon i's x,y,z to j's x,y,z

Walkthrough:
i=1, j=2
i=1, j=3
i=1, j=4
i=2, j=3
i=2, j=4
i=3, j=4

По каждой оси (x, y и z) скорость каждой луны изменяется ровно на +1 или -1, чтобы стянуть луны вместе

Given two numbers - the velocities of a pair of moon's shared axis:
  If both are equal
    Do nothing
  Else, each differ
    Decrement the greater number by 1
    Increment the lesser number by 1

Walkthrough:
 5 <>  3
-1    +1

 2 <>  2
 -     -

 1 <>  4
+1    -1

Обновление положения каждой луны путем применения скорости

Просто добавьте скорость каждой луны к ее собственному положению.

Пример приведен:

Where positions are:
x= 1, y=2, z=3

And velocities are:
x=-2, y=0, z=3


New positions are:
   1    2    3
  -2   +0   +3
-----------------
x=-1, y=2, z=6

Velocities remain unchanged:
x=-2, y=0, z=3

Еще одна простая часть: вычисление полной энергии системы.

For each moon:
Calculate the product of two sums:
  1. Sum of the absolute values of the x,y,z positions
  2. Sum of the absolute values of the x,y,z velocities
Return the sum of all products

Письменный набросок моего рабочего алгоритма

Split the input at each newline character to create an array of strings

Modify each string according to the following operations:
  Use the regular expression on each string to create a 3-element array of strings
  Coerce each string to a number
  Based on the order of the match (0,1,2), set each as value of the respective x,y,z keys inside an object that stores positions and velocities
  Return the object with stored x,y,z key-value pairs for position and velocity

For each step from 0 to i - as defined by the input parameter
  Compare each pair of moons
    Update each moon's velocity x,y,z based on whether the position x,y,z is <,>,== the other moon's position
  Update each moon's position x,y,z by adding the current velocity x,y,z

Calculate the total energy by following these operations:
Accumulate a sum - starting at 0
  For each moon
    Calculate the product of two sums:
      1. Sum of the absolute values of the x,y,z positions
      2. Sum of the absolute values of the x,y,z velocities
  Add the product to the accumulating sum

Return the sum

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

Создание анимации кажется излишним.

Часть 2

1. Еще одна задача на производительность и оптимизацию алгоритма, я полагаю?
2. LCM & GCD
3. Я пытался, но не смог

Еще одна проблема производительности и оптимизации алгоритмов, я полагаю?

• Вот что я подумал.
• Но вскоре после того, как я «сдался» и пролистал сегодняшний мегатред решений, оказалось, что я ошибался

LCM & GCD

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

Я попытался, но не смог

• Я написал алгоритм, который определяет шаг, когда каждая позиционная координата для каждой луны возвращается на себя.
• Я заново создал обе полезные функции для LCM & GCD после того, как нашел в Интернете статьи, иллюстрирующие код.
• Я написал несколько редукторов, которые вычисляют LCM для различных значений (например, для аналогичных осей каждой луны, для каждой оси одной луны).
• LCM всегда были экспоненциально больше, чем правильные ответы, указанные в инструкции.

Я чувствую, что я очень близок.

Но я чувствую, что любая дальнейшая работа только расстроит меня безрезультатно.

Празднование моих достижений

• Я решил часть 1, которая оказалась проще, чем я предполагал при первом взгляде на эту головоломку!
• Я понял и заново создал алгоритмы для вычисления LCM и GCD.
• Я построил симулятор четырех лун, вращающихся вокруг невидимого Юпитера.

Облом:

• Я не решил Часть 2
• На этот раз никаких GIF, так как инструкции отлично иллюстрируют работу моих алгоритмов.

Пора двигаться дальше!