## DEV Community

Nicky Meuleman

Posted on • Originally published at nickymeuleman.netlify.app

# Advent of Code 2022 Day 14

## Day 14: Regolith Reservoir

TL;DR: my solution in Rust

The distress signal you received yesterday came from a cave behind a waterfall.

The cave is slowly filling with sand!

Today's input file is the list of rock edges.

An example input looks like this:

``````498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
``````

Every rock formation has perfectly square edges.

Between every edge it returned, you can draw a straight line, every point on the line is also a rock.

This scan means that there are two paths of rock.

1. The first path consists of two straight lines
2. The second path consists of three straight lines.
• A unit of sand is big enough to fill one coordinate.
• A unit of sand has to come to a rest before an other one starts falling.
• The source of sand is at coordinates `x=500`, and `y=0`.

For every position sand is in, a sequence of checks are done to determine where it goes next, or if it stays put:

1. Sand goes straight down one step.
2. If that position is blocked, it goes down and to the left instead.
3. If that position is blocked, it goes down and to the right instead.
4. If that position is blocked, the sand comes to a rest.

Every unit of sand continues falling until it comes to a rest.

At that point, the next unit of sand starts falling.

## Parsing

Good news everyone, the `Coord` struct is back to represent a coordinate in our square grid.

``````struct Coord {
x: i32,
y: i32,
}
``````

I parsed the input into a list of lists.
Each item is a list containing rock edge coordinates.

``````fn parse() -> Vec<Vec<Coord>> {

input
.lines()
.map(|line| {
line.split(" -> ")
.map(|coords| {
let (x, y) = coords.split_once(',').unwrap();
let x = x.parse().unwrap();
let y = y.parse().unwrap();
Coord { x, y }
})
.collect()
})
.collect()
}
``````

## Part 1

You don't know what's underneath the lowest point of your scan, you assume it's an endless abyss.

The question asks how many units of sand came to a rest before sand starts falling into the abyss.

in pseudocode:

``````let rock_lines = parse();
let mut cave = // build a cave out of rock lines
let max_y = // y coordinate of the lowest rock in the cave;
let start = Coord { x: 500, y: 0 };

loop {
let mut sand = start;
// the sand falls until it can't anymore
sand = sand.fall();
if sand.is_falling() {
if sand.y > max_y {
// sand is falling into the abyss
}
} else {
// insert final coord of this piece of sand into the cave
}
}
``````

### Helpers

Every tile in the cave grid can be in 3 possible states:

1. It's air
2. It's a rock
3. It's sand
``````enum Tile {
Rock,
Sand,
Air,
}
``````

I'll construct the `cave` in two steps.

1. create a collection of every rock coordinate in the cave.
2. create the cave as 2D list. Where every item in the outer list is a row, and every row is a list of `Tile`.
``````fn rocks_in_cave(rock_lines: Vec<Vec<Coord>>) -> HashSet<Coord> {
rock_lines
.iter()
.flat_map(|path| {
path.iter().tuple_windows().flat_map(|(start, end)| {
let diff_x = end.x - start.x;
let diff_y = end.y - start.y;
let direction = Coord {
x: diff_x.signum(),
y: diff_y.signum(),
};
// one of two differences is always 0 because rock lines are vertical or horizontal
let amount = diff_x.abs().max(diff_y.abs()) as usize;

// generate Coord for every tile in a window
(0..=amount).map(move |amount| {
let diff_x = amount as i32 * direction.x;
let diff_y = amount as i32 * direction.y;

Coord {
x: start.x + diff_x,
y: start.y + diff_y,
}
})
})
})
.collect()
}
``````

Rusty aside: a `HashSet` requires that the elements implement the `Eq` and `Hash` traits.

I derive those, it works.
While I'm at it, I make sure I can copy a coordinate too.

``````#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct Coord {
x: i32,
y: i32,
}
``````

To create the cave from that

``````let rock_lines = parse();
let rocks = rocks_in_cave(rock_lines);

let max_y = rocks.iter().map(|p| p.y).max().unwrap();
// the width in the puzzle is infinite
// the needed width at maximum is the base of an Isosceles triangle with max_y height and a top edge at x=500
let width = 500 + max_y + 2;
// start cave filled with air
let mut cave = vec![vec![Tile::Air; width as usize]; (max_y + 2) as usize];
for pos in rocks {
cave[pos.y as usize][pos.x as usize] = Tile::Rock;
}
``````

