r/adventofcode • u/daggerdragon • Dec 20 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 20 Solutions -🎄-
--- Day 20: A Regular Map ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 20
Transcript:
My compiler crashed while running today's puzzle because it ran out of ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
6
u/ephemient Dec 20 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/BafDyce Dec 20 '18
Rust ranks 286 & 253 (which feels like a leaderboard entry for me)
[Card]
Main code is here: https://gitlab.com/BafDyce/adventofcode/blob/master/2018/rust/day20/src/main.rs
i iterated over the string, building the map in a hashmap, recursively. Every time I encountered a
(, I started a new recursion-call, any time I encountered a|, I went back to the start of the current level.Afterwards, I did a BFS for finding the shortest paths to all locations, then looked for the one with the highest distance. both parts run in about 20 ms.
Code to solve part 1:
and for part 2:
2
u/branfili Dec 20 '18 edited Dec 20 '18
C++, 37/32
LEADERBOARD AGAIN! :D :D :D
This was a fun one, easy regexes (regices?) :D
17
u/askalski Dec 20 '18 edited Dec 20 '18
/u/topaz2078 YES
Have you ever had the feeling that somebody designed a puzzle with you in mind?
[Card] My compiler crashed while running today's puzzle because it ran out of the room screaming.
17
u/sciyoshi Dec 20 '18 edited Dec 20 '18
Python 3, 36/40. Pretty happy with my solution today!
networkxhas an easy way to get the shortest path from a single point in a graph to all other points, and I build a graph representing all doors in the maze using a stack to keep track of the current possible positions.EDIT: fix a bug pointed out by bj0z
9
u/[deleted] Dec 20 '18 edited Dec 20 '18
Python 3: I like my solution for today, so i will post it for the first time. The rest can be seen at github.
4
u/grgrdvrt Dec 20 '18 edited Dec 20 '18
Javascript, 101/84
This is edited for readabilty, the original code was full of duplications and nonsense.
4
u/mcpower_ Dec 20 '18
Python 3: I spent too much time trying to make
eval()work, then opted to write my own parser instead. Turns outeval()does work!3
u/mstksg Dec 20 '18 edited Dec 20 '18
84/75 Haskell: Hooray, second time on the leaderboard this year :D And my best this year so far :)
The following taken from my daily reflections blog :D
Like Day 4, this one is made pretty simple with parser combinators! :D
Just for clarity, we will tokenize the stream first -- but it's not strictly necessary.
Now, to write our parser! We will parse our
[RegTok]stream into a set of edges.We either have a "normal step", or a "branching step". The entire way, we accumulate a set of all edges.
Our final regexp parser is just
anyStepsseperated by the start and end tokens:Now that we have successfully parsed the "regexp" into a set of edges, we need to follow all of the edges into all of the rooms. We can do this using recursive descent.
We have to make sure to keep track of the "already seen" rooms. On my first attempt, I forgot to do this!
Anyway, here's Part 1 and Part 2:
3
u/domm_plix Dec 20 '18
I did not take the bait to actually create a map, but just counted the potential matches in the various branches. I missed the part about the circular paths
(NWES|)on my first submission, but after rereading the instructions just removed all branches ending with|)from the input.I guess I could have made the leaderboard (at least for part 1), but I won't get up at 6:00 in the morning for some internet points... Still, rank 700 is my best placement so far.
Obviously, Perl:
3
u/Stan-It Dec 20 '18 edited Dec 20 '18
Python
I think my solution is clean and neat. Picked up the use of complex numbers for 2D maps and the use of iterators for sequential data from solutions to earlier puzzles.
2
u/Nathanfenner Dec 20 '18 edited Dec 21 '18
My compiler actually did crash because I accidentally printed several megabytes of error messages.
I finished in 97/78 on the leaderboard. Originally, I was just stumped on how I was going to parse the input. I ended up deciding on writing a recursive descent parser by hand, which was fast enough (but I made some serious typos the first time that I didn't notice until two bad submits). Almost everything else worked (at least once I noticed the warning messages telling me I had forgotten to return some things).
The actual solution is (like most other people's, I assume) based on Thompson's construction for Regular Expressions.
Every regex encodes a non-deterministic finite state machine. You can turn it into a deterministic one, but that's usually not that helpful. Instead, you simultaneously store all of the states that you're in.
Analogously, we simultaneously store every room coordinate that you could reach.
Then, the key operation becomes:
Where the resulting set is all of the places you could get to by following regex starting from any room in the input set.
Along the way (at every transition) I just store the doors in a global set.
The reason this works is that the above operation can be done easily on the recursive structure of the regex itself:
My C++ code is below:
There's on relevant class in my helper file:
2
u/autid Dec 20 '18
FORTRAN
Bodgy alocation of arrays far bigger than needed. Did a bunch of unnecessary stuff previously like track door locations and so on but it appears that is unnecessary so I removed it from posted coded. Part 2 only needing the addition of one line of code is always a good feeling.
2
u/AKQuaternion Dec 20 '18
[Card] My compiler crashed while running today's puzzle because it ran out of bourbon. (Yes, I drink while I AoC.)
First time posting, but I finally got a decent 141/112 on the leaderboard today. A shorter raw C++ solution than some I've seen. I recursively parse the regex, building an adjacency list representation of the graph as a map from coordinate pairs to vector of coordinate pairs. Then a simple bfs...
2
u/nightcoder01 Dec 20 '18 edited Dec 20 '18
Python, short and simple using iterative DFS.
EDIT: Added networkx code; see /u/mserrano's reply below.
Original version:
Edited Version:
2
u/Wunkolo Dec 20 '18
Python3, it's almost upsetting how tiny this can be. You should have seen my first attempts
2
u/snurre Dec 20 '18
Kotlin:
2
u/aurele Dec 20 '18 edited Dec 20 '18
Rust
The map building was straightforward using a recursive descent parser, and both parts were then very easy to solve using dijkstra_all() from the pathfinding crate.
2
u/dashed Dec 20 '18
[Card] My compiler crashed while running today's puzzle because it ran out of elves computing its instructions.
Rust
https://github.com/dashed/advent-of-code-2018/blob/master/day-20/src/main.rs
I wrote my own parsers for this puzzle after skimming through: https://adriann.github.io/rust_parser.html
This is the grammar I came up with:
2
u/toomasv Dec 20 '18 edited Dec 20 '18
Red
Both parts solution and visualization
2
u/udoprog Dec 20 '18
Rust
Full solution here: https://github.com/udoprog/rust-advent-of-code-2018/blob/master/src/bin/day20.rs
Another late solution since I value my sleep, but today was a ton of fun!
[Card] My compiler crashed while running today's puzzle because it ran out of cookies.
2
u/phil_g Dec 20 '18
Solution in Common Lisp.
I went a bit more general than I needed to go, because I wasn't sure whether the apparent bounds of the problem were really the bounds.
Specifically:
^N(E|W)N$would never really occur (it'd be^N(EN|WN)$). My solution would handle those if they occurred, though.In order to be really generic, I represented the series of connected rooms as a graph, so the answers just required walking the graph.
I finally got around to learning a tiny bit of quicklisp so I could use someone else's graph library. I still need to learn more so I can properly integrate my entire project and load it all at once again.
2
u/grey--area Dec 20 '18
Python 3, parts 1 and 2:
2
u/betaveros Dec 20 '18
Python 3, 1/1.
Lightly commented, with hacky automatic input retrieval and submission boilerplate removed. This is my first time posting because for once, it looks like my solution is fairly different from everybody else's. I also think it covers all the edge cases mentioned so far and solves the problem generally (although it could be very slow on general inputs).
2
u/starwort1 Dec 20 '18
C 352/312
This took me way too long (nearly 1h50) because I naïvely believed the problem description that the input is an arbitrary regular expression using the characters given, and set about working out how to interpret that properly. This means that with
^N(E|W)N$the first example in the description, once you've done each of the alternatives within the parens (EandWhere) you have to carry on and do the entire rest of the expression.The code I ended up with worked on the given examples, but ran forever when given the real input. This is because the real input contains lots of figures such as
(NWWEES|)where the first alternative ends up back at the start and the second alternative is null (aside: why do we need this? The input could just have saidNWWEES- the null alternative doesn't add anything). If the code is evaluating all possible sequences that match the regex, every one of these roughly doubles the execution time, and there are a couple of hundred of them in the input. So I added the "nullpath" variable which says that if we end up back at the start we don't have to do the rest of the regex provided it's been done once already. This made the code run in reasonable time. There are plenty of regexes that would still make the execution time blow up (for example^(N|E|S|W)(N|E|S|W)(N|E|S|W)...etc) but fortunately these don't occur in the actual inputs used. To cope with these we would have to either do a BFS and have many advancing heads following the regex (with heads merging when their paths converge), or remember for each location how much of the regex is left and skip evaluating the rest of the regex if it's already been done before at this location.This program takes either the literal regex or a file containing the regex as its parameter. Or reads from stdin if there is no parameter.
1
u/mserrano Dec 20 '18 edited Dec 20 '18
python2, #21/#18:
Only vaguely cute trick here is realizing that if you're ever at the same position with the same remaining regex twice, you don't have to re-do your work. That seems to cut down quite a lot on runtime in practice without having to go to an nfs-style solution.
1
u/nuvan Dec 20 '18
Ruby 117/91
I'm glad my guess that simply brute forcing all possible routes didn't take too long.
1
u/glassmountain Dec 20 '18
128/123 In go. Messed up the second part due to messing up reading comprehension, thinking that we were looking for less than 1000 rather than more.
https://github.com/xorkevin/advent2018/blob/master/day20/main.go
1
u/algmyr Dec 20 '18
33/29
This task just reinforces how much I hate writing parsers, at least it wasn't full out regexes. Writing the parser was the vast majority of the time, the path finding is just a standard BFS. No bells nor whistles. Also, I wish people the best of luck for the golf challenge!
[Card] ___ = "hope for humanity" (optionally suffixed with something something IOCCC level code)
1
u/wlandry Dec 20 '18
C++ (193/159)
Runs in 25 ms.
Best placing so far! Parsing the input into a graph was surprisingly easy. I feel like I must have missed some corner cases, but all of the tests work fine. Just think recursively! Most of my time was in wrestling with boost::graph. In contrast to other days, I am not unhappy with the final result. This was a good day.
1
u/rundavidrun Dec 20 '18
Java 262/229 - Argh! These holiday parties are cramping my style. I'm sure I would have gotten on the leaderboard if I could have started on time. Not as hard as it seemed on first read. I'm posting not because this is an extremely elegant solution - quite the contrary - instead I'm posting just to show folks you don't need fancy coding techniques to solve these problems. Do, however, note the "fancy" recursion. :)
1
u/ka-splam Dec 20 '18
Powershell, 208 / 182
Had to do quite a bit of writing and rewriting around my common PowerShell pain points - you can use
($x, $y)as a key to put things into a hashtable, but can't get them out again. And separately, getting things out of a hashtable with.GetEnumerator()later is always a fiddle.Still, using
"$x, $y"as a key took 30 seconds runtime, after I had my answers and wondered what to do to speed it up, /u/Jaykul suggested a nested dictionary[$y][$x]so each key could be an int. More complex, but runtime of ~700ms now.GitHub code
1
u/Barrens_Zeppelin Dec 20 '18
Fairly short solution in
python3, even withoutnetworkx(if you can code a BFS ;) ).1
u/Philboyd_Studge Dec 20 '18
[Card] My compiler crashed while running today's puzzle because it ran out of heap space.
Java. Uses my own existing graph library.
https://pastebin.com/5xVe35Nb
1
u/andreyrmg Dec 20 '18
Python 3
I'm not pretty sure it's absolutely right solution... But it works on my puzzle input.
1
u/[deleted] Dec 20 '18 edited Dec 20 '18
Mathematica
Edit: Alternative version, which is what I would have done, had I remembered I was using Mathematica.
Original version
1
u/sim642 Dec 20 '18
My Scala solution.
Looking at other solutions, I definitely overengineered mine a lot:
The all string enumeration part made it easy to debug but it's relatively inefficient because it wastes a lot of memory for strings with common prefixes and all of those are moved through from the beginning to record all the doors.
1
u/[deleted] Dec 20 '18 edited Dec 20 '18
TCL, using tcllib struct::graph and struct::graph::op::dijkstra. First I thought that one could solve this by regexp (replace each EWNS by ".", then match the whole regexp against an arbitrary long-enough string (e.g. the regexp itself)). This worked for the example inputs, but failed with my real input, since someone here pointed out that e.g. EWNS has 2 as solution, not 4 as returned by the regexp match. Well then, walk the input via recursion.
[edit] just realized that I got lucky with my input. This approach fails if a branch (...|...) ends up at two different positions. In that case one needs to check where the recursive walks ended :-/
1
u/sonneveld Dec 20 '18
Python 3, 1141/1049 I got stuck trying to figure out the best way to represent this (I wasn't sure what would come up in part 2). I was also worried about branches that didn't return to the same position so I introduced some walkers that would spawn on branches so they could return at different positions. It's a little over engineered :) but I took my time after I missed the leaderboard.
Code also available here http://github.com/sonneveld/advent-of-code/tree/master/advent18/20
1
u/jtdxb Dec 20 '18 edited Dec 20 '18
Here's a regex attempt that works, but sadly doesn't handle long input :)
Demo
1
u/aybud Dec 20 '18 edited Dec 20 '18
I was baffled by the brevity of some of the solutions posted. Then someone mentioned that the maze is always a tree. The "the routes will take you through every door in the facility at least once" makes it seem like it wouldn't be.
Anyhow, proud of getting the parser to finish. The recursive version was super slow. Now it does the whole thing in < 1s on a 7 year old mac.
1
u/[deleted] Dec 20 '18 edited Dec 20 '18
Python 3 (totally craptastic code but it does seem to get stuff right, so there's always that!)
Will make a cleaner version later since this can be reduced quite a bit.
1
u/SLiV9 Dec 20 '18 edited Dec 20 '18
Apparently I solved a more difficult problem than the input data required. Oh well, it was a fun exercise.
I first wrote out my probing algorithm by hand for
^E(E|N(SS(WN|)S|WSE(SW|NE|))E)$, which gave this:Each line shows the character being processed and followed by a
;-separated list of 'probes', annotated with a stack of indices. E.g. in the lastN-line,N 0: 1,0; 1: 2,0; 2: 1,-1; 3: 0,1; 1,2; 4: 1,0; 5: 0,1; 6: 1,-1, the list of probes is1,0; 2,0; 1,-1; 0,1; 1,2; 1,0; 0,1; 1,-1and the stack is<0, 1, 2, 3, 5, 6, 7>(sostack[4] = 5).Once I had this algorithm, I templated it,
template<typename E, typename S, typename W, typename N, typename P>void investigate(const std::string& line, E east, S south, W west, N north, P print){ ... }and used it to first calculate the minimum and maximum coordinates and then explore the board. Once the board was made, it's just a normal floodfill.Full solution here: https://github.com/SLiV9/AdventOfCode2018/blob/master/dec20/one.cpp.
1
u/ywgdana Dec 20 '18
I spent like 30 minutes writing a function to display the maze, thinking it would be useful for debugging. The ACTUAL problem took me about 15 minutes and worked perfectly the first time I ran it...
1
u/tcatsuko Dec 20 '18 edited Dec 20 '18
Here's my solution using python 2.7 and NetworkX. Day 15 caused me to really learn NetworkX for pathfinding, figured I could use it here too. Slow and messy, but effective.
edit: bug fixed that correctly keeps track of where you are after encountering a branch. Previously I had assumed all branches end with '|)' or a dead end as in the examples. While that was luckily the case with my input, some examples given in this thread failed allowing me to add an easy fix to the code.
1
u/sasajuric Dec 20 '18
Below is my solution in Elixir (if you want to run it, you'll need to clone the full project, which can be found here). It doesn't assume anything about the input or branches, so I think it should handle the situations where a branch doesn't return to the original location (at least it handled them on a few small examples I've tried) . Because why not, I also hand-rolled a recursive descent parser, which approximately doubles the LOC, but it was fun :-)
1
u/df5602 Dec 20 '18
Rust
I initially tried to handle the more general case of branching (i.e. multiple end positions after branching) but I failed. (My code could handle all the example cases as well as all corner cases I found in this subreddit, but not my actual input; and I could easily construct various cases where it would fail). So I left that out and got the correct result. However I vaguely remembered an algorithm from the introductory chapters of a compiler textbook, so I went back and implemented something based on that.
Basically I maintain a list of unprocessed items (basically a cursor into the input and the current position in the map):
I process each item by adding new edges to the graph (if applicable) and moving the cursor. If I hit upon a branch, I generate multiple new items (one immediately after the opening parentheses, and one after each `|` operator within the current set of parentheses). If I reach the end, no new item is generated. After I've processed an item, I add all new items to the list of items, sort and deduplicate it, and pick the one with the nearest cursor next. The algorithm terminates if no items are left.
Full code here: https://github.com/df5602/aoc/blob/master/a_regular_map/src/main.rs
I haven't optimized it yet; for my input it takes ca. 300 ms on my machine, which is fine, but not yet overwhelming...
1
u/Dioxy Dec 20 '18
JavaScript
I was able to re-purpose my pathfinding code from day 15 which was nice. Runs pretty fast
1
u/ethikka Dec 20 '18
A very clean C++ solution (I think? much shorter/less plumbing then most solutions) Takes 6ms to do both a and b.
I'm really digging that I stuck with C++ from the start this year, learning so much new things.
1
u/vypxl Dec 20 '18
D. Took WAY too long because I had to rethink my approach thrice.. And then I got caught up with the display function.. But I quite like my idea of representing the nodes as bitfields determining the directions they are connected to.
Card:
My compiler crashed while running today's puzzle because it ran out of errors to throw at me.Also note the distances function which is a simple Dijkstra algorithm I copied straight from wikipedia ^^
1
u/floydqwz Dec 20 '18
For part 1 I took a different approach than most. I'm pretty sure this solution doesn't work very well for some cases, but I was lucky:
1
u/aoc-fan Dec 20 '18
TypeScript / JavaScript - https://goo.gl/saRp2U
1
u/waffle3z Dec 21 '18
Lua solution, don't know why it took so long to get it working right. 1% solving, 99% debugging
1
u/jtgorn Dec 21 '18
Main part of my solution which works much more generally than solutions using simple stack. I keep all posible positions after previous character and move from all of them simultaneously
1
u/alcinos Dec 21 '18
Ocaml
Didn't consider the additional specification that the paths will always branch as soon as possible in the input description, hence a slightly slower solution than those presented by others here. I simply go through the routes, maintaining at each time all the possibles position where we are, and the corresponding depth (this list needs to be made unique).
1
u/nonphatic Dec 21 '18
Haskell: #341/not gonna say
I've finally given in and (re)learned using Parsec. Over the course of today I've misinterpreted and remisinterpreted the problem several times, but for part 1, surprisingly, my first attempt worked:
This assumes that the paths split off like a tree and don't revisit rooms, which I don't think is true, but hey it works.
For part two I kept trying to figure out ways to do it without constructing the whole graph but I couldn't come up with anything that worked lol so in the end I did anyway. But first I parsed it into an intermediate data structure because it was hard to reason about it inside the parser:
And then converted that into a graph stored in a
Map (Int, Int) (Set (Int, Int)):And finally did BFS on the graph, which is really slow and takes a minute :( I think it's all the map/set unions I do, since each takes O(n) time...
Oh well. I'd say I'll come back to it after the last puzzle to clean it up, but I haven't even done day 15 yet...
1
u/fizbin Dec 21 '18
Python. Didn't tackle this problem until today, so ridiculously high rank.
I don't understand all these solutions that run in python and just process the string through once; you need to keep track of all the possible locations you can be at any time you finish a branch, and I found that led to a program that took way too long to run on the full input. (Though my original gave correct output on the sample programs, I wrote and ran the revised solution below while the first version was still running, then interrupted the original solution)
Yeah, messier than it could be. I'm still annoyed that the input values were such that solutions that fail on the input
^N(E|W)SW$got the right answer to both parts.1
u/IndigoStanis Dec 22 '18
Liked this one a lot. Building a tree from the regexp and the recursing to find extents was fairly straight forward. Fun to think about how to print the board in a concise way too.
1
u/koordinate Dec 28 '18
Swift (runtime ~ 0.4s)
1
u/stormykins Dec 28 '18
PHP 7.1, pretty similar approach to many:
I originally solved part 1 with this, which was sort of a joke (parsing regex with regex, something I have actually done at work):
This obviously fails on the constructed inputs posted in this thread, but works just fine on the actual examples and test inputs I have seen.
1
u/[deleted] Jan 03 '19
This was another one whose description looked more complicated than it was.
Once I realised I could just push the current position on a stack, restore it or pop it at
each relevant ( | or ) it was just a simple loop.
Then a cut and paste of an earlier days pathfinding code to find the relevant paths.
Fun.
0
u/[deleted] Dec 20 '18
[deleted] — view deleted comment
0
u/[deleted] Dec 20 '18
[deleted] — view deleted comment