Symmetric Difference (Advanced Algorithms)

Symmetric Difference (Advanced Algorithms)
0

#1
function sym(args) {
  var argsArr = [];
  var arrCount = arguments.length;
  var count = 0;
  var uniqueArr;

  //push arguments into one array for easier access
  for(var i = 0; i < arguments.length; i++){
    argsArr.push(arguments[i]);
  }

  while(count < arrCount - 1){
    //on first loop filteredArr is first argument array
    if(count === 0){
      filteredArr = argsArr[count];
    }
    // combine the arrays being compared and filter values that
    // only appear in one of the original arrays - not both
    uniqueArr = filteredArr.concat(argsArr[count+1]).filter(unique);

    //increase the count and reset filteredArr to uniqueArr
    count++;
    filteredArr = uniqueArr;
  }

  function unique(val){
    if(filteredArr.indexOf(val) === -1 || argsArr[count+1].indexOf(val) === -1){
      return val;
    }
  }

  //before returning unique array, remove repeating values
  uniqueArr = uniqueArr.filter(function(val, i){
    return uniqueArr.indexOf(val) == i;
  });

  return uniqueArr;
}

sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);

This is my current (working) solution for the Symmetric Difference advanced algorithm. It’s taken me a while to get to this point, but I can’t help think it could be done in a more efficient way. If anyone has advice and can point me in a better direction, I’d appreciate it, before I just go look at the solution.

Thanks.


#2

Notice that the challenge is about doing a symmetric difference on two arrays at a time. Whenever you’re doing a binary operation like that on an array of items, reduce should be the first thing that you think of.

That in mind, here’s an ES6 version using reduce

// jshint esversion: 6
"use strict"; // jshint ignore:line
function sym(...args) {
  
  function sym2(a1,a2) {
    const out = [];
    for (let e of a1) {
      if (a2.indexOf(e) == -1 && out.indexOf(e) == -1) {
        out.push(e);
      }
    }
    for (let e of a2) {
      if (a1.indexOf(e) == -1 && out.indexOf(e) == -1) {
        out.push(e);
      }
    }
    return out;
  }
  
  return args.reduce(sym2);
}

sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);

#3

As chuckadams said, this is the sort of thing .reduce() is made for. Because .reduce() is an function you can call on any array, the first this you are going to want to do is get all of the arguments (the number can vary for this challenge) into an array.

Usage is fairly simple: yourArray.reduce(callback) in this case yourArray would be replaced with the name of the array that has all you arguments (each of which should also be an array).
There are some other arguments you can use with .reduce(), but that is all you need for this challenge.

Here is a quick explanation of how .reduce() works (there is more, but again, we don’t need it for this challenge):
.reduce() takes the first two elements of the array (let’s call them previousValue and currentValue) and passes them to a callback* function, the callback function is a function you write that should process (in this case compute the symmetric difference) those two elements and then return a result. The returned result is then passed to the callback as ‘previous’ along with the third element in the array which is passed as ‘current’; the result of this is passed to the callback along with the fourth element… and so on until all of the elements have been passed. This is exactly what you need to do for this challenge, so it fits nicely.

With this in mind, all you need to do is put all arguments in an array and remove all duplicates within a single array (i.e. convert them to sets), write a callback function that computes and returns the symmetric difference of two sets, and then .reduce() the array with your arguments in it.

*a little more info about callbacks, because they were hard for me to wrap my head around at first. A call back is a function you write, it can either be written directly in the function in which it is called or can be written elsewhere (but within the same scope) and then passed by name to the function:

