problemreductions/models/misc/

rectilinear_picture_compression.rs

//! Rectilinear Picture Compression problem implementation.
//!
//! Given an m x n binary matrix M and a nonnegative integer K, determine whether
//! there exists a collection of at most K axis-aligned all-1 rectangles that
//! covers precisely the 1-entries of M. Each rectangle (r1, c1, r2, c2) with
//! r1 <= r2, c1 <= c2 covers entries M[i][j] for r1 <= i <= r2, c1 <= j <= c2,
//! and every covered entry must be 1.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use serde::de::Deserializer;
use serde::{Deserialize, Serialize};

type Rectangle = (usize, usize, usize, usize);

inventory::submit! {
    ProblemSchemaEntry {
        name: "RectilinearPictureCompression",
        display_name: "Rectilinear Picture Compression",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Cover all 1-entries of a binary matrix with at most K axis-aligned all-1 rectangles",
        fields: &[
            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "m x n binary matrix" },
            FieldInfo { name: "bound", type_name: "i64", description: "Maximum number of rectangles allowed" },
        ],
    }
}

/// The Rectilinear Picture Compression problem.
///
/// Given an m x n binary matrix M and a nonnegative integer K, determine whether
/// there exists a collection of at most K axis-aligned all-1 rectangles that
/// covers precisely the 1-entries of M.
///
/// # Representation
///
/// The configuration space consists of the maximal all-1 rectangles in the
/// matrix. Each variable is binary: 1 if the rectangle is selected, 0 otherwise.
/// The problem is satisfiable iff the selected rectangles number at most K and
/// their union covers all 1-entries.
///
/// # Example
///
/// ```
/// use problemreductions::models::misc::RectilinearPictureCompression;
/// use problemreductions::{Problem, BruteForce};
///
/// let matrix = vec![
///     vec![true, true, false, false],
///     vec![true, true, false, false],
///     vec![false, false, true, true],
///     vec![false, false, true, true],
/// ];
/// let problem = RectilinearPictureCompression::new(matrix, 2);
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize)]
pub struct RectilinearPictureCompression {
    matrix: Vec<Vec<bool>>,
    bound: i64,
    #[serde(skip)]
    maximal_rects: Vec<Rectangle>,
}

impl<'de> Deserialize<'de> for RectilinearPictureCompression {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        #[derive(Deserialize)]
        struct Inner {
            matrix: Vec<Vec<bool>>,
            bound: i64,
        }
        let inner = Inner::deserialize(deserializer)?;
        Self::try_new(inner.matrix, inner.bound).map_err(serde::de::Error::custom)
    }
}

impl RectilinearPictureCompression {
    /// Create a new RectilinearPictureCompression instance.
    ///
    /// # Panics
    ///
    /// Panics if `matrix` is empty or has inconsistent row lengths.
    pub fn new(matrix: Vec<Vec<bool>>, bound: i64) -> Self {
        Self::try_new(matrix, bound).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        matrix: Vec<Vec<bool>>,
        bound: i64,
    ) -> Result<Self, crate::registry::ConstructionError> {
        if matrix.is_empty() {
            return Err("Matrix must not be empty".into());
        }
        let cols = matrix[0].len();
        if cols == 0 {
            return Err("Matrix must have at least one column".into());
        }
        if matrix.iter().any(|row| row.len() != cols) {
            return Err("All rows must have the same length".into());
        }
        let mut instance = Self {
            matrix,
            bound,
            maximal_rects: Vec::new(),
        };
        instance.maximal_rects = instance.compute_maximal_rectangles();
        Ok(instance)
    }

    /// Returns the number of rows in the matrix.
    pub fn num_rows(&self) -> usize {
        self.matrix.len()
    }

    /// Returns the number of columns in the matrix.
    pub fn num_cols(&self) -> usize {
        self.matrix[0].len()
    }

    /// Returns the bound K.
    pub fn bound(&self) -> i64 {
        self.bound
    }

    /// Returns a reference to the binary matrix.
    pub fn matrix(&self) -> &[Vec<bool>] {
        &self.matrix
    }

    /// Returns the precomputed maximal all-1 sub-rectangles.
    ///
    /// Each rectangle is `(r1, c1, r2, c2)` covering rows `r1..=r2` and
    /// columns `c1..=c2`.
    pub fn maximal_rectangles(&self) -> &[Rectangle] {
        &self.maximal_rects
    }

    /// Number of cached maximal all-1 rectangles.
    pub fn num_rectangles(&self) -> usize {
        self.maximal_rects.len()
    }

    /// Sum of maximal rectangle areas, counting overlapping cells separately.
    pub fn total_rectangle_area(&self) -> usize {
        self.maximal_rects
            .iter()
            .map(|&(r1, c1, r2, c2)| (r2 - r1 + 1) * (c2 - c1 + 1))
            .sum()
    }

    fn build_prefix_sum(&self) -> Vec<Vec<usize>> {
        let m = self.num_rows();
        let n = self.num_cols();
        let mut prefix_sum = vec![vec![0; n + 1]; m + 1];

        for r in 0..m {
            let mut row_sum = 0;
            for c in 0..n {
                row_sum += usize::from(self.matrix[r][c]);
                prefix_sum[r + 1][c + 1] = prefix_sum[r][c + 1] + row_sum;
            }
        }

        prefix_sum
    }

