AoC Day 17: Reservoir Research

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.

Good luck!

Discussion

A solution in python, with a lot of code to clean up.

import collections
import re

Line = collections.namedtuple('Line', 'min_x max_x min_y max_y')

range_regexp = re.compile(r'\s*(?P<axis>[x|y])=(?P<min>\d+)(\.\.(?P<max>\d+))?\s*')

class Ground:

def __init__(self, lines):
self.parsed_lines = [parse_line(line) for line in lines]
self._get_limits()
self._create_slice()
self._fill_with_clay()
self._create_spring()

def _get_limits(self):
self.min_x = min(l.min_x for l in self.parsed_lines) - 1
self.max_x = max(l.max_x for l in self.parsed_lines) + 1
self.real_min_y = min(l.min_y for l in self.parsed_lines)
self.min_y = min(self.real_min_y, 0)
self.max_y = max(l.max_y for l in self.parsed_lines)
self.width = self.max_x - self.min_x + 1
self.height = self.max_y - self.min_y + 1

def _create_slice(self):
self.slice = [['.' for _ in range(self.width)] for _ in range(self.height)]

def _fill_with_clay(self):
for min_x, max_x, min_y, max_y in self.parsed_lines:
for x in range(min_x, max_x + 1):
for y in range(min_y, max_y + 1):
self.set(x, y, '#')

def _create_spring(self):
self.set(500, 0, '+')
self.drops = [(500, 0)]

def get(self, x, y):
return self.slice[y - self.min_y][x - self.min_x]

def set(self, x, y, val):
self.slice[y - self.min_y][x - self.min_x] = val

def show(self):
return '\n'.join(''.join(self.get(x, y)
for x in range(self.min_x, self.max_x + 1))
for y in range(self.min_y, self.max_y + 1))

def find_bottom(self, x, y, bottom):
xx_min = x
while self.get(xx_min - 1, y) == bottom:
xx_min -= 1
xx_max = x
while self.get(xx_max + 1, y) == bottom:
xx_max += 1
return xx_min, xx_max

def find_sand(self, x, y):
xx_min = x
while xx_min > self.min_x + 1 and self.get(xx_min - 1, y) == '.':
xx_min -= 1
xx_max = x
while xx_max < self.max_x - 1 and self.get(xx_max + 1, y) == '.':
xx_max += 1
if self.get(xx_min - 1, y) == '#' and self.get(xx_max + 1, y) == '#':
return xx_min, xx_max
else:
return None

def steps(self):
while True:
if len(self.drops) == 0:
return

(x, y) = self.drops.pop()

if y == self.max_y:
continue

if self.get(x, y) == '+':
if self.get(x, y + 1) == '.':
self.set(x, y + 1, '|')
yield
self.drops.append((x, y + 1))
elif self.get(x, y) == '|':
if self.get(x, y + 1) == '.':
self.set(x, y + 1, '|')
yield
self.drops.append((x, y))
self.drops.append((x, y + 1))
elif self.get(x, y + 1) in ('#', '~'):
if self.get(x - 1, y) == '.':
self.set(x - 1, y, '|')
yield
self.drops.append((x - 1, y))
elif self.get(x - 1, y) == '#' and self.get(x,y) == '|':
right = self.find_right(x, y, '|')
if right:
self.rest_water(x, right, y)
yield

if self.get(x + 1, y) == '.':
self.set(x + 1, y, '|')
yield
self.drops.append((x + 1, y))
elif self.get(x + 1, y) == '#' and self.get(x,y) == '|':
left = self.find_left(x, y, '|')
if left:
self.rest_water(left, x, y)
yield

def run(self, debug=False):
if debug:
self.print()
for _ in self.steps():
if debug:
self.print()

def print(self):
print()
print(self.show())

def count(self):
return sum(1 for row in self.slice for c in row if c in ('|', '~'))

def count_dry(self):
return sum(1 for row in self.slice for c in row if c == '~')

def find_right(self, x, y, char):
assert self.get(x, y) == char
assert self.get(x, y + 1) in ('#', '~')
x_max = x
while self.get(x_max + 1, y) == char and self.get(x_max + 1, y + 1) in ('#', '~'):
x_max += 1
if self.get(x_max + 1, y) == '#' and self.get(x_max + 1, y + 1) in ('#', '~'):
return x_max
else:
return None

def find_left(self, x, y, char):
assert self.get(x, y) == char
assert self.get(x, y + 1) in ('#', '~')
x_min = x
while self.get(x_min - 1, y) == char and self.get(x_min - 1, y + 1) in ('#', '~'):
x_min -= 1
if self.get(x_min - 1, y) == '#' and self.get(x_min - 1, y + 1) in ('#', '~'):
return x_min
else:
return None

