compare order of two arrays-CodePudding

Say I have this default array in JavaScript:

const default = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']

I have this array provided by the user:

const user_arr = ['red', 'green', 'violet']

I need to compare these two arrays and validate that the user array is in the correct order (i.e. I am allowed to skip levels, but reverse order is not allowed).

So the following arrays would be valid:

['red', 'orange', 'violet']
['yellow', 'blue']
['green', 'indigo', 'violet']

There arrays would be invalid:

['red', 'violet', 'orange']
['green', 'violet', 'yellow]

Is this possible without using complex tree data structures?

CodePudding user response：

Here I map each element in the user array to its index in the proper array.

The array of indexes is checked to make sure it's in ascending order.

note that "default" is a javascript keyword and isn't a valid variable name

const proper = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']

const isValid = (arr) => {
  
  const isAscending = (arr) => arr.every((el, i, a) => 
    i === a.length - 1
    ? true
    : el < a[i   1]
  );

  return isAscending(arr.map(el => proper.indexOf(el)));
}

const user_arr = ['red', 'green', 'blue']

console.log(isValid(user_arr));
console.log(isValid(['red', 'indigo', 'orange']));

CodePudding user response：

This approach uses a Map which maps the value of an item to its index within the array.

Then we check for every element in a user array whether we have that array in our original array. If we have not, the user array is invalid. If it is a known item we need to get its position in the original array and check if it greater than the previous position we have checked. If it is, everything is fine, if it is not, the user array is invalid.

const order = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
const indexToValue = new Map();
order.forEach((item, idx) => indexToValue.set(item, idx));

const validArrays = [
  ["red"],
  ["red", "orange", "violet"],
  ["yellow", "blue"],
  ["green", "indigo", "violet"],
];

const invalidArrays = [
  ["red", "violet", "orange"],
  ["green", "violet", "yellow"],
];

/**
 *
 * @param {Array<string>} userArray
 * @param {Map<string, number>} indexToValue
 * @returns
 */
function checkCorrectness(userArray, indexToValue) {
  if (!Array.isArray(userArray) || userArray.length === 0) return false;
  let prev = -1;
  return userArray.every((item) => {
    // an unknown item is in the user array so it is invalid 
    if (!indexToValue.has(item)) return false;
    // get index of the element in the original array
    const idxInOrig = indexToValue.get(item);
    // if the current index is smaller than the previous index -> invalid! stop immediately 
    if (idxInOrig < prev) return false;
    // everything is fine current index is bigger than previous -> continue with next one
    prev = idxInOrig;
    return true;
  });
}

console.log("Invalid arrays")
invalidArrays.forEach(invalid => console.log(checkCorrectness(invalid, indexToValue)));
console.log("Valid arrays")
validArrays.forEach(valid => console.log(checkCorrectness(valid, indexToValue)));