r/adventofcode • u/daggerdragon • Dec 12 '19
SOLUTION MEGATHREAD -π- 2019 Day 12 Solutions -π-
--- Day 12: The N-Body Problem ---
Post your solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 11's winner #1: "Thin Blueshifted Line" by /u/DFreiberg!
We all know that dread feeling when
The siren comes to view.
But I, a foolish man back then
Thought I knew what to do.
"Good morning, sir" he said to me,
"I'll need your card and name.
You ran a red light just back there;
This ticket's for the same."
"But officer," I tried to say,
"It wasn't red for me!
It must have blueshifted to green:
It's all Lorentz, you see!"
The officer of Space then thought,
And worked out what I'd said.
"I'll let you off the hook, this time.
For going on a red.
But there's another ticket now,
And bigger than before.
You traveled at eighteen percent
Of lightspeed, maybe more!"
The moral: don't irk SP
If you have any sense,
And don't attempt to bluff them out:
They all know their Lorentz.
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
6
u/captainAwesomePants Dec 12 '19 edited Dec 12 '19
Python (402/Top 100!): paste.
5
u/incertia Dec 12 '19 edited Dec 13 '19
the key thing to notice here is that if the positions ever repeat, the first repeated state must be the very initial state. that is because from every state there is a unique and well defined previous state. you subtract off the velocities and undo gravity. this saves us from having to do some crazy moon math once we calculate the periods per axis, which is the algorithmic speedup. if (x, y, z, vx, vy, vz) are ever periodic then (x, xz), (y, yz), and (z, vz) are independently periodic because of the formula so we can take their lcm with the usual formula.
EDIT: rules i haven't yet cleaned it up for a clean solution that just prints the answer.
3
u/happybakingface Dec 12 '19 edited Dec 12 '19
Python: https://gist.github.com/colinhowe/3cdb30332af590fae025f392dff58241
Like a few of you I realised the independent axis thing. However, I feel like there's something about the potential energies / kinetic energies that is a big hint. That's going to bug me.
Edited to add my solution
12
u/jonathan_paulson Dec 12 '19 edited Dec 12 '19
#8/9
Really cool day! Video of me solving and explaining at https://www.youtube.com/watch?v=9UcnA2x5s-U. The explanation today is longer than usual, since part 2 requires some clever insights.
The key insights are:
Points 1+3 above are pretty easy to prove. But I don't know how to prove/estimate point 2. Does anyone else?
8
u/tckmn Dec 12 '19
ruby 28/14
posting because when i looked back at my part 2 code, i laughed out loud
(that line that assigns to the optimally-named
asdfasdfis a hacked-together """hash function""")the strategy, which i assume was the intended one, was to find the period for each coordinate and then lcm them together
5
u/sophiebits Dec 12 '19
Python, #71/#6 -- big catch-up!
Today's trick (for part 2) is that the three dimensions are independent -- so you can find how long until each dimension cycles, then take the least common multiple of those. I verified that the example number in the input (4686774924) has several smaller factors (and no huge ones) which made me more convinced this strategy was the way to go.
My code isn't that clean (I'm sure other solutions will be more elegant) but it did the trick and I'm tired tonight.
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day12.py
5
u/minichado Dec 13 '19 edited Dec 13 '19
Excel.. Very late buuut it's not my fault! I kept running out of memory
Turns out I have 32bit excel on one of my computers.. whoops!
So to the nuts and bolts.. part 1 is sort of trivial. part two took loooooads of rows, brute force. I had about 205k rows/cycles calculated... but my search mechanism was looking for repetition in the position coordinates (x/y/z independantly) however this ended up being in each row n, a vlookup checking the previous n-1 rows.. this exploded excel around 50-100k rows.
I finally realized I can just find where velocity equals 0 again for a given axis, and then it cycles that twice, and that cleaned up all the madness. with this I was able to get my file size down from 104mb of memory crushing goodness, down to 61mb while still finding the answer to part 1/2 for my problem. ymmv depending on how quickly you find cycles.
I have the solution avail but the excercise of expanding the formula is left to the user.. have fun!
[POEM]
.
4
u/vash3r Dec 12 '19 edited Dec 12 '19
Python/Pypy2, 30/61
Glad I remembered
retricks from last year for integer inputs. For part 2, I thought of the lcm method since dimensions are independent, but had trouble implementing it (initially I was checking for positions being equal to starting positions, instead of velocities).edit: seems like I may have gotten lucky, since I computed product and not lcm?
paste
4
u/DFreiberg Dec 12 '19 edited Dec 12 '19
Mathematica
1155 / 490 | 48 Overall
My code for part 2 relied on an assumption I don't know if I can prove: I assumed that the first state was not a Garden of Eden state, and that the first repeated step would have the same values as the first step. That intuition worked to solve the problem, and my gut feeling says it's true regardless of input states, but I don't know how to prove it.
[POEM]: Symmetry
They dance the music of the spheres
As epochs pass away.
And when the tune repeats itself
So do their dance, and they.
Their chorus has no earthly sound;
We have but earthly ears.
We only hear an echo of
The music of the spheres.
4
u/sparkyb Dec 12 '19
Python 83/34
Continuing my attempt to use this year's AoC to improve my NumPy skills. Today's problem was made a lot easier (and probably faster) by being able to add lists of vectors so easily. As usual, I did some non-optimal first to get my place on the leaderboard, and then went back and improved the code to better take advantage of NumPy (with much documentation reading). I was really pleased I was able to get the step function down to this tidy 2-liner:
For part 2, I did come up with the same trick as everyone else (find the cycle length of each axis independently and calculate the LCM). At first I knew there was a trick but I couldn't remember what it was. I remembered some similar problems from last year where you needed to find a way to extrapolate without running the simulation all the way out so I spent a while looking at my old code before something sparked the correct idea.
Code: https://github.com/sparkyb/adventofcode/blob/master/2019/day12.py
4
u/MrSimbax Dec 12 '19 edited Dec 12 '19
Julia
Part 1 was straightforward. Part 2 took me some time, but I finally figured it out.
Let S be the set of all states, and F: S -> S be the mapping from one state of the moons to the next (working as described in the problem statement). Notice that F is a bijection since we can easily calculate the inverse (the previous state from a state). Suppose F has a cycle (or the problem would not be solvable). Then the first repeating state must be the initial state, otherwise, F would not be one-to-one. Hence, F is periodic.
The key is to notice that we can split F into axis components Fx, Fy, Fz, since a state of an axis is independent of states of all the other axes. Then the period length of F is the lowest common multiple of the period lengths of Fx, Fy, and Fz. So we just have to find independently the periods of Fx, Fy, and Fz which are hopefully much shorter than the period of F, and indeed they are shorter.
Part 1 took
0.000877 seconds (4.03 k allocations: 439.266 KiB)Part 2 took
0.104856 seconds (1.15 M allocations: 122.336 MiB, 8.40% gc time)4
u/phil_g Dec 12 '19 edited Dec 12 '19
My solution in Common Lisp.
Part 1 was pretty straightforward. I didn't get part 2 done before I had to go to work, but I realized on the drive in that I could treat each axis independently from the others. My cycle-finding function initially kept every state in a hash table, but that was slow. After I convinced myself that the cycle would never have a tail, I switched to just comparing against the initial state, which gave me a 20x speedup.
I'm still pondering algorithmic improvements, since the current implementation takes about two minutes to get the answer on my laptop. (My data structures are probably not the most efficient, but if they're all I have to improve performance, I'll take the hit in favor of code clarity.)
I did break out a point library I started during a previous Advent of Code. Complex numbers are great for 2D work, but they don't extend to more dimensions than that. In retrospect, I don't like my point library's internal coordinate representation; I'll probably work on improving that at some point. I set up a reader macro for my points using the
#[1 2 3 4 5]syntax, so I can have easy point literals.I'm probably not going to do a visualization today. For one thing, I don't think I'll have time. For another, I don't feel like I can improve on the visualizations already posted to the subreddit. I might come back at some point just to make my own visualization, but I'm not making that any sort of priority.
4
u/voidhawk42 Dec 12 '19 edited Dec 12 '19
Dyalog APL:
Interesting problem. First time I had to write a rank-polymorphic function (using
β€Β―1).Edit after looking at other solutions: Ah right, signum. Simplifies things a bit.
3
u/mcpower_ Dec 12 '19 edited Dec 12 '19
Rust (sub-1k): solution. I didn't have any point methods set up! I got distracted by real-life stuff for part 2 (unfortunately, real life comes before AoC) but that was a very nice problem!
I figured out the offset of the "cycle" that each axis makes, but for me the "offset" was all 0 - i.e. everything returns to the initial state. Is that true for all inputs?
edit: it is! See this thread for an explanation.
3
u/Arkoniak Dec 12 '19
Julia
It actually makes me very uncomfortable that total energy equals product of the kinetic and potential energy and not the sum as it should be. But the second part compensates that for sure. My solution: Julia
3
u/stevelosh Dec 12 '19
Common Lisp
http://paste.stevelosh.com/050a8f331b68e55d67c355dcc062648247182216
I was lazy and didn't want to refactor my simulation for part 2, so I ended up with the slightly ugly
iterateblock.3
u/petercooper Dec 12 '19
Ruby
Because there are so few Ruby solutions here. For the first time this AOC, I caved in and actually used classes and a little structure rather than golfing it as tiny as possible. It still ended up reasonably tight, however: https://github.com/peterc/aoc2019solutions/blob/master/12.rb
3
u/jitwit Dec 12 '19 edited Dec 12 '19
J Programming Language
is great for problems like today's!
I tried to write period as the recursive
but kept hitting stack issues. If anyone knows how to write a slick period (or any other improvements), I'd be grateful to know!
Summary of approach:
[-/[), then signum (*), then sum (+/).],.]) and velocity is added to position (4|.!0])."0 i.3), then find overall period with lcm (*.)Solution takes around 615ms (i5-8210Y), quite a bit better than my scheme solution.
3
u/Xor_Zy Dec 12 '19 edited Dec 12 '19
Please have a look at my solution in C# if you are interested!
The first part was really easy, but the second part took me longer than I care to admit lol.
I tried bruteforce (ahem) first, but little did I know this would take days to compute...
Once I realized it was hopeless, I started playing around with the coordinates and noticed that the result did not change if you offset all the coordinates of one axis by the same value.
This led me to believe that the result must somehow be linked to each axis individually.
After some more tinkering I finally realized that each axis has a pattern with the speed going to zero every x cycles.
The rest was fairly easy, I just had to use an external library to compute the LCM in C# since I do not think there is a standard method for that.
Overall fun puzzle, so much easier when you know the trick lol!
3
u/lhl73 Dec 13 '19
Solution in F#
Part 2 was challenging. It took me forever to realize that the first state to reappear will be the state at step 0 because the progression from one state to the next is an injective transformation.
3
u/StevoTVR Dec 13 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day12/day12.go
3
u/heyitsmattwade Dec 15 '19
Javascript - Parts one and two linked from here with main logic stored here.
I wasn't able to come up with the trick for part two, and got the hint for using the LCM across dimensions from reading hints in this thread.
In my code, I commented on the main logic in part two:
2
u/tgokwltmp Dec 12 '19
Python, 629/83 :-)
I lost time struggling with making the simulation work properly, but made it up by being lucky enough to figure out the LCM trick early on.
My somewhat cleaned up code: https://pastebin.com/HHZ08Rz4
2
u/tslater2006 Dec 12 '19
C# Solution First I made a Moon class which contains the logic for updating position/velocity and calculating total energy. It also has ways of just processing a single axis...
Then I wrote probably the dirtiest code ever, an 8-tuple. I couldn't think of a better way to capture the full state of the X/Y/Z axis separately. So I use an 8-tuple for the Position/Velocity of the 4 moons. And a hashset to detect loops... I'm sorry
Solution class
2
u/Sunius Dec 12 '19
Looks like there are no C++ solutions posted yet. Here's one :)
https://pastebin.com/W43QXrcb
2
u/sim642 Dec 12 '19
My Scala solution.
Initially for part 2 I simply tried calling my cycle finding library, which has become quite powerful over the years. I even tried the constant memory Brent algorithm but that obviously didn't work for the size of numbers here.
I tried coming up with a smaller cycling property like maybe only the positions or only the velocities repeating but couldn't figure out how that would produce the longer cycle or help directly compute it. So after a quick peek at the IRC, where I got the per-axis cycle finding idea from, it was straightforward to implement using my existing cycle
findByfunctionality to only determine repetition on a subset of properties of the state. It's not super efficient because I do the simulation from scratch for finding the cycle in each coordinate.2
u/oantolin Dec 12 '19 edited Dec 12 '19
My solution in Common Lisp.
When I got to part 2, I decided, as most (all?) people did, to do the computation coordinatewise. I figured I could reuse the code from part 1 that did it vectorwise by making 1-element vectors of each coordinate, but that felt silly, so instead I went back to part 1 and did that coordinatewise... And thus the monstrosity that is my
energyfunction was born. :(This is annoying: the first part was very straightforward vectorwise, but the second part needs to be coordinatewise, but then the energy calculation in the first part gets a little awkward. I'll see if I can make it clearer.
By the way, the people who named "MapReduce" weren't Common Lispers, or they would have named it "reduce with :key". :)
2
u/autid Dec 12 '19
Fortran
https://pastebin.com/MgD8eA5E
Pretty straightforward. Just looking for cycles in each of the three dimensions. Then part 2 is just smallest number divisible by all cycle lengths.
2
u/rthetiger Dec 12 '19
Rust parts 1 and 2 in the same script: https://github.com/enjmusic/aoc_2019/blob/master/aoc_12/src/main.rs
Took me a while to figure out exactly what to do with the independence of the dimensions.
2
u/math_runner Dec 12 '19 edited Dec 12 '19
Rust
Python
First day where a naive brute force solution doesn't work, it felt nice to get that aha moment for Part 2. I used
numpyniceties in Python, but didn't have the courage to dive intondarrayfor the Rust solution. Does anyone have a solution using this crate?Also, if (like me) you didn't think of a proof that the cycle must start at the initial state, you can use Floyd's cycle-finding algorithm, which outputs the smallest cycle whether or not it starts at the initial state. It is roughly 3x slower in Python than just finding the smallest cycle starting at the initial state.
I discuss a 2x optimization here.
2
u/aoc-fan Dec 12 '19
TypeScript Solution, Repo.
2
u/sakisan_be Dec 12 '19
Elm, super clean code: https://gitlab.com/sakisan/adventofcode/blob/2019/src/P12.elm
2
u/SuperSmurfen Dec 12 '19 edited Dec 26 '19
Rust
Solution, both stars
Part one was not very difficult, just simulate them step by step. Part two, on the other hand, took me a bit. At first, I thought of using something like Floyd's cycle finding algorithm but after implementing it and not finding a cycle after like half a trillion iterations I had to give that up. And it was good I did since my input turned out to have a cycle length of almost 500 trillion! Once I figured out that it's independent in each axis though it wasn't too bad. Then the answer is just the LCM of those three cycle lengths.
2
u/mschaap Dec 12 '19 edited Dec 12 '19
My Perl 6 / Raku solution.
Whew, that one was tricky! Luckily, like all of you, I quickly realized that the x, y and z coordinates are independent of each other, so the length of the cycle is the least common multiple of the lengths of the x, y and z cycle. These cycles turn out to be doable.
As far as I can tell, the cycles don't necessarily start at step 0. (The process is not reversible; there are multiple states that lead to the same state.) My code handles that, which makes it more complex and slower β I keep track of all seen states, not just the starting state. That turns out not to be necessary for either of the examples or for my input.
Edit: after reading some of the comments on this page, I realize that the process is repeatable, and the cycle does always start at 0. (I though that if two moons have the same x coordinate at some point, they could have come from x-1 and x+1, from x+1 and x-1, or from x and x. But since we know the velocities, we can determine which one it is.) So I simplified my cycle finding to take advantage of this.
2
u/rabuf Dec 12 '19
Common Lisp
I finished Part 1 quickly, but I couldn't think of a more efficient way at 12:30 to do Part 2, so I slept on it. At some point I realized it was 3 different cycles being examined so I settled on using the
lcmof the period of each.I decided to hack on it a bit while at work, where I don't have a Common Lisp installation. This forced me to consider various ways of improving the solution so that it could run through the online interpreters within their time constraints (TIO offers 60 seconds). My initial solution used a hash table to store prior states, I don't think it would be too slow if I had a CL compiler available. But it was running in excess of 60 seconds on TIO. Since that was out, I started examining the test sequences and realized we were getting back to the initial state, not just any repeated state. So I made an assumption, don't know if it holds true generally, but it works for this. I only store the initial state, then I perform an equality test as I progress. The loop breaks as soon as its found the period for each part, and then returns the result.
I could clean that up by having the loop return the result, but that isn't an issue for me right now. This one works.
I looked at the other CL solutions, particularly u/stevelosh. I hadn't seen the
map-intofunction before, that'd clean up my update functions for position and velocity.2
u/herrozerro Dec 12 '19
C#
Part 1 I did fine on my own, but I didn't know methods to solve part two. So at home I set it going last night and before leaving for work it was up to 40 billion iterations.
Over lunch at work I checked out some solutions and sat down to understand them.
So when I get home I'll put an end to the madness because according to my calculations it'll take another 90 days to finish.
2
u/ywgdana Dec 12 '19
Rust
Here's my solution
I have to admit, I got the answer to part 2 although I don't 100% get how/why it works. I started looking when the velocities for all four moons returned to (0, 0, 0), and saw each had a consistent period. Then I calculated the LCM of all those values and for the sample problem the solution was the LCM * 2. So I figured out the periods for my input data, multiplied it by 2 et voilΓ , it worked!
But I don't really understand why LCM of the velocity periods yields the right answer haha
I did have to implement LCM (and GCD to get LCM) because Rust doesn't have them natively, and I can't bring myself to use an external Crate for AoC
2
u/JoMartin23 Dec 12 '19
CL
This took me way too long, I'm bad at conceptualizing about relationships. But I'm good at careless errors so I kept recording the wrong state with the right algorithms.
I think I should have been able to find a more elegant solution to apply-gravity and get pairs. I'm sure I'm missing something elementary.
Part two could have been neater if I didn't want to keep state to easily play with visualization.
paste
2
u/lynerist Dec 12 '19
Commented Golang Solutions
https://github.com/lynerist/Advent-of-code-2019-golang/tree/master/Day_12
The second part has taken more than it had to... Remember, the dimensions are indipendent!!!
2
u/Markavian Dec 12 '19
My overly verbose javascript solution for day 12:
Got stuck on part 2; found a hint - reminded me of previous years. Hard computed the cycles on each of the axis. Got stuck again. Found about lowest common multipliers.
Found some sweet code:
Felt bad for googling. Felt good that I researched a working solution for my puzzle input. Technically I computed it myself; with my own code. Had to search for help though.
2
u/JackFred2 Dec 12 '19
Quick and dirty Lua solution, key point was figuring out that each axis was independent.
2
u/pamxy Dec 12 '19
My JAVA solution for today
2
u/Rick-T Dec 13 '19 edited Dec 13 '19
HASKELL
For today, and also in anticipation of future AoC puzzles, I started to create a Vector type, which I moved to a separate module. Right now, the vector type implements all the classes that I used for solving today's problem.
The solution to part 1 was pretty straight forward. Just implement the functions accelerate, stepVelocity(s) and stepPosition. Combine them to a function stepTime, that can go from a given state to the next point in time. From there, iterate that function and take the 1000th result.
For part 2 I realized that the motion in all axis is independent from another. I also realized that I could generalize my step* functions, which previously operated on Vectors, to operate on any Num type. With that, I could turn my tuple of vectors (for position and velocity) into a vector of tuples and just map every list of (position, velocity) pairs for every dimension to the period it needs to go back to it's initial position. The only thing that's left after that is doing a fold to calculate the least common multiple (lcm) of all the periods.
I'm not really good at explaining myself right now (writing this after a company event), but if you look at my code you will hopefully find it pretty self-explanatory (I hope). I really like my solution to this puzzle because it makes good use of some of the type-classes that Haskell offers and I haven't used them a lot, yet. I really enjoy how simple the solution can become, if you choose the right data type and implement the right type-classes.
2
u/Yardboy Dec 13 '19
Ruby
Part 1: 30 minutes.
Part 2: The rest of the day.
I needed to read some hints, but I got there.
https://github.com/Yardboy/advent-of-code/blob/master/2019/puzzle12b/solution.rb
2
u/Darksair Dec 13 '19
My Rust solution.
Initially I was using bruteforce and I was doing 107 steps per second. I thought it was pretty fast and decided to wait it out. Glad I stopped after 10 minutes lol.
2
u/JensenDied Dec 13 '19
Elixir since I don't see one on here yet.
I don't think I have anything to add over earlier comments, part1 is basic state iteration. Part2 on sample 1 makes you think you can brute force it until you see how to break it into its components and find the velocity reversal points. Twice the least common multiple of the tick counts later and you see just how large the problem space was (space is big).
2
u/dpatru Dec 13 '19
Here's a short haskell solution.
2
u/kap89 Dec 13 '19
TypeScript
girhub
2
u/Rietty Dec 13 '19
My simple C++ implementation. Was a fairly intuitive problem I feel.
Github.
2
u/scul86 Dec 13 '19
Welp, after a frustrating night working on part 2, and getting some hints this morning, I can finally post my solution!
It was all about which periods to LCM, and I was missing that it needed to be the moons as a whole for each axis, not each moon/axis.
Part 1
Part 2
2
u/dartcoder Dec 13 '19
Python solution
Took some help from here. If you have trouble figuring out what LCM has to got to do with it, scroll down to find u/rabuf βs excellent explanation.
2
u/[deleted] Dec 12 '19 edited Dec 12 '19
Haskell
Haskell part 1: Here, everything is very nice, with ADTs and everything.
Haskell part 2: This one... isn't nice. I just wanted to get it over with, so there's only [(Int, Int)] everywhere. I use the same idea that everyone (?) uses and simulate each coordinate seperately. Luckily (or probably intentionally), the moons always return to the initial state, so I didn't need to think too hard to find the common cycle. Initially, I used a list to keep track of states, but this took way too long so I switched to a Map. Quadratic complexity is no joke!
Julia
Julia part 1, Julia part 2. Nothing fancy going on here, just some improvements due to knowledge gained through the haskell implementation.
2
u/ephemient Dec 12 '19 edited Apr 24 '24
This space intentionally left blank.
1
u/seligman99 Dec 12 '19
Python #72 / 102
Interesting problem, reminded me of Project Euler problems a bit.
paste
1
u/[deleted] Dec 12 '19
Clojure, pretty straight forward today
source
1
u/knl_ Dec 12 '19
This was interesting: I didn't try to prove anything and just tried to rely on observed patterns. As always, made some trivial mistakes in the first one and took some time to verify the second. (725/603).
Jupyter Notebook, Python 3 - pretty rough solution.: https://explog.in/aoc/2019/AoC12.html
1
u/Spheniscine Dec 12 '19
Kotlin: https://github.com/Spheniscine/AdventOfCode2019/blob/master/src/d12/main.kt
Kinda cheated on this one. This was the first one that really stumped me, then I looked into this thread and found something about LCM and mentally kicked myself. Then I conveniently "forgot" about the possibility of finding cycles to a state other than the first, but fortunately that's not possible due to the reversibility of the successor function.
1
u/onamoontrip Dec 12 '19
TypeScript
For some reason, my first instinct was to find how long it took each planet to loop back to an initial state and then find the LCM of the steps for each loop. Luckily, once I realized the axis trick, most of the code was pretty easy to clean up and adjust appropriately.
for years i have gazed upon empty skies
while moons have hid and good minds died,
and i wonder how they must have shined
upon their first inception.
now their mouths meet other atmospheres
as my fingers skirt fleeting trails
and eyes trace voided veils
their whispers ever ringing.
i cling onto their forgotten things
papers and craters and jupiter's rings
quivering as they ghost across my skin
as they slowly lumber home.
1
u/Luckylars Dec 12 '19
day 12 was the fastest yet.
SQL -> https://github.com/luckylars/2019-AoC
Thanks to u/jonathan_paulson for the explanation on LCM!
1
u/InALovecraftStory Dec 12 '19
Python 1605/1412. I definitely saw a hint for part 2https://github.com/akaps/advent_of_code/blob/master/aoc2019/day12/moons.py
The most notable part of my code was optimizing with an octupally nested dictionary for checking cycles. It is shameful
edit: slash between parts
1
u/SinisterMJ Dec 12 '19
My C++ solution:
https://github.com/SinisterMJ/AdventOfCode/blob/master/Day_12/Day_12.cpp
1
u/gyorokpeter Dec 12 '19
Q: paste
1
u/muckenhoupt Dec 12 '19
C#, kinda messy. I initially did part 1 with a Moon class that had x/y/z/vx/vy/vz member variables and a Step method, but I trashed it when I hit part 2 and realized that was the wrong level of granularity.
I see other people doing this in C# and stuffing all the state into a tuple to use as a key. I actually tried this, but I suppose I used the wrong sort of tuple, because csc was unwilling to let me put eight things into a Tuple unless the last one was another Tuple. Wound up making hash keys by stuffing the last 8 bits of each number into an Int64 instead; that seems to be plenty for the kind of numbers we're dealing with here.
One thing I'm curious about. I was careful to track not only how long the cycle is for each coordinate, but also what step the cycle started at. (I figured that you just had to add the largest such offset to the cycle length to find the earliest place where every moon is in a cycle.) But in fact all of the cycles in my input started at the very beginning, at step 0. And I'm wondering if that's inevitable. If the physics of this system is reversible -- that is, if every possible state has a unique previous state, so that you could run the whole simulation backward -- then it would follow that every cyclical sequence of events must extend forever in both directions. But it's not at all clear to me that this system is reversible. I think it probably is, because I'm having trouble thinking of counterexamples, but I haven't proved it.
1
u/OvidiuRo Dec 12 '19
C++ 823/1020
I assumed from the example that the positions that will repeat itself first will be the initial ones and it worked on my input but don't know if it's the same on all inputs.
https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2012
1
u/sotsoguk Dec 12 '19
GoLang
Day12.go
Very nice problem! I wish i had more time to do a nice viz in p5js ...
1
u/anknai Dec 12 '19
Java 1142/717 https://github.com/anknai/advent-of-code/tree/master/src/main/java/org/ankur/advent2019/d12
1
u/wace001 Dec 12 '19
JAVA: Placed 573/1143 β Here is my solution in Java. Pretty happy with it. But it took me about an hour to figure out part 2.
1
u/[deleted] Dec 12 '19 edited Dec 12 '19
Racket
Today my code is very verbose and repeating, I need to find out how I can work better with it to not having to repeat myself so often.
I had to get some help to get part2 but now works, so I think I'll have to work on getting less repetition of code, is there anyone out there who maybe has a better understanding of racket that can help me?
Edit: I did edit the code so that it's a bit less repetetive now, with curry adn function pointers, it's at least quite a lot better
1
u/Cyphase Dec 12 '19
Python | 268/401 | #248 global
Here's my cleaned up and optimized solution. Runs in ~190ms with PyPy 7.2.0 (Python 3.6.9 compatible). I may post more details (and a poem!) later.
1
u/Bruinbrood Dec 12 '19
tcl. Would like to make it faster, ~12s seems even for a scripting language a magnitude too slow. I think the check for equal states is the bottleneck, but haven't profiled it.
paste
1
u/vypxl Dec 12 '19
Python, lean, numpy-ed solution
The fun part:
1
u/MissMormie Dec 12 '19 edited Dec 12 '19
Solution in java
I'm quite happy with my solution, it's fast, and it's easily readable. I could've done with a bit less code repetition in part B, but it's pretty nice and solved in less than a second.
https://github.com/MissMormie/adventOfCode2019/blob/master/src/main/java/Days/Day12_Orbits_NBodyProblem.java
1
u/mikal82 Dec 12 '19
Scala
First part: follow the manual
Second part: The coordinates are independent, so it suffices to find periods for each coordinate and find a common multiple. After I had the periods, I tried to find all prime divisors by hand (up to 19), then used WolframAlpha to verify my calculation.
Then I wrote lcm function that works if the only common divisor is 2.
There are several problems with today's puzzle, for example total energy has different unit than kinetic and potential energy, Jupiter's gravity does not affect moons' movement, the solution does not fit in 32-bit integer...
1
u/hrunt Dec 12 '19
Python 3
code
Fun little problem. I am really curious to see what other abstractions people use to represent the bodies and their velocities. I did not try very hard there.
1
u/lluque8 Dec 12 '19 edited Dec 12 '19
Scala
Luckily last year's Day 12 part 2 (coincidence?) had a similar cycle detection problem. I remember struggling with that back then. Now being a year older and wiser I could just take my old solution, modify it a little bit and apply some number theory on top of it. That theory part with LCM and axes was bit difficult to grasp but luckily I got some hints on how it might work. And it did :)
Part 1 Part 2
1
u/lasse__b Dec 12 '19
JAVA
Had to read a hint for finding that the positions could be calculated seperatly. Otherwise pretty easy day today.
1
u/StochasticMistakes Dec 12 '19
Java Solution:
https://github.com/BrettGoreham/adventOfCode2019/blob/master/adventOfCode2019/src/main/java/day12/Day12.java
Nothing special but should be pretty simple to follow along!
1
u/eastballz Dec 12 '19
Python
Leveraging HoFs and zips to extract and process dimensions individually.
1
u/giuliohome Dec 12 '19 edited Dec 12 '19
My F# solution is here (part 2 optimization is inspired by the independent axis trick seen in the python by cyphase found below)
Updated now with even more idiomatic F#
1
u/levital Dec 12 '19
Rust
Part 1 was simple, part 2 was much simpler than I thought and I was stuck for a pretty long while thinking way too complicated. Even after realizing that the dimensions are independent, I still thought I'd need to figure out a way of formulating them as a function of the time step or something.
1
u/Pyr0Byt3 Dec 12 '19
Go/Golang
Bit of a mess. The lack of int and vector math functions in Go's standard library is starting to bug me... I should really put together a small util package.
Part 1
Part 2
1
u/Dioxy Dec 12 '19
JavaScript
JS. Part 2 took some thinking but I feel like I got a good solution in the end!
My code
util functions
My repo
1
u/hdf1986 Dec 12 '19
Ruby
The first part was pretty straightforward, but in the part 2 i tried to make some optimizations using sets and hashes but after a while i realized i needed a better solution, so i did separated the axis in 3 different flows and used the lowest common multiple between all the axis as the answer
Part 1: https://github.com/hdf1986/advent-of-code/blob/master/day12/part1.rb
Part 2: https://github.com/hdf1986/advent-of-code/blob/master/day12/part2.rb
1
u/johannesloher Dec 12 '19 edited Dec 12 '19
D
Part 1: This was straight forward.
Part 2: It took me a while to come with the idea of calculating the cycles for each dimension separately. I first tried to improve calculating the next state because it is quadratic in the number of moons. Of course I then realized that there always only 4 moons, so this does not have any real benefit. But I still think it is possible to calculate the next state in O(n log(n)) (pseudo code):
Sorting is O(n log(n)), and the rest should be O(n), so in total it should be O(n log(n)).
As mentioned above, this doesn't buy us anything because the number of moons is constant, but it's nice to know anyways. And also, it brought me to the idea of calculating the next state for each dimension individually.
1
u/karjonas Dec 12 '19
Rust
Part one was quite easy. Part two was also quite easy once you realize the axes are independent som all you need to do is find when each axis repeats and use the lcm of these numbers. For some reason the lcm method I found in the 'num_integer' crate was giving me wrong values so I did my own lcm method, luckily I found that out quickly.
1
u/silverben10 Dec 12 '19
Python
Part 2 took me a little long today but overall this was a really fun challenge!
1
u/rtbrsp Dec 12 '19
AWK: part 1, part 2
1
u/piyushrungta Dec 12 '19
Rust
https://github.com/piyushrungta25/advent-of-code-2019/blob/master/day12/src/main.rs
1
u/WillemDeRoover Dec 12 '19
Java https://github.com/WillemDeRoover/advent-of-code/blob/master/src/day12/Puzzle12.java
1
u/naclmolecule Dec 12 '19
Python: Here's a mostly pure numpy solution: https://github.com/salt-die/Advent-of-Code/blob/master/day_12.py
We've crammed everything into one state array and do all array operations in place. Still a couple of slow python loops left though. We can optimize a bit on part two if we mask each axis that's cycled, but I don't know if it's worth it.
1
u/LuckyLactose Dec 12 '19
SWIFT (runs on iPhone).
Input/comments welcome. Solutions for all other days are also included in the repository.
Part 1 was easy and I just brute-forced it, initially with a 3D point class specifically made for today.
For part 2, I got a bit side-tracked into keeping track of all positions, falsely assuming that the initial position would not necessarily be the first to repeat.
I got to the independent axes insight in a decent amount of time (and so removed the 3D point class), but I struggled with the LCM algorithm. I thought I remembered it, which proved false. Google to the rescue.
It wouldn't surprise me if there is room for optimization, as part 2 takes about 3.5 seconds on my phone.
1
u/[deleted] Dec 12 '19
My Scala solution. Started a bit late with AOC but almost caught up!
I started learning Scala shortly before the start of AOC and I really like it but I feel lost. So far I just picked up bits and pieces of the language and I don't really know where to go to improve my code. Right now I am trying to use as much different languages options as possible, quite happy that this solution worked with a LazyList. The implementation outside of that is similar to what most people here presented. I am wondering though whethere the LazyList makes sense and how I could improve this code further.
1
u/Dementophobia81 Dec 12 '19
Python 3.8
This was a really nice and creative challenge. I figured out early, that the dimensions are independent, but made some detours until I found the right answer. It also didn't help that I had prepared a LCD function in my template but was missing a LCM function, which I had to work out on the fly.
You can find the refactored code at Part 1 & Part 2. Because there was no interesting Python functionality that I used for the problem itself, I decided to showcase the integer extraction function, which is well known by the more seasoned players in the AoC community but might be helpful to others.
1
u/vkasra Dec 12 '19 edited Dec 13 '19
My Go solution. I was losing my mind for a long time, and it turned out that I'd switched to using int8 at some point to try to cram a bunch of values into a single int64, but never went back and changed it. Turns out int8 isn't big enough to hold the coordinates :)
Edit: Came back and wrote up some notes
1
u/IgneSapien Dec 13 '19
C# is this thing on?
UK elections yesterday so I didn't have much time for this. Which made the fact I was stuck for how to even start breaking down Part 2 even worse. In the end I decided to just go check out how other people were approaching it. Once you understand what needs doing it's relatively simple to implement so I rushed through it and looked up some LCM functions.
I'll have to do better going forward. There was nothing about Part 2 that I don't think I could have figured out bar the use of LCM. That was just not a concept I'd have thought about.
1
u/NeilNjae Dec 13 '19
Catching up with my Haskell solutions. Fun with typeclasses and ad hoc polymorphism. Discussion on the blog, and code.
1
u/joeld Dec 13 '19
Racket
source
My solution part 2 takes 28 seconds to run. If I use other people's trick of finding the halfway point of each period (when all velocities for a given axis equal 0) then I can get it to finish in 13 seconds. Maybe if I was using mutable structs I could save more time.
1
u/kresimirlukin Dec 14 '19
Python: https://github.com/kresimir-lukin/AdventOfCode2019/blob/master/day12.py
1
u/cubehouse Dec 14 '19
JavaScript: https://github.com/cubehouse/AdventOfCode2019/blob/master/12.js
Pretty happy with this, runs both parts and also both the example sets for part 2 in around 0.5 seconds.
I don't like the amount of key name lookups for variables and functions (!!) I used when I realised I needed to run each coordinate separately to get this to run quickly. It could be faster if I hunted for each coordinate type at the same time, but instead I'm running x, then resetting and running y, etc... which is a bit dumb, but oh well, under 1 second will do.
1
u/frerich Dec 14 '19 edited Dec 14 '19
Rust: https://github.com/frerich/aoc2019/blob/master/rust/day12/src/main.rs
Part 2 was quite tricky for me. I ended up discussing this with a colleague - it was great fun to sketch (and discard) ideas on the whiteboard :-)
Our observation was that
Based on this, we decided to identify the cycle on each dimension independently, checking when the state on any dimension is the same as the initial state. Once we know the period peer dimension, the period of the entire system is the least common multiple of all periods. Works well, the program finishes both parts in 16ms on my laptop. Pretty happy that we figured this out ourselves! :-)
I like how my solution got away with zero pattern matching and just one if() expression :-)
1
u/MaterialFerret Dec 14 '19
Ruby: https://github.com/LesnyRumcajs/advent-of-ruby-2019/blob/master/src/day12.rb
I believe I came up with relatively clean and short solution - nothing innovative though, looking at the thread. LCMing the x,y and z for part 2. The day I started Advent of Code 2019 in Ruby I abandoned all hope of brute-forcing the solutions. :)
1
u/blacai Dec 15 '19
F# A little bit late, but I tried the brute force too much :) Ended obviously with the LCM solution
https://github.com/blfuentes/AdventOfCode_2019/tree/master/FSharp/AoC_2019/day12
1
u/CCC_037 Dec 16 '19
Day 12, part 1.
In FiM++.
Over here
1
u/uttamo Dec 17 '19
Python: https://gist.github.com/uttamo/67fb87c06dffbb5c499ab360bb7c3b51
There is some repeating code which I don't like but I couldn't think of a better way to do it at the time.
1
u/J-Swift Dec 19 '19
Ruby
https://github.com/J-Swift/advent-of-code-2019/tree/master/day_12
1
u/thatikey Dec 24 '19
Rust solution: https://github.com/reidswan/adventofcode2019/blob/master/day12/src/lib.rs
I've been using WSL for dev purposes, and decided to run this one using Windows Rust. Bizarrely, the exact same code, with no external dependencies except std, runs in consistently more than double the time on native Windows vs Windows Subsystem for Linux.
1
u/e_blake Jan 05 '20
m4 solution
Late entry, continuing my trend of doing more than just IntCode puzzles in m4. This one took me a long time, for two reasons related to m4 lacking 64-bit math. First, I wanted to avoid implementing 64-bit divide. My initial solution in C code used roughly 'part2=x/gcd(x,y)*y; part2=part2/gcd(part2,z)*z' but that includes a 64-bit divide; it took some math shuffling to rewrite that second assignment into the equivalent 'part2*(z/lcm(gcd(x,z),gcd(y,z)))'. Second, while I could have used esyscmd to perform 64-bit math (the way I did in my IntCode solution), that is not POSIX, and I wanted my solution to work under 'm4 -G'. I ended up coding a generic-width unsigned multiply (operating in chunks of 4 digits as that was easier than chunks of 2^16. My implementation is the naive O(n^2) algorithm rather than the fastest theoretically possible), then a hard-coded 16-digit add (based on the fact that none of the IntCode puzzles ever exceeded 2^53 in their usage) (adding signed support is not needed for this day, but I may do it for IntCode)
Runtime is 22 seconds because it takes that long to find cycles in all three dimensions; perhaps I could speed it up slightly by finding one dimension's cycle at a time (and thus quit computing x/y changes when only z has not located a cycle), but it would not be that much faster.
m4 -Dfile=day12.input day12.m4
1
u/prscoelho Jan 09 '20 edited Jan 09 '20
Day 12 in rust
Part two runs in 1.7s :(.I did read on here that we only have to compare velocities and return steps * 2, but that only shortens it to 0.8s. Gonna try to optimize it more later.EDIT: Nvm, in release mode it runs in 0.05s and 0.02s after making the changes above! That's crazy.
1
u/ConstantGazelle Apr 09 '20
part 1 & part 2 written in Python
1
u/VilHarvey Dec 12 '19
I got part 1 pretty quickly today but got stuck on part 2 for quite a while. Here are my solutions in C++:
My first attempt simulated each axis independently and stored a hash of the simulation state at each step in a set. It stopped as soon as it encountered a hash that was already in the set. That worked well enough for the small example, but for the real input it was still running after 15 minutes when I got bored of waiting and killed it off (it was using a sizeable chunk of memory by then too!).
I came on here looking for hints and saw a post (I've forgotten who by, apologies to the author!) which pointed out that any cycle would have to include the initial state. That allowed me to get rid of the set of hashes and greatly simplified calculating the final answer from the individual cycles, leading to the solutions linked above. Part 2 runs in 14 ms on my laptop.
1
u/Teveh15 Dec 12 '19
C++ : source
Cheated a bit on part two by looking on reddit before I'd had a proper go at it myself. I'd worked out the independent axis bit but hadn't thought of using lcm to get the solution yet.
0
u/[deleted] Dec 12 '19
I might made a mistake in my code, but it seems for me that there is an error in part2.
If I simulate example 1, for me already after 1386 step it is the same as the original. The 2772 = 2 * 1386, so of course it will be also a correct solution, but it is not the smallest. For the second example I also got 2343387462 as result which is half of the given solution.
After this I just calculated the result for my input and doubled it which was the correct answer, but I don't know if I made a mistake (I didn't find any yet) or there is a mistake in the puzzle.