Skip to content

Instantly share code, notes, and snippets.

@chasingmaxwell
Last active May 19, 2020 22:40
Show Gist options
  • Save chasingmaxwell/b183f55c6282e5fb90247151a3f098f2 to your computer and use it in GitHub Desktop.
Save chasingmaxwell/b183f55c6282e5fb90247151a3f098f2 to your computer and use it in GitHub Desktop.
Prompt for Four Kitchens JavaScript Practice Group 2020.05.20
/* @flow */
export type Range<P> = {
payload: P,
start: number,
end: number,
priority: number,
};
/**
* Given a set of ranges, remove any overlapping ranges giving preference to
* those with a higher priority value.
*
* NOTE: ranges with invalid start/end values (start > end) are filtered out.
*
* @param ranges An array of ranges with the following properties:
* @param ranges[].start The lower bound of the range.
* @param ranges[].end The upper bound of the range.
* @param ranges[].payload The value associated with the range. This prevents
* the payload from requiring the properties start, end, and priority.
* @param ranges[].priority The numeric value which determines which overlapping
* range will be given preference. Ranges with higher priority values are
* preferred over those with lower priority values.
*/
module.exports = function removeOverlap<P>(
ranges: Array<Range<P>>
): Array<Range<P>> {
return ranges;
};
const removeOverlap = require('./removeOverlap');
describe('removeOverlap', () => {
it('removes exactly overlapping ranges', () => {
expect(
removeOverlap([
{ payload: 'one', start: 1, end: 3, priority: 1 },
{ payload: 'two', start: 1, end: 3, priority: 2 },
])
).toEqual([{ payload: 'two', start: 1, end: 3, priority: 2 }]);
});
it('removes a range extending the lower bound of another range', () => {
expect(
removeOverlap([
{ payload: 'one', start: 0, end: 3, priority: 1 },
{ payload: 'two', start: 1, end: 4, priority: 2 },
])
).toEqual([{ payload: 'two', start: 1, end: 4, priority: 2 }]);
});
it('removes a range extending the upper bound of another range', () => {
expect(
removeOverlap([
{ payload: 'two', start: 0, end: 3, priority: 2 },
{ payload: 'one', start: 1, end: 4, priority: 1 },
])
).toEqual([{ payload: 'two', start: 0, end: 3, priority: 2 }]);
});
it('removes more than two overlapping ranges', () => {
expect(
removeOverlap([
{ payload: 'one', start: 1, end: 3, priority: 1 },
{ payload: 'three', start: 1, end: 3, priority: 3 },
{ payload: 'two', start: 1, end: 3, priority: 2 },
])
).toEqual([{ payload: 'three', start: 1, end: 3, priority: 3 }]);
});
it('removes a range containing another range', () => {
expect(
removeOverlap([
{ payload: 'two', start: 1, end: 3, priority: 2 },
{ payload: 'one', start: 0, end: 4, priority: 1 },
])
).toEqual([{ payload: 'two', start: 1, end: 3, priority: 2 }]);
});
it('removes a range contained in another range', () => {
expect(
removeOverlap([
{ payload: 'one', start: 1, end: 3, priority: 1 },
{ payload: 'two', start: 0, end: 4, priority: 2 },
])
).toEqual([{ payload: 'two', start: 0, end: 4, priority: 2 }]);
});
it('removes multiple groups of overlapping ranges', () => {
expect(
removeOverlap([
{ payload: 'one', start: 0, end: 3, priority: 1 },
// overlapping
{ payload: 'eight', start: 3, end: 6, priority: 8 },
{ payload: 'two', start: 3, end: 7, priority: 2 },
{ payload: 'three', start: 7, end: 8, priority: 3 },
// overlapping
{ payload: 'seven', start: 9, end: 11, priority: 7 },
{ payload: 'six', start: 10, end: 14, priority: 6 },
{ payload: 'five', start: 11, end: 13, priority: 5 },
{ payload: 'nine', start: 15, end: 16, priority: 9 },
// overlapping
{ payload: 'four', start: 17, end: 18, priority: 4 },
{ payload: 'ten', start: 17, end: 20, priority: 10 },
])
).toEqual([
{ payload: 'one', start: 0, end: 3, priority: 1 },
{ payload: 'eight', start: 3, end: 6, priority: 8 },
{ payload: 'three', start: 7, end: 8, priority: 3 },
{ payload: 'seven', start: 9, end: 11, priority: 7 },
{ payload: 'five', start: 11, end: 13, priority: 5 },
{ payload: 'nine', start: 15, end: 16, priority: 9 },
{ payload: 'ten', start: 17, end: 20, priority: 10 },
]);
});
it('removes all the different kinds of overlapping ranges all at once', () => {
expect(
removeOverlap([
{ payload: 'in', start: 0, end: 1, priority: 1 },
{ payload: 'out', start: 0, end: 9, priority: 4 },
{ payload: 'in', start: 1, end: 2, priority: 1 },
{ payload: 'in', start: 2, end: 3, priority: 1 },
{ payload: 'out', start: 2, end: 5, priority: 6 },
{ payload: 'out', start: 2, end: 6, priority: 7 },
{ payload: 'priority', start: 3, end: 6, priority: 10 },
{ payload: 'out', start: 3, end: 6, priority: 3 },
{ payload: 'out', start: 3, end: 7, priority: 9 },
{ payload: 'out', start: 4, end: 7, priority: 8 },
{ payload: 'out', start: 4, end: 5, priority: 5 },
{ payload: 'in', start: 6, end: 7, priority: 2 },
{ payload: 'in', start: 7, end: 9, priority: 0 },
])
).toEqual([
{ payload: 'priority', start: 3, end: 6, priority: 10 },
{ payload: 'in', start: 6, end: 7, priority: 2 },
{ payload: 'in', start: 0, end: 1, priority: 1 },
{ payload: 'in', start: 1, end: 2, priority: 1 },
{ payload: 'in', start: 2, end: 3, priority: 1 },
{ payload: 'in', start: 7, end: 9, priority: 0 },
]);
});
it('When there are collisions in priority, return the range with the lowest start', () => {
expect(
removeOverlap([
{ payload: 'out', start: 5, end: 7, priority: 2 },
{ payload: 'out', start: 6, end: 8, priority: 2 },
{ payload: 'in', start: 4, end: 9, priority: 2 },
])
).toEqual([{ payload: 'in', start: 4, end: 9, priority: 2 }]);
});
it('filters out a range overlapping two other ranges in both lower/upper bounds', () => {
expect(
removeOverlap([
{ payload: 'in', start: 5, end: 7, priority: 4 },
{ payload: 'out', start: 6, end: 9, priority: 1 },
{ payload: 'in', start: 8, end: 9, priority: 2 },
])
).toEqual([
{ payload: 'in', start: 5, end: 7, priority: 4 },
{ payload: 'in', start: 8, end: 9, priority: 2 },
]);
});
it('filters out ranges with invalid start/end values', () => {
expect(
removeOverlap([
{ payload: 'in', start: 0, end: 5, priority: 1 },
{ payload: 'out', start: 2, end: 1, priority: 2 },
])
).toEqual([{ payload: 'in', start: 0, end: 5, priority: 1 }]);
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment