Given a data matrix, calculate html rowspan and colspan

Question

I have a sparse matrix like below consisting of data cells (1..9) and empty cells (=zero):

[
    [ 1, 2, 0, 3 ],
    [ 0, 4, 0, 0 ],
    [ 5, 6, 7, 8 ],
]

I'd like to display this as an html table, but there should be no empty cells - they should be "covered" by their neighbouring data cells' row- and colspans:

<table border=1 cellpadding=10>
    <tr>
        <td rowspan=2>1</td>
        <td colspan=2>2</td>
        <td>3</td>
    </tr>
    <tr>
        <td colspan=3>4</td>
    </tr>
    <tr>
        <td>5</td>
        <td>6</td>
        <td>7</td>
        <td>8</td>
    </tr>
</table>

(this is one possible implementation, we could also use colspan=4 on the second row and no rowspan).

Generating actual html is not a problem, but I have trouble writing an algorithm to calculate row and column spans for data cells.

EDIT: still looking for an answer for this. It seems to be trivial to work with colspans only and concatenate each data cell with empty cells on its left/right. However, I'd like cells to be as square shaped as possible, so the answer should include rowspan logic as well. Thanks!

EDIT2: all answers so far summarized here: http://jsfiddle.net/ThQt4/

Answer 1

There are a few things to consider in what you want.

If you always prefer squares over the biggest shape, you could end up with a lot of single rows an colums, because a rectangle always starts with a square. And a square or rectangle can only start if the top-left part has a value.

Consider this array:

[1, 2, 3, 4, 5],
[7, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 2, 0, 0, 5]

If you choose squares over the biggest shape you'll end up with a square and three columns

[1] [2] [3] [4] [5] instead of [1] [2] [3] [4] [5]
[  7  ] [ ] [ ] [ ]            [        7        ]
[     ] [ ] [ ] [ ]            [                 ]

Furthermore, you could end up with empty single cells:

[1, 1, 2, 0],   gives   [1] [1] [  2  ]
[3, 0, 0, 0],           [         ] [?] <---
[0, 0, 0, 5],           [    3    ] [5]
[0, 0, 0, 1]            [         ] [1]

The largest square here is size 3x3 starting with 3. If you first claim the 3x3 and then the row starting with 2, you'll end up with an empty cell [?] above 5.

One last thing, if you have zeros in the top row or left column, you could also end up in trouble:

                                             V
[1, 0, 0, 2],  will leave you with  [  1  ] [?] [2]
[0, 0, 3, 4],                       [     ] [3] [4]
[0, 5, 6, 7]                    --->[?] [5] [6] [7]

That said, maybe your array isn't that complicated and maybe you don't mind the empty cells. In either way, it was fun solving this puzzle with your specs. My solution obeys the following rules:

1) squares go first.

2) Size matters. The bigger, the better

3) Rows and colums: Size matters. The biggest go first.

4) Colspan goes over rowspan

Fiddle

var maxv = arr.length;
var maxh = arr[0].length;
var rsv = [];
var rsh = [];
pop_arr();
var shape;
try_sq();
try_rect();
try_loose();


//TRY SQUARES FIRST
function try_sq() {
    var sv, sh;
    shape = [];
    for (sv = 0; sv < maxv - 1; sv++) {
        for (sh = 0; sh < maxh - 1; sh++) {
            if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) {
                continue;
            }
            check_sq(sv, sh);
        }
    }
    if (shape.length > 0) {
        occu();
    }
}


//TRY RECTANGLES
function try_rect() {
    var sv, sh;
    var rect = false;
    do {
        shape = [];
        for (sv = 0; sv < maxv; sv++) {
            for (sh = 0; sh < maxh; sh++) {
                if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) continue;
                check_rec(sv, sh);
            }
        }
        if (shape.length > 0) {
            occu();
        } else {
            rect = false;
        }
    } while (rect === true);
}

//TRY LOOSE
function try_loose() {
    var sv, sh;
    //SET THE 1x1 with value
    for (sv = 0; sv < maxv; sv++) {
        for (sh = 0; sh < maxh; sh++) {
            if (arr[sv][sh] !== 0 && (rsv[sv][sh] == -1 || rsh[sv][sh] == -1)) {
                rsv[sv][sh] = 1;
                rsh[sv][sh] = 1;
            }
        }
    }
    //SEARCH FOR rectangles wit no value
    var rect = true;
    do {
        shape = [];
        for (sv = 0; sv < maxv; sv++) {
            for (sh = 0; sh < maxh; sh++) {
                if (arr[sv][sh] !== 0 || (rsv[sv][sh] > -1 || rsh[sv][sh] > -1)) {
                    continue;
                }
                rect = check_loose(sv, sh);
            }
        }
        if (shape.length > 0) occu();
        else {
            rect = false;
        }
    } while (rect === true);
}


