Advent of Code 2023 Day 22

Day 22: Sand Slabs

https://adventofcode.com/2023/day/22

The sand is falling in compacted bricks. They are stacking on top of each other!

Today’s input is a snapshot of the bricks while they were still falling.

An example input looks like this:

input.txt

1,0,1~1,2,1
0,0,2~2,0,2
0,2,3~2,2,3
0,0,4~0,2,4
2,0,5~2,2,5
0,1,6~2,1,6
1,1,8~1,1,9

Each line of the input represent a single brick. It is represented by 2 points, one for each end of the brick/stick/whetever you want to call them.

The bricks will never rotate, and are very strong (something, something, magic). Even if only one piece of a brick is supporting all other bricks, the tower will not fall.

The bricks cannot pass through eachother, so a falling brick will come to rest when it encounters a space that is either occupied by an other brick, or the ground.

The ground is located at z=0, a higher z means the brick is up in the air higher.

Parsing

The 2 points for a brick are separated by a tilde ~, and each coordinate within it is separated by a comma ,.

I used the word coordinate, so I made a Coord structure. One that can handle 3D space this time. Paired with a method that can turn a string like "1,2,3" into a Coord { x: 1, y: 2, z: 3}:

struct Coord {
    x: u16,
    y: u16,
    z: u16,
}

impl Coord {
    fn from(s: &str) -> Self {
        let (x, y, z) = s.split(",").collect_tuple().unwrap();
        Self {
            x: x.parse().unwrap(),
            y: y.parse().unwrap(),
            z: z.parse().unwrap(),
        }
    }
}

A Brick has 2 Coords, one for from, and one for to.

struct Brick {
    from: Coord,
    to: Coord,
}

impl Brick {
    fn from(s: &str) -> Self {
        let (lhs, rhs) = s.split_once("~").unwrap();
        Self {
            from: Coord::from(lhs),
            to: Coord::from(rhs),
        }
    }
}

Using that to parse the input into a list of bricks:

fn parse(input: &str) -> Vec<Brick> {
    input.lines().map(Brick::from).collect()
}

Part 1

First, let the ~~sky~~ bricks fall.

The question asks how many bricks can be safely disintegrated.

A brick can be safely disintegrated if removing it causes no other bricks to fall.

The pseudocode I want to work towards:

let mut bricks = parse(input);

(0..bricks.len())
    .filter(/* keep bricks that disintegrate safely */)
    .count()

Preparation

To let every brick fall, I sorted all bricks by z first, then made them fall one by one, starting at the lowest one.

fn prepare(bricks: &mut Vec<Brick>) {
    // sort bricks by lowest height
    bricks.sort_by_key(|brick| brick.from.z);

    // coord - block_idx
    let mut occupied = HashSet::new();

    for brick in bricks.iter_mut() {
        brick.fall(&occupied);
        for (x, y, z) in iproduct!(
            brick.from.x..=brick.to.x,
            brick.from.y..=brick.to.y,
            brick.from.z..=brick.to.z
        ) {
            let coord = Coord { x, y, z };
            occupied.insert(coord);
        }
    }
}

The occupied map keeps track of every single Coord that is occupied by bricks that have come to rest. After a Brick has fallen, all its coordinates are added to the occupied map, and the next Brick can start falling.

The fall method lets a Brick fall as far as possible while respecting the positions that are already occupied.

impl Brick {
    fn can_fall(&self, occupied: &HashSet<Coord>) -> bool {
        // ground is at z == 0
        let above_ground = self.from.z > 1;
        let blocked = (self.from.x..=self.to.x)
            .cartesian_product(self.from.y..=self.to.y)
            .any(|(x, y)| {
                let pos = Coord {
                    x,
                    y,
                    z: self.from.z - 1,
                };
                occupied.contains(&pos)
            });

        above_ground && !blocked
    }

    fn fall(&mut self, occupied: &HashSet<Coord>) {
        while self.can_fall(occupied) {
            self.from.z -= 1;
            self.to.z -= 1;
        }
    }
}

Now that the bricks have fallen, I want to build up some data structure that keeps track of which bricks are supporting/supported by other bricks.

This can be done while letting the bricks fall!

For every brick, I kept track if the index in that sorted list to identify it. When a brick has fallen, I add every Coord the brick occupies to 2 maps.

Above map - given the index of a brick, return all bricks it supports
Below map - given the index of a brick, return all bricks it is supported by.

To achieve this, some minor changes:

