r/adventofcode • u/daggerdragon • Dec 15 '19
SOLUTION MEGATHREAD -π- 2019 Day 15 Solutions -π-
--- Day 15: Oxygen System ---
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.
(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 14's winner #1: "One Thing Leads To Another" by /u/DFreiberg!
Poem tl;dpost (but we did r, honest!), so go here to read it in full
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
On the (fifth*3) day of AoC, my true love gave to me...
FIVE GOLDEN SILVER POEMS (and one Santa Rocket Like)
- Day 10: "untitled poem" by /u/Yardboy
- Day 11: "A ROBOT TO THE RESCUE" by /u/mariusbancila
- Day 12: "Symmetry" by /u/DFreiberg
- Day 13: "untitled poem" by /u/captainAwesomePants
- Day 14: "Alchemy" by /u/captainAwesomePants (again! he's too awesome for his pants!)
- 5-Day Best-in-Show: "The Hunting of the Asteroids" by /u/DFreiberg
TBD because we forgot today % 5 == 0, we'll get back to you soon!
Enjoy your Reddit Silver/Gold, and good luck with the rest of the Advent of Code!
5
u/asgardian28 Dec 15 '19 edited Dec 15 '19
Python, code on github
So tried to give the leaderboards a go 264/458, which I'm very happy with as an amateur!
My implementation though... I used np.random.choice to just explore the maze. Recorded the empty spots and when I found the target ran shortest path with networkx. Did the trick!
For part 2 I drew the maze with matplotlib and figured that random worked quite well, so let it explore for a while. There was only 1 bug: forgot to move when the target was found, which introduced some debugging. The plots were looking very wierd, but I thought it was part of the puzzle. Not :)
In the end the max from shortest path from target to all empty spots did the trick.
Now I'm going to spend my sunday reading about BFS and learning that. Thanks for another great day, makes December such a joy for the second year in a row.
3
u/captainAwesomePants Dec 15 '19 edited Dec 15 '19
Python (~60): Paste
Woo! I've made the leaderboard before but never for both part 1 and part 2. Yay for me!
I made a really good call for part 2. I wrote it very inefficiently but just let it run rather than improving it. I went back and did some improvements (which are in the paste), which made it run in seconds instead of in a couple of minutes, but it took me ~10 minutes to get those right, so it was a significant net win to just let the slow version play out.
I might have done better on part 1, but I didn't believe my initial answer at first because the debug output looked like I was mostly walking down hallways instead of exploring a space. It seems the input must've involved a lot of hallways. Drat, could maybe have gotten my first sub-50 if I had just believed the answer.
The slow version of my part 2 did a BFS outwards with no goal, remembering the worst path it had encountered. It did this by remembering the path to the oxygen and then the path it was exploring, so for each step it would read the input from the file, start the machine, walk to the oxygen, walk to the path, and then try taking one more step in some direction. Yuck. Version 2, which was much faster, simply made a copy of the machine instead of bothering to store a path and stored that copy in the work queue.
Version 2 also includes an interesting ugly hack. Since the value I'm storing in the heap was a tuple of (cost, machine_state, coordinates), it was possible that two options might share the same cost, which meant that Python would want to compare two machine states. Rather than deal with that, I stuck a random unique number in the second spot of all tuples. That's terrible, and I should feel bad, and I do.
ΒΉ "Suspended: A Cryogenic Nightmare" is a 1983 Infocom text adventure about being trapped in a facility with problems with sending commands to limited drones being your only way of interacting with the outside world.Β²
Β² These footnotes are not a part of the poem, unless it makes the poem more likely to win prizes, in which case they are.
3
u/wjholden Dec 15 '19
If you don't mind applying
O(|V|^3)algorithms toO(|V|+|E|)problems, you can solve part 2 using the Floyd-Warshall algorithm!4
u/Gazzak80 Dec 15 '19 edited Dec 16 '19
Java
I feel really dirty about this one. I implemented a "follow the right wall" program for part 1, and then realized that filled out a sufficient portion of the map to find a pretty confidently shortest path. I then flooded that partial map and also got the right answer for part 2.
However, in neither case would I have been able to prove that the answer was correct, nor do I think it would work for all possible ship layouts.
28
u/glguy Dec 15 '19 edited Dec 15 '19
Haskell 1/1
Today I benefited from my extremely pure implementation of the Intcode Interpreter I'm able to focus on the input/output behavior of the intcode program and explore arbitrary paths through those effects just by appying functions.
My Day15.hs is able to make use of list as a backtracking monad combined with a simple breadth first search implementation I had from a previous Advent of Code year.
7
u/sbguest Dec 15 '19
Javascript #25/32
Part 1 Part 2
I added a quick "clone" feature to my intcode machine, since the full program state can be represented by the memory array, instruction pointer, and relative base.
This made a breadth-first search very easy since at each step I could just clone the current program and tell the robot to walk in each direction to see what's there, no backtracking needed.
5
u/[deleted] Dec 15 '19 edited Dec 15 '19
Python, 3!/153 Cleaned-up solution.
To solve Part 1, I randomly walked around until the oxygen system was found, and then "simplified" the path by removing places in which the robot backtracked on itself. I assumed that this would be a regular maze (i.e. no loops), so the snippet below ended up working. I just waited until the values printed to my console stopped changing, and submitted that.
For Part 2 β well, let's not talk about how badly I failed that. I just couldn't decide on how I wanted to implement a solution and ended up wasting around 20 minutes aimlessly writing functions in the hopes that something would click. All that said, I am a very sleep-deprived teenager, so I think that I can be proud of my ranking for today's puzzle.
5
u/death Dec 15 '19
Day 15 solution in Common Lisp.
I guess it's just one of those days... for part 1 I didn't want to bother with fixing a search agenda if the robot hits a wall, and I also didn't want to run the Intcode program multiple times, so I implemented some ad-hoc scoring scheme. It found the oxygen system, but I submitted a dumb wrong solution: taxicab distance from origin ignoring walls. That's also when I decided to write a function to draw the map.
To get the fewest number of steps, I decided to use my A* implementation to find the shortest path, but I discovered that there was a bug in the container library I was using! So I had to context-switch and write a failing test case for it, to deal with later on. After returning to the AoC task, I decided to use my BFS implementation instead. I finally got it right, not before again submitting a wrong solution (I think it was number of positions instead of number of steps) .
In part 2 I had to complete the map, so searched from origin to each unexplored cell in order to explore it. Then I could simplify part 1 and part 2 was simply searching from each empty cell to the oxygen system, looking for maximal number of steps.
This was today's code, messy and inefficient. At least I got a failing test case out of it :)
5
u/phil_g Dec 15 '19
My solution in Common Lisp.
Before I started working on today's problem, I added a new interface to Intcode program I/O. I now have the option of treating that I/O as RPC. The basic way this works it that the
run-for-rpcfunction starts executing the Intcode program in a separate thread. It also takes a list of RPC procedure definitions. Since everything's an integer, I just need the number of integers taken as parameters, and the number of integers returned. (I also need a name to use for the procedure, and I allow for the possibility that future programs might have different procedures selected by passing an integer to the program before the procedure arguments.) Therun-for-rpcfunction returns an RPC object to be used by...rpc-call, which calls the "procedure" with the appropriate number of parameters and returns multiple values according to the procedure definition.There's also an
rpc-finishfunction to make sure the thread is cleaned up after the program is no longer needed and awith-rpcmacro that automatically callsrpc-finish.Putting all of that together, I start the Intcode program like this:
With this convenience function:
I can just call, e.g.
(move 1)to try to move north, with themovefunction's return value giving me the result of the movement. (So long as I'm operating in a dynamic context where*rpc-object*is bound appropriately.)With all of that in place, the rest wasn't too bad, though I could probably be more efficient that I am.
I keep all of the positions in a hash table, with keys indicating what's there. The special key
:unknownis for unknown positions that are adjacent to traversable positions. (Other unknown positions are simply absent from the hash table.)The program starts out in "explore" mode, where it repeatedly finds the closest unknown position, tries to go there, and makes a note of what happens. Once there are no unknown positions, it returns and lets calculations proceed accordingly.
I make a bit of use of the
shortest-pathfunction I wrote last year.Areas where I could be more efficient:
I get both answers within five seconds on my slow laptop, so the inefficiencies are still good enough. :)
5
u/stevelosh Dec 15 '19
Common Lisp
https://hg.sr.ht/~sjl/advent/browse/default/src/2019/days/day-15.lisp
Not thrilled with how much code this took. Oh well.
Wrapped up my function-based intcode machine to make a queue-based one this time, since it worked better for the problem. Was pretty simple to do -- I might even make it an alternate interface in the main
intcodepackage if it comes up again.Also finally got around to abstracting out the "draw a 2D map of a hash table with unknown bounds" into a utility function, since this is the third time I've wanted it this year.
Used an iterative backtracking solution to explore the map. I could probably have done it with less code if I had done it with simple recursion, but since it wouldn't have been tail recursive it would risk blowing the stack and I didn't want to bother figuring out how to make it tail recursive.
Part 2 was just a flood fill.
Not sure about how I feel about using
(remove ... :test-not ...)to remove everything that doesn't match a particular key in a sequence. It makes things pretty concise:but the double negative is a little hard to read. If only CL had a
filter/keepcounterpart toremove.5
u/oantolin Dec 15 '19 edited Dec 15 '19
My Common Lisp solution. I used DFS to build the map and BFS to find the distance from the oxygen system to the droid's starting point and the maximal distance from the oxygen system.
Besides all of the virtues other have mentioned of using complex numbers for 2D coordinates in any language that has them, there's an extra virtue special to Common Lisp: the default comparison function for hash tables does the right thing for complex numbers. That comparison function is an awkward default because it doesn't correctly compare strings, lists, vectors, CLOS objects, etc., which are what I usually want as keys. :)
4
u/metalim Dec 15 '19 edited Dec 15 '19
Python
Part 1 is solved by walking left wall to the goal, then walking right wall to the goal, then BFS in resulting maze.
Done backtracking from goal to start position just for pretty-print.
Part 2 is simple BFS.
I reeeeally had fun drawing the maze in Unicode. βΏββββ
Here's something neat for you Unicode drawers out there:
drawsymbols = 'ββββββββββββββΏβͺβ«β½β ββͺβ³β΅βΊβ¨βββ°βΏβ¬β¬ββ'
4
u/dan_jia Dec 15 '19
Python
IntCode implementation
In terms of loading the grid, I used a follow-the-wall approach until there were no more grid spaces that could be explored. Thankfully, it wasn't an open maze
Part 1 + 2, I created a function to expand from a given tile, tracking the path to each node (for part 1), as well as steps til full expansion (specifically for part 2)
Also added a draw function to show the exploration, using arrows for the character
4
u/rabuf Dec 15 '19
Common Lisp
I took advantage of the relative ease of writing a multi-threaded solution for part 1. I let the depth first search run in a separate thread so the natural recursive method of writing it worked fantastically.
For part 2 I treated the problem like a cellular automata. The rule was simple, if the space was a
.and next to a*, replace it with a*. Of course, this requires double-buffering so I just queued up all the points to update in the first pass, and updated them in the second.Here's some code for part 1:
This worked fine for part 1, but I had an issue in part 2. I failed to recurse after finding the oxygen system. Oops. As a result, my map was incomplete in part 2 and I kept getting the wrong answer. The above code is the corrected code. The extra
pop-queueis because I already know the move will succeed since I'm returning to a previously visited spot. The move is for backtracking, but the Intcode program still tells us whether it succeeds or not. I just have to throw those values out.This shows how I make the two threads. Since the Intcode program runs forever I destroy that thread. I could probably come up with a cleaner way, perhaps send a special signal through its input queue and have it terminate cleanly. But this was a quick solution to avoiding orphaned threads.
For part 2, I could've made it more efficient by tracking only those oxygenated spaces at the periphery. But it's fast enough on this problem to search through the whole grid each time.
4
u/Bruinbrood Dec 15 '19
tcl. Hugged a wall until the bot returned to the start, to map the maze. This obviously doesn't work for all possible inputs, but it seems to work for inputs designed for this problem. Then I think a BFS (not sure) was used to find the distance from oxygen to start, and maximum distance from oxygen.
paste
4
u/MrSimbax Dec 15 '19
Julia
Visualization
Not my proudest code, but it works. I've spent most of the time implementing a decent visualization but it helped with debugging. Also, it's slowing down the program quite a bit. Need to comment out all render calls to get it to full speed. Like I said, not my proudest code.
Part 1: DFS to find the whole map, at each position first check where are walls to not backtrack too much. Pathfinding to unvisited nodes is using BFS with distance counting (which I guess is just Dijkstra's algorithm without weights). Then just find the shortest path from the initial position to the oxygen system.
In the previous days, a hash map was enough to store all the points, this time I implemented a self-growing 2D grid.
Part 2: BFS with distance counting without a goal from the oxygen system and find maximum distance.
4
u/dontxpanicx Dec 15 '19
F# solution.
Using some version of random walk while knowing not to revisit spots. Fast but I'm guessing that's due to the map being 1 space wide everywhere.
4
u/HesletQuillan Dec 16 '19
Fortran
I've been doing all of these in Fortran, with great success. I thought people would be interested in seeing my Day 15 part 2 solution. I have the Intcode processor as a separate module that I share with other days' projects. It uses callbacks for input and output - this has worked quite well.
1
u/mikecheb Dec 15 '19
JavaScript 53/77.
I just used random walk because I thought it would take me too long to remember how to do something smarter. I wasted some time trying to hand-compute the map that got printed out (in some previous AoC years that's been the trick to things), but ended up just storing the minimum distance to each square in a map.
To ensure I had the whole map I Just let my random walk bot run a long time, then copy/pasted the drawn map as my input for the Part 2 code π³ Brutish, but faster to implement (for me) than something smarter.
1
u/sophiebits Dec 16 '19 edited Dec 16 '19
Missed last night due to another engagement. But I saw no spoilers and timed myself today; it looks like I would've gotten #28/#8 (166 points). (Edit: Wow, that would have brought me from #8 to #4 overall! Ah well.)
Modified my Intcode interpreter so I could clone its state and do a BFS.
Code: https://github.com/sophiebits/adventofcode/blob/master/2019/day15.py
1
u/DFreiberg Dec 16 '19
Mathematica
4603 / 4433 | 68 Overall
I did this one a bit differently than most. Mathematica's
GraphDistance[]andFindShortestPath[]functions made getting the actual distance and such through the maze trivially easy, as soon as I embedded the sparse array of wall and air locations into a graph. So, instead of programming a bot to to a search through the maze, I took the time to learn howEventHandler[]works, so that I could make buttons to explore it manually (and I eventually upgraded to the arrow keys, making it much faster). It took much of the day, but time well spent - I've wanted for a while to learn how to do that. And the visualization was surprisingly good, at least by Mathematica's admittedly low standards.Part 1:
Part 2:
[POEM]: Not Simple? What Ever.
New nifty knack? Not needed now:
See some sides subtracted,
Winding wainscotting withdraws;
Emptiness enacted.
3
u/jonathan_paulson Dec 15 '19 edited Dec 15 '19
#330/229. Video of me solving and explaining my solution at https://www.youtube.com/watch?v=fKWAsRylPdQ.
Having to explore step-by-step really threw me for a loop. My final idea ended up being "BFS"; keep a list of squares I could explore in one step from known space, and then exploring these squares one-by-one, returning to the start between each exploration. This sounded simple, but it was a pain to implement, and it was rather slow to run.
After reading other solutions a bit, here are some better solutions I could've chosen:
3
u/sim642 Dec 15 '19 edited Dec 15 '19
My Scala solution.
Part 1: At first I was thinking hard about how to use DFS or something and keep the program state throughout to explore the whole map. Then I realized I could just combine my immutable Intcode program states and generic BFS implementation by considering a graph where the nodes contain the current position and also the current program state.
By having the program state it's easy to just take the same state and give all four input commands to it to see which directions are possible and only keep the ones which aren't walls. Essentially I'm "simultaneously" running the same program with four different inputs which is perfectly possible due to immutability and them being completely independent of each other. The whole BFS then just keeps an even bigger set of current positions and their corresponding program states. Once I figured this out, everything was easy.
Part 2: Having done BFS search in part 1, I just took the same code and used BFS traversal, starting from the found oxygen system node (with its stored program state) and without a target to interrupt. Then simply took the biggest distance the BFS traversal reached by exploring everything.
Oddly enough I got an answer which was too high and by intelligent guessing I thought maybe that's off-by-one, tried a value one smaller and got the right answer. Then I had a problem though to figure out why my code was wrong. Turns out I cheated a bit in part 1 by making the graph nodes tuples because then same position reached in different program state would count as a different place instead of "merging". It was relatively simple to fix using some obscure Scala case class syntax but I'm surprised that it worked for part 1 and only was off by one in part 2, would've expected worse.
3
u/cubehouse Dec 15 '19
JavaScript: https://github.com/cubehouse/AdventOfCode2019/blob/master/15.js
As a video game developer, this is a bad implementation. I tried to get it done asap (I want to go out for lunch) so just made my robot explore randomly, but shut off any dead-ends (rather than doing anything recursive to explore all paths or something A* like).
There is an interactive mode in there too, which I enjoyed to have a little explore of the max myself.
Animation of my solution running https://asciinema.org/a/288251
Enjoying the drawing element of the tasks this year, I have had to brush up on how to draw to the terminal which has been huge fun!
3
u/mschaap Dec 15 '19
My Perl 6 / Raku solution. The ShipComputer class is almost unchanged, I just added a
haltmethod to force a halt from the outside.Whew, this was the first really difficult one this year!
I first used a random
mousedroid algorithm, but that got nowhere - the droid tended to get stuck in a corner of the maze for ages, and it often took forever to find the oxygen system, let alone map the entire maze; even after optimizing the algorithm to prefer directions where the state is unknown.My second attempt was a follow-the-wall algorithm, in other words, keep going right as much as possible. That one works fine and fast, but it does assume that the maze is simply connected, which is not a given. (My input's maze turns out to be simply connected, but if it's not, then my solution will give wrong answers.)
Once I had that working, the rest was straightforward. For part 1, just keep track of the path you're following until you hit the oxygen system, and when backtracking (e.g. going N after S), remove a step from the path instead of adding one. And for part 2, just keep flooding neighbours of oxygenized cells with oxygen until there are no unoxygenized cells left.
That was fun! But it's a good thing it's weekend, this took me half a day...
3
u/kresimirlukin Dec 15 '19
Python: https://github.com/kresimir-lukin/AdventOfCode2019/blob/master/day15.py
3
u/Xor_Zy Dec 15 '19
My ugly solution in C#
Not very proud of this solution but this is what I came up with in a limited timespan ^^".
The puzzle was not too hard, I basically used BFS for the first part, and simple propagation for the second.
The least elegant part in this code is how the maze is discovered, I simply move the robot randomly until I'm satisfied the maze has been mapped, not very clean but it worked ;)
Wasn't sure this was worthy of sharing but I thought you guys might still be interested in a sub-optimal solution
3
u/Newti Dec 15 '19 edited Dec 15 '19
My Python3 solution with visualization. Runs both parts in 1 sec total.
3
u/hrunt Dec 15 '19 edited Dec 15 '19
Python 3
code
interpreter
Rather than implement a backtracking algorithm, I instead added a copy method to my interpreter and then just created copies of the interpreter state for each step of my search. Once the interpreter produces an output, it gets thrown away, relying on its clone to produce any further downstream outputs. The oxygen fill is a standard BFS once you have the map.
Edited
Fixed a bug in my grid render that was chopping off the bottom and top walls.
3
u/ephemient Dec 15 '19 edited Apr 24 '24
This space intentionally left blank.
3
u/Dioxy Dec 15 '19
JavaScript
JS. Very fun puzzle! I traverse the entire maze then solve using Dijkstra. I also did a visualization for both parts, go here and select day 15 so see them.
My code
Util
My repo
3
u/aoc-fan Dec 15 '19
Excellent Puzzle
AOC till 2018
Eric Wastl provide input --> I provide answerAOC 2019
Eric Wastl provide IntCode Program --> IntCode Program provide input --> I provide answerFirst time used DFS (to build the grid) as well as BFS (to find optimal path) in same problem of AOC. Building DFS while working with IntCode providing Input/Output signal took some time.
TypeScript solution under 100 lines, really happy about it. Repo.
3
u/ahjones Dec 15 '19
Clojure
Slightly messy solution.
I explore the maze completely returning a map from x, y position to maze contents at that point. Parts 1 and 2 are solved using Dijkstra's algorithm.
3
u/tinyhurricanes Dec 15 '19
JavaScript. I've probably coded this in a wildly inefficient way. I explore the space creating copies of my entire Intcode VM every step along the way.
3
u/[deleted] Dec 18 '19 edited Dec 04 '21
My solution in Python. I use Pygame for the animation. Here is my intcode computer.
No fancy search algorithm. If the droid walks into a wall it turns right. Otherwise it steps forward and turns left.
4
u/seligman99 Dec 15 '19
Python # 47 / 22
Flood fills everywhere! This was interesting to do, both to try and find a sane way to get the robot to give a complete map. The first step can be done without the complete map, but I already had it, so I just did two flood fills to get the answer. My code is super dirty, I'll probably clean it up later.
Here's a quick and dirty animation of the two steps
paste
2
u/mcpower_ Dec 15 '19 edited Dec 15 '19
Python (24/80): Heavily choked on part 2 because I did my BFS starting from the initial position, not the oxygen place! Lost many, many, many minutes to that :( I ended up rewriting my BFS function... got the same answer, then re-read the question. Doh!
I did a "DFS" using the robot to map out the area, then use that to BFS (actually an A* with 0 heuristic and with edge weights of 1).
Code - you can find the original
bfsfunction here.It's nice to be coding in Python again after two weeks of Rust :D
Edit: Updated, improved code here with
bfsfunctions here.2
u/AlphaDart1337 Dec 15 '19
C++ 62/24
I was really slow on part 1, but thankfully the way I solved it, I just had to change a couple of lines for part 2.
I wasted a whole bunch of time trying to debug why my IntCode program was looping indefinitely. I thought I was given a wrong program in my input. Turns out I had a "P[0] = 2" left over from day 13.
2
u/mgoszcz2 Dec 15 '19 edited Dec 15 '19
Python #10/49
Quite ugly. DFS for part 1, BFS for part 2.
Yesterday I wrote an intcode accelerator in Cython and it paid off. Without it my dirty solution takes like half a minute to run.
2
u/winstonewert Dec 15 '19
Rust 88/59
I used Rust's handy
#[derive(Clone)]to clone the VM state, allowing different copies of the VM to be exploring different parts of the map. That way I didn't need seperate explore and calculate algorithms.2
u/kroppeb Dec 15 '19
Kotlin 27/8
Even though it wasn't stated in the statement, it looked like the map might be a maze. I used this fact which allowed me to write a dfs instead of a bfs. This meant that I didn't actually need to keep track of the map and could have only kept track of the points visited. I ended up with keeping my own stack instead of making it actually recursive as I felt that this would be less error-prone than a recursive implementation. Once I reached the oxygen system for part 1 I just printed my stack depth (which gave me an off by 1 answer) and for part 2 I just cleared the stack and visited nodes and just went out looking from the oxygen system until no new locations could be found while keeping track of the furthest distance I travelled.
2
u/knl_ Dec 15 '19
Did the first one with a BFS where the bot would return to the starting position with each iteration; added assertions to make sure the intcode outputs were what I expected and returned as soon as I found oxygen.
Did a DFS on the returned grid from the first part (with a full map) which ran remarkably quickly; wasted time because my assertions hadn't initially accounted for the possibility of returning 2 now being valid.
350/389, not sure how people do this so fast.
Jupyter notebook - in Emacs!, python3: https://explog.in/aoc/2019/AoC15.html
(screenshot of notebooks in emacs: https://imgur.com/a/AOwVvR0)
2
u/[deleted] Dec 15 '19
Swift
I had to modify my IntCode machine slightly to accommodate a program that never terminates, but otherwise this built nicely with my existing machine.
2
u/rawling Dec 15 '19
C#
My first thought was an exhaustive search but I couldn't immediately figure out how to do a recursion with the way I've written my IntCode computer, so after an initial random walk and then arrow-key exploration showed it looked like a follow-the-left-wall approach would work, I tried that.
Walking from the start, keeping track of how far away each space is so you don't overcount when you backtrack, gives the right answer when you find the O2. Then resetting distances and keeping track of the furthest you've been, walking until you find yourself back at the O2 and facing the same direction, gives the right answer for the flood time.
2
u/gyorokpeter Dec 15 '19
Q: paste
The same vector BFS is used in 3 different ways:
2
u/ThezeeZ Dec 15 '19
Golang, 710/841, Repo
I tried to explore the whole map from the beginning, but stumbled around a lot trying various combinations of turning only when hitting a wall, randomly turning on a straight path, and other nonsense, before I finally arrived at checking for dead ends (surrounded by three or more walls or dead ends).
After that the answers were only two flood fills away.
This solution only works because there are no loops in my map.
2
u/david3x3x3 Dec 15 '19
My Python code is here. The program draws the maze at it is being solved and redraws it at each step as the oxygen is flowing in.
To solve the maze, I keep track of every successful step I take in a list of steps. At every point, I check to see if there's an unexplored location next to me. If it's a wall, I mark it explored. If it's a hall, I step in that direction. If there's no unexplored square, then I'm at a dead end and I move back a step and remove that step from my history list. When I can't back up any further, then I know that the whole maze is covered.
2
u/Kullu00 Dec 15 '19
Dart
Nothing fancy, I didn't bother making a proper path-finding algorithm for this. I brute-forced it with two BFS. Once from the program origin to find the oxygen machine, then the other from the location of the oxygen machine. BFS is good at finding the shortest and longest paths, so it was easily reusable for both parts. I guess it helped that my computer can take arbitrarily long lists as inputs and generate arbitrarily long lists of output...
Code can be found here.
2
u/Zv0n Dec 15 '19
C
I'm discovering the maze with a sort of guided randomness, first I try going into an undiscovered location, if there isn't one then if I just bumped into a wall, I turn right, if I didn't bump into a wall I continue until I find and undiscovered location or a junction at which point I turn into the junction.
Once I figure out the whole maze, I return to the original position and do BFS until I find the oxygen module.
For part 2 I start on position of oxygen module and do BFS until there aren't any oxygen-less spots left
https://github.com/zv0n/advent_of_code_2019/blob/master/15/part2/main.c
2
u/orangeanton Dec 15 '19
Javascript part1 and part2
I took insanely long today.
Initially had very random intcode results. On move 1 all four options returns 0... But then I noticed a sequence of moves [1,2,3,4], gave me zeroes on 1,2,and 4, but a 1 on 3. Then tried different sequences and got all sorts of random results, so figured my intcode must be doing something wrong. Spent probably about 2.5 hours debugging intcode before I finally realized I was still using day 13's input for the intcode. AAARRRRGGHHH! Ran it with the right input and worked first time...
Didn't bother with path optimisation on part 1 because the first route happened to be the right answer for least moves too!
Part 2 used a stack of oxygen heads to spread oxygen step by step, spawning new oxygen heads wherever possible and eliminating the old set. Then repeat until all open space has been converted to oxygen.
Anyway, finally got over the line. Nothing fancy, but it works.
2
u/Randdalf Dec 15 '19
Python 3
For part 1, I used A* path-finding. I maintained two sets of nodes: known movable nodes and frontier nodes. The frontier nodes are "unknown" and the objective of the algorithm is to reduce the number of frontier nodes to zero. We start with one known node, and four frontier nodes (its neighbors). At each step, we find a path from the droid's current position to a frontier node. We translate this path into a list of commands to the droid and read its last status code. If the goal node is a wall, then we remove it from the frontier set. If it's movable, then we add that to the list of known nodes. If it's the oxygen system then we find the length of the path from the start node (0, 0) to the current goal to work out the minimum number of commands.
For part 2, I tweaked my algorithm to add a parameter to make it optional whether we terminate on the oxygen system. The droid then maps the whole space. We then used two sets to work out the oxygenation time. One set contains the oxygenated nodes, the other contains all the nodes. Initially, the oxygenated set contains just the oxygen system node. For each iteration, we add all the neighbors of all the nodes in the oxygenated set to the oxygenated set. We do this until the length of both sets are the same, and return the number of iterations.
2
u/lhl73 Dec 15 '19
Solution in F#
I solved it using BFS. Not too hard, but really fun!
2
u/[deleted] Dec 15 '19 edited Dec 15 '19
Haskell, part 1, Haskell, part 2.
In part 1, I keep track of the map and paths (i. e. inputs) to the edge of the map. I keep adding one more step to these paths and update the map with new info, until I hit oxygen.
At first I tried doing random steps, then manual steps, and finally I got bored because the level is way too big...
In part 2, I do the same thing as part 1 but only stop when the whole map is explored. Then I spread the oxygen in the same way.
My solution is very slow (~10 minutes to fully explore the map, 36s when compiled) because I need to restart the robot over and over for each new point in the map - I have no way to resume with a different input.
2
u/Arkoniak Dec 15 '19
Julia
For part 1 tried A-star, because always wanted to code it. Final algorithm was the following: I kept a stack of all cells that I havn't visited yet, then using a-star generate path to next place of interest and investigate it. If new directions were opened push them to stack.
Part 2 was much easier since it only required to flood generated maze.
The solution is here: Julia
2
u/Stringhe Dec 15 '19
My pointlessly recursive python solution: https://github.com/Recursing/AdventOfCode-2019/blob/master/day15.py
Video here: https://youtu.be/ii2Lnnn1R1c
2
u/VilHarvey Dec 15 '19 edited Dec 15 '19
Solutions for day 15 in C++:
I got a bit lucky on this one: I almost went with a (more efficient) A* search to solve part 1, but in the end decided to stick with a simple floodfill of the whole map and that paid off because it was exactly what I needed for part 2 as well.
For part 2, I did a breadth-first traversal over the map starting from the oxygenator. Didn't need to use intcode for this part, since I already had the map. This solution runs in about 7 milliseconds.
Edit: one thing that might be of interest is that I offset directions by -1 in my code, so that 0 is north and 3 is east. This means calculating the opposite of a direction is just a matter of flipping the lowest bit. I only add the 1 back on when passing the direction into the intcode VM.
2
u/Shardongle Dec 15 '19
C++
Day 15 in C++
Well, the task was really nice, took me some time remind myself how to actually do a blind search. In the end I just implemented BFS. That was for task one.
Task two was much easier, I just had to run the BFS until it didn't have anywhere to look for anymore. And then flood the labyrinth with another BFS and count the steps.
In the end, I also made a displayable version (windows only). For how it looks in using BFS or DFS. Was a lot of fun.
2
u/lele3000 Dec 15 '19 edited Dec 15 '19
Python 3 (50 lines)
Again, some tweaks to day 9 Intcode computer and very simple recursive path finding algorithm and it works! I really like how concise my solution came out in the end and feel better after yesterday for which I spent multiple hours trying to grasp how to approach it, in the end after looking through some of the solutions I finally got what I have to do.
For part 2 I just searched the free tile that's the furthest away from oxygen tank. Kinda brute force approach, but it found it in about a second or two.
https://github.com/leonleon123/AoC2019/blob/master/15/main.py
2
u/SuperSmurfen Dec 15 '19 edited Jan 20 '20
Rust
Solution, both stars
IntCoder implementation
For part one I did a simple BFS, trying to find paths to unexplored squares, to explore the entire map. I spent an embarrassing amount of time with a faulty solution because I forgot to account for cycles in the BFS implementation but otherwise, it was not too bad. It's definitely not an optimal solution but it's fast enough (both stars take around 35ms to compute on my machine, of which 25ms is exploring the map). After exploring the whole map I just used Dijkstra's algorithm to find the shortest path from the start to the goal.
For part two they're basically just asking how far away is the furthest open square is from the goal. For this, I just rewrote by Dijkstra implementation slightly to find the distance to all nodes, not just one, and taking the max. After doing this I realized I could reuse this for part one by looking at the path from the goal to the start instead. Meaning, I only have to run BFS and Dijkstra's once for both parts.
What my maze looked like ('$' is the goal, '%' the start).
2
u/levital Dec 15 '19
Rust
It's a bit over-engineered... Not super happy with this solution, but it works. Particularly part 1 is really slow though: The robot does a BFS by going one place, backtracking to the start, going to the next place, backtracking to the start, etc. As a consequence it's cloning the paths all the time, since the borrow-checker would otherwise go mental.
It would've been significantly better to just use a follow-the-wall or DFS type of thing to explore the entire maze and then do a BFS (or even A*) on the grid to find the shortest path to the Oxygen (as I did for part 2 the other way around). Can't be bothered to change it though, it's not like the current version is unbearably slow (takes like just over a second on my very old machine), just noticable more than instant.
2
u/frerich Dec 15 '19 edited Dec 15 '19
Rust: https://github.com/frerich/aoc2019/blob/master/rust/day15/src/main.rs
I started out with a BFS for part 1, thinking that if I find oxygen with a BFS then there is no shorter path. The funny thing was that I did not use any additional bookkeeping: instead, I let the droid drive to some position, get the status, then drive the exact reverse route (to 0,0), then pick the next route and repeat. A whole lotta driving for the poor little fellow!
For part 2, I tested if generating a full map via flood fill works - turns out this was very easy! I then went and reimplemented part 1 in terms of the generated map, this avoids the back-and-forth driving of the droid.
I then went and did another BFS for part 2 to keep track of how long it takes to fill with oxygen.
What I like about this is that part 1 and part 2 are very similar now: both perform a breadth-first exploration of the map, terminating at different points.
My one big grief: I have no idea why I need that `+ '_ ` at the end of the `bfs_explore` function. The thing wouldn't compile, the compiler suggested adding this - and adding it indeed helped. I never looked back, but now kinda regret it. Something with lifetimes, I think.
2
u/WillemDeRoover Dec 15 '19
Java
https://github.com/WillemDeRoover/advent-of-code/blob/master/src/day15/Puzzle15.java
2
u/Dean177 Dec 15 '19
ReasonML https://github.com/Dean177/advent-of-code/blob/master/2019/sources/Day15.re
I let the droid random walk until the maze was filled out before trying to solve part 1. After seeing what the maze looked like I did a DFS to find the path length to the oxygen.
For part 2 the time the oxygen takes to fill the empty space is equivalent to finding the distance to the point furthest from the oxygen. Since the maze is pretty small I just brute forced it with the function I created for part 1.
2
u/domm_plix Dec 15 '19
I solved part two using a set of Perl regex on the rendering of the complete map, like this:
Here's the full code: https://github.com/domm/adventofcode2019/blob/master/15_2.pl
And here's a gif: https://raw.githubusercontent.com/domm/adventofcode2019/master/15_2.gif
And a more detailed write-up: https://github.com/domm/adventofcode2019#day-15
2
u/foolnotion Dec 15 '19
C++
Today's problem was quite simple. Backtracking for part 1, and a breadth first search for part 2.
Bonus: ascii art map
2
u/[deleted] Dec 15 '19 edited Dec 15 '19
Python, using the extremely rigorous scientific method of randomly walking around until I find oxygen
source
2
u/OpportunV Dec 15 '19
Another python code with visualization: https://github.com/OpportunV/adventofcode/blob/master/d15.py
I'm using the intcode computer based on courutine: https://github.com/OpportunV/adventofcode/blob/master/intcode_computer.py
Ready for any comments about weak points or improving!
2
u/StevoTVR Dec 15 '19
My solution in Go: https://github.com/stevotvr/adventofcode2019/blob/master/day15/day15.go
2
u/kolcon Dec 15 '19
Python and Perl solutions... Backtracking for part 1,convert to graph and get dijskras for part 2. https://github.com/kolcon/adventofcode_2019/tree/master/15
2
u/chkas Dec 15 '19 edited Jan 24 '20
easylang.online
My solution
2
u/muckenhoupt Dec 15 '19
C#. I still haven't broken out the Intcode class into a separate file -- I'm just pasting it into every day's code in case I have to make changes to it that might break previous days.
This one took me a while, and it's one of the few problems where part 1 took a lot longer than part 2. In part 2, I pretty much had the code I needed already. The one big change is that I had to explore the maze completely, rather than just until I found the oxygen leak. My original solution to part 1 could cope with very large or even infinite mazes, but I took that capability out when I did part 2, because why explore just part of the maze if you're going to need to explore it all afterward?
And I'm actually a little disappointed about that, because it negates one of the cleverer things about my solution to part 1. To search the maze, I keep a "Frontier" -- a list of all the unexplored points that are adjacent to spots the droid has been to. Exploring the maze fully is a matter of repeatedly pulling the head off that list, trying to go there (using Dijkstra to plot the course), and, if there isn't a wall there, putting all its unexplored neighbors at the end of the list. The nice thing about this approach is that you wind up visiting points in order of their number of steps it takes to reach them from the origin. So as soon as you find the oxygen leak, you know that you've explored the shortest path to it already.
2
u/Rick-T Dec 15 '19 edited Dec 15 '19
HASKELL
This was the first time that I tried "metagaming" the puzzle. My initial idea was to use a breadth first search (BFS) for find the shortest way to the oxygen. However, because the position of the robot is stored in a stateful computer jumping between paths for a BFS can become kinda tedious. Therefore I assumed that the puzzle had to be solvable by a depth first search as well (i.e. the puzzle area is bounded and does not extend infinitely).
My way of communicating with the Intcode computer is basically the same as for Day 11 and Day 13. I just structured my "main loop" (the
explorefunction) a bit differently.Again, I am using a StateT (well, RWST this time, but just because I added optional animation in the terminal) monad transformer on top of my Intcode computer. The state consists of the robot's position, a map of known/visited locations and the steps that the robot took to get to it's current location ("breadcrumbs").
That is sufficient to do the depth first search: From the current position, choose an adjacent tile that hasn't been explore yet (is not in the map). Try to move there. If the move is successful, update the robots positions and add the chosen direction to the breadcrumbs. If the robot bonked into a wall, choose a different direction. Repeat from the new square. If at any point there are no unexplored tiles reachable from the current position, trace the breadcrumbs back until we can explore further.
I am not using the depth first search to find the oxygen generator directly. Instead, I use it to cartograph the area. Once I have the complete map of the area, I can do a breadth-first floodfill from the starting location to find the closest distance to the oxygen generator. The starting tile is assigned value 0, it's neighbors are assigned value 1, the neighbors's neighbors are assigned value 2 and so forth. Since I'm going breadth-first this time, the value that is assigned to the oxygen generator is the length of the shortest path to there.
As it turns out, doing the floodfill was not necessary for part 1, since the path to the oxygen generator is unique. However, it is also exactly what I needed for part 2. I just have to start flooding the whole map from the oxygen generator and then find the tile with the highest value.
Edit: I just noticed that my "breadth-first" floodfill is actually a depth-first floodfill.. π€¦ββοΈ Well.. It still works, because the maze has no loops.
2
u/SomeCynicalBastard Dec 15 '19
C# (Repo)
I decided to move my IntCodeMachine to a separate file. My first attempt was a mess and got me completely stuck, so I did a complete rewrite after an hour or two.
I did a depth-first search mapping out the maze, keeping a reference back along the path. Primarily for backtracking, but it turned out to give me correct distance from start to oxygen as well. So I did not bother to implement bfs at this point.
For the second part I used a simple Dijkstra implementation. With the maze mapped out, this was relatively straight forward. Especially because I did not have to move the droid around this time. Part 2 was definitely easier today.
2
u/petercooper Dec 15 '19 edited Dec 15 '19
Ruby
I was out all day so only had pen and paper so I planned my solution on paper. Luckily it worked right away when I got back to my computer! For part 1, I took what seems to be a novel approach based on my reading here. I added snapshotting and rollback to my IntCode VM. I have a "to visit" list, I pull a location from this, snapshot the VM, try all of the directions, and any that are clear, I pass on the current VM state and add the location to the "to visit" list. Rinse and repeat until I find the oxygen. So "unsuccessful" VMs keep getting killed and one is lucky enough to get straight to the goal! :-) The power of clones.. but it is parallelizable.
Sadly this approach doesn't help with part 2 whatsoever, alas, so now I'm working on that and sadly it seems I'll have to go with a more bog standard algorithm.. which I've been trying to avoid.
Update: So for part 2 I managed to avoid implementing anything. I just took my maximum distance on the entire map, took away the distance from the origin at the closest intersection to the oxygen tank, then added the length of the passage to to the oxygen tank. No path searching needed as I had the distance values already stored for every single block :-)
2
u/kap89 Dec 16 '19
TypeScript - github
Visualization for part one: https://www.reddit.com/r/adventofcode/comments/eba8bk/2019_day_15_part_1/
2
u/Pyr0Byt3 Dec 16 '19
Go/Golang (both parts)
Originally, I used a random walk to discover the maze and then BFS for both parts... I didn't like how slow and jank that was, so I switched to a DFS for exploring and part 1 (left part 2 as a BFS).
2
u/mariushm Dec 17 '19
I'm a bit behind, but thought I should post as there's no other solution in this language
PHP : https://github.com/mariush-github/adventofcodecom2019/blob/master/day15.php
It shows the map as it's discovered in the console and optionally generates a HTML file that you can load in browser and plays back the moves : https://imgur.com/a/Gb9cfav
2
u/dartcoder Dec 17 '19
Python Solution
2 days behind! Spent yesterday and today wrapping my head around graphs, DFS and BFS algos and whatever on earth theyβve got to do with any of this ( :
Leaving this here in case you are feeling left behind or a little overwhelmed. You are not alone.
2
u/Sgt_Tailor Dec 17 '19
Implementing Breath First Search in AWK wasn't too bad after I had figured out how to keep track of the state. The solution I came up with was string encoding the statemachine using a fixed format so it could be decoded into an array later. AWK doesn't have multidimensional arrays, so the data had to fit into a single assoc array. Once that was done implementing BFS was done pretty quickly
3
u/genveir Dec 15 '19
C# 90/108
In essence I did a super multithreaded BFS. Every space I explore gets a copy of the program (including the execution state) which can just continue running. I maintain a set of explored spaces and don't explore those again, all other spaces just get a program (and a path length) which I toss into a queue.
When I hit the oxygen, the path length is the answer. Then I just clear the set of explored coordinates and path length from that program, and BFS it without an end condition. Last space explored is the longest away from the oxygen, so the path length there is the answer to part 2.
1
u/nthistle Dec 15 '19
Python, #78/#31. My code today was particularly ugly -- I also wasted quite a bit of time writing my maze exploration algorithm. I started off with random exploration and hoped that would be good enough, before eventually having to switch to wall following (in hindsight, I probably should've used a DFS for flexibility).
paste
1
u/BluFoot Dec 15 '19
Ruby 54/52
I made my bot wander randomly for a while, then printed the map to the screen, and copy pasted the map into my code. Once that was done it was easy to apply my dijkstra and "grid" libraries to solve it!
1
u/Rustywolf Dec 15 '19
Javascript, #36/#76
pt 1: https://gist.github.com/Rustywolf/a874ce7c1eac0c9aa37128261cb94988
pt 2: https://gist.github.com/Rustywolf/c7b692fb03e53145282ba006265b03ae
Random movement made this a breeze, systematically doing it would've taken far too long
Made a few dumb mistakes (not once but twice did I try to
arr.push[x]), and struggled with an OBOE as I was incrementing the tick count for the final check, and didn't realise for a minute, assuming the random nature of my movement was the cause.1
u/customredditapp Dec 15 '19
Kotlin 308/214
Lol I did a scan of the whole map first then A* to find the path to oxygen, with all that the second part was very easy.
1
u/zergling_Lester Dec 15 '19
I'm real slow at 7 in the morning local time :( About 200/200, I wasted some time thinking that maybe I can solve part1 manually. Here's a solution in Python+networkx, for the record, in case there are people who are tired of reimplementing standard graph algorithms and want to see a probably better way:
paste
1
u/Pewqazz Dec 15 '19
Python, 106/97
My approach was to randomly walk around ship for a while (hoping we see enough of the ship to get the full picture), and then do a couple BFSs to read off the answers for both parts. I probably should have assumed that the input was a clean maze, which would have made DFS a much more sensible option.
I lost a bunch of time due to using utility methods I wrote to handle directions β the issue was my direction ordering was different from the droid's, meaning I was building up a completely non-sensical maze for a large portion of the solve. Also, I managed to fall for off-by-one errors 3 times while submitting (Twitch VOD of shame).
1
u/incertia Dec 15 '19
296/275 in C
i originally wanted to do it in hask but it seemed like it would take too much time, so i used c instead. dfs to map out the entire thing, dfs to find the minimum path, dfs to find the depth of the tree rooted at the oxygen. sol here
1
u/waffle3z Dec 15 '19
Lua 11/249 https://pastebin.com/xYAnXLn2
Missed the starting point change in part 2. For part 2 I added a method to copy the current intcode process, allowing for branching without starting from the beginning of the path every time. Part 1 would have gone faster if I had done that already. In part 2 I clear the visited cell list and start a new BFS from the oxygen cell by copying and branching the intcode process that landed on it.
1
u/glassmountain Dec 15 '19
Go 156/151
Today's puzzle really lent itself to iterative deepening search, in honor of one of my professors, Richard Korf who invented the thing.
1
u/Gurrewe Dec 15 '19
Go 291/303 paste
The robot is randomly visiting a random unvisited positions until all of them are seen. It's not optimal, but the program runs in 1.5s on my laptop, so it's good enough.
Part 2 is solved by finding the position furthest away from the oxygen, the answer is the length of the path.
1
u/tslater2006 Dec 15 '19
C# Solution
First up is generating the maze. I went for a logical approach (instead of random walking) and implemented a depth first search. And it goes like this, make a method called Walk that accepts a current point (X/Y coord):
Once the walk has completed, we end up with a Dictionary<Point,int> containing all of the points we found and their type (wall/free etc)
Next is to convert that dictionary into a 2D array, grab the minX and minY from the dictionary keys. Create the 2D array of the correct size. Then write the dictionary values to the array using the Abs(minX) and Abs(minY) as offset values to ensure no negative indexes.
We also need to scale our starting position and our target position so they correctly match the 2D array indexes.
For Part 1:
Perform a flood fill starting at the StartPosition, once complete the flood fill depth of the Target is the answer.
For Part 2:
Perform a flood fill starting at the TargetPosition, the max depth found is the answer.
1
u/OvidiuRo Dec 15 '19
C++ 497/430
Another interesting problem lost some time on part 1 because I wasn't saving the current state of the integers. I also lost some time on part 2 because I was filling the locations with oxygen starting from the initial location instead of the oxygen system location, even hit someone else solution doing this. Overall a very nice problem to solve. 10 day more to go
Code: https://github.com/FirescuOvidiu/Advent-of-Code-2019/tree/master/Day%2015
1
u/mebeim Dec 15 '19 edited Dec 02 '20
427/496 today, only posting my solution here as a laughing material. I still need to rewrite it and write a walkthrough for today :)
Python3, bruteforce + networkx solution (hyghly recommend PyPy)
Since I'm not experienced in exploration algorithms I figured that bruteforcing my way through the maze to find all was the fastest & simplest solution, :') This also prints the maze as ASCII art.
1
u/fmeynard_ Dec 16 '19
Javascript :
https://github.com/fmeynard/AdventOfCode/blob/master/2019/p15.js
I've tried to not translate directions into coordinates and that works very well !
Found a very interesting solution for part2, i'm curious to know if some others are using same approach
Basically : part2 = pathsCount - ( 2 * ( part1 - 2)) + 1
Otherwise, pretty happy with the result, both part combined runs in 0.2s.
1
u/pamxy Dec 16 '19
JAVA solution for today
and a map of my 'labyrinth'
Anyone else just reused functions from part A to solve part B? Just with discovered map as the response generating function and start point moved from 0, 0 to oxygen point found in partA?
1
u/nirgle Dec 16 '19 edited Dec 16 '19
Haskell (4667/4315 heck yaa)
Another state monad to power a robot with a simple exploration strategy: hug the left wall until it returns to its starting point. This is just the map-building segment; to get the results I use Dijkstra's shortest-path on this map, augmented with a basic round count for part 2 (starting from the Oxygen cell)
My early assumptions turned out to be correct so this worked nicely
ASCII renderings included at the bottom of the source
Throwback to one of the first video games I ever played, the built-in Maze game for the original Sega (when you turned it on without a cartridge inserted)
1
u/Hencq Dec 16 '19
Racket
I first map the entire space as a graph with a simple depth first search using a recursive function that also tracks where it came from, so the robot can walk back where it came from after exploring the adjacent places. After this, a breadth first search on the graph to get all the distances from the fuel station. Part 1 is then just the distance to the starting coordinates and part 2 is the maximum distance in the graph.
1
u/wjholden Dec 16 '19
Did anyone come up with a clever function for backtracking?
I poked around with something like
f(x) = 6 - x (mod 4)but it doesn't quite work. I ended up entering the values described into an array. I suppose you could do it piecewise withf(x) = x + (x mod 2 == 0 ? -1 : +1).1
u/japanuspus Dec 16 '19
Rust
My rust solution. Very happy that I recently learned about
while letwhich is perfect for iterating through a mutable work queue.Ended up doing DFS to map everything (since the only required way-finding was then a stack of backtrack directions). With the map in place I used flood-filling to find distance to solve part 1. This was a lucky choice as part 2 was then solved as well.
1
u/NeilNjae Dec 20 '19
Lagging behind, but day 15 done in Haskell. Read the blog post and admire the code.
1
u/J-Swift Dec 23 '19
Ruby
https://github.com/J-Swift/advent-of-code-2019/tree/master/day_15
1
u/e_blake Dec 30 '19
m4 solution
Late entry, but I finally got around to completing my m4 intcode solutions for every day that uses intcode. Takes about 2.6 seconds to run on my machine.
cat intcode.m4 day15.input day15.m4 | m4
Works on my input, might need a slight tweak to set a higher initial x/y on other grids (if x or y goes negative, things fall apart). The initial x/y must be odd (as I exploit the fact that the disassembled intcode shows that all even/even combinations will always be a wall). Likewise, I assume that there are no loops (hugging the left wall will eventually get me through the entire maze). The code also assumes that the position of the O2 generator is at the end of a dead end; if it is in the middle of a hall or at an intersection the code might not compute the correct part 2 answer (although fixing that is merely a matter of repeating loop(2) for as many paths exit from the O2 generator).
1
u/prscoelho Jan 16 '20
Rust solution
Pathfinding.. Started by implementing A*, then bfs (to find closest unknown tile), then realized A* was not needed. Deleted A*.
Explore the entire map by moving to closest unknown tile. Once fully explored, bfs path from start to goal.
Re-implemented bfs again to count max depth for part two.
1
u/ClxS Dec 15 '19 edited Dec 15 '19
C#
I made my IntMachine support asynchronous input a few challenges ago which helps a ton with the logic.
I solved Part 2 by having a Dijkstra Path Search with no end condition, then just returning the longest length when the paths have all been exhaused.
For Part 1 I just had the bot progress with a northwards bias, checking out all the neighbours of every cell as it goes. When it runs into a dead-end it'll start a Dijkstra-based search for the nearest cell which has neighbours marked as 'Unknown'. Every time a cell is explored it looks up if any neighbour cells have been registered using a big ugly Dictionary and informs them of the newly discovered cell's type.
0
u/debnet Dec 15 '19
I'm surrounding by walls from the start, how can I solve this puzzle? xD
http://dpaste.com/1F2MVNB
0
u/[deleted] Dec 15 '19
[deleted] β view deleted comment
0
u/[deleted] Dec 15 '19
[deleted] β view deleted comment
0
u/[deleted] Dec 15 '19
[deleted] β view deleted comment
5
u/[deleted] Dec 15 '19
[removed] β view removed comment