NickyMeulemanNime
Metadata
  • Date

  • Last update

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 16

  • Newer post

    Advent of Code 2022 Day 18

Table of contents
  1. Day 17: Pyroclastic Flow
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Final code
  5. Final code

Advent of Code 2022 Day 17

Day 17: Pyroclastic Flow

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

You enter a tall, narrow chamber. Rocks start falling.

For some reason, there’s a loud song playing in this room. Very mysterious stuff! I don’t mind, it’s a bop.

The falling rocks have these shapes, where # is rock and . is air:

####
.#.
###
.#.
..#
..#
###
#
#
#
#
##
##

The “pieces” fall in that order, wrapping when the end of that list of 5 pieces is reached.

Jets of steam push around the rocks as they fall.

Today’s puzzle input is the sequence of directions the pieces will be pushed in.

An example input looks like this:

input.txt
>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
  • < means a jet of air that blows a piece left
  • > means a jet of air that blows a piece right

As with the pieces, if the end of the list is reached, it repeats.

The chamber is exactly seven units wide.

Each piece appears so that its left edge is two units away from the left wall and its bottom edge is three units above the highest rock in the room (or the floor, if there isn’t one).

After a piece appears, it alternates between being pushed by a jet of hot gas one unit and falling down one unit. If a movement would cause the piece to move into the walls, the floor, or an other piece, that movement doesn’t happen. When a piece is prevented from falling, a new piece immediately begins falling.

Parsing

The jets are an instance of a Jet enum that’s Left or Right. The input is a list of them.

day_17.rs
enum Jet {
Left,
Right,
}
fn parse(input: &str) -> Vec<Jet> {
input
.trim()
.chars()
.map(|c| match c {
'<' => Jet::Left,
'>' => Jet::Right,
_ => panic!("invalid input, {}", c),
})
.collect()
}

I’m also counting getting those pieces into useful data structure as parsing today. Oh, and I’m also storing the width of the chamber in a constant.

I chose to represent the pieces as a series of point offsets to a point.

Point? You know what that means, Coord is back for an other appearance!

Each Coord offset represents a rock in the piece.

#[derive(Debug, PartialEq, Default)]
struct Coord {
x: usize,
// positive y goes up.
// happy mathematicians, sad game programmers
y: usize,
}
const WIDTH: usize = 7;
const PIECES: [&[Coord]; 5] = [
// horizontal line
&[
Coord { x: 0, y: 0 },
Coord { x: 1, y: 0 },
Coord { x: 2, y: 0 },
Coord { x: 3, y: 0 },
],
// plus
&[
Coord { x: 0, y: 1 },
Coord { x: 1, y: 0 },
Coord { x: 1, y: 1 },
Coord { x: 1, y: 2 },
Coord { x: 2, y: 1 },
],
// J (or backwards L)
&[
Coord { x: 0, y: 0 },
Coord { x: 1, y: 0 },
Coord { x: 2, y: 0 },
Coord { x: 2, y: 1 },
Coord { x: 2, y: 2 },
],
// vertical line
&[
Coord { x: 0, y: 0 },
Coord { x: 0, y: 1 },
Coord { x: 0, y: 2 },
Coord { x: 0, y: 3 },
],
// square
&[
Coord { x: 0, y: 0 },
Coord { x: 1, y: 0 },
Coord { x: 0, y: 1 },
Coord { x: 1, y: 1 },
],
];

Part 1

The question asks how tall the tower of rocks will be when 2022 pieces stopped falling.

The instructions in pseudocode:

pseudocode.rs
let jets = parse(input);
let mut pieces_count = 0;
let mut top = 0;
while pieces_count != 2022 {
// choose new piece to start dropping
// set current coordinate all offsets in a piece are related to as x: 2, y: top + 3
loop {
// get new jet direction
// apply jet (update current coordinate if successful)
// try to fall (update current coordinate if successful)
// if not successful: break out of loop
}
// settle the current piece, add all offsets to the map of settled pieces
// update the highest rock coordinate and store it in "top"
pieces_count += 1;
}
top

