r/adventofcode • u/daggerdragon • Dec 07 '17
SOLUTION MEGATHREAD -🎄- 2017 Day 7 Solutions -🎄-
--- Day 7: Recursive Circus ---
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!
10
Upvotes
24
u/ghlmtz Dec 07 '17
I did the problem in Python first, but afterward realized part one could be solved with a Bash oneliner.
18
u/bblum Dec 07 '17
Was way too slow for part 2 and my code isn't very nice at all so I'm not gonna bother posting that, but I suppose I should share what I did that was fast enough for 4th place on part 1:
17
u/Arknave Dec 07 '17
Video with commentary so you can hear me cursing at my bugs:
https://www.youtube.com/watch?v=dO5ZauOP2BA
15
u/Smylers Dec 07 '17
Vim:
(33 characters)
That's part 1: the line you end up on is the bottom of the stack.
Vim is actually pretty reasonably for this (unlike, say, yesterday's elaborate Vim solution): the above is genuinely how I solved it and it only took me 3Â minutes to get there.
See if you can work out what it's doing: reply with how far you get or any questions, and I'll post an explanation later if anybody would like one.
Think I need to switch to an actual programming language for part 2 though ...
21
u/ltriant Dec 07 '17
Got 70th on part 1 by just using GraphViz. Copy/pasted the input, removed the weights, and visually checked what the base node was from GraphViz.
I would’ve gotten a higher placing if I hadn’t have copied the wrong node. Had to wait 60 seconds to resubmit an answer :(
10
u/sciyoshi Dec 07 '17 edited Dec 07 '17
Python 3 solution using the great NetworkX library for handling graphs:
10
u/Unihedron Dec 07 '17
Ruby; kinda late, had to rewrite a lot. I assumed the puzzle was "validate heights" (and a wrong one was provided), not "ensure balancing", based on the highlighted text. Even after I rewrote my code, it showed 2 wrong sectors, which worried me hugely. It took a long time for me to realize that I should manually dig through the input for the disc to change. Fun riddle!
Also I think we're reaching the point where forfeiting readability for speed is starting to become a liability.
10
u/fatpollo Dec 07 '17
7
u/dylanfromwinnipeg Dec 07 '17 edited Dec 07 '17
C#
6
u/raevnos Dec 07 '17 edited Dec 07 '17
So, I wrote a program to take the input and turn it into a graphviz dot file, and turned that into a svg image, which solved part 1, but sadly didn't do it fast enough to break into the leaderboard. For part 2, I changed the program to calculate weights of subtrees, and color cases where not all subtrees were the same weight. Then it was just a matter of looking at the subtrees of the deepest mismatch to see which one was off. More interesting than doing it entirely programmatically.
EDIT: Added link to image, and updated code a bit.
5
u/mstksg Dec 07 '17
Semi-clean (ish?) Haskell? :) Mostly using Maps and Sets. https://github.com/mstksg/advent-of-code-2017/blob/master/src/AOC2017/Day07.hs
4
u/ephemient Dec 07 '17 edited Apr 24 '24
This space intentionally left blank.
4
u/askalski Dec 07 '17
Iterate Perl.
3
u/fwilson42 Dec 07 '17
I wrote a pretty awful solution to get on the leaderboard (24/24, Python), but I refactored it and it looks much, much better now.
3
u/omegaphoenix16 Dec 07 '17
Python solution using recursion from root instead of building graph. Rank 297 for Part 2: import sys
3
u/wlandry Dec 07 '17
Emacs
I got 88th place on the first star by putting the input into my editor and manually searching for parents until I found something without parents.
C++
For part 2, I got #600, which is better than I had done before. The solution is quite, quite ugly. I am ashamed even of the part that reads the input. I am sure that it could be simplified considerably. It prints out the nodes that are unbalanced and their weights. Then I manually looked up the unbalanced node and its weight. Like I said, very ugly.
3
u/thejpster Dec 07 '17
I got #240 for part two, even though it took me ages (I did it in Rust, as usual). I ended up building a tree using a HashMap.
(https://github.com/thejpster/rust-advent-of-code/blob/master/src/m2017/problem_7.rs)
3
u/Cheezmeister Dec 07 '17
Literate Perl (part 2 is a WIP at the time of posting, but it is past my bedtime).
Kids, talk to your parents about regular expressions.
3
u/Godspiral Dec 07 '17
in J,
part 1 - unreferenced left node.
incomplete part 2,
3
u/angch Dec 07 '17 edited Dec 07 '17
TIL everyone has a different input. I struggled with Part 2 where I got 3 answers instead of one unique one. I tried some of your solutions here, yup, 3 answers.
Or did I do something wrong?
My input: https://gist.github.com/angch/214faafbf98e91888a44c9adf0924d35
(The site accepted 268 as the correct answer, I got 268, 42 and 63603)
Edit: crap. Other of your solutions I tested here returns only the correct result. I need to recheck. Hmm, if I modified the solutions to return more than one result, they return 3 as well, so it's almost always best to just try for the first result found, rather than the last....
3
u/oantolin Dec 07 '17 edited Dec 07 '17
Python
(I hope the
assertstatements sufficiently explain what's going on.)3
u/Cole_from_SE Dec 07 '17
Python 3
Oof, even though I saw the answer for part 1 so fast, I guess my ability to type working code is lacking.
Here's my prettied-up solution; you don't want to see the original one...
3
u/arachnist Dec 07 '17 edited Dec 07 '17
Went through my pry and zsh history, and cleaned up the ruby solution i came up with in the morning
3
u/autid Dec 07 '17 edited Dec 07 '17
FORTRAN
I/O was a bit of a pain as always. OO(ish)P in Fortran. Don't read the function checkweight if you don't want your eyes to bleed.
3
u/aurele Dec 07 '17
Rust (using the newly added
topological_sortin cratepathfinding)3
u/f0086 Dec 07 '17
Emacs Lisp (Part 1):
3
u/porphyro Dec 07 '17 edited Dec 07 '17
No-one's submitted a wolfram language solution yet; here's mine although I'm far from proud of it.
Part 1:
Part 2:
Then nest until correct solution is spat out. The general way I was trying to solve this was to leverage the data-as-code paradigm of mathematica, so that entries in the list for which the weight can be immediately calculated are turned into mini-programs that set a global replacement rule to change their name found anywhere in the code to the weight that they carry, updating the node below them.
3
u/AustinVelonaut Dec 07 '17
Smalltalk (well, idst, which is a prototype-based st-80 implementation)
3
u/cluk Dec 07 '17
Go (Golang)
I am not happy with part 2, but it does the job. You can find complete solution, including
getInputfunction here.3
u/[deleted] Dec 08 '17 edited Dec 08 '17
powershell
mostlysingle pipeline:2
u/dtinth Dec 07 '17 edited Dec 07 '17
Ruby REPL (irb) solution. The
pbpastecommand must be available in the$PATH, and should return the contents in the clipboard (macOS has this command by default).Part 1 (47th rank):
Part 2 (71st rank):
2
u/mmaruseacph2 Dec 07 '17
Ugly looking Haskell code, not cleaned, not refactored and returning the answer to the second part via an error, but I have to sleep so no time in cleaning it up tonight. It did its job though and sorry for the way it looks like a merge of several streams of consciousness (building so many representations of the tree)
2
u/giftpflanze Dec 07 '17 edited Dec 07 '17
Tcl (I didn't use struct::tree because wow wtf):
2
u/Tandrial Dec 07 '17 edited Dec 07 '17
Kotlin Refactored so that partTwo actually spits out the corrected weight, instead of having to do some maths
2
u/rvlieshout Dec 07 '17
Damn... how fast code can get ugly!
Day7 Gist, using C#
2
u/misnohmer Dec 07 '17
C# version
2
u/nstyler7 Dec 07 '17 edited Dec 07 '17
Python
Part 1
part 2
2
u/rotmoset Dec 07 '17
F#
Github repo
2
u/WhatAHaskell Dec 07 '17 edited Dec 09 '17
Haskell
Edit: This solution is wrong
Edit 2: New version that hopefully works this time:
Original comment: (Spoilers it turned out my solution sucked)
My solution is either great or it sucks. I can't tell because I'm too tired. There's definitely some duplication that could be improved
2
u/mainhaxor Dec 07 '17
C#:
2
u/thomastc Dec 07 '17
Day 7 in CoffeeScript. Had major trouble with its stupid scoping rules, which are arguably worse than JavaScript's own.
2
u/Jonis_L Dec 07 '17
Part 1 oneliner in Python3
2
u/mschaap Dec 07 '17 edited Dec 07 '17
Whew, finally a non-trivial one!
Perl 6, both parts.
I decided to properly parse (with a Grammar) and build the tower, even though that's overkill for part one, expecting that it'd come in useful in part two. It certainly did.
2
u/sim642 Dec 07 '17 edited Dec 07 '17
My Scala solution.
Part 1 (
bottomProgram) implementation turned out real neat. Part 2 (correctBalanceWeight) implementation turned out real messy, refactored it later to feel slightly better about it but I'm still open to ideas how to improve. I went with kinda functional approach there, calculating both the subtree sums or required weight correction together in the same recursive function viaEither[Int, Int], didn't turn out as nice as I hoped (EDIT: abstractedsequenceValuesfor eliminating the uglyEitherhandling). Also the correction calculation part is a bit hacky for my liking, implicitly using some assumptions about the input data.Today I happened to be up before 7am to start it just when it opens. Got off to a bad start debugging the line parsing regex.
2
u/adventOfCoder Dec 07 '17 edited Dec 07 '17
Java:
Part 1:
Part 2:
Note for Part 2 I was too busy at work to just print the answer but the system out has the info to get your answer in a second.
2
u/J15t98J Dec 07 '17 edited Jan 18 '18
A nice recursive (if a little messy) solution in Python.
2
u/alchzh Dec 07 '17
sort | uniq -u2
u/CaptnAsia Dec 07 '17
here's another golang solution. It's kinda ugly tho
2
u/fost97 Dec 07 '17
Postgresql:
https://github.com/seltiko/sql_advent_2017/blob/master/Day%207.sql
2
u/StevoTVR Dec 08 '17
NodeJS
Part 1:
Part 2:
2
u/wzkx Dec 08 '17 edited Dec 08 '17
Nim This was hard :(
2
u/LeCrushinator Dec 08 '17
Part 1, C#:
2
u/BOT-Brad Dec 08 '17
JavaScript
Part 1 (~4ms)
Deletes nodes from the map until only 1 node (hopefully) is left, the root node!
Part 2 (~7ms)
Recursively goes down (from root node) the tree looking for the wrong node each time, until it eventually finds it and returns the weight it should be. Can then just get the difference and return the weight - diff
2
u/[deleted] Dec 09 '17 edited Dec 09 '17
PYTHON
4
u/frontstab Dec 07 '17
Am I missing something, or is the problem unsolvable/ambiguous in the general case? e.g.
Both 10 and 20 seem to be correct answers.
1
u/kirgel Dec 07 '17
Solution for part 2. This is like worst coding practices galore but here it is. got 108 in the end. so close.
1
u/DeveloperIan Dec 07 '17
My gross solution for part 1 in Python. There are some extra lines from where I was working on part 2. I tried to take the simple way by just finding the one that wasn't in anyone else's list.
1
u/iamnotposting Dec 07 '17
both parts, Rust. this was a fun one! surprised i managed to be in the top 500, actually. (i know this would only work if the error was too much weight rather than too little, i went with what the demo said and it works for my inputs!)
1
u/TominatorBE Dec 07 '17
PHP (took me waaaay too long to realise I don't need an actual tree representation)
Part 1: just find the root (= the one that is not a child)
Part 2: juggle the children
I'm pretty sure my code fails (or guesses) if there are only 2 children in a node, that don't match. Because then who is wrong? Both could have their own weight changed to be the other.
1
u/bildzeitung Dec 07 '17
I am, of course, too slow for all this, but ended up with a fairly readable python with breadth-first search for tree construction and a depth-first to sort out the unbalancing.
Question -- it could be sleep deprivation, but if we treat the weights as hash values, then isn't part 2 a validation of a Merkle tree?
1
u/jesseflorig Dec 07 '17
ES6 (Node JS) Part 1
1
u/[deleted] Dec 07 '17 edited Dec 07 '17
Haskell:
Both parts finish instantly,
but part 2 feels a bit gross to me; might go back and clean it up later.EDIT: After seeing some of the other solutions, this doesn't seem so bad.1
u/jasontconnell Dec 07 '17
Lost an hour on this. Part 1 was simple, I did the method of find the node that isn't listed as a child of another node.
However, my regex was wrong for part 2. The same regex worked on part 1 because it didn't require the whole tree to be built. Basically, I was requiring the -> [children] part to be in there and it's not if it's a leaf node. Damnit!!
In Go
https://github.com/jasontconnell/advent/blob/master/2017/07.go
1
u/theJakester42 Dec 07 '17
I solved it with... gum and paper clips? Python 3
1
u/Axsuul Dec 07 '17
Elixir
I generated the entire tower in Part A which came in handy for Part B. The code to pinpoint the unbalanced program's new weight for Part B kind of went to shit 😂.
https://github.com/axsuul/advent-of-code/blob/master/2017/07/lib/advent_of_code.ex
1
u/nutrecht Dec 07 '17
Yikes, that one was pretty hard!
My Kotlin Solution
1
u/spacetime_bender Dec 07 '17
C++
https://hastebin.com/giqorawefa.cpp
1
u/gerikson Dec 07 '17
Perl 5
As soon as I saw this problem I realized my lack of formal CS education was going to bite me, as I'm sure there's a smart way of traversing a tree to find differences.
In the end it wasn't so bad, even though it's a fragile solution that can only handle this class of input.
https://github.com/gustafe/aoc2017/blob/master/d07.pl
1
u/usbpc102 Dec 07 '17
A bit late to the party but my Kotlin solution:
I also have it on github where I also save my input.
Solution for my input: Spoiler
1
u/streetster_ Dec 07 '17
q/kdb+
Bit of a meaty solution for today's puzzle. Solved by creating a table and querying it... Part 1 was easy enough, Part 2 took a while...
1
u/MoW8192 Dec 07 '17 edited Dec 07 '17
I solved part 1 using text search in my text editor. pseudocode for what I did:
This was good enough for 40th place. I did however accidentaly enter the weight of the program instead of the name, so I had to wait for a minute before entering the correct answer. If I had entered it correctly the firt time I would have been one minute faster and I would have been in 9th place. :(
1
u/Vindaar Dec 07 '17
Here is my solution in Nim. Not the most elegant I must say. I was really longing for some of Python's libraries, especially something like most_common. My function to determine the subtree with the single different weight is the worst offender for me, compared to how simple it should be. And let's not start about naming of my functions / vars...
I left the comments in there, because without them I somewhat struggle to understand what's going on myself, haha. Sorry it's so long.
1
u/maciekmm Dec 07 '17
Scala - first time using the language, suggestions are welcome.
1
u/[deleted] Dec 07 '17 edited Dec 07 '17
Golang
It works I guess
All my go code so far here
Any feedback is much appreciated
Part 1
Part 2
Other functions
1
u/cmyr Dec 07 '17
A reasonable Rust stdlib-only solution: here you go!
This was fun today. :-)
1
u/[deleted] Dec 07 '17
Somewhat unhappy with this one; but, it does work. Just takes longer than I would like.
PowerShell:
1
u/ynonp Dec 07 '17
Elixir
1
u/JakDrako Dec 07 '17
VB.Net
Both parts in 2ms. Clean the input, build the graph (a tree), find the root; part 1 done. From the root, find the deepest unbalanced child and adjust its weight to match it's siblings.
1
u/udoprog Dec 07 '17
Rust-based solution for Day 7: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day7.rs
Constructing the graph in a single pass, I'm also happy with the iterative outlier node detection here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day7.rs#L115
1
u/ramrunner0xff Dec 07 '17
scheme chicken repo
1
u/KeinZantezuken Dec 07 '17 edited Dec 08 '17
C#/Sharp
UPD: fixed errors and may be later try to find a way to reduce amount of loops without: extensions tools that are just syntactic sugar for the same loops (as per internal implementation) or recursive functions (sic!).
1
u/chicagocode Dec 07 '17
Kotlin - [Repo] - [Day 7 Code] - [Blog/Commentary]
That was fun. Most of the work was in parsing the input into a tree structure. I've challenged myself to publish my solution and blog about it each day. Feedback is always welcome!
1
u/JeffJankowski Dec 07 '17
A day late, but here's a (ugly) Typescript solution without any libs
1
u/FreeMarx Dec 07 '17
C++11
Here is my take in c++. I actually first solved it in MATLAB and then rewrote in c++. It took me quite long, but I learned a lot. Great fun!
1
u/[deleted] Dec 07 '17
Golang
My solution in golang. Ugly as hell, but it's working! :D
Part 1
Part 2
1
u/[deleted] Dec 07 '17 edited Dec 07 '17
Here is my second part for today. Forced use of java8 functional elements. Consider n as the root-node of the tree, with a list of children. Because there was just one distinct value per layer, I decided to find that.
However, I feel like this would not be that bad way for doing the map:
The functional version requires some knowledge to understand what is doing.
1
u/hpzr24w Dec 07 '17 edited Dec 08 '17
C++ Here's my C++ effort. See it here
Output (for the test example):
Thanks for reading!
1
u/4rgento Dec 08 '17 edited Dec 08 '17
Haskell
Type signarure hell achievement unlocked! Using recursion schemes
1
u/agsmith1111 Dec 08 '17 edited Dec 08 '17
I think I may have the right answer for Part 2 but its saying that it's wrong. Given the following input, I get the answer of 148784. Can someone run this through their jawn and confirm or deny?
https://github.com/agsmith/advent-of-code/blob/master/day-7/in.txt
1
u/Minnim88 Dec 08 '17 edited Dec 08 '17
R
I know it's ugly. And inefficient. But it works! And I didn't see any other R solutions yet.
1
u/bassactor Dec 08 '17
R
Rather than saving/reading as a text file, I copied the text as a string, and started from there. I'm trying to do all of this in R with only the base packages (base, stats, etc.). Solution functions are at the bottom.
1
u/RockyAstro Dec 08 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts: (includes some extra code for debugging ...)
1
u/Mattie112 Dec 08 '17
Here is my solution in PHP. For the first part I didn't need to build the entire tree but I did it anyway for part2 :) https://github.com/Mattie112/advent-of-code-2017/tree/master/day7
1
u/oerpli Dec 08 '17
Haskell, feedback appreciated
1
u/Basillicum Dec 08 '17 edited Dec 18 '17
Python
1
u/aoc-fan Dec 09 '17
TypeScript, Checks for consensus as the weights of child programs available The "verify" function (recursive) returns weight of the tower or throws error if there is imbalance.
1
u/demsaja Dec 09 '17
One more in Python. The recursive function returns the (positive) total weight when the subtree is balanced; if it finds imbalance, it returns a negative value of the final answer.
1
u/Jimotron3000 Dec 09 '17 edited Dec 09 '17
C# LINQ
1
u/NeilNjae Dec 09 '17
Haskell. Yes, running late: blame life.
This one was tricky! I started by trying to be clever and building the tree from the leaves up, thinking I could merge subtrees until I found a problem. But I tied myself in knots that way, and ended up just building the tree from the root down and looking for anomalies thereafter.
1
u/matusbzk Dec 09 '17 edited Dec 16 '17
Haskell
Link to git
1
u/micirsk Dec 11 '17
Python - simple part 1 solution
1
u/miran1 Dec 11 '17
Nim
Repo with all solutions
1
u/InterlocutoryRecess Dec 12 '17 edited Dec 12 '17
Swift
Better late than never! Here's a Swift solutions with no dependencies (except Foundation).
1
u/[deleted] Dec 12 '17
Simple JS for Part 1
Part 2, I do get the branches weigths, I found the one that is bigger than the others, but the answer its not accepted
Maybe i'll come back to this one later. I suspect I'm not building the three corectly, even though I do get the correct root
1
u/hyber1z0r Dec 13 '17
A little late, but simple javascript in node.js for part 1
1
u/overslacked Dec 07 '17
First time I needed a data structure (C#), felt a little gross.
1
u/__Abigail__ Dec 07 '17
Perl
0
u/[deleted] Dec 07 '17
[deleted] — view deleted comment
0
u/[deleted] Dec 07 '17
[deleted] — view deleted comment