freeCodeCamp Algorithm Challenge Guide: Symmetric Difference

freeCodeCamp Algorithm Challenge Guide: Symmetric Difference
0.0 0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

Symmetric difference is the difference between two sets i.e., the collection of elements which are members of either set but not both.

In the symmetric difference algorithm, you would work through the arrays of numbers in this manner: sym(A, B, C) translates to sym(sym(A, B), C) i.e., the symmetric difference of set A and set B is found first and then, the symmetric difference of the resultant set and set C is found.

Example: sym([1, 2, 5], [2, 3, 5], [3, 4, 5]) equals [1, 4, 5].

Relevant Links

:speech_balloon: Hint: 1

The arguments object is not an array. It is similar to an array, but does not have any array properties except length. For example, it does not have the pop method. However, it can be converted to a real array: var args = Array.prototype.slice.call(arguments);

try to solve the problem now

:speech_balloon: Hint: 2

Write a function that returns the symmetric difference of the two arrays: yourFunction([1, 2, 3], [2, 4, 6]) must return [1, 3, 4, 6]

try to solve the problem now

:speech_balloon: Hint: 3

Use Array.prototype.reduce along with yourFunction to repeat the process on multiple arguments

Something strange about the definition of symmetric difference is that if one identical item occurs in three different sets, it is a member of the symmetric difference. For example:

a = [1, 2, 5]
b = [2, 3, 5]
c = [3, 4, 5]

sym(a, b) = [1, 3]
sym([1, 3], c) = [1, 4, 5]

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function sym() {
    var args = [];
    for (var i = 0; i < arguments.length; i++) {
        args.push(arguments[i]);
    }

    function symDiff(arrayOne, arrayTwo) {
        var result = [];

        arrayOne.forEach(function(item) {
            if (arrayTwo.indexOf(item) < 0 && result.indexOf(item) < 0) {
                result.push(item);
            }
        });

        arrayTwo.forEach(function(item) {
            if (arrayOne.indexOf(item) < 0 && result.indexOf(item) < 0) {
                result.push(item);
            }
        });

        return result;
    }

    // Apply reduce method to args array, using the symDiff function
    return args.reduce(symDiff);
}

:rocket: Run Code

Code Explanation:

  • push() is used to break down the arguments object to an array, args.
  • The symDiff function finds the symmetric difference between two sets. It is used as a callback function for the reduce() method called on args.
  • arrayOne.forEach() pushes the elements to result which are present only in arrayOne as well as not already a part of result.
  • arrayTwo.forEach() pushes the elements to result which are present only in arrayTwo as well as not already a part of result.
  • The result, which is the symmetric difference is returned. This solution works for any number of sets.

Relevant Links

:sunflower: Intermediate Code Solution:

function sym() {

  // Convert the argument object into a proper array
  var args = Array.prototype.slice.call(arguments);

  // Return the symmetric difference of 2 arrays
  var getDiff = function(arr1, arr2) {

    // Returns items in arr1 that don't exist in arr2
    function filterFunction(arr1, arr2) {
      return arr1.filter(function(item) {
        return arr2.indexOf(item) === -1;
      });
    }

    // Run filter function on each array against the other
    return filterFunction(arr1, arr2)
      .concat(filterFunction(arr2, arr1));
  };

  // Reduce all arguments getting the difference of them
  var symarray = args.reduce(getDiff, []);

  // Run filter function to get the unique values
  var unique = symarray.filter(function(elem, index, self) {
    return index === self.indexOf(elem);
    });
  return unique;
}

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

:rocket: Run Code

Code Explanation:

  • The slice() method is used to break down the arguments object to an array, args.
  • The getDiff function finds the symmetric difference between two sets, arr1 and arr2. It is used as a callback function for the reduce() method called on args.
  • The first filterFunction() returns elements in arr1 that don’t exist in arr2.
  • The next filterFunction() is run on each array against the other to check the inverse of the first check for uniqueness and concatenate it.
  • symarray consists of the reduced arguments.
  • filter() is used on symarray to keep only the unique values and unique is returned.

Relevant Links

