Describe a 2D Bitmap Using Filled Rectangle Mapping

Question

Idea:

Consider a 2-bit bitmap of arbitrary side-lengths overlaid on a coordinate grid and imaged with random data (1's represent an element of the image, 0's represent the "blank" canvas background):

y x—0 2 4 6 8 10  14  18  
|
0   0000000000111100000000
    0000000011111110000000
2   0000111111111111000000
    0000011111111111000000
4   0000000000000000000000
    1111111000000000011111
6   1111111111100000000011
    1111111111111111000000

Next, consider how the rasterized image may be described using a series of drawn, solid rectangles. Example:

    0 2 4 6 8 101214161820

0   0000000000111100000000
    0000000011111110000000
2   0000111111111111000000
    0000011111111111000000
4   0000000000000000000000
    xxxxxxx000000000011111
6   xxxxxxx111100000000011
    xxxxxxx111111111000000

The x's describe a region of the bitmap that may be described using a solid rectangle. Finally, consider how that rectangular section of the image can be described under the X-Y coordinate system by two of its vertices in the format:

{x0,y0,x1,y1}

In this case,

{0,5,6,7}

describes the example rectangular section.

Challenge: Design a program which receives a 2D matrix containing bitmap data and outputs a concatenated list of rectangle coordinates.

Restrictions:

The output, when processed by remapping (plotting using 1's) the rectangles back onto a blank coordinate canvas (a canvas of all 0's) of the same side-length dimensions, should yield exactly the input matrix.

The output should be a concatenated list of all computed rectangles, no extraneous parsing characters or structures distinguishing one set of coordinates from another. The list will be read top-down, ordering will be inferred given that each rectangle requires only two coordinates to be described.

Example I/O:

(Do mind that this example in no way presents the ideal output, however, it is a valid output.)

Input 2D matrix:

0000000000111100000000
0000000011111110000000
0000111111111111000000
0000011111111111000000
0000000000000000000000
1111111000000000011111
1111111111100000000011
1111111111111111000000

Output concatenated list:

{10,0,13,3,8,1,9,3,5,2,7,3,4,2,4,2,14,1,14,3,15,2,15,3,0,5,6,7,7,6,10,7,11,7,15,7,17,5,21,5,20,6,21,6}

Efficiency score:

Programs will be ranked by their average-case efficiency using this resource (or one which functions identically) to generate pseudorandom, 2-bit, 20x20 matrices. Determine the average-case efficiency by calculating the arithmetic mean of the output lengths of at least 10 iterations (sum of the lengths divided by the number of iterations). The lesser the average length of the output, the greater the efficiency.

Answer 1

Python 3 + Z3, optimal, 51.19 ± 0.10 rectangles

(Random 20×20 bitmaps with \$\frac17\$ probability of 0, average of 10000 cases, 95% confidence interval.)

import sys
import z3

bitmap = [list(map(int, line)) for line in sys.stdin.read().splitlines()]
height = len(bitmap)
width = len(bitmap[0])
rects = set()
for y0 in reversed(range(height)):
    for x0 in reversed(range(width)):
        x2 = width - 1
        for y1 in range(y0, height):
            if bitmap[y1][x0] != 1:
                break
            x1 = x0
            while x1 < x2 and bitmap[y1][x1 + 1] == 1:
                x1 += 1
            rects.discard((x0 + 1, y0, x1, y1))
            rects.discard((x0, y0 + 1, x1, y1))
            rects.discard((x0, y0, x1, y1 - 1))
            rects.add((x0, y0, x1, y1))
            x2 = x1
cover = {
    (x, y): [] for y in range(height) for x in range(width) if bitmap[y][x] == 1
}
use = {}
for x0, y0, x1, y1 in rects:
    u = use[x0, y0, x1, y1] = z3.Bool(f"use{x0}_{y0}_{x1}_{y1}")
    for y in range(y0, y1 + 1):
        for x in range(x0, x1 + 1):
            cover[x, y].append(u)
solver = z3.Optimize()
solver.add([z3.Or(c) for c in cover.values()])
solver.minimize(z3.Sum([z3.If(u, 1, 0) for u in use.values()]))
assert solver.check() != z3.unsat
model = solver.model()
print(sum((list(rect) for rect, u in use.items() if z3.is_true(model[u])), []))

Answer 2

Rust

Try it online

Average case num rectangles: 57.9054 (10000 iterations of 20x20 matrices, with 1/7 probability of "0")

Solution to example input: {10,0,13,3,8,1,14,3,4,2,15,2,5,3,15,3,0,5,6,7,17,5,21,5,0,6,10,7,20,6,21,6,0,7,15,7}

The algorithm is pretty simple: for each horizontal line of 1s, use that as the top side of a rectangle, extend this rectangle down while possible, and if it covers some previously uncovered area, add it to the list. This assumes rectangles can overlap. I have not verified whether the output is always correct, but the example input looks ok. The output was verified against the input for 10000 iterations, and it looks correct.

The code includes a benchmark function to calculate the score, and a function to draw the result. The input can be changed in the main function.

extern crate rand;
use rand::{Rng, thread_rng};

#[derive(Copy, Clone, Debug)]
struct Rect {
    x0: usize,
    y0: usize,
    x1: usize,
    y1: usize
}

