9 votes

Day 12: The N-Body Problem

Automatically posted December 12, 2019 (edited December 12, 2019)

Tags: advent of code.2019

Today's problem description: https://adventofcode.com/2019/day/12

Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

7 comments

PapaNachos

December 12, 2019 (edited December 12, 2019)

Link

I had been staying up to do these when they were released at midnight, but I was tired last night and so decided to work on this one later, so I'm a bit behind. But since I'm going at a chill pace...

I had been staying up to do these when they were released at midnight, but I was tired last night and so decided to work on this one later, so I'm a bit behind. But since I'm going at a chill pace anyway, I felt like making my code less janky than I might otherwise. Also, this input was simple enough that I didn't even bother parsing it, I just put it in manually.

Part 1 - Python

I create moon objects that have all the behaviors I need and just let them run. After 1000 steps I print out the value. In the actual simulation it's compartmentalized enough that I spend more code on the output than on the simulation. I figured this might be helpful for Part 2, and I think it will be.

class moon:
    def __init__(self, name, x_pos, y_pos, z_pos):
        self.x_pos = x_pos
        self.y_pos = y_pos
        self.z_pos = z_pos
        self.x_vel = 0
        self.y_vel = 0
        self.z_vel = 0
        self.name = name
    def calc_potential_energy(self):
        return abs(self.x_pos) + abs(self.y_pos) + abs(self.z_pos)
    def calc_kinetic_energy(self):
        return abs(self.x_vel) + abs(self.y_vel) + abs(self.z_vel)
    def calc_total_energy(self):
        return (self.calc_potential_energy() * self.calc_kinetic_energy())
    def apply_gravity(self, moon_list):
        for moon in moon_list:
            if moon is not self:
                if super_verbose:
                    print(f"Comparing {self.name} to {moon.name}")
                x_mid = (self.x_pos + moon.x_pos)/2
                if self.x_pos > x_mid:
                      self.x_vel = self.x_vel - 1
                elif self.x_pos < x_mid:
                      self.x_vel = self.x_vel + 1
                y_mid = (self.y_pos + moon.y_pos)/2
                if self.y_pos > y_mid:
                      self.y_vel = self.y_vel - 1
                elif self.y_pos < y_mid:
                      self.y_vel = self.y_vel + 1
                z_mid = (self.z_pos + moon.z_pos)/2
                if self.z_pos > z_mid:
                      self.z_vel = self.z_vel - 1
                elif self.z_pos < z_mid:
                      self.z_vel = self.z_vel + 1
    def move_it_move_it(self):
        self.x_pos = self.x_pos + self.x_vel
        self.y_pos = self.y_pos + self.y_vel
        self.z_pos = self.z_pos + self.z_vel
             
input_string = """<x=-17, y=9, z=-5>
<x=-1, y=7, z=13>
<x=-19, y=12, z=5>
<x=-6, y=-6, z=-4>"""

#Real
Io = moon("Io", -17, 9, -5)
Europa = moon("Europa", -1, 7, 13)
Ganymede = moon("Ganymede", -19, 12, 5)
Callisto = moon("Callisto", -6, -6, -4)

#Example1:
#Io = moon("Io", -1, 0, 2)
#Europa = moon("Europa", 2, -10, -7)
#Ganymede = moon("Ganymede", 4, -8, 8)
#Callisto = moon("Callisto", 3, 5, -1)

moon_list = [Io, Europa, Ganymede, Callisto]


step_max = 1000
step = 0
verbose = False
super_verbose = False
while step < step_max:
    step = step + 1
    for moon in moon_list:
        moon.apply_gravity(moon_list)
    for moon in moon_list:
        moon.move_it_move_it()
        if verbose:
            print("-------------")
            print(f"Step: {step}")
            print(moon.name)
            print(f"Positions: X: {moon.x_pos}, Y: {moon.y_pos}, Z: {moon.z_pos}")
            print(f"Velocities: X: {moon.x_vel}, Y: {moon.y_vel}, Z: {moon.z_vel}")
            print(f"Enrgy: Kinetic: {moon.calc_kinetic_energy()}, Potential: {moon.calc_potential_energy()}, Total: {moon.calc_total_energy()}")