fn prepare(bricks: &mut Vec<Brick>) -> (HashMap<u16, HashSet<u16>>, HashMap<u16, HashSet<u16>>) {
    // sort bricks by lowest height
    bricks.sort_by_key(|brick| brick.from.z);

    // coord - block_idx
    let mut occupied = HashMap::new();
    let mut above_map: HashMap<u16, HashSet<u16>> = HashMap::new();
    let mut below_map: HashMap<u16, HashSet<u16>> = HashMap::new();

    for (idx, brick) in bricks.iter_mut().enumerate() {
        brick.fall(&occupied);

        for (x, y) in (brick.from.x..=brick.to.x).cartesian_product(brick.from.y..=brick.to.y) {
            for z in brick.from.z..=brick.to.z {
                let coord = Coord { x, y, z };
                occupied.insert(coord, idx as u16);
            }
            // check if the coord of a brick below this one (that's why we use the min z, to handle vertical blocks) is occupied
            let below = Coord {
                x,
                y,
                z: brick.from.z - 1,
            };
            if let Some(&below_idx) = occupied.get(&below) {
                above_map.entry(below_idx).or_default().insert(idx as u16);
                below_map.entry(idx as u16).or_default().insert(below_idx);
            }
        }
    }

    (above_map, below_map)
}

And to the methods on Brick:

impl Brick {
    fn can_fall(&self, occupied: &HashMap<Coord, u16>) -> bool {
        // ground is at z == 0
        let above_ground = self.from.z > 1;
        let blocked = (self.from.x..=self.to.x)
            .cartesian_product(self.from.y..=self.to.y)
            .any(|(x, y)| {
                let pos = Coord {
                    x,
                    y,
                    z: self.from.z - 1,
                };
                occupied.contains_key(&pos)
            });

        above_ground && !blocked
    }

    fn fall(&mut self, occupied: &HashMap<Coord, u16>) {
        while self.can_fall(occupied) {
            self.from.z -= 1;
            self.to.z -= 1;
        }
    }
}

Helpers

Using those 2 maps I can write a helper function to determine if a brick is safe to disintegrate.

The function takes in an id (index in the list of resting bricks) along with those 2 maps.

For every id that gets passed to the function:

If no bricks are above it, it is safe to disintegrate.
If there are bricks above it, removing it should not cause any of those bricks to fall.

fn disintegrates_safely(
    id: u16,
    above_map: &HashMap<u16, HashSet<u16>>,
    below_map: &HashMap<u16, HashSet<u16>>,
) -> bool {
    if let Some(above) = above_map.get(&id) {
        // check if the removed block was the only one supporting this upper block
        above
            .iter()
            .all(|idx| below_map.get(idx).unwrap().len() > 1)
    } else {
        // no blocks above, this block is safe to remove
        true
    }
}

Code

day_22.rs

pub fn part_1(input: &str) -> usize {
    let mut bricks = parse(input);
    let (above_map, below_map) = prepare(&mut bricks);

    (0..bricks.len())
        .filter(|&id| disintegrates_safely(id as u16, &above_map, &below_map))
        .count()
}

Part 2

It’s not fast enough! We’ll have to take risks and set off a chain reaction.

For every individual brick, calculate how many bricks would fall if you remove it.

The question asks what the sum is of all those bricks.

The pseudocode I want to work towards:

let mut bricks = parse(input);
let (above_map, below_map) = prepare(&mut bricks);

(0..bricks.len())
    .map(/* remove 1 brick and calculate how many other bricks fall */)
    .sum()

Helpers

The parsing and preparating are identical to part1.

A function that takes in the id of a Brick, removes it, and recurses with the ids of all Bricks that no longer have any Brick supporting them:

fn disintegrate(
    id: u16,
    above_map: &HashMap<u16, HashSet<u16>>,
    below_map: &HashMap<u16, HashSet<u16>>,
    disintegrated: &mut HashSet<u16>,
) {
    disintegrated.insert(id);

    if let Some(above) = above_map.get(&id) {
        for above_idx in above {
            if let Some(below) = below_map.get(above_idx) {
                if below.iter().all(|idx| disintegrated.contains(idx)) {
                    disintegrate(*above_idx, above_map, below_map, disintegrated)
                }
            }
        }
    }
}

The id of every removed Brick is remembered in a set. So the length of that set - 1 is the amount of every other brick the first brick caused to fall. (minus 1 because it includes the brick that was originally removed, and the question doesn’t ask for that)

Code

day_22.rs

pub fn part_2(input: &str) -> usize {
    let mut bricks = parse(input);
    let (above_map, below_map) = prepare(&mut bricks);

    (0..bricks.len())
        .map(|id| {
            let mut disintegrated = HashSet::new();
            disintegrate(id as u16, &above_map, &below_map, &mut disintegrated);
            disintegrated.len() - 1
        })
        .sum()
}

Final code

day_22.rs

