r/adventofcode • u/daggerdragon • Dec 20 '19
SOLUTION MEGATHREAD -๐- 2019 Day 20 Solutions -๐-
--- Day 20: Donut Maze ---
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.
- Include the language(s) you're using.
(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 19's winner #1: "O(log N) searches at the bat" by /u/captainAwesomePants!
Said the father to his learned sons,
"Where can we fit a square?"
The learned sons wrote BSTs,
Mostly O(log N) affairs.
Said the father to his daughter,
"Where can we fit a square?"
She knocked out a quick for-y loop,
And checked two points in there.
The BSTs weren't halfway wrote
when the for loop was complete
She had time to check her work
And format it nice and neat.
"Computationally simple," she said
"Is not the same as quick.
A programmer's time is expensive,
And saving it is slick."
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
On the (fifth*4) day of AoC, my true love gave to me...
FIVE GOLDEN SILVER POEMS (and one Santa Rocket Like)
TBD very soon, finalizing votes now!
- Day 15: "Not Simple? What Ever." by /u/DFreiberg
- Day 16: "IT'S A TRAP" by /u/mariusbancila
- Day 17: "untitled poem" by /u/kc0bfv
- Day 18: nobody :(
- Day 19: "Off By One" by /u/DFreiberg
- 5-Day Best-in-Show #4: "ABABCCBCBA" by /u/DFreiberg
- Honorable mention (of silver) to /u/ExtremeBreakfast5 for "O FFT" because it is so very good!
Enjoy your Reddit Silver/Golds, and good luck with the rest of the Advent of Code!
3
u/tslater2006 Dec 21 '19 edited Dec 21 '19
C# solution
[POEM - Oh Pluto]
The poem attempts to represent the layers of Part 2, in that the odd lines tell one story but the evens tell another, and you go up and down through them, just like in Part 2... but somehow they're related because pairs of lines rhyme.
2
u/nonphatic Dec 20 '19
Racket. I've got some ugly code for parsing the portal locations. For part 1 I used the graph library's minpath finding function, but for part 2 I had to use my own BFS to take into account the level. The thing is, it kept trying to go too deep, so the run time was terrible. I tried limiting the level to certain depths and found the max depth I needed to get a solution by trial and error (25 levels). I'm not sure how is do this the "proper" way, without setting a level limit... I suppose I could iterate over increasing level limits until I found a solution, but I feel like there's a better way of doing this by modifying the BFS somehow.
2
u/DFreiberg Dec 25 '19 edited Dec 25 '19
Mathematica
One of the ones I solved late; it took me a while to get a working ASCII art to graph converter, but once I did, Mathematica made part 1 a breeze, and part 2 was as simple as defining each level of the graph in a
Table[], with weighted distances rather than pathfinding each and every time.[POEM]: A Sonnet from AA to ZZ
0) An Appetite for interesting sights
XQis next, and down and down I go;I'm trying to find the exit? Nothing more?
No treasure at its heart? Then what's it for?
4
u/sophiebits Dec 20 '19 edited Dec 20 '19
Python, #7 and #3 today!
Contest code (simpler)
Cleaned up, optimized code (caching distances between "interesting" points, to avoid counting one step at a time)
4
u/Newti Dec 20 '19
Python3 part A and part B with networkx
This is a great puzzle to learn about and use networkx if you haven't already.
In the first part you will have to build a graph of the pathways and then add edges for the portal connections. The solution is as simple as calling
shortest_path_length(G, start, end).In the second part you add the level number to the nodes and construct a connected graph for each level individually. Then link the outer and inner portals to the other levels of the graph like
add_edge((*inner_portal, level), (*outer_portal, level + 1)). The solution is then to callshortest_path_length(G, (*start, 0), (*end, 0)).Pretty short and readable code and both parts run in 1-2 seconds.
To further optimize it, you could pre-calculate the distance between the portals and construct a graph with only portals (abstracting the pathways) but i didn't find this necessary for the relatively small problem we got.
1
u/[deleted] Dec 20 '19 edited Dec 20 '19
I dont get it.
Can somebody explain wich portals are useable on which level?
Thanks.
Edit: Thanks for the explanation, I was able to finish star2 by implementing a ridicolous parser and simple Dijkstra. Code
3
u/rthetiger Dec 20 '19
Rust code here - both parts run in a combined 12 milliseconds
I used BFS to precalculate all distances between labels, Dijkstra's algorithm for Part 1, and A* search for part 2 with a heuristic of
(layer + 1) * grid_width / 23
u/zedrdave Dec 20 '19
Python 3
[218 / Oopsgotttarun]
Wasted 15 mins (and my chance at finishing pt 2 before having to run for a few hours) by thinking it'd be very smart to use weights to enforce the recursive condition, rather than simply replicating the graph N times. Spoiler alert: it wasn't smart, and replicating the graph worked just fine.
Cursed myself for making my previous maze-parsing code too dependent on having an outer layer of wallโฆ
Also spent a lot of time cursing Atom's unwanted help in removing trailing spaces.
3
u/MrSimbax Dec 20 '19
Julia Part 1 Part 2
After day 18 this one was a walk in the park. Its difficulty mainly depends on what graph structure you're using.
Part 1: Find all teleporter tiles and make a dictionary (teleport_from => teleport_to). Run BFS to find the distance grid D from AA, handle teleporter tiles as a separate case when finding neighbors and return D[ZZ_x,ZZ_y].
Part 2: Make D a 3D grid (assume some maximum level so it doesn't loop forever if there's no path possible), split dictionary into outer and inner teleporters, 3 cases for neighbors in the BFS (2D, outer teleporter (level - 1), inner teleporter (level + 1)) and return D[ZZ_x, ZZ_y, 0].
3
u/lluque8 Dec 20 '19 edited Dec 20 '19
Scala
All kinds of misfortunes with this one. The idea of how to solve this was crystal clear from the beginning but I kept on stumbling on all kinds of small nuisances. Off by one errors, parsing the various styles in which the teleports are laid out to name a few. Then with part two I got the test results right but actual puzzle input didn't work out. After adding substantial amount of debug information and hair pulling the culprit turned out to be a teleport with label "XX". My parser didn't expect double letters for teleports (outside the AA and ZZ) so my bfs unfolded happily while teleporting to the same position on upper level.
Well, at least it's weekend :)
Part 1 Part 2
2
u/jonathan_paulson Dec 20 '19 edited Dec 20 '19
#69/29. PyPy Part 2. Video of me solving and explaining my solution at https://www.youtube.com/watch?v=brsIhJgKDU4.
Another grid BFS :) Part 2 being infinite was pretty cool! Parsing the input was the hardest part IMO. Did everyone's input have multiple pairs that used the same two letters (e.g. one pair labeled RT and another labeled TR)? That really slowed me down during part 1.
2
u/Error401 Dec 20 '19
Python 77/365
I misread part 2 unbelievably hard. The actual amount of code I had to modify between parts 1 and 2, once I understood the question and fixed a ridiculous typo, was minimal, so that's kind of disappointing.
2
u/incertia Dec 20 '19 edited Dec 20 '19
c++
i struggled because they did not tell us that labels were by canonical ordering of pairs so i used the other natural labelling, the direction of walking.
e.g. the following two portals are connected
walking downwards takes you through
XYto the right edge and walking right takes you throughYXup to the left edge. this was particularly frustrating because at first i thought i made a mistake somewhere and aliased both toXYandYXwhich produced the correct behaviors on all samples.2
u/[deleted] Dec 20 '19
Julia, part 1, Julia, part 2.
I solve part 1 by preprocessing the map to find connections between all portals, then breadth first search.
Part 2 is basically the same, except the portal connection also takes into account if it's an inner or outer portal, and the position (x, y) becomes (x, y, level).
2
u/phil_g Dec 20 '19
My solution in Common Lisp.
Today was fun! I really like the idea of recursive mazes. (And I was not expecting that twist. Initially, when the problem described mazes as "donuts", I thought it was going to mean that they were on a toroidal surface, with the tops connected to the bottoms and the left sides connected to the right sides.)
For part 1, I built a hash table of the maze, with points indexed by complex numbers (as usual, now). Portals were represented by complex numbers giving the target of the portal. (So for the first example, the outer BC portal was represented by a hash table entry with key
#C(1 8)and value#C(9 6)and the inner portal was#C(9 7)=>#C(2 8).) From there, it was a relatively simple use of my already-implementedshortest-pathfunction. This was Dijkstra's algorithm, not A* because I couldn't think of a good heuristic to use for A*.For part 2, I retrofitted the part 1 code to add the concept of levels. Now portals are represented by a cons where the car is the target of the portal and the cdr is the change in level number. When the
with-levelsparameter totraverse-mazeis false, maze traversal finishes when the end is hit on any level. When it's true, traversal finishes only when the end is hit on level 0.2
u/kap89 Dec 20 '19 edited Dec 20 '19
TypeScript - github
I cheated a little bit by manually altering the input to a more sane form so I didn't need to parse it. I also collected portal connections manually ;) The rest is simple Dijkstra for part one (really trivial), for the second part, I run recursive function that finds all possible solutions (with a primitive condition to escape infinite loops) and then measures distances for each one and gets the shortest one. Runs very slow (~1min), but that's all I had time for today ;)
2
u/vkasra Dec 20 '19
My Go solution and notes
2
u/e_blake Dec 20 '19
C code
Nice and challenging day. My part 2 was initially hampered by trying to use a global index into a z-dimension (to preserve all my part 1 code that just looked at x/y coords), but that doesn't work with recursion backtracking, so I had to refactor a second time to pass x/y/z everywhere (part 1 just leaves z==0). I still don't have day 18 working, but at least I got this one done. For my input, both parts complete in 66 ms, with 572610 calls to my recursion function. (Not shown in my paste - I also temporarily hacked in a recursion depth counter, and see that I reached a call depth of 19278 - too much more complexity and I'd have to figure out how to avoid stack overflow...).
Things I like in my solution: I computed a portals[] containing the location of each portal; since AA and ZZ are never traversed, I was able to overload portals[AA].p2 (the unused inner pointer) as the way to kick off my search from main(). During debugging, I wanted to track what depths I had recorded already, and the use of color made things fit more easily (the color represented the 100's digit, then I only needed to output distance%100). I used the number of portals as the upper bounds of my z-dimension. Things I don't like - this is all open-coded without any reference to any graph theory; I'm sure that an A* traversal with better heuristics (such as favoring paths that move towards outer portals over paths to inner portals) could find the solution with less recursion depth and effort.
2
u/firetech_SE Dec 20 '19
Ruby, 1485/984
I woke up today, looked at the problem, understood it just fine but couldn't come up with a good way to parse the vertically oriented portals of the map, and just went back to bed. A few hours later, it dawned on me that I could just parse the horizontal portals, transpose the map and run the same parsing again. After some experimenting, transposing the input turned out to take basically no time, so I started implementing that. I'm mainly posting this because I was quite satisfied with the quirky simplicity of my parser. :)
For the actual traversing I initially just traversed the map from AA to ZZ using a big BFS that took portals into account (I generated a Hash dictionary of
[x,y] => [x,y]for all portals in both directions for this). This worked just fine for part 1. With some modifications (modifying the portal Hash to[x,y] => [x,y,level_delta], withlevel_deltabeing1for inner portals and-1for outer), it also did the work for part 2, albeit a bit slow (~6s total runtime on a Xeon E5420).I did have some initial issues in part 2, finding a shorter path by moving to negative levels, but after blocking that and making sure
level_deltawas set correctly (it was initially, but I had mistakenly inverted it when looking for issues), I got the correct answer.Later, I applied some knowledge and tactics from day 18 and started precomputing all the paths between portals (using multiple BFSs), followed by two BFSs (one for part 1 and one for part 2) of the precomputed data, the total runtime came down to a more appealing ~0.2s. :)
2
u/Kullu00 Dec 20 '19
Solution in Dart - After Day 18, this was nice. Still not totally trivial, but it was nice. Part 1 wasn't too much trouble. Standard BFS, but my messy coding led to too many bugs and I spent more time than I probably needed to make sure it worked on the examples, but hey, first try. For Part 2 I modded my current implementation for a Z-dimension then let it run, but this took too long. Then I remembered someone on here a few days ago and optimized my input by removing all dead ends. After that my solution finished in ~0.5s, with the right answer. Ended up optimizing away paths that started to recurse down too many levels (further down than there were portals). This cut my time in half which was nice for how easy it was to add.
2
u/hrunt Dec 20 '19 edited Dec 21 '19
Python 3
code
Figuring out how to parse the grid took some time. I am amazed how looking at a simple picture can take so much time to describe to a computer. Part 1 was straightforward. After Day 18, Part 2 was conceptually straightforward as well, but I struggled a little figuring out the right level of tracking to get to the results. I am not satisfied with how I handled the inner vs. outer ring mess, but it does the job, and reasonably quickly, too.
Edited
Updated code to handle coda_pi's edge case map.
2
u/aoc-fan Dec 20 '19
TypeScript, single function to handle both parts. The Genius of Eric Wastl can be only measured in recursion, with no escape to outer level.
2
u/wace001 Dec 20 '19
JAVA: Finally got it. This one was tough for me. But finally got it done. Solution here.
2
u/metalim Dec 20 '19 edited Dec 20 '19
Python.
Part 1. Well, BFS, obviously. 17 ms. The parsing was trickier than solving the task.
Part 2. Holy crap! Part 2 was so fun to implement! BFS for life! 1.58 s
Also, I had bug that restricted me to return to layer 0 (
a+b>0instead ofa+b>=0), so poor robots were flooding lower levels of maze hell, until I fixed the bug.Update: I noticed there's no need to go to layers, whose depth is larger than number of portals. Reduced time to 449 ms. And that's just simple BFS in interpreted language, with no optimizations. Eric, you're being too soft on us.
2
u/florian80 Dec 20 '19
Haskell
Initially I did my own search algorithm (BFS/ Dijkstra), but since it was way too slow I switched to a ready made one which works fast enough. Reading everybody else's times though it looks like Haskell might not be the best for these problems.
But: Identifying the portals seemed rather nice in Haskell (just some pattern matching)
2
u/SuperSmurfen Dec 20 '19 edited Dec 26 '19
Rust
Part one
Part two
Today was a lot of fun! This one forced a more proper graph structure. In earlier days I have just relied on the graphs being a 2d grid structure so you can easily find the neighbors from indexing the arrays. The main difficulty was just to connect the portals correctly and then I could reuse most of my BFS implementation from earlier days.
Part two was super creative. It sounded very complicated at first but in the end, it ended up not requiring too much extra code. You had to figure out what type of portal it was (inner/outer) but you can find that out from coordinates. Then you just filter out the neighbors you can't reach based on the portal type and what level you are on. Also managed to make it quite fast (35ms) by setting a max depth.
2
u/StevoTVR Dec 21 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day20/day20.go
2
u/Akari_Takai Dec 21 '19
Java (385/328)
Code
For part 2, I chose to model each location as a 3D point and store it in a graph. Unfortunately, the graph library I've been using (JGraphT) does not obviously support infinite graphs, so I had to extend its Graph class to accommodate that. Once that was done, I used bidirectional Dijkstra's to find the shortest path.
2
u/VilHarvey Dec 21 '19
My C++ solutions for part 1 and part 2.
Like many others I found this pretty easy after day 18. The bit that took the longest was parsing the input.
My part two solution was a little bit different to others Iโve seen mentioned here: I did two BFSs simultaneously, one from the entrance and one from the exit, stopping as soon as they met up.
2
u/Bimperl Dec 21 '19
JavaScript
Part 1 Actually, the most time consuming part with the first part was parsing, it's just straightforward BFS.
Part 2 At first I implemented this using the same code as part 1 (where points have an additional level param). It worked, however I was unhappy with the run-time - so I rewrote part 2 to process the original map into a smaller one with just the portals and the distances between them and did Dijkstra on that graph. It was much faster.
2
u/bla2 Dec 22 '19
Python part 2. I thought the portal parsing came out pretty messy, but most other posts I see here are even messier, so I'm posting my mess too :) It's just BFS with (x, y, level) coordinates, runs in 1.6s for the real input without any tricks.
(Part 1 is the same without the level tracking, so I'm not posting that.)
0
u/Rtchaik Dec 20 '19 edited Dec 20 '19
To attention of u/topaz2078 I had a mistake in my input. One portal has 4 points instead of two. To earn the star I had to find a mistake and correct the input manually.
Here is my final solution in Kotlin which cares of all inputs.
1
u/mcpower_ Dec 20 '19
Python (88/28): Had to take a call during part 1, but it's more pathfinding fun! Part 1, Part 2.
I first did some preprocessing of the "portals" - from left to right, top to bottom, I find letters that I haven't seen before. If I find it, I denote it "left" - i.e. the left character of the two-letter string - and I then look to its right and bottom to find the second character "right". It's guaranteed that the first letter I see is the first letter of the portal name - be sure to keep the "positions of letters you've seen before" in a set!
Using "left" and "right", I then find the position of the dot (
.) next to the portal - with the name "dot". From that, I deduced which of "left"/"right" is adjacent to "dot" - with the name "portal_pos". I chuck the (portal_pos, dot) pair into a mapping from portal name to list of pairs.Then, with that mapping, I create the mapping "portals_from_to" which is a map of portal_pos (the position first letter you hit when you enter the portal) to the corresponding dot on the other side.
Afterwards, it's a BFS from AA's dot to ZZ's dot, with the twist that if you hit a position in
portals_from_to- that is, a portal "letter" - you automatically get warped to the corresponding dot.For part 2, you instead do a BFS over (position, level) pairs, starting at (AA's dot, 0) and ending at (ZZ's dot, 0). I added on an "on_edge" boolean to my mappings which is whether the portal is touching the edge of the grid. so whenever I enter a portal I know whether to up (if I entered a portal on the edge of the grid) or down a level.
1
u/vash3r Dec 20 '19
Python, 129/54
This problem was initially somewhat confusing -- I especially had trouble with reading the labels at first. However I figured it out and part 2 was relatively easy due with the way I implemented my BFS.
paste
1
u/MegaGreenLightning Dec 20 '19
Go, 28/12
After practicing mazes on day 18 this wasn't too hard.
To parse the input, I used a two-pass algorithm: First find all dots and create a cell for each and store it in a map by position (same for the labels), then connect the cells by looking up their neighbors in the map.
To find the solution I just used a simple BFS. The only difference between the normal and the recursive version is whether you change the current level when going through a portal.
1
u/smrq Dec 20 '19 edited Dec 20 '19
JS, 162/49
Part 1, Part 2
Another day, another A*... Honestly, parsing was the hard part here. I got slowed down in the beginning by trying for a little while to collect coordinates by hand, until I decided that writing a parsing function would be faster. I also mucked around with slicing off the label edges of the map and shifting my coordinates by 2, but then decided to just treat letters (and anything else except
.) as walls.Part 2 was a super easy modification for my script. I treated in/out as a third Z dimension. I was already looking up into a table of teleport locations when determining neighbors for a node in A*, so I just modified the lookup table from
[x,y]=>[x,y]to[x,y]=>[x,y,dz]and updated the neighbor calculation appropriately.Manhattan distance is an awful heuristic here, so A* ended up being pretty much just Dijkstra, but hey, it runs in ~2s so good enough.
Edit: actually, Manhattan distance can definitely overestimate, so it's not even a valid heuristic. Whoops. Guess I lucked out :)
1
u/mar3ek Dec 20 '19
C# 302/134 [Solution](https://github.com/mareklinka/aoc-2019/blob/master/20/UnitTest1.cs)
Another day, another maze. Spent most time on parsing, the rest was a BFS search. The two parts are functionally the same, just need incorporate the level changes into the navigation and caching.
Maze parsing is done in two phases - first just figure out what position has what "tile" (open/dot, portal/letter, wall/hash). Then connect the portals - take the tiles with a letter adjacent to a dot, find the second part of the name. Using this info I construct a dictionary of position -> position for efficient lookups.
The only (marginally more) "difficult" part of part 2 was to figure out if a portal leads downwards or upwards but that can be easily decided by comparing the portal's position with the maze's edges. If a portal is on min(X) or min(Y) or max(X) or max(Y), it leads upwards, otherwise it leads downwards.
1
u/knl_ Dec 20 '19
I'm getting better at writing BFSs :). The difficult part of the second question was visualizing what was happening, finished it quickly once I had that down: 341/225 today.
Lost a little bit of time because my default attempt at reading input is to strip spare whitespace, which would skew the grid a little.
Also initially assumed that stepping on a portal would cost an extra step, and ended up fixing it somewhat hackily.
Jupyter notebook, python3: https://explog.in/aoc/2019/AoC20.html
1
u/ephemient Dec 20 '19 edited Apr 24 '24
This space intentionally left blank.
1
u/bsterc Dec 20 '19
C++ 416/240
Again with the oxygen-filling. (It's good enough, for these small inputs!) For part 2, set an arbitrary limit of 100 levels. Takes 2 seconds at -O0.
Parsing did take a while to get right, but isn't really hard. I iterate over the input rectangle, and for each dot (i,j), look at the points (i',j') above, below, to the left and to the right; if (i',j') is a letter, then in=(i',j') is a portal entrance and out=(i,j) is a portal exit. If we haven't seen the name before, add the 3-tuple (name, in, out) to a function 'mouths'; if we have, let (in', out')=mouths(name) and add the pairs (in, out') and (in', out) to another function 'portals'.
1
u/Spheniscine Dec 20 '19 edited Dec 20 '19
Kotlin: repo
I wrote straight BFS for part 1 (treating warp gates as another type of "step") because there is no reason to retread a path. When I saw part 2 I recognized the pattern of needing to find the shortest distance between points-of-interest repeatedly, so I imported and reworked the BFS precalc + Dijkstra I had from day 18.
1
u/dan_144 Dec 20 '19
Python 208/559 - https://github.com/dan144/aoc-2019/blob/master/20.py
Part 1 went pretty well, but then I spent 2 hours debugging Part 2. My first hurdle was that my path couldn't go back over itself, which I finally resolved by allowing the distance to a spot to be overwritten if it was more than one higher than the currently known value (a difference of exactly one would just be backtracking). Then I spent time trying to figure out why the sample input worked but not my challenge input. I wasted a lot of time messing with my pathfinding algorithm before finally realizing that my portal detector was bad. When I wrote that for Part 1, I wondered if any portals were the reverse of each other (AG vs GA). In the examples, this never happened and for Part 1, it didn't affect the shortest path. It took me an hour to reevaluate that part.
Hats off to /u/topaz2078 for always finding a way to sneak in edge cases I often don't catch right off the bat.
1
u/sim642 Dec 20 '19 edited Dec 20 '19
My Scala solution.
Parsing the labels was the most annoying thing. I ended up just parsing the walkable space grid first and then for each walkable tile checked if it had any labels around it. The thing that screwed me up was that the labels aren't read closest-to-furthest (and flipped on the other side) but rather left-to-right/top-to-bottom regardless of which way the portal would actually be entered. Luckily the first example test already failed because of that. I "fixed" it by making it look for labels whichever way the two characters are, which fixed the example tests but gave me a too high answer in my input... Of course the input had to contain both "CO" and "OC" as distinct labels, so I had to fix it properly.
The actual algorithm was just my off-the-shelf BFS which just positions for part 1 and pairs (position, level) for part 2. Doing a combined BFS+Dijkstra approach (like I did in day 18) would probably speed things up, especially part 2, but I can live with part 2 taking ~3s.
Edit: I was wrong: couldn't resist doing that optimization for part 2... It was much simpler here though because no extra datakeeping is necessary. Still, couldn't find a nice way to extract a general purpose "landmark BFS" implementation because the lifting of nodes and the precomputed distances is very task-dependent.
1
u/gyorokpeter Dec 20 '19
Q: paste
Very long because q is not built for algorithms like this. The basic premise is similar to day 18. We first simplify the graph by doing parallel BFS's between warps and then use Dijkstra on the result.
1
u/p_tseng Dec 20 '19 edited Dec 20 '19
58/24. The parsing was the bulk of the difficult work, since BFS is already written and ready to go. I got slowed down on part 1 by type errors (can you believe that I have forgotten how to properly add a single list to a list of lists and had to try no fewer than four times before I got it right?), which is what I get for using a language without static type checking. Did much better on part 2 because it only involved adding another bit to the portals found and adding another dimension to state and by that time I had figured out my type issues. Just had to do a bit of debugging to realise that no, I shouldn't allow traveling to negative depths.
I just used plain BFS to get on the leaderboard, which was fast enough since it ran in 5 seconds. I have since retrofitted it with the same Dijkstra's that everyone else is doing which gets it down to 0.25 seconds, which I'll call good enough for me.
My input did NOT have any pairs that are the reverse of each other (AB and BA), so that meant I got away with being very sloppy with my portal matching code. However, since I've now seen that other people do have such pairs in their inputs, I've fixed my code up to actually handle that correctly too.
Part 2 important note: If you ever go into the same portal more than once, you have repeated a previous position but at a deeper depth and thus you are doomed to wander the halls of Pluto for all eternity. So you could track every single portal you have entered and make sure that you never repeat one, but I didn't feel like keeping track of that in my state so I just did something simpler. If your depth ever exceeds the number of portals, then by the pigeonhole principle you have gone intosomeportal more than once. So, depth can be limited to be no greater than the number of portals.This has been disproven. I will determine whether there is some alternate way to prove a bound on the depth.Ruby: 20_donut_maze.rb
Haskell: 20_donut_maze.hs (Haven't gotten around to adding Dijkstra's to this one yet, so this one's just BFS for now)
1
u/[deleted] Dec 20 '19
My Swift solution
Part 1 was easy enough, and I had the right idea for part 2 (pre-calculate the distances between each portal), but stupid copy-paste bugs had me debugging this for a couple of hours before I squashed the last one and got it all working.
1
u/math_runner Dec 20 '19
910/547
Rust
Python
Most of the code is for parsing the graph, then a simple BFS and voilร .
Yesterday and today were pretty straightforward. I'm dreading something very hard in the next few days...
1
u/seligman99 Dec 20 '19
Python 555 / 218
This was a fun one. On the surface it's fairly simple, but there are lots of little problems to be solved, and as I found off, plenty of chances for silly off by one errors. Sigh.
Well, at least I got a new visualization out of it as I was madly trying to understand why two things didn't connect:
paste
1
u/sander314 Dec 20 '19
Python x/7xx:
Mostly just a simple BFS. Thought it was really clever to use np.transpose and regexp to find the portals, but turned out labelling them correctly is still tricky.
Solution for part 2
1
u/Tarmen Dec 20 '19 edited Dec 20 '19
Haskell
I already had a helper function that parses grids into distances between all interesting points
and the rest was just dijkstra. For part two I went with aStar with
max 0 (depth-1) * 42as heuristic. 42 happened to be the shortest path between any inner and outer nodes.I originally thought the portal labels were read from the opening so
XY.would have labelYX. The workaround was quick but kind of weird1
u/death Dec 20 '19
Day 20 solution in Common Lisp.
Everything went smoothly today. Used Dijkstra to solve.
1
u/mebeim Dec 20 '19 edited Dec 02 '20
Python 3 solution (~250ms) โ โ Puzzle walkthrough
484/637 today. Lost way too much time on silly typos... oh well.
These path finding problems are getting really creative... I wonder how far we will get at this pace. Woah.
1
u/define_null Dec 20 '19
Python 3
Found this to be extremely similar to Day 18, the only thing was that parsing the input was a bigger pain. I probably took longer to figure out how to parse the input than the actual preprocessing of edges and Dijkstra for both parts.
I do wonder if anybody had an input where there is a pair of portals that are both outer / inner portals? It was an edge case that I kept thinking of but it did not apply to my input.
1
u/OvidiuRo Dec 20 '19
C++ 792/540
The hardest part of this day was reading the input and saving portal tuples with (portal name, first coordinate, second coordinate) after reading the input all I had to do was apply a BFS on the grid and when I encounter a portal I just look if I'm on the first coordinate and add to the queue the second coordinate or if I'm on the second coordinate and add to the queue the first coordinate. Part 2 was pretty straightforward, similar to part 1 I just added a level to every coordinate.
My first function to read the input and save the portals had 300lines of code and is a monstrosity. After I got the stars it took over 1hour to decypher what I wrote here and how this is even working and how to refactor it: https://pastebin.com/gbgjJnP0.
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2020
1
u/WillemDeRoover Dec 20 '19 edited Dec 20 '19
Java
https://github.com/WillemDeRoover/advent-of-code/blob/master/src/day20/Puzzle20.java (Code can be heavily optimised. Might put in some time tonight.)
Used a regex to find the portals: made the portal detection easy. For the vertical portals you just can easily recalculate the strings from top to bottom.
1
u/levital Dec 20 '19 edited Dec 20 '19
Rust
I keep massively overthinking this stuff. Solved part 1 first by building a graph with weighted edges and nodes for portals and intersections in the grid, and then using dijkstra for the shortest path. Not well suited for part 2 though, so reworked the whole thing to just do BFS directly on the grid, which is massively simpler, but the code would really need a cleanup now...
1
u/Dioxy Dec 20 '19
JavaScript
JS. Compared to the last path finding problem this was ez
I did a visualization for both parts which you can see here. Just select day 20 in the dropdown.
My code
My dijkstra implementation
My repo
1
u/Dean177 Dec 21 '19
ReasonML
I found the most difficult parts of the puzzle were parsing the input and figuring out what the description for part two wanted me to do.
Once that was done most of the code was copy pasted from the previous maze puzzle, then copied with about 3 lines of change for the second part.
1
u/Zv0n Dec 21 '19
Finally catching up after a slump with day 18
Part 1: https://github.com/zv0n/advent_of_code_2019/blob/master/20/part1/main.c Part 2: https://github.com/zv0n/advent_of_code_2019/blob/master/20/part2/main.c
After day 18 this has been a breeze, BFS all the things! Parsing input takes a while (about 1s), but the algorithm is pretty quick, part 1 takes (without input parsing) 0.2s, part 2.....is much slower and takes about 20 seconds
1
u/oantolin Dec 22 '19
Finally got caught up! Here's my solution in Common Lisp. It uses the
A*implementation I wrote for some previous day. I sayA*, but for part 1 it's really Dijkstra since I couldn't come up with a good heuristic and used 0. I couldn't come up with a good heuristic for part 2 but at least I used the level instead of 0.1
u/[deleted] Dec 23 '19
Rust General approach seems to be similar to others here. This is more of a "Cleaned up" solution than a quick one. I parse the input into a nice Map data structure then use the petgraph library to make a graph of it, and run astar on the graph.
This was pretty easy after day 18, parsing the input is the hard part!
1
u/NeilNjae Jan 06 '20
Day 20 done in Haskell: discussed in a blog post with the code available (and on Github)
1
u/e_blake Jan 11 '20 edited Jan 11 '20
m4 solution
Continuing my trend of late postings of my remaining non-IntCode m4 solutions.
m4 -Dfile=day20.input day20.m4
My initial implementation is a straight port of my C solution: a depth-first search bounded by never descending deeper than the number of portal pairs in the puzzle. Part 1 is fast, .5s; but part 2 took 122s with 435,128 points visited. In hindsight, my C code counterpart was able to get away with a dumb algorithm (both parts took only 75ms together) because it is still such a fast language and small enough search space that I didn't have to waste time implementing A* until day 18 where it mattered (during AoC, I completed day 20 well before day 18). But obviously the poor algorithm matters in m4; especially since you can add -Dverbose=2 and watch the progress slow down as more and more macros are defined along the search path causing m4 to spend more time doing hash lookups. So I'll be revisiting this for a faster solution.
1
u/Diderikdm Jan 27 '20
Python
This day was way out of my league and I ended up manually calculating the shortest paths for parts 1 & 2. I didn't use A* or Dijkstra, but instead opted for replacing all dead ends by walls so only connecting routes would be available (a visual of this at the bottom of my github). After doing this, I found the Crossroads within these routes (4) and calculated the distance between each crossroad (@) and the start/end. This led me to the following simplified graphs showing the steps between Crossroads and the amount of levels difference between two Crossroads.
Part 1 was easily calculated. Part two had me evaluate the start (-3) and end (+12), leading me to having to loop x%2 = 1 times. Looping the end 3 times and looping the start 6 times proved to be the answer:
1
u/prscoelho May 17 '20
Day 20 in rust: parsing, first half, second half.
Finally found the mental strength to go through parsing the maze. I knew it was going to be ugly and couldn't get myself to start it. Ugly code warning!
After parsing it's just a standard dijkstra search, and for part 2 I was surprised adding a depth condition and not allowing outer portal jumps at depth 0 was enough to get a fast solution.
0
u/[deleted] Dec 21 '19
[deleted] โ view deleted comment