A piece of sand has a `Coord`.

If it falls, it falls in one of three spots.
I call those possible spots the `neighbours` of a `Coord`.

``````impl Coord {
fn neighbours(&self) -> [Coord; 3] {
let down = Coord {
x: self.x,
y: self.y + 1,
};
let down_left = Coord {
x: self.x - 1,
y: self.y + 1,
};
let down_right = Coord {
x: self.x + 1,
y: self.y + 1,
};

[down, down_left, down_right]
}
}
``````

When a piece of sand falls, it follows the rules mentioned at the top.
Falling into the place of the first neighbour it can.

``````impl Coord {
fn neighbours(&self) -> [Coord; 3] {
// --- snip ---
}

/// returns Some(Coord) of this coords first neighbour it can move to, none if the sand is static
fn next(&self, cave: &[Vec<Tile>]) -> Option<Coord> {
// first available position in neighbours (down, left-down, right-down)
self.neighbours()
.into_iter()
.find(|coord| cave[coord.y as usize][coord.x as usize] == Tile::Air)
}
}
``````

This way of checking for a possible next position of falling sand is perfect to adjust our pseudocode to use a `while let` loop.

### Final code

``````pub fn part_1() -> usize {
let rock_lines = parse();
let rocks = rocks_in_cave(rock_lines);

let start = Coord { x: 500, y: 0 };
let max_y = rocks.iter().map(|p| p.y).max().unwrap();
// the width is a guessing game, in the puzzle it's infinite
let width = 500 + max_y + 2;

// start cave filled with air
let mut cave = vec![vec![Tile::Air; width as usize]; (max_y + 2) as usize];
for pos in rocks {
cave[pos.y as usize][pos.x as usize] = Tile::Rock;
}

for i in 0.. {
let mut sand = start;
// the sand falls until it can't anymore and next returns None
while let Some(next_air_coord) = sand.next_p1(&cave) {
sand = next_air_coord;
if sand.y > max_y {
return i;
}
}

// insert final coord into the cave as sand tile
cave[sand.y as usize][sand.x as usize] = Tile::Sand;
}

unreachable!()
}
``````

## Part 2

There was no abyss!

The floor is 2 tiles underneath the lowest rock in your scan.
It appears to be infinite.

The question asks how many units of sand came to a rest when the entry at x=500, y=0 is blocked.

A few additions to the code!

The `next` method on `Coord` needs to check if a unit of sand hits the floor.
It can't move down further once it does, so it comes to rest.

``````/// returns Some(Coord) of this coords first Coord it can move to, none if it is static
fn next(&self, cave: &[Vec<Tile>], floor_y: i32) -> Option<Coord> {
if (self.y + 1) == floor_y {
// hit floor
return None;
}
// first available position in neighbours (down, left-down, right-down)
self.neighbours()
.into_iter()
.find(|p| cave[p.y as usize][p.x as usize] == Tile::Air)
}
``````

The condition where the code stops looping changed too.

The one from part1 is removed, and a return is added at the end of the infinite loop.
It checks if the sand is at the beginning after it came to rest.

``````// --- snip ---
for i in 0.. {
let mut sand = start;
// the sand falls until it can't anymore and next returns None
while let Some(next_air_coord) = sand.next_p2(&cave, floor_y) {
sand = next_air_coord;
}

// insert final coord into the cave as sand tile
cave[sand.y as usize][sand.x as usize] = Tile::Sand;

if sand == start {
return i + 1;
}
}
``````

### Final code

``````use itertools::Itertools;

pub fn part_2() -> usize {
let rock_lines = parse();
let rocks = rocks_in_cave(rock_lines);

let start = Coord { x: 500, y: 0 };
let max_y = rocks.iter().map(|p| p.y).max().unwrap();
// the width is a guessing game, in the puzzle it's infinite
let width = 500 + max_y + 2;
let floor_y = max_y + 2;

// start cave filled with air
let mut cave = vec![vec![Tile::Air; width as usize]; (max_y + 2) as usize];
for pos in rocks {
cave[pos.y as usize][pos.x as usize] = Tile::Rock;
}

for i in 0.. {
let mut sand = start;
// the sand falls until it can't anymore and next returns None
while let Some(next_air_coord) = sand.next(&cave, floor_y) {
sand = next_air_coord;
}

// insert final coord into the cave as sand tile
cave[sand.y as usize][sand.x as usize] = Tile::Sand;

if sand == start {
return i + 1;
}
}

unreachable!()
}
``````

