Ryan Palo

Posted on Dec 17, 2018

AoC Day 17: Reservoir Research

#adventofcode #discuss

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!

Top comments (6)

Juan Manuel Gimeno • Dec 17 '18

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())

Neil Gall • Dec 18 '18

After I failed twice your solution inspired me, so thanks! I'll post it as a separate reply.

Javid Asgarov • Dec 28 '18 • Edited

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.

(function() {
  let data = document.getElementsByTagName('pre')[0].innerHTML.split('\n');
  data.pop();
  let gridN = 3000;

  let minY = Infinity;
  let maxY = 0;
  let minX = Infinity;
  let maxX = 0;
  let types = {
    water: '~',
    dry: '|',
    clay: '#',
    sand: '.'
  };

  function getFirstValue(str) {
    if (str[0] === 'x') {
      return { x: +str.slice(2) };
    } else {
      return { y: str.slice(2) };
    }
  }

  function getSecondValue(str) {
    let values = str.slice(2).split('..');
    let start = +values[0];
    let end = +values[1];
    let result = [];
    for (let i = start; i <= end; i++) {
      result.push(i);
    }
    return result;
  }

  function makeGrid(n) {
    const fabric = [];
    for (let i = 0; i <= n; i++) {
      fabric[i] = [];
      fabric[i][n] = '.';
      fabric[i].fill('.', 0, n);
    }
    return fabric;
  }

  function putValuesInGrid(first, second, grid) {
    let arr = Array.isArray(first) ? first : second;
    let x = Array.isArray(first) ? second.x : first.x;
    let y = Array.isArray(first) ? second.y : first.y;
    if (y) {
      grid[y].forEach((item, i) => {
        if (arr.indexOf(i) > 0) {
          grid[y][i] = '#';
        }
      });
    } else {
      for (let i = arr[0]; i <= arr[arr.length - 1]; i++) {
        grid[i][x] = '#';
      }
    }
  }

  function fillGrid() {
    const grid = makeGrid(gridN);
    grid[0][500] = '+';
    data.forEach(str => {
      let splitMe = str.split(', ');
      let first = getFirstValue(splitMe[0]);
      let second = getSecondValue(splitMe[1]);
      let x = first.x !== undefined ? first : second;
      let y = first.y !== undefined ? first : second;
      if (Array.isArray(y)) {
        minY = y[0] < minY ? y[0] : minY;
        maxY = y[y.length - 1] > maxY ? y[y.length - 1] : maxY;
      } else {
        minY = y < minY ? y : minY;
        maxY = y > maxY ? y : maxY;
      }
      if (Array.isArray(x)) {
        minX = x[0] < minX ? x[0] : minX;
        maxX = x[x.length - 1] > maxX ? x[x.length - 1] : maxX;
      } else {
        minX = x < minX ? x : minX;
        maxX = x > maxX ? x : maxX;
      }
      putValuesInGrid(first, second, grid);
    });
    return grid;
  }

  function goSideway(grid, x, i, value) {
    let xVal = x + value;
    let fallsThrough = false;
    while (
      (grid[i][xVal] === types.sand || grid[i][xVal] === types.dry) &&
      x >= 0 &&
      !fallsThrough
    ) {
      grid[i][xVal] = types.dry;
      const bottom = grid[i + 1][xVal];
      const isFalling = bottom === types.sand || bottom === types.dry;
      if (isFalling) {
        fallsThrough = true;
      } else {
        xVal += value;
      }
    }
    if (fallsThrough) {
      return xVal;
    }
    if (grid[i][xVal] == types.clay) {
      return null;
    }
  }

  function settleWater(grid, x, y) {
    for (let z = x; grid[y][z] !== types.clay; z++) {
      grid[y][z] = types.water;
    }
    for (let z = x; grid[y][z] !== types.clay; z--) {
      grid[y][z] = types.water;
    }
  }

  function lookDown(x, y, grid) {
    let i = y + 1;
    let canGoDown = grid[i][x] === types.sand || grid[i][x] === types.dry;
    while (canGoDown && i <= maxY) {
      grid[i][x] = types.dry;
      i++;
      canGoDown = grid[i][x] === types.sand || grid[i][x] === types.dry;
    }
    let canSettle = grid[i][x] === types.clay || grid[i][x] === types.water;

    if (canSettle && i <= maxY && grid[i - 1][x] !== types.water) {
      i = i - 1;
      let leftX = goSideway(grid, x, i, -1);
      let rightX = goSideway(grid, x, i, 1);
      if (leftX) {
        grid[i + 1][leftX] = types.dry;
        lookDown(leftX, i + 1, grid);
      }
      if (rightX) {
        grid[i + 1][rightX] = types.dry;
        lookDown(rightX, i + 1, grid);
      }
      leftX = goSideway(grid, x, i, -1);
      rightX = goSideway(grid, x, i, 1);
      if (leftX === null && rightX === null) {
        settleWater(grid, x, i);
        lookDown(x, y, grid);
      }
    }
  }

  function printData(grid) {
    let str = '';
    grid.slice(0, maxY + 1).forEach((row, index) => {
      str += row.slice(minX, maxX + 10).join('');
      str += '<br>';
    });
    document.body.style.fontSize = '18px';
    document.body.innerHTML = '<code>' + str + '</code>';
  }

  function calculateAnswer(grid) {
    let answer = 0;
    let secondAnswer = 0;
    grid.forEach((row, y) => {
      row.forEach(value => {
        let isWater = value === types.water || value === types.dry;
        let isSettled = value === types.water;
        if (y <= maxY && y >= minY && isWater) {
          answer += 1;
        }
        if (y <= maxY && y >= minY && isSettled) {
          secondAnswer += 1;
        }
      });
    });
    console.log(answer, 'answer');
    console.log(secondAnswer, 'second answer');
  }

  function findAnswer() {
    const grid = fillGrid();
    lookDown(500, 0, grid);
    calculateAnswer(grid);
    printData(grid);
  }

  const answer = findAnswer();
})();

