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>
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.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 writeThis 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 inputNon-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 completeModerately 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 themModerately Spoilery Tip 1 - Part 2
You should only need to compare against your initial state, rather than every state in your historyModerately 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 wantHeavily 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 SummaryPart 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:
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
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
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 writeapply_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
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
NBody.py
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
@Deimos, I edited the title, but the direct link still needs to be edited into the topic text:
https://adventofcode.com/2019/day/12
Done, thanks.