I grouped a couple of variables to keep track of the state of the chamber in a struct:

#[derive(Default)]
struct State {
jet_count: usize,
piece_count: usize,
top: usize,
map: Vec<[bool; WIDTH]>,
curr: Coord,
}

At the start of the simulation, every number starts at 0, and the map is empty.

  • jet_count is a number to keep track of how many jets in total have blown.
  • piece_count is a number to keep track of how many pieces in total have started falling.
  • top is a number to keep track of how tall the tower currently is
  • map is a list of 7 wide boolean arrays, each keeping track of where settled rocks are at that height.
  • curr is the coordinate pair where the offsets of a piece will apply to in order to figure out where the rocks of a piece are.

When a piece stops falling, it is added to the map list.

Helpers

A helper to determine given a new curr coordinate, if the state using that as curr would be valid.

impl State {
fn is_valid(&mut self, new_curr: &Coord, piece: &[Coord]) -> bool {
piece.iter().all(|offset| {
let x = new_curr.x + offset.x;
let y = new_curr.y + offset.y;
while self.map.len() <= y {
self.map.push([false; WIDTH]);
}
x < WIDTH && !self.map[y][x]
})
}
}

The only wall collision that is checked is the one with the right wall. This is because a Coord has fields that can only ever be 0 or greater

Collisions with other pieces are checked by indexing into map and seeing if a rock is there.

Because this was a finnicky problem to get right, I implemented Display so I could print out the state of the chamber.

This takes the list of booleans in map and turns them into:

  • # for true
  • . for false

It then creates empty rows to fit the current piece if necessary. For every offset in the current piece, it adds a @ to that map.

That map is then printed to the screen with | on the sides or each row. And at the bottom, a +-----+, just like the examples in the question!

That way, in the solution code I can pop in a println!("{}", state); and see the same output as in the question text.

This was an awesome tool for finding off by one errors (and there were a lot of those)

impl Display for State {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let piece = PIECES[self.piece_count % PIECES.len()];
let mut print: Vec<Vec<_>> = self
.map
.iter()
.map(|row| {
row.iter()
.map(|rock| if *rock { '#' } else { '.' })
.collect()
})
.collect();
let mut local_top = self.top;
for offset in piece {
let x = self.curr.x + offset.x;
let y = self.curr.y + offset.y;
while print.len() <= y {
print.push(vec!['.'; WIDTH]);
}
print[y][x] = '@';
local_top = local_top.max(y + 1);
}
for row in (0..local_top).rev() {
let mut row_str = String::from('|');
for col in 0..7 {
row_str.push(print[row][col]);
}
row_str.push('|');
row_str.push('\n');
write!(f, "{}", row_str)?;
}
writeln!(f, "+{}+", "-".repeat(WIDTH))
}
}

The code for part1 has the locations where that printing of the state is used commented out.

Final code

day_17.rs
pub fn part_1(input: &str) -> usize {
let target = 2022;
let jets = parse(input);
let mut state = State::default();
while state.piece_count != target {
// new piece starts falling
let piece = PIECES[state.piece_count % PIECES.len()];
state.curr.x = 2;
state.curr.y = state.top + 3;
// println!("== Piece {} begins falling ==", state.piece_count + 1);
// println!("{}", state);
loop {
// jet
let jet = &jets[state.jet_count % jets.len()];
let new_curr = match jet {
Jet::Left => Coord {
x: state.curr.x.saturating_sub(1),
y: state.curr.y,
},
Jet::Right => Coord {
x: state.curr.x + 1,
y: state.curr.y,
},
};
if state.is_valid(&new_curr, piece) {
state.curr = new_curr;
}
state.jet_count += 1;
// println!(
// "Jet of gas pushes piece {}:",
// match jet {
// Jet::Left => "left",
// Jet::Right => "right",
// }
// );
// println!("{}", state);
// fall
let new_curr = Coord {
x: state.curr.x,
y: state.curr.y.saturating_sub(1),
};
if state.curr.y == 0 || !state.is_valid(&new_curr, piece) {
break;
}
state.curr = new_curr;
// println!("Piece falls 1 unit:");
// println!("{}", state);
}
// settle
for offset in piece {
let x = state.curr.x + offset.x;
let y = state.curr.y + offset.y;
while state.map.len() <= y {
state.map.push([false; WIDTH]);
}
state.map[y][x] = true;
// y is 0 indexed.
state.top = state.top.max(y + 1);
}
// prepare for next iteration of while loop
state.piece_count += 1;
}
state.top
}

