7
\$\begingroup\$

Problem Explained:

Imagine there is a list of running results of 1000m, like following:

[
    { id: 1, date: '2017-01-01 00:00:00', duration: 195 },
    { id: 2, date: '2017-01-10 00:00:00', duration: 270 },
    { id: 3, date: '2017-03-12 00:00:00', duration: 220 },
    { id: 4, date: '2018-01-10 00:00:00', duration: 218 },
    { id: 5, date: '2018-02-23 00:00:00', duration: 220 },
    { id: 6, date: '2018-05-18 00:00:00', duration: 215 }
]

I'd like to find out the fastest run of each year, which will be

[
    { id: 1, date: '2017-01-01 00:00:00', duration: 195 },
    { id: 6, date: '2018-05-18 00:00:00', duration: 215 }
]

Here's my ugly solution (TypeScript):

const items = JSON.parse('Use the JSON above.');
const results: any[] = [];
const fastestOfEachYear: object = {};
const idsOfFastestEachYear: object = {};

// Go through the list to find the fastest of each year.
// Save the IDs in an object.
items.forEach((item) => {
    const runId = item['id'];
    const date = item['date'];
    const dateParts = date.split('-');
    const year = new Date(dateParts[0], dateParts[1] - 1, dateParts[2]).getFullYear();
    const duration = item['duration'];

    // Found a faster one, update our objects with the new item.
    if (fastestOfEachYear[year] == null || fastestOfEachYear[year] > duration) {
        fastestOfEachYear[year] = duration;
        idsOfFastestEachYear[year] = runId;
    }
});

// Retrieve the IDs of the runs that are the fastest of a year.
const idsOfFastest = Object.keys(idsOfFastestEachYear).map((key) => idsOfFastestEachYear[key]);

// Loop through the list again to find those items matching the IDs
// Save them to results.
items.forEach((item) => {
    const runId = item['id'];
    if ($.inArray(runId, idsOfFastest) !== -1) {
        results.push(item);
    }
});

Surely there are nicer and better ways of achieving this? (Reviews in TypeScript, ES6 or even just Vanilla JS are ok.)

\$\endgroup\$
  • \$\begingroup\$ Are you interested in solutions using lodash/underscore or similar? It's so much easier with good abstractions at hand. \$\endgroup\$ – tokland Jun 10 '18 at 18:35
  • \$\begingroup\$ @tokland: Yes, I thought about using some handy methods from lodash, but I struggled to introduce lodash into my Rails + webpacker + TypeScript project. But yes, a lodash solution would be acceptable too! \$\endgroup\$ – Yi Zeng Jun 11 '18 at 2:37
6
\$\begingroup\$

First solution using .forEach, for...in and .sort

