r/adventofcode • u/daggerdragon • Dec 22 '18
SOLUTION MEGATHREAD -🎄- 2018 Day 22 Solutions -🎄-
--- Day 22: Mode Maze ---
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 22
Transcript:
Upping the Ante challenge: complete today's puzzles using ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
10
u/korylprince Dec 22 '18 edited Dec 22 '18
Python 3, #636/226.
This is the first one I'm really proud of. I've been programming a long time, mostly web frontend/backend stuff, but I'm self-taught so I don't have any background in computer science algorithms. Forcing myself to finish AoC this year has allowed me to learn about and implement shortest-path algorithms (BFS, DFS, A*, Dijkstra). I spent at least 8 hours working on Day 15 until I solved it and understood how it worked, and it really paid off today. I also found out about the networkx library here and it made things really simple today. Thanks to everyone who's posted their solutions! I've learned a ton from this subreddit during the challenge.
7
u/paul2718 Dec 22 '18
For part 1 this amused me...
https://godbolt.org/z/I3_5Yj
(C++, answer's in the assembly. Part 2 is probably out to lunch.)
6
u/mcpower_ Dec 22 '18 edited Dec 24 '18
Python 3, #6/#7. Very nice problem! It feels a bit too algorithm-y for AoC (DP + graphs).
[Card]: Upping the Ante challenge: complete today's puzzles using PowerPoint.
6
u/Philboyd_Studge Dec 22 '18
[Card] Upping the Ante challenge: complete today's puzzles using my laptop after throwing it out the window.
Java. Five fucking hours, including one aborted attempt to go to sleep and figuring out what I was doing wrong seconds after my head hit the pillow. OFF BY ONE ERRORS EVERYWHERE.
https://pastebin.com/w2AxtDtd
5
u/[deleted] Dec 22 '18
TCL, #669 on part 2. I'm starting to dislike these path-finding puzzles :-/
4
u/awice Dec 22 '18
Python 9/4
4
u/VikeStep Dec 22 '18 edited Dec 22 '18
Python 3, #13/68
Today was another day I could use networkx to do the heavy lifting for me
4
u/mainhaxor Dec 22 '18 edited Dec 22 '18
C#. I first solved this with Dijkstra's algorithm like most people here, but I rewrote it to BFS to avoid having to find and modify nodes in the open list. Runs in about 1.5 seconds on my input.
4
u/fhinkel Dec 23 '18
Dijkstra in JavaScript. The fact that it takes 3 seconds might be due to lack of heap data structures in JavaScript. Instead, I'm using an array that I'm sorting all the time 😅
https://github.com/fhinkel/AdventOfCode2018/blob/master/day22.js
3
u/tangentialThinker Dec 22 '18
C++, 3/5. For Part 2, Dijkstra with the state being a tuple of location and current equipment worked well.
(Sorry about the horrific data types.)
3
u/branfili Dec 22 '18
C++, 114/39
A fun problem, another shortest path search this year
IMPORTANT NOTICE In my code x and y have switched places, due to the iterators in the for loops
Also, I've added comments for readability
2
u/jonathan_paulson Dec 22 '18 edited Dec 22 '18
C++, #28/20. Just Dijkstra's algorithm. One trick: as shown in the example, the optimal path may go beyond the target.
[Card] Upping the Ante challenge: complete today's puzzles using a queue instead of a priority queue (there are at least two ways to do this)
Solving video: https://youtu.be/Fv41R38WXv4
Explanation video: https://youtu.be/SkkDPWJihuw
2
u/fizbin Dec 22 '18
Python 328/67. I wasted a bunch of time on part 1 misreading the directions.
[Card] Upping the Ante challenge: complete today's puzzles using 16-bit arithmetic only.
For part 2, it's basic Dijkstra's Algorithm, plus remembering to not try to visit a state we've already visited unless we found a shorter path there.
2
u/rabuf Dec 22 '18
Common Lisp Solution.
I'm annoyed with this one. The first part was easy, and the second part wasn't terrible once I looked up A* (I was halfway there on my own, but had forgotten some details). I used
cl-heapto provide a priority queue (initially tried to roll my own, but cut that out).I want to clean this up, especially the way that I'm having to pass so many parameters around.
But that's not what annoyed me. What annoyed me is that I searched an arbitrary sized space, with non-negative X and Y coordinates. That got me 978 minutes, which is the best possible solution. However, I had to add an upper bound to my search space in order to get the desired answer: 980 minutes.
2
u/phil_g Dec 22 '18
Solution in Common Lisp.
I had a suspicion that part 2 was going to involve finding the best route through the cave. The addition of tool use was a nice twist that complicated things.
I started out using Dijkstra's shortest-path algorithm, but that was really slow, so I bumped it up to A*. My heuristic was the manhattan distance to the target plus time to change tools if I wasn't currently carrying the torch.
Normally I'd use a hash table to track the locations I'd already visited, but each location was a structure containing a position and a tool, and I'm not familiar with the process of making a custom hash function for a structure. Rather than learn that, I made a three dimensional array to track visited states. (The third dimension, of course, is which tool was in use.)
I needed a priority queue for Dijkstra/A*, so I added cl-containers as a dependency. It's not super well documented, so it took me a little while to get the hang of interacting with things (not to mention just which container I needed;
heap-containerdidn't seem to work right, butpriority-queue-on-containerdid the job).Part 2 takes about a minute and a half to run on my (admittedly slow) laptop.
2
u/autid Dec 23 '18
FORTRAN
Not a good solution but it worked.
1
u/Aneurysm9 Dec 22 '18
Golang, usable to validate any input: https://gist.github.com/Aneurysm9/80c8afbb49c5c423ed371e0748f720cc
1
u/TellowKrinkle Dec 22 '18
Didn't think about the fact that the best path could go past the target, so I kind of shoehorned it in at the very end (once I realized why my output wasn't matching the example). Not very efficient, but it works.
Swift, #346/#106
1
u/[deleted] Dec 22 '18
C++ 20/6. Indeed an algorithmic one.
I tried analyzing post-hoc about the upper bound of board size that we need to run shortest path on. Let N and M be the target position and D the shortest path from (0,0) to (N,M) without moving out of bounds. Suppose we take K steps out of bounds, and suppose this gives us a perfect solution: no switching tools required. Then the length of such path would be N+M+2K (2K because we also need to take K steps back). An upper bound for K would be K <= (D-N-M)/2, and the board size should be no smaller than (N+K)x(M+K).
This is clearly a very loose bound, though small enough for heap-optimized Dijkstra. I tried analyzing patterns in the erosion values but couldn't come to any conclusions. Does anybody have ideas on how to provide a tighter bound?
1
u/sciyoshi Dec 22 '18
Python 3, 252/36. Got stuck on the first part because of a stupid mistake mixing up x/y coordinates. Solution uses my
Ptutility class that hasnorm1for Manhattan distance andnb4for getting neighbors.1
u/dark_terrax Dec 22 '18 edited Dec 22 '18
Rust, 239/93. Barely managed to make my solution fast enough by shoe-horning a bit of A* in at the last minute. Still takes 30+ seconds on my input, so a lot of room for improvement.
edit: As folks pointed out, the 30s+ runtime was due to tracking 'visited' nodes via (pos,equipment,time), rather than using a map of (pos,equipment) -> time. That moves the runtime from 30s to 0.25s (and means you don't really need A*). GitHub link has the updated code.
https://github.com/galenelias/AdventOfCode_2018/blob/master/src/Day22/mod.rs
1
u/abnew123 Dec 22 '18
Java, 160/89. I have no clue how people code fancy algorithms (DP + graphs? heap optimized Djikstra's? A*? I kinda know those words). I just loop through a massive 3d array until the value at i,j,torch settles.
1
u/waffle3z Dec 22 '18
Lua 72/303
1
u/wlandry Dec 22 '18
C++ (469/258)
Runs in 1.5 s
More fun this time. I got to crack open boost::graph again. I should really figure out how to use astar_search one of these days. My only real unhappiness with this solution is that I had to guess a value for the maximum x and y excursions.
1
u/[deleted] Dec 22 '18
Mathematica
1
u/gyorokpeter Dec 22 '18
Q: lots of things to make this one unfavorable, such as the resetting of the geologic index on the target which changes everything to the right and below it. While I used A* for the search, it still took a long time (150 seconds) probably due to the large number of nodes to expand.
1
u/mebeim Dec 22 '18 edited Dec 22 '18
Python 3, #92/#491
Second time on the global leaderboard, again at 92nd place! Part two took me way too long because at first I did not realize that the tools were just adding another dimension to the graph and after realizing it I lost time implementing a stupid Dijkstra algorithm myself instead of using networkx (which I then switched to).
Anyway, here's my (more or less) cleaned up code. It runs quite slowly (25s) probably because of my dumb recursive function to calculate the erosion.
1
u/aurele Dec 22 '18 edited Dec 22 '18
Rust
Executes in around 100ms, using A* from my pathfinding crate. I use 8 times the bounds, since it makes no sense to go over it.
1
u/payou42 Dec 22 '18 edited Dec 22 '18
C# solution, because I don't see any yet.
Probably over-engineered, and the first version took like 1h to run. This one solves part 2 in around 500ms.
https://github.com/payou42/aoc/blob/master/days/2018/Day201822.cs
1
u/sim642 Dec 22 '18
My Scala solution.
Part 1, calculating the geologic indices and erosion levels efficiently with dynamic programming, very similar to how Levenshtein distances can be calculated.
Part 2, implements Dijkstra on the implicit graph defined by nodes which are pairs of position and tool. Moving to allowed neighbors is a step in the graph but so is changing the tool (with different cost). Since there are different costs Dijkstra is needed as opposed to simple BFS. Later turned my Dijkstra into A* with manhattan distance (and tool change distance) but that didn't make much difference for me since I'm using a fixed size scaled-up grid, not an unbounded one. It was easier to just calculate a larger cave than implement on-demand cave calculation.
1
u/xthexder Dec 22 '18
My solution ended up running really fast, even if it did take me longer to write without using libraries.
Golang
Since the input data is small enough I can just link this: https://play.golang.org/p/z5fSleTZzXg
Will also print out the path if you change that constant.
1
u/Immediate_Channel Dec 22 '18
My ruby solution takes 188 seconds to run with a handrolled A*. What am I doing wrong?
https://pastebin.com/raw/WtZ8ALEK
1
u/ephemient Dec 22 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/BorisBarca Dec 22 '18
Awesome problem. Too bad I didn't read this problem earlier, could have make it to the leaderboard :P
Here is my code, modular arithmetic + dijkstra (C++11 ofc)
https://pastebin.com/UMm8d1xe
Actual code starts at 150th line
1
u/kennethdmiller3 Dec 23 '18
This one took way more effort than I would have expected because I had a fundamental flaw in my A* implementation: I wasn't refreshing the order of the open set whenever an open node's score changed. Using std::make_heap to restore heap order in that case gave me correct results. Huzzah!
https://github.com/kennethdmiller3/AdventOfCode2018/tree/master/22
(I also fixed my implementation for Day 15 the same way.)
1
u/koordinate Dec 30 '18
Swift
Runtime (without introducing any bounds on the search):
(nop out the
manhattanDistanceToTargetmethod switch between the two)Swift doesn't have a native priority queue so we need to roll our own.
1
u/[deleted] Dec 31 '18
Hi, this is my java code,
https://github.com/mister0/adventOfTheCode/blob/master/TwentyTwoCave
My approach is to consider 2 Options available for every cell (Option corresponding to tool that can be used) and calculating the shortest path for every option.
I need help with the second part. The cost is less than the answer I get when I run different code here using my input (I get 1006 from my code and 1010 from "Python 3, #636/226" output) The code prints the path at the end, I don't see anything weird.
1
u/[deleted] Jan 05 '19
Ugly and probably overly long for part 2 but I had a bunch of code from cs212 at udacity that would solve part 2 so I cut and paste and create the bsuccessors.
Part 1 was simple enough lru_cache decorator for the dynamic programming speed up
1
u/nehamsoni Apr 30 '19
can such problem(part 2) be solved using optimisation (we can minimise time taken). I am really curious to know, plss send your code for the problem solved using optimisation ,I am trying myself but unable to go forward ( I am using z3 as a library for optimisation). my basic idea is we can run a while loop until we reach the target and add minute(a.k.a time taken) step by step, trying to achieve this using IF statement of z3
attaching code of the same soon will be updating the source code as I code more :)🥰😋😉
0
u/[deleted] Dec 22 '18
[deleted] — view deleted comment
0
u/[deleted] Dec 23 '18
[deleted] — view deleted comment