Javascript: Find out of sequence dates

Question

Consider this nested array of dates and names:

var fDates = [
    ['2015-02-03', 'name1'],
    ['2015-02-04', 'nameg'],
    ['2015-02-04', 'name5'],
    ['2015-02-05', 'nameh'],
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-07', 'name0'],
    ['2015-02-08', 'nameh'],
    ['2015-02-15', 'namex'],
    ['2015-02-09', 'namew'],
    ['1980-12-23', 'name2'],
    ['2015-02-12', 'namen'],
    ['2015-02-13', 'named'],
]

How can I identify those dates that are out of sequence. I don't care if dates repeat, or skip, I just need the ones out of order. Ie, I should get back:

results = [
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-15', 'namex'],
    ['1980-12-23', 'name2'],
]

('Namex' is less obvious, but it's not in the general order of the list.)

This appears to be a variation on the Longest Increase Subsequence (LIS) problem, with the caveat that there may be repeated dates in the sequence but shouldn't ever step backward.

Use case: I have sorted and dated records and need to find the ones where the dates are "suspicious" -- perhaps input error -- to flag for checking.

---

NB1: I am using straight Javascript and NOT a framework. (I am in node, but am looking for a package-free solution so I can understand what's going on...)

Answer 1

This solution tries to get all valid sequences and returns the longes sequences for filtering the parts out.

It works by iterating the given array and checks if the values could build a sequence. If a value is given, which part result has a valid predecessor, the array is appended with this value. If not a backtracking is made and a sequence is searched with a valid predecessor.

act.   array
value   7  3  4  4  5  1 23  7   comment
-----  ------------------------  ---------------------------
   7    7                        add array with single value

   3    7                        keep
           3                     add array with single value

   4    7                        keep
           3  4                  add value to array

   4    7                        keep
           3  4  4               add value to array

   5    7                        keep
           3  4  4  5            add value to array

   1    7                        keep
           3  4  4  5            keep
                       1         add array with single value

  23    7                23      add value to array
           3  4  4  5    23      add value to array
                       1 23      add value to array

   7    7                23      keep
        7                    7   fork above, filter for smaller or equal and add value
           3  4  4  5    23      keep
           3  4  4  5        7   fork above, filter for smaller or equal and add value
                       1 23      keep
                       1     7   fork above, filter for smaller or equal and add value

function longestSequences(array, getValue = v => v) {
    return array
        .reduce(function (sub, value) {
            var single = true;

            sub.forEach(function (s) {
                var temp;

                if (getValue(s[s.length - 1]) <= getValue(value)) {
                    s.push(value);
                    single = false;
                    return;
                }

                // backtracking
                temp = s.reduceRight(function (r, v) {
                    if (getValue(v) <= getValue(r[0])) {
                        r.unshift(v);
                        single = false;
                    }
                    return r;
                }, [value]);

                if (temp.length !== 1 && !sub.some(s => s.length === temp.length && s.every((v, i) => getValue(v) === getValue(temp[i])))) {
                    sub.push(temp);
                }
            });

            if (single) {
                sub.push([value]);
            }
            return sub;
        }, [])
        .reduce(function (r, a) {
            if (!r || r[0].length < a.length) {
                return [a];
            }
            if (r[0].length === a.length) {
                r.push(a);
            }
            return r;
        }, undefined);
}

function notInSequence(array, getValue = v => v) {
    var longest = longestSequences(array, getValue);
    return array.filter((i => a => a !== longest[0][i] || !++i)(0));
}

var array = [7, 3, 4, 4, 5, 1, 23, 7, 8, 15, 9, 2, 12, 13],
    fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
    usuallyFailingButNotHere = [['2015-01-01'], ['2014-01-01'], ['2015-01-02'], ['2014-01-02'], ['2015-01-03'], ['2014-01-03'], ['2014-01-04'], ['2015-01-04'], ['2014-01-05'], ['2014-01-06'], ['2014-01-07'], ['2014-01-08'], ['2014-01-09'], ['2014-01-10'], ['2014-01-11']],
    test2 = [['1975-01-01'], ['2015-02-03'], ['2015-02-04'], ['2015-02-04'], ['2015-02-05'], ['1929-03-12'], ['2023-07-01'], ['2015-02-07'], ['2015-02-08']];

console.log(longestSequences(array));
console.log(notInSequence(array));

console.log(notInSequence(fDates, a => a[0]));

console.log(longestSequences(usuallyFailingButNotHere, a => a[0]));
console.log(notInSequence(usuallyFailingButNotHere, a => a[0]));

console.log(longestSequences(test2, a => a[0]));
console.log(notInSequence(test2, a => a[0]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Here's an adaptation of Rosetta Code LIS to take a custom getElement and compare functions. We can refine the comparison and element-get functions based on your specific needs.

function f(arr, getElement, compare){
  function findIndex(input){
    var len = input.length;
    var maxSeqEndingHere = new Array(len).fill(1)
    for(var i=0; i<len; i++)
      for(var j=i-1;j>=0;j--)
        if(compare(getElement(input, i), getElement(input, j)) && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
          maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
    return maxSeqEndingHere;
  }

  function findSequence(input, result){
    var maxValue = Math.max.apply(null, result);
    var maxIndex = result.indexOf(Math.max.apply(Math, result));
    var output = new Set();
    output.add(maxIndex);
    for(var i = maxIndex ; i >= 0; i--){
      if(maxValue==0)break;
      if(compare(getElement(input, maxIndex), getElement(input, i))  && result[i] == maxValue-1){
        output.add(i);
        maxValue--;
      }
    }

    return output;
  }

  var result = findIndex(arr);
  var final = findSequence(arr, result)
  return arr.filter((e, i) => !final.has(i));
}

var fDates = [
    ['2015-02-03', 'name1'],
    ['2015-02-04', 'nameg'],
    ['2015-02-04', 'name5'],
    ['2015-02-05', 'nameh'],
    ['1929-03-12', 'name4'],
    ['2023-07-01', 'name7'],
    ['2015-02-07', 'name0'],
    ['2015-02-08', 'nameh'],
    ['2015-02-15', 'namex'],
    ['2015-02-09', 'namew'],
    ['1980-12-23', 'name2'],
    ['2015-02-12', 'namen'],
    ['2015-02-13', 'named'],
];

console.log(f(fDates, (arr, i) => arr[i][0], (a,b) => a >= b));

Answer 3

This solution uses the function reduce and keeps the previously accepted date to make the necessary comparisons.

var fDates = [['2015-02-03', 'name1'], ['2015-02-04', 'nameg'], ['2015-02-04', 'name5'], ['2015-02-05', 'nameh'], ['1929-03-12', 'name4'], ['2023-07-01', 'name7'], ['2015-02-07', 'name0'], ['2015-02-08', 'nameh'], ['2015-02-15', 'namex'], ['2015-02-09', 'namew'], ['1980-12-23', 'name2'], ['2015-02-12', 'namen'], ['2015-02-13', 'named']],
results = fDates.reduce((acc, c, i, arr) => {
  /*
   * This function finds a potential valid sequence.
   * Basically, will check if any next valid sequence is
   * ahead from the passed controlDate.
   */
  function sequenceAhead(controlDate) {
    for (var j = i + 1; j < arr.length; j++) {
      let [dt] = arr[j];
      //The controlDate is invalid because at least a forward date is in conflict with its sequence.
      if (dt > acc.previous && dt < controlDate) return true; 
    }
    
    //The controlDate is valid because forward dates don't conflict with its sequence.
    return false; 
  }
  
  let [date] = c; //Current date in this iteration.
  if (i > 0) { // If this is not the first iteration
    if (date === acc.previous) return acc; // Same as previous date are skipped.
    // If the current date is lesser than previous then is out of sequence.
    // Or if there is at least valid sequence ahead.
    if (date < acc.previous || sequenceAhead(date)) acc.results.push(c); 
    else acc.previous = date; // Else, this current date is in sequence.
  } 
  else acc.previous = date; // Else, set the first date.

  return acc;
}, { 'results': [] }).results;

console.log(results);

.as-console-wrapper { max-height: 100% !important; top: 0; }