loading...

Daily Challenge #93 - Range Extraction

thepracticaldev profile image dev.to staff ・1 min read

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!

Posted on by:

thepracticaldev profile

dev.to staff

@thepracticaldev

The hardworking team behind dev.to ❤️

Discussion

pic
Editor guide
 

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
 

lolol, when ES6 looks like Haskell 🤓

 

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

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.

 

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

 

Let's do Ruby today:

def solution(input)
  input
    .chunk_while { |i, j| i + 1 == j }
    .flat_map do |a|
      case a.size
      when 1 then a.first.to_s
      when 2 then [a.first.to_s, a.last.to_s]
      else "#{a.first}-#{a.last}"
      end
    end
end

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"]
 
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.

 

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)

 

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

 

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!