Part 2

The elephants with you are not impressed. They would like to know how tall the tower will be after 1000000000000 pieces have stopped.

That’s a lot of zeros. A trillion rocks! Must be quite a high chamber, eh?

The question asks how tall the tower of rocks will be when 1000000000000 pieces stopped falling.

Changing the 2022 to a trillion in the code above would provide a correct answer. The only question is, am I willing to wait the time it takes to complete?

The answer is no. Luckily, there is a pattern in the dropped rocks that repeats.

Part 2 is about finding that repetition and fast forwarding as close to that trillion as possible.

To help with that, a few extra fields for the State struct:

#[derive(Default)]
struct State {
jet_count: usize,
piece_count: usize,
top: usize,
map: Vec<[bool; WIDTH]>,
curr: Coord,
seen: HashMap<(usize, usize), (usize, usize, usize)>,
added_by_repeats: usize,
}

A seen key is a combination of the index into PIECES and the index into jets.

A cycle can only be detected the third time we encounter such a pair though.

This is because some of the first pieces will have hit the floor. By the time a combination of pieces_idx, jets_idx comes around again, the fallen blocks only interact with other blocks when falling. That is the first repeatable cycle.

The seen values are:

  1. A counter of how many times a key was seen
  2. The pieces_count at that time
  3. The top at that time

Using those 2 last pieces of information, the difference in top between now and the previous time we encountered a (pieces_idx, jet_idx) pair can be calculated. We fast forward as much times as we can without hitting the trillion. The increase in top that would have caused is stored in amount_added.

The remaining amount to the trillion is simulated as before.

Final code

day_17.rs
pub fn part_2(input: &str) -> usize {
let target = 1_000_000_000_000;
let jets = parse(input);
let mut state = State::default();
while state.piece_count != target {
// new piece starts falling
let piece = PIECES[state.piece_count % PIECES.len()];
state.curr.x = 2;
state.curr.y = state.top + 3;
loop {
// jet
let jet = &jets[state.jet_count % jets.len()];
let new_curr = match jet {
Jet::Left => Coord {
x: state.curr.x.saturating_sub(1),
y: state.curr.y,
},
Jet::Right => Coord {
x: state.curr.x + 1,
y: state.curr.y,
},
};
if state.is_valid(&new_curr, piece) {
state.curr = new_curr;
}
state.jet_count += 1;
// fall
let new_curr = Coord {
x: state.curr.x,
y: state.curr.y.saturating_sub(1),
};
if state.curr.y == 0 || !state.is_valid(&new_curr, piece) {
break;
}
state.curr = new_curr;
}
// settle
for offset in piece {
let x = state.curr.x + offset.x;
let y = state.curr.y + offset.y;
while state.map.len() <= y {
state.map.push([false; WIDTH]);
}
state.map[y][x] = true;
// y is 0 indexed
state.top = state.top.max(y + 1);
}
// look for cycle
if state.added_by_repeats == 0 {
let key = (
state.piece_count % PIECES.len(),
state.jet_count % jets.len(),
);
// at third occurrence of key, the values in the seen map repeat
// add as many of them as possible without hitting the goal piece_count
if let Some((2, old_piece_count, old_top)) = state.seen.get(&key) {
let delta_top = state.top - old_top;
let delta_piece_count = state.piece_count - old_piece_count;
let repeats = (target - state.piece_count) / delta_piece_count;
state.added_by_repeats += repeats * delta_top;
state.piece_count += repeats * delta_piece_count;
}
// update seen map
// key: (piece_count % PIECES.len(), jet_count % jets.len())
// value: (amount_of_times_key_was_seen, piece_count, top)
state
.seen
.entry(key)
.and_modify(|(amnt, old_piece_count, old_top)| {
*amnt += 1;
*old_piece_count = state.piece_count;
*old_top = state.top;
})
.or_insert((1, state.piece_count, state.top));
}
// prepare for next iteration of while loop
state.piece_count += 1;
}
state.top + state.added_by_repeats
}

