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:

A counter of how many times a key was seen
The pieces_count at that time
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}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2022 Day 17

Day 17: Pyroclastic Flow

Parsing

Part 1

Helpers

Final code

Part 2

Final code

Final code