1use std::collections::{HashMap, HashSet};
2
3use itertools::{iproduct, Itertools};
4
5#[derive(PartialEq, Eq, Hash)]
6struct Coord {
7    x: u16,
8    y: u16,
9    z: u16,
10}
11
12impl Coord {
13    fn from(s: &str) -> Self {
14        let (x, y, z) = s.split(",").collect_tuple().unwrap();
15        Self {
16            x: x.parse().unwrap(),
17            y: y.parse().unwrap(),
18            z: z.parse().unwrap(),
19        }
20    }
21}
22
23struct Brick {
24    from: Coord,
25    to: Coord,
26}
27
28impl Brick {
29    fn from(s: &str) -> Self {
30        let (lhs, rhs) = s.split_once("~").unwrap();
31        Self {
32            from: Coord::from(lhs),
33            to: Coord::from(rhs),
34        }
35    }
36
37    fn can_fall(&self, occupied: &HashMap<Coord, u16>) -> bool {
38        // ground is at z == 0
39        let above_ground = self.from.z > 1;
40        let blocked = (self.from.x..=self.to.x)
41            .cartesian_product(self.from.y..=self.to.y)
42            .any(|(x, y)| {
43                let pos = Coord {
44                    x,
45                    y,
46                    z: self.from.z - 1,
47                };
48                occupied.contains_key(&pos)
49            });
50
51        above_ground && !blocked
52    }
53
54    fn fall(&mut self, occupied: &HashMap<Coord, u16>) {
55        while self.can_fall(occupied) {
56            self.from.z -= 1;
57            self.to.z -= 1;
58        }
59    }
60}
61
62fn parse(input: &str) -> Vec<Brick> {
63    input.lines().map(Brick::from).collect()
64}
65
66fn disintegrate(
67    id: u16,
68    above_map: &HashMap<u16, HashSet<u16>>,
69    below_map: &HashMap<u16, HashSet<u16>>,
70    disintegrated: &mut HashSet<u16>,
71) {
72    disintegrated.insert(id);
73
74    if let Some(above) = above_map.get(&id) {
75        for above_idx in above {
76            if let Some(below) = below_map.get(above_idx) {
77                if below.iter().all(|idx| disintegrated.contains(idx)) {
78                    disintegrate(*above_idx, above_map, below_map, disintegrated)
79                }
80            }
81        }
82    }
83}
84
85fn disintegrates_safely(
86    id: u16,
87    above_map: &HashMap<u16, HashSet<u16>>,
88    below_map: &HashMap<u16, HashSet<u16>>,
89) -> bool {
90    if let Some(above) = above_map.get(&id) {
91        // check if the removed block was the only one supporting this upper block
92        above
93            .iter()
94            .all(|idx| below_map.get(idx).unwrap().len() > 1)
95    } else {
96        // no blocks above, this block is safe to remove
97        true
98    }
99}
100
101fn prepare(bricks: &mut Vec<Brick>) -> (HashMap<u16, HashSet<u16>>, HashMap<u16, HashSet<u16>>) {
102    // sort bricks by lowest height
103    bricks.sort_by_key(|brick| brick.from.z);
104
105    // coord - block_idx
106    let mut occupied = HashMap::new();
107    let mut above_map: HashMap<u16, HashSet<u16>> = HashMap::new();
108    let mut below_map: HashMap<u16, HashSet<u16>> = HashMap::new();
109
110    for (idx, brick) in bricks.iter_mut().enumerate() {
111        brick.fall(&occupied);
112
113        for (x, y) in (brick.from.x..=brick.to.x).cartesian_product(brick.from.y..=brick.to.y) {
114            for z in brick.from.z..=brick.to.z {
115                let coord = Coord { x, y, z };
116                occupied.insert(coord, idx as u16);
117            }
118            // check if the coord of a brick below this one (that's why we use the min z, to handle vertical blocks) is occupied
119            let below = Coord {
120                x,
121                y,
122                z: brick.from.z - 1,
123            };
124            if let Some(&below_idx) = occupied.get(&below) {
125                above_map.entry(below_idx).or_default().insert(idx as u16);
126                below_map.entry(idx as u16).or_default().insert(below_idx);
127            }
128        }
129    }
130
131    (above_map, below_map)
132}
133
134pub fn part_1(input: &str) -> usize {
135    let mut bricks = parse(input);
136    let (above_map, below_map) = prepare(&mut bricks);
137
138    (0..bricks.len())
139        .filter(|&id| disintegrates_safely(id as u16, &above_map, &below_map))
140        .count()
141}
142
143pub fn part_2(input: &str) -> usize {
144    let mut bricks = parse(input);
145    let (above_map, below_map) = prepare(&mut bricks);
146
147    (0..bricks.len())
148        .map(|id| {
149            let mut disintegrated = HashSet::new();
150            disintegrate(id as u16, &above_map, &below_map, &mut disintegrated);
151            disintegrated.len() - 1
152        })
153        .sum()
154}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 22

Day 22: Sand Slabs

Parsing

Part 1

Preparation

Helpers

Code

Part 2

Helpers

Code

Final code