2
\$\begingroup\$

Say we have these data:

var mat = [
  {
    "id": "A-B",
    "x": "1",
    "y": "0",
    "weight": "100"
  },
  {
    "id": "A-C",
    "x": "2",
    "y": "0",
    "weight": "77"
  },
  {
    "id": "A-D",
    "x": "3",
    "y": "0",
    "weight": "95"
  },
  {
    "id": "A-E",
    "x": "4",
    "y": "0",
    "weight": "18"
  },
{
    "id": "B-C",
    "x": "1",
    "y": "2",
    "weight": "3"
  },
 {
    "id": "D-F",
    "x": "5",
    "y": "3",
    "weight": "18"
  },
{
    "id": "B-A",
    "x": "0",
    "y": "1",
    "weight": "10"
  },
  {
    "id": "C-A",
    "x": "0",
    "y": "2",
    "weight": "7"
  },
{
    "id": "C-B",
    "x": "2",
    "y": "1",
    "weight": "1"
  },
  {
    "id": "D-A",
    "x": "0",
    "y": "3",
    "weight": "5"
  },
  {
    "id": "E-A",
    "x": "0",
    "y": "4",
    "weight": "18"
  },
 {
    "id": "F-D",
    "x": "3",
    "y": "5",
    "weight": "1"
  }
]

My task is to compare each object with its counterpart — i.e. compare A-B with B-A etc. Note that for each pair, the x value of one is the y value of the other, and the y of one is the x of the other. I want to only keep elements that have the higher weight of their pair. If a pair has the same value of weight - as you see with A-E and E-A then both are discarded.

I am very unfamiliar with JavaScript. This is how I achieved this, but I have to feel like there is a better (i.e. less code, faster) way of doing it. Also apologies if my javascript terminology is wrong.

// First I stored variables as vectors
var x = mat.map(function(x) {return x.x;});
var y = mat.map(function(x) {return x.y;});
var weights = mat.map(function(x) {return x.weight;});

// create a sequence of indices the length of the original array
var seq = [];
for (var i = 0; i < x.length; ++i) seq.push(i)

The strategy is to find the indices where each value of x is matched in y and vise-versa. I use the helper function below to find which index is true for both for all:

// This is a Function to find matches
Array.prototype.diff = function(arr2) {
    var ret = [];
    this.sort();
    arr2.sort();
    for(var i = 0; i < this.length; i += 1) {
        if(arr2.indexOf( this[i] ) > -1){
            ret.push( this[i] );
        }
    }
    return ret;
};

Here, I go step by step to find the index that matches (i.e. is the opposite id):

// create a sequence
var seq = [];
for (var i = 0; i < x.length; ++i) seq.push(i)

var seqindices = [];
for(var j=0; j < seq.length; j++) {

var indicesy = [];
for(var i=0; i<x.length;i++) {
    if (y[i] === x[j]) indicesy.push(i);
}

var indicesx = [];
for(var i=0; i<x.length;i++) {
    if (x[i] === y[j]) indicesx.push(i);
}

seqindices.push(indicesx.diff(indicesy));
}

// seqindices
// 6,7,9,10,8,11,0,1,4,2,3,5

Now I compare the weights of each against its matching index and only keep weights if greater, remove if equal to or lower.

var matres = [];
for(var i=0; i<seqindices.length;i++) {
    if (weights[i] > weights[seqindices[i]]) matres.push(mat[i]);
}

This gives the following result:

[
  {
    "id": "A-B",
    "x": "1",
    "y": "0",
    "weight": "100"
  },
  {
    "id": "A-C",
    "x": "2",
    "y": "0",
    "weight": "77"
  },
  {
    "id": "A-D",
    "x": "3",
    "y": "0",
    "weight": "95"
  },
  {
    "id": "B-C",
    "x": "1",
    "y": "2",
    "weight": "3"
  },
  {
    "id": "D-F",
    "x": "5",
    "y": "3",
    "weight": "18"
  }
]

I have to believe I have gone a really long way round to get this result. Hopefully someone can advise a better way.

\$\endgroup\$
  • \$\begingroup\$ Where do the data come from? Is it guaranteed that every element has its counterpart in the array? Is the order of the elements in the input or output significant? \$\endgroup\$ – 200_success Mar 2 '16 at 4:42
  • \$\begingroup\$ The data will always have a direct counterpart as in this example. Having said that, it would be beneficial for code to generalize to one other situation when there may be id's of the kind A-A, B-B, C-C etc. but in that case A-A, B-B, etc. will only appear once (the reciprocal will not be shown). It's possible that I would want to add that condition in the future. \$\endgroup\$ – jalapic Mar 2 '16 at 4:47
2
\$\begingroup\$

Rewrite

Here's a functional approach, with notes inline as comments.

Note that the internal variables are all essentially simple "helper" functions or calculations, which allow us to write the entire algorithm that you're seeking as a single statement (the final return).

The basic idea is to first group together the pairs of "twin" elements. Once we have that, we just go through the pairs and select the one with the highest weight.

function bestOfPairs(input) {
  var pairId   = elm    => elm.id.split('-').sort().join(''),        // creates an id that's the same for both elements of a "pair"
      byWeight = (a, b) => parseInt(b.weight) - parseInt(a.weight);  // reverse sort by weight: best candidate will be first in array
      grouped  = input.reduce((m, x) =>
        (m[pairId(x)] = (m[pairId(x)] || []).concat(x)) && m         // groups together elements as pairs, based on their id
      , {});

  return Object.keys(grouped).map(id => {                            // each "id" here is the "pairs" id, that is, the id being used to create the groups
    var sorted  = grouped[id].sort(byWeight),
        invalid = sorted[1] == undefined || 
                  sorted[0].weight == sorted[1].weight;
    return invalid ? null : sorted[0];                               // returns the element with higher weight, or null if they're equal, or there's only one
  })
  .filter(x => x !== null);                                          // this removes elments with the same weight
}

