Every array occurence in 2d array

Question

I have two arrays - grid and pattern

const G = [
  [9,9,9,9,9,9]
]
const P = [
  [9,9]
]

I want to get every occurrence of P within G. So the output would be something like this:

[
    {
        line: 0,
        charAtStart: 0,
        charAtEnd: 2,
    },
    {
        line: 0,
        charAtStart: 2,
        charAtEnd: 4,
    },
    {
        line: 0,
        charAtStart: 4,
        charAtEnd: 6,
    },
    {
        line: 0,
        charAtStart: 6,
        charAtEnd: 8,
    },
    {
        line: 0,
        charAtStart: 8,
        charAtEnd: 10,
    }
]

What I've done so far:

for(let i = 0, l = G.length; i < l; i++) {
  if(G[i].toString().includes(P[0].toString())) {

    console.log(G[i].toString(), '\n',
                P[0].toString(), '\n',
                G[i].toString().indexOf(P[0].toString())
               )

    availableFirstLines.push({
      line: i,
      charAtStringStart: G[i].toString().indexOf(P[0].toString()),
      charAtStringEnd: (G[i].toString().indexOf(P[0].toString())) + P[0].toString().length - 1
    })
  }
}

So I loop through G. First of all I check if P even exists within G[0]. If so I push its indexOf first char and last char. So my output is

[
    {
        line: 0,
        charAtStart: 0,
        charAtEnd: 2,
    }
]

problem is that it does detect only first occurrence and then move on. Should I have nested loop to get every occurrence?

Edit I accidentally provided wrong output. I've changed it.

why are the last 2 objects in your output? charAtStart 6 and above would be an indexes outside of your inner array in G? — Nick Parsons
– Nick Parsons, Commented Nov 3, 2019 at 0:53
Becaue I convert it into string so , are also counted. Notice that property of availableFirstLines in code is charAtStringStart. I probably should called it same in input & output. — BT101
– BT101, Commented Nov 3, 2019 at 0:55

Nick · Accepted Answer · 2019-11-03 01:11:56Z

1

Basically you need three levels of nested loops:

Loop over the values in G
Loop over the values in P for each value in G
Loop over the G value looking for all occurrences of the P value

The third part can be done with a while loop over indexOf, setting the fromIndex value to just past the start of the previous match:

const G = [
  [9,9,9,9,9,9]
]
const P = [
  [9,9]
]
let availableFirstLines = [];

G.forEach((Gv, Gi) => {
  const Gs = Gv.toString();
  P.forEach(Pv => {
    const Ps = Pv.toString();
    let i, fi = 0;
    while ((i = Gs.indexOf(Ps, fi)) >= 0) {
      availableFirstLines.push({
        line: Gi,
        charAtStringStart: i,
        charAtStringEnd: i + Ps.length - 1
      });
      fi = i + 1;
    }
  })
});
console.log(availableFirstLines);

answered Nov 3, 2019 at 1:11

Nick

147k23 gold badges67 silver badges106 bronze badges

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

Comments

Nick Parsons · Accepted Answer · 2019-11-03 10:21:22Z

You could recursively do this by using .indexOf() and passing through a starting index for each new recurse you do. You will need to recurse for each "line" in your graph:

const G = [
  [9,9,9,9,9,9]
];

const P = [
  [9,9]
];

const findIndexOf = (line, lineArr, innerP, idx = 0) => {  
  const charAtStart = lineArr.toString().indexOf(innerP.toString(), idx);
  const charAtEnd = charAtStart + innerP.toString().length-1;
  if(charAtStart === -1)
    return [];
  
  return [{line, charAtStart, charAtEnd}, ...findIndexOf(line, lineArr, innerP, charAtEnd)];
}

const res = G.reduce((acc, line, i) => 
  [...acc, ...findIndexOf(i, line, P[i])], []);

console.log(res);

If you want the pattern to be batched for every row (not just its associated row in the G array, you can use an additional inner .reduce() method, which will loop the pattern over each row in your graph like so:

const G = [
  [9,9,9,9,9,9],
  [9,9,9,9,9,9]
];

const P = [
  [9,9]
];

const findIndexOf = (line, lineArr, innerP, idx = 0) => {  
  const charAtStart = lineArr.toString().indexOf(innerP.toString(), idx);
  const charAtEnd = charAtStart + innerP.toString().length-1;
  if(charAtStart === -1)
    return [];
  
  return [{line, charAtStart, charAtEnd}, ...findIndexOf(line, lineArr, innerP, charAtEnd)];
}

const res = G.reduce((acc, line, i) => 
  [...acc, ...P.reduce((r, p) => [...r, ...findIndexOf(i, line, p)], [])], []);

console.log(res);

glneto · Accepted Answer · 2019-11-03 01:38:56Z

0

You only need 1 loop through G, since you said P is going to be a single line array.

Using indexOf comparing the G value with the pattern will give you the index of the pattern occurrences.

Then you just need to change your indexOf call to start where the last pattern occurrence ends. The second indexOf parameter will take care of that.

This snippet should work, ignoring , characters:

var G = [[9,9,9,9,9,9]];
var P = [[9,9]];

var pattern = P[0].join('');
var availableFirstLines = [];

for (let i = 0; i < G.length; i++) {
  var currentArray = G[i];
  var stringArray = currentArray.join('');
  let indexOccurrence = 0;

  while (indexOccurrence != -1) {
    // This will set the index to the the beginning of the pattern occurrence.
    indexOccurrence = stringArray.indexOf(pattern, indexOccurrence);

    if (indexOccurrence != -1) {
        availableFirstLines.push({
          line: i,
          charAtStart: indexOccurrence,
          charAtEnd: indexOccurrence + pattern.length
        });

        // This will make sure to ignore the previous encountered occurrence.
        indexOccurrence += pattern.length;
    }
  }
}

console.log(availableFirstLines);

edited Nov 3, 2019 at 1:38

answered Nov 3, 2019 at 0:43

glneto

5273 silver badges10 bronze badges

3 Comments

BT101 Over a year ago

After fixing type error with ; inside loop declaration it provide same output as my code. Please also take a look at my edit.

BT101 Over a year ago

This is basically not want I meant. The P in my code is some kind of pattern that I want to find in G. And I always care about only first line therefore I change P[0] to string.

glneto Over a year ago

@dopeCode oh sorry, I think I got what you mean now, I updated my answer. It's not the definitive solution but maybe it will help you take the right track.

Collectives™ on Stack Overflow

Every array occurence in 2d array

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related