print("Final Results:")
for moon in moon_list: 
    print("-------------")
    print(moon.name)
    print(f"Positions: X: {moon.x_pos}, Y: {moon.y_pos}, Z: {moon.z_pos}")
    print(f"Velocities: X: {moon.x_vel}, Y: {moon.y_vel}, Z: {moon.z_vel}")
    print(f"Energy: Kinetic: {moon.calc_kinetic_energy()}, Potential: {moon.calc_potential_energy()}, Total: {moon.calc_total_energy()}")

Part 2 - Python

Part 2 was taking forever (3*10^14, awesome), so I got annoyed and worked on a much more efficient solution. Since the different axes don't interact at all, I could break it down into component vectors and deal with each one independently. Then find the Least Common Multiple (LCM) of the number of steps each took to repeat, which is the solution. Another way to do it would be to find all the prime factors of each number and then multiply them all together accounting for duplicates. By that I mean if you have the prime factors of x = [2,3,3,5], y = [3,3,7,11] and z = [2, 2, 3] then your solution should be whatever you get when you multiply [2, 2, 3, 3, 5, 7, 11] together. It probably would have been faster to compute than my LCM, but it would have been more annoying to write

x_steps = 0
y_steps = 0
z_steps = 0

for vector in ["x", "y", "z"]:
    class moon:
        def __init__(self, name, x_pos, y_pos, z_pos):
            self.x_pos = x_pos
            self.y_pos = y_pos
            self.z_pos = z_pos
            self.x_vel = 0
            self.y_vel = 0
            self.z_vel = 0
            self.name = name
        def calc_potential_energy(self):
            return abs(self.x_pos) + abs(self.y_pos) + abs(self.z_pos)
        def calc_kinetic_energy(self):
            return abs(self.x_vel) + abs(self.y_vel) + abs(self.z_vel)
        def calc_total_energy(self):
            return (self.calc_potential_energy() * self.calc_kinetic_energy())
        def apply_gravity(self, moon_list):
            for moon in moon_list:
                if moon is not self:
                    if super_verbose:
                        print(f"Comparing {self.name} to {moon.name}")
                    x_mid = (self.x_pos + moon.x_pos)/2
                    if self.x_pos > x_mid:
                          self.x_vel = self.x_vel - 1
                    elif self.x_pos < x_mid:
                          self.x_vel = self.x_vel + 1
                    y_mid = (self.y_pos + moon.y_pos)/2
                    if self.y_pos > y_mid:
                          self.y_vel = self.y_vel - 1
                    elif self.y_pos < y_mid:
                          self.y_vel = self.y_vel + 1
                    z_mid = (self.z_pos + moon.z_pos)/2
                    if self.z_pos > z_mid:
                          self.z_vel = self.z_vel - 1
                    elif self.z_pos < z_mid:
                          self.z_vel = self.z_vel + 1
        def apply_gravity_x(self, moon_list):
            for moon in moon_list:
                if moon is not self:
                    x_mid = (self.x_pos + moon.x_pos)/2
                    if self.x_pos > x_mid:
                          self.x_vel = self.x_vel - 1
                    elif self.x_pos < x_mid:
                          self.x_vel = self.x_vel + 1
        def apply_gravity_y(self, moon_list):
            for moon in moon_list:
                if moon is not self:
                    y_mid = (self.y_pos + moon.y_pos)/2
                    if self.y_pos > y_mid:
                          self.y_vel = self.y_vel - 1
                    elif self.y_pos < y_mid:
                          self.y_vel = self.y_vel + 1
        def apply_gravity_z(self, moon_list):
            for moon in moon_list:
                if moon is not self:
                    z_mid = (self.z_pos + moon.z_pos)/2
                    if self.z_pos > z_mid:
                          self.z_vel = self.z_vel - 1
                    elif self.z_pos < z_mid:
                          self.z_vel = self.z_vel + 1
        def move_it_move_it(self):
            self.x_pos = self.x_pos + self.x_vel
            self.y_pos = self.y_pos + self.y_vel
            self.z_pos = self.z_pos + self.z_vel
    def copy_universe_state(moon_list):
        state = []
        for moon in moon_list:
            state.append(moon.x_pos)
            state.append(moon.y_pos)
            state.append(moon.z_pos)
            state.append(moon.x_vel)
            state.append(moon.y_vel)
            state.append(moon.z_vel)
        return state
    input_string = """<x=-17, y=9, z=-5>
    <x=-1, y=7, z=13>
    <x=-19, y=12, z=5>
    <x=-6, y=-6, z=-4>"""



    #Real
    Io = moon("Io", -17, 9, -5)
    Europa = moon("Europa", -1, 7, 13)
    Ganymede = moon("Ganymede", -19, 12, 5)
    Callisto = moon("Callisto", -6, -6, -4)

    #Example1:
    #Io = moon("Io", -1, 0, 2)
    #Europa = moon("Europa", 2, -10, -7)
    #Ganymede = moon("Ganymede", 4, -8, 8)
    #Callisto = moon("Callisto", 3, 5, -1)

    moon_list = [Io, Europa, Ganymede, Callisto]

    identical = False
    #history = []
    step = 0
    verbose = False
    super_verbose = False
    #vector = "x"

    #history.append(copy_universe_state(moon_list))
    initial_state = copy_universe_state(moon_list)
    while not identical:
        step = step + 1
        #print(step)
        for moon in moon_list:
            if vector == "x":
                moon.apply_gravity_x(moon_list)
            elif vector == "y":
                moon.apply_gravity_y(moon_list)
            elif vector == "z":
                moon.apply_gravity_z(moon_list)
            elif vector == "all":
                moon.apply_gravity(moon_list)
        for moon in moon_list:
            moon.move_it_move_it()
        universe_state = copy_universe_state(moon_list)
        #print(universe_state)
        #history.append(universe_state)
        #for state in history[:-1]:
        if universe_state == initial_state and step > 1:
            print(f"Identical state for {vector} reached after {step} steps" )
            identical = True
            if vector == "x":
                x_steps = step
            elif vector == "y":
                y_steps = step
            elif vector == "z":
                z_steps = step
            elif vector == "all":
                x_steps = step
                y_steps = step
                z_steps = step
