0

My input is a 2D jagged array, it contains some rows of variable lengths. I'd like to convert it into a list of 2D rectangular non overlapping arrays (whose rows have the same length, with no whole) and I need to know the locations of those rectangular arrays in the jagged array.

You can see the expected result here, each rectangular array has a distinct color.

This is an example of input :

[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ][ ]
[ ][X][X][X][X][X][X][X]
[ ][ ][X][X][X][X][ ][ ]
[ ][X][X][X][X][ ][ ][ ]
[ ][X][X][X][X][ ][ ][ ]
[ ][ ][X][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

I get that in output:

[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][A][ ][ ][ ][ ]
[ ][B][G][G][G][F][E][E]
[ ][ ][G][G][G][F][ ][ ]
[ ][D][G][G][G][ ][ ][ ]
[ ][D][G][G][G][ ][ ][ ]
[ ][ ][C][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

The test cases are here. The instructions to build the project are here.

There are several similar questions on StackOverflow here (mainly focused on whether it's NP-hard or not), here (only looking for the largest rectangle), here (looking for some rectangles) and here (different performance needs, efficiency is more important for me).

I spent several months in writing and implementing my own algorithm in Java as you can see here but it's terribly inefficient, it would spend several days with about 600 256*256 arrays supplied in input. I haven't evaluated this source code yet.

Is there a faster algorithm to convert a jagged array into a list of rectangular arrays and their locations in this jagged array?

Community
  • 1
  • 1
gouessej
  • 3,640
  • 3
  • 33
  • 67
  • 1
    Please don't expect people to follow links to get the question. The question should stand on it's own. – weston Mar 07 '16 at 14:40
  • 1
    I did follow the link to the code https://sourceforge.net/p/tuer/code/HEAD/tree/pre_beta/src/main/java/jfpsm/ArrayHelper.java#l766. That is a monster of a method! – weston Mar 07 '16 at 14:43
  • so you are saying you implemented the dr dobbs method and still want a faster one. – gpasch Mar 07 '16 at 14:58
  • 1
    I'm not sure if this question is answerable in its current state. You haven't provided example input and output - or if you have it's behind one of those links, and they themselves are hard to read. If you do provide example input and output it sounds like your question would be "please review the code I've written and comment on whether the algorithm is a good choice". If that is your question, it would be better fitted for http://codereview.stackexchange.com/ ... But even then it needs cleaning up to meet that sites standards. – perfectionist Mar 07 '16 at 16:17
  • @gpasch No I wrote my own algorithm and I implemented it. Dr Dobb's method seems to be efficient to get the largest rectangle but I'm not sure that it can be efficient to get all rectangles. – gouessej Mar 07 '16 at 18:55
  • @weston I'm currently providing an example of input and output. – gouessej Mar 07 '16 at 19:04
  • Are the rectangles allowed to overlap ? This can make a big difference. –  Mar 08 '16 at 09:24
  • @YvesDaoust No they aren't. Good point, I have to mention it. – gouessej Mar 08 '16 at 21:22

0 Answers0