Complex table merging javascript & jquery algorithm

Question

I have a rather unique problem that I'm having trouble solving. I have a 2 x 3 table, arranged like shown below.

_1____2__
1-|____|____|
2-|____|____|
3-|____|____|

Data is populated into the cells of the table. Sometimes, the data in a column or row can be the same. For example, if (1,1) and (1,2) have the same data. In some cases (1,1), (1,2), and (1,3) can all have the same data. If the values in the cells are the same, and adjacent, they need to be merged. For example, if (1,1) and (1,2) both have a value of "100", the two cells get merged. I've done this manually by using jquery like:

(1,2).hide();
(1,1).attr("rowspan", "2");

I hide the (1,2) cell instead of delete, since the tables can be reset to the original 2x3 and then repopulated if needed. Manually, this works great, but I need a dynamic method. Below is the overall goal of what needs to be accomplished.

If two vertically adjacent cells or three vertically adjacent cells in their respective columns have a values that are equal, then those cells are merged together.
Row cells, like (1,1) and (2,1) can have duplicated data, and are never merged.
For reference, the groups of cells that are compatible to be merged are {(1,1),(1,2)}, {(1,1),(1,2),(1,3)}, {(1,2),(1,3)}, {(2,1),(2,2)}, {(2,1),(2,2),(2,3)}, {(2,2),(2,3)}
Multiple merges can happen at a time. For example: {(1,1),(1,2)} have the same data, and {(2,1),(2,2),(2,3)} have the same data. Both groups are individually merged.

My main question is, how would I go about writing an algorithm to do this, without writing out every possible situation. Can someone show me an example of something that would work? I realize this is complex, so feel free to ask questions for clarification. Thanks so much in advanced. This is a huge help!

Sounds like a job for....Karnaugh Mapping. See en.wikipedia.org/wiki/Karnaugh_map
The table is always originally 2 x 3. The merging of the cells can cause the table to become 2 x 2 or 2 x 1.
Could you separate the data calculation from the presentation? Meaning, wouldn't it be easier to handle the combination checking first, and then draw a table based on the result?
@diodeus sounds potentially promising theoretically, though I would have no idea how to implement a concept like that.

thg435 · Answer 1 · 2012-02-07 19:05:59Z

Like this? http://jsfiddle.net/4zGvg/ Works with arbitrary rows/cols.

The idea: we have values matrix and span matrix. The values of span are

0 = hide this cell

1 = normal cell

x > 1 = cell with rowspan x

Iterate by columns in direct order and by rows in reverse order. If some cell's value is equal to the value below it, increase this cell's span and delete the span of the below cell:

for (var col = 0; col < cols; col++) {
    for (var row = rows - 2; row >= 0; row--) {
        if (values[row][col] == values[row + 1][col]) {
            span[row][col] = span[row + 1][col] + 1;
            span[row + 1][col] = 0;
        }
    }
}

Once this is done, you can use span to generate the complete table or to show/hide cells and set their rowspan attributes.

Very cool. Best answer I've found. I will try to implement this solution. Thanks.

James Montagne · Answer 2 · 2012-02-07 18:31:17Z

Since it's always 2x3, you could just bruteforce it.

http://jsfiddle.net/Csxbf/

var $cells = $("td");

if ($cells.eq(0).text() == $cells.eq(2).text()) {

    if ($cells.eq(2).text() == $cells.eq(4).text()) {
        $cells.eq(2).hide();
        $cells.eq(4).hide();
        $cells.eq(0).attr("rowspan",3);
    } else {
        $cells.eq(2).hide();
        $cells.eq(0).attr("rowspan",2);
    }

} else if ($cells.eq(2).text() == $cells.eq(4).text()) {
    $cells.eq(4).hide();
    $cells.eq(2).attr("rowspan",2);
}

This could definitely be optimized, this is just quick and dirty. You definitely would want to save references to the cells and not call eq so many times. You would have to do the same for the 2nd column.

If the table could change sizes, you would want to loop over each cell in the column and for every range that matched, hide the matches and set the rowspan. Relatively easy, but not really needed here.

I actually have a version bruteforced which works fine. I was hoping to optimize it.
For a small static table bruteforce is going to be optimal as far as performance goes. Something more dynamic is just going to add overhead.
I understand. I'm happy with the bruteforce code I've written already. My reason for posting this was simply my curiosity behind additional solutions. Thanks for your response.

asked	today
viewed	59 times
active	today

Complex table merging javascript & jquery algorithm

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged javascript jquery html algorithm or ask your own question.

Complex table merging javascript & jquery algorithm

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged javascript jquery html algorithm or ask your own question.

Hello World!

Related