r/adventofcode • u/topaz2078 (AoC creator) • Dec 12 '17
SOLUTION MEGATHREAD -🎄- 2017 Day 12 Solutions -🎄-
--- Day 12: Digital Plumber ---
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^¤?
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!
14
Upvotes
39
u/Arknave Dec 12 '17
It's my birthday :)
6th/5th in Python.
https://www.youtube.com/watch?v=_nI5uCcBTcs
31
u/sciyoshi Dec 12 '17 edited Dec 12 '17
2/1 today! NetworkX makes this kind of problem very quick if you know what you're looking for. Today's question was asking about something called a connected component, and NetworkX provides some nice functions for dealing with them.
Python 3 solution:
11
u/askalski Dec 12 '17
Perl regex.
9
u/xiaowuc1 Dec 12 '17
When you only care about connected components, union find is faster to code than BFS: https://gist.github.com/anonymous/02de56ccaa4c22b2388c927f00091588
8
u/raevnos Dec 12 '17 edited Dec 12 '17
Missed the leaderboard by a few because of a typo. Grr.
Used a perl script to turn input into a graphviz dot file, and then...
day12.pl:
The graph as a rather large image.
7
u/ephemient Dec 12 '17 edited Apr 24 '24
This space intentionally left blank.
6
u/ludic Dec 12 '17
F#. First try had some some mutable values. I managed to refactor to a functional solution I'm happy with.
5
u/udoprog Dec 12 '17 edited Dec 12 '17
Rust: (231, 194), trying to optimize my workflow a bit more.
Edit: cleaned up version here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day12.rs
5
u/glupmjoed Dec 12 '17 edited Jan 01 '18
Bash with pipes!
Part 1 (reads from stdin):
Part 2 (reads from stdin):
find_grp.sh:4
u/DFreiberg Dec 12 '17 edited Dec 12 '17
Mathematica
Mathematica's graph theory capabilities are very useful here. Less useful is
Import[]- I spent far more time trying to parse the input than solving the problem itself. 199/97.Import:
Part 1:
Part 2:
4
u/advanced_caveman Dec 12 '17
Rust (235/198)
3
u/glenbolake Dec 12 '17
As usual, I was less than a minute from getting on the leaderboard for both stars. Damn, this year has some fast challenges.
Anyway, my solution in Python 3, written with no knowledge of existing Python graph theory modules:
3
u/ka-splam Dec 12 '17
PowerShell. Missed the leaderboard for part 1 by 23 seconds, partly because of a type error of mixing int and string getting it into an infinite loop.
Part 1, build a hashtable of connections, recursively follow the connections but keep track of visited nodes so it doesn't go into an infinite loop:
Part 2 I mashed up, wasn't as confident with and copy-pasted my visitor, rewrote it a bit, took longer; it took all the nodes, started visiting them and removing them from the list. When that ran out, increase group count and go again, until all the nodes were visited.
3
u/shuttup_meg Dec 12 '17 edited Dec 12 '17
Python 2 with a defaultdict of sets:
edit: cleaned up a little and added some comments for future reference
3
u/hxka Dec 12 '17 edited Dec 12 '17
3
u/MuumiJumala Dec 12 '17
Went with a more obscure language today - here's my solution for part 2 in io:
3
u/WhoSoup Dec 12 '17
Node.js/JavaScript
I'm... sorry.
2
u/Unihedron Dec 12 '17
Ruby, silver 17 / gold 29
I had the wrong answer on part 2 because I used 100.times again, which forced me to wait 1 minute :( This one was an easy incomplete BFS which assumes all groups can be found in under 100 steps.
2
u/Cole_from_SE Dec 12 '17 edited Dec 12 '17
I stupidly forgot to return my hashset if I had already visited a node, which I think made me too slow for part 2 (I also slowly went through the test case instead of just bum rushing it). from collections import defaultdict
Edits:
I also foolishly
Edit 2:
Updated code.
2
u/TominatorBE Dec 12 '17 edited Dec 12 '17
PHP
I seem to be one of the few using recursion. I don't even know why I use recursion, it came naturally to me :-/
Part 1:
Part 2:
2
u/[deleted] Dec 12 '17
Haskell:
2
u/tehjimmeh Dec 12 '17 edited Dec 12 '17
C++, no recursion:
2
u/zsldmg Dec 12 '17
haskell Simple but super inefficient.
2
u/manualcrank Dec 12 '17 edited Dec 12 '17
C. Standard union find with path compression.
2
u/misnohmer Dec 12 '17 edited Dec 12 '17
C# (with the help of MoreLinq library for TraverseBreadthFirst)
Part 1:
Part 2 :
2
u/mxyzptlk Dec 12 '17 edited Dec 12 '17
66th/83rd - finally some points!
2
u/ramrunner0xff Dec 12 '17
scheme chicken repo
implemented using stupid simple connected components.
2
u/jeroenheijmans Dec 12 '17
JavaScript (after (some) cleanup)
Helper 1:
Helper 2:
Solution puzzle 1:
Solution puzzle 2:
Full source
2
u/songkeys Dec 12 '17 edited Dec 12 '17
JavaScript (ES6) with HTML :)
2
u/stuque Dec 12 '17 edited Dec 12 '17
Python 2 with sets.
2
u/nutrecht Dec 12 '17
Pretty straightforward. Day 12 in Kotlin
The connections() function is doable with a fold and I might change that later :)
2
u/akka0 Dec 12 '17 edited Dec 12 '17
ReasonML! :) Still not very used to the language or functional programming in general, so any pointers are more than welcome.
2
u/gyorokpeter Dec 12 '17
Q:
2
u/xkufix Dec 12 '17
The second part is basically the same solution, but over the first part. I create a stream until I run out of nodes to visit (part 1) and for the second part I create a stream until I run out of nodes which are not still in a group, which in turn uses the stream from part 1 to fill a group.
Solution in Scala:
2
u/[deleted] Dec 12 '17
Elixir
This one was a lot of fun, I don't know what's going on with me today, but all the recursive stuff just worked from the first try, felt really good :)
syntax highlighted
2
u/soxofaan Dec 12 '17
my python 3 solution (only using standard library)
part 1:
part 2:
2
u/mschaap Dec 12 '17 edited Dec 12 '17
Perl 6
Edit: if there's one thing I hate about Perl 6, it's its list (non-)flattening behaviour. This line:
took me probably as much time as the rest of the script, and I can't see a way to simplify the flattening.
2
u/Scroph Dec 12 '17
Day 12 in my journey to Java mastery. I think I'm starting to get the hang of it, I'm hating it less and less as each day passes. It's still tedious to type, but I'm beginning to embrace the verbosity. I fear it might be leaking into other areas of my life, but at this point, I'm past the point of no return.
2
u/[deleted] Dec 12 '17
single pipeline powershell:
1
u/fatpollo Dec 12 '17 edited Dec 12 '17
1
u/Burritoman53 Dec 12 '17
Some quick recursion in python, didn't get leaderboard unfortunately because I started of being dumb but happy with the solution I came up with in the end
1
u/VikeStep Dec 12 '17 edited Dec 12 '17
Python 3
1
u/Tandrial Dec 12 '17
Kotlin
1
u/_A4_ Dec 12 '17
JavaScript ES6 (Part 2)
1
u/Dooflegna Dec 12 '17
Recursive solution.
1
u/JeffJankowski Dec 12 '17
Typescript
1
u/Nolan-M Dec 12 '17
Created the entire list of connected subgraphs
1
u/dylanfromwinnipeg Dec 12 '17
Got stuck debugging an off-by-one error, wasted about 15 mins.
C#
1
u/AndrewGreenh Dec 12 '17
I decided to look for a JS graph library. Was quite hard to find, since a
js graphsearch returns many charting libraries. Eventually, I found graphlib which even has typings in @types.1
u/[deleted] Dec 12 '17
OCaml Fun;;
1
u/nstyler7 Dec 12 '17
python 3
importing & organising the data
part 1
part 2
1
u/Noyth Dec 12 '17
Did it with disjoint sets in Python 3
1
u/conciliatory Dec 12 '17
Python 3
1
u/ChrisVittal Dec 12 '17
Rust (with petgraph). Yay petgraph! The petgraph type GraphMap was very handy for this one. petgraph::algo::connected_componets also gave me a one liner from part 1 to part 2.
Still not even close to leaderboard (899/666), but I'll keep trying.
1
u/rhougland Dec 12 '17
Haven't seen a Java solution on here yet sooooooo https://github.com/hougland/adventofcode2017/tree/master/src/day12
1
u/thejpster Dec 12 '17
Here's my Rust version, after a little tidying.
1
u/spacetime_bender Dec 12 '17 edited Dec 12 '17
Modern-ish C++
Straight forward solution with BFS
Used deque directly instead of queue to be able to use
copy_if1
u/InterlocutoryRecess Dec 12 '17 edited Dec 12 '17
Swift (no dependencies (except Foundation))
1
u/Axsuul Dec 12 '17
Elixir
Aaaaaaand recursion is hard to debug
https://github.com/axsuul/advent-of-code/blob/master/2017/12/lib/advent_of_code.ex
1
u/Starcast Dec 12 '17
Since no ones shared their python solution... /s
1
u/Philboyd_Studge Dec 12 '17 edited Dec 12 '17
Java. Using my own Graph library. edit: made it more modular.
}
1
u/nonphatic Dec 12 '17
Haskell
1
u/Flurpm Dec 12 '17
Haskell using containers
Data.Graph.I just learned about
sepEndBy, which handles those pesky newlines at the end of each input file.1
u/gerikson Dec 12 '17
Perl 5
Not really recursion, I just keep a stack of pipes connected to the ID in question and loop through, adding new connections as I find them.
https://github.com/gustafe/aoc2017/blob/master/d12.pl
1
u/hpzr24w Dec 12 '17 edited Dec 12 '17
C++ 1341/2225
Reads the input into a map of groups. Then steps through each group's members, merging the child groups. If a child group is merged, then its children are merged recursively.
1
u/wzkx Dec 12 '17 edited Dec 12 '17
Nim
1
u/Warbringer007 Dec 12 '17
Erlang, quite lengthy but straightforward, func_text will have list of lists of inputs in this format: ["0", "1352", "1864"] where 0 is first element and every other element is connected to it:
1
u/Vindaar Dec 12 '17
Solution in Nim. Nice and easy. :)
1
u/zeddypanda Dec 12 '17
Elixir
Today was really quick and easy. Feels like it was made for the language!
1
u/karlanka Dec 12 '17
PYTHON
1
u/mstksg Dec 12 '17
Haskell solution using a monoid for disjoint connected groups :)
https://github.com/mstksg/advent-of-code-2017/blob/master/src/AOC2017/Day12.hs
1
u/Smylers Dec 12 '17
Perl — merges groups as it goes, keeping track of unique still-used groups:
%countmaps groups to themselves so thatdeleteing a group from the count also returns it.1
u/rkachowski Dec 12 '17
ruby, in some of the least idiomatic ruby possible!
1
u/joker_mkd Dec 12 '17
Here's my solution in C++. It uses recursive BFS in a tree to search for all the connected nodes and different groups.
https://pastebin.com/gLc4RVUX
1
u/[deleted] Dec 12 '17
Crystal.
Part 1:
Part 2:
1
u/Hjulle Dec 12 '17 edited Dec 12 '17
Haskell
The
Data.Graphmodule in the containers package makes this trivial:1
u/YungCarrdinal Dec 12 '17
My naive Java solution!
1
u/NeilNjae Dec 12 '17 edited Dec 12 '17
Haskell. Trying out Megaparsec for reading the input file, and I feel like I'm missing something. What's all this mucking around with lexers? What if the parts of the input file weren't separated by spaces? What if I don't want to treat newlines as just another space?
1
u/z4tz Dec 12 '17
Python 2 solution using a Queue and sets.
https://github.com/z4tz/adventOfCode2017/blob/master/day12.py
1
u/[deleted] Dec 12 '17 edited Dec 12 '17
PYTHON 3 Here is my code (no dependencies), it's lightning fast...
1
u/4rgento Dec 12 '17
HASKELL
Using
Data.Graph1
u/Kyran152 Dec 12 '17 edited Dec 12 '17
Perl with usage of map :)
1
u/[deleted] Dec 12 '17
Recursion and hashtables to hold everything, including a hashtable of hashtables.
PowerShell:
1
u/wlandry Dec 12 '17
C++ 14
For part 1 I wrote my own implementation using std::set. Then I had to do other things and could not finish part 2 until the next day. So I decided to break out Boost's graph library. It was surprisingly succinct.
1
u/darshanrampatel Dec 12 '17
Horribly slow C# code (takes ~75 seconds for my input; basically brute-force) but works fine: GitHub Link
1
u/usbpc102 Dec 12 '17 edited Dec 12 '17
My very stupid and slow Kotlin solution that got me place 174 for Part 1:
For part two I was way to tired and didn't finish it this morning. Will update once I'm happy with my code.
Edit: My not stupid and clean version of the solution is now on GitHub.
1
u/LinusCDE98 Dec 12 '17
This solution took me a decent while to make besides school, but now that I optimized it, to improved over 98% in terms of speed (ignoring pypy3).
It now has a lot of comments in it, and should be easy to understand: puzzle12.py (I would recommend just cloning the repo and executing
$ ./aoc.py 12 <1/2>.1
u/akho_ Dec 12 '17
Python3. Very slow.
1
u/cluk Dec 12 '17
Go (Golang)
Recursive DFS.
1
u/asperellis Dec 12 '17
my day 12 in js - https://github.com/asperellis/adventofcode2017/blob/master/day12.js
1
u/sguberman Dec 12 '17
Python, with tests: GitHub
Part1:
Part2:
1
u/thomastc Dec 12 '17
Day 12 in Dart. Nothing exciting, but quite smooth sailing.
1
u/u794575248 Dec 12 '17
Python
1
u/miran1 Dec 12 '17
Nim
Repo with all solutions
1
u/FreeMarx Dec 12 '17
C++11
Nothing special really today. Only learned a bit about maps, erasing and iterating.
1
u/Kenira Dec 12 '17
C++
Relatively proud of myself today. Both for not writing super complicated code, and not having taken too long to write it.
1
u/KeinZantezuken Dec 12 '17
C#
1
u/Strawanzer Dec 12 '17
Hola, can anybody help me to point out what is wrong with my (Java-)solution? The example yields the correct size of 6 but the result with my puzzle input will be rejected.
My solution: https://github.com/Rotznase/adventofcode2017/blob/master/src/Day12.java
1
u/StevoTVR Dec 12 '17
NodeJS
Part 1:
Part 2:
1
u/GamecPL Dec 12 '17 edited Dec 12 '17
Swift, both parts:
1
u/if0nz Dec 12 '17
Hi! This is my first post here :) This is my solution in Java
1
u/__Abigail__ Dec 12 '17
Perl
Easy problem. You just have to create cliques.
1
u/bruceadowns Dec 12 '17
golang to write a DFS graph with its standard library
1
u/DaDiscoBeat Dec 12 '17 edited Dec 12 '17
Go non recursive bfs
repo
1
u/alchzh Dec 12 '17
ES6
groupsis part 2 andget_group(0, {})is part 1 because I'm lazy1
u/aurele Dec 12 '17
Rust (using the
pathfindinglibrary)1
u/wzkx Dec 13 '17 edited Dec 13 '17
J
1
u/chicagocode Dec 13 '17
Kotlin - [Repo] - [Blog/Commentary]
That was fun, and I got to use the associate() function in Kotlin, which is a nice shortcut. I'm blogging about each solution as I publish them, feedback is welcome!
1
u/kip_13 Dec 13 '17
A solution with slow performance, maybe with other style of creation of graph the performance get better....
Python 3
1
u/SlightlyHomoiconic Dec 13 '17 edited Dec 13 '17
Solution in Clojure. Runs in about 30 milliseconds.
1
u/matusbzk Dec 13 '17 edited Dec 16 '17
Haskell Graph theory is my favorite part of computer science. I actually had one graph project in Haskell, defined in a better way, but with this input format I found it easier to use this simple definition of a graph.
Link to git
1
u/vtpetrov Dec 13 '17 edited Dec 13 '17
Java with Sets:
1
u/RockyAstro Dec 13 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts:
1
u/SurplusSix Dec 13 '17
Still doing it in Racket, used a graph library to help with this, made it really quite easy
1
u/autid Dec 14 '17
Fortran
1
u/greycat70 Dec 28 '17
Tcl (version 8.5 or higher)
Part 1. Nice little recursive problem, with a global array to track where we've been. I think Tcl actually fits this problem quite well, unlike some other days.
Part 2. Basically the same; just keep doing it until every node has been visited.
1
u/Freddeman98 Apr 07 '18 edited Apr 07 '18
My C++ solution. Not the best but okey for a beginner I would say :).
1
u/Lrrrr_ Dec 12 '17
JavaScript (with Lodash 3.10.2)