:rotating_light: Advanced Code Solution:

function sym() {
  // difference between set A and set B
  const diff = (A, B) => new Set([...A].filter(n => !B.has(n)));
  // spread operator to convert array like object to array
  const result = [...arguments]
    // map elements in arguments (array) to Set
    .map(arr => new Set(arr))
    // using the formula in https://en.wikipedia.org/wiki/Symmetric_difference
    // i reduce it by uniting the diff(A, B) and diff(B, A)
    .reduce((acc, set) => new Set([...diff(acc, set), ...diff(set, acc)]));

  // convert the set to array by using spread operator again
  return [...result];
}

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

:rocket: Run Code

Code Explanation:

  • diff consists of the difference between set A and set B.
  • result holds the object which has been converted to an array using the spread operator.
  • map() is used to populate the new set object with elements from arr using the symmetric difference formula.
  • Before returning, the set is converted to an array using the spread operator.

Relevant Links

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:
  • Please add your username only if you have added any relevant main contents. (:warning: DO NOT remove any existing usernames)

See :point_right: Wiki Challenge Solution Template for reference.


#2

#3

#4

Hi @Rafase282,

I’m not sure how to contribute to this, so I hope this is the right place. Symmetric difference turned out to be the hardest problem for me so far (went from very bruteforce to a respectable degree of cleverness).
Anyway, I think my solution is perhaps more readable as an Intermediate solution (I’m not confident enough to call it better, it may be less performant)… would you be so kind to have a look?

      function sym() {
      // get the arguments in a proper Array
      var args = Array.prototype.slice.call(arguments);
      // call reduce on the arguments using the diff function, and return the end-result
      return args.reduce(diff);
    }

    // returns the unique elements in the union of the arrays
    function diff(arrX, arrY){
      // clean up both arrays, so we don't have duplicates in a set/array
      arrX = sortAndClean(arrX);
      arrY = sortAndClean(arrY);
      // concatenate both arrays and sort
      // then cleverly filter out elements that show up more than once (common elements)
      // leaving us with the unique elements in the union
      var result = arrX.concat(arrY).sort(function(a,b){
        return a - b;
      }).filter(function(x, i, arr){
        return arr.indexOf(x) === arr.lastIndexOf(x);
      });

      return result;
    }
    // sortAndClean simply ends up giving us the unique elements in the Array
    // i.e. it sorts and de-duplicates
    function sortAndClean(arr){
      arr = arr.sort(function(a,b){
        return a - b;
      }).filter(function(x, i, arr){
        return x !== arr[i+1];
      });
      return arr;
    }
    //Test it
    sym([1, 2, 5], [2, 3, 5], [3, 4, 5]);

Cheers,
-Balach


#5

It was a difficult problem for me as well. I came up with this:


function sym() {
  var inputs = Array.from(arguments);
  
  return inputs.reduce(function(prev, current) {
    prev = Array.from(new Set(prev));
    current = Array.from(new Set(current));
    
    return prev.concat(current).filter(function(el, i, arr) {
      return (arr.indexOf(el) === (arr.length - 1) || arr.indexOf(el, i+1) === -1) &&
             ((arr.lastIndexOf(el) === 0) || arr.lastIndexOf(el, i-1) === -1);
    });
  });
  
}

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

#6
function sym(args) {
  var arr = Array.from(arguments);
  arr = arr.reduce(function(a, b) {
    var aNotB = a.filter(function(val) { return !b.includes(val); });
    var bNotA = b.filter(function(val) { return !a.includes(val); });
    return aNotB.concat(bNotA);
  });
  return arr.filter(function(value, index, self) {
    return self.indexOf(value) === index;
  });
}

#7

I am confused when there are multiple values in a single set. Based on all the descriptions of Symmetric
Difference, the operation is a SET LEVEL comparison, not a comparison of ELEMENTS within a SET.

Thus I think the test is wrong…

For example is says this test – "sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]) should return [1, 4, 5]."
I think it should actually return [1,1,2,4,5]