Here what I did to achieve this:

  1. First sort your array of objects, i.e convert:

    data = [ {...}, {...}, {...}, {...}, {...}, {...} ]
    

    into an object sorted by year:

    sortedY = { 2017: [{...}, {...}, {...}], 2018: [{...}, {...}, {...}] }
    

    You can achieve such result by using a forEach loop:

    const sortedY = {};
    data.forEach(e => {
        const year = e.date.split('-')[0];
        sortedY[year] = sortedY[year] || [];
        sortedY[year].push(e);
    });
    
  2. Then we will need to sort each object [{...}, {...}, {...}] per year by duration. sorted is not an array. We can't use map unfortunately: use a for...in loop instead. However to sort each key/value (<=> year/array of results for this year) we can use one of Array's methods: sort, the sorting criteria is the following:

    (a,b) => a.duration > b.duration
    

    Where a and b are two different races from the same year.

    So with:

    sortedY[year].sort((a,b) => a.duration > b.duration)
    

    You get an array of sorted races for the year year.

    The last thing to do is saving the first of the sorted array (the first is the one with the shortest duration, so select it with [0] and add it to result:

    result[year] = sortedY[year].sort((a,b) => a.duration > b.duration)[0]
    

The final code is:

const sortedY = {};
data.forEach(e => {
    const year = e.date.split('-')[0];
    sortedY[year] = sortedY[year] || [];
    sortedY[year].push(e);
});

const result = {};
for(year in sortedY) {
   result[year] = sortedY[year].sort((a,b) => a.duration > b.duration)[0];
}

console.log(result);
<script>
const data = [ { id: 1, date: '2017-01-01 00:00:00', duration: 195 }, { id: 2, date: '2017-01-10 00:00:00', duration: 270 }, { id: 3, date: '2017-03-12 00:00:00', duration: 220 }, { id: 4, date: '2018-01-10 00:00:00', duration: 218 }, { id: 5, date: '2018-02-23 00:00:00', duration: 220 }, { id: 6, date: '2018-05-18 00:00:00', duration: 215 } ]
</script>


Second solution using only .forEach

I realised there was a quicker way of doing this: we don't need to loop over the array data twice! One loop will suffice. Indeed, we'll fill result as we navigate through data only replacing a yearly race if a race is shorter in duration.

So a race will be added to result[year] only if:

!result[year] || (result[year] && e.duration < result[year].duration)

is true, i.e. if either:

  • there is no race registered for the year year

  • there is one but its duration is longer than the one that we're checking

So the code is shorter, simpler and I bet it will be quicker: its complexity is \$O(n)\$. The previous code was cool but not so much efficient. I was looping twice the data: first time for the sorting, second on the sorted array. Not even mentioning that I was using sort...

let result = {};
data.forEach(e => {
  const year = e.date.split('-')[0];
  if( !result[year] || (result[year] && e.duration < result[year].duration) ) {
    result[year] = e;
  }
})

console.log(result);
<script>
const data = [ { id: 1, date: '2017-01-01 00:00:00', duration: 195 }, { id: 2, date: '2017-01-10 00:00:00', duration: 270 }, { id: 3, date: '2017-03-12 00:00:00', duration: 220 }, { id: 4, date: '2018-01-10 00:00:00', duration: 218 }, { id: 5, date: '2018-02-23 00:00:00', duration: 220 }, { id: 6, date: '2018-05-18 00:00:00', duration: 215 } ]
</script>

\$\endgroup\$
  • 2
    \$\begingroup\$ Very elegant solution. Thanks! I'll accept once I've got a chance to try it out. \$\endgroup\$ – Yi Zeng Jun 11 '18 at 7:26
3
\$\begingroup\$

@Ivan has said enough already, so I'll allow myself to include only code that will give you exactly the same output that you expected in your question.

It works just like @Ivan's second solution, except that it uses .reduce() and gives you only values of the same resultant object as his, which is what you were looking for. \$O(n)\$ complexity.

const getFastestRuns = input => Object.values(input.reduce((acc, curr) => {
  const year = curr.date.substring(0, 4);
  if (!acc[year] || (curr.duration < acc[year].duration)) {
    acc[year] = curr;
  }
  return acc;
}, {}));

/* DEMO */

const input = [
  { id: 1, date: '2017-01-01 00:00:00', duration: 195 },
  { id: 2, date: '2017-01-10 00:00:00', duration: 270 },
  { id: 3, date: '2017-03-12 00:00:00', duration: 220 },
  { id: 4, date: '2018-01-10 00:00:00', duration: 218 },
  { id: 5, date: '2018-02-23 00:00:00', duration: 220 },
  { id: 6, date: '2018-05-18 00:00:00', duration: 215 }
];

console.log(
  JSON.stringify(
    getFastestRuns(input)
  )
);

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, I tried using only .reduce in my second attempt but failed. I didn't know the method could take initialValue as [the second argument]. Thanks for sharing +1. \$\endgroup\$ – Ivan Jun 11 '18 at 12:28
1
\$\begingroup\$

The problem is that you are kind of re-implenting abstractions (groupBy, min, ...) found in utility libraries like lodash, underscore, ramda... So my advice would be to just use one of these and write declarative/functional code. Something like this:

const _ = require('lodash');
const getYear = run => parseInt(run.date.split("-")[0]);
const fastestRunByYear = _(runs)
  .groupBy(getYear)
  .map(runsForYear => _.minBy(runsForYear, "duration"))
  .value();

If not using external libraries was a requirement, for whatever reason, then I'd implement groupBy and minBy as a separate functions and use the same code above (without _ wrappings, of course). Note that I could move the getYearcode into the map, but I create a separate function to make it more clear.

\$\endgroup\$
  • \$\begingroup\$ Thanks! Yes, now I have Lodash in my project. \$\endgroup\$ – Yi Zeng Jun 14 '18 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.