impl Rect {
    fn contains_xslice(&self, xa: usize, xb: usize) -> bool {
        self.x0 <= xa && xb <= self.x1
    }
    fn contains(&self, r: &Rect) -> bool {
        // r is completely inside of self
        self.x0 <= r.x0 && r.x1 <= self.x1 && self.y0 <= r.y0 && r.y1 <= self.y1
    }
}

fn display_rects(r: &[Rect]) -> String {
    let s = r.iter()
        .map(|z| format!("{},{},{},{}", z.x0, z.y0, z.x1, z.y1))
        .collect::<Vec<_>>()
        .join(",");

    // transform 1,1 into {1,1}
    format!("{{{}}}", s)
}

fn draw_rects(r: &[Rect], w: usize, h: usize) -> String {
    let mut s = format!("");
    for y in 0..h {
        for x in 0..w {
            let p = Rect { x0: x, x1: x, y0: y, y1: y };
            if r.iter().any(|a| a.contains(&p)) {
                s.push_str("1");
            } else {
                s.push_str("0");
            }
        }
        s.push_str("\n");
    }
    s
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Matrix {
    v: Vec<u8>,
    size: (usize, usize),
}

impl Matrix {
    fn new(w: usize, h: usize) -> Self {
        Self {
            v: vec![0; w*h],
            size: (w, h),
        }
    }
    fn from_str(s: &str) -> Self {
        let mut v = vec![];
        let mut w = None;
        let mut h = 0;
        for l in s.lines() {
            h += 1;
            let mut tw = 0;
            for c in l.chars() {
                tw += 1;
                let x = match c {
                    '0' => 0,
                    '1' => 1,
                    a => panic!("Invalid input! {:?} at {},{}", a, tw, h),
                };
                v.push(x);
            }
            if let Some(ww) = w {
                if tw != ww {
                    panic!("All lines must have the same width! {} != {}", tw, ww);
                }
            } else {
                w = Some(tw);
            }
        }

        let w = w.unwrap_or(0);

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn random(w: usize, h: usize) -> Self {
        let mut rng = thread_rng();
        let mut v = vec![];

        for _ in 0..w*h {
            let n = rng.gen_range(0, 6+1);
            let x = if n == 0 { 0 } else { 1 };
            v.push(x);
        }

        Matrix {
            v,
            size: (w, h),
        }
    }
    fn get(&self, x: usize, y: usize) -> u8 {
        self.v[y * self.size.0 + x]
    }
    fn hline(&self, y: usize) -> &[u8] {
        &self.v[y * self.size.0 .. (y + 1) * self.size.0]
    }
    fn hline_1_pieces(&self, y: usize) -> Vec<Rect> {
        let mut r = vec![];
        let line = self.hline(y);
        let xmax = self.size.0 - 1;
        let y0 = y;
        let y1 = y;
        let mut lineit = line.iter();
        let mut xoff = 0;
        while lineit.len() > 0 {
            // Find first non-zero pixel
            if let Some(x0) = lineit.position(|&x| x != 0) {
                let x0 = xoff + x0;
                // x0..x1 is a line of 11111
                let x1 = x0 + lineit.position(|&x| x == 0).unwrap_or(xmax - x0);
                r.push(Rect { x0, x1, y0, y1 });
                // Remember offset because the iterator is being consumed
                xoff = x1 + 2;
            }
        }

        r
    }
    fn rectangles(&self) -> Vec<Rect> {
        let mut r: Vec<Rect> = vec![];
        let ymax = self.size.1 - 1;
        // For each hline, add rectangles covering the maximum width possible
        let hpieces: Vec<Vec<Rect>> = (0..self.size.1).map(|i| self.hline_1_pieces(i)).collect();
        // Extend each rectangle down while possible
        for (y0, layer) in hpieces.iter().enumerate() {
            for rect in layer {
                let mut y = y0 + 1;
                while y <= ymax {
                    if hpieces[y].iter().any(|&r| r.contains_xslice(rect.x0, rect.x1)) {
                        y += 1;
                    } else {
                        break;
                    }
                }
                let y1 = y - 1;
                let rn = Rect { y1, ..*rect };
                if r.iter().any(|&r1| r1.contains(&rn)) {
                    // An equivalent rectangle is already in the vec
                } else {
                    // This rectangle covers some new area, push it
                    r.push(rn);
                }
            }
        }

        r
    }
}

fn benchmark(iterations: usize) -> f64 {
    let mut sum = 0;
    for _ in 0..iterations {
        let m = Matrix::random(20, 20);
        let r = m.rectangles();
        let output = draw_rects(&m.rectangles(), 20, 20);
        assert_eq!(m, Matrix::from_str(&output));
        sum += r.len();
    }
    sum as f64 / iterations as f64
}

fn main() {
    let input = "\
0000000000111100000000
0000000011111110000000
0000111111111111000000
0000011111111111000000
0000000000000000000000
1111111000000000011111
1111111111100000000011
1111111111111111000000
";
    let m = Matrix::from_str(input);
    assert_eq!(input, draw_rects(&m.rectangles(), 22, 8));
    println!("{}", display_rects(&m.rectangles()));
    println!("{}", benchmark(10000));
}