A collection of closest values from two arrays

Question

I'm looking for optimization of an algorithm to solve a simple problem which may be hard to explain. I'm not looking for a speed or performance but simplicity and clarity when you read the code. Maybe someone has more clever solution than mine. I imagine one-liner would probably be an overkill.

I have two collections of cells ordered by date. Each of the cell can have a price value. We can assume that there can't be a price in two cells for the same date. I want to have one collection of dates, but where is no price for the date:

• which collection have a closest price from the past
• if there is no price in the past, look in the future

Here's what I have so far (it gives accurate results):

const array1 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12' },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15', price: 10 },
  { date: '2019-11-16' },
];

const array2 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12', price: 10 },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15' },
  { date: '2019-11-16' },
];

const merged = Object.values(array1).map((element, index) => {
  let filled;
  if (element.price) {
    filled = 1;
  }
  if (array2[index].price) {
    filled = 2;
  }
  if (filled) {
    return {
      date: element.date,
      filled
    }
  } else {
    return {
      date: element.date
    }
  }
});

const first = merged.find(element => element.filled);

let currentFill = first && first.filled;

const emptyMap = merged.map((element, index, array) => {
  if (!element.filled) {
    return {
      date: element.date,
      empty: currentFill
    }
  }
  currentFill = element.filled;
  return element;
})

console.log(emptyMap);

Answer 1

const array1 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12' },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15', price: 10 },
  { date: '2019-11-16' },
];

const array2 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12', price: 10 },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15' },
  { date: '2019-11-16' },
];

function collect(collection1, collection2) {
  let firstEmptyId = null
  let currentId = null
  let indexes = [/* [1] optimization */]
  let collection = collection1.map(({ date, price }, i) => (
    ((price && (currentId = 1)) || (collection2[i].price && (currentId = 2)))
      ? ((firstEmptyId || (firstEmptyId = currentId)), { date, filled: currentId })
      : ((firstEmptyId || /*see[1]*/ indexes.push(i)), { date, empty: currentId })
  ))
  // only two iterations => index.length === 2
  indexes.forEach((i) => (collection[i].empty = firstEmptyId))
  return collection
}

console.log(collect(array1, array2))

Answer 2

To my understanding, what will probably make the code most difficult to read is the last statement: "if there is no price in the past, look in the future".

This requirement means that instead of going forward only through the collections and only applying values from previously handled elements where necessary, you have to also look ahead until something happens.

For greatest simplicity, I recommend to go once from front to back, ignoring the "look ahead" part, and then, in the resulting collection, go once from back to front copying the last reached (i. e. earliest) filled element to the ones in front:

const array1 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12' },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15', price: 10 },
  { date: '2019-11-16' },
]

const array2 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12', price: 10 },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15' },
  { date: '2019-11-16' },
]

const length = array1.length
const result = new Array(length)
let emptySource = undefined

// First run: from earlier to more recent
// Applies value for "empty" when price was available once
for (let i = 0; i < length; ++i) {
  let e1 = array1[i]
  let e2 = array2[i]
  const date = e1.date
  if (e1.price) {
    result[i] = {
      'date': date,
      'filled': 1
    }
    emptySource = 1
  } else if (e2.price) {
    result[i] = {
      'date': date,
      'filled': 2
    }
    emptySource = 2
  } else {
    result[i] = {
      'date': date,
      'empty': emptySource
    }
  }
}

// Second run: from more recent to earlier
// Finds the earliest element ever "filled",
// then applies its value to all still unset "empty" elements
// (which necessarily all have a lower index)
for (let i = length - 1; i >= 0; --i) {
  const e = result[i]
  if (e.filled) {
    emptySource = e.filled
  } else if (e.empty === undefined) {
    e.empty = emptySource
  }
}

console.log(result)

Answer 3

Here's my spin on this:

const array1 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12' },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15', price: 10 },
  { date: '2019-11-16' },
];

const array2 = [
  { date: '2019-11-10' },
  { date: '2019-11-11' },
  { date: '2019-11-12', price: 10 },
  { date: '2019-11-13' },
  { date: '2019-11-14' },
  { date: '2019-11-15' },
  { date: '2019-11-16' },
];

const mappedToCollection = array1.map((el, i) => ({
  date: el.date,
  //You can just as easily store the actual collection here and not just a number
  collection: (el.price && 1) ||
    (array2[i].price && 2) ||
    undefined,
}));

const firstExactMatch = mappedToCollection.find(el => el.collection);

const closestCollections = mappedToCollection.reduce((acc, el, i) => [
  ...acc,
  {
    date: el.date,
    collection: el.collection ||
      (acc[i-1] && acc[i-1].collection) ||
      (firstExactMatch && firstExactMatch.collection),
    exactMatch: !!el.collection,
  },
], []);

console.log(closestCollections);

As stated in the question, not the most performant or short solution, but tried to make it readable and explicit.