Only 8 more days of Advent! On Day 17, we've got some water that is flowing down in the ground through sand and around clay to create reservoirs.
It's always interesting to me when they want us to model some sort of physical scenario. The purely code-based algorithms are neat, but things like mine carts and water flow are extra interesting.
Top comments (6)
A solution in python, with a lot of code to clean up.
After I failed twice your solution inspired me, so thanks! I'll post it as a separate reply.
Thirsty elves! As a Scotsman a lack of drinking water is an alien concept but we have to help where we can. I remember when this kind of programming challenge seemed impossibly hard but I've been looking forward to one all month. It's basically a depth-first search (no pun intended, although maybe it was by the Advent of Code authors?) with a slight twist: when the water reaches a level where it can flow horizontally it goes in both directions, which amounts to breadth-first searching at those branches. You could be strict with the one-square-at-a-time modelling but it's stated that the water flow is infinite, so magically doubling the water volume at a horizontal branch (by searching both ways) makes no difference to the end result. That's the beauty of thinking of the data structure as a whole rather than the individual nodes in it.
First we need to get that data into the program. We make a data model for the veins of clay described in the input data:
... and we reach for our favourite parser combinator library!
I really struggled with this one, taking three attempts. At first I did a recursive search as hinted at above, but it ran out of memory and heap space. Back to the drawing board, I stuck with the recursion (adding the use of Kotlin's
tailrec), building a set of mutually recursive functions representing the various states of flowing down, flowing across inside container, flowing up when there are walls on both sides. I got it to mostly work but couldn't get the right answer out. So I abandoned that and ended up with the solution here.
The space is represented as a 2D grid in which I fill in the veins of clay first, then fill in with flowing and standing water as the filling algorithm progresses. Flows can split so there is a set of current flow positions and the algorithm proceeds until this is empty. The first condition handled is easy - when we reach the bottom of the bounding box, the water drains out so we just remove that flow.
We need to look at where the water is going and act appropriately.
If the space is empty the water just flows down. If it hits already flowing water the streams just merge so we abort the current one.
If the space has standing water or clay, it gets more complex. We scan horizontally both left and right looking for features. The interesting features are walls, which contain the water, and edges, over which it flows. We represent these with a really simple sum type.
We're going to fill a horizontal row from the flow point to the feature on both sides. But if either side is an edge we'll fill with flowing water, and if both sides are walls we'll fill with still water then move the flow upwards to fill up the container.
The rest is just ancillary functions. Finding features is just a scan for the appropriate geometry:
Sequences came in handy for generating the positions for each side of a row, then concatenating them to get the full set of position to fill.
Answering the problem questions was a simple query over the grid.
Client-side js, just pasting it into the console with the puzzle input. Takes a minute or so to complete, a lot of recursive calls. gridN value is arbitrary, just big enough for the puzzle, I think probably all inputs are within this range. Took me a while to figure out the edge case, where the water falls down from both sides. But it works now, even with the weird tricks here and there.
This one was hard! I think mainly because of my non-recursive approach.
I'm gonna omit reader.js which is the same as the other solutions and jump to the point:
I don't like my solution much, but it solves the problem :-) I had problems with several shapes and combinations of already partially filled containers, but I fixed them in the end.