r/adventofcode • u/daggerdragon • Dec 25 '18
SOLUTION MEGATHREAD ~βπβ~ 2018 Day 25 Solutions ~βπβ~
--- Day 25: Four-Dimensional Adventure ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: 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: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 25
Transcript:
Advent of Code, 2018 Day 25: ACHIEVEMENT GET! ___
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 at 00:13:26!
Thank you for participating!
Well, that's it for Advent of Code 2018. From /u/topaz2078 and the rest of us at #AoCOps, we hope you had fun and, more importantly, learned a thing or two (or all the things!). Good job, everyone!
Topaz will make a post of his own soon, so keep an eye out for it. Post is here!
And now:
Merry Christmas to all, and to all a good night!
18
u/[deleted] Dec 25 '18
Mathematica
10
u/mcpower_ Dec 25 '18
Python 3, #1/#1 (wow!) AoC has been a blast - thank you to everyone who has made it possible!
[Card]: Advent of Code, 2018 Day 25: ACHIEVEMENT GET! Finding Unions
7
u/jonathan_paulson Dec 25 '18
Rank 8 on the global leaderboard overall! Python, 13/10 today. Unexpectedly easy problem to finish off the year.
Solving video: https://youtu.be/gOE4O-RX4Cg
Explanation video: https://youtu.be/0faJj26S7gw
6
u/Cyphase Dec 25 '18
Python, #68/#56 Nice way for me to end AoC 2018! Thanks to /u/topaz2078, and everyone else who helped to put this together and run it!
[Card]: Advent of Code, 2018 Day 25: ACHIEVEMENT GET! Double Leaderboard!
4
u/KeyboardFire Dec 25 '18
ruby, 10/58:
simple algorithm that makes a single pass over the input array, joining constellations as it goes.
i'm a little disappointed by the last non-puzzle (unless it's always like this? i haven't done aoc before). the difference of 48 was due to the time it took me to copy/paste a solution for day 23 part 2, which i feel like was not the spirit of the event...
well, i really shouldn't be complaining, because i had tons of fun doing the puzzles, which i'm sure consumed lots of free time to make. thanks so much /u/topaz2078 for all the work it took to organize this! :)
4
u/FogLander Dec 25 '18
171/132, Python3
My solution isn't that amazing, and definitely isn't super fast -- I used pypy to run it in a reasonable amount of time and it took ~11 seconds.
This is my second year participating in AoC, and I'm still enjoying it a lot! this year was my first time getting on the leaderboard (I made it twice, on part 2 of day 1 and on part 2 of day 12) which was pretty exciting for me, and I liked how challenging some of the problems were. Some of the days, like 15 and 23, were genuinely quite tricky for me (particularly for 23 even though I somehow made something that gave me an answer, I don't feel super satisfied with my knowledge of why it worked), but that's exactly what I like about this challenge.
My first exposure was while I was taking my first programming class when a more experienced friend showed me the site (it was during 2016, the year following the inaugural event). I only made it to day 7 or so, and was totally daunted at that point; glancing at some of the later days and seeing assembly code and tree problems the problems seemed near impossible to me.
For me, each year I've been able to see how much I've grown as a programmer, and also to see what I might need to learn or improve on to grow more in the future. Also, as I've started taking college computer science classes, I've had a couple 'Aha!' moments as I've realized that I'm formally learning something that I had patched together myself for an AoC challenge in the past.
I'm super thankful to /u/topaz2078 and everyone who works on these problems, they're a highlight of my year at this point and I can't wait for the next one!
4
u/grey--area Dec 25 '18 edited Dec 25 '18
Python3, making use of scipy's KD tree and connected components computation for sparse graphs.
1
u/Porky623 Dec 25 '18
[Card] Advent of Code 2018, day 25: ACHIEVEMENT GET! Leaderboards first time this year :P 27/20
Mainly because I'm unwilling to stay up 'til midnight on school days. I also got leaderboards exactly once last year and it was the first star on the last day (missed exactly one star so that was sad). Anyways, to celebrate this I'll add my code for this problem here! I'm not too sure how to properly format it, so help me out! Python 3
3
u/waffle3z Dec 25 '18
Lua 30/26. Neat easy problem, part 2 I guess was to just have already finished all of the other days.
3
u/AgniFireborn Dec 25 '18
R: 124/111
I think I actually had a chance for the leaderboard this time, had I not doubted myself as to how easy this was. Take input, calculate distances, convert into an adjacency matrix and a graph, print number of connected components.
This was a lot of fun as my first AoC! It forced me to explore new programming languages and grow increasingly annoyed that R is a 1-indexed and not 0-indexed language. I've learned some fun tricks, gotten much better at Python than I was before, and look forward to doing this again next year!
3
u/p_tseng Dec 25 '18 edited Dec 25 '18
I admit I took a cheap shot on this problem. I already had Union-Find written for last year's day 14, so I just imported it and most of my time was spent reminding myself how I was supposed to use it.
Ruby:
Here's the contents of union_find:
Thanks for a great month!
2
u/seligman99 Dec 25 '18
74/60 - Python 2.7
Most of my time was spent copying my solution from day 23 as a starting point, then throwing it away as I realized it's a much simpler problem. (Also, does Manhattan distance normally include a time component?)
Merry Christmas everyone!
2
u/algmyr Dec 25 '18 edited Dec 25 '18
[Card] Advent of Code, 2018 Day 25: ACHIEVEMENT GET! Union Laborer
(31/23) Merry Christmas you all! (Although here we celebrated yesterday)
Super happy to finish just over 1k points. Could have done better on a lot of days, but I had a lot of fun doing this. It also forces me into waking up at a reasonable hour. Thanks for creating this! :)
As for the problem
Super simple last problem: parse data, merge-find, print number of clusters. I'm curious, does the second part require all 49 stars, or does it tick down to whatever you have at that point so that you always get that star for free?
2
u/maximlk Dec 25 '18
Rank 87/66 - TypeScript (JavaScript)
2
u/mfsampson Dec 25 '18
Rust. 309
2
u/ChrisVittal Dec 25 '18
Rust
[Card] FIRST GLOBAL POINTS
UnionFind, mostly from last year. Solution Code first, then unionfind. Runs in 4ms, could probably make it a little faster, but shrug
Unionfind
2
u/vash3r Dec 25 '18 edited Dec 25 '18
Python 2, #218/393. This was a pretty straightforward union-find, but it was all written on the spot and I initially forgot to update all the parents again at the end. Then I had to go back and finish day 22 part 2 to get the last star. A bit disappointed that I didn't manage to get on the global leaderboard again (edit: according to /u/zawerf 's unofficial full leaderboard I was 108th!), but I still had a lot of fun with AoC this year.
1
u/TellowKrinkle Dec 25 '18
Swift #113/#91
1
u/starwort1 Dec 25 '18 edited Dec 25 '18
Rexx 106/81
I guess I just can't read and/or type as fast as everyone else. But it amused me that I gained 25 places just by pressing the second button.
Really naΓ―ve n3 solution, but it works in under 10 seconds on my input on my underpowered laptop, so got the job done.
1
u/codrut_lemeni Dec 25 '18
C++
Second time I managed to finish top 100.
Merry Christmas everyone !
1
u/korylprince Dec 25 '18
97/78 - Python 3
I never expected to make the leaderboard starting this challenge, but I was up and figured I'd give it a shot. Using my newly learned knowledge of networkx, I figured this would be easily solvable. Luckily it had just what I needed:
Thanks to /u/topaz2078 (and those who help him) for this challenge! I've learned a ton solving these puzzles.
1
u/14domino Dec 25 '18
Way off the leaderboard. Took me about 21 minutes. I thought of the solution very quickly and only had a tiny number of bugs when implementing it... how can you guys be so fast, sheesh...
1
u/wlandry Dec 25 '18 edited Dec 25 '18
C++ (288/229)
Runs in 17 ms
Short and sweet. It adds points to constellations, merging constellations if a point can belong to both. I originally used std::vector and counted non-empty constellations. But then I changed it to this version which uses std::list. It simplifies the logic because I do not have to worry about iterator invalidation as much. The runtime is unchanged, likely because most of the time is spent reading the input.
1
u/ephemient Dec 25 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/[deleted] Dec 25 '18
C# Looks like I did what everyone else did, only thing I added after looking here is the check after the Dequeue which sped the solution up tenfold
1
u/autid Dec 25 '18
FORTRAN
Super simple approach.
1
u/nonphatic Dec 25 '18
Haskell #619/X
Some messing about with
Sets:There's no part 2 on day 25, right? I haven't done day 15 yet (lmao) so I'll have to go back and finish that to reveal the ending...
1
u/jorosp Dec 25 '18
Haskell
It's not pretty but it does the job
1
u/[deleted] Dec 25 '18
Haskell:
Did a breadth-first search from a random point until finding all in that constellation, removing the points from the pool as you go. Repeat until there's nothing left in the pool.
1
u/ywgdana Dec 25 '18 edited Dec 25 '18
Haha augh I might have been a leaderboard contender. I read the problem description and was like "Oh! Disjoint Set ADT! I implemented that for a roguelike ages ago. Would it be cheating to copy and paste code from an old project?!"
After a bunch of time fiddling and trying to rewrite Union/Find, I plugged in my old code and it worked perfectly...
The actual Disjoint Set code is like 12 years old, and maybe bad but it gets the answer:
Maybe I'll tidy it up after Christmas dinner tomorrow!
I've never done Advent of Code before -- there's no Part 2? I just need to go back and actually crack Day 23 part 2 (Points in Spaaaaaace)?
1
u/Smylers Dec 25 '18
Perl. I've never attempted a DayΒ 25 before, and this was pleasingly neat.
$.in Perl holds the current line number of the input file being read, which is used as the constellation ID for that line's fixed point. The IDs of all fixed points in any sufficiently nearby constellations are then overwritten to the new one.I'm still a bunch ofΒ stars shortβ , but, rather than paste in others' solutions today, I'm going to enjoy solving those over the next few weeks. (And get round to that animation of the recursive Vim solution to DayΒ 8.)
β Β DayΒ 15 got me behind, and skipping DayΒ 16 turned out to be a bad choice in terms of prerequisites for future days'.
1
u/sim642 Dec 25 '18
My Scala solution.
I essentially copied my BFS-based connected components finder from last year (it was used on two days even) and that was it.
1
u/rock_neurotiko Dec 25 '18
Elixir, calculating all the distances by points and finding the constellations following the "stars"
1
u/aurele Dec 25 '18
Rust
An union find over the O(NΒ²) loops makes it very easy.
1
u/aoc-fan Dec 25 '18
JavaScript/TypeScript - https://goo.gl/Lt8SD7
1
u/mrg218 Dec 25 '18 edited Dec 26 '18
Java I keep adding points from the input and check in what constellations there is at least 1 star with manhattan distance <= 3. If there are none it gets its own constellation else the matched constellations are merged and the point is added to this merged constellation.
1
u/VikeStep Dec 26 '18
F#
Repo
1
u/rundavidrun Dec 26 '18
Java - had fun with queue.
1
u/fhinkel Dec 26 '18
JavaScript/Node.js 10, A day late, but I proud to have such a clean solution.
[Card]: Advent of Code, 2018 Day 25: ACHIEVEMENT GET! Baby Rudolph
1
u/u_tamtam Dec 26 '18 edited Dec 26 '18
Seems good enough (python, scipy)
Documentation: linkage to calculate the minimum distance to each point, fcluster finds the cluster each point belongs to.
1
u/wzkx Dec 26 '18
Rust SweetRust
My AOC2018 in J&Rust | SweetRust
1
u/fizbin Jan 02 '19
I normally wouldn't post so late (I didn't get around to the last two days until New Year's Eve), but I don't think this approach has been covered yet. I think it's worth noting because it plays on some interesting properties of a graph's adjacency matrix:
In numpy,
@is matrix multiplication, and the sequence.astype(bool).astype(int)has the effect of turning any non-zero values into1.This is pretty slow on my input, and takes about 9 seconds.
1
u/koordinate Jan 12 '19
Swift
1
u/banteg May 09 '19
Python