def lcm(x, y, z):
    greatest = max([x,y,z])
    lcm = 0
    while True:
        lcm = lcm + greatest
        if lcm % x == 0 and lcm % y == 0 and lcm % z == 0:
            return lcm

print(lcm(x_steps, y_steps, z_steps))

This one requires a bit of knowledge of math and/or efficiency in order to solve in any non-ridiculous time period, so I've included a bunch of additional hints. I'm also happy to answer any questions. I'll try to answer without more spoilers than what you specifically ask for.

Non-Spoilery Tips - Part 1

Watch your off-by-1 errors and +/- signs in your input

Non-Spoilery Tips - Part 2

For Part 2 they are not kidding about it potentially taking a long time. You need to seriously think about how to make it more efficient. If I had run mine using my first-pass method it probably would have taken weeks or longer to complete

Moderately Spoilery Tip - Part 1

Make sure to separate your change in velocity (gravity) and actual movement calculations. You want to do the gravity calculation for each moon BEFORE you actually move any of them

Moderately Spoilery Tip 1 - Part 2

You should only need to compare against your initial state, rather than every state in your history

Moderately Spoilery Tip 2- Part 2

Simulating each axis separately will save you a ton of time, but you'll have to use a bit of math to get from there to the answer you want

Heavily Spoilery Tip - Part 2

