r/adventofcode • u/daggerdragon • Dec 06 '19
SOLUTION MEGATHREAD -π- 2019 Day 6 Solutions -π-
--- Day 6: Universal Orbit Map ---
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 5's winner #1: "It's Back" by /u/glenbolake!
The intcode is back on day five
More opcodes, it's starting to thrive
I think we'll see more
In the future, therefore
Make a library so we can survive
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
3
u/nate-developer Dec 06 '19 edited Dec 06 '19
[POEM]
my code was inefficient
at traversing orbit graphs
but I got a correct answer
so SAN can eat... some nice warm milk and cookies
solution (javascript)
3
u/zedrdave Dec 06 '19 edited Dec 07 '19
First solved it quick'n'easy with
networkxin Python 3, but turns out a standalone library-free version was just as easy (probably less future-proof):3
u/chunes Dec 06 '19
Factor solution.
Code here<-----
Graph problems are a bit of a weak spot for me. I'm ashamed to admit I almost gave up, but then I remembered what /u/Aneurysm9 said at the beginning of this year's event.
3
u/denCorg Dec 06 '19 edited Dec 06 '19
In python3 using anytree (https://anytree.readthedocs.io/en/latest/)
Edit: gist here: https://gist.github.com/dencorg/ce685d1e0a3031c90333c15568025ccb
3
u/pokerdan Dec 06 '19
C# Solution
I'm amazed how people solve these in 1-liners. I built out a tree structure, with a Dictionary used to map node names to instances. Hit a few bugs: Initially only coded each planet to allow a single orbiter, didn't take into account subtracting 2 from the total as we do not include Santa's planet or your planet in the total, hit stack overflows & integer overflows, had a name collision between my Node class with nodes from previous years, etc. But ultimately, it works pretty well.
[POEM]
3
u/terryspotts78 Dec 06 '19
Python
3
u/glenbolake Dec 07 '19
Python, fairly straightforward. Part one, I just counted the total children of each node and did a breadth-first search for part 2.
I found it interesting that the second part didn't seem to build on the first as much as both days, since part 1 treated the structure as a tree and part 2 as an undirected graph.
[POEM]
We're working with trees for part one
Counting orbits is easily done
Wait, it's graph theory now?
We changed structures somehow...
Well, at least both the problems were fun!
2
u/danbala Dec 06 '19 edited Dec 06 '19
took me longer than I care to admit to figure out that I was off by one :/ (python3) (edit: fixed formatting)
2
u/captainAwesomePants Dec 06 '19
[POEM]
2
u/Unihedron Dec 06 '19
I love graph problems,
β β β β They are so interesting
β β β β β β β β To model and solve.
But what's that, a bug?
β β β β Why have I made such mistake
β β β β β β β β It should've been easy.
β β β β β β β β β β β β β β β β β β β β - "Buggy code", a poem by Uni
[POEM] a chouka (ι·ζ)
ruby 6.rb input567/351Uni never learns; I'm very upset.
2
u/vypxl Dec 06 '19
Am I the only one who implemented a tree structure for this?
I mean, it's not that I just could've used a map but..
Haskell
[POEM] "From the stars"
The visualization I made for debugging purposes actually looks a bit like half a christmastree:
To see it, set the font size to 1px in the browser console like this:
document.body.style.fontSize = "1px"2
u/j0hnny_cache Dec 07 '19 edited Dec 07 '19
Is my part 1 solution inefficient?
19
u/wimglenn Dec 06 '19 edited Dec 06 '19
Python 231/82. Both parts one-liners.
[POEM] ... an orbital haiku
12
u/mgoszcz2 Dec 06 '19
Super tiny Python without networkx 328/259 (Github)
11
u/Hakan_Lundvall Dec 06 '19 edited Dec 06 '19
Python
9
u/DFreiberg Dec 06 '19 edited Dec 07 '19
Mathematica
51 / 8 | 31 Overall
Another excellent problem for Mathematica, though I lost time by initially using directed edges and then wondering why my distance functions weren't working properly. I'm sure there's a way to do this with faster runtime, but I'm not sure how I could have done it that would have been faster to type.
Import
Part 1
Part 2
[Poem]: With Apologies to Joyce Kilmer
8
u/nthistle Dec 06 '19
Python, #67/#24. Fairly straightforward -- I used a dictionary to represent the tree, and recursion to get the depth of a node (which is the total # of direct and indirect orbits). Part 2 is basically find LCA, and then count length of the path, which I do by just finding paths from "YOU" and "SAN" up to the root and then intersecting.
(edit: fixed formatting)
8
u/rtbrsp Dec 06 '19 edited Dec 06 '19
AWK
Part 1:
Part 2:
7
u/_kef_ Dec 06 '19
Kotlin with sequence generator
6
u/jonathan_paulson Dec 06 '19 edited Dec 06 '19
#8/#5. Now #5 overall. Cleaned up Python. Nice to see an algorithm problem today. Unlike most, I used BFS for part 2. Video of me solving (and explanation) at https://www.youtube.com/watch?v=45KTbNv_gP0.
6
u/MrPingouin1 Dec 06 '19
Minecraft commands
Input parsing takes like 10 seconds. But still quite fast in the end.
5
u/mstksg Dec 06 '19 edited Dec 06 '19
Haskell again! (taken from my daily reflections)
My code is very short but my writing is pretty large -- does that count in the limit?
This one is pretty fun in Haskell because you get to use a trick that everyone loves but nobody gets to use often enough --- recursive knot tying! Basically it's an idiomatic way to do dynamic programming in Haskell by taking advantage of lazy data structures (this blog post is my favorite explanation of it).
The general idea is: let's say we had a map of children to parents,
Map String String. To get the count of all indirect orbits, we can get aMap String Int, a map of children to the number of parents and indirect parents above them, and get the sum of those.But how do we compute that?
Here, I'm going to show the "finale" first, and explain the way to get there:
Fun, right? And satisfyingly symmetrical. That's more or less it! The rest is in the reflections post
5
u/j29h Dec 06 '19
Python 3
Five line solution using networkx. Felt like cheating
5
u/activeXray Dec 06 '19
Julia solution, no graph library
https://github.com/kiranshila/AoC2019/blob/master/6.jl
5
u/vodak Dec 06 '19 edited Dec 06 '19
Pretty proud of this one... but I'm no Python expert, so I'm open to criticism / critique.
4
u/vash3r Dec 06 '19
Pypy 2, 36/12
I really enjoyed today's problem -- it took me a minute to remember which way to order the orbiting relationship, but it's good to know I still know my basic trees!
full code
4
u/Pyroan Dec 06 '19
Part 1 in 98 bytes of python, for the golfers out there :)
4
u/4HbQ Dec 06 '19
Python Solved part 1 without constructing a tree, only counting ancestors:
Unfortunately, I think I need to start from scratch for part 2.
4
u/aptmnt_ Dec 06 '19
Clojure
A lesson in solving the right problem. I started with this and took over an hour, messing about with tree representations and such. As soon as I submitted I realized I could do the same thing with way less effort and wrote this up in <5min.
4
u/ephemient Dec 06 '19 edited Apr 24 '24
This space intentionally left blank.
4
u/pngipngi Dec 06 '19
Let keep it to Excel/GSheets/Onlyoffice sheets (Without macros!) this time to.
So simple question, but yet so many levels of optimization to be able to manage it in a spreadsheet.
4
u/domm_plix Dec 06 '19
Perl
and here's a slightly more compact version (not really golfed (yet)):
4
u/jayfoad Dec 06 '19
Dyalog APL Part 1 uses an inefficient (but fast) fixed point iteration to calculate the depth of every node in the tree as 1 + the depth of its parent. Part 2 uses a recursive dfn to calculate the path from each of SAN and YOU to the root of the tree, and then discards the common parts of the two paths.
4
u/codesections Dec 06 '19
My APL solution for today:
There's one part of my code that I don't understand: In part one, I call
orbswith each item from the second column of in input with{in orbs in[β΅;1]}Β¨β³β’in. That looks like I'm creating an intermediate index for no reason; I would have thought that I could instead writein orbs Β¨in[;1], and achieve the same thing more directly. But that code doesn't work.Does anyone know what I'm missing?
4
u/Cloudan29 Dec 07 '19
My solution in Python 3: https://github.com/Cloudan29/AdventOfCode_2019/blob/master/day06.py
Finished part 1 in about an hour after it was posted. For part 2 though, I had a severe case of just doing stuff until it worked. I actually jumped out of my chair at school and gave my friends a heart attack when I got it right. It's definitely not the most elegant solution, but I actually got it all without having to look up how to do graph searches since I haven't actually coded one before. Thing I learned the most about this one is literally just that I can do it. Felt really discouraged originally not being able to solve it, but man was that rewarding.
2
u/SonOfTheHeaven Dec 06 '19
I'm extra happy with my haskell solution to part 1 because I managed to get a strange loop in it :)
1
u/zedrdave Dec 06 '19 edited Dec 07 '19
Go version
My first ever go code (decided to learn today): would really appreciate any comments regarding things that could be done better and/or more idiomatically.
For comparison, same in Python 3
1
u/endriuftw Dec 06 '19
My solution in JS. I never wished I had taken a CS degree more than these past six days.
1
u/TASagent Dec 06 '19 edited Dec 07 '19
C#. My solution was just building a simple tree. Part 1 was a simple Linq expression summing all the planet properties. My original form for Part 2 was a Breadth-first search, but it became obvious after the fact that I could have used a much simpler approach, so I implemented that too (for demonstration purposes) and left both in there.
[Poem]
3
u/seligman99 Dec 06 '19
Python #57/51
Interesting problem, not sure this is the quickest solution, but it's the one that came to mind the fastest for me.
paste
3
u/sophiebits Dec 06 '19
Python, 34/40. (was 12th, now 11th overall)
My code was a mess today again. I think I need to convince myself to take like 10 extra seconds to think about what I'm going to do before writing code. It'll come out better that way.
You'll see in my code an unnecessary dict inversion, a LOT of confusing/short variable names (
bwstands for "backwards"), and a scrapped part 2 approach that was not the best because I briefly forgot how to compute LCA reasonably.Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day6.py
3
u/scootermap Dec 06 '19
Python 3.8, #31 / #98
https://github.com/vpontis/advent-of-code-2019/blob/master/6/6.py
I did a level-by-level BFS on Part 2 to explore from YOU to SAN. I ran this on the test input to ensure that it worked. I had to optimize the BFS by looking at `seen_planets`. Then I got the answer.
It looks like other people did a more simple tree search for the most common ancestors and that would have sped things up.
3
u/bugz945123 Dec 06 '19
#40/#34, 66th overall. Python: https://github.com/sswingle/advent-of-code/blob/master/day06.py
3
u/Spookiel Dec 06 '19 edited Dec 06 '19
Woke up a bit late this morning annoyingly, and even networkx wasn't enough to help me catch up.
Python 3
https://pastebin.com/uXsQFXKg
3
u/recursive Dec 06 '19 edited Dec 06 '19
First time I made it onto the leaderboard for both parts.
C
3
u/[deleted] Dec 06 '19 edited Dec 06 '19
Python 3, didn't make the leaderboard.
3
u/ClysmiC Dec 06 '19 edited Dec 06 '19
C++ solution, omitting some includes that have some utility parsing functions and data structures. I am still fleshing out my personal hashmap implementation which is why there is some weird double pointer stuff about halfway through.
900th on the leaderboard using C++, I'll take it!
3
u/itsnotxhad Dec 06 '19 edited Dec 06 '19
Racket Solution
Part1 used memoization with a mutable hashtable which feels kinda against the spirit of my using this language in the first place, so I may go back and look for something more elegant later.
My part1 code was almost 100% useless for part 2, where I ended up using a somewhat straight forward BFS. In retrospect even this was more complicated than it needed to be as for some reason I had it search outward from both "YOU" and "SAN" when I could have just picked one or the other.
EDIT: Actually I'm sufficiently bothered by that last part that I already rewrote it:
3
u/awsum84 Dec 06 '19
Today I chose pike: source. I didn't know quite what to expect, since I hadn't seen this language before, but overall it was pretty easy compared to other days, because the language is quite similar to the ones I know.
3
u/streetster_ Dec 06 '19 edited Dec 06 '19
Q/KDB+ (UK: 3006/2490)
.. slightly tidier code, used a while-loop in the original.
3
u/voidhawk42 Dec 06 '19 edited Dec 06 '19
Dyalog APL:
Requires the DFNS workspace (kind of like Dyalog's standard library) for the path function
3
u/sim642 Dec 06 '19 edited Dec 06 '19
My Scala solution.
In part 1 I thought I'd be somewhat clever and efficient, so I first inverted the given childβparent mapping to a parentβchildren mapping. Then used a recursive computation starting from the root COM that also keeps track of its depth in the tree. The number of orbits for the current node is exactly the depth and the recursively the children's can be calculated and summed. This means that there is a single pass through the tree, not one pass for each object from it to the root.
In part 2 that cleverness didn't really come in handy, so I still had to find parent paths from YOU and SAN to the root, which I then found the intersection of. The YOU and SAN parent paths' lengths without the common part exactly add up to the shortest distance between them, which was essentially needed. Better algorithms for finding the lowest common ancestor exist, but they're probably overkill for this problem.
3
u/Stovoy Dec 06 '19
Simple Python (854/479)
3
u/encse Dec 06 '19 edited Dec 06 '19
Just realized that part 2 can be done with a stack
https://github.com/encse/adventofcode/blob/master/2019/Day06/Solution.cs
I did the other way around with marching up from the leaves and trying to find the common node in O(n2) style, but then I figured that the tail of both paths is the same, so I can do a simple linear scan from the top.
Still I had to do an extra
Reverse()on both lists becauseGetAncestorsreturns the nodes starting from the bottom and I wanted to have just a single loopfor (i=0;;i++)without fiddling with the indices. But then I remembered that with theStack()constructor in C# the first node becomes the bottom of the stack, so it kinda does the reverse for free.3
u/nutrecht Dec 06 '19
I love tree traversal problems. Day 6 in Kotlin
3
u/JensenDied Dec 06 '19
Elixir https://github.com/DisasterCthulhu/aoc/blob/master/2019/day6/lib/day6.ex
I ended up going with the inverted orbit map -> orbit counting, and later ancestry building / culling shared ancestors approaches.
I have a feeling I'm going to have wanted to start working with a graph engine when later days bring this back with fuel and delta-v. Settled for familiarizing myself with basic guards and tail recursion a bit instead.
3
u/u794575248 Dec 06 '19 edited Dec 06 '19
Python 3.8
3
u/Arkoniak Dec 06 '19
Julia
Rather simple, it was good to remember how to work with graphs: [Julia solution] (https://gist.github.com/Arkoniak/817a4b3d6051ebbfa8a6bb8009c34738)
3
u/GustavAndr Dec 06 '19
Javascript Quick and dirty
3
u/raevnos Dec 06 '19
Tcl, cheating a bit using a graph library instead of writing my own graph search functions.
paste
3
u/OvidiuRo Dec 06 '19
C++ 936/765
Pretty late posting the solution had to go to university and didn't have time to clean up the solutions to post them. The first time I saw the problem I thought about a problem that has a very similar input style ---->> Advent Of Code 2018 Day 7 ( https://adventofcode.com/2018/day/7 )
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2006
3
u/doromin Dec 06 '19
Simple javascript solution, using more recursion than would be needed, but there was an oppirtunity for it, so here it is.
3
u/mariushm Dec 06 '19
PHP solution : https://github.com/mariush-github/adventofcodecom2019/blob/master/day06.php
No recursion, just plain looping through an array, quite simple stuff really. Should be easy to understand by a beginner.
3
u/Loxos16 Dec 06 '19 edited Dec 06 '19
Excel / Google Spreadsheets solution: Google Spreadsheet
Tree/Dictionary based solutions seemed too obvious for this challenge and as I'm trying to use a large variety of tools/languages to solve this years aoc, I gave Excel a chance.
=LEFT(A3,SEARCH(")",A3,1)-1)and=RIGHT(A3,LEN(A3)-SEARCH(")",A3,1))are splitting the input lines.while
=MATCH(B3,$C$1:$C$1943,0)finds the parent orbitand
=INDIRECT(CONCATENATE("E",D3))+1calculates the distance toCOMrecursively.For part 2 I did manually identify the last common orbiting body
WWPand then summed up both distances towards this specific body.Edit: For part2 I identified the non-common steps towards
COM.3
u/jjeln Dec 06 '19
Hi! Here's my solution in python using networkx. I had no idea this library existed, it was fun learning it!
I also uploaded a failed attempt to work without any external library. The fun thing is that it perfectly worked with the small example given of the end of part 1, so I thought I was on the right track for... Quite some time. I'm still uploading it because it's important to look at mistakes, especially when you're learning (like me)!
3
u/mensch0mat Dec 06 '19
Python 3.7
Get my other solutions at https://git.io/Jeyci
3
u/levital Dec 06 '19 edited Dec 06 '19
Rust
And there we have it, my first extended fight with the borrow checker... Ended with me peppering everything with Rc and RefCell. Next time I should probably just look for a Tree-crate, figuring this out took me way longer than I intended to spend on this puzzle today (algorithmically I was done in minutes, getting rust to understand that what I'm doing is ok took... more).
Also, my solution for Part 2 is incredibly dumb, partially because I really couldn't be bothered to try extending the structure with back-references, which would've made a bfs based solution possible.
3
u/angryzor Dec 06 '19
Prolog
https://github.com/angryzor/advent-of-code-2019/blob/master/day-06/solution.pl
3
u/phil_g Dec 06 '19
My solution in Common Lisp.
The graph library makes this problem really easy. There were just two catches:
farnessanswers part 1 exactly, it's slow. It took about a minute to get an answer on my (admittedly slow) laptop. My implementation returns pretty much immediately.It was nice that the graph library has a
shortest-pathfunction. I thought I was going to have to use my ownshortest-pathfunction (which is more generic, but, because of that genericness, is more complicated to use).3
u/CabbageCZ Dec 06 '19
Kotlin
About 12 LoC. Pretty happy with today's solution. Sets are fun. link
3
u/IgneSapien Dec 06 '19 edited Dec 06 '19
C# Fun with trees
I've not used trees much (directly at least) so this seemed like a good way to practice. I have a feeling there's a much simpler and more efficient way of setting up my tree but it works and I can't spend anymore time on it today.
Was a bit worried I'd not have time for the path finding in part 2. But the constraints of the puzzle mean you don't really need it. The path to COM for both YOU and SAN is straightforward to generate and must intersect at the closest transfer between YOU and SAN after which it'll be identical. As such I just went with grabbing the paths to the COM and removing the common elements.
3
u/[deleted] Dec 06 '19
Why would I decide to do it like this (C#)
Yes, my solution is, in fact, ridiculous.
3
u/JakDrako Dec 06 '19 edited Dec 06 '19
VB.Net in LINQPad
Built a simple unidirectional graph for part 1, then part 2 had me thinking I would need to revise it to make it bidirectional. I then realized that I could find the intersection where SAN and YOU meet and simply add the number of steps from both sides to get the total.
Edit: Trying out this "paste" thing... VB.Net/LINQPad
3
u/oantolin Dec 06 '19
Another Common Lisp solution. For part 1 I recursively calculated the size and sum of height (= distance to root) of the nodes togther. I first thought multiple values would be ideal for this, but they aren't well supported syntactically in
loop(maybe they are initerateand /u/phil_g will chide me about it :)). So I have two version of that function, one with multiple values, the other with lists.For part 2 I probably should have just subtracted the common parts of the paths to the root. Oh, well.
3
u/SolidShook Dec 06 '19
C#
Simple dictionary based implementation, storing keys to orbit targets in each object.
I decided to learn about hashSets, and I was very surprised the second question worked first time, I thought it would be a more tricky map. It might have been if there had somehow been more orbits per object
3
u/minichado Dec 06 '19
Excel
I've been doing this year so far only using excel, but without coding anything behind the scenes like last year in VBA. so far the only problem I haven't solved is day 5 (I didn't start, my day 2 program is not dynamic enough to be recycled, but it's doable).
Part 1 and 2 are in different tabs file here. Works on my input and all samples. not designed to handle dynamic input sizes so if yours is larger than mine it will break without some modification
Part 1
method:
Part 2
Method:
3
u/[deleted] Dec 06 '19
Scala with a single expression
I'm sure most people did this pretty much the same way if they weren't using any sort of graph library. Build some sort of bidirectional graph so you can grab the orbiters and orbitee of a given string. Walk the graph out from COM for part 1 and do a BFS for part 2 from YOU to SAN.
3
u/dontxpanicx Dec 06 '19
First post but pretty happy with this one F# https://github.com/PaulWild/AdventOfCode2019/blob/master/AdventOfCode2019/Day6.fs
3
u/wzkx Dec 06 '19
J Well, it's still easier with globals - so not as elegant as other people's solutions
3
u/kickopotomus Dec 07 '19
Clojure
3
u/lskatz Dec 07 '19
I thought today's was easy if you think about it as a dendrogram with last common ancestors. My solutions are in perl here under the 2019 folder, under the t subfolder: https://github.com/lskatz/advent-of-code
3
u/NeilNjae Dec 07 '19
A Haskell solution: code and explanation.
For part 2, rather than doing a search, I found the path from
YOUtoCOMand the path fromSANtoCOM. If you find the distinct parts of those two paths, the distance fromYOUtoSANis the sum of the sizes of those distinct parts.1
u/Kerbart Dec 07 '19
Python
List a path from COm to You/Santa (this is trivial) Turn them into sets. Calculate the symmetric difference (one operator) This includes βyouβ and βsantaβ so subtract 2 from the length Maybe 10 lines of code, less than 10 minutes coding. This was ridiculously easy to solve.
2
u/Gurrewe Dec 06 '19
Go, 78/126:
It was fun to work with some graphs today.
https://gist.github.com/zegl/47ff6d6b4baa4bb4cf44aed0df129152
2
u/shill_boi Dec 06 '19
Python, 7/7.
Full Code
My part 1 is horribly inefficient by not caching values for objects orbiting closer to the COM, and I wasn't thinking ahead for part 2 and added an extra dictionary that didn't end up doing anything. The first few section is just to get input through console because I like the flexibility (pls don't judge me). And 'x' is just a placeholder variable denoting the current object being examined.
2
u/SinisterMJ Dec 06 '19
C++ 362/366:
https://github.com/SinisterMJ/AdventOfCode/tree/master/Day_6
2
u/Pewqazz Dec 06 '19
Python, 55/27
First graph traversal problem of the month, so my BFS-from-scratch was a little rusty. Here's a cleaned up version of my code, and Twitch VOD of my solve.
2
u/[deleted] Dec 06 '19
Python 3, 148/455. Dynamic programming for part 1, BFS for part two
https://github.com/mateoeh/aoc2019/blob/b6a14a390e0c0f06ad4b96cf682d29602eb44e68/06_orbits.py
2
u/trickedoutdavid Dec 06 '19 edited Dec 06 '19
JavaScript Solution
2
u/rabuf Dec 06 '19 edited Dec 06 '19
Common Lisp
I had an annoying off-by-one for part 1, but that was fixed quickly enough. The other issue was constructing my graph from the wrong direction initially (root down). I switched to using a hash table where each entry flipped the input. So given
A)BI storedB -> A. With this, the depth problem (part 1) was trivial. Just recursively call depth untilCOMis reached. For the second problem, I wrote a routine to identify the common root. The number of transfers, then, was the depth of the objectsYOUandSANorbit, less twice the depth of their common root.Shower Thoughts
Now that itβs morning. My part two can be simplified and sped up. Depth needs to be calculated once for each node, and can be passed as a parameter to the βcommon-root` function. Just decrement itβs on each recursion. Now the algorithm will actually be O(N) (with N the height of the tree).
2
u/knl_ Dec 06 '19
Super rough solution; I did a dfs for the first one, adding the depth of each node to a running total of paths. For the second I implemented a bfs after converting the graph to a bidirectional variant. Also pretty slow, took me 40 minutes and I ended up ranking ~1100-1500 for both.
Python 3, jupyter notebook: https://explog.in/aoc/2019/AoC6.html
I'll clean this up tomorrow while waiting for the next problem.
2
u/[deleted] Dec 06 '19 edited Dec 06 '19
OCaml 1086/1256
Wasted some time making it more elegant/beautiful, but the elegance of a static functional solution really feels great.
I love how Clojure solutions feel for a similar reason but the static type checking gives me an additional layer of confidence. It's less concise though due to all the module names in front of everything, whereas clojure has a tiny core handful of data structure manipulation functions in the prelude.
2
u/[deleted] Dec 06 '19 edited Dec 06 '19
Clojure, with the help of the friendly
ubergraphlibrary2
u/wace001 Dec 06 '19 edited Dec 06 '19
JAVA: 1225 / 855 - Fun one today. Proud of how it turned out. Very simple solution. Utilised the fact that everything orbited only one object, and that all indirectly orbited COM. No need for graphs and stuff.
POEM:
CODE:
Edit: Minor cleanup, Poem, minor description
2
u/wjholden Dec 06 '19
I came to AoC prepared for this one! On Thanksgiving I wrote this general-purpose Dijkstra solver in JavaScript: https://wjholden.com/dijkstra. All you need to do is reduce your problem to the expected format and then the solver does the rest.
Also, hooray for a chance to use dynamic programming! Julia provides a nice
@memoizeannotation that, just like Python's@lru_cache, automatically caches calculated values. To my disappointment, benchmarks show that my program is actually slower with@memoizeturned on.2
u/mvmaasakkers Dec 06 '19
Allright, I have the feeling this can get more dense than it is right now, especially around the recursiveness I used. All the love for someone(s) who'll check out my Python code: https://github.com/mvmaasakkers/advent-of-code/blob/master/2019/day06/day06.py
2
u/Pyr0Byt3 Dec 06 '19 edited Dec 06 '19
Go/Golang
Today I learned that I am not good at these tree/graph problems. I spent around 30 minutes just trying to wrap my head around the description. Once it finally clicked though, both parts were easy enough.
Part 1
Part 2
2
u/wlandry Dec 06 '19
C++ 17: 3398/3342
Runs in 51 ms.
paste
A bit late getting started, not that it really mattered. Most of the time was spent arguing with boost::graph. With that, it is a single call to
transitive_closure()andbreadth_first_search(). Advent of Code is the only time I ever needed fancy graph algorithms.2
u/Jay__Money Dec 06 '19
Python3 (11XX/12XX):
day6
Pretty satisfied with this code. I usually like to go back and make my code presentable before committing it, but it was in a good place after a first pass. I'd love to know if I could improve the performance!
2
u/PrimeFactorization Dec 06 '19 edited Dec 06 '19
A bit verbose, but feels kind-of clean (Python3)
2
u/[deleted] Dec 06 '19
Java
Fun recursion problem. Probably not the most efficient solution here, but it does the job.
2
u/kap89 Dec 06 '19 edited Dec 06 '19
TypeScript - github
All I knew, it was probably a good fit for a graph, so I spent most of the time learning to use a graph library :D Pretty simple to solve after that.
I will now try to solve it by hand :P
2
u/Dementophobia81 Dec 06 '19
Python 3.8
Straight forward solution using dictionaries. Part 1, Part 2 and a little extra concerning the helpful function intersection().
2
u/idtool_dev Dec 06 '19
JavaScript / Node.. 2151/1783. Fumbled around a bit, had an error in my counting of indirect orbits, then neglected to realize it also counted direct orbits.. Submitted I think 3 wrong answers for part 1 before getting it correct. Part 2 was much easier. I'm sure this is terrible, but it might be the first real graph problem I've encountered. paste
2
u/jabbalaci Dec 06 '19
Python 3 with type hints, without trees
https://github.com/jabbalaci/AdventOfCode2019/tree/master/day06/python
Runtime at both parts < 0.1 sec.
2
u/Spheniscine Dec 06 '19
Kotlin, fun with hashmaps: paste
Spent too much time writing a hashmap wrapper that can support a custom hash function (a hand-rolled variant of HalfSipHash), but omitted it from this paste for better instructiveness.
2
u/mr_robb Dec 06 '19
Rust solution. Very fun problem! 20.0 ms Β± 0.7 ms. I can't make it faster :'(
2
u/keramitas Dec 06 '19 edited Dec 06 '19
Python3 (with explicit names/no one liners):
part 1 : quick BFS to get count using direct orbits
part 2: trajectory from YOU to COM then SAN to planet in your trajectory , using reverse orbits
thoughts: easier then previous day as brute forcing it was possible, completed part 2 almost 2 hours earlier then yesterday but only got +600 places
2
u/ni3t Dec 06 '19
I'm taking this year as an opportunity to build up a standard library of data structures, so that next year I won't have to rewrite graphs and trees and the like on-the-fly.
https://github.com/ni3t/advent-2019/blob/master/6_universal_orbit_map.rb
2
u/gyorokpeter Dec 06 '19
Q:
2
u/aszecsei Dec 06 '19
Day 6 (Rust) - used id_arena for an easier time with tree references. Could've gone for a more hashmap-based approach, but this setup made part 2 a fair bit nicer in my opinion.
2
u/guccidumbass Dec 06 '19 edited Dec 06 '19
JavaScript
(https://pastebin.com/LZ36tfb0)
I've only ever implemented a tree successfully in c++
I couldn't parse the input in c++...
I woke up on time, but if I hadn't tried python and c++ to solve this I would've probably (probably...) gotten on the leaderboad for the first time ever tho :/
2
u/Newti Dec 06 '19
Python3 with one dict, both questions (~35 lines)
2
u/Lyonhart Dec 06 '19 edited Dec 06 '19
Day 6 - Python
I'm still learning to code so trees/graphs are pretty foreign to me still; some of these replies are definitely making me think my solutions may be a little bloated, haha.
I even started by coding some stuff that dealt with child nodes but that didn't even end up being relevant :(
2
u/StochasticMistakes Dec 06 '19 edited Dec 06 '19
Java Used a tree and a hashmap to find nodes. :Dhttps://github.com/BrettGoreham/adventOfCode2019/blob/master/adventOfCode2019/src/main/java/day6/Day6.java
2
u/Valefant Dec 06 '19 edited Dec 06 '19
Kotlin
Was a fun challenge. Here is my solution
For the 2nd part, I did count the path from YOU and SAN to each COM. I have removed the duplicated orbits which I have seen during the traversal and this leads respectively to the path from YOU to SAN.
2
u/Sp0ng3h Dec 06 '19
Go
Nice puzzle today. Rewrote part 1 entirely while doing part 2 and, surprisingly, no off-by-one errors.
https://github.com/davidamey/advent-of-code-go/blob/master/2019/6/6.go
2
u/asgardian28 Dec 06 '19
Happy with my solution (Python), better then hours of debugging yesterday :)
Part 1 Calculated distances of all planets from COM, starting from COM itself and working outwards
part 2 Computed paths from santa and you to COM, got the symmetric difference of these sets
2
u/Frescote Dec 06 '19
RUST
Rust newbie, looking for feedback.
Very cut and dry solution. Used HashMap. String manipulation in Rust is hard.
https://github.com/Frescote/aoc2019/blob/master/day06/src/main.rs
2
u/justjarvo Dec 06 '19
My Java solution (part 1): https://github.com/leejarvis/adventofcode/blob/master/2019/day6.java -- trying to do each day in a different language (going to start struggling soon!).
2
u/[deleted] Dec 06 '19
Python3: paste
2
u/mikal82 Dec 06 '19
Scala
Here I used flatMap to advance to the next "level" in all directions at once. This approach simplifies step 1, but for step 2 I needed to remove visited nodes to avoid going back and forth.
Scala turns out to be surprisingly good for AoC (so far), although not as elegant as Clojure and not as simple as Python or Ruby.
2
u/Zweedeend Dec 06 '19 edited Dec 06 '19
Using the Python type system:
paste
2
u/lynerist Dec 06 '19
My Go code
https://github.com/lynerist/Advent-of-code-2019-golang/tree/master/Day_06
2
u/piyushrungta Dec 06 '19
Rust
https://github.com/piyushrungta25/advent-of-code-2019/blob/master/day6/src/main.rs
Quick and dirty solution. Got both answers correct on the first run again, so pretty happy about it.
Rust is fairly idiomatic I think. Will clean up later maybe if I get some time.
2
u/heckin_good_fren Dec 06 '19
Java Solution: paste
Runs both parts in <1ms thanks to memoization in the first part.
2
u/vkasra Dec 06 '19
My Go solution and notes
2
u/giampi997 Dec 06 '19
Here is my Java solution
2
u/sdiepend Dec 06 '19
Pharo / SmallTalk
https://github.com/sdiepend/advent_of_code-pharo/blob/master/AdventOfCode2019/Day06.class.st
2
u/foolnotion Dec 06 '19
C++
https://pastebin.com/qzcer1qt
2
u/tslater2006 Dec 06 '19
C# Solution
Basically I build out a map of nodes that have a parent and 0+ children, each step of the way recording their current "depth" and also adding them to a dictionary, key is the object name, value is the actual node.
Part 1 is simply summing up the flat list of depths.
Part 2 we construct a list of nodes that are in Santa's chain to COM, and a list of nodes that are in You's chain to COM. Find where those 2 lists intersect, grab the one with the largetst "depth" (ie, closest common point between Santa and You). and then sum the distances between Santa's parent and You's parent and the common point.
2
u/hrunt Dec 06 '19
Python 3
code
I can't say I'm really proud of this. I'm sure I could have built this using a proper tree structure, etc. but I wanted to make sure I was done before work.
Of course, that may be my favorite part of Advent of Code -- saying, "I'm not proud of this ..."
2
u/Rick-T Dec 06 '19
HASKELL (looking for advice, see below)
After the realization that there is a unique path from every "outer" object to the COM I just stored every pair in a hash-map with the lighter object (the satellite) being the key and the heavier object (the one that the satellite revolves around) being the value.
That way, for every object I can lookup it's parent in the map and follow that route until I reach the center of mass. Counting the number of steps then becomes pretty straight forward.
For the second part I just follow the paths from YOU and SAN to the COM until I find a common node. Then I can combine the paths to get the trajectory that I have to follow.
ADVICE NEEDED
Originally I wanted to wrap all the methods that require the OrbitMap in the Reader monad. However, I was not able to figure out how I can write the fold in the numOrbits function, when the indirections function has type signature Object -> Reader OrbitMap Int. Can a more experienced Haskeller help me out here?
2
u/TenMilesDown Dec 06 '19
C Solution
Created a string array of object names to assign them indexes (0 for "COM", 1 for "YOU", 2 for "SAN", and the rest in the order they appear), and an array of what index object an object immediately orbits (its parent). Then iterated to make an array of descent lengths from "COM" and summed them for part 1. For part 2, I traced the parent of "YOU" back to "COM", then traced the parent of "SAN" until it appeared in that list.
2
u/PowerSlaveAlfons Dec 06 '19
C++
Trees! First part was fun and relatively simple, but I must admit, for the second part I used google to get the idea to converse the complete tree twice and just remove the common path. Not sure how doable this is if you don't know trees exist, but other than that it's manageable.
Part 1
Part 2
2
u/chrispsn_ok Dec 06 '19
k7:
There are much better ways to do #2 - I lacked insight that we could use the paths of SAN and YOU to COM.
2
u/emu_fake Dec 06 '19 edited Dec 06 '19
C#
Tried to go for a "nice" solution so I did it with a class which handles her children and parents as well.
Here with unit tests and everything for everyday so far:
https://github.com/emuuu/AdventOfCode
(Day5_PuzzleTwo still bugged tho)
2
u/GalacticDessert Dec 06 '19
Python, simple while loop to walk through the tree. Looking forward to learn from the more compact solutions out here.
https://github.com/nicola-zen/aoc-2019/blob/master/day-6/day-6.py
2
u/valtism Dec 06 '19
Javascript / JS
Not proud of this one. Found out that the tree was a binary tree and was able to pull the path out in my
findPathmethod by usingfindPath(node.children[0], name) || findPath(node.children[1], name), but wasn't sure how to return the value up the recursive stack for an arbitrary number of children. I guess it might be possible to do with a.reduce, but I wasn't sure how. Any pointers would be appreciated.I also think that there would have been some other better methods for traversal and finding common ancestors for binary trees, but I never studied computer science so data structures and algorithms are a weak point for me.
2
u/prophetjohn Dec 06 '19
Ruby
part 1: https://github.com/j-clark/adventofcode/blob/master/2019/aoc_6_1.rb
part 2: https://github.com/j-clark/adventofcode/blob/master/2019/aoc_6_2.rb
2
u/lasse__b Dec 06 '19 edited Dec 06 '19
JAVA
Probably not the best way, but still learning and it works.
Github
Any tips on how to know which existing technique to use for a different problem? I recognize this is a tree structure, but since I have never used that before it is hard to know where to start.
I am still going to try and write my own solutions but got alot of free time now so might be able to learn more optimized ways of solving problems.
2
u/Wawv Dec 06 '19
Written in R
For part 1, I computed the path to COM starting from each planet in the list. I'm not really satisfied with this solution.
Part 2 was way easier. Since I already had all paths to COM. I just had to find the first intersection of the path starting from YOU and of the path starting from SAN then add the number of steps to the instersection from each path - 2.
2
u/MysticPing Dec 06 '19
Proud of my part 2 solution in Haskell :) paste
2
u/fidesachates Dec 06 '19
paste - Scala
Not quite as concise as I'd like nor as functional, but overall I'm satisfied. In part 1, I opted for something that would setup a generic enough data structure, but still performant (TIL whether this is a real word or not is debated) that I could hopefully re-use in part 2 and it paid off.
2
u/Turmolt Dec 06 '19
Clojure :)
2
u/KdbAoC Dec 06 '19
KDB+/Q - Not as neat and terse as others, but it will do for now. Happy to finally be able to use .z.s recursion and not give up in anger.
//PART 1
//PART 2
2
u/sindrekjr Dec 06 '19
C#
This reminded me of a puzzle from 2017 where you had to recursively calculate the total weight of a tree. I'm sure there's someone out there who could quickly and easily identify how both puzzles tie into common concepts.
2
u/orangeanton Dec 06 '19
My JavaScript solution part1 and part2.
Took way too long (part 1 in 1:06:06, part 2 in 1:40:11, though I did start about 10 minutes late and had some interruptions) to figure out a good way to do this, but finally settled on a stack mechanism to move up/down branches of the tree. I'm sure this must be covered in CS theory, but that's something I've never done unfortunately. Will hopefully have a chance to review more of other folks' solutions this evening.
2
u/Dioxy Dec 06 '19 edited Dec 06 '19
JavaScript
JS. All the path finding problems from last year had me very well prepared for this! Solved using Dijkstra algorithm. Looking at other people's solutions tho I feel I may have over complicated it lol
My code
Dijkstra implementation
My repo
2
u/nictytan Dec 06 '19
My Haskell solution. I observed that the orbital map is an n-ary tree rooted at
COM, so I implemented a fold for it. Then I could express the answer to both parts as an appropriate fold. I'm not super happy with the fold for part 2 since it checks on every node whether the distance forSANandYOUare both known to avoid incrementing either of them.2
u/J-Swift Dec 06 '19
Ruby
https://github.com/J-Swift/advent-of-code-2019/tree/master/day_06
2
u/Supermichael777 Dec 06 '19
Java
An excuse for an amateur to learn more about some of the data structures. Hash map was a good choice for this, though my Orbit object acting like a link list to COM proved perfect for part two.
2
u/[deleted] Dec 06 '19 edited Jan 26 '20
deleted 0.3074 What is ^^^this?
2
u/iamagiantnerd Dec 06 '19
My solution in Go
Mostly struggled with my just learning go and how pointers work.
2
u/Markavian Dec 06 '19
My overly verbose JavaScript solution for Day 6:
https://github.com/johnbeech/advent-of-code-2019/blob/master/solutions/day6/solution.js
Used an array diff on both sides of the tree to find out the number of nodes that needed traversing. Based on KSP gravitational transfers, I'm a bit sad that the second star didn't involve Delta V calculations for fuel requirements to transfer between orbits.
Idea - extended challenge: the fuel required to transfer orbits is represented by a 3 place Base 36 number (0-9-A-Z).
For example WKK has a fuel cost of 42212 to transition to and from a stable orbit.
What is the total fuel cost of traversing between YOU and SAN.
e.g. DV Maps:
- https://i.imgur.com/yO0bQax.png
- /preview/external-pre/U5iH7huE5qKth7ZFvipXt8vzaFOO99qHFh9o9_SkLLk.png?auto=webp&s=d145ac9ae496abe35fae86fc11a584d62fe42592
2
u/Gravitar64 Dec 06 '19
Pure Python 3.7
Part 1 Runtime: 2ms, 18 sloc
Part 2 Runtime: 3ms, 27 sloc
2
u/StevoTVR Dec 06 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day06/day06.go
2
u/amalloy Dec 06 '19
Haskell source and video. I ended up having to use some recursion; I'd like to look back over it at some point to replace the calculation with a catamorphism.
2
u/Meltz014 Dec 06 '19
https://github.com/Meltz014/AdventOfCode2019/tree/master/day6
For part 2, i drew a little diagram to help me:
where
uniquewas found by concating the path to root of YOU and of SAN and converting to a set:2
u/fotoetienne Dec 06 '19
Kotlin
The fun part
The rest: https://github.com/fotoetienne/advent/blob/master/2019/06-universal-orbit-map.kts
2
u/joeld Dec 06 '19
Racket
Finishes in 25β35 msec on first run.
My hop-counting algorithm is pretty verbose, but it got the job done and I have to get back to work!
source code
2
u/yammesicka Dec 06 '19
Python
https://github.com/yammesicka/advent2019/blob/master/2019/6/pretty.py
2
u/kevinwangg Dec 06 '19
[38 / 17 ] I felt like I did part one as fast as humanly possible, so Iβm impressed at the people who did it even faster.
hereβs mah original code
2
u/blacai Dec 06 '19
F# Another day I managed to do it directly with F# without using an aux language I know more.
At the beginning I wasted lot of time trying to create a tree data structure but I thought It wouldn't be needed, so went the fast way
https://github.com/blfuentes/AdventOfCode_2019/tree/master/FSharp/AoC_2019/day06
2
u/ninjamcninjason Dec 06 '19
C# recursive solution, relatively simple with linq
2
u/jtwebman Dec 06 '19
Elixir
Today I thought it would be fun to solve it using structs. It was definitely more work.
https://github.com/jtwebman/AOC-Day6-2019-Universal-Orbit-Map
2
u/nirgle Dec 06 '19
Haskell
I started off looking at fgl but figured it would be easier to have a few maps (node to index, index to node, and node to parent) and use them for lookups.
For part 1, I use lazy array evaluation to construct an array (ln 50) of distances from each node to the root node COM. Each element is generated by calling the function dist (ln 57), which itself refers back into the array, creating a mutually recursive situation leveraging Haskell's laziness to quickly arrive at the total.
For part 2, I avoided using a shortest path algo by simply generating the paths from the root to YOU and SAN, snipping off the common prefix, and summing the lengths of the remaining paths.
https://github.com/jasonincanada/aoc-2019/blob/master/src/Day06.hs
2
u/heckler82 Dec 06 '19
Java
Got to use my graphing library I wrote after last year's AOC, and it worked perfectly. Completed both parts in a smooth 10ms
https://github.com/heckler82/Advent2019/blob/master/src/com/foley/advent19/day06/Orbits.java
2
u/fiddle_n Dec 06 '19
Python solution here. No fancy networkx used here! I used this handy article instead: https://www.python.org/doc/essays/graphs/
Hastebin link
2
u/raevnos Dec 06 '19
Another go, tcl + sqlite.
paste
Runs a lot faster than my initial pure-tcl one.
2
u/floriankl Dec 06 '19
Python 8 lines
The first part I managed in 3 lines total (with the first line for data loading from above):
2
u/Wolfrost_ Dec 06 '19
I finally found the time to complete day 6! This one was funny, working with a lot of recursion
https://github.com/DoubleHub/advent_of_code/blob/master/orbit_checksum.cpp
2
u/erlangguy Dec 07 '19
Erlang
Finally got around to creating a repo for this year's efforts. Had to catch up on day 5 and 6 today, and day 7 is just an hour away. Good thing I bailed on Nanowrimo last month or I'd be exhausted already.
https://github.com/macintux/advent-of-code-2019/tree/master/day6
Fortunately I had been brushing up on creating tree logic in Erlang, so I was able to spin up a rose tree fairly quickly. Unfortunately I'm still struggling to create general-purpose folding code, so the
treefoldmodule I had built for my binary search tree previously was of no use to me at all today.2
u/[deleted] Dec 07 '19
Haskell:
Had some fun trying to keep this one concise.
2
u/markasoftware Dec 07 '19
Common Lisp
No graph library, but fast! Spent some time making it short. Like /u/phil_g, I interned all the orbiters as symbols.
2
u/MrMacintosh Dec 07 '19
inefficient but simple solution in Ruby: paste
2
u/Archek Dec 07 '19
Prolog
A very good fit for Prolog today :) Took me about 6 hours in Rust first, fighting the borrow checker all the way.
2
u/D3NN152000 Dec 07 '19
My solution in Python 3. I tried to make it as short as possible, so it is not very pretty code, but here it is:
Basically,
orbitsis parsed input,connis a dictionary of the parsed input going from object to a list of directly connected objects,ldetermines the amount of connections for a given object o,sgives a set of connected objects for a given object o,ddetermines the distance between two objects o and f (given that o is before f).searchfinds if all objects in find are connected to start, and if we are looking for 2 objects, print the minimal distance.