The space near Jupiter is not a very safe place; you need to be careful of a [big distracting red spot](https://en.wikipedia.org/wiki/Great_Red_Spot), extreme [radiation](https://en.wikipedia.org/wiki/Magnetosphere_of_Jupiter), and a [whole lot of moons](https://en.wikipedia.org/wiki/Moons_of_Jupiter#List) swirling around. You decide to start by tracking the four largest moons: *Io*, *Europa*, *Ganymede*, and *Callisto*. After a brief scan, you calculate the *position of each moon* (your puzzle input). You just need to *simulate their motion* so you can avoid them. Each moon has a 3-dimensional position (`x`, `y`, and `z`) and a 3-dimensional velocity. The position of each moon is given in your scan; the `x`, `y`, and `z` velocity of each moon starts at `0`. Simulate the motion of the moons in *time steps*. Within each time step, first update the velocity of every moon by applying *gravity*. Then, once all moons' velocities have been updated, update the position of every moon by applying *velocity*. Time progresses by one step once all of the positions are updated. To apply *gravity*, consider every *pair* of moons. On each axis (`x`, `y`, and `z`), the velocity of each moon changes by *exactly +1 or -1* to pull the moons together. For example, if Ganymede has an `x` position of `3`, and Callisto has a `x` position of `5`, then Ganymede's `x` velocity *changes by +1* (because `5 > 3`) and Callisto's `x` velocity *changes by -1* (because `3 < 5`). However, if the positions on a given axis are the same, the velocity on that axis *does not change* for that pair of moons. Once all gravity has been applied, apply *velocity*: simply add the velocity of each moon to its own position. For example, if Europa has a position of `x=1, y=2, z=3` and a velocity of `x=-2, y=0,z=3`, then its new position would be `x=-1, y=2, z=6`. This process does not modify the velocity of any moon. For example, suppose your scan reveals the following positions: ``` ``` Simulating the motion of these moons would produce the following: ``` After 0 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 1 step: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 2 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 3 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 4 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 5 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 6 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 7 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 8 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 9 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 10 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= ``` Then, it might help to calculate the *total energy in the system*. The total energy for a single moon is its *potential energy* multiplied by its *kinetic energy*. A moon's *potential energy* is the sum of the [absolute values](https://en.wikipedia.org/wiki/Absolute_value) of its `x`, `y`, and `z` position coordinates. A moon's *kinetic energy* is the sum of the absolute values of its velocity coordinates. Below, each line shows the calculations for a moon's potential energy (`pot`), kinetic energy (`kin`), and total energy: ``` Energy after 10 steps: pot: 2 + 1 + 3 = 6; kin: 3 + 2 + 1 = 6; total: 6 * 6 = 36 pot: 1 + 8 + 0 = 9; kin: 1 + 1 + 3 = 5; total: 9 * 5 = 45 pot: 3 + 6 + 1 = 10; kin: 3 + 2 + 3 = 8; total: 10 * 8 = 80 pot: 2 + 0 + 4 = 6; kin: 1 + 1 + 1 = 3; total: 6 * 3 = 18 Sum of total energy: 36 + 45 + 80 + 18 = 179 ``` In the above example, adding together the total energy for all moons after 10 steps produces the total energy in the system, `*179*`. Here's a second example: ``` ``` Every ten steps of simulation for 100 steps produces: ``` After 0 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 10 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 20 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 30 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 40 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 50 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 60 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 70 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 80 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 90 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 100 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= Energy after 100 steps: pot: 8 + 12 + 9 = 29; kin: 7 + 3 + 0 = 10; total: 29 * 10 = 290 pot: 13 + 16 + 3 = 32; kin: 3 + 11 + 5 = 19; total: 32 * 19 = 608 pot: 29 + 11 + 1 = 41; kin: 3 + 7 + 4 = 14; total: 41 * 14 = 574 pot: 16 + 13 + 23 = 52; kin: 7 + 1 + 1 = 9; total: 52 * 9 = 468 Sum of total energy: 290 + 608 + 574 + 468 = 1940 ``` *What is the total energy in the system* after simulating the moons given in your scan for `1000` steps? Your puzzle answer was `7687`. \--- Part Two --- ---------- All this drifting around in space makes you wonder about the nature of the universe. Does history really repeat itself? You're curious whether the moons will ever return to a previous state. Determine *the number of steps* that must occur before all of the moons' *positions and velocities* exactly match a previous point in time. For example, the first example above takes `2772` steps before they exactly match a previous point in time; it eventually returns to the initial state: ``` After 0 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 2770 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 2771 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= After 2772 steps: pos=, vel= pos=, vel= pos=, vel= pos=, vel= ``` Of course, the universe might last for a *very long time* before repeating. Here's a copy of the second example from above: ``` ``` This set of initial positions takes `4686774924` steps before it repeats a previous state! Clearly, you might need to *find a more efficient way to simulate the universe*. *How many steps does it take* to reach the first state that exactly matches a previous state? Your puzzle answer was `334945516288044`. Both parts of this puzzle are complete! They provide two gold stars: \*\* At this point, you should [return to your Advent calendar](/2019) and try another puzzle. If you still want to see it, you can [get your puzzle input](12/input).