9 votes

Day 12: The N-Body Problem

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

  1. PapaNachos
    (edited )
    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
  2. Hvv
    (edited )
    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:

    1. 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)
    2. 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
  3. Crespyl
    (edited )
    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
  4. [2]
    Gyrfalcon
    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
    1. PapaNachos
      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
  5. [2]
    cfabbro
    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