def rest_water(self, x_min, x_max, y):
for x in range(x_min, x_max + 1):
self.set(x, y, '~')

def parse_line(line):
limits = [0] * 4
for part in line.split(','):
groups = range_regexp.match(part).groupdict()
offset = 0 if groups['axis'] == 'x' else 2
min_ = int(groups['min'])
max_ = int(groups['max']) if groups['max'] else min_
limits[offset] = min_
limits[offset + 1] = max_
return Line(*limits)

def test_parse_line():
assert Line(495, 495, 2, 7) == parse_line('x=495, y=2..7')
assert Line(495, 501, 7, 7) == parse_line('y=7, x=495..501')
assert Line(501, 501, 3, 7) == parse_line('x=501, y=3..7')
assert Line(498, 498, 2, 4) == parse_line('x=498, y=2..4')
assert Line(506, 506, 1, 2) == parse_line('x=506, y=1..2')
assert Line(498, 498, 10, 13) == parse_line('x=498, y=10..13')
assert Line(504, 504, 10, 13) == parse_line('x=504, y=10..13')
assert Line(498, 504, 13, 13) == parse_line('y=13, x=498..504')

def test_show():
expected = """\
......+.......
............#.
.#..#.......#.
.#..#..#......
.#..#..#......
.#.....#......
.#.....#......
.#######......
..............
..............
....#.....#...
....#.....#...
....#.....#...
....#######..."""

with open('test_input.txt', 'r') as test:
test_ground = Ground(line.strip() for line in test)
assert expected == test_ground.show()

def test_run():
expected = """\
......+.......
......|.....#.
.#..#||||...#.
.#..#~~#|.....
.#..#~~#|.....
.#~~~~~#|.....
.#~~~~~#|.....
.#######|.....
........|.....
...|||||||||..
...|#~~~~~#|..
...|#~~~~~#|..
...|#~~~~~#|..
...|#######|.."""

with open('test_input.txt', 'r') as test:
test_ground = Ground(line.strip() for line in test)
test_ground.run()
assert expected == test_ground.show()

def test_count():
with open('test_input.txt', 'r') as test:
test_ground = Ground(line.strip() for line in test)
test_ground.run()
assert 57 == test_ground.count()

# Problematic case

def test_problem():
expected = """\
..........+..........
.....................
.#.................#.
.#.................#.
.#.................#.
.#.................#.
.#.................#.
.#.................#.
.#......######.....#.
.#......#....#.....#.
.#......#....#.....#.
.#......######.....#.
.#.................#.
.#.................#.
.###################."""

with open('problem_input.txt', 'r') as test:
test_ground = Ground(line.strip() for line in test)
test_ground.print()
assert expected == test_ground.show()
test_ground.run()
test_ground.print()

if __name__ == '__main__':
with open('input.txt', 'r') as file:
ground = Ground(line.strip() for line in file)
ground.run()
print("Part1:", ground.count() - ground.real_min_y + 1)
print("Part2:", ground.count_dry())


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:

sealed class Vein {
data class Vertical(val x: Int, val y: IntRange): Vein()
data class Horizontal(val y: Int, val x: IntRange): Vein()
}


... and we reach for our favourite parser combinator library!

fun parse(input: String): List<Vein> {
val integer = INTEGER.map(String::toInt)
val integerRange = sequence(integer, string("..").next(integer)) { x, y -> x..y }
val verticalVein: Parser<Vein> = sequence(string("x=").next(integer), string(", y=").next(integerRange), Vein::Vertical)
val horizontalVein: Parser<Vein> = sequence(string("y=").next(integer), string(", x=").next(integerRange), Vein::Horizontal)
val vein = or(verticalVein, horizontalVein)
return vein.sepBy(WHITESPACES).parse(input.trim())
}


Part 1

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.

    val flows = mutableSetOf<Pos>(Pos(500, 0))

