javascript, diff function returning same string

Question

i was wondering if somebody could help me on my diff function. its supposed to find the diff between 2 inputs. the function takes in 2 arrays so if array 1 has.. "word1", "word2" and array 2 has "word1", "word2", and "word3", it should just return "word3". it works for the most part, but with the certain input below, it doesn't work.

function diff(a1, a2) {

if (a1.length > a2.length
       || a1.length == a2.length) {
    return [""];
}
a1 = a1.slice(0);
a2 = a2.slice(0);


for (i = 0; i < a1.length; i++) {
    for (k = 0; k < a2.length; k++) {
        if (a1[i] == a2[k]) {
            a1.splice(i, 1);
            a2.splice(k, 1);
        }
    }
}

for (j = 0; j < a2.length; j++) {
    for (p = 0; p < a1.length; p++) {
        if (a2[j] == a1[p]) {
            a2.splice(p, 1);
            a1.splice(j, 1);
        }
    }
}


a1 = a1.concat(a2);
return a1;
}

var s1 = ["one", "two", "three", "four",];
var s2 = ["one", "two", "three", "four", "five"];


document.write(diff(s1, s2));

the answer should just return "five", but its returning "four", "four", "five". help would be much appreciated. im super stuck. thanks a bunch!

Answer 1

As far as I understand, you want to return an array containing only differing elements from both. Try it this way, without complex double loops and splices and whatnot:

function diff(a1, a2) {

  var aa1 = {}, aa2 = {}, res = [];

  // create an object from a1, containing value:array-index pairs:
  for (var i = 0; i < a1.length; i++) {
      aa1[a1[i]] = i;
  }
  // create an object from a2 like the one from a1
  for (var i = 0; i < a2.length; i++) {
      aa2[a2[i]] = i;
  }
  /**
    * loop through the first object (from a1)
    * if a value in this object is not found in 
    * the object from a2, push that value to 
    * the result array (res)
   */
  for (var l in aa1){
    if (aa1.hasOwnProperty(l) && !(l in aa2)) {
        res.push(a1[aa1[l]]);
    }
  }
  /**
    * but the second array can also contain
    * values differing from the values in the first.
    * So, repeat the above for the object created 
    * from a2
   */
  for (var l in aa2){
   if (aa2.hasOwnProperty(l) && !(l in aa1)) {
        res.push(a2[aa2[l]]);
   }
 }
 /**
   * now res contains all different values
   * note: double values are not counted
   * so ['one','two','tree'] vs ['one','two','four','four']
   * will return ['tree','four']
   * note2: if you want to find the first difference,
   * return res[0]
   */

 return res;
}

If it's just the first difference you want to find, this (array only) method will do:

function diff(a1, a2) {
  var firstdiff = null, i = -1;

  /**
    * local function to check if value [val] 
    * exists in array [arr]. Called from
    * within the loops
    */
  function check(val,arr){
      var i = -1;
      while(++i<arr.length){
          if(val === arr[i]){ return true;}
      }
      return false;
  }
  // loop a1 and check values vs a2-values
  while (++i<a1.length){
    if (!check(a1[i],a2)) {
      return firstdiff = a1[i];
    }
  }
  // no difference found, continue a2 vs a1
  i = -1;
  while (++i<a2.length){
    if (!check(a2[i],a1)) {
      return firstdiff = a2[i];;
    }
  }
  // there are no differences, firstdiff = null
  return firstdiff;
}

Answer 2

The problem is that array.splice reduces the length of the array thus making the for loop skip over elements. Possible solution is to decrement the iterator.

EDIT:

When you splice the array it removes elements from the array making it shorter. So lets assume we are running this code:

test_array = [1, 2, 3, 4, 5];
for(i = 0; i < test_array.length; i++) {
    document.write(test_array[i]);
    if(i == 2) {
        test_array.splice(i, 1);
    }
}

you can see that it outputs 1235, rather than 12345. That would be because when i = 2 and the element is removed, all the elements in the array have their index recalculated. So if before the splice the array is:

• [0] = 1
• [1] = 2
• [2] = 3
• [3] = 4
• [4] = 5

after it becomes:

• [0] = 1
• [1] = 2
• [2] = 4
• [3] = 5

Meanwhile the for loop moves on to i = 3 but instead of test_array[3] being 4, it is now 5, thus the number 4 was skipped over.

An easy solutions for this is you can decrement the iterator.

Example:

test_array = [1, 2, 3, 4, 5];
for(i = 0; i < test_array.length; i++) {
    document.write(test_array[i]);
    if(i == 2) {
        test_array.splice(i, 1);
        i--;
    }
}

Answer 3

This comment quickly explains what your code was doing:

@Crystal, first double loop: at i=0 k=0 "one"=="one" so each is removed; at i=0 k=1 "two"!="three"; at i=0 k=2 "two"!="four"; at 0 3 "two"!="five"; 1 0 "three"!="two"; 1 1 "three"=="three" so each is removed; 1 2 "four"!="five"; no more cycles. In the second double loop: 0 0 "two"=="two" so each is removed; 0 1 is not run because at this point a1 only has "four" so a1.length==1. Thus we concat "four" in a1 with "four" and "five" in a2

To get the answer you want, change

a1.splice(i, 1);

to

a1.splice(i--, 1);

And rinse,repeat for the other 3 similar cases within the double loops. So you will have 4 cases of taking the splice and decrementing by one its first argument. This decrementing makes up for the splice's removal.

However, you now only need one of the double loops since that will remove all overlaps.

Also, why do you have a check at the top to filter out the cases of a1 having length greater than or equal to the length of a2? Remove that section as well.

The answer will be "five". You can test very different data if you want, and it should work.

So this might be your program:

function diff(a1, a2) {

a1 = a1.slice(0);
a2 = a2.slice(0);


for (i = 0; i < a1.length; i++) {
    for (k = 0; k < a2.length; k++) {
        if (a1[i] == a2[k]) {
            a1.splice(i--, 1);
            a2.splice(k--, 1);
        }
    }
}


a1 = a1.concat(a2);
return a1;
}

var s1 = ["one", "two", "seven", "three", "four",];
var s2 = ["one", "two", "four", "five", "six"];


document.write(diff(s1, s2));

Answer 4

You loop over the array while splicing it, but you don't adjust for that with your indexes.