yourArray.reduce(function(arg1, arg2) { //your function here });

OR

yourArray.reduce(myCallback); ... function myCallback(arg1, arg2) { //your function here }

I personally prefer the second option because it means the callback can also be called by other functions, but that isn’t always necessary. It’s important to note the syntax in the second option, you don’t include the parenthesis or the arguments with your callback when you call reduce (or any function that you pass a callback too) but they are included wherever you actually declare your function, as in my example above.

Finally, here was the solution I came up with if you’re interested:

function removeDupes(arr) {
  return arr.filter(function(val,i,self) {
      return self.indexOf(val) === i;
    });
}

function sym() {
  var args = Array.prototype.slice.call(arguments); //this converts the arguments to an array called args
  
  function symDiff(arr1, arr2) {
    arr1 = removeDupes(arr1); //these two lines convert the passed arrays to sets by removing duplicates
    arr2 = removeDupes(arr2);
    var index = 0;
    for (var i in arr2) {
      index = arr1.indexOf(arr2[i]);
      if (index >= 0) {
          arr1.splice(index, 1);
        }
      else arr1.push(arr2[i]);
    }
    return arr1;
  }
  
  return args.reduce(symDiff);
}

sym([1, 2, 3], [5, 2, 1, 4]);

#4

Hey, guys, thanks for the replies. I came up with a sort of hybrid I’m happier with. My main difference being I used regular for loops to iterate through the given arrays since I’m not familiar with let…of…, and I’ve read you shouldn’t use for…in… on arrays (only objects).

This was definitely helpful in getting the arguments into an array vs. using a for loop:

And yes, .reduce() was definitely the way to go.

My new version:

function sym(args) {
  var args = Array.prototype.slice.call(arguments);
  function findUniqueVals(a1, a2){
    var unique = [];
    for(var j = 0; j < a1.length; j++){
      if(a2.indexOf(a1[j]) === -1 && unique.indexOf(a1[j]) === -1){
        unique.push(a1[j]);
      }
    }
    for(var i = 0; i < a2.length; i++){
      if(a1.indexOf(a2[i]) === -1 && unique.indexOf(a2[i]) === -1){
        unique.push(a2[i]);
      }
    }
    
    return unique;
  }
  return args.reduce(findUniqueVals);

}
sym([1, 2, 5], [2, 3, 5], [3, 4, 5]);

#5

Looks awesome! I like it better than my own! Thanks for mentioning that for…in is bad for arrays, learn something new everyday!


#6

Just wanted to mention the time complexity of this algorithm.
indexOf happens in linear time. So do the for loops and the reduce function. All in all this amounts to cubic time.
A better way would be to use objects to store the data as a type of hash and then search through those, which should happen in logN time for a total of N^2logN.

Though I should probably mention that I don’t really know much about js and I only just finished an algorithm course so I don’t have much exp with these sort of things so I could be wrong :sweat_smile:

This is my code if you need an example



function sym(args) {
  return Array.from(arguments)
    .reduce(function (arr1, arr2) {
    
    function getHash (arr) {
      var hash = {};
      for (var i = 0; i < arr.length; i++) {
        hash[ arr[i] ] = true;
      }
      return hash;
    }
    
    function getDif(arr1, arr2) {
      var dif = [], hash = getHash(arr1);
      for (var i = 0; i < arr2.length; i++) {
       if (!hash[ arr2[i] ]) { 
         dif.push(arr2[i]);
         hash[ arr2[i] ] = true;
       }
      }
      return dif;
    }
    
    return getDif(arr1, arr2).concat(getDif(arr2, arr1));
  });
}


#7

Arrays should use for..of and not for..in due to Javascript being a deeply confused language, with Arrays being even more confused than most things. Actually the best way to avoid the confusion is to avoid explicit loops altogether and strictly use .reduce, .forEach, or .map methods on arrays instead, depending on the value(s) you may or not need out of it in the end.

(reduce is the king of array operations – you can implement all the others using it)


#8

Hey, you know ECMAScript 2015 features well :slight_smile: I wonder whether you had any prior experience before learning at FreeCodeCamp? What is your background? :wink:
I almost finished the FCC’s front-end course, without even touching these ‘let’ and ‘…args’ stuff, i wonder how much work is still ahead of me?


#11

I’ve got a fairly long programming background in general. Only had a vague familiarity with ES6/2015 when starting FCC, but most of the ideas it introduces are similar to other languages. If JS is your first language, it’ll take a while to get entirely up to speed (months at least), but you can later take those concepts to other programming languages and you’ll learn them in a flash (relatively speaking). If that’s among your goals, I recommend picking up TypeScript, since it will teach you about modern type systems found in other languages.

Also, once the next version of Safari is out, every modern browser will support ES6/2015 natively. Til then, just use chrome for the FCC challenges, and babel on projects.

@P1xt - I don’t know that you’d want to use Set for that last solution, since the ordering of sets is not guaranteed, and the challenge will check that. Tho it is always hard to know what’s the “correct” answer for a totally contrived challenge, so if it passes, it passes :wink:


#13

I wasn’t aware that JS’s Set type (and Map too, it appears) preserved insertion order – it’s rather unusual in most languages unless you specifically ask for that behavior. Good to know.