Specifically they first set contains four elements 1, 1, 2 & 5. Although the number 1 is duplicated, for Symmetric Difference you are comparing ALL ELEMENTS in the first set with all elements in sets two and three. Since neither sets two or three contain a number one, all ones are valid. Furthermore if set two had only a single 1, then it would eliminate 1 of the number ones but not both.

Now if you said, “UNIQUE SET ELEMENTS” then I’d agree that the answer would be [1,4,5]


#8

For what it’s worth, from the Wikipedia entry on Sets:

…two definitions of sets which differ only in that one of the definitions lists set members multiple times, define, in fact, the same set. Hence, the set {11, 6, 6} is exactly identical to the set {11, 6}. The second important point is that the order in which the elements of a set are listed is irrelevant (unlike for a sequence or tuple). We can illustrate these two important points with an example:

{6, 11} = {11, 6} = {11, 6, 6, 11} .

Javascript is consistent with this, e.g., new Set([11, 6, 6, 11]) results in creation of a set object {11, 6}


#9

My take on a solution to this one:

function sym() {
 // Convert arguments into an array and eliminate duplicate elements 
 // within each argument.
  return [...arguments].map(arg => [...new Set(arg)])
     // concatenate successive arguments a and b     
     .reduce((a,b) => a.concat(b)
     // elements that are in both a and b will appear twice, filter 
     // these out to get the Symmetric Difference
     .filter((el, i, arr) => 
         !(arr.indexOf(el) < i || arr.indexOf(el, i + 1) > -1)))
    .sort((a,b) => a - b );
}

#10

Thanks. I still recall from SAT and past problems describing a SET or (BAG) of “12 BLUE and 6 RED MARBLES” and a SET of “12 RED MARBLES and 6 BLUE MARBLES” with the Intersection being “6 RED and 6 BLUE”

It seems there is a distinction (that is not clear in the problem description) that they are talking about a pure mathematical description of a set…for example mathematicians would describe the set of WHOLE NUMBERS, and as such there are no duplicates WHOLE NUMBERS., the number ONE is the number ONE no matter how many times is listed. But if I’m talking about the SET of THINGS (like COLORED MARBLES) if I have FIVE BLUE MARBLES, I do in fact have FIVE different things.

Thanks Philip


#11

Hi, this problem wasn’t the most dificult to me, the “Smallest Common Multiple Complete” problem freaked me out, so I’ll put here my solution, but I don’t think that is better, just a little diferent from the others soluctions shown here:

function sym(args) {
  
  var auxArguments = Array.from(arguments);
  var auxArr = [];
  
  for(var i = 1 ; i < auxArguments.length; i ++){
    auxArr = auxArguments[i-1].filter(function (value, index){
      return auxArguments[i].indexOf(value) === -1 && auxArguments[i - 1].indexOf(value, index + 1) === -1;
  }).concat(auxArguments[i].filter(function(value1, index1){
      return auxArguments[i - 1].indexOf(value1) === -1 && auxArguments[i].indexOf(value1, index1 + 1) === -1;
   }));
        
    auxArguments[i] = auxArr;
  }
  
  return auxArr;
  
}

#12

@drguildo Thought I come up with a neat concise version, but you already have pretty much the same: :smiley:

/*jshint esversion: 6 */
function sym(params) {
  var args = Array.prototype.slice.call(arguments);
  return args.reduce((a, b) => {
    return a.filter(el => !b.includes(el)).concat(b.filter(el => !a.includes(el)));
  }, []).filter((el, i, arr) => arr.indexOf(el) === i).sort((a, b) => a - b);
}

I also sorted the array at the end, which is not necessary to pass the test but to get the same sorted result as proposed.

By the way, I like most of your solutions from the other exercises as well! It proves that you really put in some thought on refactoring like I do. :slight_smile:


#14

How about this one-liner? Can anyone do it shorter? :stuck_out_tongue:

function sym(args) {
  return Array.from(arguments) \
         .reduce((a,b)=>a.concat(b).filter(el=>(a.indexOf(el)==-1||b.indexOf(el)==-1),[])) \
         .filter((el,index,array)=> array.indexOf(el)==index);
}

#15

