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:

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.

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:

funScan.findFeature(pos:Pos,dir:(Pos)->Pos):Feature{varp=poswhile(contains(dir(p))){if(this[dir(p)]==Fill.CLAY)returnFeature.Wall(p)elseif(this[p.down()]==Fill.EMPTY||this[p.down()]==Fill.FLOWING_WATER)returnFeature.Edge(p)p=dir(p)}throwIllegalStateException("Can't find a feature at row ${pos.y}")}

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.

funPos.to(end:Pos):Sequence<Pos>{valdir=if(y==end.y){if(x>end.x)Pos::leftelsePos::right}elseif(x==end.x){if(y>end.y)Pos::upelsePos::down}elsethrowIllegalArgumentException("Positions must agree on one axis")varp=thisreturnsequence{while(p!=end){yield(p)p=dir(p)}yield(end)}}

Answering the problem questions was a simple query over the grid.

## re: AoC Day 17: Reservoir Research VIEW POST

FULL DISCUSSIONThirsty 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

bothdirections, 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!

## Part 1

I

reallystruggled 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

upwardsto 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.

Full code