Least Common Multiple or prime-factor math of each individual (x, y, z) axis should get you the solution MUCH more easily. I explain what you need to know about in my Part 2 Summary

6 votes

Hvv
December 12, 2019 (edited December 12, 2019)
Link
Part 1 is quite fun and easy, since it's basically just making a simulation with admittedly weird physics rules and letting it buzz around for a little. Part 2 is... not. Part 1 Strategy The...
Part 1 is quite fun and easy, since it's basically just making a simulation with admittedly weird physics rules and letting it buzz around for a little.

Part 2 is... not.
Part 1 Strategy

The hardest part of this question is making sure everything executes in order and that everything executes properly.

Using any preferred data structure to store coordinates and velocities, we just use a bunch of loops and if statements.

Then, running the simulation exactly as described:

For every coordinate, go through every pair of objects, check which one has a higher position, and increment and decrement appropriately (and beware the case when they have the same position)

For each object, add the velocity to the position.

At the end, going through each object, tally its kinetic energy and potential energy and multiply them to get its total energy, and sum over objects to get the total energy of the system.

Make sure that the number of loops is correct, and everything should be OK.
Part 1 Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> ii; typedef pair<int,ii> ti; vi x[3]; vi vx[3]; int main() { int a[3]; int sz = 0; while(scanf("<x=%d, y=%d, z=%d> ",&a[0],&a[1],&a[2]) == 3) { for(int i=0;i<3;i++) { x[i].push_back(a[i]); vx[i].push_back(0); } sz++; } ll ctr = 0; ll tot = 0; int N = 1000; for(int i=0;i<N;i++) { for(int id=0;id<3;id++) { for(int i=0;i<x[id].size();i++) { for(int j=0;j<i;j++) { if(x[id][i] > x[id][j]) { vx[id][i]--; vx[id][j]++; } else if(x[id][i] < x[id][j]) { vx[id][i]++; vx[id][j]--; } } } } ll res = 0; //cout << "TIME " << T << '\n'; for(int i=0;i<sz;i++) { ll pt = 0,kn = 0; //cout << "OBJ\n"; for(int j=0;j<3;j++) { x[j][i] += vx[j][i]; //cout << x[j][i] << " " << vx[j][i] << '\n'; pt += abs(x[j][i]); kn += abs(vx[j][i]); } //cout << "ENG " << pt*kn << '\n'; res += pt*kn; } tot = res; } cout << tot << '\n'; }
Part 2 Strategy

Although we have the obvious strategy of churning out the system states step by step, just simulating the system out until it repeats will not work (my answer was on the order of 10^14), so we need to resort to funkier methods of finding out when the system repeats.

There might be a cool way to be able to predict the system N states in advance, but I'm not smart enough to think of one, so instead we're going to have to actually analyze the problem and pray that things work out.

Observe that the system is time-reversible. Empirically, we can "reverse time" one step by first undoing the velocity movement and then changing the velocity by the opposite of what "gravity" would have done.

This is important because we then know the first position that will be repeated: the starting position.

If any position occurs twice, the position that occurred just before it will also occur twice (since we can reverse time to get to it), and so on all the way back to the starting position.

Observe next that we're actually running 3 simulations, one for each coordinate.

Because of the weird way gravity works, the calculations of the velocity and position of one coordinate of one object only depend on the positions of the other objects in that particular coordinate.

This one is important, since, combined with the first observation, we now have a chance at not having to simulate this system forever to find out when it repeats.

Instead of simulating everything, we simulate each individual coordinate independently to see when they all repeat, hope that this simulation is short, and combine those little answers to get our final big answer.

Focusing on the starting position, if one coordinate goes back to the start in N steps and another goes back to the start in M steps, the two coordinates combined will repeat in LCM(N,M) steps.

For 3 loops, the loop length for the entire system will be the LCM of all three individual lengths.

If the input isn't pathological (which luckily it wasn't for me), these individual loops will be relatively short, and so taking the LCM (and using 64 bit integers) gets us an answer that is far bigger than it should be.
Part 2 Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> ii; typedef pair<int,ii> ti; vi ox[3],ov[3]; vi x[3]; vi vx[3]; ll gcd(ll a, ll b) { if(a == 0) return b; if(b == 0) return a; return gcd(b,a%b); } ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } int main() { int a[3]; int sz = 0; while(scanf("<x=%d, y=%d, z=%d> ",&a[0],&a[1],&a[2]) == 3) { for(int i=0;i<3;i++) { x[i].push_back(a[i]); vx[i].push_back(0); } sz++; } for(int i=0;i<3;i++) { ox[i] = x[i]; ov[i] = vx[i]; } ll ctr = 0; ll tot = 0; int N = 1000; ll rp[3] = {0,0,0}; for(int id=0;id<3;id++) { while(1) { rp[id]++; for(int i=0;i<x[id].size();i++) { for(int j=0;j<i;j++) { if(x[id][i] > x[id][j]) { vx[id][i]--; vx[id][j]++; } else if(x[id][i] < x[id][j]) { vx[id][i]++; vx[id][j]--; } } } bool bs = true; for(int i=0;i<sz;i++) { x[id][i] += vx[id][i]; if(x[id][i] != ox[id][i]) { bs = false; } if(vx[id][i] != ov[id][i]) { bs = false; } } if(bs) { break; } } } for(int i=0;i<3;i++) { cout << "SMALL RESULT: " << rp[i] << '\n'; } cout << "BIG RESULT:\n"; cout << lcm(lcm(rp[0],rp[1]),rp[2]) << '\n'; }
5 votes

