NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2023 Day 21

Advent of Code 2023 Day 23

1. Day 22: Sand Slabs
2. Parsing
3. Part 1
4. Part 2
5. Final code

# Advent of Code 2023 Day 22

## Day 22: Sand Slabs

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,10,0,2~2,0,20,2,3~2,2,30,0,4~0,2,42,0,5~2,2,50,1,6~2,1,61,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,}.css-13aqjzy{display:inline-block;}
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.

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

To achieve this, some minor changes:

.css-14ew794{background-color:#01121f;border-left-color:#9ccc65;border-left-style:solid;border-left-width:0.25rem;display:block;margin-right:-0.5rem;margin-left:-0.5rem;padding-right:0.5rem;padding-left:0.25rem;}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:

1. If no bricks are above it, it is safe to disintegrate.
2. 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
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}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 == 039        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 && !blocked52    }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 block92        above93            .iter()94            .all(|idx| below_map.get(idx).unwrap().len() > 1)95    } else {96        // no blocks above, this block is safe to remove97        true98    }99}100
101fn prepare(bricks: &mut Vec<Brick>) -> (HashMap<u16, HashSet<u16>>, HashMap<u16, HashSet<u16>>) {102    // sort bricks by lowest height103    bricks.sort_by_key(|brick| brick.from.z);104
105    // coord - block_idx106    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 occupied119            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() - 1152        })153        .sum()154}