How to split an array of arrays based on certain condition?

Question

I have an array which contains groups of some adjacent rectangles:

var paths = [
  [3,4,6,7],
  [8,10],
  [13]
];

The rectangles are defined as follows:

var rectangles = [
  {id:1,left:[],right:[2]},
  {id:2,left:[1],right:[11]},
  {id:3,left:[2],right:[4]},
  {id:4,left:[3],right:[5]},
  {id:5,left:[11],right:[6,12]},
  {id:6,left:[5],right:[7]},
  {id:7,left:[6],right:[]},
  {id:8,left:[],right:[9]},
  {id:9,left:[8],right:[10]},
  {id:10,left:[9],right:[2]},
  {id:11,left:[2],right:[5]},
  {id:12,left:[5],right:[]},
  {id:13,left:[],right:[9]}
];

From the rectangles definition, i see that rectangles 4 and 6 are not neighbors, because 4 is not right of 6 and 6 is not left of 4. The same for 8 and 10.

Now, i would like to split the paths array to have separate entries for every group of adjacent rectangles, like this:

result = [
  [3,4],
  [6,7],
  [8],
  [10],
  [13]
];

How can i split the array and create new entries when i find two consecutive id's of two non-adjacent rectangles?

Fiddle with test data: https://jsfiddle.net/4jpy84k4/

EDIT: Final solution thanks to Tobias K.: https://jsfiddle.net/j1of5p4c/4/

Tobias S · Accepted Answer · 2016-09-05 07:55:19Z

1

Without converting your reactangles this is my solution:

var paths = [
  [3,4,6,7],
  [8,10],
  [13]
];

var rectangles = [
{id:1,left:[],right:[2]},
{id:2,left:[1],right:[11]},
{id:3,left:[2],right:[4]},
{id:4,left:[3],right:[5]},
{id:5,left:[11],right:[6,12]},
{id:6,left:[5],right:[7]},
{id:7,left:[6],right:[]},
{id:8,left:[],right:[9]},
{id:9,left:[8],right:[10]},
{id:10,left:[9],right:[2]},
{id:11,left:[2],right:[5]},
{id:12,left:[5],right:[]},
{id:13,left:[],right:[9]}
];

function getRectangle(index){
  for (var i=0; i<rectangles.length; i++){
    if (rectangles[i].id == index){
	  return rectangles[i];
	}
  }
  return undefined;
}

function isNeighbour(p1, p2) {
  var r1 = getRectangle(p1);
  var r2 = getRectangle(p2);
  if (r1 == undefined || r2 == undefined){
  	return false;
  }
  return r1.left.indexOf(p2) >= 0 || r1.right.indexOf(p2) >= 0 || r2.left.indexOf(p1) >= 0 || r2.right.indexOf(p1) >= 0;
}

function groupPaths(paths) {
  var results = [];
  var neighb = [];
  for (var i=0; i<paths.length; i++){
    if (paths[i].length == 1){
	  results.push(paths[i]);
	  continue;
	}
  	for (var j=0; j<paths[i].length; j++){
	  if (j+1 == paths[i].length){
	  	neighb.push(paths[i][j]);
	  	results.push(neighb);
	  	neighb = [];
		continue;
	  }
	  while(isNeighbour(paths[i][j], paths[i][j+1])){
	  	neighb.push(paths[i][j]);
		j = j+1;
	  }
	  neighb.push(paths[i][j]);
	  results.push(neighb);
	  neighb = [];
  	}
  }
  return results;
}

var res = groupPaths(paths);
for (var i=0; i<res.length; i++){
  for(var j=0; j<res[i].length; j++){
    console.log(i + ': ' + res[i][j]);
  }
}

edited Sep 5, 2016 at 7:55

answered Sep 4, 2016 at 8:58

Tobias S

1,2758 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

deblocker Over a year ago

I just updated my sample Fiddle with your solution, you can see the exact definition of neighbors. Beside this, just one doubt: why the result is: [[3,4],[6,7],[8],[10],[[13]]]? The last entry shall be simply [13].

Tobias S Over a year ago

I cannot see, why 13 should be wrapped twice, cause therefore if ask: " if (j+1 == paths[i].length){"

deblocker Over a year ago

It's here: results.push([paths[i]]); shall be results.push(paths[i]); Please update your answer so i can accept it :-)