Crespyl

December 12, 2019 (edited December 12, 2019)

Link

Ooof. I can handle software design and implementation problems like the Intcode stuff pretty well, but the truly "mathier" problems have always been a bit of a weak point for me. Part 1 was a...

Ooof.

I can handle software design and implementation problems like the Intcode stuff pretty well, but the truly "mathier" problems have always been a bit of a weak point for me. Part 1 was a pretty straightforward simulation, but Part 2 was the first problem that I bounced off of with no idea how to approach and ended up needing to get a couple hints.

Part 2 Spoilers

The key pieces of information for me is that a) the system will return to its exact start (it won't "degenerate" into a loop that doesn't include the start), and b) each axis is totally independent of the other axis (I wasted time writing some vector math helpers that I ended up not needing), and therefore there are three sub-cycles we can inspect. In hindsight, I should've realized this as soon as I noticed that I could write apply_gravity by iterating over the axis indices.

Armed with this knowledge, I went back in and adapted my naive search function to only examine one axis at a time, found the period of each sub-cycle, and was at last able to bring the problem down to something that my limited ability could handle (with some help from Mathematica).

Part 1 & 2

#!/usr/bin/env crystal

struct Vec3
  property x : Int32
  property y : Int32
  property z : Int32

  def initialize
    @x, @y, @z = 0,0,0
  end

  def initialize(x,y,z)
    @x = x
    @y = y
    @z = z
  end

  def to_s
    "(%i,%i,%i)" % [@x,@y,@z]
  end

  def reduce(init, &block)
    state = init
    state = yield state, @x
    state = yield state, @y
    state = yield state, @z
    return state
  end

  def []=(i : Int, val : Int32)
    case i
    when 0 then @x = val
    when 1 then @y = val
    when 2 then @z = val
    else raise "Bad index into Vec3"
    end
  end

  def [](i : Int)
    case i
    when 0 then @x
    when 1 then @y
    when 2 then @z
    else raise "Bad index into Vec3"
    end
  end

  def +(v : Vec3)
    Vec3.new(@x + v.x, @y + v.y, @z + v.z)
  end
  def -(v : Vec3)
    Vec3.new(@x - v.x, @y - v.y, @z - v.z)
  end
  def *(v : Vec3)
    Vec3.new(@x * v.x, @y * v.y, @z * v.z)
  end
