The challenge on [day 14] leads to a large cave system behind a waterfall. A distress signal leads further inside. While going deeper into the underground sand is pouring into the cave. There is not much time to figure out where the sand is going and how to avoid this trap.
The input is two-dimensional vertical slice (another grid) of the cave above. It's made out of air and rocks. The scanner reports the shape of the rock formations consisting of coordinates.
The input may look like:
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
where every line is a path that describes a shape. The first path has two segments, the second path has three segments. Drawing the shapes on a grid looks like:
4 5 5
9 0 0
4 0 3
0 ......+...
1 ..........
2 ..........
3 ..........
4 ....#...##
5 ....#...#.
6 ..###...#.
7 ........#.
8 ........#.
9 #########.
The sand starts to fall on position 500,0 marked by +. Rocks are displayed with a #, the air is displayed with .. The scan lines from the input are rendered in the grid as rocks.
Sand itself is one unit at a time, the next sand only drops when the previous sand comes to rest or drops out of bounds.
Part 1
The goal is to simulate the falling sand & determine the number of sand that comes to rest, before the remaining sand always flows into the abyss below.
A unit of sand moves as follows.
- if possible always falls down one step
- if the tile immediately below is block (rock or sand), the unit attempts to move left-down first, then right-down.
- sand moves as long as it's able to move
- sand rest if it can't move any of the three possible destinations are block
- sand falls out of bounds if it passes below the lowest rock
In the given example layout a total of 24 units will come to rest in the grid before all further sand moves out.
As in earlier challenges we will use Grid & Pos structs to manage positions inside the grid. This time the grid does not contain a list of all cells, but rather keeps a map of all rocks & rested sand.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(u8)]
enum Cell {
Rock = 0,
Sand,
}
#[derive(Debug, PartialOrd, Ord, PartialEq, Eq, Copy, Clone)]
struct Pos {
x: i32,
y: i32,
}
impl Pos {
pub fn new(x: i32, y: i32) -> Self {
Self { x, y }
}
}
impl std::ops::Add for Pos {
type Output = Pos;
fn add(self, rhs: Self) -> Self::Output {
Self {
x: self.x + rhs.x,
y: self.y + rhs.y,
}
}
}
#[derive(Debug, Clone)]
struct Grid {
cells: BTreeMap<Pos, Cell>,
depth: i32,
min_x: i32,
max_x: i32,
}
impl Grid {
pub fn new(cells: BTreeMap<Pos, Cell>) -> Self {
let mut depth = i32::MIN;
let mut min_x = i32::MAX;
let mut max_x = i32::MIN;
for (pos, _) in cells.iter() {
min_x = i32::min(min_x, pos.x);
max_x = i32::max(max_x, pos.x);
depth = i32::max(depth, pos.y);
}
Self {
cells,
depth,
min_x,
max_x,
}
}
pub fn build(lines: Vec<Vec<Pos>>) -> Self {
let mut cells = BTreeMap::new();
for line in lines.iter() {
for line in line.windows(2) {
if let [l, r] = line {
if l.x == r.x {
let x = l.x;
let y_start = i32::min(l.y, r.y);
let y_end = i32::max(l.y, r.y);
for y in y_start..=y_end {
cells.insert(Pos::new(x, y), Cell::Rock);
}
} else {
let y = l.y;
let x_start = i32::min(l.x, r.x);
let x_end = i32::max(l.x, r.x);
for x in x_start..=x_end {
cells.insert(Pos::new(x, y), Cell::Rock);
}
}
}
}
}
Self::new(cells)
}
}
fn part1(mut grid: Grid) -> usize {
todo!()
}
fn parse(input: &str) -> Grid {
todo!()
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(grid.clone()));
}
#[cfg(test)]
mod tests {
use super::*;
const INPUT: &str = r#"
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
"#;
#[test]
fn check_part1() {
assert_eq!(24, part1(parse(INPUT)));
}
}
The interesting part of the code above is the Grid#build method that takes a list of scanned lines (Vec of Vec<Pos>) to build the Grid from. It also determines the horizontal & vertical extents of the grid. Lines with rocks are either fully vertical or horizontal.
Each segment of a scanned shape is added pair-wise using std::slice::windows.
The next is to parse the input, again the parser combinator framework nom is used.
A given line, e.g. 498,4 -> 498,6 -> 496,6, is separated by -> (including surrounding whitespaces). The other parts are split by
the , (comma), both left & right parts are converted i32. The parse function then becomes.
use nom::{
bytes::complete::tag, character::complete::i32, multi::separated_list1, sequence::tuple,
IResult,
};
fn parse_pos(input: &str) -> IResult<&str, Pos> {
let (input, (x, _, y)) = tuple((i32, tag(","), i32))(input)?;
Ok((input, Pos::new(x, y)))
}
fn parse_line(input: &str) -> Vec<Pos> {
let (_, points) = separated_list1(tag(" -> "), parse_pos)(input).unwrap();
points
}
fn parse(input: &str) -> Grid {
let lines = input
.lines()
.map(str::trim)
.filter(|&line| !line.is_empty())
.map(parse_line)
.collect::<Vec<_>>();
Grid::build(lines)
}
The parse_line function reads a single line from the input, the parse_pos parses the coordinates into a Pos.
The remaining missing logic is to run the simulation until no more sand can be added to the grid, then count the existing sand.
We will add two new methods on Grid, one is to simulate falling of a single sand unit, the other is to run the full simulation
and then count the existing sand.
impl Grid {
pub fn fill_sand(&mut self) -> usize {
while self.scan(Pos::new(500, 0)) {}
// count all the sands
self.cells
.iter()
.filter(|(_pos, &cell)| cell == Cell::Sand)
.count()
}
fn scan(&mut self, start: Pos) -> bool {
let directions = [Pos::new(0, 1), Pos::new(-1, 1), Pos::new(1, 1)];
let mut sand = start;
loop {
let next_pos = directions
.iter()
.map(|dir| sand + *dir)
.find(|&next_pos| self.cells.get(&next_pos).is_none());
match next_pos {
Some(pos) => {
if pos.y >= self.depth {
break;
}
sand = pos.clone();
}
None => {
self.cells.insert(sand, Cell::Sand);
if sand == start {
return false;
}
return true;
}
}
}
false
}
}
The heart of the logic is the Grid#scan method. It spawns a new sand at the start position, loops over the possible directions
to move the sand down, until either the sand falls below the depth threshold (& entering the abyss) or the sand comes to rest.
There is an additional check that no further sand is spawned when the sand cannot move at all.
The test should pass now, running the program returns the first solution.
Part 2
For the second part you realize the cave does not have an endless abyss below, but rather there is a floor which sits two units below the lowest depth. The floor is an infinite horizontal line. Otherwise the simulation stays the same, except that no sand now falls outside the cave. The result is the sand should fill up the existing cave to the top until no new sand can be spawned anymore.
For this a small update of the grid setup for part 2 is done:
fn part2(mut grid: Grid) -> usize {
todo!()
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(grid.clone()));
println!("Part 2: {}", part2(grid));
}
#[cfg(test)]
mod tests {
#[test]
fn check_part2() {
assert_eq!(93, part2(parse(INPUT)));
}
}
The given example input results in 93 units of sand. The missing part now is how to set up the grid for the adjusted cave. We know the sand can only fall into a pyramid shaped pile until it hits the top, therefore it should be sufficient to span a long enough segment as the floor.
impl Grid {
fn set_cell(&mut self, pos: Pos, cell: Cell) {
self.cells.insert(pos, cell);
}
}
fn part2(mut grid: Grid) -> usize {
grid.depth += 2;
grid.min_x = 500 - grid.depth - 1;
grid.max_x = 500 + grid.depth + 1;
let y = grid.depth;
for x in grid.min_x..=grid.max_x {
grid.set_cell(Pos::new(x, y), Cell::Rock);
}
grid.fill_sand()
}
First the total depth is adjusted to cover two extra units, then the horizontal extents are calculated from the starting x position,
which is still 500. The extra line of rocks acts as the floor & is added to the grid.
The Grid#set_cell method is to add a rock at a specific position in the grid.
Once we run the tests again, they should pass. Executing cargo run --release on the command line should output the second solution.
The simulation may take a while longer, on my computer it takes about 0.25 seconds.