# Advent of Code 2019 - Day 12

# Advent of Code 2019 - Day 12

*Find my full solution repo here.*

This was a nice puzzle, even though I got stuck on the second half for a couple days. I tried a couple wrong approaches to storing and looking up previous states - namely binary trees and dictionary keys with a try/catch lookup.

Eventually, I caved and looked up a hint on
reddit. One commenter laid out helpful
insights (the main one being that the repeated state **must** be the initial
state, because all future states are children of the first) in a way that the
problem was still interesting to solve.

## Adding Up Energy

The first part went smoothly since implementing the solution is mostly just
following the instructions. I made a `Body`

class that had the required
behavior and kept a list of 4 of them to simulate the moons.

```
class Body:
# Position {'x': n, 'y': n, 'z': n}
def __init__(self, position):
self.initial_pos = position.copy()
self.position = position
self.velocity = {'x': 0, 'y': 0, 'z': 0}
def update_velocity(self, velocity):
self.velocity['x'] += velocity['x']
self.velocity['y'] += velocity['y']
self.velocity['z'] += velocity['z']
def update_position(self):
self.position['x'] += self.velocity['x']
self.position['y'] += self.velocity['y']
self.position['z'] += self.velocity['z']
```

The code for advancing the simulation by a step is simple enough.
`update_velocities(body1, body2)`

finds the delta for each velocity axis and
then applies it to both bodies. `update_position()`

applies each body’s
velocity to its position.

```
def advance_time(bodies):
for i in range(0, len(bodies)):
for j in range(i+1, len(bodies)):
update_velocities(bodies[i], bodies[j])
for body in bodies:
body.update_position()
```

To find the energy, just iterate through each body and sum the absolute value of each position & velocity axis.

## The Hard Part

The second part was much tougher for me. Both methods of storing and comparing historical values that I tried (trees and state as dictionary keys) was slow. With these approaches, the simulation was completing between 1.4m-2.3m steps in 30 seconds. Given that the example required 4-ish billion steps - this was way too slow.

I beat my head on the wall for a long time on this problem and eventually gave in and got a hint off the AoC reddit. A nice user pointed out that:

a) The repeated state must be the same as the initial state, and b) You can find the period of each axis individually

Wow! Those are both great insights that make the correct approach so much clearer. Another thing this puzzle taught me is that I should spend more time considering approaches from a logical/math viewpoint. Doing so could give a lot of insight into what needs to be computed in the first place.

Without further ado, here is my solution for part 2.

```
def found_all_steps(steps):
for i in range(3):
if steps[i] < 0:
return False
return True
def is_same_state(bodies, axis):
found = []
for i in range(4):
same_pos = bodies[i].position[axis] == bodies[i].initial_pos[axis]
same_vel = bodies[i].velocity[axis] == 0
found.append(same_pos and same_vel)
return all(found)
bodies = parse_input("./input/day12.txt")
axes = ['x', 'y', 'z']
steps = [-1, -1, -1]
step_ct = 0
while not found_all_steps(steps):
advance_time(bodies)
step_ct += 1
for index, axis in enumerate(axes):
if steps[index] < 0 and is_same_state(bodies, axis):
steps[index] = step_ct
print("part 2: " + str(lcm.reduce(steps)))
```

The key is to find the first step at which each axis repeats and then find the least common multiple (I’m using numpy for this).

Next time, I’m going to do more thinking and less coding when something seems like the obviously wrong path.

*Find my full solution repo here.*