end


class Moon
  property pos : Vec3
  property vel : Vec3
  property name : String

  def_hash @name, @pos, @vel

  def initialize(name, pos, vel)
    @name = name
    @pos = pos
    @vel = vel
  end

  def initialize(name : String, pos : Vec3)
    @name = name
    @pos = pos
    @vel = Vec3.new
  end

  def move
    @pos = @pos + @vel
  end

  def energy
    pot = @pos.reduce(0) { |sum, v| sum+(v.abs) }
    kin = @vel.reduce(0) { |sum, v| sum+(v.abs) }
    pot * kin
  end

  def to_s
    "%s: pos %s vel %s" % [@name, @pos.to_s, @vel.to_s]
  end

  def clone
    Moon.new(@name, @pos, @vel)
  end

end

def apply_gravity(a : Moon, b : Moon)
  (0..2).each do |axis|
    if a.pos[axis] < b.pos[axis]
      a.vel[axis] = a.vel[axis] + 1
      b.vel[axis] = b.vel[axis] - 1
    elsif a.pos[axis] > b.pos[axis]
      a.vel[axis] = a.vel[axis] - 1
      b.vel[axis] = b.vel[axis] + 1
    end
  end
end

def step(moons)
  moons.permutations(2).map{ |pair| pair.to_set }.to_set.each do |pair|
    a, b = pair.to_a
    apply_gravity(a, b)
  end
  moons.each { |m| m.move }
end

def find_cycle(moons : Array(Moon), axis : Int32) : Int64
  start = moons.map { |m| {m.pos[axis], m.vel[axis]} }
  n = 1_i64
  step(moons)
  while moons.map{ |m| {m.pos[axis], m.vel[axis]} } != start
    n += 1
    step(moons)
  end
  return n
end

# Part 1

moons = [] of Moon
moons << Moon.new("a", Vec3.new(6,10,10))
moons << Moon.new("b", Vec3.new(-9,3,17))
moons << Moon.new("c", Vec3.new(9,-4,14))
moons << Moon.new("d", Vec3.new(4,14,4))

1000.times do |i|
  step(moons)
  #puts "after #{i+1} steps:"
  #moons.each { |m| puts m.to_s }
end

puts "Part 1:"
moons.each { |m| puts m.to_s }
puts "system_e: %i" % moons.reduce(0) { |sum,m| sum + m.energy }

# Part 2

moons = [] of Moon

#test
# moons << Moon.new("a", Vec3.new(-8,-10,0))
# moons << Moon.new("b", Vec3.new(5,5,10))
# moons << Moon.new("c", Vec3.new(2,-7,3))
# moons << Moon.new("d", Vec3.new(9,-8,-3))

#input
moons << Moon.new("a", Vec3.new(6,10,10))
moons << Moon.new("b", Vec3.new(-9,3,17))
moons << Moon.new("c", Vec3.new(9,-4,14))
moons << Moon.new("d", Vec3.new(4,14,4))

moons.each { |m| puts m.to_s }

cycle_x = find_cycle(moons.clone, 0)
cycle_y = find_cycle(moons.clone, 1)
cycle_z = find_cycle(moons.clone, 2)

puts "%i, %i, %i" % [cycle_x, cycle_y, cycle_z]
puts cycle_x.lcm(cycle_y.lcm(cycle_z))

4 votes

[2]

Gyrfalcon

December 12, 2019

Link

Okay wow part 2 was a lot. I fully admit that I don't think I would have solved it without the tips people shared here. Big thanks to both @PapaNachos and @Hvv on that! I wasn't able to split...

Okay wow part 2 was a lot. I fully admit that I don't think I would have solved it without the tips people shared here. Big thanks to both @PapaNachos and @Hvv on that! I wasn't able to split things up in some of the ways that make it easier because I did the initial implementation with an object and I didn't want to add a bunch of weird methods to it.

Code is for both parts 1 and 2.

Planet.py

