Identify removed, appended and prepended between two arrays

Question

I am trying to find deep differences between two arrays, like below

 var arr = [5,4,6,7,8,9]; var against = [1,2,4,5,6];

then result should be

 appended = [7, 8, 9], prepended = [], removed = [1, 2]

I am running out of logic and this is what I have tried

 var prepend = [];
 var append = [];
 var removed = [];

 var len = against.length;

 while (len--) {
    var itm = listSplit[len];
    if (arr.indexOf(itm) === -1) {
       removed.push(len);
    } else if (itm < arr[0]) {
       // ??
    }
 }

How can I find these values. Give me some idea on logic to find this.

Answer 1

You can achieve your answer by using filter function only.

Here is what you wants

var appended = arr.filter(function (elm) {
    return against.filter(function (elm2) {
        return elm2 == elm
    }).length == 0;
})

Above code is for appended array.

var removed = against.filter(function (elm) {
    return elm < arr[0]
});

Above code is for removed array

var prepended = arr.filter(function (elm) {
    return elm < against[0]
});

Above code is for prepended array.

Answer 2

This works .

// 1. inputs are sorted arrays. example [ -7, -6, 0, 4, 5, 6, 7, 8, 9 ] [ 1, 2, 4, 5, 6 ]
// 2. differences are contiguous. If not, question the question!
function diff(now, was) {
var results = {prepended:[], appended:[], removed:[]}
    // prepended is -7 thru 0. Its realm is the now array
    for ( var inow = 0; inow < now.length; ++inow ) {
        if ( now[inow] >= was[0] ) {
            break;
        }
    }
    // inow points to first element in now that is part of was
    results.prepended = now.slice(0,inow);

    // removed is 1 thru 2. Its realm is the was array
    var ref = now[inow];
    for ( var iwas = 0; iwas < was.length; ++iwas ) {
        if ( was[iwas] == ref ) {
            break;
        }
    }
    // iwas points to the first element in was that is present in now
    results.removed = was.slice(0,iwas);

    // appended is 7 thru 9. Its realm is now
    var ref = was[was.length-1];
    var i = now.indexOf(ref);
    if ( i !== -1 ) {
        while ( ++i < now.length && now[i] == ref ) {}
        results.appended = now.slice(i);
    }
    console.log("> orig", now, was);
    console.log("> results", results);
}

console.log("\nempties");
diff([], []);

console.log("\nsample");
diff([-7,-6,0,4,5,6,7,8,9], [1,2,4,5,6]);

console.log("\nsample2");
diff([-7,-6,0,4,5,6,6,7,8,9], [1,2,4,5,6]);

console.log("\nonly prepended/removed");
diff([-7,-6,0,4,5,6], [1,2,4,5,6]);

console.log("\nonly removed");
diff([4,5,6], [1,2,2,4,4,5,6]);

The output when run in node

C:\node>node pa.js

empties
> orig [] []
> results { prepended: [], appended: [], removed: [] }

sample
> orig [ -7, -6, 0, 4, 5, 6, 7, 8, 9 ] [ 1, 2, 4, 5, 6 ]
> results { prepended: [ -7, -6, 0 ],
  appended: [ 7, 8, 9 ],
  removed: [ 1, 2 ] }

sample2
> orig [ -7, -6, 0, 4, 5, 6, 6, 7, 8, 9 ] [ 1, 2, 4, 5, 6 ]
> results { prepended: [ -7, -6, 0 ],
  appended: [ 7, 8, 9 ],
  removed: [ 1, 2 ] }

only prepended/removed
> orig [ -7, -6, 0, 4, 5, 6 ] [ 1, 2, 4, 5, 6 ]
> results { prepended: [ -7, -6, 0 ], appended: [], removed: [ 1, 2 ] }

only removed
> orig [ 4, 5, 6 ] [ 1, 2, 2, 4, 4, 5, 6 ]
> results { prepended: [], appended: [], removed: [ 1, 2, 2 ] }

Answer 3

The unfortunate answer: it's impossible.

It's impossible because we don't have a "change log" on what happened to the array to get it to a particular state.

Consider, for example, the following arrays:

var original = [2, 2, 2];

var modified1 = original.concat(2);

var modified2 = [2].concat(original);

var modified3 = modified2.slice(1);

This is of course an extreme example, but in their final states, modified1 has the same contents as modified2 (despite taking different paths to get there), and, perhaps worse, modified3 actually has the same value as original, despite having been substantially modified in the meantime.

