Best way to search for repeated values in a Multidimensional array in javascript

Question

What is the best approach to solve the following problem in Javascript? I have attempted to solve it but i am running into too much trouble, it is not even worth it to post my current code, it's an ugly mess.

I have a multidimensional array 'Teams' with multiple arrays that have a TeamName (string), WinRecord (number), LossRecord (number), and a Sort_Key (number) in this format: [TeamName, W, L, sort_key]

My data looks like this:

Teams = [
   ['Team A', 25, 2, 88],
   ['Team B', 20, 7, 84],
   ['Team C', 20, 7, 76],
   ['Team D', 20, 7, 54],
   ['Team E', 20, 7, 65],
   ['Team F', 20, 6, 34],
   ['Team G', 19, 8, 67],
   ['Team H', 20, 7, 11],
   ...
   ['Team N', 3, 24, 33]
]

The previous data is in an arbitrary order for a reason.

What I want to do is to look inside the Multidimensional Array "Teams" where the W-L record is the same in the adjacent arrays. From the previous data, teams B, C, D and E have the same W-L record and they are all adjacent to each other. Team F does NOT have the same because although it matches the W but it does not match the L. Notice that team H has the same 20-7 record but since it is NOT adjacent, we do not consider it for our comparison!

Now I want to re-organise the adjacent teams B, C, D and E , in ASC order by sort_key. The arrays that do not have a matching W-L with another array must stay in the same position. Therefore the solution would look like this:

Teams = [
   ['Team A', 25, 2, 88], //stays in the same place because it has no W-L match adjacent
   ['Team D', 20, 7, 54],    //sort_key is the lowest of this "chunk" so this goes first
   ['Team E', 20, 7, 65],    //sort_key second in ASC order  
   ['Team C', 20, 7, 76],    //then this one
   ['Team B', 20, 7, 84],    //finally this is the highest sort_key of this "chunk"
   ['Team F', 20, 6, 34], //stays in the same place because it has no W-L match adjacent
   ['Team G', 19, 8, 67], //stays in the same place because it has no W-L match adjacent
   ['Team H', 20, 7, 11], //stays in the same place because its NOT ADJACENT to the last 20-7 team
   ...
   ['Team N', 3, 24, 33] //stays in the same place because it has no W-L match adjacent
]

Note:The previous example has adjacent arrays with the same W-L of 20-7 , but there might be more "chunks" with matching W-L arrays that are adjacent to each other, this may happen multiple times until we reach array at position 'n'.

What I have in mind is:

1. To take the first array and compare with the next array, if there is a W-L match to check the next one, n times until there is no further match. If there is no match we move on to the next array and perform this step again.

2. If there is an adjacent W-L we need to keep checking the next array until there is no exact match and we stop. All the adjacent matching arrays can be copied to a temporary array. We need to save "from" the original_position because if we take data from Teams[2] all the way to Teams[5] we need to re-insert the sorted values later starting at position 2. Maybe save this original_position into a variable?

3. We now sort the temporary array by sort_key ASC. We now copy the temp array into the original Teams array "from" the original_position.

4. We keep going looking for more matches like this until we reach position 'n' and we can exit and return the finalised properly sorted Teams array.

It doesn't seem so complicated but I cannot figure out how to compare multidimensional arrays with two matching values (W-L)... Please help :)

Answer 1

You are requesting a three level sort within a group. Use array.sort(comparator-function).

A .map is used to adjust the data structure for sorting by 4-levels; computed-group, win, loss, key. A second .map reverts to the original data structure.

Example:

var Teams = [
      ['Team A', 25, 2, 88],
      ['Team B', 20, 7, 84],
      ['Team C', 20, 7, 76],
      ['Team D', 20, 7, 54],
      ['Team E', 20, 7, 65],
      ['Team F', 20, 6, 34],
      ['Team G', 19, 8, 67],
      ['Team H', 20, 7, 11],
      ['Team N',  3, 24, 33]
    ];

    var group = 0;
    
    Teams =
      Teams
      .map((item,index) => {
      
        if ( (index > 0)  
             &&
             ( item[1] != Teams[index-1][1]  // wins different
               ||
               item[2] != Teams[index-1][2]  // losses different
             )
           ) group++;  // adjacency group
        
        return { item: item, group: group }  
        })
      .sort((a,b) => {
        const d0 = a.group - b.group // computed group ascending
        // const d1 = b.item[1] - a.item[1];  // wins   (accounted for in group)
        // const d2 = b.item[2] - a.item[2];  // losses (accounted for in group)
        const d3 = a.item[3] - b.item[3];  // key ascending

        // return (d0 != 0) ? d0 : (d1 != 0) ? d1 : (d2 != 0) ? d2 : d3;
        return (d0 != 0) ? d0 : d3;
        })
      .map(item => item.item)
    ;

    document.write ('<PRE>' + 
      Teams
      .reduce ( 
        (html, item) => html + JSON.stringify(item) + "\n"
        , ""
      ) + '</PRE>'
    );