class Planet(object):

    def __init__(self, position, velocity=None):

        self.position = position
        if velocity is None:
            self.velocity = [0, 0, 0]
        else:
            self.velocity = velocity

    @property
    def potential_energy(self):
        pot = 0
        for idx in range(3):
            pot += abs(self.position[idx])
        return pot

    @property
    def kinetic_energy(self):
        kin = 0
        for idx in range(3):
            kin += abs(self.velocity[idx])
        return kin

    @property
    def total_energy(self):
        return self.potential_energy * self.kinetic_energy

    def update_velocity(self, planets):

        for planet in planets:

            for idx in range(3):

                if planet.position[idx] > self.position[idx]:
                    self.velocity[idx] += 1
                elif planet.position[idx] < self.position[idx]:
                    self.velocity[idx] -= 1
                else:
                    pass

    def update_position(self):

        for idx in range(3):
            self.position[idx] += self.velocity[idx]

NBody.py

from Planet import Planet
import re
import copy
from functools import reduce


def create_planets(file_name):

    pattern = "<x=(.*), y=(.*), z=(.*)>"
    prog = re.compile(pattern)

    planets = []

    with open(file_name, 'r') as fid:
        raw_input = fid.readlines()

    for line in raw_input:
        result = prog.match(line)
        planet_position = []
        for idx in range(1,4):
            planet_position.append(int(result.group(idx)))

        planets.append(Planet(planet_position))

    return planets

# Least common multiple stuff that I only knew to use because I spoiled it for
# myself :(
def gcd(a, b):

    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

input_file = "PuzzleInput.txt"

planets = create_planets(input_file)

for time_step in range(1000):

    for idx in range(len(planets)):

        other_planets = [planet for planet in planets if planet != planets[idx]]
        planets[idx].update_velocity(other_planets)

    for idx in range(len(planets)):
        planets[idx].update_position()

total_energy = 0

for planet in planets:
    total_energy += planet.total_energy

print(total_energy)

planets = create_planets(input_file)

initial_states = copy.deepcopy(planets)

done = False
matches = [0 for i in range(len(planets[0].position))]
step = 0

while not done:

    for idx in range(len(planets)):

        other_planets = [planet for planet in planets if planet != planets[idx]]
        planets[idx].update_velocity(other_planets)

    for idx in range(len(planets)):
        planets[idx].update_position()

    step += 1

    for idx in range(len(planets[0].position)):

        if matches[idx]:
            continue

        match_found = True

        for jdx in range(len(planets)):

            if (planets[jdx].position[idx] != initial_states[jdx].position[idx]
                or planets[jdx].velocity[idx] != initial_states[jdx].velocity[idx]):
                match_found = False
                break

        if match_found:
            matches[idx] = step

    done = True
    for match in matches:
        if not match:
            done = False
            break

time_to_repeat = reduce(lcm, matches)
print(time_to_repeat)

3 votes

PapaNachos
December 12, 2019
Link Parent
Glad my tips helped! Part 2 Spoilers My method for splitting up the different components was to only apply gravity in one direction at a time which meant the other dimensions stayed static. A...

Glad my tips helped!

Part 2 Spoilers

My method for splitting up the different components was to only apply gravity in one direction at a time which meant the other dimensions stayed static. A minor update to your update_velocity method would let you do something similar, maybe by taking an argument for which direction(s) should be active. But your way of checking for only a match in that variables position and velocity is a clever way of achieving the same goal. I think it's actually faster since it looks like you only need to go through the simulation once

2 votes

[2]
cfabbro
December 12, 2019
Link
@Deimos, I edited the title, but the direct link still needs to be edited into the topic text: https://adventofcode.com/2019/day/12

@Deimos, I edited the title, but the direct link still needs to be edited into the topic text:
https://adventofcode.com/2019/day/12

1 vote
1. Deimos
  December 12, 2019
  Link Parent
  Done, thanks.
  
  Done, thanks.
  
  1 vote