Advent of Code 2025 - Day 9Movie Theater

Rust | Problem statement | Source code | Tags: GeometryCoordinate compression

Part 1

Just enumerate all pairs of points and find the largest rectangle area.

let max_area = coords
    .iter()
    .combinations(2)
    .map(|pair| {
        let (x1, y1) = pair[0];
        let (x2, y2) = pair[1];
        ((x1 - x2).abs() + 1) * ((y1 - y2).abs() + 1)
    })
    .max()
    .unwrap();
rust

Part 2

Now we want the rectangle that's inscribed in the polygon. The polygon looks like this:

Polygon

In case this gives any more intuition πŸ˜‰

I'd like to keep the same approach of enumerating pairs of points, but now with an additional check to see if the rectangle ever intersects with the polygon. The most straightforward way is to paint the polygon on a grid and check if any point in the rectangle is not painted; however, since the coordinates span about 10610^6 units, we can't map the coordinates directly to grid indices. Instead, we can use coordinate compression to map the coordinates to a smaller grid, noticing that most grid indices are unnecessary since only the corner coordinates of the polygon are relevant.

I've done this many times. First I create two lookup tables, one decompressor and one compressor. I map coordinates to the range 1..=n, because I want to reserve a rim of padding around the grid for flood-filling the outside.

let x_decompressor = coords
    .iter()
    .map(|&(x, _)| x)
    .sorted()
    .dedup()
    .enumerate()
    .map(|(i, v)| (i + 1, v))
    .collect::<BTreeMap<_, _>>();
let y_decompressor = coords
    .iter()
    .map(|&(_, y)| y)
    .sorted()
    .dedup()
    .enumerate()
    .map(|(i, v)| (i + 1, v))
    .collect::<BTreeMap<_, _>>();
let x_compressor = x_decompressor
    .iter()
    .map(|(&new, &old)| (old, new))
    .collect::<BTreeMap<_, _>>();
let y_compressor = y_decompressor
    .iter()
    .map(|(&new, &old)| (old, new))
    .collect::<BTreeMap<_, _>>();
let x_max = x_decompressor.len();
let y_max = y_decompressor.len();
let mut grid = vec![vec![0; y_max + 2]; x_max + 2];
for (&(x1, y1), &(x2, y2)) in coords
    .iter()
    .chain(std::iter::once(&coords[0]))
    .tuple_windows()
{
    let cx1 = *x_compressor.get(&x1).unwrap();
    let cy1 = *y_compressor.get(&y1).unwrap();
    let cx2 = *x_compressor.get(&x2).unwrap();
    let cy2 = *y_compressor.get(&y2).unwrap();
    if cx1 == cx2 {
        for y in cy1.min(cy2)..=cy1.max(cy2) {
            grid[cx1][y] = 1;
        }
    } else {
        for x in cx1.min(cx2)..=cx1.max(cx2) {
            grid[x][cy1] = 1;
        }
    }
}
rust

This is the new shape:

Compressed polygon

Now ideally I can start from an interior point and flood-fill the inside of the polygon. However, finding an interior point is a bit tricky, so instead I flood-fill the outside of the polygon. I've also done this many times.

let mut visited = vec![vec![false; y_max + 2]; x_max + 2];
let mut st = vec![(0, 0)];
visited[0][0] = true;
while let Some((x, y)) = st.pop() {
    grid[x][y] = 2;
    for (nx, ny) in neighbors(x, y, grid.len(), grid[0].len()) {
        if !visited[nx][ny] && grid[nx][ny] != 1 {
            visited[nx][ny] = true;
            st.push((nx, ny));
        }
    }
}
rust

Because the polygon has no "holes", any rectangle that intersects with the outside must also intersect with the polygon. So we can just check if any point on the rectangle border is marked as 2.

let (x1, y1) = pair[0];
let (x2, y2) = pair[1];
let cx1 = *x_compressor.get(&x1).unwrap();
let cy1 = *y_compressor.get(&y1).unwrap();
let cx2 = *x_compressor.get(&x2).unwrap();
let cy2 = *y_compressor.get(&y2).unwrap();
for x in cx1.min(cx2)..=cx1.max(cx2) {
    if grid[x][cy1] == 2 || grid[x][cy2] == 2 {
        return false;
    }
}
for y in cy1.min(cy2)..=cy1.max(cy2) {
    if grid[cx1][y] == 2 || grid[cx2][y] == 2 {
        return false;
    }
}
true
rust