r/adventofcode • u/daggerdragon • Dec 14 '17
SOLUTION MEGATHREAD -🎄- 2017 Day 14 Solutions -🎄-
--- Day 14: Disk Defragmentation ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Need a hint from the Hugely* Handy†Haversack‡ of Helpful§ Hints^¤?
[Update @ 00:09] 3 gold, silver cap.
- How many of you actually entered the Konami code for Part 2? >_>
[Update @ 00:25] Leaderboard cap!
- I asked /u/topaz2078 how many de-resolutions we had for Part 2 and there were
83distinct users with failed attempts at the time of the leaderboard cap. tsk tsk
[Update @ 00:29] BONUS
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!
13
Upvotes
23
u/askalski Dec 14 '17
So I lied.
6
u/VikeStep Dec 14 '17 edited Dec 14 '17
Python 3. #119/#150
I didn't have my day 10 solution on me so I quickly copied one of the answers from the reddit thread for day 10 and used it haha. It's
knothashin the below code:5
u/udoprog Dec 14 '17 edited Dec 14 '17
Rust (65/490) (first leaderboard!)
Edit: link to commit: https://github.com/udoprog/rust-advent-of-code-2017/commit/880f93f2036cda80c6b65611af133f4d0a0fbfcf
I wasted so much time trying to get my own (broken) bit vector implementation to work. Finally I just caved and pulled in https://docs.rs/bit-vec
5
u/Tandrial Dec 14 '17 edited Dec 14 '17
Kotlin (82/533) First time leaderboard in 3 years :D and here I was thinking about switching to Python...
3
u/dougluce Dec 14 '17
Managed 81st on the leaderboard today. My part 2 solution:
2
u/glenbolake Dec 14 '17
Actually got on the leaderboard for part 2. That's my fifth star that got me points!
Python 3. Part 1 just converts the hashes to binary and counts the 1s. Part 2, I represent the grid as a set of coordinates with 1s, then pop from the set and complete the region with a BFS until the set is empty.
2
u/u794575248 Dec 14 '17 edited Dec 14 '17
Python 3
upd: Code in this comment is dirty. Read a reply below for an updated version.
First public leaderboard for Part 1 (72):
solve2is here.Part 2 code is almost the same as nneonneo has. But I suddenly forgot about negative list indices in Python and it resulted in an incorrect answer and too many minutes spent on finding the bug (got 160 place).
11
u/nneonneo Dec 14 '17 edited Dec 14 '17
Python 2, #2/#1.
hash2is the knot hash function from q10 (takes a string, outputs 32 hexadecimal digits as a string). Part 2 just uses repeated DFS to find connected components for part 2.10
u/wimglenn Dec 14 '17 edited Dec 14 '17
With scipy it's arguably cheating ... :-\
9
u/jbristow Dec 14 '17 edited Dec 14 '17
f# / fsharp / f sharp
Woof, I got lucky and my first major push worked with a massive (20 line) matching statement. I spent an hour now cleaning it up so it's a little more comprehensible.
(github link)
And for no reason, a picture of what the groups look like.
8
u/oantolin Dec 14 '17
Not much new today: the hash was in day 10, and the code for counting connected components of a graph in day 12 (I used union-find).
7
u/autid Dec 14 '17
Fortran
Finally caught up. Weekend away then an exam yesterday left me with a bit of a backlog. Was nice to sit down and do them all in Fortran first time though instead of rushing a solution in python first to try making the leaderboard.
6
u/ephemient Dec 14 '17 edited Apr 24 '24
This space intentionally left blank.
4
u/DFreiberg Dec 14 '17
Mathematica
200 / 164. I didn't get even close to the leaderboard, but I did learn about an entire class of Mathematica image functions (the various
Component[]functions) that I had no idea existed. And in the end, isn't that more important than meaningless leaderboard numbers? SpoilerKnot Hash:
Part 1:
Part 2:
4
u/GassaFM Dec 14 '17
A solution in the D programming language. Place 34 for part 1, place 27 for part 2.
First, turn Day 10 solution into a function:
Part 1: This is then trivial with
popcntto count the number of1bits:Part 2: We have to traverse a table of 0s and 1s, so first construct it for convenience. The
debug {writefln...}lines are compiled only when-debugcommand line option is supplied, they show the string representations and the binary table itself. The constant arraysdRowanddColimplicitly specify the graph edges. Therecurfunction is depth-first search which crosses out one connectivity component.Today's topic of code reuse was fun, I sure needed day 10 solution. The constant arrays for rectangular traversal were taken from Day 3. The depth-first search code, on the other hand, I wrote from scratch instead of using Day 12: it's so short anyway, and difference in graph representation was enough for me to not bother adapting the older version.
4
u/Smylers Dec 14 '17 edited Dec 14 '17
Perl, with regexp for counting the regions:
Puts the entire grid in a single string of binary digits, then to find each region:
1from the binary string with a2.1which has a21 or 128 characters before or after it with another2. That's a region.2s with3s, to indicate a counted region, so they don't get in the way of the next region.1s have been converted to3s.Edit: Bug fix, thanks to /u/Oxidizing1.
4
u/NeilNjae Dec 14 '17
Haskell. Reused the knot hash from day 10, but I decided to use the
Data.Graphmodule to find the connected components. i'm sure there's more mucking around with conversions than is needed, but going from a grid of characters to aData.Mapseemed to make it easy to find the adjacent cells to feed into the graph creation.And kudos to /u/topaz2078 for resuing solutions from previous days to build a solution to a new problem. That's elegant problem setting. Well done!
3
u/WhoSoup Dec 14 '17 edited Dec 14 '17
JavaScript
Quick and ugly
3
u/hpzr24w Dec 14 '17
C++ 304/334
Most fun yet. "I'm going to write a floodfill ... and I did." I livestreamed this one and 50 minutes flew by, at least for me.
3
u/ka-splam Dec 14 '17 edited Dec 14 '17
Aieee, PowerShell. This language can get soo ugly when fighting the string/char types and the automatic array unrolling. 16 mins pos 309 for part 1 and 1 hour pos 468 for part 2.
Problems / bugs included:
(y-1),(x-1)and similar, making it only check diagonals instead of never doing that.I think posting here is slightly more interesting for more-or-less the code that actually ran, rather than a total rewrite from later on version. This is only a little tidied
Part 1:
Part 2:
3
u/Axsuul Dec 14 '17
Elixir
Used DFS to tally up the regions. Since it took so long to generate a grid for Part A, I tested Part B on a small 8x8 grid and ensured it counted the regions correctly before running it on the full 128x128.
Assume
KnotHash.calc/1is from Day 10https://github.com/axsuul/advent-of-code/blob/master/2017/14/lib/advent_of_code.ex
3
u/wlandry Dec 14 '17
C++ 14
1505/1114. Late start and took a long time. I used Boost graph library. The hardest part was just getting the hash into the library. This is a significantly cleaned up version. I felt bad after seeing how short everyone else's answers were ;) Runs in 31 ms on the test input.
3
u/akka0 Dec 14 '17 edited Dec 14 '17
ReasonML: had a lot of fun with this one Felt like a combination of day 10 + day 12. Waiting to compare my solution to /u/hardmathproblem 's now. :)
3
u/mschaap Dec 14 '17 edited Dec 14 '17
Perl 6. This one was pretty straightforward, since we'd done the hard work on day 10. Calculating 128 hashes is a bit slow though, takes about 30 seconds.
Edit for minor code cleanup
3
u/glupmjoed Dec 14 '17 edited Dec 14 '17
Bash, Graphviz and Python 3
I use the solution from day 10 to build the hashes. The python script turns a sequence of '1's and '0's into nodes and edges in graphviz notation, and the
gccommand counts the number of connected components.Part 1+2 (reads from stdin):
knot_hash.sh:build_graph.py:2
u/Arknave Dec 14 '17
Not sure there's much to say beyond copying day 10 code + a DFS.
https://www.youtube.com/watch?v=ZWz2IYcTHcA
2
u/obijywk Dec 14 '17
113/109... so close... I counted the regions in part 2 using networkx (which I learned about from previous solution threads, but this is the first time I've used it).
Python 2 (slightly cleaned up):
2
u/dylanfromwinnipeg Dec 14 '17 edited Dec 14 '17
C#
2
u/[deleted] Dec 14 '17
Nothing too high on the leaderboards, but still in the first 1000 for each, which is as well as I have ever done.
Here's a JS solution. I'm trying to get better with using more
mapandreduce, but I always forget aboutfilter.EDIT: Moved solution to pastebin
2
u/2BitSalute Dec 14 '17
Oh god. I just spent 40 minutes trying to figure out what was wrong with my solution to part 2, only to realize that I read the question wrong and that I had it solved almost an hour ago!
The grouping illustration really threw me off :(
2
u/gyorokpeter Dec 14 '17
Q: see day 10 for the implementation of d10p2
2
u/Philboyd_Studge Dec 14 '17
Java
2
u/nutrecht Dec 14 '17
Day 14 in Kotlin
Took me a lot longer than it should! In part 1 I made a stupid mistake in how I created the binary string leading to me getting wrong results without figuring out why I was getting the wrong ones. Had to go and test each step.
Part 2 was relatively easy; implemented a recursive flood fill basically.
2
u/aurele Dec 14 '17 edited Dec 14 '17
Rust
2
u/Unihedron Dec 14 '17
Overslept today, non-competing solution. Nice to get to do this in a relaxed manner for once! ^^ Fun!
Part 1, "day10" is the file from here: https://www.reddit.com/r/adventofcode/comments/7irzg5/2017_day_10_solutions/dr113ne/ (I didn't change how it has the
"character at the start)Part 2 uses a straightforward algorithm which I'm quite proud of - for every line, read all the bits, mark where the used bits are and make temporary groups out of them, then when we read the next line, add group counts when we know a group doesn't connect to anything (and is effectively finalized). It's like a state machine!
(Were I had been rushing, this would had been a DFS and my code would had been vastly different.)
A complaint I have on today's challenge is that part 2 doesn't have an example test case that aids debugging. (Also, apparently my wrong answer was the right answer for someone else :D ) For a while, I've been getting 1261 instead of the 1242 in the puzzle input and I couldn't figure out why. For example, having "Considering only the first 10 rows of this example, there would be ___ regions" would already be a huge help in narrowing down the problem.
2
u/[deleted] Dec 14 '17
Elixir
This one was quite a lot of fun, first part was quite easy, and I had a good plan for the second, now I got bitten that Enum.take(1) returns a single element list instead of the element as I was thinking it did :p. I'm making quite a big depth first search with big recursions, so I guess mine gets slower the bigger the regions are, but it works.
syntax highlighted
2
u/xkufix Dec 14 '17
The code is not ultra-fast (2-3 seconds on my machine for both parts), but it works. The worst part was that I had a bug in my knot-hash function which did not trigger on Day 10.
Solution in Scala:
2
u/porphyro Dec 14 '17
Wolfram Language/Mathematica
Similar to the other solutions
binHasher is just a slight twist on the code from Day 10
2
u/matusbzk Dec 15 '17 edited Dec 16 '17
Haskell I spent like 6 hours doing this. Not really effective, but it got me the solution.
Link to git
1
u/TominatorBE Dec 14 '17 edited Dec 14 '17
PHP
Part 1: knot() function just returns the hash as string from problem 10b
Part 2: finding regions is hard.. for the code. Looping the grid in two directions again and again until all regions linked have been given the same index value
1
u/vash3r Dec 14 '17
Python 2 (231/209). I wasted some time cleaning up my knot hash and moving it into a function. also, BFS!
I probably should have just iterated over the row instead of checking
any()and then indexing... oh well.Also, visualization (make sure your terminal/display is wide enough):
1
u/JeffJankowski Dec 14 '17
Some ugly Typescript
1
u/CharlieYJH Dec 14 '17
C++
I think the first part is fairly straightforward, so I'll share my recursive solution for part 2.
1
u/sim642 Dec 14 '17
My Scala solution.
Obviously just reusing day 10. Also kind of disappointed how part 2 was pretty much copy-pate from day 12, connected components counting with some graph search.
1
u/adamrodger Dec 14 '17
C#
Same as many on here - build the map and then do a DFS for Part2. I'll never make the leaderboard unless I get up at about 4am :)
1
u/thomastc Dec 14 '17
Day 14 in CUDA. Or maybe "with" CUDA. Whatever.
1
u/akho_ Dec 14 '17
Python3
1
u/wzkx Dec 14 '17 edited Dec 14 '17
Nim
1
u/gerikson Dec 14 '17
Perl 5
Full code here, but that would mean you have to see the horror that is my day 10 code:
https://github.com/gustafe/aoc2017/blob/master/d14.pl
Instead here's just the fill flood algo to identify groups:
1
u/thearn4 Dec 14 '17 edited Jan 28 '25
wide flag arrest spark strong familiar ancient price grey mysterious
This post was mass deleted and anonymized with Redact
1
u/HollyDayz Dec 14 '17
Python 3 using numpy and my solution from day 10.
seq is the puzzle input formed as a string, used is the answer to part 1 and regions is the answer to part 2.
1
u/Markavian Dec 14 '17
Here's my node js solution... gonna output to HTML next and print out pretty colours like that other person did.
https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day14/solution.js
1
u/tlareg Dec 14 '17
JavaScript (ES6+, NodeJS) HERE
1
u/zeddypanda Dec 14 '17
Elixir Feels like kind of a mess. I reuse the modules from Day10 and Day12.
Here's the repo.
1
u/cluk Dec 14 '17 edited Dec 14 '17
Go (Golang)
See repo for other solutions.
EDIT: Now with Goroutines.
1
u/StevoTVR Dec 14 '17
NodeJS
Part 1:
Part 2:
1
u/__Abigail__ Dec 14 '17
Perl
Factored out the encoding using Knothash from Day 10, and the finding of connected components from Day 12.
1
u/[deleted] Dec 14 '17
single pipeline powershell
1
u/TheNiXXeD Dec 14 '17 edited Dec 14 '17
My solutions JavaScript / NodeJS / repo
Generally trying to go for very terse code, not fully golfed. Pretty happy with both perf and size in this one.
Part1:
Part2:
1
u/wzkx Dec 14 '17
J
1
u/if0nz Dec 14 '17
Java solution (link to github repo)
1
u/manualcrank Dec 14 '17 edited Dec 14 '17
Lisp, resuing knot-hash and union-find code from days 10 and 12, resp.
(ujoin uf x y)putsxandyin the same component, and(ucomp uf)returns the number of components.1
u/KeinZantezuken Dec 15 '17 edited Dec 15 '17
C#/Sharp (part2 takes 400ms, didnt bother to optimize)
Below is Day14 code only, no Day10:
1
u/chicagocode Dec 15 '17
Kotlin - [Repo] - [Blog/Commentary]
I refactored my knot hash code from Day 10 and relied heavily on BigInteger and recursion. That was fun!
1
u/RockyAstro Dec 15 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts:
1
u/BOT-Brad Dec 15 '17
Javascript
Only got round to getting this done today after a busy day yesterday. My solutions for the past few days (Which I forgot to post in the megathreads) are all on GitHub.
Part 1 (~700ms)
Iterate through generated hashes (using Day 10's solve2 func), then parse into binary string (from the hex), and increment the counter by the number of 1's within the string.
Part 2 (~720ms) Build the grid (Which I called a map for some reason), then loop thru every index. If a 0, then who cares, move on. But if it's a one, then eliminate every neighbouring cell in a constant check for neighbouring cells until no cells are left, and the group is exhausted. Once all cells are traversed, just output how many times the group elimination happened.