## Optimization

A possible optimization is to keep track of empty positions while a unit of sand is falling.

Every subsequent unit of sand will follow the same path as the previous one until it is blocked.

I added it to the `simulate` function below and commented what's happening.

## Final code

``````use std::collections::HashSet;

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Coord {
x: i32,
y: i32,
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum Tile {
Rock,
Sand,
Air,
}

impl Coord {
fn neighbours(&self) -> [Coord; 3] {
let down = Coord {
x: self.x,
y: self.y + 1,
};
let down_left = Coord {
x: self.x - 1,
y: self.y + 1,
};
let down_right = Coord {
x: self.x + 1,
y: self.y + 1,
};

[down, down_left, down_right]
}

/// returns Some(Coord) of this coords first Coord it can move to, none if it is static
fn next(&self, cave: &[Vec<Tile>], floor_y: Option<i32>) -> Option<Coord> {
if let Some(y) = floor_y {
if (self.y + 1) == y {
// hit floor
return None;
}
}
// first available position in neighbours (down, left-down, right-down)
self.neighbours()
.into_iter()
.find(|p| cave[p.y as usize][p.x as usize] == Tile::Air)
}
}

fn parse() -> Vec<Vec<Coord>> {

input
.lines()
.map(|line| {
line.split(" -> ")
.map(|coords| {
let (x, y) = coords.split_once(',').unwrap();
let x = x.parse().unwrap();
let y = y.parse().unwrap();
Coord { x, y }
})
.collect()
})
.collect()
}

fn simulate(rocks: &HashSet<Coord>, floor_y: Option<i32>) -> usize {
let start = Coord { x: 500, y: 0 };
let max_y = rocks.iter().map(|p| p.y).max().unwrap();
// the width is a guessing game, in the puzzle it's infinite
let width = 500 + max_y + 2;

// start cave filled with air
let mut cave: Vec<Vec<Tile>> = vec![vec![Tile::Air; width as usize]; (max_y + 2) as usize];
for pos in rocks {
cave[pos.y as usize][pos.x as usize] = Tile::Rock;
}

// subsequent pieces of sand flow in exactly the same path as the previous one if it's not blocked,
let mut last_path_cache = vec![start];

for i in 0.. {
let mut sand = start;
// try to reuse the path of the previous block of sand
while let Some(pos) = last_path_cache.pop() {
if cave[pos.y as usize][pos.x as usize] == Tile::Air {
sand = pos;
break;
}
}

// add current position of sand to cache
// sand coordinate is guaranteed to be unblocked at this point
last_path_cache.push(sand);

// the sand falls until it can't anymore and next returns None
while let Some(next_air_coord) = sand.next(&cave, floor_y) {
sand = next_air_coord;
// record empty positions as sand falls so they can be filled in the future
last_path_cache.push(sand);
if floor_y.is_none() && sand.y > max_y {
return i;
}
}

// insert final coord into the cave as sand tile
cave[sand.y as usize][sand.x as usize] = Tile::Sand;

if floor_y.is_some() && sand == start {
return i + 1;
}
}

unreachable!()
}

fn rocks_in_cave(rock_lines: Vec<Vec<Coord>>) -> HashSet<Coord> {
rock_lines
.iter()
.flat_map(|path| {
path.iter().tuple_windows().flat_map(|(start, end)| {
let diff_x = end.x - start.x;
let diff_y = end.y - start.y;
let direction = Coord {
x: diff_x.signum(),
y: diff_y.signum(),
};
// one of two differences is always 0 because rock lines are vertical or horizontal
let amount = diff_x.abs().max(diff_y.abs()) as usize;

// generate Coord for every tile in a window
(0..=amount).map(move |amount| {
let diff_x = amount as i32 * direction.x;
let diff_y = amount as i32 * direction.y;

Coord {
x: start.x + diff_x,
y: start.y + diff_y,
}
})
})
})
.collect()
}

pub fn part_1() -> usize {
let rock_lines = parse();
let rocks = rocks_in_cave(rock_lines);

simulate(&rocks, None)
}

pub fn part_2() -> usize {
let rock_lines = parse();
let rocks = rocks_in_cave(rock_lines);

let max_y = rocks.iter().map(|coord| coord.y).max().unwrap();
simulate(&rocks, Some(max_y + 2))
}
``````