Let’s tackle another Free Code Camp advanced algorithm – ‘Symmetric Difference’. The challenge here is to ‘create a function that takes two or more arrays and returns an array of the symmetric difference (△ or ⊕) of the provided arrays.’
The symmetric difference of two sets of elements is the set that occurs in either one of the two sets, but not both (i.e. the symmetric difference of [1,2,3,4] and [3,4,5,6] is [1,2,5,6]). For more reading on symmetric difference, check out this wiki page.
Free Code camp gives us the following as a starting point:
|
1 2 3 4 5 |
function sym(args) { return args; } sym([1, 2, 3], [5, 2, 1, 4]); |
This is another case where we have to write a function for which we need to handle an unknown number of arguments. To accomplish this, we’ll be using the arguments object. I’ve covered the arguments object in a previous post, ‘Seek and Destroy’. If you are unfamiliar with or would like a refresher of the arguments object, please check it out.
One of the helpful hints FCC provides us with is a link to the Array.prototype.reduce() method. The arr.reduce method is a great way to cycle through and apply a function to each element of an array.
The arr.reduce method takes 2 arguments, a callback function (which will be applied to each element of the array) and an initial value (the element to provide as the first argument to the first callback function call – see here for more).
If you’re new to JavaScript, or somewhat unclear of what a callback function is, JavaScriptIsSexy.com has an excellent post on callbacks.
The callback takes a possibility of 4 arguments – previousValue, currentValue, currentIndex and array. This is important, as it means when we write our callback function, we will have access to these 4 values within the function (for further clarity on exactly what the four values are, check out the MDN link mentioned previously).
I think we should break down this challenge into two main problems. We need to:
- Write a function that returns an array of the symmetric difference (⊕) between two given arrays
- Use this function to handle an unknown number of arguments. For example:
- find (arg1 ⊕ arg2)
- if there’s an agr3, find arg3 ⊕ (arg1 ⊕ arg2)
- continue for argX
At this point, I’m going to start discussing my solution to the problem. If you’re working through FCC, I’d suggest attempting a solution on your own given what we’ve discussed above. Otherwise, proceed on…
Let’s start by writing the function we’ll use to calculate the symmetric difference between two arrays.
In other words, we need to write a function that receives two arrays as arguments, then returns an array of the numbers that are in one of the argument arrays, but not both.
One way to do this is to
- create a new empty array (curDiff) to store the symmetric diff
- use arr.reduce() to cycle through each array (need to compare each array against the other, not just one against the other)
- in the callback function of arr.reduce
- check if an element is in the other array or in the curDiff array (to prevent duplicates in curDiff)
- if not – push element to curDiff
- hint – arr.indexOf() will return -1 if the given element is not found
- return curDiff
Here’s the JavaScript code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function findSymDiff(a, b){ //array to hold diffence var curDiff = []; //compare a against b and curDiff a.reduce(function(prevVal, curVal){ if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1) curDiff.push(curVal); }, 0); //check b against a and currentDiff b.reduce(function(prevVal, curVal){ if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1) curDiff.push(curVal); }, 0); return curDiff; } |
We now have a function (findSymDiff()) that we can use within our main function to get the symmetric difference between two arrays. We now have to set up the logic to handle an unknown number of parameters received by our main function.
Our logic (using the arguments object) can look something like this:
- create new array (symDiff) to store the array returned by findSymDiff()
- compare arguments[0] to arguments[1] using findSymDiff()
- cycle through argument[]
- compare symDiff to arguments[x]
To accomplish this, we can set up a simple for loop.
If we set
|
1 |
symDiff = arguments[0]; |
we can call
|
1 |
symDiff = findSymDiff(symDiff, arguments[i]); |
in our for loop starting at i=1 and loop while i<arguments.length.
Then all we have to do is return symDiff!
Here’s how everything looks when we put it together:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
function sym(args) { //function to find symmetric difference between 2 arrays function findSymDiff(a, b){ //array to hold diffence var curDiff = []; //check 1st array against 2nd and currentDiff (to prevent duplicates from same array) a.reduce(function(prevVal, curVal){ if(b.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1) curDiff.push(curVal); }, 0); //check 2nd against 1st and currentDiff b.reduce(function(prevVal, curVal){ if(a.indexOf(curVal)==-1 && curDiff.indexOf(curVal)==-1) curDiff.push(curVal); }, 0); return curDiff; } //variable to hold the symmetric difference //set first arg equal to symDiff to make 1st call easier var symDiff = arguments[0]; //loop through all arguments for(var i=1; i<arguments.length; i++){ symDiff = findSymDiff(symDiff, arguments[i]); } return symDiff; } |
This solution passes all of the FCC test cases.
Thanks for reading, feel free to leave comments or additional solutions below. And if you’re working through Free Code Camp, hopefully this helped straighten out the code.
-Jeremy
