DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #93 - Range Extraction

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 by the starting integer separated from the end integer in the range by a dash, -.
  • the range includes all integers in the interval including both endpoints. It is not considered a range unless it spans at least 3 numbers. For example 12, 13, 15-17

Complete the solution so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format.

Example:

solution([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])

returns (-6,-3-1,3-5,7-11,14,15,17-20)


This challenge comes from jhoffner on CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (12)

Collapse
 
erezwanderman profile image
erezwanderman

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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
not_jffrydsr profile image
@nobody

lolol, when ES6 looks like Haskell 🤓

Collapse
 
ynndvn profile image
La blatte • 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")
Collapse
 
erezwanderman profile image
erezwanderman • 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.

Collapse
 
thepeoplesbourgeois profile image
Josh

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

Thread Thread
 
erezwanderman profile image
erezwanderman

OK, I see now.

Collapse
 
erezwanderman profile image
erezwanderman
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.

Collapse
 
anders profile image
Anders

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)

Collapse
 
yasar2385 profile image
Yasar

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]

Collapse
 
peledzohar profile image
Zohar Peled

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

Collapse
 
peledzohar profile image
Zohar Peled

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);
Enter fullscreen mode Exit fullscreen mode

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
)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Try it online!