Given two arrays of the same length, find which elements are "shifted"

Question

To start, here are some examples.

['d', 'b', 'c', 'd', 'e']
['c', 'd', 'e', 1, 2]
// desired result: [1, 2]

[1, 2, 3]
[2, 3, 4]
// desired result: [4]

['Hello', 'Goodbye', 'Goodbye', 'Hello']
['Goodbye', 'Hello', 'Goodbye', 'Goodbye']
// desired result: ['Goodbye', 'Goodbye']

The elements are shifted n indexes (where n is less than the length of both arrays). The arrays are always the same length. They are always shifted from the right side of the array. Is there a way to do this?

I was thinking of finding the largest subset in both arrays then taking the right or something. Can't find a great way to approach it

Shouldn't the last result be `['Goodbye', 'Goodbye', 'Goodbye', 'Goodbye']? — Selfish, Oct 02 '15 at 19:34
shift off the A until they match, then take a subset of B starting at A's new length. — ergonaut, Oct 02 '15 at 19:34
To clarify, are the values of `n` in your examples `2, 1, 2`? — ryanyuyu, Oct 02 '15 at 19:40

score 3 · Accepted Answer · answered Oct 02 '15 at 19:50

The logic is somewhat simple, the major problem is to compare two Arrays.

I'm using the JSON.stringify to do that, but it's possible to loop through the Arrays too.

First you loop into arr a and shift it, until it has the same elements of the first items of b.

Then, you get the arr b and slice from the length of arr a.

function findCrazyShifts(a, b) {
  while (JSON.stringify(a) !== JSON.stringify(b.slice(0, a.length))) {
    a.shift();
  }

  return b.slice(a.length);
}

console.log(findCrazyShifts(['d', 'b', 'c', 'd', 'e'], ['c', 'd', 'e', 1, 2]));
// result: [1, 2]

console.log(findCrazyShifts([1, 2, 3], [2, 3, 4]));
// result: [4]

console.log(findCrazyShifts(['Hello', 'Goodbye', 'Goodbye', 'Hello'], ['Goodbye', 'Hello', 'Goodbye', 'Goodbye']));
// result: ['Goodbye', 'Goodbye']

score 2 · Answer 2 · edited May 23 '17 at 11:51

function unshifter(a,b) {  
  while(!a.equals(b.slice(0,a.length))) {
    a.shift();
  }
  return b.slice(a.length, b.length);
}

// attach the .equals method to Array's prototype to call it on any array
Array.prototype.equals = function (array) {
    // if the other array is a falsy value, return
    if (!array)
        return false;

    // compare lengths - can save a lot of time 
    if (this.length != array.length)
        return false;

    for (var i = 0, l=this.length; i < l; i++) {
        // Check if we have nested arrays
        if (this[i] instanceof Array && array[i] instanceof Array) {
            // recurse into the nested arrays
            if (!this[i].equals(array[i]))
                return false;       
        }           
        else if (this[i] != array[i]) { 
            // Warning - two different object instances will never be equal: {x:20} != {x:20}
            return false;   
        }           
    }       
    return true;
}  

console.log(unshifter(['d', 'b', 'c', 'd', 'e'], ['c', 'd', 'e', 1, 2]));
console.log(unshifter([1, 2, 3], [2, 3, 4]));
console.log(unshifter(['Hello', 'Goodbye', 'Goodbye', 'Hello'], ['Goodbye', 'Hello', 'Goodbye', 'Goodbye']));

This code uses How to compare arrays in JavaScript?

Looks right to me. This JSFiddle shows it working for the three examples given, anyway: http://jsfiddle.net/4t5ajjnq/. You could improve this answer by including that `equals` method here and including those examples in a runnable snippet. — Drew Gaynor, Oct 02 '15 at 19:51

score 1 · Answer 3 · answered Oct 03 '15 at 11:22

Such a task can be achieved by iterating through the 2nd array (b) from the end and comparing backwards with a from it's end. Just a few lines of code, and this avoids unnecessary mutation of arrays. Can be further optimized at the cost of code complexity by skipping ahead ("accelerating" i) depending on what's found in the inner compare, but I left that bit out as it doesn't seem necessary here:

function getShifted(a, b) {
  if(a.length != b.length)
    return;

  var len = a.length;
  for(var i = b.length - 1, j; i >= 0; i--) {
    for(j = 0; j <= i && a[len - j - 1] == b[i - j]; j++);
    if(j > i) {
      return b.slice(i + 1);
    }
  }

  return [];
}


function writeShifted(a, b) {
  document.write('a: ' + JSON.stringify(a));
  document.write('<br />');
  document.write('b: ' + JSON.stringify(b));
  document.write('<br />');
  document.write('shifted: ' + JSON.stringify(getShifted(a, b)));
  document.write('<br /><br />');
}

writeShifted(['d', 'b', 'c', 'd', 'e'],
             ['c', 'd', 'e', 1, 2]);
// desired result: [1, 2]

writeShifted([1, 2, 3],
             [2, 3, 4]);
// desired result: [4]

writeShifted(['Hello', 'Goodbye', 'Goodbye', 'Hello'],
             ['Goodbye', 'Hello', 'Goodbye', 'Goodbye']);
// desired result: ['Goodbye', 'Goodbye']

Given two arrays of the same length, find which elements are "shifted"

3 Answers3