Jenga

Today's task is all about removing bricks without breaking anything (or breaking as much as possible?).

You're given a list of coordinate pairs that each describe a brick; you have to "settle" them (drop them down like tetris pieces, basically; so they're all supported by either the floor or other bricks); and then determine various things about what would happen when you remove specific ones.

First thing I did was check a couple things about the input:

all bricks are 1 tile thick; meaning, their two sets of coordinates only ever differ in up to 1 axis;
for all bricks, the first coordinate pair contains the lowest z coordinate within the brick.

These are good to know. First one is really important for the solution, the second one makes the implementation a bit less annoying.

So, since the bricks are suspended mid-air, and we know they're all thickness-1 sticks, there's a really simply way to decide which order to drop them in: Simply sort by z. Because there's no complicated shapes, this ensures that later bricks in our list can only ever land on top of earlier ones.

Because the whole task seems to resolve around support, ie. what each brick is supported by, I made sure to make gathering that information central to my settling procedure:

fn shadow(([x1, y1, _], [x2, y2, _]): Brick) -> impl Iterator<Item = (i32, i32)> {
    (x1..=x2).flat_map(move |x| (y1..=y2).map(move |y| (x, y)))
}

fn support_map(input: &str) -> Vec<Vec<usize>> {
    let mut bricks: Vec<_> = parse(input).collect();
    let mut supports = vec![vec![]; bricks.len()];
    let mut map = HashMap::new();

    bricks.sort_unstable_by_key(|b| b.0[2]);

    for (i, &brick @ ([x1, y1, z1], [x2, y2, z2])) in bricks.iter().enumerate() {
        let mut z = brick.0[2];
        while z > 0 {
            for (x, y) in shadow(brick) {
                if let Some(&v) = map.get(&[x, y, z - 1]) {
                    if !supports[i].contains(&v) {
                        supports[i].push(v);
                    }
                }
            }

            if !supports[i].is_empty() {
                break;
            }

            z -= 1;
        }

        for z in z..=(z + z2 - z1) {
            for y in y1..=y2 {
                for x in x1..=x2 {
                    map.insert([x, y, z], i);
                }
            }
        }
    }

    supports
}

shadow returns all (x, y) pairs that we need to check for collisions whilst moving down. The simple implementation is thanks to the simple brick shapes.

support_map does the actual settling: After sorting the bricks, we move straight down along the z axis until we hit something (or reach z = 0). On each step, for every (x, y) pair in the shadow, we check if moving 1 more would hit a brick. We record all other bricks hit that way. If any were recorded, or we reached z = 0, we can stop moving.

Then, we simply record all positions occupied by the brick; in a hashmap of position => number of brick occupying it.

Once we're done, we can discard everything except the list of which brick is supported by which other bricks. For the ith brick, supports[i] contains the indices of the bricks it is supported by. If supports[i] is empty, that means it is supported by the floor.

And it as it turns out, supports is all we need to complete both tasks. We don't care about the actual physical layout of anything at all.

Part one asks us to count the number of bricks for which it is true that removing that specific brick wouldn't cause anything else to lose support. This is easy to check: If we wanted to see if removing the brick with index 4 would make anything else lose support, we simply check if there's any other brick support exclusively by 4—ie. we would check that supports doesn't contain the list [4] anywhere.

let supports = support_map(input);
Ok((0..supports.len())
	.filter(|&i| !supports[i..].iter().any(|s| s == &[i]))
	.count())

Part two inverts it, kind of: Try removing each brick in turn, and count how many other bricks would lose support due to it. This one is technically slightly trickier, because there might be a chain reaction: Removing brick 4 might cause bricks 9 and 17 to lose support, but brick 25 then was supported by both 9 and 17, so it would also lose support.

But, thanks to the simple shapes (again) we can simply treat any brick that fell more as completely removed, same as the original brick we removed. With that, it becomes simple to determine the number of bricks that were (re)moved:

let supports = support_map(input);
Ok((0..supports.len())
	.map(|i| {
		let mut disintegrated = vec![i];
		for (di, s) in supports[i..].iter().enumerate() {
			if !s.is_empty() && s.iter().all(|n| disintegrated.contains(n)) {
				disintegrated.push(i + di);
			}
		}
		disintegrated.len() - 1
	})
	.sum())

I was surprised by how easy to implement today's task turned out to be; but I think honing in very quickly on the importance of the supports map is the reason for that. The trap today is trying to actually operate on the physical brick map.

I'm glad to get a bit of a rest after yesterday...