DEV Community

Daily Challenge #93 - Range Extraction

dev.to staff on October 16, 2019

A format for expressing an ordered list of integers is to use a comma separated list of either: individual integers a range of integers denoted b...

Read full post

erezwanderman • Oct 16 '19

I've challenged myself to come up with another JS solution. Highly functional, with sorting of the output but without the sort function.
Here it comes, including test cases:

  const solution = x =>
    x.reduce(
      (r, vfirst) =>
      [
        ...r.filter(y => y[0] < vfirst),
        ... (x.indexOf(vfirst - 1) === -1 ? [[vfirst, ...x.map(y => [y]).find(([vlast]) => (
          vlast > vfirst &&
          !x.some(v => v == vlast + 1) &&
          x.every(v => v < vfirst || v >= vlast || x.indexOf(v + 1) > -1)
        )) || [] ]] : []),
        ...r.filter(y => y[0] > vfirst)
      ],
      []
    ).map(y => y.slice(-1)[0] - y[0] >= 2 ? y[0] + '-' + y.slice(-1)[0] : y.join()).join();



  console.log(solution([10]))                                                                           // 10
  console.log(solution([10, 10]))                                                                       // 10
  console.log(solution([10, 10, 9]))                                                                    // 9,10
  console.log(solution([12, 11]))                                                                       // 11,12
  console.log(solution([10, 11]))                                                                       // 10,11
  console.log(solution([12, 11, 10]))                                                                   // 10-12
  console.log(solution([9, 10, 11]))                                                                    // 9-11
  console.log(solution([9, 9, 10, 11]))                                                                 // 9-11
  console.log(solution([9, 10, 9, 11]))                                                                 // 9-11
  console.log(solution([10, 11, 12, 14, 15, 16, 17, 17, 9, 13, 8, 6, 5]))                               // 5,6,8-17
  console.log(solution([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]));      // -6,-3-1,3-5,7-11,14,15,17-20
  console.log(solution([6, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]));    // -6,-3-1,3-11,14,15,17-20
  console.log(solution([1, 10, 12, 11, -5]));                                                           // -5, 1, 10, 11, 12

@nobody • Oct 18 '19

lolol, when ES6 looks like Haskell 🤓

La blatte • Oct 16 '19 • Edited

Did anybody ask for some ugly code?

f=a=>(r=[],a.map((e,i)=>i&&!(a[i-1]+1-e)?r.push(r.pop().concat(e)):r.push([e])),r.map(e=>e.length-1?`${e[0]}-${e.pop()}`:''+e))

How does it work? Well it's a oneshot, I didn't take any time before writing it, I guess it should be way easier:

r[]: Initialize the result array
a.map : In this one, a ternary operation is used in order to handle two cases:
- i && !(a[i-1]+1-e) is true : We are not in the first element, and the previous one is equal to "current one minus 1". In this case, with some pop/concat/push, take the last array of the result array and add the current element to it
- i && !(a[i-1]+1-e) is false : Initialize the next element in the result array: an array with the current element ([e])
With the input example, r is equal to this value at this stage: [[-6], [-3, -2, -1, 0, 1], [3, 4, 5], [7, 8, 9, 10, 11], [14, 15], [17, 18, 19, 20]], we need to format it
r.map : In this one, e will be equal to each array. We will need to differentiate array with a length of 1 and the others, as their notation is different (-6 vs 7-11). To do this, we will use another ternary:
- e.length-1 is true : The current element has more than one element, build a string with the first and last element
- e.length-1 is false : The current element has only one element, return a string with the array (''+[-6] will return "-6")

erezwanderman • Oct 16 '19 • Edited

You are grouping groups of 2. You should only be grouping 3 or more consecutive numbers.
Also, you are not sorting the list, so it will fail on unordered lists.

Josh • Oct 17 '19

The problem states that the list will always go in increasing order

erezwanderman • Oct 17 '19

OK, I see now.

erezwanderman • Oct 16 '19

const x = [-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20];
const solve = x => {
  const sorted = x.sort((a, b) => a - b);
  const grouped = sorted.map((x, i, a) => i == a.findIndex((x2, i2) => i2 - x2 == i - x) && a.filter((x2, i2) => i2 - x2 == i - x) || []);
  const ranged = grouped.map(x => x.length > 2 ? x[0] + '-' + x.slice(-1)[0] : x);
  return ranged.flat().join(',');
}
console.log(solve(x));

Of course solve can be re-written as one-liner if you feel the need for that.

Anders • Oct 18 '19

This is my take on this one, longer code, hopefully easy to read...

function Solution(a) {

    var AddSequenceToString = function (seq, s) {

        if (s) { s += ', '; }
        s += (seq.length >= 3)? seq[0] + '-' + seq[seq.length - 1] : seq.join(', ');
        return s;
    }

    var sequence = [];
    var s = '';

    for (var i = 0; i < a.length; ++i) {

        var n = a[i];

        if (sequence.length == 0 || sequence[sequence.length - 1] == n - 1) { 

            sequence.push(n);

        } else {

            s = AddSequenceToString(sequence, s);
            sequence = [n];
        }
    }

    s = AddSequenceToString(sequence, s);

    return s;
}

And since I am a sucker for benchmarking, I compared it (Chrome 77, Win10) with the other solutions posted so far, 10 000 runs, average of 5 tests with the sample test data:

154 ms for erwzwanderman (first)
59 ms for erwzwanderman (second)
57 ms for La blatte
11 ms for Anders

(NOTE: I added a .join() to La blattes solution as it returns an array, not a string)

Yasar • Mar 26 '21

Hi,
It's possible also for [number, string] with combination of delimiters ?
I get with order of input only
Input => solution([1.1,1.2,1.3,1.5]);
Output=> 1.1,1.2,1.3,1.5
Ex. Output=> 1.1-1.3,1.5

Examples are given below:
Case 1 ==> [1.1, 1.2, 1.3, 1.4, 1.5]
Case 2 ==> [1-1, 1-2, 1-3, 1-4, 1-5]
Case 3 ==> [1-1.1, 1-1.2, 1-1.3, 1-2.1, 1-3.1]

Zohar Peled • Oct 16 '19

Gaps and islands. I've done something similar in sql once, hope I can find that SO post tomorrow.

Zohar Peled • Oct 17 '19

Well, I did find that SO post - had to change the solution a bit for the "group must contain more than two members" rule, but that was easy enough - So here's a pure T-SQL solution.

First, table setup:

DECLARE @T AS TABLE
(
    N int
);

INSERT INTO @T VALUES
(-6), 
(-3), (-2), (-1), (0), (1), 
(3), (4), (5), 
(7), (8), (9), (10), (11), 
(14), 
(15), 
(17), (18), (19), (20);

Then, a cte to group the consecutive values together:

With Grouped AS
(
    SELECT N,
           N - DENSE_RANK() OVER(ORDER BY N) As Grp
    FROM @T
)

And finally query that cte:

SELECT STUFF(
(
    SELECT ',' + 
            CASE 
            WHEN COUNT(N) > 2 THEN
               CAST(MIN(N) as varchar(11)) +'-' + CAST(MAX(N) as varchar(11)) 
            WHEN COUNT (N) = 2 THEN
                CAST(MIN(N) as varchar(11)) +',' + CAST(MAX(N) as varchar(11)) 
            ELSE
                CAST(MIN(N) as varchar(11))
            END
    FROM Grouped   
    GROUP BY grp
    FOR XML PATH('')
), 1, 1, '')  As GapsAndIslands

Try it online!