Compare each element in an array against every other element

Question

I need to compare schedules for overlap, anywhere from 2 to infinite number of schedules.

For example, an array with 3 schedules would look like this:

var dateRanges =  [
    {
      DaysOfWeek: ['Sun', 'Mon'],
      StartTime: "01:00",
      StopTime: "17:00",
      AllDay: false
    },
    {
      DaysOfWeek: ['Tues', 'Wed'],
      StartTime: "12:00",
      StopTime: "21:59",
      AllDay: true
    },
            {
      DaysOfWeek: ['Thur', 'Sun'],
      StartTime: "12:00",
      StopTime: "21:59",
      AllDay: true
    }
  ]

I'm struggling to figure out how to compare all arrays with each other. So far I have this

checkScheduleForOverlap: function (dateRanges) {

  var result = dateRanges.reduce((result, current, i, arr) => {
    // console.log(previous, current);

    // get the previous range
    if (i === 0) { return result; }
    var previous = arr[i - 1];

    // Schedule1
    var startTime1 = new Date('1970-01-01T' + previous.StartTime + 'Z');
    var stopTime1 = new Date('1970-01-01T' + previous.StopTime + 'Z');

    // Schedule2
    var startTime2 = new Date('1970-01-01T' + current.StartTime + 'Z');
    var stopTime2 = new Date('1970-01-01T' + current.StopTime + 'Z');

    previous.DaysOfWeek.forEach(function (prevDay) {

      console.log(prevDay);
      current.DaysOfWeek.forEach(function (currDay) {
        console.log(currDay);

        if (prevDay === currDay) {
          var overlap = (startTime1 <= stopTime2) && (stopTime1 >= startTime2);

          // store the result
          if (overlap) {
            // yes, there is overlap
            result.overlap = true;
            // store the specific ranges that overlap
            result.days.push(currDay);
          }
        }
      });
    });

    return result;

    // seed the reduce
  }, { overlap: false, days: [] });

  // return the final results
  console.log(result);
  return result;

}

But it only compares the second array with the first, and the third with the second. It also needs to compare the third with the first. (and if there were 4 schedules, each would need to compare to the other.)

Am I on the right track here, and what can be done to get each DaysOfWeek schedule to compare the StartTime and StopTime with the values in the other schedule?

I created a fake date object using a static day, and I'm only comparing the time values.

I'm open to doing it a completely different way if this is not an efficient way to do it.

infinite number of schedules I'm pretty sure you mean finite. — Keith
– Keith, Commented Jun 11, 2018 at 22:05
I mean infinite because a user can add an infinite number of schedules, and all have to be checked against each other for overlaps. — TetraDev
– TetraDev, Commented Jun 11, 2018 at 22:07
a user can add an infinite number of schedules No they can't. — Keith
– Keith, Commented Jun 11, 2018 at 22:08
In this universe, it is physically impossible for a user to do something an infinite number of times. You probably want something like Compare each element in an array against every other element. You might be able to use moment-range: github.com/rotaready/moment-range/blob/master/README.md — CertainPerformance
– CertainPerformance, Commented Jun 11, 2018 at 22:38
Compare each element in an array against every other element Yes that's correct, I didn't know I was invoking philosophical dilemmas. I updated the title :-D — TetraDev
– TetraDev, Commented Jun 11, 2018 at 23:34

user3297291 · Accepted Answer · 2018-06-12 09:18:54Z

Let's focus on the part of your problem that is about comparing items between multiple arrays. The actual logic of the comparison isn't important for now.

It all starts with a nested for loop:

var arr1 = [ "A", "B", "C" ];
var arr2 = [ "1", "2", "3" ];

// Runs arr1.length * arr2.length = 9 times
for (let i = 0; i < arr1.length; i += 1) {
  for (let j = 0; j < arr2.length; j += 1) {
    console.log(
      "run", i * arr2.length + j, 
      "result", arr1[i], arr2[j]
    );
  }
}

Once you have a function that loops over all pairs of two arrays, what's left to do is to find all possible pairs from a single list of arrays:

const arrays = [ [ "A" ], [ "B" ], [ "C" ] ];

for (let i = 0; i < arrays.length - 1; i += 1) {
//                                ^^^
  for (let j = i + 1; j < arrays.length; j += 1) {
//             ^^^^^
    console.log(
      JSON.stringify(arrays[i]), 
      JSON.stringify(arrays[j])
    );
  }
}