Answer 2

You can write a generic groupAdjacent function. It has two parameters -

1. t - the input array
2. equal - a function to test if elements are considered adjacent

function groupAdjacent(t, equal)
{ function* run (r, q, i)
  { if (i >= t.length)
      return yield [...r, q]
    if (equal(q, t[i]))
      return yield* run([...r, q], t[i], i + 1)
    yield [...r, q]
    yield* run([], t[i], i + 1)
  }
  return t.length
    ? Array.from(run([], t[0], 1))
    : [] 
}

Next we define two functions specific to your particular teams data -

1. teamAdjacent - determines what makes a team adjacency
2. teamSort - compares two teams for sorting

const teamAdjacent = (a, b) =>
  a[1] == b[1] && a[2] == b[2] // w/l is equal

const teamSort = (a, b) =>
  a[3] - b[3]                  // sort by sortKey, ascending

Finally we tie everything together. groupAdjacent creates an array of groups, then we .sort each group, and lastly call .flat to return an un-grouped result -

const result =
  groupAdjacent(teams, teamAdjacent)
    .map(_ => _.sort(teamSort))
    .flat()

console.log(result)

['Team A', 25, 2, 88]
['Team D', 20, 7, 54]
['Team E', 20, 7, 65]
['Team C', 20, 7, 76]
['Team B', 20, 7, 84]
['Team F', 20, 6, 34]
['Team G', 19, 8, 67]
['Team H', 20, 7, 11]
['Team N', 3, 24, 33]

Expand the snippet to verify the results in your own browser -

function groupAdjacent(t, equal)
{ function* run (r, q, i)
  { if (i >= t.length)
      return yield [...r, q]
    if (equal(q, t[i]))
      return yield* run([...r, q], t[i], i + 1)
    yield [...r, q]
    yield* run([], t[i], i + 1)
  }
  return t.length
    ? Array.from(run([], t[0], 1))
    : [] 
}

const teamAdjacent = (a, b) =>
  a[1] == b[1] && a[2] == b[2] // w/l is equal

const teamSort = (a, b) =>
  a[3] - b[3]                  // sort by sortKey, ascending

const teams =
  [ ['Team A', 25, 2, 88]
  , ['Team B', 20, 7, 84]
  , ['Team C', 20, 7, 76]
  , ['Team D', 20, 7, 54]
  , ['Team E', 20, 7, 65]
  , ['Team F', 20, 6, 34]
  , ['Team G', 19, 8, 67]
  , ['Team H', 20, 7, 11]
  , ['Team N', 3, 24, 33]
  ]

const result =
  groupAdjacent(teams, teamAdjacent)
    .map(_ => _.sort(teamSort))
    .flat()

console.log(result)

---

You can write groupAdjacent without recursion too, if you wish -

function* groupAdjacent(t, equal)
{ if (t.length === 0) return
  let g = [t[0]]
  for (const _ of t.slice(1))
    if (equal(_, g[0]))
      g.push(_)
    else
      (yield g, g = [_])
  yield g
}

The only difference with this version is that you must wrap the groupAdjacent call in Array.from -

const result =
  Array.from(groupAdjacent(teams, teamAdjacent))
    .map(_ => _.sort(teamSort))
    .flat()

// => (same output)

---

related reading

• Javascript: shuffling groups of objects in an array
• How can I sort an indirect array with javascript?
• How should i sort a list inside an object in functional programming with different logic based on different condition?

---

equivalence

Scott points out the use of .map(fn).flat() is identical to .flatMap(fn)¹. I should've noticed this because I don't think I've ever used .flat and this is yet another scenario where it's not necessary -

const result =
  groupAdjacent(teams, teamAdjacent)
    .map(_ => _.sort(teamSort))
    .flat()

Is equivalent to -

const result =
  groupAdjacent(teams, teamAdjacent)
    .flatMap(_ => _.sort(teamSort))

