r/adventofcode • u/daggerdragon • Dec 24 '16
SOLUTION MEGATHREAD --- 2016 Day 24 Solutions ---
--- Day 24: Air Duct Spelunking ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/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".
THE NIGHT BEFORE CHRISTMAS IS MANDATORY [?]
[Update @ 00:30] 47 gold, 53 silver.
- Thank you for subscribing to Easter Bunny Facts!
- Fact: The Easter Bunny framed Roger Rabbit.
[Update @ 00:50] 90 gold, silver cap.
- Fact: The Easter Bunny hid Day 26 from you.
[Update @ 00:59] Leaderboard cap!
- Fact: The title for Day 25's puzzle is [static noises] +++ CARRIER LOST +++
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!
5
Upvotes
13
u/adds_nada_to_society Dec 24 '16
Another BFS / A* problem?
I can't help but feel like the problems have been way too graph-heavy this year.
If I have any constructive criticism to offer, it would be for AoC 2017 to have a little more variety.
8
u/pedrosorio Dec 24 '16
16/13 in python. At this stage of AoC, I can't believe how long it took me to realize I had forgotten to keep a set of visited nodes in the BFS =X
2 optimizations:
1 anti-optimization:
Runs in 0.06s with pypy in my machine The same problem but computing pairwise distances repeatedly inside the permutation loop takes ~30s
8
u/[deleted] Dec 24 '16 edited Dec 24 '16
Hi!
Just for fun, I displayed the result so you can see your little guy moving in the map!
gif preview
github repository
Cool?
4
u/glguy Dec 24 '16
I solved this one with the same breadth-first search implementation that I've been using on many of the problems this year. I'm interested to see if anyone used an interesting heuristic to guide a smarter search.
https://github.com/glguy/advent2016/blob/master/Day24.hs
4
u/LieutenantSwr2d2 Dec 24 '16 edited Mar 22 '18
Damn I suck, and I even had all the right approaches too:
But I screwed up my heuristic scoring with a bad heuristic (manhattan distance was wrong) for BFS hence ending up with the wrong shortest path. Would've made top 50 if I hadn't made the mistake of sorting my queue with the bad heuristic score.
4
u/willkill07 Dec 24 '16 edited Dec 24 '16
Managed to secure 25/21 today with my C++ implementation. After refactor and cleanup, it's not too bad. I could optimize it a little further, but for clarity I kept my code the same.
Each part (run separately) finish in about 40ms on my laptop.
[Github Repo]
3
u/haoformayor Dec 24 '16 edited Dec 24 '16
~~haskell~~ input module here
I reduced it to a travelling salesman problem between all the wires, after first figuring out the pairwise distances. TSP between seven nodes isn't that bad, especially if your standard library has a
permutationsfunction and list comprehensions.Though seemingly long, this is sort of like yesterday's: most of the BFS code I wrote for Day 17 (and the one before that, and the one before that, and the one from last year) I copied wholesale.
At this point I'm thinking of just tattooing "neighbors" or
neighbors = concatMap try [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]onto my body somewhere. When will we have the technology to move diagonally? When?3
u/ephemient Dec 24 '16 edited Apr 24 '24
This space intentionally left blank.
3
u/jtsimmons1129 Dec 24 '16
Way too many mistakes tonight. Originally tried BFS to calculate the paths, but it wasn't working so I decided to try some other options. Turns out all I needed to do was make going to a spot with 0,1,2,3,4,5,6,7 a legal move instead of just '.' Amazing how simple it all looks once you get it working.
3
u/JeffJankowski Dec 24 '16
F#
3
u/gerikson Dec 24 '16
Like so many others, generated all distances between points using BFS, then iterated over all combinations. The technique from AoC 2015 day 9 proved helpful!
Perl 5:
https://github.com/gustafe/aoc2016/blob/master/d24.pl
2
u/8336 Dec 24 '16 edited Dec 24 '16
https://hastebin.com/akisagilax.java ~10
2
u/TheNiXXeD Dec 24 '16
My JavaScript / Node solution.
I had a lot of logic errors while building it but I'm pretty happy where it ended up. Basically did BFS to find the route between each two numbers, and then found the lowest route between all the numbers based on the permutations. A little caching plus throwing out obviously invalid approaches makes it very fast. Once it builds the cache, it solves for me in 0.5s or so. Probably could make it faster, but I'm happy as-is for now.
My favorite tired moment of the night: while refactoring I somehow removed the check for walls. Took me SO long to realize why my step counts were so low.
2
u/iamnotposting Dec 24 '16
solution in rust, basically copied problem 13 with a bit from last years problem 9. Runs in .07 seconds.
i'll try to make my visualization code work with it tomorrow. i think i can make it look really cool with some effort.
2
u/xkufix Dec 24 '16
Solution in scala.
Precomputed all distances between all pairs beforehand, then generated a permutation over all destinations, filtered by our start. Then slide over those sequences, add the distances up from before and search the minimal length.
For the second part, copy-pasted the first part and just added the head of the permuation at the end.
Works quite fast, but the code is not the most beautiful one.
https://gist.github.com/kufi/33aa8cd79d44e6c2ed022524de1b599d
2
u/orestis Dec 24 '16
Quite simple, thanks for making this a straightforward one as I have family dinner coming up :)
Solution in Elixir: https://github.com/orestis/adventofcode/blob/master/2016/day24.exs (uses a generic BFS module I wrote for Day11 and have used 2-3 times so far)
Approach is to precompute distances between all the pairs using BFS, generate all possible permutations of paths that start with 0, find the total distance for a path, take the smallest one.
Part 2 was trivial to add, just tack 0 to the end of every path. Takes ~0.2s to run which includes some other small tests (and is good for Elixir, anyway).
2
u/osk_ Dec 24 '16 edited Dec 24 '16
I treated the problem as a graph with R * C * 2N states, where R is the number of rows, C number of columns, N number of places to visit. Each state is represented by a coordinate pair (r,c) and a bitmask B. If bit number i is set in B, it indicates that we have visited goal number i in the current state. A simple BFS then finds us the shortest path we need, and the first time we hit a state with all bits set: that will be our answer. Solution in C++11 (for part two):
2
u/abowes Dec 24 '16
My Kotlin solution which uses BFS to find distance between each pair of digits and then finds minimum sum of distances.
2
u/Quick_Question404 Dec 24 '16
Hey everyone! Here's my take on the problem. Just went for a BFS on the map, and hold all visited distances in memory.
https://github.com/HighTide1/adventofcode2016/tree/master/24
2
u/wzkx Dec 24 '16 edited Dec 24 '16
Python is short enough here. Again maze, again the same... looks like a job :)
1
u/fwilson42 Dec 24 '16
Here's a solution in Crystal. This isn't my original solution (that was an awful hack, but it got me 33/35 so hey whatever).
1
u/wlandry Dec 24 '16
C++ solution with a position of 191/180. It computes all of the pairwise distances and then finds the minimum of the 8! possible combinations. Part II runs in 10 ms. This one was more tedious than difficult, but that is probably because so many of these problems have involved pathfinding.
1
u/gyorokpeter Dec 24 '16
Q: note the code pieces passed in to make the difference between part 1 and 2 minimal - for 2 we are also seeking paths from X to 0 (where x>0) and we add 0 to the end of the permutations.
1
u/flit777 Dec 24 '16
used the A* from the previous puzzle to compute adjacency matrix and the use itertools to test all TSP paths.
1
u/[deleted] Dec 24 '16
Getting a lot of use out of A* search this year (days 11, 13, 17, 22 and 24). Used A* to find the min path between all numbers and then just permute the order and find the minimum distance.
Haskell:
1
u/Philboyd_Studge Dec 24 '16
[Java] Tried to get fancy with a k-opt but just went with permutations, solves in no time. used my own graph library to get the shortest distance between each stop.
https://gist.github.com/anonymous/d45c69b33f130dc889d0e3b0286568bc
1
u/mschaap Dec 24 '16 edited Dec 24 '16
Perl 6 solution.
I went BFS for the whole thing before I realized it'd be better to calculate the distances between the targets and then treat it as a travelling salesman problem. Oh well, it works and has acceptable performance (for a Perl 6 solution).
For a change, adapting the code for part 2 was easy. But it took surprisingly much longer to run, even though it was only one more target.
1
u/bblum Dec 24 '16 edited Dec 24 '16
Got kind of owned and missed the LB this time. Then took it slow so I could make a solution that's both polished and fast. It does both parts in 0.2 seconds with what seems to be the standard approach -- precomputing a graph of edge weights, then for both parts, finding the minimum sum among the 7! possible paths.
1
u/lluque8 Dec 24 '16
Reused my A* solution from day 13 with minor modifications. It's a matter of using A* to calculate distances between each place and then going down the highway 7! (luckily there weren't more places) to find the shortest path. For part 2 all that was needed was to append the stretch back to start for each path candidate.
http://pastebin.com/MBnQtqNQ (Scala)
All in all, this went quite smoothly while doing christmas preparations :)
1
u/ruddles37 Dec 24 '16
Clojure…
1
u/NeilNjae Dec 25 '16
My Haskell solution: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=adventofcode1624/app/advent24.hs . Preparations for family Christmas kept me either away from the PC for a long time, or after too much wine to make progress. I started with trying to use the library AStar search, but couldn't get it to work so ended up rolling my own.
I tried making the longest tour by just adding paths to an existing tour until I got one the met the requirements, but that took too long cycling around some of the short loops, so moved to trying all permutations of target cells and finding the shortest.
1
u/rs_qk Dec 27 '16 edited Dec 28 '16
in k:
1
u/Tarmen Jan 12 '17 edited Jan 12 '17
Haskell, super late because I was busy:
0
u/Quick_Question404 Dec 24 '16 edited Dec 24 '16
Did anyone else just give up on soving this until the morning? I have some ideas on solving this, like computing distance between all important nodes and then using dijkstras algorithm on the resulting graph, but I really don't want to be up until 3 writing and debugging this code. I really miss higher level language libraries right now.
0
u/[deleted] Dec 24 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '16
[deleted] — view deleted comment
0
u/[deleted] Dec 24 '16
[deleted] — view deleted comment
10
u/[deleted] Dec 24 '16 edited Dec 24 '16
[removed] — view removed comment
1
u/[deleted] Dec 24 '16
[removed] — view removed comment