Now that we've got the basics covered, we can chain them together and refactor. I'll have to admit that the refactor is a bit of a personal taste thing, it's perfectly fine to wrap the for loops in functions without the other changes.

I've named the first principle combinations, and used reduce and map instead of the for loops. The second for loop is now contained in allPairs.

// Utilities:
const combinations = ([xs, ys]) => 
  xs.reduce(
    (cs, x) => cs.concat(ys.map(y => [x, y])),
    []
  );
  
const allPairs = (xs) => 
  xs.reduce(
    (ps, x, i) => ps.concat(xs.slice(i + 1).map(y => [x, y])),
    []
  );

const flatten = xxs => xxs.reduce((xs, ys) => xs.concat(ys))

const findMatches = (matchFn, arrays) => flatten(
    allPairs(arrays).map(combinations)).filter(matchFn);

// App:
// Let's just stick to an easy example
const overlap = ([x, y]) => x === y;

console.log(
  findMatches(
    overlap, 
    [ [ 1, 2 ], [ 1, 3 ], [ 1, 2, 3], [ 4, 5 ], [ 1 ] ]
  )
);

This approach returns you pairs of overlapping elements. You'll have to include your own overlaps function. You can gain some efficiency by using find instead of filter, which returns the first overlapping pair. If you really want to return as early as possible, before even constructing all pair combinations, you'll have to move some more stuff around (but I can't imagine the performance will be an issue).

Thank you for the comprehensive answer! You went about approaching it a different way than I did and I can learn from this for the future. I posted an answer below to show what I ended up creating before you posted. I will see what I can incorporate from your answer to make my code better.

TetraDev · Accepted Answer · 2018-06-12 17:29:43Z

I was able to get it working using the following code. It could possibly be improved for efficiency but for small lists, it works great.

 /**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
checkScheduleForOverlap: function (dateRanges) {

  function dateRangeOverlaps (a_start, a_end, b_start, b_end) {
    if (a_start <= b_start && b_start <= a_end) return true; // b starts in a
    if (a_start <= b_end && b_end <= a_end) return true; // b ends in a
    if (b_start < a_start && a_end < b_end) return true; // a in b
    return false;
  }

  function multipleDateRangeOverlaps () {
    var i, j;
    if (arguments.length % 2 !== 0)
      throw new TypeError('Arguments length must be a multiple of 2');
    for (i = 0; i < arguments.length - 2; i += 2) {
      for (j = i + 2; j < arguments.length; j += 2) {
        if (
          dateRangeOverlaps(
            arguments[i], arguments[i + 1],
            arguments[j], arguments[j + 1]
          )
        ) return true;
      }
    }
    return false;
  }

  var result = {
    overlappingDays: [],
    overlap: false
  };

  // for every Schedule
  for (let i = 0; i < dateRanges.length; i++) {
    var current = dateRanges[i];

    // current Schedule
    var startTime1 = current.StartTime;
    var stopTime1 = current.StopTime;

    current.DaysOfWeek.forEach(function (currDay) {

      // console.log('currentScheduleDay', currDay);

      // for every OTHER schedule
      for (let j = 0; j < dateRanges.length; j++) {
        var nextSchedule = dateRanges[j];

        if (j === i) {
          continue;
        }

        nextSchedule.DaysOfWeek.forEach(function (nextDay) {
          // console.log('nextScheduleDay', nextDay);

          if (nextDay === currDay) {

            // next Schedule
            var startTime2 = nextSchedule.StartTime;
            var stopTime2 = nextSchedule.StopTime;

            // var overlap = (startTime1 <= stopTime2) && (stopTime1 >= startTime2);
            var overlap = multipleDateRangeOverlaps(startTime1, stopTime1, startTime2, stopTime2);

            // store the result
            if (overlap) {
              // yes, there is overlap
              result.overlap = true;
              // store the specific ranges that overlap
              result.overlappingDays.push(currDay);
            }

          }
        });
      }

    });
  }

  // remove duplicates in result

  var obj = {};

  for (var i = 0, len = result.overlappingDays.length; i < len; i++) {
    obj[result.overlappingDays[i]] = result.overlappingDays[i];
  }

  result.overlappingDays = new Array();

  for (var key in obj) {
    result.overlappingDays.push(obj[key]);
  }

  if (result.overlappingDays) {
    this.scheduleDaysOverlap = result.overlappingDays;
  }

}

Collectives™ on Stack Overflow

Compare each element in an array against every other element

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related