while (!flows.isEmpty()) {
val flow = flows.first()
flows.remove(flow)

if (flow.y == boundingBox.y.endInclusive) {
this[flow] = Fill.FLOWING_WATER
continue
}
...


We need to look at where the water is going and act appropriately.

        when (this[flow.down()]) {


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.

            Fill.EMPTY -> {
this[flow] = Fill.FLOWING_WATER
flows += flow.down()
}

Fill.FLOWING_WATER -> {
this[flow] = Fill.FLOWING_WATER
}


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.

sealed class Feature {
abstract val pos: Pos
data class Wall(override val pos: Pos): Feature()
data class Edge(override val pos: Pos): Feature()
}


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.

            Fill.CLAY, Fill.STILL_WATER -> {
val featureLeft = findFeature(flow, Pos::left)
val featureRight = findFeature(flow, Pos::right)
val fillRange = flow.to(featureLeft.pos) + flow.to(featureRight.pos)

if (featureLeft is Feature.Edge || featureRight is Feature.Edge) {
fill(fillRange, Fill.FLOWING_WATER)
if (featureLeft is Feature.Edge) flows += featureLeft.pos
if (featureRight is Feature.Edge) flows += featureRight.pos
} else {
fill(fillRange, Fill.STILL_WATER)
flows += flow.up()
}
}


The rest is just ancillary functions. Finding features is just a scan for the appropriate geometry:

fun Scan.findFeature(pos: Pos, dir: (Pos) -> Pos): Feature {
var p = pos
while (contains(dir(p))) {
if (this[dir(p)] == Fill.CLAY)
return Feature.Wall(p)
else if (this[p.down()] == Fill.EMPTY || this[p.down()] == Fill.FLOWING_WATER)
return Feature.Edge(p)
p = dir(p)
}
const yRegex = /^y=(?<y>\d+), x=(?<x1>\d+)..(?<x2>\d+)$/; const map = []; let minY = Number.POSITIVE_INFINITY; let maxY = -1; let minX = Number.POSITIVE_INFINITY; let maxX = -1; // Marking clay squares for (const line of lines) { let match = line.match(xRegex); if (match) { let { x, y1, y2 } = match.groups; x = +x; y1 = +y1; y2 = +y2; for (let i = y1; i <= y2; i++) { if (!map[i]) map[i] = []; map[i][x] = MAP.CLAY; } minY = Math.min(minY, y1); maxY = Math.max(maxY, y2); minX = Math.min(minX, x); maxX = Math.max(maxX, x); } else { match = line.match(yRegex); if (match) { let { y, x1, x2 } = match.groups; y = +y; x1 = +x1; x2 = +x2; if (!map[y]) map[y] = []; for (let i = x1; i <= x2; i++) { map[y][i] = MAP.CLAY; } minY = Math.min(minY, y); maxY = Math.max(maxY, y); minX = Math.min(minX, x1); maxX = Math.max(maxX, x2); } } } minX--; maxX++; // Marking spring squares map[0] = []; map[0][500] = MAP.SPRING; // Marking sand squares for (let i = 0; i <= maxY+1; i++) { if (!map[i]) map[i] = []; for (let j = minX-1; j <= maxX+1; j++) { map[i][j] = map[i][j] || MAP.SAND; } } return { map, minY, maxY, minX, maxX }; }; const getKey = ({x, y}) => ${x},${y}; const getWaterFlowBySquare = (cache, square) => cache.get(getKey(square)); const setWaterFlowBySquare = (cache, waterFlow) => cache.set(getKey(waterFlow), waterFlow); const newWaterFlow = (args, cache) => { const waterFlow = new WaterFlow(args); setWaterFlowBySquare(cache, waterFlow); return waterFlow; }; const openTheTap = (map, minY, maxY) => { let hasOverflown = false; const cache = new Map(); const waterFlow = [new WaterFlow({ x: 500, y: 0 })]; do { const waterSquare = waterFlow.shift(); const newFlow = waterSquare.flow(map, cache); waterFlow.push(...newFlow.filter(flow => flow.y <= maxY)); } while (waterFlow.length > 0); }; const countWater = (map, minY, maxY, minX, maxX, types = [MAP.WATER_DOWN, MAP.WATER_RESTING]) => { let squaresCount = 0; for (let i = minY; i <= maxY; i++) { for (let j = minX; j <= maxX; j++) { if (types.includes(map[i][j])) { squaresCount++; } } } return squaresCount; }; module.exports = { MAP, buildMap, openTheTap, countWater };  17a.js const { readFile } = require('./reader'); const { buildMap, openTheTap, countWater } = require('./17-common'); (async () => { const lines = await readFile('17-input.txt'); const { map, minY, maxY, minX, maxX } = buildMap(lines); openTheTap(map, minY, maxY, minX, maxX); const squaresCount = countWater(map, minY, maxY, minX, maxX); console.log(The number of tiles the water can reach is${squaresCount}.);
})();


17b.js

const { readFile } = require('./reader');

const {
MAP,
buildMap,
openTheTap,
countWater
} = require('./17-common');

(async () => {
console.log(The number of remaining resting water tiles is \${squaresCount}.);