//check SINGLES 
function check_loose(start_v, start_h) {
    var vd, hd, iv, ih, rect;
    var hor = ver = 1;
    var horb = 0;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    rect = true;
    vd = start_v + ver;
    hd = start_h + hor;

    //check horizontal
    for (sh = start_h + 1; sh <= mxh; sh++) {
        if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) {
            break;
        }
        hor++;
    }
    //check vertical
    for (iv = start_v + 1; iv <= mxv; iv++) {
        if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) {
            break;
        }
        ver++;
    }
    if (hor > ver || hor == ver) {
        shape.unshift({
            0: (hor),
            1: [start_v, start_h, 1, hor]
        });
        return true;
    } else if (ver > hor) {
        shape.push({
            0: (ver),
            1: [start_v, start_h, ver, 1]
        });
        return true;
    }
    return false;
}




//check SQUARE        
function check_sq(start_v, start_h) {
    if (arr[start_v + 1][start_h] !== 0) {
        return false;
    }
    if (arr[start_v][start_h + 1] !== 0) {
        return false;
    }
    var vd, hd, sv, sh, square;
    var hor = ver = 1;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    //CHECK DIAGONAL
    do {
        square = true;
        vd = start_v + ver;
        hd = start_h + hor;
        //diagonal OK
        if (arr[vd][hd] !== 0) {
            if (hor == 1) {
                if (ver == 1) {
                    return false;
                }
                square = false;
                break;
            }
        }
        //check horizontal
        for (sh = start_h; sh <= hd; sh++) {
            if (arr[vd][sh] !== 0) {
                square = false;
                break;
            }
        }
        if (square === false) break;
        //check vertical
        for (sv = start_v; sv <= vd; sv++) {
            if (arr[sv][hd] !== 0) {
                square = false;
                break;
            }
        }
        if (square === false) break;
        hor++;
        ver++;
    } while (square === true && vd < mxv && hd < mxh);
    //SQUARE OK
    if (hor > 1 && ver > 1 && hor == ver) {
        shape.push({
            0: (hor * ver),
            1: [start_v, start_h, ver, hor]
        });
    }
}


//check RECTANGLE
function check_rec(start_v, start_h) {
    var vd, hd, iv, ih, rect;
    var hor = ver = 1;
    var horb = 0;
    var mxv = maxv - 1;
    var mxh = maxh - 1;
    rect = true;
    vd = start_v + ver;
    hd = start_h + hor;

    //check horizontal
    if (start_h < maxh) {
        for (sh = start_h + 1; sh <= mxh; sh++) {
            if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) break;
            hor++;
        }
    }
    //check vertical
    if (start_v < maxv) {
        for (iv = start_v + 1; iv <= mxv; iv++) {
            if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) break;
            ver++;
        }
    }
    if (hor == 1 && ver == 1) return false;
    if (hor > ver || hor == ver) {
        shape.unshift({
            0: (hor),
            1: [start_v, start_h, 1, hor]
        });
        return true;
    } else {
        shape.push({
            0: (ver),
            1: [start_v, start_h, ver, 1]
        });
        return true;
    }
    return false;
}


//FIND LARGEST SHAPE
function occu() {
    var le = shape.length;
    for (var i = 0; i < le; i++) {
        var b = Math.max.apply(Math, shape.map(function (v) {
            return v[0];
        }));
        for (var j = 0; j < shape.length; j++) {
            if (shape[j][0] == b) break;
        }
        var c = shape.splice(j, 1);
        claim(c[0][1]);
    }
}


//CLAIM SHAPE
function claim(sh) {
    var iv, ih;
    for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
        for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
            if (rsv[iv][ih] > -1 || rsh[iv][ih] > -1) return false;
        }
    }
    for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
        for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
            rsv[iv][ih] = 0;
            rsh[iv][ih] = 0;
        }
    }
    rsv[sh[0]][sh[1]] = sh[2];
    rsh[sh[0]][sh[1]] = sh[3];
}

function pop_arr() {
    var em = [];
    em[0] = arr[0].concat();
    for (var i = 0; i < maxh; i++) {
        em[0][i] = -1;
    }
    for (i = 0; i < maxv; i++) {
        rsv[i] = em[0].concat();
        rsh[i] = em[0].concat();
    }
}

Answer 2

Interesting question. This works in most browsers. It uses the array method reduce which is perfect for these type of problems.

var matrix = [
  [ 1, 2, 0, 3 ],
  [ 0, 4, 0, 0 ],
  [ 5, 6, 7, 8 ],
];

var table = matrix.reduce(function(rows, row){
  rows.push(row.reduce(function(newRow, col){
    var lastCol = newRow[newRow.length - 1];
    if (!col && lastCol) {
      lastCol.colspan = (lastCol.colspan || 1) + 1;
    } else if (!col && !lastCol) {
      var lastRowCol = rows[rows.length-1][newRow.length];
      if (lastRowCol) lastRowCol.rowspan = (lastRowCol.rowspan || 1) + 1;
    } else {
      newRow.push({value:col});
    }
    return newRow;
  }, []));
  return rows;
}, []);


var expected =  [
  [{value : 1, rowspan: 2}, {value:2, colspan: 2}, {value:3}],
  [{value : 4, colspan: 3}],
  [{value : 5}, {value:6}, {value:7}, {value:8}]
];

table.should.eql(expected); // Passed OK