Best search algorithm for longest nights - Javascript

I would suggest using a loop over the days, and on each iteration, identify the room with the longest consecutive openings starting from the current day; then, increment the days by that number of days.

To make parsing easier, you can pre-process the data so that the availability info is available in an object indexed by a number date index - for example, turn

availability: [
  { roomId: 105, date: '2018-01-01' },
  { roomId: 105, date: '2018-01-02' },
  { roomId: 105, date: '2018-01-04' },
  { roomId: 105, date: '2018-01-06' }
]

into

'105': {
  1: true,
  2: true,
  4: true,
  6: true
}

That way, to figure out how long room X will be available from day N, simply repeat a test of rooms[x][n] === true and increment n until the test fails.

If this was being done multiple times (starting from the same dataset of rooms), you could do all the real calculations once, in advance, and construct an object containing the best rooms to choose for each day, for example:

{ // keys represent day index
  1: { roomId: 101, availableUntil: 3 },
  2: { roomId: 101, availableUntil: 3 }, // just as good as room 103
  3: { roomId: 101, availableUntil: 3 }, // just as good as 103 and 102
  // room 101 not available on Jan 4, room 104 becomes the best room to choose:
  4: { roomId: 104, availableUntil: 6 },
  5: { roomId: 104, availableUntil: 6 },
  6: { roomId: 104, availableUntil: 6 } // just as good as 105
}

Then, given an input of the days one wants to stay, calculating the least disruptive room changes is a simple matter of property lookup until the end day is reached.

To simplify the readability of the following code, I'll use a helper function

const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

so that indicies start at 1 and go to 6, to test your input, but in your real code, you would of course instead use something robust that calculates the number of days between the dateStr and some date, such as Jan 1 1970, or something like that. (or, feel free to use the moment(toDate).diff(moment(fromDate), 'days') that you're currently using if that works for you)

Now, the code: First transform the dataset into an object that looks like:

/*
{
  101: {
    1: true,
    2: true,
    3: true,
    5: true,
    6: true,
  },
  102:
  // ...
}
*/
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

Then, the main getBestRoomFromDay function, that takes a day index and searches through every room object in datasetByRoom, for the one with the most consecutive openings starting from the current day:

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

In action, an example of calling getBestRoomFromDay for each dayIndex in the input (1-6):

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}}

console.log('Example of testing getBestRoomFromDay function on all days:');
for (let i = 1; i < 7; i++) {
  console.log('Day ' + i + ': ' + JSON.stringify(getBestRoomFromDay(i)));
}

Then, to construct a schedule from a from and to date string, such as '2018-01-01' to '2018-01-06', just repeatedly call getBestRoomFromDay with the appropriate day, incrementing the day index the required amount on each iteration:

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}};

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

In full, unminified:

const dataset = [
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
];
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

As mentioned previously, if you had to calculate multiple getBestRoomFromDays from the same dataset (that is, without insertion of the new reservation), you could construct an object in advance that contains the getBestRoomFromDay for every possible value it could be called with, thus ensuring that every day calculation will only ever be done once.

Yes, there is a simpler way to do this:

1. Collapse your availability information into a list of intervals of continuous availability like [{start:1, end:3, room: "101"}, {start ...etc...
2. Sort the intervals by start day, and reverse the list so you can pop them off in order (faster than shifting)
3. Initialize your "need_room" to day 1
4. while your "need_room" day, is less than the last day of your stay:
   1. Pop off all intervals with start day <= your need_room day, and remember the one with the latest end day. If that latest end day is < need_room day, then there is no solution.
   2. Add the room with the latest end day to your output. If it goes all the way to the end of your stay, then you're done.
   3. Otherwise, your new "need_room" day is the one after then end day of the room.

The search idea that I have is by using non-available-night indexes:

If we map through the availability and get the available night indexes, we will have something like this:

const availableIndexes = [
  [0, 1, 2, 4, 5],
  [0, 2, 3, 4],
  [1, 2, 5],
  [3, 4, 5],
  [0, 1, 3, 5]
]

Then we can have the non-available nights indexes like this:

const notAvailableIndexes = [
  [3],
  [1, 5],
  [0, 3, 4],
  [1, 2, 3],
  [2, 4]
]

So this is the algorithm:

Find the largest number (means the longest night)

step1 = [
  [3], // select this as this has the biggest number
  [1, 5],
  [0, 3, 4],
  [1, 2, 3],
  [2, 4]
]

Remove the indexes afterward

// after each step, remove the indexes

Repeat the same until the end

step2 = [
  [], // not using this, as it was selected from the previous step
  [5],
  [4],
  [], // select this as this has all the availability until the end of the stay period
  [4]
]

Below is the rough implementation in Javascript based on the idea above (not tested/run before):

const rooms = [
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
];

const fromDate = '2018-01-01';
const toDate = '2018-01-06';
const totalNights = moment(toDate).diff(moment(fromDate), 'days');

// Get all the not available nights index for each room
const notAvail = rooms.map(room => {
  let array = [];
  Array.from(Array(totalNights)).forEach((null, index) => {
    const date = moment(fromDate).clone().add(index, 'days').format('YYYY-MM-DD');
    // if available
    if (room.availability.find(av => av.date === date)) {
      array.push(null);
    }
    // if that night is not available, push the index
    else {
      array.push(index);
    }
  });
  // return clean array without null values
  return array.filter(Boolean);
})

/**
  we should get this array:
    const notAvail = [
      [3],
      [1, 5],
      [0, 3, 4],
      [1, 2, 3],
      [2, 4]
    ]
**/

const stack = [];
let currentNight = 0;
let tempUnavailIndex = null;

// keep searching until it reaches the end of the stay period
do {
  let roomId = null;
  let longestCount = 0;

  // Get the longest night
  notAvail.forEach((arr, index) => {
    if (index !== tempUnavailIndex) {
      const firstIndex = arr[0];
      // If the night is available
      if (currentNight !== firstIndex) {
        // if it is available until the end of the stay (empty array) 
        if (!arr[0]) {
          roomId = rooms[index].roomId;
          longestCount = totalNights - currentNight;
        }
        // else if it the longest nights
        else if (arr[0] > longestCount) {
          roomId = rooms[index].roomId;
          longestCount = arr[0];
        }
      }
    }
  });

  // If there is a day where no rooms are available, throw an error
  if (roomId === null) {
    throw new Error('No room available for the period of stay!');
  }

  // Set the room to be unavailable for next search
  tempUnavailIndex = roomId;

  // Push each night into the stack
  Array.from(Array(longestCount)).forEach(() => {
    // Push the object into the stack
    stack.push({
      roomId,
      date: moment(fromDate).clone().add(currentNight, 'day')
    });
    // Increment the night
    currentNight += 1;
  });

  // Remove the current search indexes from the notAvail array
  notAvail.map(arr => arr.filter(index => index > currentNight));
}
while (currentNight !== totalNights)

I think there should be a better way to do this