I then made a method with that logic to reuse it between part 1 and part 2.

Final code

day_17.rs
1use std::{collections::HashMap, fmt::Display};
2
3const WIDTH: usize = 7;
4const PIECES: [&[Coord]; 5] = [
5 // horizontal line
6 &[
7 Coord { x: 0, y: 0 },
8 Coord { x: 1, y: 0 },
9 Coord { x: 2, y: 0 },
10 Coord { x: 3, y: 0 },
11 ],
12 // plus
13 &[
14 Coord { x: 0, y: 1 },
15 Coord { x: 1, y: 0 },
16 Coord { x: 1, y: 1 },
17 Coord { x: 1, y: 2 },
18 Coord { x: 2, y: 1 },
19 ],
20 // J (or backwards L)
21 &[
22 Coord { x: 0, y: 0 },
23 Coord { x: 1, y: 0 },
24 Coord { x: 2, y: 0 },
25 Coord { x: 2, y: 1 },
26 Coord { x: 2, y: 2 },
27 ],
28 // vertical line
29 &[
30 Coord { x: 0, y: 0 },
31 Coord { x: 0, y: 1 },
32 Coord { x: 0, y: 2 },
33 Coord { x: 0, y: 3 },
34 ],
35 // square
36 &[
37 Coord { x: 0, y: 0 },
38 Coord { x: 1, y: 0 },
39 Coord { x: 0, y: 1 },
40 Coord { x: 1, y: 1 },
41 ],
42];
43
44enum Jet {
45 Left,
46 Right,
47}
48
49#[derive(Debug, PartialEq, Default)]
50struct Coord {
51 x: usize,
52 // positive y goes up.
53 // happy mathematicians, sad game programmers
54 y: usize,
55}
56
57#[derive(Default)]
58struct State {
59 jet_count: usize,
60 piece_count: usize,
61 top: usize,
62 map: Vec<[bool; WIDTH]>,
63 curr: Coord,
64 added_by_repeats: usize,
65 seen: HashMap<(usize, usize), (usize, usize, usize)>,
66}
67
68impl State {
69 fn is_valid(&mut self, new_curr: &Coord, piece: &[Coord]) -> bool {
70 piece.iter().all(|offset| {
71 let x = new_curr.x + offset.x;
72 let y = new_curr.y + offset.y;
73 while self.map.len() <= y {
74 self.map.push([false; WIDTH]);
75 }
76 x < WIDTH && !self.map[y][x]
77 })
78 }
79
80 fn simulate(&mut self, target: usize, jets: Vec<Jet>) {
81 while self.piece_count != target {
82 // new piece starts falling
83 let piece = PIECES[self.piece_count % PIECES.len()];
84 self.curr.x = 2;
85 self.curr.y = self.top + 3;
86
87 // println!("== Piece {} begins falling ==", state.piece_count + 1);
88 // println!("{}", state);
89
90 loop {
91 // jet
92 let jet = &jets[self.jet_count % jets.len()];
93 let new_curr = match jet {
94 Jet::Left => Coord {
95 x: self.curr.x.saturating_sub(1),
96 y: self.curr.y,
97 },
98 Jet::Right => Coord {
99 x: self.curr.x + 1,
100 y: self.curr.y,
101 },
102 };
103 if self.is_valid(&new_curr, piece) {
104 self.curr = new_curr;
105 }
106 self.jet_count += 1;
107
108 // println!(
109 // "Jet of gas pushes piece {}:",
110 // match jet {
111 // Jet::Left => "left",
112 // Jet::Right => "right",
113 // }
114 // );
115 // println!("{}", state);
116
117 // fall
118 let new_curr = Coord {
119 x: self.curr.x,
120 y: self.curr.y.saturating_sub(1),
121 };
122 if self.curr.y == 0 || !self.is_valid(&new_curr, piece) {
123 break;
124 }
125 self.curr = new_curr;
126
127 // println!("Piece falls 1 unit:");
128 // println!("{}", state);
129 }
130
131 // settle
132 for offset in piece {
133 let x = self.curr.x + offset.x;
134 let y = self.curr.y + offset.y;
135 while self.map.len() <= y {
136 self.map.push([false; WIDTH]);
137 }
138 self.map[y][x] = true;
139 // y is 0 indexed
140 self.top = self.top.max(y + 1);
141 }
142
143 // look for cycle
144 if self.added_by_repeats == 0 {
145 let key = (self.piece_count % PIECES.len(), self.jet_count % jets.len());
146 // at third occurrence of key, the values in the seen map repeat
147 // add as many of them as possible without hitting the goal piece_count
148 if let Some((2, old_piece_count, old_top)) = self.seen.get(&key) {
149 let delta_top = self.top - old_top;
150 let delta_piece_count = self.piece_count - old_piece_count;
151 let repeats = (target - self.piece_count) / delta_piece_count;
152 self.added_by_repeats += repeats * delta_top;
153 self.piece_count += repeats * delta_piece_count;
154 }
155 // update seen map
156 // key: (piece_count % PIECES.len(), jet_count % jets.len())
157 // value: (amount_of_times_key_was_seen, piece_count, top)
158 self.seen
159 .entry(key)
160 .and_modify(|(amnt, old_piece_count, old_top)| {
161 *amnt += 1;
162 *old_piece_count = self.piece_count;
163 *old_top = self.top;
164 })
165 .or_insert((1, self.piece_count, self.top));
166 }
167
168 // prepare for next iteration of while loop
169 self.piece_count += 1;
170 }
171 }
172}
173
174impl Display for State {
175 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
176 let piece = PIECES[self.piece_count % PIECES.len()];
177 let mut print: Vec<Vec<_>> = self
178 .map
179 .iter()
180 .map(|row| {
181 row.iter()
182 .map(|rock| if *rock { '#' } else { '.' })
183 .collect()
184 })
185 .collect();
186 let mut local_top = self.top;
187 for offset in piece {
188 let x = self.curr.x + offset.x;
189 let y = self.curr.y + offset.y;
190 while print.len() <= y {
191 print.push(vec!['.'; WIDTH]);
192 }
193 print[y][x] = '@';
194 local_top = local_top.max(y + 1);
195 }
196 for row in (0..local_top).rev() {
197 let mut row_str = String::from('|');
198 for col in 0..7 {
199 row_str.push(print[row][col]);
200 }
201 row_str.push('|');
202 row_str.push('\n');
203 write!(f, "{}", row_str)?;
204 }
205 writeln!(f, "+{}+", "-".repeat(WIDTH))
206 }
207}
208
209fn parse(input: &str) -> Vec<Jet> {
210 input
211 .trim()
212 .chars()
213 .map(|c| match c {
214 '<' => Jet::Left,
215 '>' => Jet::Right,
216 _ => panic!("invalid input, {}", c),
217 })
218 .collect()
219}
220
221pub fn part_1(input: &str) -> usize {
222 let target = 2022;
223 let jets = parse(input);
224 let mut state = State::default();
225 state.simulate(target, jets);
226
227 state.top + state.added_by_repeats
228}
229
230pub fn part_2(input: &str) -> usize {
231 let target = 1_000_000_000_000;
232 let jets = parse(input);
233 let mut state = State::default();
234 state.simulate(target, jets);
235
236 state.top + state.added_by_repeats
237}

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.