Neil Gall • Dec 18 '18 • Edited

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)
    }
    throw IllegalStateException("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.

fun Pos.to(end: Pos): Sequence<Pos> {
    val dir = if (y == end.y) {
        if (x > end.x) Pos::left else Pos::right
    } else if (x == end.x) {
        if (y > end.y) Pos::up else Pos::down
    } else throw IllegalArgumentException("Positions must agree on one axis")
    var p = this
    return sequence {
        while (p != end) {
            yield(p)
            p = dir(p)
        }
        yield(end)
    }
}

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

fun part1(input: Scan): Int {
    input.fill()
    return input.boundingBox.positions().count { p ->
        input[p] == Fill.STILL_WATER || input[p] == Fill.FLOWING_WATER 
    }
}

Full code

Tiago Romero Garcia • Dec 23 '18

Javascript solution

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:

17-common.js

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

const MAP = {
    CLAY: '#',
    SAND: '.',
    SPRING: '+',
    WATER_DOWN: '|',
    WATER_RESTING: '~'
};

const DIRECTIONS = {
    LEFT: 'left',
    RIGHT: 'right',
    DOWN: 'down',
    UP: 'up'
};

class WaterFlow {
    constructor({x, y, parent, left, right, down, up, cache}) {
        this.x = x;
        this.y = y;
        this.parent = parent;
        this.left = left;
        this.right = right;
        this.down = down;
        this.up = up;
    }

    flow(map, cache) {        
        const next = [];        
        const { x, y, parent } = this;
        const squareBelow = map[y+1][x];

        // If square below is empty, flow down
        if (squareBelow === MAP.SAND) {
            next.push(this.flowDown(map, cache, x, y));
        }
        // If it came from its parent, then flow to the sides
        else if ([MAP.CLAY, MAP.WATER_RESTING].includes(squareBelow)) {
            // Flow to the left
            const { leftmostWaterFlow, newLeftmostWaterFlow, hasReachedLeftClay } = this.flowToTheLeft(map, cache);
            if (!hasReachedLeftClay && newLeftmostWaterFlow) {
                next.push(newLeftmostWaterFlow);
            }

            // Flow to the right
            const { rightmostWaterFlow, newRightmostWaterFlow, hasReachedRightClay } = this.flowToTheRight(map, cache);
            if (!hasReachedRightClay && newRightmostWaterFlow) {
                next.push(newRightmostWaterFlow);
            }

            // If trapped on both sides, return up
            if (hasReachedLeftClay && hasReachedRightClay) {
                this.markWaterResting(map, leftmostWaterFlow, rightmostWaterFlow);
                const upstream = this.findUpstream(leftmostWaterFlow, rightmostWaterFlow);
                next.push(upstream);
            }
        }

        return next;
    }

    flowDown(map, cache, x, y) {
        this.down = newWaterFlow({x, y: y+1, up: this, parent: DIRECTIONS.UP}, cache);
        map[y+1][x] = MAP.WATER_DOWN;
        return this.down;
    }

    flowToTheLeft(map, cache) {
        let hasReachedLeftClay = false;
        let { x, y } = this;
        let currentWaterFlow = this;
        let newLeftmostWaterFlow;
        let nextSquare = map[y][x-1];
        let nextSquareBelow = map[y+1][x-1];

        while ([MAP.SAND, MAP.WATER_DOWN, MAP.WATER_RESTING].includes(nextSquare) && nextSquareBelow !== MAP.SAND) {
            if (nextSquare === MAP.SAND) {
                currentWaterFlow.left = newWaterFlow({x: x-1, y, right: currentWaterFlow, parent: DIRECTIONS.RIGHT}, cache);
                map[y][x-1] = MAP.WATER_DOWN;
            }
            else if (!currentWaterFlow.left) {
                currentWaterFlow.left = getWaterFlowBySquare(cache, {x: x-1, y});
                currentWaterFlow.left.right = currentWaterFlow;
            }
            currentWaterFlow = currentWaterFlow.left;

            x--;
            nextSquare = map[y][x-1];
            nextSquareBelow = map[y+1][x-1];
        }
        if (nextSquare === MAP.CLAY) {
            hasReachedLeftClay = true;
        }
        else if (map[y+1][x] === MAP.WATER_DOWN) {
            do {
                currentWaterFlow = currentWaterFlow.down;
                y++;
            } while (map[y+1][x] === MAP.WATER_DOWN);
            newLeftmostWaterFlow = currentWaterFlow;
        }
        else if (nextSquareBelow === MAP.SAND) {
            newLeftmostWaterFlow = currentWaterFlow.left = newWaterFlow({x: x-1, y, right: currentWaterFlow, parent: DIRECTIONS.RIGHT}, cache);
            map[y][x-1] = MAP.WATER_DOWN;
        }

        return { hasReachedLeftClay, leftmostWaterFlow: currentWaterFlow, newLeftmostWaterFlow };
    }

    flowToTheRight(map, cache) {
        let hasReachedRightClay = false;
        let { x, y } = this;
        let currentWaterFlow = this;
        let newRightmostWaterFlow;
        let nextSquare = map[y][x+1];
        let nextSquareBelow = map[y+1][x+1];

        while ([MAP.SAND, MAP.WATER_DOWN, MAP.WATER_RESTING].includes(nextSquare) && nextSquareBelow !== MAP.SAND) {
            if (nextSquare === MAP.SAND) {
                currentWaterFlow.right = newWaterFlow({x: x+1, y, left: currentWaterFlow, parent: DIRECTIONS.LEFT}, cache);
                map[y][x+1] = MAP.WATER_DOWN;
            }
            else if (!currentWaterFlow.right){
                currentWaterFlow.right = getWaterFlowBySquare(cache, {x: x+1, y});
                currentWaterFlow.right.left = currentWaterFlow;
            }
            currentWaterFlow = currentWaterFlow.right;

            x++;
            nextSquare = map[y][x+1];
            nextSquareBelow = map[y+1][x+1]
        }
        if (nextSquare === MAP.CLAY) {
            hasReachedRightClay = true;
        }
        else if (map[y+1][x] === MAP.WATER_DOWN) {
            do {
                currentWaterFlow = currentWaterFlow.down;
                y++;
            } while (map[y+1][x] === MAP.WATER_DOWN);
            newRightmostWaterFlow = currentWaterFlow;
        }
        else if (nextSquareBelow === MAP.SAND) {
            newRightmostWaterFlow = currentWaterFlow.right = newWaterFlow({x: x+1, y, left: currentWaterFlow, parent: DIRECTIONS.LEFT}, cache);
            map[y][x+1] = MAP.WATER_DOWN;
        }

        return { hasReachedRightClay, rightmostWaterFlow: currentWaterFlow, newRightmostWaterFlow };
    }

    markWaterResting(map, leftmostWaterFlow, rightmostWaterFlow) {
        let {x, y} = leftmostWaterFlow;
        let maxX = rightmostWaterFlow.x;
        for (let i = x; i <= maxX; i++) {
            map[y][i] = MAP.WATER_RESTING;
        }
    }

    findUpstream(leftmostWaterFlow) {
        let square = leftmostWaterFlow;
        while (square.right && square.parent !== DIRECTIONS.UP) {
            square = square.right;
        }

        return square[square.parent];
    }

}

const buildMap = lines => {
    const xRegex = /^x=(?<x>\d+), y=(?<y1>\d+)..(?<y2>\d+)$/;
    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 () => {
    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, [MAP.WATER_RESTING]);
    console.log(`The number of remaining resting water tiles is ${squaresCount}.`);
})();

E. Choroba • Dec 18 '18 • Edited

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.

DEV Community

AoC Day 17: Reservoir Research

Top comments (6)

Part 1

Javascript solution

17-common.js

17a.js

17b.js

Read next

syntackle.live is now syntackle.com

What I learned in 6 months of working on a CodeGen dev tool GPT Pilot

Music Monday — What are you listening to? (Funk, Soul, Disco, & Reggae Edition)

Why YouTube Never Runs Out of Storage? It's NOT just CLOUD!