Array algorithm: How to reform this nested array use javascript?

Question

I have a table like this:

The colored blocks have coordinates as an array:

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

Now I want to group the neighboring blocks (horizontal and vertical) to independent child array.

The output estimated is like:

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

How to use a function to do this?

Edit: I tried to iterate each value in the input array and compare to [1, 1], if one of the coordinate is the same, push them to an new array and delete in the input array, and use recursion to do this again. But I stuck by a problem...as I should group [2, 5] and [4, 5] but cannot group [4, 4] and [6, 4]

Nina Scholz · Accepted Answer · 2021-01-07 12:57:41Z

2

You could filter the grouped items and build a new group with the own indices.

const
    data = [[1, 1], [2, 1], [2, 4], [2, 5], [3, 2], [3, 4], [4, 4], [4, 5], [4, 6], [4, 7], [5, 3], [6, 3], [6, 4], [6, 5]],
    offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]],
    groups = data.reduce((r, [i, j]) => {
        const
            own = [];
            temp = r.filter(group => {
                const found = group.some(g => offsets.some(o => i + o[0] === g[0] && j + o[1] === g[1]));
                if (!found) return true;
                own.push(...group);
            });

        return [...temp, [...own, [i, j]]];
    }, []);
    
console.log(groups);

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

answered Jan 7, 2021 at 12:57

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

Comments

Isabella Riquetti · Accepted Answer · 2021-01-07 12:51:04Z

It seems to me that you are having just a logic problem, not a JavaScript, since you know how to nest the array, is just having a problem to find the right logic to group neighbors.

You can't just compare one part of the coordinate, since the other can me really distant. You need to compare both. If you want to find the neighbor coordinate you need to have one part of the coordinate equal and the another part exactly with 1 distance away.

var arr =
    [
        [1, 1],
        [2, 1],
        [2, 4],
        [2, 5],
        [3, 2],
        [3, 4],
        [4, 4],
        [4, 5],
        [4, 6],
        [4, 7],
        [5, 3],
        [6, 3],
        [6, 4],
        [6, 5]
    ];

var groupedArr = new Array();
for(i = 0; i < arr.length; i++)
{
    var grouped = false;
    for(j = 0; j < groupedArr.length; j++)
    {
        for(k = 0; k < groupedArr[j].length; k++)
        {
            if((arr[i][0] == groupedArr[j][k][0] && Math.abs(arr[i][1] - groupedArr[j][k][1]) == 1)
            || (arr[i][1] == groupedArr[j][k][1] && Math.abs(arr[i][0] - groupedArr[j][k][0]) == 1))
            {
                groupedArr[j].push(arr[i]);
                grouped = true;
                break;
            }
        }
        
        if(grouped)
            break;
    }

    if(!grouped)
    {
        var newGroup = new Array();
        newGroup.push(arr[i]);
        groupedArr.push(newGroup);
    }
}

console.log(groupedArr);

After viewed all your solutions I found that my logic is on the right way but make a mistake on the usage of recursion :)

Yavuz Sevgi · Accepted Answer · 2021-01-07 13:42:54Z

2

looks like clustering problem. But we can solve with this simple code for small data.

ax = [[1, 1], [2, 1], [2, 4], [2, 5], [3, 2], [3, 4], [4, 4], [4, 5], [4, 6], [4, 7], [5, 3], [6, 3], [6, 4], [6, 5]];
console.log(JSON.stringify(reForm(ax)));
function reForm(a) {
    const ret = [];
    while (a.length > 0) {
        var sub = [a.shift()];
        var i=0;
        while (i<sub.length){
            var j=0
            while(j<a.length){
                if((a[j][0]==sub[i][0] && Math.abs(a[j][1]-sub[i][1])==1) ||
                (a[j][1]==sub[i][1] && Math.abs(a[j][0]-sub[i][0])==1))
                    sub.push(...a.splice(j,1));
                    else j++
            }
            i++;
        }
        ret.push(sub);
    }
    return ret;
}

answered Jan 7, 2021 at 13:42

Yavuz Sevgi

213 bronze badges

1 Comment

kroos Over a year ago

Actually I have the same logic with this but I am not smart enough to handle the three levels of nesting loop... :(

Kimura Shinji · Accepted Answer · 2021-01-07 13:52:04Z

1

You can do this by using recursion

var array =[
  [1, 1],
  [2, 1],
  [2, 4],
  [2, 5],
  [3, 2],
  [3, 4],
  [4, 4],
  [4, 5],
  [4, 6],
  [4, 7],
  [5, 3],
  [6, 3],
  [6, 4],
  [6, 5]
]
var returnval = new Array();
 while(array.length>0)
 {
    var temp = new Array();
    var item = array[0];
    array.splice(0, 1);
    temp.push(item);
    findnext(item,temp);
    returnval.push(temp);
          
 }
 console.log(returnval); 
 function findnext(item, temp)
 {
  for(var i=0;i<array.length;i++)
    {
      if((array[i][0]==item[0] && Math.abs(array[i][1]-item[1])==1) || (array[i][1]==item[1] && Math.abs(array[i][0]-item[0])==1))
      {
        temp.push(array[i]);
        item1 = array[i];
        array.splice(i,1);
        findnext(item1, temp);
      }
    }
 }

edited Jan 7, 2021 at 13:52

answered Jan 7, 2021 at 13:10

Kimura Shinji

1,7604 gold badges24 silver badges48 bronze badges

Collectives™ on Stack Overflow

Array algorithm: How to reform this nested array use javascript?

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related