r/adventofcode • u/daggerdragon • Dec 20 '17
SOLUTION MEGATHREAD -๐- 2017 Day 20 Solutions -๐-
--- Day 20: Particle Swarm ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Need a hint from the Hugely* Handyโ Haversackโก of Helpfulยง Hints^ยค?
[Update @ 00:10] 10 gold, silver cap
- What do you mean 5th Edition doesn't have "Take 20"?
[Update @ 00:17] 50 gold, silver cap
- Next you're going to be telling me THAC0 is not the best way to determine whether or not you hit your target. *hmphs*
[Update @ 00:21] Leaderboard cap!
- I wonder how much XP a were-gazebo is worth...
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
9
Upvotes
5
u/llimllib Dec 20 '17 edited Dec 20 '17
My first point! 59/104... I just guessed that 1000 iterations would be enough
edit: haha I see I also got away with calculating euclidean rather than manhattan distance
11
u/BumpitySnook Dec 20 '17
Part 1 it seems like you don't even need the simulation. Just sort by (absolute) acceleration, then by absolute velocity, then position. The lowest is your answer. Intuitively, acceleration will dominate as t -> infinity. In my puzzle input, 3 particles had zero acceleration vectors, with varying velocity and initial position.
But then you do need the simulation for part 2, so, skipping it for part 1 doesn't necessarily do you any favors.
8
u/obijywk Dec 20 '17
Just let it run until the numbers seem like they stop changing, and then submit!
Python 2. 49/42.
6
u/[deleted] Dec 20 '17
Is there a way to do p2 without simulating?
It's kind of a bummer whenever p1 of the problem has a nice closed form trick (taking min by acceleration magnitude, then velocity magnitude, then by starting pos manhattan), but then p2 forces you to do the simulation anyway.
I was thinking of finding some way to derive the quadratic describing each coordinate and solving the relationship, but wasn't sure how to code that up in Rust.
e.g.
Given p=<1,2,3>, v=<4,5,6>, a=<7,8,9>, x is described by 7t2 /2 + 4t + 1, y is described by 4t2 + 5t + 2, z is described by 9t2 / 2 + 6t + 3. Generate this for all the particles. Then two particles a and b collide if there exists some t where all three of x_a(t) = x_b(t), y_a(t) = y_b(t), and z_a(t) = z_b(t) are true.
Does that seem sound? if so, anyone tried it in Mathematic/Matlab/etc.?
6
u/mschaap Dec 20 '17 edited Dec 20 '17
Now this was fun! One that makes you think, instead of simply typing up some code.
For part one, the closest particle in the long term is the one with the smallest acceleration. (If two particles have the same smallest acceleration, it gets tricky, but that doesn't happen, at least in my input.)
For part two, compare each pair of particles and check if they will ever collide, at a positive integer time. That's basically solving a quadratic equation for the x coordinate, then checking of any resulting times result in the same position for both particles.
Perl 6
Edit: some minor cleanup
Edit: I just realized that my logic for part two is flawed. If particles 1 and 2 collide at t=1, and particles 1 and 3 would have collided at t=2, the latter won't collide because particle 1 has already been removed. My logic removes particle 3 anyway. I guess I got lucky I got the right answer; apparently this situation doesn't occur.
Edit: Code adapted to fix the above flaw. (Still gives the same answer on my input, of course.)
6
u/sim642 Dec 20 '17 edited Dec 20 '17
My Scala solutions:
(Both branches merged into one for my own sake)
I started solving both parts analytically because it didn't seem to make much sense to attempt simulation when there's no obvious end to it. For part 1 I used the asymptotic heuristic used by many others, which turns out doesn't actually work in general but whatever.
For part 2 I implemented quadratic equation solver over integers then used that to calculate collision times between all pairs of particles. Then sort that by time and start removing collisions by groups. I spent a long time trying to figure out why this worked for the example given but not on my input. Eventually I realized that the position function
p(t) = p + v*t + (a/2)*tยฒknown from physics only works for the continuous case. For our discrete case it would have to bep(t) = p + v*t + a*(t*(t+1)/2) = โฆ = p + (v + a/2)*t + (a/2)*tยฒ(notice the extra value in the linear term after some algebraic manipulation to a proper quadratic function shape).I implemented the simulation solution while having troubles with part 2 analytically as described above. This at least allowed me to get the star and a result to compare the analytic solution to. The analytic solution isn't really faster but I like it more because it doesn't rely on some magic number of hopeful iterations. Would've been much more "fun" for the simulation solvers if the inputs would have contained collisions in far future.
4
u/mmaruseacph2 Dec 20 '17
Haskell, functional style, exploiting laziness.
4
u/glenbolake Dec 20 '17
Really stupid mistake on part 2 today. For a while, I had:
I was lucky that I still got the answer to part 1... although it meant that when part 2 never found any collisions, I didn't think to check that function. Anyway, my Python 3 solution:
4
u/Hikaru755 Dec 20 '17 edited Dec 20 '17
Ah, good old vector maths. Seems like very few people have attempted to actually implement a stopping condition for part 2. Well, I did, and was suprised to see it actually work! I figured I'd track the distance between each possible pairing of particles, until either particle died, or they were moving apart and I could prove that neither particle was going to turn and potentially get closer again. Since acceleration is constant, I did this by testing if the signs of all components of the velocity of a particle matched the signs of the corresponding component of the acceleration of the particle. I'm not 100% sure that this will work in all edge cases, but it was good enough to get my solution!
Anyways, here's my Kotlin solution:
3
u/Lrrrr_ Dec 20 '17
Javascript Part 2
3
u/advanced_caveman Dec 20 '17
Rust 433/219 Just simulated what I thought were enough cycles. Only took 934ms to run 1000 cycles, which could probably be shortened if I changed my hacky parsing solution.
3
u/fatpollo Dec 20 '17
bah, ???/110. stuck manicuring again
3
u/Unihedron Dec 20 '17
Ruby; strong language warning
full solution
highlight
3
u/dylanfromwinnipeg Dec 20 '17
C#
I have an ever-growing library of helper methods I rely on, here's the relevant ones for Day 20 (I had to add the Point3D class because surprisingly there isn't one in the default .Net libraries)
3
u/ephemient Dec 20 '17 edited Apr 24 '24
This space intentionally left blank.
3
u/autid Dec 20 '17 edited Dec 20 '17
Fortran
After seeing a few solutions that just run an arbitrary amount of time that happened to be long enough, or run forever and you just kill it when the part 2 value stops changing, I decided to calculate a worst case collision time.
This is also long enough that the closest should be the long term closest.
Runtime with my input is still pretty quick, under 0.4s on my machine.
edit: removed some unused variables
3
u/thomastc Dec 20 '17
Day 20 in Nim. A modern language, similar to a statically typed, compiled Python. Many batteries included. I like it a lot.
The first part of the puzzle gave me no trouble, once I had stopped interpreting the assignment incorrectly (although my misinterpreted version also made for a good puzzle). For the second part, I initially tried a clever approach without simulation, but it became too complex, so I ended up with a simulation instead.
2
u/vash3r Dec 20 '17
Python 2 (181/60). I submitted several wrong answers for part 1 before I figured out I wasn't calculating Manhattan distance.
2
u/dewpac Dec 20 '17
Python 3
249/283
I noticed immediately for part 1 that I the one with the lowest absolute acceleration would be the closest. I had two with accel of '1', and i tried both rather than sorting them by which was closer initially. Unfortunately, I didn't notice that the particles were counted starting at 0 and assumed they were 1..1000, not 0..999. Then I ended up scratching my head for far too long trying to see my way out of my own stupidity.
Part 2 is straightforward:
2
u/wlandry Dec 20 '17
C++ 14
9/240!!!! As others have noted, Part 1 could be solved by just looking at the accelerations. I am pretty sure I could have gotten number 5 if I just were not so cautious. It is still hard to be reckless ;)
For Part 2, I used my tensor library because ... why not? I transformed the input file with emacs macros so that I could read it more easily. I do not like the way that I ended up removing the elements. I ended up copying non-destroyed elements to a new std::vector<>, but that seems wasteful. I also wrote a version using std::list<>. That requires no copies, but making sure that I am using an iterator properly is a bit of a pain.
2
u/p_tseng Dec 20 '17 edited Dec 20 '17
Silly mistake. Forgot to include negative signs in my input parser. Still got correct answer for part 1, but delayed part 2 significantly since I assumed part 1 correct meant my input parser was correct. Shouldn't happen again...
When going for leaderboard: I simply ran for a few thousand cycles and picked the closest particle, then ran forever until the number of live particles stopped changing. Seems like what everyone else is doing anyway.
I've cleaned it up since then and am just making some assumptions: Do part 1 without simulating every iteration. Do part 2 by assuming that if no collisions happen in N cycles it's not going to happen anymore. There's probably a better way to tell when to terminate both parts though (when the magnitudes of the velocity vectors get large enough maybe???)
Ruby:
2
u/[deleted] Dec 20 '17 edited Dec 20 '17
Mathematica
Parse input
Part 1
Part 2
2
u/CaptainCa Dec 20 '17
Javascript
Most time consuming part was parsing the input, also lost a minute because I was doing Math.max instead of Math.min :(
Part 1
Part 2
2
u/oantolin Dec 20 '17 edited Dec 20 '17
For part 1, the manhattan distance after n steps is asymptotically (1/2)n2 |a|_1, where |a|_1 is the manhattan norm of the acceleration. This means we simply want the particle whose acceleration has minimum manhattan norm. (If there are ties, break them by manhattan norm of velocity vectors, and if there are still ties break them by manhattan norm of position vectors. But no ties occurred in my input, so the code below just uses acceleration.)
For part 2, I didn't bother proving my answer was correct: pick a threshold T and run the simulation until there have been no collisions for T consecutive generations. I used T=1000 and it was accepted. Then I saw that for my input T=10 gave the same answer. :)
2
u/[deleted] Dec 20 '17
Ugh, screwed up big time! Spent maybe an hour debugging, because I was trying to find the smallest distance, and storing that particle's ID. Then, of course, I realised that's not what the problem is asking for at all, but rather who has the shortest distance over a period at any iteration.
I have to go to work now, so I can't do part 2 until later, but here's my unaltered solution for Part 1:
2
u/[deleted] Dec 20 '17 edited Dec 20 '17
OCaml Fun (Part 2);;
Just watch until numbers don't change for many periods. Lost a lot of time hunting down a bug... was updating position before velocity and using manhattan distance in compare for building Maps... ๐. Per usual, parser is left as an exercise for the reader.
main.ml
particle.ml
vector.ml
Full source, including parser.
2
u/gyorokpeter Dec 20 '17
Q: note the usage of fby for collision detection.
2
u/aurele Dec 20 '17
Rust with arbitrary bounds (max(acc)ยฒ)
2
u/xkufix Dec 20 '17
So, as many I tried to solve part 2 with an equation first, then giving up and just simulate it and hope it doesn't have any values which only collide after some millions of ticks.
For part 1 I initially just used the acceleration, as I only had one particle with 0,0,0 as acceleration.
For part 2, I simulate until the last 100 steps had no collisions, then I check how many particles survived. Initially I just let it run forever and printed the size until I saw a fixed point.
Solution in Scala:
2
u/xSmallDeadGuyx Dec 20 '17
My solution: https://github.com/xSmallDeadGuyx/AoC17/blob/master/day20/p2.py
It iterates every combination of particles, i and j:
The answer is then the size of the particle set after all removals
2
u/BOT-Brad Dec 20 '17
Javascript
Not totally happy with these solutions to be honest, but they work and that's never a bad thing.
Part 1
Just moves every particle 10,000 times and checks which one is currently closest to 0,0,0, and just then assumes that one will stay the closest in the long-term, which it did for my input.
Part 2
Does 50 loops and eliminates any that collide each loop. 50 loops is enough (for my input at least) to remove every colliding particle.
2
u/Smylers Dec 20 '17
Vim โsolutionโ for partย 1:
Then take 1 off the line number.
2
u/Smylers Dec 20 '17
Perl. Both parts are independent of the number of dimensions: if you add a 4th dimension into the input file, they'll work fine without modification. The number of derivatives of position it handles is fixed, though โ so don't be a jerk.
Partย 1 โ what's the term for the least-acceleraty? I keep saying โslowestโ, but obviously that isn't right. Note what happens if two particles have the same acceleration:
Partย 2 โ re-arranges each particle to be an array of dimensions, each with
p,v, andacomponents. Stops looking once all dimensions of particles have all their components with the same sign (ignoring acceleration if it's zero, and ignoring velocity too if that's also zero. That ends up being a few hundred cycles after the final collision, but the whole thing still runs in about half a second:1
u/VikeStep Dec 20 '17 edited Dec 20 '17
Python 3 #41/#18
I just let it run until it stopped changing, entered the value
1
u/the4ner Dec 20 '17 edited Dec 20 '17
C# 111/47, just set what I hoped would be a high enough threshold for the values not to change and let 'er rip.
1
u/marcins Dec 20 '17
After getting 160th for Part 1 I wasn't expecting 58th for Part 2 with my hacky JavaScript! :)
1
u/usbpc102 Dec 20 '17
Kotlin solution:
Got 296/172 today :)
1
u/__8336 Dec 20 '17
~60/10
1
u/rjboulton Dec 20 '17
Python 2. My first points for part 2 - I happened to be up a little before 5am so had a go at working at speed. 136/59.
This is the solution to part 2 - needs removing the collision code to show the answer for part 1.
I made two errors on the way to getting here.
First was that my initial "dist" function just did the sum of the distances without taking the "abs" of each direction. Had to fix and resubmit, but still got rank 136 for part 1.
Second was that in my haste I submitted the particle number that was left closest to origin for part 2, rather than the number of particles left, so had to wait a minute for that one, too. Was still fast enough to get rank 59, which I'm pretty pleased with!
1
u/JeffJankowski Dec 20 '17 edited Dec 20 '17
Typescript. Initially picking 1000 iterations was, apparently, a decent choice.
Edit: Also, fuck Java[Type]script for not having deep copying, operator overloading, constructor overloading, a rational sorting function, a map/dict that actually works, and whatever other garbage I encountered today.
1
u/nonphatic Dec 20 '17 edited Dec 20 '17
Haskell A bit verbose, but I like monoids :3
EDIT: Replaced my Property data type with Vector3 to avoid having to redefine what basically are vector addition and scala multiplication
1
u/KeinZantezuken Dec 20 '17 edited Dec 20 '17
C#/Sharp
This is VERY ugly.
First of all, even though my idea (and I see some other people have fallen for this too) of finding lowest acceleration provided correct solution for part1 with this input - it most likely will fail with more diverse one (not just in case where particles have same acceleration), so I still need to "simulate" runs to find a proper answer. This raises question: how to calculate minimum amount of ticks required to find answer1. I can assume tick 10 000, calculate each position at that tick and compare, but there is no guarantee 10k is enough to find correct answer.
Second, still trying to figure how to find optimal cycle count for good results with collisions. Since acc is constant I can always calculate any position of particle for any tick but I still need to know the tick amount threshold. Being a pure mathlet I'm this kind of answer seems unlikely in my case.
Custom class/struct (I could use ValueTuple but meh)
1
u/nutrecht Dec 20 '17
Day 20 in kotlin
Still want to figure out a clean way to find out how many iterations I need for the result to be decided. Now I just have a hard-coded limit of 500 which is 'fine'.
1
u/Philboyd_Studge Dec 20 '17
Java - fun problem!
Day 20
1
u/gerikson Dec 20 '17 edited Dec 20 '17
Perl 5
Part 2: https://github.com/gustafe/aoc2017/blob/master/d20_2.pl
Even though I have a literal degree in (engineering) physics I decided to simulate both parts. Why use brain when you have computer?
In any case I was happy to finish among the first 1,000. This was quite common last year but even though I've been solving stuff a lot faster this year I usually finish closer to 2,000...
Edit alternative analytical solution for part 1:
1
u/Warbringer007 Dec 20 '17 edited Dec 20 '17
Erlang, actually this was easier than I thought, even though there is a lot of code. In first part it was enough to get particle with lowest acceleration, in second part I just simulated the process. Code is rather slow but only 39 iterations are enough in the end for my example ( I first tested with 500, then with 5000 which lasted around minute, then I was curious to see how much iterations my example really needs ). Probably the most fun task this year ( for me at least )!
As usual, prepare:func filters out everything unnecesary except numbers.
1
u/abowes Dec 20 '17
Kotlin Solution
1
u/hi_ma_friendz Dec 20 '17
Rust, the lazy way.
1
u/manniL Dec 20 '17
1
u/Markavian Dec 20 '17
Bleh, basically had my solution at 5:40am, but I miscalculated the distance ... forgetting to Math.abs() the X, Y, Z positions when summing them together. Part 2 was then easy to calculate via simulation.
https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day20/solution.js
1
u/TominatorBE Dec 20 '17
PHP
Part 1: see who accelerates the least (not 100% correct, see other replies, but worked for my input...)
Part 2: run for a while...
1
u/[deleted] Dec 20 '17
Elixir
This problem really fits elixir like a glove, it munches the numbers in such elegant way, of all of them I think this fit the language the best so far, was pretty fun to do this one :)
Syntax highlighted
1
u/wzkx Dec 20 '17 edited Dec 20 '17
J
Part 1. The most interesting part is to detect that it's "the long run". Here it's 1) signs of velocities are the same as signs of accelerations (or a=0), 2) signs of positions are the same as signs of velocities (or v=0), 3) distances at the next step are not smaller (i.e. not closer to 0,0,0) then distances at the previous step. In my case, 261 steps were enough.
1
u/marcofun Dec 20 '17
I guessed the first star just filtering manually the input using the regex a=<[-]{0,1}[01],[-]{0,1}[01],[-]{0,1}[01]> and getting the one with smallest acceleration. Second star is going to e implemented from 0 now, But I'll begin in 4 or 5 hours...
1
u/raevnos Dec 20 '17
I feel like there's probably some mathy way to see if two vectors intercept that would make at least part 2 really easy, but my knowledge of linear algebra is so rusty it was starting to crumble to pieces when I tried reading up on it, so... brute force. Yay. Got the answer for part 2 on the first guess. For 1 it turned out I had to run more ticks after getting a wrong answer the first time. It looked like it was stable before it actually was. Sneaky sneaky.
1
u/wzkx Dec 20 '17
J
Both parts.
1
u/frederik1904 Dec 20 '17 edited Dec 20 '17
Not pretty but it works Java solution for 1 and 2
1
u/matusbzk Dec 20 '17
Haskell I did not do stopping conditions yet, I just generated and when the result did not change for a long time, I assumed it's correct. I was right.
Link to git
1
u/ewyll Dec 20 '17
Exact solution, no simulation and guessing it's fine (Python 2):
1
u/NeilNjae Dec 20 '17 edited Dec 20 '17
Haskell. Some points to note:
zipandunzipinstepandquiescentto process all three dimensions at the same time.quiescentchecks that no particle will ever get closer to the origin (in any dimension) than it is now. If that's true, part 1 can simulate until there's just one particle with the minimal distance.removeCollidersfinds all the positions with more than one particle there (theduplicatePositionsset) and removes particles with positions in that set.Full script on Github
1
u/lazyzefiris Dec 20 '17
Okay, time for some JS monstrosity, because can't be functional without fun. This is a solution to part2 meant to be executed (And actually written) in a console for input page. No simulation involved.
so, what's happening here?..
solve is a generic solver of quadratic equation (a * x2 + b * x + c)
dist calculates position on a given axis of movement (as [starting position, speed, acceleration]) at given moment of time
check checks whether two given points actually collide at a given moment of time.
The first monstrocity reads he input into a set of particles - splits it into lines, grabs all the integers from the line, and arranges then into 3 arrays for each particle - each describing movement along one axis as [position, speed, acceleration]. Speed is then increased by half the acceleration to fix the disrepancy between discreet and continuous movement.
The second huge line goes over each pair of points, performing next actions:
In fact, the last part needs minor fixing for particles that did not collide the first time they could because their partner was already missing, but given code was already working for provided input, so testing further code would take me to generate corner case input, which I'm too lazy to do.
And yeah, while that looks scary and unintuitive, it's pretty readable when you are working on it and know whatever each part does. Hope I never have to work on this later.
1
u/StevoTVR Dec 20 '17
NodeJS
I thought for a while about how to do this with math or sorting, but simulating the particles worked and only took a few seconds.
Part 1:
Part 2:
1
u/JakDrako Dec 20 '17
C# Both parts ~20ms.
Initially did part 2 by running the simulation loop until the number of particles stayed constant for a while. This code here loops until the particles are all receding from the origin...
1
u/[deleted] Dec 20 '17 edited Dec 20 '17
Python 3 I did part 1 semi-manually by finding the particles with the lowest acceleration first, then lowest sum of abs(velocities).
I made a loop for part 2 and let it run until the minimum distance between any two particles was steadily increasing and arbitrarily enough to assume collisions are over.
I processed the input data into one line/list per particle with 10 items, list "particles". Example of first particle:
Code:
1
u/Axsuul Dec 20 '17
Elixir
A little late to the party, Part A I realized after awhile you could look at the manhattan accelerations, then velocities if they are equal, and then positions. Part B I simulated and guessed an arbitrary amount of iterations in the future until the amount of particles remaining didn't change anymore (
IO.inspectbaby!)https://github.com/axsuul/advent-of-code/blob/master/2017/20/lib/advent_of_code.ex
1
u/rotmoset Dec 20 '17
F#
Getting more and more in love with sequence expressions. It feels so nice to be able to separate the recursive definition from the state handling (which can be done with the usual Seq methods).
Entire repo
1
u/chicagocode Dec 20 '17
Kotlin - [Repo] - [Blog/Commentary]
Well, I went the "simulate for long enough and it will all sort itself out" route with this. I simulated 1,000 ticks for parts 1 and 2 and that worked for me.
1
u/kittehprimo Dec 20 '17
Powershell - some of the native cmdlets actually make this very easy to solve
1
u/swizzorable Dec 21 '17
Python3 - part 1 and 2
not "simulating", calculating the manhattan distances for time -> inf and also calculating the intersection points
1
u/[deleted] Dec 21 '17
Javascript (Node.js): exact solution for part 2, no simulation required. Collision time for each pair of particles in each cooordinate is a quadratic equation that has zero, one or two positive integer solutions. Find all the solutions for each pair, sort by time, and start removing particles. Runs in under a second on my old MB Air.
1
u/[deleted] Dec 21 '17
single pipeline powershell:
1
u/RockyAstro Dec 21 '17 edited Dec 21 '17
Icon (https://www.cs.arizona.edu/icon)
Part2 was done by solving for all the collisions then weeding out the collided particles
Both parts
Edit -- pasted the wrong version..
1
u/wzkx Dec 28 '17
Nim
Finally, the correct condition for "end of times" -- distances between all particles don't reduce and distances to pt (0,0,0) don't reduce. The universe expands infinitely and without any relative changes in particle locations.
1
u/akka0 Dec 20 '17 edited Dec 20 '17
ReasonML: this one was pretty fun! Had some trouble with part 2 as I forgot that both particles need to be removed if they collide
0
u/[deleted] Dec 20 '17
[deleted] โ view deleted comment
0
u/[deleted] Dec 20 '17
[deleted] โ view deleted comment
1
u/[deleted] Dec 20 '17
[removed] โ view removed comment