Conclusion: without a very strict set of rules around what modifications can be made to the arrays and in which order, it's impossible to be as particular as saying what was prepended, appended, or removed.

What you can always do, however, is provide a diff. Diff's are useful in this case, because they don't care about how the changes occurred; they only care about what the final difference actually is. Keep in mind, however, you still need to define how you want the diff to work. That is, given the following arrays:

var array1 = [1, 2, 3, 4, 5];

var array = [2, 3, 4, 5, 6];

... would you define that as two changes?

1. Removed a leading 1
2. Added a trailing 6

...or five changes (since the values differ at each index)? If you say only two, then what about:

var array1 = [1, 1];

var array = [1, 6];

It's the exact same modification (remove a leading 1, add a trailing 6), but in this case it looks more like just a single change:

1. Change trailing 1 to a 6.

So yeah, this is one of those "answer the question by way of retaliating with a bunch of other questions" answers, but you need to clearly define what you need here. As it stands, there are more than a few ambiguous cases to account for.

Answer 4

Updated Fiddle

Not sure if you want the result in VanillaJS or using another Library. With Underscore.JS or Lodash.JS you'd do something like:

_.difference(against, arr) // [1,2] aka removed
_.difference(arr, against) // [7,8,9] aka appended

I don't really get what you mean with prepended because your example doesn't contain this info. Would it be distinction of the appended numbers which are added before/afterwards the original arr? What about gaps which you need to fill up? Maybe you can come up with some additional examples.

In case of simple pre/app nding you'd search for the lowest number in against and split the append() result by that one. Everything before = prepend, afterwards = append. This is doable with following approach:

// Lets say the difference is [1,7,8,9] and min number of against = 2
_.filter(_.difference(arr, against), function(n) { return n < _.min(against) }) // [1]
_.filter(_.difference(arr, against), function(n) { return n > _.min(against) }) // [7,8,9]

Answer 5

My answer is kind of complex but does the job.

JSFIDDLE

var arr = [5,4,6,7,8,9,3];
var against = [1,2,4,5,6];
var prepend = [];
var append = [];
var removed = [];
for(i=0;i<arr.length;i++){
    for(j=0;j<against.length;j++){
        if(arr[i]==against[j])
            break;
        else if(j==against.length)
            append.push(arr[i]);
        else if((parseInt(against.toString().replace(/,/g,"").indexOf(arr[i]))!=-1)!=true
               && arr[i]<against[against.length-1]
               && (parseInt(prepend.toString().replace(/,/g,"").indexOf(arr[i]))!=-1)!=true)
            prepend.push(arr[i]);
        else if(parseInt(removed.toString().replace(/,/g,"").indexOf(against[j]))==-1
               && (parseInt(arr.toString().replace(/,/g,"").indexOf(against[j]))!=-1)!=true)
            removed.push(against[j]);
        else if(parseInt(against.toString().replace(/,/g,"").indexOf(arr[i]))==-1
               && (parseInt(append.toString().replace(/,/g,"").indexOf(arr[i]))!=-1)!=true
               && (parseInt(prepend.toString().replace(/,/g,"").indexOf(arr[i]))!=-1)!=true)
            append.push(arr[i]);   
    }
}
//testing
    console.log("Appended = [" + append.toString() + "]");
    console.log("Prepended = [" + prepend.toString() + "]");
    console.log("Removed = [" + removed.toString() + "]");

Answer 6

One of the solutions could be:

var arr = [7,8,9,5,4,6]; 
var against = [1,2,4,5,6];
// make a copy of the original array as appended
var appended = arr;
var removed =[];
var prepended =[];

for(var i=0;i<against.length;i++)
{  
    //if the element is not present in the original array, add it to removed.
    if(appended.indexOf(against[i]) == -1)
    {
        removed.push(against[i]);
    }
    else
    {
        //if it is already present, it was not appended, nor prepended, 
        //remove it from appended.
        appended.splice(appended.indexOf(against[i]),1);
    }
}
// one more loop to seperate the prepended from the appended values.
for(var j=0;j<appended.length;j++)
{   
    if(appended[j] < against[against.length-1])
    {
        prepended.push(appended.splice(j,1));
        j--;
    }
}

The final values in appended array will be the appended ones, and in removed will be the removed ones. The retained ones would be the prepended.