Here’s what I came up with. it was hard, ,but not the hardest for me to solve. I agree with others, it threw me for a loop that repeats of the same value were not allowed.


function diffArray(arr1,arr2) {
  console.log("starting to diff", arr1,arr2);
  var unique1=[];
  var unique2=[];
  var kindOfUnique;
  unique1=arr2.filter(function(val) {
    return arr1.indexOf(val) === -1;
  });
  console.log("unique1=", unique1);
  unique2=arr1.filter(function(val) {
    return arr2.indexOf(val) === -1;
  });
  console.log("unique2=", unique2);
  kindOfUnique=unique1.concat(unique2);
  var noDup = kindOfUnique.filter (function (value, index, array) {
    //console.log("value=", value, "index=", index);
    //  console.log(array);
      return array.indexOf (value) == index;
  });
  console.log(noDup);
  return noDup;

}
function sym(arg) {
  var combined= Array.prototype.slice.call(arguments);
  //console.log(combined);
  //console.log(combined.reduce(diffArray,[]));
  return combined.reduce(diffArray,[]);
}
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);



#16

obtw, the ‘estimate’ of the number of hours to complete a section is laughable in my case…
(as in grossly underestimated)


#17

Mine :

function sym(args) {
let arg = […arguments];
let newArr = [];
let redArr = arg.reduce((arrayOne,arrayTwo)=>{
newArr = arrayOne.filter((item)=>{return arrayTwo.indexOf(item)===-1;}).concat(arrayTwo.filter((item)=>{return arrayOne.indexOf(item) === -1;}));
return newArr.filter((item,pos)=>{return newArr.indexOf(item)===pos;});});
return redArr;
}

sym([3, 3, 3, 2, 5], [2, 1, 5, 7], [3, 4, 6, 6], [1, 2, 3], [5, 3, 9, 8], [1]);


#18

Very nice, understandable solution. I played with it a bit and it appears you don’t actually need reduce.

function diffArray(arr1, arr2) {
  var newArr = arr1.concat(arr2)
    .filter( (el) => arr1.indexOf(el) == -1 || arr2.indexOf(el) == -1)
    .filter( (el, index, array) => array.indexOf(el) == index);

  return newArr;
}

Notes:

  • This problem is limited to diffing two arrays. It appears an earlier incarnation of the test allowed an arbitrary number of argument arrays.
  • For the given test input (both in the main challenge set and the new beta, which appear identical for this problem), the second filter is not necessary. But try diffArray([1, 1, 2], [2, 3 ]) to see why it’s needed.

#19

@pennyJack
@cambsCoder
Hey there! I’ve made almost the same solution, it’s kinda fun to know someone else wrote the same code:

const sym = (...args) =>
  args.reduce((acc, val) =>
    acc.concat(val).filter(x => !val.includes(x) || !acc.includes(x))
  ).filter((x, i, self) => self.indexOf(x) == i);

How about using a spread operator in your solution like […arguments] instead of Array.prototype.slice.call(arguments)? I know it’s poorly supported, but you’ve already used includes() which is not so good as well :slight_smile:
Here is the link: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Spread_operator


#20

I would like to offer this solution:

function unique (value, index, self){
  return self.indexOf(value)===index
  }

function sym(...args) {
  var arr = args.reduce(function(accum, item){
    item=item.filter(unique)
    var newAccum = accum.filter(element => !item.includes(element))
    var newAccum2 = item.filter(element => !accum.includes(element))
    newAccum = newAccum.concat(newAccum2)
    return newAccum
  }, [])
  return arr;
}

#21

Here my solution too. Slightly different than the other solutions here.

function sym(args) {
var difference = [];
var unique = [];
for (var i=0; i<arguments.length; i++) {
/* Make each element in the individual array unique */
unique = arguments[i].filter(function(item, j, ar){ return ar.indexOf(item) === j; });

/* Compare each element for being in the difference-aray */
for (var y=0; y<unique.length; y++) {
  pos = difference.indexOf(unique[y]);
  if (pos == -1) {
    difference.push(unique[y]);
  }
  else {
    difference.splice(pos, 1);
  }
}

}
return difference;
}