    fn range_is_all_ones(
        prefix_sum: &[Vec<usize>],
        r1: usize,
        c1: usize,
        r2: usize,
        c2: usize,
    ) -> bool {
        let area = (r2 - r1 + 1) * (c2 - c1 + 1);
        let sum = prefix_sum[r2 + 1][c2 + 1] + prefix_sum[r1][c1]
            - prefix_sum[r1][c2 + 1]
            - prefix_sum[r2 + 1][c1];
        sum == area
    }

    /// Enumerate all maximal all-1 sub-rectangles in the matrix.
    ///
    /// A rectangle is maximal if it cannot be extended one step left, right,
    /// up, or down while remaining all-1. The result is sorted lexicographically.
    fn compute_maximal_rectangles(&self) -> Vec<Rectangle> {
        let m = self.num_rows();
        let n = self.num_cols();

        // Step 1: Enumerate right-maximal candidate rectangles by fixing
        // (r1, c1, r2) and taking the widest all-1 prefix common to rows r1..=r2.
        let mut candidates = Vec::new();
        for r1 in 0..m {
            for c1 in 0..n {
                if !self.matrix[r1][c1] {
                    continue;
                }
                // Find the rightmost column from c1 that is all-1 in row r1.
                let mut c_max = n;
                for c in c1..n {
                    if !self.matrix[r1][c] {
                        c_max = c;
                        break;
                    }
                }
                // Extend downward row by row, narrowing column range.
                let mut c_end = c_max; // exclusive upper bound on columns
                for r2 in r1..m {
                    // Narrow c_end based on row r2.
                    let mut new_c_end = c1;
                    for c in c1..c_end {
                        if self.matrix[r2][c] {
                            new_c_end = c + 1;
                        } else {
                            break;
                        }
                    }
                    if new_c_end <= c1 {
                        break;
                    }
                    c_end = new_c_end;
                    candidates.push((r1, c1, r2, c_end - 1));
                }
            }
        }

        // Step 2: Remove duplicates.
        candidates.sort();
        candidates.dedup();

        // Step 3: Filter to keep only rectangles that cannot be extended in
        // any cardinal direction. A 2D prefix sum makes each extension check O(1).
        let prefix_sum = self.build_prefix_sum();
        candidates
            .into_iter()
            .filter(|&(r1, c1, r2, c2)| {
                let can_extend_left =
                    c1 > 0 && Self::range_is_all_ones(&prefix_sum, r1, c1 - 1, r2, c1 - 1);
                let can_extend_right =
                    c2 + 1 < n && Self::range_is_all_ones(&prefix_sum, r1, c2 + 1, r2, c2 + 1);
                let can_extend_up =
                    r1 > 0 && Self::range_is_all_ones(&prefix_sum, r1 - 1, c1, r1 - 1, c2);
                let can_extend_down =
                    r2 + 1 < m && Self::range_is_all_ones(&prefix_sum, r2 + 1, c1, r2 + 1, c2);

                !(can_extend_left || can_extend_right || can_extend_up || can_extend_down)
            })
            .collect()
    }
}

impl Problem for RectilinearPictureCompression {
    const NAME: &'static str = "RectilinearPictureCompression";
    type Solution = Vec<bool>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("num_cols", num_cols),
        ("num_rows", num_rows),
        ("num_rectangles", num_rectangles),
        ("total_rectangle_area", total_rectangle_area),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        Ok({
            crate::types::Or({
                let rects = &self.maximal_rects;
                if config.len() != rects.len() {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "rectangle-selection length does not match the maximal rectangles".into(),
                    ));
                }
                // Count selected rectangles.
                let selected_count = config.iter().filter(|&&selected| selected).count();
                let selected_count = i64::try_from(selected_count).map_err(|_| {
                    crate::traits::EvaluationError::IntegerOverflow(
                        "converting selected-rectangle count to i64".into(),
                    )
                })?;
                if selected_count > self.bound {
                    return Ok(crate::types::Or(false));
                }

                // Check that all 1-entries are covered.
                let m = self.num_rows();
                let n = self.num_cols();
                let mut covered = vec![vec![false; n]; m];
                for (i, &x) in config.iter().enumerate() {
                    if x {
                        let (r1, c1, r2, c2) = rects[i];
                        for row in &mut covered[r1..=r2] {
                            for cell in &mut row[c1..=c2] {
                                *cell = true;
                            }
                        }
                    }
                }

                for (row_m, row_c) in self.matrix.iter().zip(covered.iter()) {
                    for (&entry, &cov) in row_m.iter().zip(row_c.iter()) {
                        if entry && !cov {
                            return Ok(crate::types::Or(false));
                        }
                    }
                }

                true
            })
        })
    }
}

impl crate::solvers::BruteForceProblem for RectilinearPictureCompression {
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.maximal_rects.len()]
    }
}

crate::declare_variants! {
    default RectilinearPictureCompression => "2^(num_rows * num_cols)",
}

crate::register_brute_force! {
    RectilinearPictureCompression decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "rectilinear_picture_compression",
        // Config: select both maximal rectangles (the two 2x2 blocks).
        // The maximal rectangles for this matrix are exactly:
        // (0,0,1,1) and (2,2,3,3), so config [1,1] selects both.
        instance: Box::new(RectilinearPictureCompression::new(
            vec![
                vec![true, true, false, false],
                vec![true, true, false, false],
                vec![false, false, true, true],
                vec![false, false, true, true],
            ],
            2,
        )),
        optimal_config: serde_json::json!(vec![true, true]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/misc/rectilinear_picture_compression.rs"]
mod tests;