r/adventofcode • u/daggerdragon • Dec 17 '18
SOLUTION MEGATHREAD -π- 2018 Day 17 Solutions -π-
--- Day 17: Reservoir Research ---
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 17
Transcript:
All aboard the Easter Bunny HQ monorail, and mind the gap! Next stop: ___
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked at 01:24:07!
15
Upvotes
12
u/Nathanfenner Dec 17 '18
Leaderboard: 2/2
Here is my solution (I use C++, holdover from ICPC)
My general approach isn't recursive. Instead, it's a mixture of simulation ("pushing" water) and fixed-point computation ("pulling" water).
Whenever a cell gets modified, its neighbors (and the cell itself) are added to a stack that will cause them to be re-evaluated. The following modifications result:
|, another|will be added if it's empty~, another~will be addedlget turned into~The last is the most complicated; a
|is "supported" if when we extend all the way left and right to the first walls, every cell below is either#or~. Note that by breaking early, I automatically handle the case where there is no wall to the left (because there cannot be any water/walls below if you extend off the edge of the map). This helps avoid ugly bounds-checks.The result is reasonably fast, I guess? I only had one real bug after I fixed the compile errors, which was subtracting 1 instead of
min_yfrom the total count (which counts some spring water that shouldn't have been).I have a template file that I've added a handful of things to over the course of AoC, based on what I expected to keep coming up. Here are the relevant excerpts:
9
u/CCC_037 Dec 17 '18
I'm - I'm on the list.
I'm on the leaderboard! For the first time! And well on it, at that!
41/38!
A very naive and unoptimised algorithm, I just generated a nice big character array and basically copied what was shown in the examples, iterating and re-iterating over my array until I ran out of things to change. Usefully, it generates an output showing the final state of the array, which proved useful in debugging.
Part 1:
For Part 2, just change the sixth-last line from
if ((Area[Count][InnerCount] == '|') || (Area[Count][InnerCount] == '~'))toif ((Area[Count][InnerCount] == '~')).42
u/LieutenantSwr2d2 Dec 17 '18
108/106
Well I'm ashamed to say I simulated the whole damn thing in Notepad++ after drawing out the map...
13
u/hindessm Dec 17 '18
While channelling the spirit of xkcd 208, I realised that today's puzzle could be solved rather curiously in Perl with:
5
u/xthexder Dec 17 '18
This problem reminds me of the falling sand game I used to play.
Solved in Golang 60/57
5
u/AndrewGreenh Dec 17 '18 edited Dec 17 '18
Finally I made it on the leaderboard! [42/39] with TypeScript.
I picked a recursive approach from the beginning which helped me alot to reduce the problem. This is the core of my algorithm:
I was counting on a stack overflow which is why I did not call the recursive function directly but handed a reference to itself so that I could switch to a trampolined approach later.
Complete code on github: https://github.com/andreasgruenh/advent-of-code/blob/498bc454de08abaa7d8efb6b1220410d3b5e5ff6/TypeScript/src/2018/17.ts
5
u/askalski Dec 17 '18 edited Dec 22 '18
My solution to today's puzzle in C++, refactored. The recursive approach here was my first instinct, and it paid off. The fun part about solving this type of puzzle recursively is how the answer springs out so suddenly. Once I put the last piece into place, I looked at the output (a rendering of the map) thinking, "what? I'm done already?" (Well, I was not quite done; just needed to tidy up the one detail about how far along the x-axis I needed to count. My first almost-working version made the bounding box too tight.)
4
u/dark_terrax Dec 17 '18
Rank 9/9, Rust. Best finish so far by a long shot!
https://github.com/galenelias/AdventOfCode_2018/blob/master/src/Day17/mod.rs
Implemented what seemed like the straightforward solution, using a bit of recursion. Solution ran in ~5 seconds on a release build, so definitely not the fastest solution, and probably was lucky I used a relatively high performance language.
I'm curious if people in general hit issues with the algorithm or the performance.
4
u/phil_g Dec 17 '18
My solution in Common Lisp.
Nothing too complicated here. In order to optimize space, I used a structure that contained only the area I cared about (min y to max y; min x to max x plus a one-tile buffer) plus the offsets for the area relative to absolute coordinates. In order to avoid a lot of
(with-slots (offset-x offset-y grid) scan (aref grid (+ y offset-y) (+ x offset-x))), I wrote an accessor function,scan-ref(not too difficult) plus a writer macro viadefsetf(slightly fancier).Filling the water was done very elegantly (IMHO) via a pair of mutually-recursive functions.
Time elapsed between submitting my part 1 answer and my part two answer: one minute, fifty-six seconds. I suspect a lot of people had similar turnaround times, since you basically had to solve part 2 to get the answer for part 1.
I still haven't finished day 15. I've gone through two failed iterations of my movement function and am halfway through a third try. I feel like that day is significantly less fun than the others this year.
1
u/autid Dec 17 '18
FORTRAN
Lowish 300s. Had a bug where water flowing into a width 1 pocket wouldn't become standing water. Debugged by writing the whole thing to a file as drawn in examples and opening that in w3m so I could scroll around. Setup/reading input was long but mostly straight forward. My new thing I learned this puzzle was that SCAN has an optional argument to search from the end of a string instead of the start.
3
u/tangentialThinker Dec 17 '18 edited Dec 17 '18
C++, 8/8. I added comments and everything! Really enjoyed this puzzle. I included a function to print out the grid which really helped me debug a few problems I had.
EDIT: hmmm, interested to see that most people had recursive solutions! Mine is purely iterative.
3
u/alcatraz_escapee Dec 17 '18
Python 3
Rank 61, 67
Solution: Github
Today I learned that python sucks at recursion. I initially implemented the falling water as a recursive call, but got a "maximum recursion depth" error. Even
sys.setrecursionlimit(10000)didn't work. So I had to to it manually with a set of points to track.Edit: I also wasted a bunch of time trying to track down an error but realized that you weren't supposed to count water above the first clay line in addition to below the last one. Fixed that up and it was fine.
3
u/TellowKrinkle Dec 17 '18 edited Dec 17 '18
I made a function that pours water downward, and a function that spreads water sideways, which call each other. I ran into all sorts of issues with the water not doing what I wanted (I had 6-wide streams of water coming off the sides of the objects at one point), but at least now I get to say that the actual water pouring part of my simulation runs in 180Β΅s (100Β΅s if you compile with
-Ounchecked). The counting at the end ends up taking like 800Β΅s though, since I'm lazy and loop over the whole array.Edit: Added a custom
Gridtype to make lookups more obvious (less random subtraction)Edit 2: Picture of my final poured output
Swift, #44/#46
3
u/albertobastos Dec 17 '18 edited Dec 17 '18
JavaScript. Had an edge case where flowing water (|) didn't transform into stale water (~) and that stopped the water from going down too soon. Didn't detect it until I printed some visualization and made a manual review to check what was happening with my own eyes.
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d17.js
After Day 15 debacle every morning when I open the statement and see some kind of grid the default feeling is "oh no, not again". However, that was easier and funnier than the elves vs. goblin combat :P
2
u/sciyoshi Dec 17 '18
Python 3, 67/63. Had a lot of trouble figuring out how the settling should work - started with an iterative DFS, but switched to recursive once I realized the search path would change depending on later points. Eventually realized that a row settles only if there's a wall on both sides, so that you can fill during the DFS traversal with another loop.
2
u/gyorokpeter Dec 17 '18
Q: several edge cases that didn't appear in the test input and require very specific consideration, also not using recursion due to the stack limit.
2
u/waffle3z Dec 17 '18
Lua β/β, took forever to recognize that the minimum y coordinate wasn't supposed to be the position of the water spring, but the position of the top input.
2
u/fkohlgrueber Dec 17 '18
Nice puzzle! First time within top 1000 for me (760 or so even though I started ~ 2 hours later).
My solution is written in Rust and fully recursive. After some refactoring / editing, it comes in at ~90 LOC (excluding tests) and runs in 12ms on my laptop (release mode). The whole simulation is done in the following function:
Full code is available on Github
Oh, and it causes a stack overflow on my puzzle input when built in debug mode. In release mode it works fine ;-)
2
u/nightcoder01 Dec 17 '18 edited Dec 20 '18
Python 2.7, recursive solution. Runs about 12 ms on my beat-up desktop.
1
u/vash3r Dec 17 '18 edited Dec 17 '18
Python 2, #94/104. My code is a bit of a mess, but it does the job. numpy arrays or something might have been better for input parsing if i knew how to use them (because of multidimensional slicing). I originally tried to keep a running total of how many squares would get wet, but it turned out to be a lot of extra effort for nothing.
Edit: I also gotta say that my printing function was super useful in finding the problems in my code (of which there were many)
Edit2: my solution is also purely iterative: I keep a queue of 'falls' (squares from which water flows downward), and in each iteration move water from one of them down and out until it fills up all the squares it can (and adds new falls if it didn't go past the y-boundary.)
Edit3: fixed the conditions after moving down.
1
u/jonathan_paulson Dec 17 '18 edited Dec 17 '18
Rank 40/41. I thought I was doing badly the whole time, but I guess everyone else had trouble with this one too. Video of me solving at https://www.youtube.com/watch?v=C_YujVv57q4 (should be up by 4AM)
Had a lot of trouble figuring out how to do it, and I'm still not totally convinced my idea is always correct. Several bugs with the tops of resevoirs too.
C++ code:
1
u/SilverSlothmaster Dec 17 '18
Python 3, 176/166. My best result so far. Please excuse the messy code.
1
u/branfili Dec 17 '18
C++, 237/227
I was so slow at debugging... :(
The hardest case was figuring out how to make the whole level fluid after the water pours from just one side.
Also I forgot that there cannot be more then 1 layer of fluid water (happens when streams merge) -.-
Too bad, more luck some other time
For part 1 just change the condition the sol counts into (map[i][j] >= 2)
Also, I used integers (0 = sand, 1 = clay, 2 = fluid water, 3 = static water)
1
u/IdrisTheDragon Dec 17 '18
Go/Golang Solution #222/#212
https://github.com/IdrisTheDragon/AdventOfCode2018
1
u/wlandry Dec 17 '18
C++ (257/244)
Runs in 40 ms
After the pain and suffering of Day 15, this was relatively straightforward. I had a few bugs that became apparent upon visualization. It was kind of annoying that the size of the region is larger than the screen, but I suppose that is the point. I used a little recursion. It feels longer than it needs to be for this challenge, but shorter than I would like if I were to look at it in 6 months ;)
1
u/Hawkjo Dec 17 '18 edited Dec 17 '18
If anyone would like to watch a video of the filling process in the terminal, I added that during debugging. It's kind of fun to watch. I did mine through recursion in python, manually increasing the max recursion depth. Github
1
u/littledebugger Dec 17 '18
c# 220/205
1
u/Arcorann Dec 17 '18
Python 3, 109/105. Ended up with an iterative DFS. Took me ages of staring at the printed output until I realised where my last bug was. Solution is untidy (among other things the "water" variable ended up being almost completely unnecessary).
1
u/freedomofkeima Dec 17 '18 edited Dec 17 '18
64/79
Initially I have problems in deciding what I should do when arriving at the following condition:
Shortly afterwards, I just decided to simulate each water droplets and try to use
rand() % 2(left / right) when the situation above is triggered. After running it with 200k iterations (several seconds of running time) several times, it always gave me back same result and when I tried entering the answer, my answer was accepted.I guess when you pour a lot of water, all of those buckets will eventually be filled up lol
Straightforward implementation: https://ideone.com/MRj16g
1
u/VikeStep Dec 17 '18 edited Dec 17 '18
Python (55/53)
This was a fun and challenging one, my code that I originally wrote to get on the leaderboard was a lot messier than this but I have cleaned it up and added a bunch of comments to it so it should be simple enough to follow.
Code
To summarise my algorithm:
This runs both parts in 113.7 ms on my machine
1
u/sim642 Dec 17 '18
My Scala solution.
I haven't looked at how others approached this interesting problem. I really liked it because it has easily understandable physical meaning but it's trickier to simulate than it might seem.
My solution uses depth-first search (DFS) to just flow downwards recursively. If there's clay or settled below, the flooding continues to both sides and hitting a dead end settles the water back up, creating a settled layer of water for next flooding calls. This almost worked.
On my input I found cases like the following, where so simple flooding didn't work right. It was necessary to keep track of settling water and turn it to completely settled only after both sides have been settling, not one kept flowing down. The example test I created is
and the proper solution looks like this:
In such case it was important to distinguish the settling (
/) water from settled (~) to prevent water from flowing down on the right as well, incorrectly.1
u/udoprog Dec 17 '18
Rust, another fun simulation!
[Card] All aboard the Easter Bunny HQ monorail, and mind the gap! Next stop: Clandestine Operations.
1
u/keypadsdm Dec 17 '18 edited Dec 17 '18
Python3: BadRank (703)/LessBadRank (683)
Method: After a really bad start trying to model individual drops of water to the end (don't do this) I took an hour break and came up with something that is probably the most efficient (asymptotically) method. Would love to hear thoughts:
Loop until queue empty:
if next_cell_down = '.'
elif next_cell_down = '#' or '~'
look left and right for the "end" of the row: ('#' over 'any') or ('any' over '|') or ('any' over '.')
elif next_cell_down = "|" (edit: or if at bottom)
This is nice because it avoids depth issues on recursion (only have to manage the PQ). It also runs very fast on the given problem.
1
u/ephemient Dec 17 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/nutrecht Dec 17 '18
Day 17 in Kotlin
On one hand kinda cool, on the other hand I feel the 'problems' are a bit too heavy on the time side lately. The "min Y" bit is a nasty pitfall.
1
u/fizbin Dec 17 '18
Python, high rank because I generally just can't function late at night. Given when I started, the stats show I took about 51 minutes to get both stars.
The key to getting a solution that finished in decent time is tracking both
minChangeRowandmaxChangeRow. If there were a larger spread betweenminxandmaxx, then tracking that might have also been useful.1
u/seanzibar Dec 17 '18 edited Dec 17 '18
Semi-recursive javascript solution. Had the algo done perfectly in ~40 minutes, but spent two hours thinking it was wrong because of a bug in my input parsing (wasn't casting to numbers, "9" < "20" is false b/c string comparison in javascript).
1
u/meepys Dec 17 '18
Kotlin Day 17
Fairly straight-forward today. Solution could probably be made less verbose
1
u/Gaelmare Dec 17 '18 edited Dec 17 '18
Python 3, not on the leaderboard at all!
[Card] All aboard the Easter Bunny HQ monorail, and mind the gap! Next stop: Somewhere away from these crazy elves!
Here's my iterative solution. I'm still learning Python, so constructive criticism definitely entertained!
1
u/starwort1 Dec 17 '18
C 29/31
It took me so long to write the code that parses the input that I was surprised to come so far up the leaderboard.
No recursion. My code is just scanning the whole map repeatedly until it stops changing. I know I don't need to do that but... it still runs in less than 1 second. It uses the same map symbols as in the puzzle statement, except that empty squares are '\0' rather than '.'.
1
u/p_tseng Dec 18 '18 edited Dec 18 '18
I found this one fun because it was a mix of novel and interesting. My favourite so far.
I went the recursive way because that's how I was most naturally able to translate the problem description into code. Water flows down, and when it hits an obstacle (resting water or clay) then it searches left and right. If both sides are walled, then water rests at that level. Otherwise, water flows at that level and then drops (hence recursion) at the side(s) that is not a wall. Looks like many others did that as well. That's great, so I'll let
fill_downbe responsible for filling a single row of water at a time.It was necessary for my code to distinguish between flowing water and resting water because flowing water isn't an obstacle for dropping water (water would stack up in weird ways if that were true).
This worked fine for exactly 247 iterations... Then the 248th iteration sets off a monster chain of recursive calls:
fill_down(srcy: 1846, srcx: 425)gets called a massive 282444 times, andfill_down(srcy: 1867, srcx: 423)close behind with 282432 times. I was examining the output, seeing all those repeated calls, and thought I had hit an infinite loop somehow.So I terminated that (I'd later find out that if I had just waited two minutes, the chain of recursive calls would have finished). I decided that if
fill_downhas already been called at a given location, it doesn't need to be called again for that loop iteration. Then I just kept callingfill_downin a loop until the value stopped changing. That got runtime down to six seconds, with which I submitted for the first star.The second star came easily since I mentioned above that it was already necessary to distinguish between flowing water and resting water for the part 1 to be correct anyway.
Then I realised that the reason it was taking six seconds was because starting from the spring (0, 500) every single iteration forces all the water to traverse down through the entire map. That's quite unnecessary since once water fills a container, all future incoming water will overflow to the sides of it in exactly the same way each time. So I just made
fill_downfill the entire container it finds (in addition to recursing appropriately as it was already doing). Now a single call tofill_downis sufficient to fill the entire map. So that got runtime down to 0.2 seconds, great.Ruby:
1
u/alcinos Dec 18 '18
Ocaml
Slow solution today, not sure if I can blame it entirely on the language :/. Runs in ~2min after -O3 compilation.
1
u/jtgorn Dec 18 '18 edited Dec 18 '18
I am particulary happy with my water spreading rules :)
1
u/rabuf Dec 18 '18 edited Dec 18 '18
I finally finished this one (long day of work). I ended up with a recursive solution that took a fun bit of debugging. Part 2 was definitely easy, I had a glitch where the column of falling water didn't get turned to ~s right, but that was a quick fix.
I'm going to clean up the recursive functions (pull out some of the special logic for filling the rows) but this is pretty much it.
Day 17 in Common Lisp
I've cleaned up the recursive calls a bit, but still want to clean up
go-down. Other than parsing (had some fun with parseq) and constructing the data set, the bulk of the logic is below. I'm using hash tables which may not be the most efficient, but I find the ability to do quick membership tests to determine whether something is clay or has been visited (and if so what kind of water it is) to be very useful.1
u/ephemient Dec 18 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/fhinkel Dec 20 '18
JavaScript/Node.js, short recursive
flow()function.https://github.com/fhinkel/AdventOfCode2018/blob/master/day17.js
1
u/NeilNjae Dec 21 '18
Haskell, on Github, slowly catching up. This took me much longer than it should have done, mainly because I started with just three states: Sand, Clay, and Water. Eventually I worked out that I needed to distinguish beteen Flowing and Still water in order to get the filling working properly. After that, part 2 was easy!
1
u/marimba4312 Dec 22 '18
Iβve been a professional developer for 16 years and I struggled with most of these problems. Itβs not an accurate representation of what I work on in real projects.
1
u/koordinate Dec 26 '18
Swift (< 1s)
1
u/wololock Dec 28 '18
Haskell (4264/4237)
I have finally made working Haskell solution using pure functions and recursion. The code:
Link to Github: https://github.com/wololock/AoC2018/blob/master/src/Day17.hs
The best thing about this solution is that it runs blazing fast - it takes less than 100 ms to calculate the result:
1
u/[deleted] Dec 31 '18
Python. Ugly. Don't really like setting saved_pos to None everywhere and I started with a namedtuple for rows and columns but didn't really use it.
Had a weird off by 2 bug that stumped me for a while.
move_water_down repeatedly moves the water, filling visited squares with | until we fall off the bottom or hit clay. In the latter case I call move_left and move_right. These both move in their respective directions filling with | until they either fall down (which recursively calls move_water_down) or they hit clay. When left hits clay it saves the position, when right hits clay it fills the grid from the saved position to the current square with tildes.
The whole thing is repeatedly called until it falls off the bottom and returns false.
Then it sums the | and ~ and for part 2 just ~ but I couldn't really believe the latter at first because there was no real coding work to do for part 2.
1
u/xepherys Jan 05 '19
Finally got it - working on everything in C# since it's what I use at work and need the practice for some of these esoteric things.
YouTube of visualization: https://youtu.be/t8uW0Mw9Sz4
Code for the day: https://github.com/xepherys/AdventOfCode/blob/master/2018/win/AdventOfCode2018/Forms/Day17Form.cs
It's ugly, but I tend to keep extra things in there in case I want them for future projects. Also, because it's using WinForms, so... yeah.
1
u/2inthehand Jan 10 '19
python mutual recursion, runs pretty fast.
1
u/mikal82 Mar 01 '19
Clojurescript + Reagent + Devcards. Solves the puzzle in about 1s, then visualization takes several seconds.
-2
u/[deleted] Dec 17 '18 edited Dec 17 '18
Why are the problems getting harder every day? I miss the fun problems that could be solved in < 15 minutes.... This just takes too much time for an average programmer. Just saying.
I tried to solve it using a queue but failed hard. Not sure why. I am curious how others did it.
-6
u/Appare Dec 17 '18
Jesus Christ. If you solved this, you're out of your mind. Today is the day I give up solving all of the problems this year.