Advent of Code 2022 Day 14

Day 14: Regolith Reservoir

https://adventofcode.com/2022/day/14

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

The cave is slowly filling with sand!

Your device scans the cave. Today’s input file is the list of rock edges.

An example input looks like this:

input.txt

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.

The first path consists of two straight lines
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:

Sand goes straight down one step.
If that position is blocked, it goes down and to the left instead.
If that position is blocked, it goes down and to the right instead.
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.

day_14.rs

fn parse() -> Vec<Vec<Coord>> {
    let input = std::fs::read_to_string("src/day14.txt").unwrap();

    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:

pseudocode.rs

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:

It’s air
It’s a rock
It’s sand

enum Tile {
    Rock,
    Sand,
    Air,
}

I’ll construct the cave in two steps.

create a collection of every rock coordinate in the cave.
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()
}

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];
// add rocks to cave
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

day_14.rs

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];
    // add rocks to cave
    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) {
            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

day_14.rs

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];
    // add rocks to cave
    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

day_14.rs

1use std::collections::HashSet;
2
3use itertools::Itertools;
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
6struct Coord {
7    x: i32,
8    y: i32,
9}
10
11#[derive(Debug, Clone, Copy, PartialEq)]
12enum Tile {
13    Rock,
14    Sand,
15    Air,
16}
17
18impl Coord {
19    fn neighbours(&self) -> [Coord; 3] {
20        let down = Coord {
21            x: self.x,
22            y: self.y + 1,
23        };
24        let down_left = Coord {
25            x: self.x - 1,
26            y: self.y + 1,
27        };
28        let down_right = Coord {
29            x: self.x + 1,
30            y: self.y + 1,
31        };
32
33        [down, down_left, down_right]
34    }
35
36    /// returns Some(Coord) of this coords first Coord it can move to, none if it is static
37    fn next(&self, cave: &[Vec<Tile>], floor_y: Option<i32>) -> Option<Coord> {
38        if let Some(y) = floor_y {
39            if (self.y + 1) == y {
40                // hit floor
41                return None;
42            }
43        }
44        // first available position in neighbours (down, left-down, right-down)
45        self.neighbours()
46            .into_iter()
47            .find(|p| cave[p.y as usize][p.x as usize] == Tile::Air)
48    }
49}
50
51fn parse() -> Vec<Vec<Coord>> {
52    let input = std::fs::read_to_string("src/day14.txt").unwrap();
53
54    input
55        .lines()
56        .map(|line| {
57            line.split(" -> ")
58                .map(|coords| {
59                    let (x, y) = coords.split_once(',').unwrap();
60                    let x = x.parse().unwrap();
61                    let y = y.parse().unwrap();
62                    Coord { x, y }
63                })
64                .collect()
65        })
66        .collect()
67}
68
69fn simulate(rocks: &HashSet<Coord>, floor_y: Option<i32>) -> usize {
70    let start = Coord { x: 500, y: 0 };
71    let max_y = rocks.iter().map(|p| p.y).max().unwrap();
72    // the width is a guessing game, in the puzzle it's infinite
73    let width = 500 + max_y + 2;
74
75    // start cave filled with air
76    let mut cave: Vec<Vec<Tile>> = vec![vec![Tile::Air; width as usize]; (max_y + 2) as usize];
77    // add rocks to cave
78    for pos in rocks {
79        cave[pos.y as usize][pos.x as usize] = Tile::Rock;
80    }
81
82    // subsequent pieces of sand flow in exactly the same path as the previous one if it's not blocked,
83    let mut last_path_cache = vec![start];
84
85    for i in 0.. {
86        let mut sand = start;
87        // try to reuse the path of the previous block of sand
88        while let Some(pos) = last_path_cache.pop() {
89            if cave[pos.y as usize][pos.x as usize] == Tile::Air {
90                sand = pos;
91                break;
92            }
93        }
94
95        // add current position of sand to cache
96        // sand coordinate is guaranteed to be unblocked at this point
97        last_path_cache.push(sand);
98
99        // the sand falls until it can't anymore and next returns None
100        while let Some(next_air_coord) = sand.next(&cave, floor_y) {
101            sand = next_air_coord;
102            // record empty positions as sand falls so they can be filled in the future
103            last_path_cache.push(sand);
104            if floor_y.is_none() && sand.y > max_y {
105                return i;
106            }
107        }
108
109        // insert final coord into the cave as sand tile
110        cave[sand.y as usize][sand.x as usize] = Tile::Sand;
111
112        if floor_y.is_some() && sand == start {
113            return i + 1;
114        }
115    }
116
117    unreachable!()
118}
119
120fn rocks_in_cave(rock_lines: Vec<Vec<Coord>>) -> HashSet<Coord> {
121    rock_lines
122        .iter()
123        .flat_map(|path| {
124            path.iter().tuple_windows().flat_map(|(start, end)| {
125                let diff_x = end.x - start.x;
126                let diff_y = end.y - start.y;
127                let direction = Coord {
128                    x: diff_x.signum(),
129                    y: diff_y.signum(),
130                };
131                // one of two differences is always 0 because rock lines are vertical or horizontal
132                let amount = diff_x.abs().max(diff_y.abs()) as usize;
133
134                // generate Coord for every tile in a window
135                (0..=amount).map(move |amount| {
136                    let diff_x = amount as i32 * direction.x;
137                    let diff_y = amount as i32 * direction.y;
138
139                    Coord {
140                        x: start.x + diff_x,
141                        y: start.y + diff_y,
142                    }
143                })
144            })
145        })
146        .collect()
147}
148
149pub fn part_1() -> usize {
150    let rock_lines = parse();
151    let rocks = rocks_in_cave(rock_lines);
152
153    simulate(&rocks, None)
154}
155
156pub fn part_2() -> usize {
157    let rock_lines = parse();
158    let rocks = rocks_in_cave(rock_lines);
159
160    let max_y = rocks.iter().map(|coord| coord.y).max().unwrap();
161    simulate(&rocks, Some(max_y + 2))
162}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2022 Day 14

Day 14: Regolith Reservoir

Parsing

Part 1

Helpers

Final code

Part 2

Final code

Optimization

Final code