^1. Only equivalent when flattening a depth of 1, ie .flat() and .flat(1)

Answer 3

I tend to think of these problems through the ideas of Ramda. (Disclaimer: I'm one of its primary authors.) Ramda has a function groupWith, which does the basic work of this, grouping the consecutive matching elements into subarrays, based on a function which tests whether two consecutive values should be grouped together. The one-off version of this uses two simple helper functions also inspired by Ramda, last, which fetches the last element of an array and init, which fetches everything but the last element.

Using groupWith, it's simple enough to write our main function, just calling groupWith using a function that tests if wins and losses both match and then sorting the individual groups by the sort_key and flattening the results back into a single array.

It might look like this:

// utility functions
const last = (xs = []) =>
  xs [xs.length - 1]

const init = (xs = []) =>
  xs .slice (0, -1)

const groupWith = (match) => (xs) => 
  xs.reduce (
    (xss, x, i) => i > 0 && match (x, last (last (xss)))
      ? [...init (xss), [...last (xss), x]]
      : [...xss, [x]],
    []
  )
  
  
// main function
const process = (xs) => 
  groupWith ((a, b) => a [1] == b [1] && a [2] == b [2]) (xs) 
    .flatMap (x => x .sort ((a, b) => a [3] - b [3])) 


// sample data
const teams = [['Team A', 25, 2, 88], ['Team B', 20, 7, 84], ['Team C', 20, 7, 76], ['Team D', 20, 7, 54], ['Team E', 20, 7, 65], ['Team F', 20, 6, 34], ['Team G', 19, 8, 67], ['Team H', 20, 7, 11], ['Team N', 3, 24, 33]]


// demo
console .log (process (teams))

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

This is structurally the same as the answer from Thankyou. But the code is different enough to present separately.

It might be cleaner to pull out the helper functions inlined there. That would look like:

const groupWL = (a, b) => 
  a [1] == b [1] && a [2] == b [2]

const sortByIdx3 = (a, b) => 
  a [3] - b [3]

const process = (xs) => 
  groupWith (groupWL) (xs) 
    .flatMap (x => x .sort (sortByIdx3)) 

Or alternately we could write these helpers as

const groupWL  = ([, w1, l1, ], [, w2, l2, ]) =>
  w1 == w2 && l1 == l2

const sortByIdx3 = ([, , , sk1], [, , , sk2]) => 
  sk1 - sk2 

Finally, for comparison, here is how I would do it using Ramda (but see note 1 below):

const process = pipe (
  groupWith (both (eqProps (1), eqProps (2))),
  chain (sortBy (nth (3)))
)

where pipe, groupWith, both, eqProps, chain, sortBy, and nth are all Ramda functions.

---

^{note 1} This originally used and instead of both. I'm not currently sure why that even worked, and will investigate. Thanks to user Thankyou for noting it!

Answer 4

Try this.

Logic.

1. Pop front until W/L is being different for pivot element
2. Sorting sub array and merge it into result array
3. Do the 1 and 2 until original array be empty

you can add copy login to prevent mutate original array, which is recommended

let teams = [
   ['Team A', 25, 2, 88], //stays in the same place because it has no W-L match adjacent
   ['Team D', 20, 7, 54],    //sort_key is the lowest of this "chunk" so this goes first
   ['Team E', 20, 7, 65],    //sort_key second in ASC order  
   ['Team C', 20, 7, 76],    //then this one
   ['Team B', 20, 7, 84],    //finally this is the highest sort_key of this "chunk"
   ['Team F', 20, 6, 34], //stays in the same place because it has no W-L match adjacent
   ['Team G', 19, 8, 67], //stays in the same place because it has no W-L match adjacent
   ['Team H', 20, 7, 11]
]

const groupByWL = (teams) =>{
   const pivot = teams[0]
   const ret = [ pivot ]

   for(i in teams){
      if(i == 0) continue

      const [ name, W, L ] = teams[i]
      
      if(W != pivot[1] || L != pivot[2] ) break

      ret.push(teams[i])
   }
   
   ret.sort(function(a, b) {//put your sort logic in here
      return a[3] - b[3]
   })
    
   return ret
}

const search = teams =>{
    let ret = []
    
    while(teams.length){
       const chunk = groupByWL(teams)
       teams = teams.slice(chunk.length, teams.length)
       ret = [ ...ret, ...chunk ]
       console.log(teams)
       console.log(ret)
    }
    
    return ret
}

const result = search(teams)
console.log(teams)