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 [e-mail] with your suggestions!

Comments

[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

[@nobody]

lolol, when ES6 looks like Haskell 🤓

[La blatte]

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]

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]

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

[erezwanderman]

OK, I see now.

[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.

[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)

[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]

[Zohar Peled]

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

[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);

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!