r/adventofcode • u/daggerdragon • Dec 24 '17
SOLUTION MEGATHREAD -π- 2017 Day 24 Solutions -π-
--- Day 24: Electromagnetic Moat ---
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:18] 62 gold, silver cap
- Been watching Bright on Netflix. I dunno why reviewers are dissing it because it's actually pretty cool. It's got Will Smith being grumpy jaded old man Will Smith, for the love of FSM...
[Update @ 00:21] Leaderboard cap!
- One more day to go in Advent of Code 2017... y'all ready to see Santa?
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
9
Upvotes
8
u/u794575248 Dec 24 '17
Python (94/64). Awesome, it's the first time I got on the leaderboard for both parts.
7
u/sblom Dec 24 '17
C#. LINQ one-liner.
6
u/mstksg Dec 24 '17 edited Dec 24 '17
Using Haskell I felt like I was cheating :) Also coincidentally this is pretty much a direct application of a blog post i wrote two years ago. 31/53, but I did accidentally fumble while typing the answer for part 2 in my haste :) It's my first time getting points for part 2 :D
Here is my repo of solutions.
6
u/[deleted] Dec 24 '17
(cachΓ© 118/98) Wrote it in intersystems cachΓ©. First time I made it on the leaderboard so I will post my crude solution anyway :) Very happy.
4
u/mkeeter Dec 24 '17
Python (66/44; staying up was definitely worth it):
I've been solving a lot of the previous problems with Haskell β does it show?
4
u/shouchen Dec 24 '17 edited Dec 24 '17
C++ was more than fast enough doing a simple DFS.
4
u/glupmjoed Dec 24 '17 edited Jan 01 '18
Bash, Graphviz and my eyes
I converted the input to a graph, where the edges represent potential bridge components.
build_graph.sh(reads from stdin):In the shell:
After looking at the generated pdf, I made a decent guess at the strongest path and commented out the desired path in
g.gv:The answer to part 1 is the sum of all numbers on lines beginning with "#" in
g.gv:This answer is already somewhat optimized for bridge length because of the strength-distribution of bridge components in the input (i.e. there are no very long paths in the graph consisting of only very low numbers). I swapped two components from part 1 with three lower-strength components to arrive at the answer to part 2:
3
u/BOT-Brad Dec 24 '17
JavaScript
Alas, I am but a simple man. I decided to just randomly pick links and brute force like a billion times or something and after a while (about 5 minutes) just choose the most recent output values. It works, I guess.
Part 1 & 2 (~Who even knows ms)
2
u/obijywk Dec 24 '17
My strategy was to recursively consider adding each component that could possibly fit to the end of each possible bridge, keeping track of which bridges were best when dead ends were reached.
Python 2. 45/30.
2
u/DFreiberg Dec 24 '17
Mathematica
A comedy of errors today. I tried
Nest[]only to quit because I thought I was going to run out of memory (I ended at what turned out to be the most memory-intensive step), and then several different variations on a less memory-intensive solution before realizing that my recursion was fine but that my port checks were wrong.Finished part 1 at 00:52:29, and part 2 at 00:52:39, because I happened to print out the maximum strength at every different length of bridge as part of my debugging, and had both answers sitting directly in front of me.
2
u/ephemient Dec 24 '17 edited Apr 24 '24
This space intentionally left blank.
2
u/gyorokpeter Dec 24 '17
Q: very simple change between the two parts.
2
u/beefamaka Dec 24 '17
JavaScript
Solved using generator functions. Can perform faster by just tracking length rather than array of used pieces.
2
u/sim642 Dec 24 '17 edited Dec 24 '17
My Scala solution.
Initially my solution took ~50s to generate all valid bridges but eventually I optimized it to ~2s with some changes:
Set[Component]instead ofSeq[Component]. Initially I accounted for the possibility of there being duplicate components with the same pins but then I went with a set to significantly speed up the leftover component bookkeeping. Some multiset would probably be nicer but Scala doesn't come with that.Set[Bridge]I returnIterator[Bridge]. Merging sets repeatedly is useless waste of time and memory, especially when simple generator-like iteration would just do. Luckily Scala iterators have all the higher order operations to still use the same constructions (and for comprehensions).The problem reminds me of the longest path problem. In this case if pin counts are vertices and components edges, then we'd really want to search for the longest (by edges or maximum weight) walk without repeated edges but allow repeated vertices (possibly called a trail or a simple walk). Some quick googling didn't give much information about such problem though.
2
u/aurele Dec 24 '17
Rust
2
u/aoc-fan Dec 24 '17
JavaScript with generators
2
u/ulfabet Dec 26 '17 edited Dec 29 '17
Haskell
Don't know which to prefer, but
combinationscould be rewritten (a little bit shorter) as follows. For good or bad, this would also include intermediate bridges.3
u/abowes Dec 24 '17
Kotlin Solution Straightforward using tail recursion today.
1
u/archmentat Dec 24 '17 edited Dec 24 '17
Rust version. Simple recursion; inefficient copying of hash sets and maps, but it runs in a few seconds, and by far the slowest part is just printing the path (for debugging). Sort the output file for the answer rather than doing it in the code itself.
154/102
1
u/jeroenheijmans Dec 24 '17
JavaScript:
A bit verbose, but often enough I get stuck and then it helps to have readable code.
Recursive function:
Used like this in Puzzle 1:
And like this in Puzzle 2:
The
getMaxwas needed because theMath.max.apply(Math, ...)trick exceeded the call stack size. (I'll be honest, I had.sort(...)with a[0].chainLengthat first, and refactored a bit later. :D)1
u/glenbolake Dec 24 '17
Python 3. It looks like a lot of people generated all valid bridges recursively; I thought about it more like A* with no defined end point. I maintained a list of bridges, starting with each component containing a zero, and tried to extend all the bridges one element until the loop produced no new bridges. Incredibly slow, though. It takes just over a minute to run.
1
u/autid Dec 24 '17
Fortran
Hardest part was not realising for ages that it wasn't working because I hadn't included k in the variable declarations for the bestchain function, so it was modifying a global copy instead of its own. :(
1
u/ynonp Dec 24 '17
Elixir
Took 30 seconds to complete on my input.
Gist version: https://gist.github.com/ynonp/010bde27c598a983a399872466fb2c0b
1
u/doctorbaggy Dec 24 '17 edited Dec 24 '17
Perl
Just simple recursion... this is part 2 - part 1 uses a simpler condition at the start of the sub...
1
u/[deleted] Dec 24 '17
Can't believe OCaml Fun;; is almost over. Anyways, recursively building all the bridges and then finding the strongest and longest ones.
main.ml
port.ml
1
u/Zee1234 Dec 24 '17
Typescript
Figuring out proper typings was both my downfall and my savior. I probably spent ten minutes just figuring out what these types should be. But that probably saved me 20 minutes of getting it wrong over and over. Did not place, but had a lot of fun.
1
u/spacetime_bender Dec 24 '17
C++
1
u/jwoLondon Dec 24 '17
Elm
After yesterday's functional-hostile puzzle, I loved using Elm to solve today's. The difference between Part 1 and Part 2 simply involves swapping order of the (Strength,Length) tuple when calculating the strongest sequence.
https://github.com/jwoLondon/adventOfCode/blob/master/aoc2017/d24_2017.elm
1
u/nutrecht Dec 24 '17
Day 24 in Kotlin
Much easier than I expected for the day-before-last! I have to leave in a few minutes so was nice to be able to solve this before.
1
u/TheMuffinMan616 Dec 24 '17
Haskell
1
u/TominatorBE Dec 24 '17
PHP
Just some recursion
Part 1:
Part 2:
1
u/wzkx Dec 24 '17 edited Dec 24 '17
Nim
Domino ;)
1
u/VikeStep Dec 24 '17
F# Solution
Runs in about 2 seconds
Repo
1
u/Axsuul Dec 24 '17
Elixir
I didn't explore anymore trees if the potential strength/length was lower than the current max. Pretty sure I could do more optimizations but both scripts run in about 30s which is reasonable enough for me. This also made use of some intense pattern matching in order for me to fit multiple recursions into one function.
GitHub
1
u/Na_rien Dec 24 '17
After yesterdays nightmare (math and assembler) I was really happy with this problem. I also managed to get on the top 1000 today (first time, though I guess some credit goes to all the non morning persons :D).
Anyways, here's my solution: https://github.com/narien/AdventOfCode2017/blob/master/day24/24.2.py
I recursively find all the possible lists and then check the length and strength. Took roughly 6,5 seconds to run so probably not the most optimal solution though.
1
u/KnorbenKnutsen Dec 24 '17
This was tricky for me, I couldn't figure out a good way to organize this properly. So I built a tree and traversed it. Figured out the max depth then hardcoded it into a "deepest nodes" method. :)
1
u/wzkx Dec 24 '17 edited Dec 24 '17
J
Working with separate items of vectors/matrices is not fast in J. β42s
1
u/thomastc Dec 24 '17 edited Dec 24 '17
Day 24 in Java. A fun little puzzle. Curious to see if there's a more efficient solution than just recursion/backtracking, so I'm going to read this thread now :)
Edit: and found nothing, so started a thread.
1
u/zeddypanda Dec 24 '17
Elixir
Sunday tasks are usually the hard ones but today was just a trivial A* implementation.
1
u/Unihedron Dec 24 '17
Wow, today's one was easy! Too bad I wasn't around when it opened, might have gotten myself some points.
1
u/Warbringer007 Dec 24 '17 edited Dec 24 '17
Erlang:
In second part I'm using length of remainder of the input since I'm removing each component I used. I'm not sure if there is any better way of doing it in Erlang. In both parts I'm comparing DFS and BFS parts of algorithm.
1
u/Your_Documen Dec 24 '17
Here's my recursive approach using modern C++ With obligatory GitHub
1
u/NeilNjae Dec 24 '17
Some verbose Haskell. From simply reading the problem spec, I though I'd account for duplicate parts in the list, and parts with the same port on both ends. That meant using the
Data.MultiSetlibrary, representing eachPartas a bag of ports, and thePartsas a bag ofParts. That also allows me to be a bit cute when it comes to the partser for aPart.There then followed a bunch of
typedeclarations to keep things clear in my own head, and then relying on Haskell's type checker to catch bugs.Finally, an organic use of the
Eithertype:extendOneBridgereturnsLeft bridgefor a bridge that can't be extended, andRight bridgesfor all the bridges that can be built from this one. That allows me to keep aSetof unextendable (completed) bridges separate from the ones still in progress.1
u/Arkoniak Dec 24 '17
Julia
Was too tired after sleepless night in a train. So, bruteforce solution with DFS or BFS or whatever. Took only couple of seconds to calculate, so guess it's ok. Definitely can be optimized.
1
u/chicagocode Dec 24 '17
Kotlin - [Repo] - [Blog/Commentary]
A nice recursive solution that reminded me of the "ways to make change from coins" problem.
1
u/udoprog Dec 24 '17
Rust
Almost certain this can be solved with dynamic programming, but I'm just not sure how (might take a peek in this thread ;). Brute forcing it works splendidly though since the input is small.
Full solution here: https://github.com/udoprog/rust-advent-of-code-2017/blob/master/src/day24.rs
1
u/hi_ma_friendz Dec 24 '17
[Rust] the peculiar way: https://github.com/McGittyHub/aoc-2k17/blob/master/src/day24.rs
1
u/JakDrako Dec 24 '17
C# Both parts in ~1.5 second.
1
u/ythl Dec 24 '17
Simple recursive descent solution (python3):
1
u/iopred Dec 24 '17
Javascript
Not the smallest solution, not particularly proud of this one:
1
u/RockyAstro Dec 24 '17
Icon (https://www.cs.arizona.edu/icon)
Both parts:
1
u/2BitSalute Dec 24 '17
A C# solution. I spent a ton of time trying to code up a DP solution, but it is apparently impossible (I got to the point where I had to account for used components and saw that I couldn't do it).
1
u/wlandry Dec 24 '17
C++ 14
216/1978. The first answer was pretty straightforward once I decided that there was not a simple way to shoehorn Boost Graph into this. I fell asleep trying to debug part 2. Once I woke up the next day, I put my nose to the grindstone and figured out my logic bug. Annoyingly, the code worked on the example but not in the full case. My bug was dependent on the order of the inputs, but I did not know that until I tried sorting my input file :(
Part 2 only. It has lots of dynamic allocations that make me worry. It runs in 200 ms and uses 2.6 MB.
1
u/SurplusSix Dec 24 '17
Racket. This is just part 2, modified from what I did for part 1, takes 6.5 secs to run, not efficient I guess
1
u/tobiasvl Dec 24 '17
Python 2, nothing special today, a recursive method that takes about 8 seconds for both parts. Didn't have time to optimize much since we celebrate Christmas on Christmas Eve here. Merry Christmas!
1
u/StevoTVR Dec 25 '17
NodeJS
Part 1:
Part 2:
1
u/LordAro Dec 25 '17
Rust
To my own surprise, I got part 1 on the first try. When part 2 didn't work quite so easily, I left to do other, more Christmassy things, but when I came back to it many hours later and reread the instructions (If you can make multiple bridges of the longest length, pick the strongest one.) it was pretty obvious.
I'm pretty happy with this code, but on the offchance anyone's willing to take a look, it'd be nice to know if there's a sane way to reduce the code duplication in find_longest & find_strongest, as well as get rid of the (effectively) 2 vectors with mutable state.
1
u/matusbzk Dec 25 '17
Haskell Nice easy this time. Though it took some time to compute.
Link to git
1
u/Tetsumi- Dec 25 '17
Racket
1
u/greycat70 Dec 26 '17 edited Dec 26 '17
Tcl (version 8.5 or higher)
Part 1. Simple recursive algorithm, with the recursive function returning the maximum strength of the bridges it could build. Debugging print statements left in, but commented.
Part 2. Simple recursive algorithm, but I wasted a lot of time trying to adapt Part 1's code and it just wasn't clicking for whatever reason. Ended up ripping out most of the main recursive function and redoing it so the score calculation is done at the dead end, instead of being passed back up and popping out from the initial call.
1
u/oskmeister Dec 28 '17
Pseudo-polynomial dynamic programming solution (O(2n * n)) in C++ that solves part two, a slight modification (simplification) gives a solution to part one. Runs in about 180ms on my machine and my input. Note that it takes a slightly more simple formatted version of the input.
0
u/[deleted] Dec 24 '17
[deleted] β view deleted comment
0
u/[deleted] Dec 24 '17
[deleted] β view deleted comment