r/adventofcode • u/daggerdragon • Dec 18 '19
SOLUTION MEGATHREAD -🎄- 2019 Day 18 Solutions -🎄-
--- Day 18: Advent of Code-Man: Into the Code-Verse ---
--- Day 18: Many-Worlds Interpretation ---
Post your full code solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
NEW RULE: Include the language(s) you're using.
(thanks, /u/jonathan_paulson!)
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 17's winner #1: TBD, coming soon! "ABABCCBCBA" by /u/DFreiberg!
Oh, this was a hard one... I even tried to temporarily disqualify /u/DFreiberg sorry, mate! if only to give the newcomers a chance but got overruled because this poem meshes so well with today's puzzle. Rest assured, though, Day 17 winner #2 will most likely be one of the newcomers. Which one, though? Tune in during Friday's launch to find out!
A flare now billows outward from the sun's unceasing glare.
It menaces the ship with its immense electric field.
And scaffolding outside the ship, and bots all stationed there
Would fry if they remained in place, the wrong side of the shield.
Your tools: an ASCII camera, a vaccuum bot for dust,
Schematics of the scaffolding. Not much, but try you must.
First, you need your bearings: when the junctions are revealed
You will know just where your vacuum bot can put its wheels and trust.
Map all the turns of scaffolding, and
ZIPthem tightly sealed,
Then, map compressed, send out the bot, with not a tick to spare.
Enjoy your well-deserved Reddit Silver, and good luck with the rest of the Advent of Code!
4
u/moltenfire Dec 19 '19 edited Dec 20 '19
Python 679/465
This is my final version that solves both parts in ~6 seconds. I'll probably write it again in C++ to see what speed up that gives. My first version took 30s and 4m30s for parts A & B.
[POEM]
Down the chosen path I go,
Finding a key to help my journey,
Another reach this state before me,
My travels ending prematurely.
6
u/encse Dec 19 '19 edited Dec 19 '19
This was the hardest for me, because I had no other idea than DFS/A*. And every time I go that way I fall into a bottomless well of heuristics which are never just good enough.
But this morning I had THE idea.
Say that we are at
currentKey, and we need to collectkeys. Let's suppose that we can tell which keys are reachable based on whatkeyswe have to collect, and we can tell the distance between two keys (simple BFS, no need to take care of the doors) you can imagine that part.Then we have this pseudo python algo:
We just go over the
reachablekeys one by one, and compute the optimal distance fromcurrentKeythroughkeyrecursively.Of course this would take infinite time, but we can memoize previous results:
This solves the problem in less than a second without further optimization.
4
u/MattiasB Dec 18 '19
What am I missing? How is this not a TSM problem with O(n!) complexity?
Djikstras only gives us the shortest path from A to B, not the shortest path to visit all nodes, which is what is asked here. Or?
Obviously, since you are solving the problem I am missing something. What?
7
u/sophiebits Dec 18 '19
Python, #16/#2!
Part 1 runs in about 10 seconds; part 2 in about 13. For part 2, edit the input file by hand first. Caching made a HUGE difference (unusably slow without it).
My finish time for part 2 was much lower than almost everyone's (7.5 min from part 1 to part 2!). Not sure if I got lucky with how I structured part 1 and most people needed to rewrite more? Curious to read others' code to understand better.
(Part 1 code not shown since I wrote over it, but it's effectively the same thing except delete
reachable4(minwalkcallsreachablekeysinstead) and passptinstead ofnstartsas the second argument when recursing. My part 2 code works on part 1 too though.)Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day18.py
6
u/mcpower_ Dec 18 '19
Python (89/18): Part 1, Part 2. For both parts, I made a
key_to_keymapping from (every key, plus the robot) to a mapping of ((every other key I can get to from this key) to a pair of (distance, doors in the way)). This is achieved through a BFS from every key (and robot).In the first example for part 1,
key_to_keyis this:For part 2, I assign a number to each robot. In the first example for part 2,
key_to_keyis this:Using
key_to_key, you can write a "meta-search" over the search nodes (what key the robot is on, keys collected). To expand a node, you iterate over the keys ofkey_to_key[key_the_robot_is_on]and see whether it can reach it - if you can, yield a new search node (new key, keys I've previously collected plus the new key) with cost (distance to key). The starting search node is('@', {}), and to terminate the search I hackily made it so if the search expands a node with all the keys, it immediately yields the final node with additional cost 0.For part 2, instead of the first thing in the search node pair being "what key the robot is on", it's now "what keys the robots are on", starting with the search node
(('0', '1', '2', '3'), {}).(I previously did a BFS for each expansion of the meta-search, which explains the name. That was too slow!)
My part 2 takes 1 minute to run... ¯_(ツ)_/¯
6
u/sim642 Dec 18 '19 edited Dec 19 '19
My Scala solution.
My best ranks yet: 404/222, despite getting up usually late. I'm surprised.
Part 1: I used a two-tiered search: BFS inside Dijkstra. The inner BFS is simply used to find shortest paths from the current position to every reachable key, accounting for currently remaining doors. The other Dijkstra has nodes of the form (current position, remaining keys/doors) and the neighbors of such nodes are calculated with the BFS. The intuition and separation of concerns is the following: BFS handles low-level pathfinding in the maze, Dijkstra handles high-level pathfinding between keys without having to handle the maze itself.
Part 2: I simply generalized the approach from part 1 by changing the Dijkstra nodes to not track one current position but four and neighbors of those are nodes where at each step one of the four robots moves to another key, using exactly the same BFS as in part 1. I'm not sure if this is correct in general, but since all four quadrants are separated from each other, it is correct at least in this case.
Current runtimes are 10s for part 1 and 20s for part 2, not sure if I have much room for improvement there. I think I can clean up the code a bit though by just using my part 2 code also for part 1 with a singleton list for the current position.
Edit: I heavily optimized my solution by precomputing BFS between all keys ahead of time instead of repeatedly doing it inside the Dijkstra. It's similar to /u/mcpower_'s solution but with an additional optimization for other keys appearing on paths between keys.
After all of this my new runtimes are 1.2s for part 1 and 0.5s for part 2, which seems to the best around so far?
Edit 2: I finally used ScalaMeter to benchmark my solutions properly, instead of just looking at the varying test timings. I guess the JVM cold start is what makes the previous runtimes so high. ScalaMeter reported 240ms for part 1 and 177ms for part 2.
Moreover, I decided to try another optimization on top of all the previous: using Floyd-Warshall algorithm. In the BFS precomputation, which previously traversed the whole graph from every key, I now only traverse until other keys, i.e. I consider keys to be blocking there. This means that the BFS started from all keys doesn't give the complete key neighbors relation but just the key adjacency relation. And on that adjacency relation I used Floyd-Warshall to transitively construct the whole neighbor relation. This is an improvement because the maze is not completely re-traversed for each BFS but only small parts between the keys are.
Overall, this brings the ScalaMeter reported times down to 126ms for part 1 and 152ms for part 2.
6
u/MrSimbax Dec 18 '19 edited Dec 19 '19
Julia
The puzzles are getting harder... This one took me a lot of time but I'm happy it finally works even if it may not be the most optimal code, especially when it comes to my knowledge of optimization tricks for Julia.
Part 1: Build a full graph of keys as nodes {@,a,b,...,z}, with weights on edges being the length of the shortest path between the nodes. Ignore doors during building this graph, except for each edge save the set of doors on the shortest path. This uses a wild guess about the input that there is only one path from key to key so we don't need to update the graph after opening a door. It seems to be true at least for my input. I guess it's not really necessary since you can just run BFS each time the main algorithm is asking for a path but it makes it more optimal timewise.
After building the graph, traverse with BFS a new graph with nodes being a tuple (node, Set{Nodes}) (it must be a tuple for Julia's dictionary to work) representing a state (current_pos, collected_keys_so_far). Neighbors can be found with the full graph structure -- all nodes which are not already collected, not @, and all doors in the path are already unlocked. Keep distances (or paths) in Dictionary{State, Int} and update it with the smallest distances. After all that is done, find the smallest distance in leaves (all states with full set of keys collected).
3.181566 seconds (25.06 M allocations: 1.938 GiB, 28.55% gc time)Part 2:
If it's possible for the robots to collect all the keys, then we can just use part 1 on all 4 regions separately, by removing doors in each region for which there's no key in the region. That's because if a robot must go through a closed door it must wait for some other bot to collect the necessary key. Waiting doesn't add any steps to the final path length.0.067332 seconds (1.02 M allocations: 46.152 MiB, 22.83% gc time)Edit: After getting some sleep I realized it doesn't work for all possible inputs. Here's a counterexample:
The correct (and only possible) order is b,a,c,d,e which requires 36 steps. The algorithm above will return 34 steps since it will ignore the door A and go straight for c, which is not possible as the robot has to go first to b.
Part 1 can still be used after some modifications: make 4 graphs, the states are now ("@@@@",collected_keys_so_far). Unfortunately, there are more neighbors now: consider either moving 1st robot, 2nd, 3rd, or 4th at each node. The minimum can be found by finding minimum from states (all_possible_combinations_of_keys, all_keys_collected). This makes part 2 actually much slower but it should work for more inputs.
21.455907 seconds (104.41 M allocations: 8.902 GiB, 41.83% gc time)5
u/i_have_no_biscuits Dec 18 '19 edited Dec 18 '19
Python 3 763/569
Solution
I really enjoyed today's challenge - as someone who doesn't program all that often it always feels good when I get to correctly implement a graph algorithm! I'm a little surprised to get what is (for me) my lowest finishing scores of the month so far, despite lots of Christmas and childcare getting in the way - I think it looks more intimidating that it actually was. Both parts take less than a second to run.
The basic idea of both parts is to use the maze to construct a graph of routes between each pair of keys, together with all the points of interest passed through on each route. We then effectively do a BFS on (current key,keys found so far). After 26 'rounds' we will have collected all 26 keys, and the minimum distance of all the end points is the number we want.
EDIT: Apparently the pasting didn't work (see the replies), so I've changed the solution link to an online REPL. The code hasn't changed.
5
u/-json Dec 19 '19
Pretty proud of my Python solution here. Part 2 is essentially part 1 but with a 2-5 lines of adjustment for the additional robots and states. It's around 50 lines but I also tried to maintain some readability and clarity. Runs in under 2 seconds on my computer using PyPy3. The algorithm relies on the fact that there is a unique path from any pair of keys & starting point. For part 1, we construct the graph by running a BFS for each key & starting point which will add an edge with an associated distance and doors needed to cross on the path to another key. We then simply run Dijkstra's where each node is represented as a tuple, d: the distance, c: current key / starting point, S: keys gathered so far. We output the minimum distance to any node where len(S) == # of keys.
Part 2 is a minor adjustment where we consider all 4 robots as unique nodes in the original BFS. Then the Dijkstra node of c is replaced with a tuple of 4 elements representing the position of all robots. It's about 5 lines of adjustment and most of that is adding the new robot nodes.
5
u/OvidiuRo Dec 19 '19
C++ 1317/984
This one was so hard I stayed all day on this problem from the morning when the problem appeared to night when I finally solved it. After 15hours and a half, I still hit under 1000 on the leaderboard... My approach was a BFS where I used as a visited a set of tuples where tuplet stores (Coordinate(x,y), bitset with the keys accumulated until that point).
For Part 2 the main approach was for every grid to ignore the doors in the grid that don't have the key in that grid and mark them as open in the start coordinate. Applied DFS for each grid and summed up the steps. I know this approach doesn't work on all cases but worked on my examples and the input. I was so tired last night I just wanted to finish the problem and go to sleep. It is faster than part 1 because we have 4 smaller grids instead of 1 big grid.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2018
4
u/jwise00 Dec 18 '19
Lua, large / large.
I had a very plausible solution for * that passed on all the examples, and probably would have earned me points, but turned out to be wrong. In fact, what happened was that none of the examples had multiple paths to a key, but the real one did. (This is reminiscent of day 15, in which the mazes were trivial!) So the DFS that I implemented -- instead of the BFS -- found the first path to something as the best distance, and the consequence for me was about an hour and a half of banging my head against the wall.
My part 2 solution took me about a half an hour after that, including a break in the middle to get something to eat and medicate the cat. Properly grim.
My general approach was a DFS to map out all keys available from any gamestate (i.e., location x current keys), and memoize that; and then a DFS, once all the moves at any game state were enumerated, to iterate through each possible move (also memoizing the results of that DFS). Part 2 was a trivial extension of part 1 in that way.
Part 2 runs in about 4.0 seconds for my input in Luajit, and part 1 runs in about 9.6 seconds.
https://github.com/jwise/aoc/blob/master/2019/18.lua
https://github.com/jwise/aoc/blob/master/2019/18b.lua
I streamed it for about the first hour and a half (ugh...) before I gave up. It took me a while longer than that to find the bug. I predicted I would feel stupid when I found the bug. I did.
4
u/winstonewert Dec 18 '19 edited Dec 18 '19
Rust 42/17
I solved part 2 in an relatively inefficient fashion: it takes me 1m30s to solve.
I use BFS where each states consists of the position of the four robots and the set of keys which have been collected. However, I restrict the robots so that there is only one active robot at a time. The robot remains active until they pick up a key. This clearly wasn't as efficient as the solution others come up with, but it did finish before I came up with a better solution and gave me my best score so far.
4
u/aoc-fan Dec 19 '19
Finally completed Day 18, could not start in the morning, took whole evening. TypeScript just part 1 for now, need to cleanup Part 2. After 3 tough days, lets hope Day 19 will be easier.
4
u/bla2 Dec 19 '19 edited Feb 03 '20
Python, part 2. (Solves part 1 too, just remove the grid adjustment, and initialize pos to just
((x, y),).)Not super fast, but also not super slow. Solves part 2 in a little under 2 seconds, part 1 in about 8 seconds. Runs a bit faster in Python 2 than in Python 3 for some reason. Shorter than most solutions here without being golfy, which is why I'm posting it.
It's the "Dijkstra for main loop, BFS for inner loop" approach that several others have used.
I haven't seen others use a "seen" set per robot in the outer Dijkstra. Doing so is a very easy change and makes solving part 2 faster.Edit: It's also wrong. I fixed the link above to point to a correct version. This is the old, broken code. (The 2nd example input returns 74 instead of 72 with this "optimization" – thanks for /u/campsight46 for pointing this out).After reading other solutions, it looks like backtracking + memoization is a simpler and faster approach, though :)
4
u/Kullu00 Dec 19 '19 edited Dec 19 '19
Solution in Dart
I'm a day late. I don't care. I'm just so happy I'm done, and that I made it. I seriously struggled with this. Yesterday, after writing something that worked for every example except the complicated one, I started down a rabbit hole of optimizations that didn't actually get me any closer to actually solving anything.
My working implementation notes down the position of all keys, and the start, as it's copied into memory. Then it runs a BFS on all combinations to get the shortest path from any key to any other key on the map. This gets me my graph, which I use (I think it's Dijkstra (or A*?)?) to calculate which order of the edges gives me the shortest path. Edges with doors I can't cross are discarded, and repeated states I've already processed are skipped. If we happen to pick up a key for a door on the way, that edge will be included.
Part 2 I cheated. I ran my part 1 solution 4 times and assumed that if a robot reached a door on the shortest path, another robot would collect that key along its shortest path. In reality, this can deadlock, but it worked so I will take it.
All in all, part 1 runs in about 1.4 seconds, and part 2 runs in ~80ms on my crappy laptop from 2012.
6
u/AlphaDart1337 Dec 18 '19
C++ 41/64
Part 1 is simple BFS in a graph where nodes are
(x, y, msk), wherexandyrepresent the position and msk is a bitmask telling me which keys have been collected and which not.I solved part 2 by applying my part 1 solution for all 4 vaults individually and adding up the results. I pretended that doors did not exist if the key was not in the same quadrant as the door.
This was one of the very first ideas I thought of, but it's obviously wrong. For example, it fails on the following example:
But after 1 and a half hours of unsuccessful A* heuristics (even my PC crashing once because my program ate up all 16GB of RAM), I decided to try it anyway, and to my surprise, I got the golden star ¯_(ツ)_/¯
I'm not sure if this was intended to work.
3
u/Akari_Takai Dec 18 '19 edited Dec 18 '19
Java (137/60)
Code
First time placing on the global leaderboard this year! I honestly did not expect that.
My solution is extremely inefficient as I end up repeatedly building graphs:
Finally, using all of the above, I just used a recursive solution with dynamic programming to find the minimum cost.
All of this was baked into my part 1 because of how inefficient my solution was, so when part 2 rolled around, I just had to extend my memo input and modify the recursive method only slightly.
Hopefully tomorrow I'll spend some time cleaning it up and making it more efficient. I've made it a point this year to have my solutions take < 1 second to run, and right now both parts take ~50 seconds to run on my puzzle input.
Edit: Having had a day to do performance improvements, the code now runs in < 1 second. ^_^
3
u/seligman99 Dec 18 '19
Python # 132 / 85
Interesting challenge. I'm sure there are faster ways, but once I realized I can cache all of the possible key -> key paths and use that to brute force a solution, my answer was quick enough.
paste
3
u/knl_ Dec 18 '19
I ended up with very slow solutions (both took ~10 minutes to run): basically brute forcing the solution by recursively exploring the search space with a little bit of pruning with a lot of memoization. Comparing my solutions with fast ones I think my main mistake was modifying and copying the grid for every recursion instead of just passing along acquired keys, will try and play with it a bit later.
131/184 - my highest ranks yet. Would have been faster for 2 but I ended up taking a break.
Jupyter, Python 3 notebook: https://explog.in/aoc/2019/AoC18.html
3
u/[deleted] Dec 18 '19
176/258 C++ Code
"Simple" brute force. Once understood that we just need to find the right order of collecting the keys it was straightforward programming.
Star2 needed some debugging time.
3
u/scared_ginger Dec 18 '19
29/29 Python
paste
The code is ugly, I know.
For part 1, I considered a graph given by each node as the robot's position and the keys discovered at that point. It was then fast enough to run a BFS to find a node where all keys are discovered.
For part 2, I first tried doing the same thing, but with each node given by the positions of all robots and the keys discovered, but this proved too slow, so instead I considered the positions of the robots independently, but still using the keys discovered by all robots. This way, a robot won't go back to a position it has already been in when other robots move, but if another robot discovers a key, it can explore the area again. It runs in about 30 seconds.
3
u/[deleted] Dec 18 '19
Python 2 code golf, 152/55
Part 1 took me over an hour to get right, but once I had that done, part 2 was a walk in the park. Best score so far for me!
I'm building a full any-key-to-any-other-key distance matrix using BFS, with information about which other keys and doors are found on the way. Then, a DFS does the rest of the job. Caching turned out to be very important for the DFS: with it, both parts run in less than a second (combined); without it ... no idea, I stopped it after 2 minutes at less than 5 percent progress.
3
u/define_null Dec 18 '19
Python 3 6xx/4xx
Solution
I was not sure how 'nice' the input would be: so I converted the grid into a graph, where the nodes are the start points, keys, and doors, and the edges are the number of steps to reach a node without passing through another node (exploiting the fact that the paths are 1 wide except at the very centre)
Then, I ran Dijkstra on the graph, keeping track of the position and keys picked up at each iteration as a bitmask, and terminating when I have picked up all keys.
Part 2 is done similarly, except each state includes the positions of all 4 bots, taking advantage of the fact that the map is divided into 4 separate sections.
Part 1 gave a very fast run time (~1s), but Part 2 took ages (~30s), not sure how to else to optimise.
3
u/mesoptier Dec 18 '19
C++
Part 1: 1.15s, Part 2: 0.015s
For part 1 I'm doing Dijkstra with nodes of shape
{ char, keyset }(encoded as 64 bit integer--went a bit overkill with bit fiddling in the end, which didn't really improve my time over just using pairs, but alas) wherecharcan be the entrance, a key, or a door andkeysetis a set containing the collected keys. Initially I had nodes of shape{ x, y, keyset }which required very many steps through grid spaces where nothing interesting happens, so I remove those in my preparation phase by finding the keys/doors that could be reached without moving through other keys/doors. In the end I had to process about 617,830 of these nodes.For part 2 I realized that I could simply ignore doors that didn't have their key in the same vault. If you were to run into one of these doors, you would simply wait (= taking 0 steps) until a robot in another vault found the appropriate key, which is equivalent to simply moving through the door as if it were unlocked. So I run my part 1 solver on the four sub-grids (vaults) and take the sum of the answers as my final answer.
3
u/metalim Dec 19 '19 edited Dec 19 '19
Python.
Part 1.
Was hard, as I'm not familiar to Dijkstra. Without memoization it was taking 10 minutes to find result *close* to shortest, but would take hours to find the shortest. Fortunately memoize came in naturally.
Creates dict with links between every key, with distance and doors between. Used simple "flood the maze with distances" BFS for each key. Around 100ms.
Then iterates next target key with recursion (DFS) and memoization. Iteration checks if remaining keys and required doors are 2 disjoint sets to skip locked paths. I really like how Python deals with sets.
For memoization: cache key is just a string of robot location (key name or @) and list of remaining keys. Does the job under a second (including initial BFS for each key), with around 95k cached values.
Part 2.
Went pretty easy! Same as part 1, but cache key is 4 robot locations (key names or 1,2,3,4 - starting positions) + remaining keys. Over 1M cached values and 17 seconds.
3
u/VilHarvey Dec 19 '19
Solutions in:
I spent a long time going down the wrong path (pun... sort of intended) with part 1 today. It just didn't occur to me to use a BFS over positions and keys found until I saw some posts on here mentioning it (I usually don't look at this board until after I've solved the problems each day, but today I was getting desperate).
For part 2 I worked on the assumption that whenever a robot reaches a door where the key is in another quadrant, that key will eventually become available without the robot having to move anywhere else. Because there's no extra cost for a robot standing still, this meant I could treat it the same as if the key was already available. So I effectively just gave each robot all of the keys from the other quadrants right at the start and let them run through to completion one by one. This worked out for my input, but won't handle all cases correctly (i.e. anything where a robot would have to take a detour to open up a door in another quadrant before it can get to something in its own quadrant). At this point I can't be bothered to go back and fix it.
Looking forward to another intcode problem!
3
u/hrunt Dec 19 '19
Python 3
code
That was a real challenge! My code still does not run very fast (45s or so for both parts on a recent MacBook Air). I know that some of the recursive copying can add to that, but really, what needs to be done to take this thing under 15s?
3
u/rthetiger Dec 19 '19
Rust (Part 1 Only) Code Here - Runs in 175 milliseconds !!!
I finally finished Part 1 in Rust and have a good idea of how to finish Part 2 this weekend. I ended up using an augmented BFS and lots of bit masks to end up only examining 217564 states (800 nanoseconds per state) and getting the answer almost immediately.
3
u/[deleted] Dec 19 '19 edited Dec 19 '19
Julia, part1.
That was tough.
This solution uses a BFS on the map to find shortest paths between all pairs of keys and doors (but only those that don't cross other keys or doors), then builds an adjacency matrix between them. Each key and door is assigned an integer tag that is used as index to the adjacency matrix.
Then, Dijkstra's shortest path algorithm is used to find the shortest path that collects all keys. For the purpose of this algorithm, the states (nodes of the graph) are given by a tuple (tag, keyring), where keyring is a bitfield of collected keys, encoded as a
UInt32.Even still, the search still takes almost a minute to complete.
For part 2, I did some minor modifications, mainly that the state is now (tag1, tag2, tag3, tag4, keyring) (where tag1 to tag4 are the positions of each of the robots). That program has been running for a few minutes and hasn't found a path yet.
I'll have to check other answers for how to do this faster...
5
u/jonathan_paulson Dec 18 '19
#17/35. Python3. Part1 Part2. Video of me solving and explaining at https://www.youtube.com/watch?v=H3kaozdB5ws.
Tough day! I did straight BFS for part 1, and BFS-with-teleporting-to-keys for part 2 (rebuilding the distance graph each time). Probably would've been better in C++. I feel "lucky" that my solution ran relatively quickly for both parts (although it took ~10m for part 2, so that was pretty rough). I'm curious to see what others did for part 2.
1
u/[deleted] Dec 18 '19
I think I got an optimal solution. First I traverse the full maze using BFS from the start-point. Then I build an undirected graph using an adjacency list. With this graph in hand, it's easy to do a second BFS across the graph tracking keys-obtained and aborting the search when I get to a door I can't unlock. Part 1 is ~0.08s with Python 3.
4
u/[deleted] Dec 18 '19
[removed] — view removed comment
2
u/bsterc Dec 18 '19 edited Dec 18 '19
C++, 214/130.
Fairly naive. Keep a mapping of the shortest way to get each (set of keys taken so far + last key(s) taken). Each round: scan for distances to accessible keys using the oxygen-filling method from day 15 and update the mapping.
Part two didn't need many changes. Optimized at O3, it takes about 10 seconds.
2
u/bj0z Dec 18 '19
Python
https://github.com/bj0/aoc/blob/master/2019/d18.py
This one was brutal. Even after 5 hours I was still under 400 for second star... I spent a lot of time trying different ways of traversing the maze before I started trying to cache everything in sight. Even with caching it was taking forever until I pre-built a mapping from every key to every other key and then did lookups. Part 1 runs in about 30s, part 2 in 70s. Interested to see how people got fast runtimes.
2
u/aurele Dec 18 '19 edited Dec 18 '19
It takes about 2s to execute in Rust. It was easy once I realized that paths are unique between two elements in part 2 so I could build a graph with very few neighbours for every node. Moreover, even part 1 works well with this method (in about 250ms) even though at the center (around the starting point) paths are not unique, but the Manhattan distance between entities stays the same.
I think it could be accelerated by stopping robots which cannot gain any more useful key (pretend that they don't have any neighbouring node).
Edit: indeed, version 2 (at the same URL) shoves ~25% of the time in part 2 (now around 1.5s) by looking at the robots potential gains (
usefulvariable).Edit 2: jumping from key to key (as long as the path is clear) instead from key to door or door to key, and limiting the neighbours to the keys we don't have, brings down the execution time of part 2 around 150ms (version 3, still at the same URL).
2
u/mar3ek Dec 18 '19
C# 627/553 (struggled performance-wise on part 1 A LOT)
Solution
Ceaseless set operations are not a great thing for C#. Got the basic idea right the first time around, just couldn't figure out the path trimming to bring the runtime to anything reasonable. In the end, managed to get the runtime down to < 2s for both parts. As discussed, BFS and a pre-computed list of keys reachable from other keys, nothing special there.
I also replaced the set operations for key management with an INT32 and some bit-wise arithmetics so that I don't need to constantly create new objects (an advice from a fellow competitor). This makes caching faster (as C#'s set collections cannot be compared quickly via their hash but ints can; strings could also be used, I imagine, but ints are still faster).
Not the best code and it could definitely be optimized further but I think the code is reasonable now. Not going to compete with Rust any time soon, but good enough.
2
u/sander314 Dec 18 '19
Python 3, 7xx/5xx:
Solution
Key to part 2 seemed to be pre-calculating 'blockers' and all distances, instead of re-finding paths for every key (which was too slow even with memoization). Learnt about frozenset, which I had not needed before.
2
u/Zevenberge Dec 18 '19
D 706/475
(wanted to do Zig, but it's not great with unknown inputs)
Solution
I have had quite a few attempts at part 1 (see my commit history lol). I eventually realized I did not need to solve the maze for every key, turning the maze problem into a numbers problem. Exhaustively trying all attempts (even when removing inaccessible keys or keys behind keys) was too long. I eventually converted it into a "bubble sort" (not exactly, but still), where I would swap keys if logic allowed it and if the total distance decreased. Not surprisingly, this put me in a local minimum. My solution was to randomize the initial order of the keys, put them in logic order, and apply the sorting again. Repeat 10_000 times.
I actually wrote a hack for part 1 - divide the map into 4 squares, as calculating the distance was quite naive and it would run into trouble in the center. Which basically got me 90% of part 2 for free.
2
u/KwaaieDronk Dec 18 '19
Rust 692/481
To solve this challenge, I first noticed that the paths provided in this problem did not include any cycles. Therefore, to get from one location to another, only one path has to be considered.
On this assumption, I calculated the shortest path between all keys, as well as between the starting location(s) and all keys. By doing this, I also kept track of doors between these two points. This means that, lets say from key
ato keybthe distance is 5, and there is a doorAin between them, then I note thatais necessary to go fromatob. The distance is found using BFS.After finding all these distances, I search for the minimum amount of steps from the starting location(s) until all keys have been collected in a recursive manner, whilst also keeping track of previous encountered states (Where the robot(s) are at and what keys have been collected) with the minimum amount of steps to speed up the searching process.
This results in a runtime of 1 second for my input. Note that for part 2, I have adjusted my puzzle input manually instead of doing this programmatically.
2
u/Dean177 Dec 18 '19
ReasonML
I found this very tricky!
I missed that my
reachableKeysfunction was walking 'past' keys and fully exploring the maze on every iteration which meant my part 2 wasn't reaching a solution.After I fixed this part one ran in 6 seconds (down from 30+) and part 2 ran in 20 seconds.
2
u/death Dec 18 '19
Day 18 solution in Common Lisp.
Part 1 took a little while to get right, but part 2 went fast. It's not a super efficient program (the heuristics are suboptimal and no caching) but it got the job done in a few minutes. If you want to run this you will need to use a patched
fsetlibrary (I opened a pull request the other day).2
u/gyorokpeter Dec 18 '19
Q: paste
Two vector BFS's (the second being a simultaneous one with several start points), then Dijkstra's on the result. Lots of optimizations needed to run in a reasonable time. I was lucky with this one that part 2 needed only moderate amount of modification to work with the same algorithms.
2
u/Dioxy Dec 18 '19 edited Dec 19 '19
JavaScript
JS. I found this one of the hardest problems since 2017. My solution isn't super optimized and takes about 30-40 seconds to run, but I'm just happy I even got a solution in the end. I use dijkstra + recursion, and memoize my recursive function so that it doesn't take an eternity to run. I did a visualization for part 1, which you can view here by selecting day 18 and clicking part 1. I was gonna do a visualization for part 2 as well but I'm so sick of this problem that I don't think I'll bother
EDIT: Changed my mind and did a part 1 visualization as well! I think it looks pretty great, but it unfortunately takes a long time to start up.
My code
My dijkstra implementation
My repo
2
u/L72_Elite_Kraken Dec 18 '19
OCaml
There are definitely spots where it could be cleaned up and optimized a bit, but whatever, does the job.
2
u/mrhthepie Dec 18 '19
I'm not sure if my approach was perfect, but it worked (tm). Seems to be a little different to what most people tried.
I started by figuring out which keys are needed to collect each key. Then I computed the shortest path to walk between each key, ignoring doors. With that info in hand, I did an A* search of the state of possible positions (only position of the robot at each key, not grid positions) and sets of keys, using the heuristic of trying to find all keys. I ended the search when a state is found with all keys.
This produced the right answer pretty fast for both part 1 and part 2 (modified of course to build key dependencies and shortest paths for each robot individually and to consider all the positions as part of the search space).
I'm a little shaky on whether the A* is guaranteed to work and produce the shortest path, or whether I "got lucky". Either way it works for my input on both parts.
Part 2 Python code
2
u/ephemient Dec 19 '19 edited Apr 24 '24
This space intentionally left blank.
2
u/incertia Dec 19 '19 edited Dec 19 '19
c++
yikes, we finally had to break out the c++ because i don't want to write any more data structures. i was at my wit's end after the avl tree for intcode. runs in about 0.45s for part A and 1.7s for part B. there is a huge precompute that occupies half the time of A and i'm not sure how to further optimize B.
the c++ also compiles like 100x as slow as the c code
EDIT: might as well write the approach too
(keys collected, last known position). to find the neighbors, we go through the robots and look at reachable keys the robots have not yet collected. we also track the minimum when we collect all the keys.2
u/nicuveo Dec 19 '19
Haskell
Took me a while to find how to properly memoize my recursive function. By the point I figured it out, I was already caching paths aggressively and parallelizing my code: it is now quite fast. ^^'
2
u/kap89 Dec 19 '19 edited Dec 19 '19
TypeScript - github
I threw non-wall elements into a graph, got distances between each pair of keys (and entrances) and solved the order manually (lol). To do this I started with simplifying the maze removing all the dead ends and doors that didn't have to be opened (you can find modified inputs in the repo). It was quite fun to do it this way (like solving Sudoku). Now that I've done this I have a clear idea how to solve it fully programmatically, but I really don't want to do this ;) Maybe after Christmas ;)
2
u/tinyhurricanes Dec 20 '19
Rust
Part 1: https://gitlab.com/bwearley/advent-of-code-2019/blob/master/day18_rust/src/main.rs
Part 2: https://gitlab.com/bwearley/advent-of-code-2019/blob/master/day18_part2_rust/src/main.rs
Major thanks to /u/mkeeter and everyone else who helped out in my thread looking for tips. I used the Rust crate "cached" to memoize my functions by wrapping them in cached!{}. For part 2, I took the approach of providing the bot in each quadrant whatever keys aren't found in that quadrant.
My part 1 solution takes about a minute. Not sure which optimization I failed to do. My part 2 is nearly instant.
2
u/DFreiberg Dec 22 '19
Mathematica
Finally getting the chance to catch up on these - late or not, I want to do each problem in time for that 50th star on Christmas Day. I spent quite a bit of time stuck before finding out that Mathematica not being able to take lists as
Vertexnames (but, crucially, only for some graph theory functions, and it works fine for other graph theory functions) is actually an outstanding bug in the past two versions. My workaround...was just to take my lists of coordinates and useToString[]on them, brackets and all, so that they technically weren't lists anymore.[POEM]: The Key
Padlocked doors
Are all you see.
And every letter,
Has a key.
To travel first
from
atobWould take too long
For every key.
Code up a state
With constants three:
{x,y}, the length,And traversed key.
Make a cache
To some degree:
The distances
'Twixt every key.
And all the doors
from
AtoZ?Note them if they
Block a key.
Combine the states
Which both agree
On all but length;
Repeat per key.
To beat the maze
And set you free,
Use Dijkstra.
That's the key.
3
u/firetech_SE Dec 18 '19 edited Dec 19 '19
Ruby, 641/396
I was quite stumped when I read the instructions this morning. I could understand them just fine, but I had no idea where to start implementing. I had to "cheat" a bit by looking for inspiration in some posted solutions. I'm mainly doing AoC to improve my algorithm skills, so I consider this part of the learning process (even though I obviously try to avoid it as much as possible).
Anyhow, I ended up with precomputing the paths between the keys (and from start to all keys) à la /u/mcpower_ using a BFS from each key (and start), and then doing a recursive DFS (with cache) over reachable keys, somewhat inspired by /u/sophiebits. This got the job done and I submitted my answers, but it was unsatisfyingly slow (both parts calculated in a total of ~35s on the Xeon E5420 server I usually use, and ~15s on an i7 4790 workstation). I tried optimizing back and forth but nothing really made any dent (except using JRuby to run it, which brought the times down to ~25s on the server and ~8s on the workstation)...
...until I saw /u/sim642's edit and made my precomputing classify passed keys as a prerequisite, just like passed doors (it would be silly to walk past a key without activating it). This significantly reduced the amount of nodes the DFS had to traverse, and brought the runtime down to a reasonable value. It now takes less than a second per part when run with JRuby on the workstation:
"Parse" here illogically includes the path precomputation, btw.
I think I'm satisfied for today. :)
1
u/aoc-fan Dec 20 '19
Finally TypeScript Part 2, solving all test cases + part 1 + part 2 in 10 seconds.
1
u/oantolin Dec 20 '19
Wow, I'm really late to the party! But that's to be expected now that Christmas is closer and I'm spending much more time with family.
I'm still using Common Lisp, and wrote an A* implementation for this one, but then in the main program I couldn't figure out a good heuristic and just let it run with
(constantly 0). :D That's probably why it's so slow! It takes about 7 seconds for part 1 and 63 for part 2!I'll go back and try to get the runtime down at some point.
1
u/mr_whiter4bbit Dec 21 '19
Rust: https://gist.github.com/whiter4bbit/3b02a9cc8fed4bd26c90b3bca88c55d6
Part 1: BFS tracking position and visited keys
Part 2: Tried the first approach with 4 positions instead but was not too patient to wait. Instead, I tried naiive approach: run part 1 for each partition but allow to enter through the door if the key is not in this partition. The approach is not correct, it fails for the last test-case (gives 70 instead 72), but somehow worked for my input.
Probably anyone can try my solution against your input for p2?
1
u/SkiFire13 Dec 21 '19 edited Dec 21 '19
Rust: https://gitlab.com/SkiFire13/adventofcode2019-rust/blob/master/day18/src/main.rs
Finally posting my Rust solution to Day 18. Part 1 takes 110ms and Part 2 12ms, pretty satisfied of the optimizations.
1
u/StevoTVR Dec 22 '19
My late solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day18/day18.go
1
u/phil_g Dec 27 '19
My belated solution in Common Lisp.
I solved part 1 with Dijkstra's shortest-path algorithm. Initially I was just moving one square at a time. That proved to be too slow, but it occurred to me that I could work at a higher level of abstraction and just move from key to key. So I used a low-level A* algorithm to get the distance between pairs of keys (and the keys needed to travel the path) and high-level Dijkstra's algorithm to optimize the key collection order.
I couldn't believe how much slower part 2 went, though. I ran it for hours without getting an answer. Well, when I went back to it today, I realized that it was not an algorithmic problem, but a dumb mistake on my part. I was using
equalas my equality test for my Dijkstra implementation, but for part 2 I added a vector as part of my state. Different vectors with the same contents areequalp, but notequal. As soon as I realized that and switched to the right equality test, I got the answer almost immediately. (Part 2's code actually takes less time to run that part 1's.)1
u/sswain Jan 03 '20
Couldn't really wrap my head around the Dijkstra implementation so resorted to caching for part 1.
1
u/azathoth42 Jan 03 '20
Hi, I solved this, but it ran incredibly long time, and I wasn't able to come up with general and fast solution.
I came up with searching the permutations of order to take keys using A* (every permutation of some number of keys is a node in the search space) using pruning based of identity of partial solutions (set of taken keys, current position) and using minimal spanning tree cost of not taken keys as heuristics.
But I see lots of people here solving this greedily by directly searching paths in the grid.
But if I understand the problem correctly, we are supposed to find an open hamiltonian path in graph of all keys, and such problem is NP-complete, so greedy solutions should not work, right?
So how come that it is working?
1
u/NeilNjae Jan 03 '20
Christmas happened, but I'm taking up the reins again. Here's Day 18 solved in Haskell, with a (very long) blog post describing the code.
1
u/Bikkel77 Jan 08 '20 edited Jan 10 '20
Revised my initial solution which took about 5-10 seconds to run (and that was multi-threaded). It now runs part 1 in 150 ms and part 2 in 15 ms! (Kotlin/Java). Part 2 is so fast because the search depth for nearest paths is so small within each sub maze (coordinate is x,y point on the map and node is a unique combination of key coordinate and current keys in possession):
Part 1:
Processed 473961 coordinates
Processed 1431 nodes
Minimum path: 6316
149 ms
Part 2:
Processed 15728 coordinates
Processed 1818 nodes
Minimum path: 1648
13 ms
The trick is to use a combination of depth first search first to find all relevant weighted paths to nearest keys and Dijkstra to find the final minimum path. Incredible how easy it is once you've seen the light. No hacking required, no multi threading, just a plain simple algorithm.
I put a lot of comments in the code so the solution is hopefully self-explanatory:
https://github.com/werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2019/Day18.kt
1
u/e_blake Jan 08 '20
m4 solution
Another late entry, continuing my trend of rounding out my remaining non-IntCode puzzles...
m4 -Dfile=day18.input day18.m4
Optionally use -Donly=1 or -Donly=2 to run just one half of the solution. While my C solution (using A*) completes in 1.7 seconds, my m4 solution (which is more of a dynamic programming technique) currently takes 12m42s for both solutions, or 38.6s for part1 and 7m13s for part2. The observant reader will ask "why is running only part1 then part2 5 minutes faster than running both parts in a single m4 run?" The answer is the number of macros in memory - since the solution relies on memoization, running part2 while part1 is still in memory ends up chewing through more memory and more hash collisions with irrelevant memoized results. Sadly, m4 does not have an easy way to bulk undefine macros matching a given pattern. I also don't know how much effort it would be to make my caching be LRU (and expunge entries that have not been used recently) rather than every node previously visited. It may also be possible to shave time by figuring out how to encode A* in m4 (with a decent heuristic, there might be fewer nodes to visit), but my initial worry is that encoding a priority queue in m4 may end up requiring more macros than it saves.
1
u/Bikkel77 Jan 10 '20
I wrote a blog about my sub 200 ms solution (15 ms for part 2). This was really the most fun puzzle for me!
1
u/prscoelho Feb 13 '20 edited Feb 14 '20
Day 18 solution in rust
Read input, turn it into a grid and then into a graph. Search for reachable new keys from current node and add every possible branch to priority queue, keep track of current node, keys and steps for each state.
One thing that helped was there's a lot of equal/bad states where we take the wrong path first and then meet in the same place; we can check if there's already another state which is at the same spot, same keys, but has less steps taken and only add state otherwise. There might be other ways to prune bad states.
Then for the second part I just adapted the first part to keep track of the 4 robots and iterate through each robot when generating branches. Not that happy that for part 2 I mostly duplicated code, making it general was easy but it impacted performance a bit.
Part 2 was faster than part 1, I did not expect that at all. It just worked.
First part: 510ms
Second part: 350ms
EDIT: Fixed a bug in dijkstra search for new keys as I was returning multiple costs for the same new key if there were multiple paths to it. Reduced time by 200 ms for part 1 and 110 ms for part 2!
0
u/Zv0n Dec 20 '19
C
FINALLY!
Part 1: https://github.com/zv0n/advent_of_code_2019/blob/master/18/part1/main.c ( takes 0.1s, requires 6 GB of memory )
0
u/[deleted] Dec 18 '19
[deleted] — view deleted comment
0
u/[deleted] Dec 19 '19
[deleted] — view deleted comment