Output

[ { id: 'A-B', x: '1', y: '0', weight: '100' },
  { id: 'A-C', x: '2', y: '0', weight: '77' },
  { id: 'A-D', x: '3', y: '0', weight: '95' },
  { id: 'B-C', x: '1', y: '2', weight: '3' },
  { id: 'D-F', x: '5', y: '3', weight: '18' } ]

Finally, note that I'm using ES6 syntax, which is supported by modern browsers, but if you needed support for older browsers you'd need to transpile it using Babel.

\$\endgroup\$
  • \$\begingroup\$ This is a pretty good solution. However there is a little issue if the source input includes an object without couterpart, like the {id: 'A-A', ...} which appeared in your previous output version. I was to propose an edit when you just suppressed it, so it now totally answers the initial OP. Following the OP's comment, if such objects are present they appear only once, and if an object appears only once it must be excluded from the output. So here is my suggested change to make your solution cover this case >>> \$\endgroup\$ – cFreed Mar 2 '16 at 20:13
  • \$\begingroup\$ >>> The return sorted[0].weight == ... statement, 3 lines before end, should be replaced by return (typeof sorted[1] == 'undefined' ? || sorted[0].weight == sorted[1].weight) ? null : sorted[0];. This way, any input object without counterpart is accepted without firing an error, but is not included in the output. \$\endgroup\$ – cFreed Mar 2 '16 at 20:16
  • \$\begingroup\$ thanks, i made the update to handle that case. Although with all the edge cases now, some of the simplicity is lost and it makes me want to import ramda.js and turn it into a clean 1-liner :). \$\endgroup\$ – Jonah Mar 2 '16 at 20:33
  • 1
    \$\begingroup\$ I see how you changed my suggested addin, making it more readable. That's quite right! \$\endgroup\$ – cFreed Mar 2 '16 at 20:38
  • \$\begingroup\$ @cFreed thanks for this clarification. Yes, the original data come from a 12x12 matrix and so the diagonal values A-A, B-B etc usually only have one value (we could duplicate them, but that's extra work). This (and the other solution) both work very well. \$\endgroup\$ – jalapic Mar 2 '16 at 23:51
1
\$\begingroup\$

You can just loop through the array and compare with the required condition, instead of using sort() and diff()

The below code will also look for A-A, B-B etc. situations

Javascript

Array

var mat = [
      {
        "id": "A-A",
        "x": "0",
        "y": "2",
        "weight": "100"
      },
      {
        "id": "A-A",
        "x": "2",
        "y": "0",
        "weight": "90"
      },
      {
        "id": "A-B",
        "x": "1",
        "y": "0",
        "weight": "100"
      },
      {
        "id": "A-C",
        "x": "2",
        "y": "0",
        "weight": "77"
      },
      {
        "id": "A-D",
        "x": "3",
        "y": "0",
        "weight": "95"
      },
      {
        "id": "A-E",
        "x": "4",
        "y": "0",
        "weight": "18"
      },
    {
        "id": "B-C",
        "x": "1",
        "y": "2",
        "weight": "3"
      },
     {
        "id": "D-F",
        "x": "5",
        "y": "3",
        "weight": "18"
      },
    {
        "id": "B-A",
        "x": "0",
        "y": "1",
        "weight": "10"
      },
      {
        "id": "C-A",
        "x": "0",
        "y": "2",
        "weight": "7"
      },
    {
        "id": "C-B",
        "x": "2",
        "y": "1",
        "weight": "1"
      },
      {
        "id": "D-A",
        "x": "0",
        "y": "3",
        "weight": "5"
      },
      {
        "id": "E-A",
        "x": "0",
        "y": "4",
        "weight": "18"
      },
     {
        "id": "F-D",
        "x": "3",
        "y": "5",
        "weight": "1"
      }
    ];

Code

    var result = [];

    for(var i = 0; i < mat.length; i++) {
      for(var j = 0; j < mat.length; j++) {
          var arrI = mat[i],
              arrJ = mat[j],
              arrIid = arrI.id, 
              arrJid = arrJ.id,
              reverseArrJid = arrJid.split("").reverse().join(""); //reverse the id of the variable to be compared
          if((arrIid == reverseArrJid || arrIid == arrJid)) { //check if the pair is opposite to each other OR if the pair have same value string
            var arrIweight = parseInt(arrI.weight), //convert the weight into integer for comparison
                arrJweight = parseInt(arrJ.weight); //convert the weight into integer for comparison
            if(arrIweight > arrJweight)
                result.push({id: arrIid, x: arrI.x, y: arrI.y, weight: arrI.weight});
            else if(arrIweight < arrJweight)
                result.push({id: arrJid, x: arrJ.x, y: arrJ.y, weight: arrJ.weight});
            break;
          }
      }
    }

Output

result array will be

      [
          {
            "id": "A-A",
            "x": "0",
            "y": "2",
            "weight": "100"
          },
          {
            "id": "A-B",
            "x": "1",
            "y": "0",
            "weight": "100"
          },
          {
            "id": "A-C",
            "x": "2",
            "y": "0",
            "weight": "77"
          },
          {
            "id": "B-C",
            "x": "1",
            "y": "2",
            "weight": "3"
          },
          {
            "id": "A-D",
            "x": "3",
            "y": "0",
            "weight": "95"
          },
          {
            "id": "D-F",
            "x": "5",
            "y": "3",
            "weight": "18"
          }
      ]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.