Tobias S Over a year ago

Edited based on your wishes :)

Redu · Accepted Answer · 2016-09-04 08:53:17Z

0

This is how you might do it. But first, for the sake of efficiency i had to convert your rectangles reference data into a much more usable form though. The rectangleIds look up object looks like this;

{ '1': { left: 0, right: 2 },
  '2': { left: 1, right: 11 },
  '3': { left: 2, right: 4 },
  '4': { left: 3, right: 5 },
  '5': { left: 11, right: 6 },
  '6': { left: 5, right: 7 },
  '7': { left: 6, right: 0 },
  '8': { left: 0, right: 9 },
  '9': { left: 8, right: 10 },
  '10': { left: 9, right: 2 },
  '11': { left: 2, right: 5 },
  '12': { left: 5, right: 0 },
  '13': { left: 0, right: 9 } }

Then it's just a matter of two nested reduces.

var   paths = [
               [3,4,6,7],
               [8,10],
               [13]
              ],

  rectangles = [
                {id:1,left:[],right:[2]},
                {id:2,left:[1],right:[11]},
                {id:3,left:[2],right:[4]},
                {id:4,left:[3],right:[5]},
                {id:5,left:[11],right:[6,12]},
                {id:6,left:[5],right:[7]},
                {id:7,left:[6],right:[]},
                {id:8,left:[],right:[9]},
                {id:9,left:[8],right:[10]},
                {id:10,left:[9],right:[2]},
                {id:11,left:[2],right:[5]},
                {id:12,left:[5],right:[]},
                {id:13,left:[],right:[9]}
               ],
rectangleIds = rectangles.reduce((o,r) => (o[r.id] = {left: r.left[0] || 0, right: r.right[0] || 0},o),{}),
orderedPaths = paths.reduce((sol,p) => sol.concat(p.reduce((res,c,i,a) => rectangleIds[c].left  === a[i-1] ||
                                                                          rectangleIds[c].right === a[i-1]  ? (res[res.length-1].push(c),res)
                                                                                                            : res.concat([[c]])
                                                                          ,[]))
                                       ,[]);
console.log(orderedPaths);

answered Sep 4, 2016 at 8:53

Redu

26.3k6 gold badges61 silver badges84 bronze badges

2 Comments

deblocker Over a year ago

I appreciate your help, really, Could you explain how you've come to item 5: with just one rectangle, item 6 on the right side? Could be this deducted from the sample data provided? THX

Redu Over a year ago

@deblocker Wow..what's that.. :) It's coming from your sample data. But since i take only the first item into account it worked. Is there any possibility for item 5 to have two neighboring rectangles on the right..?

Nina Scholz · Accepted Answer · 2016-09-04 08:57:52Z

0

You could use a Map and Array#forEach for the outer loop of paths and Array#reduce for the inner loop and for having the last node avaliable to the comparison part inside of the callback for assigning to a new array or just appending to the last result array.

var paths = [[3, 4, 6, 7], [8, 10], [13]],
    rectangles = [{ id: 1, left: [], right: [2] }, { id: 2, left: [1], right: [11] }, { id: 3, left: [2], right: [4] }, { id: 4, left: [3], right: [5] }, { id: 5, left: [11], right: [6, 12] }, { id: 6, left: [5], right: [7] }, { id: 7, left: [6], right: [] }, { id: 8, left: [], right: [9] }, { id: 9, left: [8], right: [10] }, { id: 10, left: [9], right: [2] }, { id: 11, left: [2], right: [5] }, { id: 12, left: [5], right: [] }, { id: 13, left: [], right: [9] }],
    rectanglesMap = new Map,
    result = [];

rectangles.forEach(function (a) {
    rectanglesMap.set(a.id, a);
});
paths.forEach(function (a) {
    a.reduce(function (r, b, i) {
        if (!i || r !== rectanglesMap.get(b).left[0]) {
            result.push([b]);
        } else {
            result[result.length - 1].push(b);
        }
        return b;
    }, undefined);
});
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered Sep 4, 2016 at 8:57

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

1 Comment

deblocker Over a year ago

Sorry, i can't assume left[0] is enough to get a neighbour.

Collectives™ on Stack Overflow

How to split an array of arrays based on certain condition?

3 Answers 3

4 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related