CODEWITHSUNDEEP
javascriptarraysalgorithmcompareindexof
Bardelman
Bardelman

Reputation: 2298

Algorithm to guess which array element has its index (position) changed inside the same array

I've been looking for a while at this thread but all i could find there as results of comparaison between two arrays are which elements were added or removed.

What i need is to just guess which element has moved from an index to another.

Example: let's take the following array:

let array1 = ['A', 'B', 'C', 'D', 'E', 'F'];

The 'E' element will move from the 4th index to the 2nd index and we wil get :

 let array2 = ['A', 'B', 'E', 'C', 'D', 'F'];

I need a function that returns which element has changed , its new index in the new array2 and its old index in the array1;

I've made such as algo in the past which roughly (from what i remember now) consists of looking for the first different element between both arrays then to check the sequence behind it to guess if the diff element found is itself the moved one or the one which took its place.

So before rewritting it , i wished i could find one ready to use ;)

Upvotes: 2

Views: 626

Answers (3)

Peter Seliger
Peter Seliger

Reputation: 13432

The approach is as follows ...

  • iterate one of the arrays, preferably the current one.
  • for each current item/value get its index from the recent array ...
  • ... and compare this item's/value's current index to its recent index.
  • in case both indices do not equal (including a recent index of -1 due to a removed value/item) create a state like object with data of the value and the indices and push it into the result array.

The implementation is based on Array.prototype.reduce where on would process the current item array and would pass the recent item array as part of a accumulator/collector as the reducer function's initial value.

function collectPositionChange({ recent, result }, value, currentIdx) {
  const recentIdx = recent.indexOf(value);
  if (recentIdx !== currentIdx) {

    result.push({ value, currentIdx, recentIdx });
  }
  return { recent, result };
}
const recentItems = ['A', 'B', 'E', 'C', 'D', 'F'];
const currentItems = ['A', 'B', 'C', 'D', 'E', 'F'];

console.log(
  currentItems
    .reduce(collectPositionChange, { recent: recentItems, result: [] })
    .result
);
console.log(
  ['A', 'C', 'D', 'B', 'E', 'F']
    .reduce(collectPositionChange, { recent: ['A', 'B', 'C', 'D', 'E', 'F'], result: [] })
    .result
);
console.log(
  ['A', 'B', 'C', 'D', 'E', 'F']
    .reduce(collectPositionChange, { recent: ['A', 'C', 'D', 'B', 'E', 'F'], result: [] })
    .result
);
.as-console-wrapper { min-height: 100%!important; top: 0; }

Upvotes: 1

Bardelman
Bardelman

Reputation: 2298

let array1 = ['A', 'B', 'C', 'D', 'E', 'F'];

// test 1 : moving 'B' from index 1 to index 3
let array2 = ['A', 'C', 'D', 'B', 'E', 'F'];

// test 2: moving 'E' from 4 to 1
// let array2 = ['A', 'E', 'B', 'C', 'D', 'F'];

// test 3 : moving 'A' from 0 to 5
// let array2 = ['B', 'C', 'D', 'E', 'F', 'A'];

function getMovedElementInfos(array1, array2) {
    let firstDiffElIndexInNewArray = array2.findIndex((el, elindx) => el !== array1[elindx]);
    let firstDiffElInNewArray = array2[firstDiffElIndexInNewArray];
    let nextElInNewArray = array2[firstDiffElIndexInNewArray + 1];
    let firstDiffElIndexInOldArray = array1.findIndex(el => el === firstDiffElInNewArray);
    let nextElInOldArray = array1[firstDiffElIndexInOldArray + 1];
    let movedEl, movedElFrom, movedElTo;
    if (nextElInNewArray === nextElInOldArray) {
        movedEl = array1[firstDiffElIndexInNewArray];
        movedElFrom = firstDiffElIndexInNewArray;
        movedElTo = array2.findIndex(el => el === movedEl);
    } else {
        movedEl = firstDiffElInNewArray;
        movedElFrom = firstDiffElIndexInOldArray;
        movedElTo = firstDiffElIndexInNewArray;
    }
    return {
        movedEl,
        movedElFrom,
        movedElTo
    }
}
const {
    movedEl,
    movedElFrom,
    movedElTo
} = getMovedElementInfos(array1, array2)

console.log('movedEl is: ', movedEl);
console.log('movedEl index in old array is: ', movedElFrom);
console.log('movedEl index in new array is: ', movedElTo);

console.log('array1[movedElFrom]: ', array1[movedElFrom]);
console.log('array2[movedElTo]: ', array2[movedElTo]);

Upvotes: 0

Jeff B
Jeff B

Reputation: 1060

I am not sure what the full requirements are, but this will detect forward and backwards movement as well as character swaps. It will work on any order, but its prediction on what changed gets less accurate the more changes that occur in a row. Here is a sample that uses a dictionary:

const array1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'];
const array2 = ['A', 'B', 'E', 'C', 'D', 'F', 'H', 'I', 'G', 'K' , 'J'];
let globalOffset = 0;
let currentSuspect = "";
var dict = new Object();
array1.forEach((char, index) => {
  dict[char] = index;
});
array2.forEach((char, index) => {
  dict[char] = dict[char] - index;
});

let offset = 0;
let prevValue = 0;
Object.entries(dict).forEach((entry, index) => {
  const [key, value] = entry;
  
  switch(true){
    case offset === 0 && value < -1:
      console.log(`The character ${key} had its index moved forward by ${Math.abs(value)}! \n New index: ${index + Math.abs(value)} - Old index: ${index}`);
      break;
    case offset < 0 && value > 1:
      console.log(`The character ${key} had its index moved backwards by ${value}! \n New index: ${index + offset} - Old index: ${index}`);
      break;
    case prevValue === -1 && offset === -1 && value === 1:
      console.log(`The characters ${key} and ${array2[index]} were swapped!`);
      break;
  }
  prevValue = value;
  offset += value;
});

Upvotes: 1

Related Questions