NickyMeulemanNime
Metadata
  • Date

  • Last update

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 13

  • Newer post

    Advent of Code 2022 Day 15

Table of contents
  1. Day 14: Regolith Reservoir
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Final code
  5. Optimization
  6. Final code

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.

  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.

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:

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

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}

Series navigation for: Advent of Code 2022

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.