Determine ranges from a list of values

Question

Given an unsorted list of unique, positive integers, output the shortest list of the longest possible ranges of sequential integers.

INPUT

• An unsorted list of unique, positive integers
  • e.g. 9 13 3 11 8 4 10 15
• Input can be taken from any one of the following:
  • stdin
  • command-line arguments
  • function arguments

OUTPUT

• An ordered list of ranges or individual values printed on one line to stdout or your language's closest similar output.
  • If two or more sequential integers (sequential by value, not by location in the list) are present, they will be denoted as an inclusive range using -, e.g. 8-11
  • All other integers are simply printed with no other notation
  • A single space will delimit the output
• Numbers not present in the input should not be in the output, e.g. 3 5 6 cannot be shortened to 3-6 because 4 is not present

EXAMPLES

Successful:

 IN> 9 13 3 11 8 4 10 15 6
OUT> 3-4 6 8-11 13 15

 IN> 11 10 6 9 13 8 3 4 15
OUT> 3-4 6 8-11 13 15

 IN> 5 8 3 2 6 4 7 1
OUT> 1-8

 IN> 5 3 7 1 9
OUT> 1 3 5 7 9

Wrong:

 IN> 9 13 3 11 8 4 10 15
OUT> 3-15

Range contains values not in the input

 IN> 9 13 3 11 8 4 10 15
OUT> 3 4 8 9 10 11 13 15

All sequential values should be represented as a range

 IN> 9 13 3 11 8 4 10 15
OUT> 3-4 8-9 10-11 13 15

Divided range, 8-9 and 10-11 should be 8-11

 IN> 9 13 3 11 8 4 10 15
OUT> 8-9 13 10-11 3-4 15

Output not ordered correctly

RULES

• Standard loopholes are disallowed
• If your language has a function to do this it's not allowed
• You may write a full program, or a function
• trailing whitespace doesn't matter

SCORING

• Least bytes wins

Answer 1

Python 2, 123 120 bytes

N=sorted(map(int,raw_input().split(' ')));print(''.join((''if n+1in N else'-'+`n`)if n-1in N else' '+`n`for n in N)[1:])

If the input can be a list as a function argument then (thanks mbomb007 and xnor for the conditionals)

93 90 81 bytes

def f(N):print''.join((' '+`n`,`-n`*-~-(n+1in N))[n-1in N]for n in sorted(N))[1:]

(77 bytes if leading whitespace is acceptable - drop the final [1:])

Answer 2

JavaScript (ES6): 171 154 140 137 bytes

Thanks edc65 and vihan1086 for the tips! [...n] is very nice but it doesn't work in these cases due to multi-digit numbers.

f=n=>{s=e=o='';n.split` `.map(Number).sort((a,b)=>a-b).map(v=>{s=s||v;if(e&&v>e+1){o+=`${s<e?s+'-'+e:s} `;s=v}e=v});return o+(s<e?s+'-'+e:e)}

ES5 variant, 198 184 183 174 bytes

f=function(n){s=e=o='';n.split(' ').map(Number).sort(function(a,b){return a-b}).map(function(v){s=s||v;if(e&&v>e+1){o+=(s<e?s+'-'+e:s)+' ';s=v}e=v});return o+(s<e?s+'-'+e:e)}

f = function (n) {
    s = e = 0, o = '';
    n.split(' ').map(Number).sort(function (a, b) {
        return a - b
    }).map(function (v) {
        s = s || v;
        if (e && v > e + 1) {
            o += (s < e ? s + '-' + e : s) + ' ';
            s = v
        }
        e = v
    });
    return o + (s < e ? s + '-' + e : e)
}

// Demonstration
document.body.innerHTML = f('1 2');
document.body.innerHTML += '<p>' + f('9 13 3 11 8 4 10 15 6');
document.body.innerHTML += '<p>' + f('11 10 6 9 13 8 3 4 15');
document.body.innerHTML += '<p>' + f('5 8 3 2 6 4 7 1');
document.body.innerHTML += '<p>' + f('5 3 7 1 9');

Answer 3

Ruby, 70 bytes

Problems like these tend to make me check the Ruby API for suitable methods, and today I discovered a new one: Array#slice_when, newly introduced in Ruby v2.2 and seemingly intended for this exact situation :)

f=->a{puts a.sort.slice_when{|i,j|j-i>1}.map{|x|x.minmax.uniq*?-}*' '}

After sorting and appropriately slicing the array, it takes each sub-array and creates a string out of the highest and lowest element, and then joins this whole array into a string.

Example:

f.call [9,13,3,11,8,4,10,15,6] prints 3-4 6 8-11 13 15

Answer 4

SWI-Prolog, 165 162 159 bytes

b(Z,C,[D|E]):-Z=[A|B],(A=:=D+1,(B=[],put(45),print(A);b(B,C,[A,D|E]));(E=[],tab(1),print(A);writef('-%t %t',[D,A])),b(B,A,[A]));!.
a(A):-sort(A,B),b(B,_,[-1]).

Pretty bad but then again Prolog is a terrible golfing language

Example: a([9,13,3,11,8,4,10,15,6]). outputs 3-4 6 8-11 13 15

Answer 5

Ruby, 86 84 bytes

s=->*a{puts a.sort.slice_when{|i,j|i+1!=j}.map{|e|e.size<2?e:[e[0],e[-1]]*"-"}*" "}

# demo
s[9, 13, 3, 11, 8, 4, 10, 15, 6]
# => 3-4 6 8-11 13 15

This is a slightly golfed version from an example in the docs for slice_when.

Answer 6

CJam, 35 bytes

l~${__0=f-ee::=0+0#/((oW>Wf*S+oe_}h

Try it online in the CJam interpreter.

How it works

l~$     e# Read a line from STDIN, evaluate it and sort the result.
{       e# Do:
  _     e#   Push a copy of the array.
  _0=f- e#   Subtract the first element from all array elements.
  ee    e#   Enumerate the differences: [0 1 4] -> [[0 0] [1 1] [2 4]]
  ::=   e#   Vectorized quality: [i j] -> (i == j)
  0+    e#   Append a zero.
  0#    e#   Push the first index of 0.
  /     e#   Split the array into chunks of that size.
  (     e#   Shift out the first chunk.
  (o    e#   Print its first element.
  W>    e#   Discard all remaining elements (if any) except the last.
  Wf*   e#   Multiply all elements of the remainder by -1.
  S+o   e#   Append a space and print.
  e_    e#   Flatten the rest of the array.
}h      e# Repeat while the array is non-empty.

Answer 7

CJam, 38 33 bytes

New version, using ideas and code fragments suggested by @Dennis:

l~$_,,.-e`{~T+\_T+:T;(_2$+W*Q?S}/

Try it online

The input format is a CJam array in square brackets.

The basic idea here is that I subtract a monotonic sequence from the sorted input sequence first:

3  4  8  9 10 11 13 15
0  1  2  3  4  5  6  7  (-)
----------------------
3  3  6  6  6  6  7  8

In this difference, values that are part of the same interval have the same value. Applying the CJam RLE operator to this difference directly enumerates the intervals.

The subtracted sequential values need to be added back during output. I'm not entirely happy with how that's done in my code. I suspect that I could save a few bytes with a more elegant way of handing that.

For generating the output of the intervals, this uses Dennis' idea of generating a negative number for the end value, which takes care of producing a -, and also simplifies the logic because only one value needs to be added/omitted depending on the interval size.

Explanation:

l~    Get input.
$     Sort it.
_,,   Create monotonic sequence of same length.
.-    Calculate vector difference between the two.
e`    Calculate RLE of difference vector.
{     Loop over entries in RLE.
  ~     Unpack the RLE entry, now have length/value on stack.
  T+    Add position to get original value for start of interval.
  \     Bring length of interval to top of stack.
  _T+:T;  Add length of interval to variable T, which tracks position.
  (     Decrement interval length.
  _     Copy it, we need it once for calculating end value, once for ternary if condition.
  2$    Copy interval start value to top...
  +     ... and add interval length - 1 to get end value.
  W*    Negate end value.
  Q?    Output end value if interval length was > 1, empty string otherwise.
  S     Add a space.
}%    End loop.

Answer 8

Jelly, 16 bytes

ṢI’kƊ.ịⱮUQ€j€”-K

Try it online!

How it works

ṢI’kƊ.ịⱮUQ€j€”-K - Main link. Takes an array L on the left
Ṣ                - Sort L; Call this A
    Ɗ            - Monad. Link the previous three links together f(A):
 I               -   Forward differences
  ’              -   Decrement
   k             -   Partition
                   This groups consecutive runs
                   Take A = [3, 4, 6, 8, 9, 10, 11, 13, 15]
                   I: [1, 2, 2, 1, 1, 1, 2, 2]
                   ’: [0, 1, 1, 0, 0, 0, 1, 1]
                   k then partitions A at truthy elements in I’
                   [[3, 4], [6], [8, 9, 10, 11], [13], [15]
       Ɱ         - For each:
     .ị          -   Take the 0.5th element

                   For non-integer left argument, x, Jelly's ị atom takes
                   floor(x) and ceil(x) and returns [floor(x)ịy, ceil(x)ịy]
                   As Jelly's indexing is 1-based and modular:
                     0ị returns the last element
                     1ị returns the first element
                     .ị returns [0ị, 1ị]

        U        - Reverse each
         Q€      - Deduplicate each
           j€”-  - Join each with "-"
               K - Join by spaces

Answer 9

Husk, ²¹ 20 bytes

;moJ'-?I§e←→ε†sġ·=←O

Try it online!

A bit lacking in the strings department, but does well.

No matter what I tried, it somehow stubbornly stayed at 21.

-1 byte from Dominic Van Essen.

Explanation

;moJ'-?I§e←→ε†sġ§=…eO
                    O order the list
               ġ      group the list by the following:
                   e  elements paired
                §=    equal
                  …   the range between them?
             †s       convert all the numbers to strings
 mo                   map each group to the following:
      ?     ε         if it's a single element:
       I              leave as is
        §e←→          otherwise, move the first and last elements to a list
   J'-                join with '-'
;                     nest to display in one line

Answer 10

CoffeeScript, 178 161 bytes

Just like my JavaScript answer. I need to figure out if using comprehensions will result in shorter code.

f=(n)->s=e=o='';n.split(' ').map(Number).sort((a,b)->a-b).map((v)->s=s||v;(o+=s+(if s<e then'-'+e else'')+' ';s=v)if(e&&v>e+1);e=v);o+(if s<e then s+'-'else'')+e

---

Original:

f=(n)->o='';s=e=0;n.split(' ').map(Number).sort((a,b)->a-b).forEach((v,i)->if!i then s=v else(o+=s+(if s<e then'-'+e else'')+' ';s=v)if(v!=e+1);e=v);o+(if s<e then s+'-'else'')+e

Answer 11

Python 2, 126 122 121 Bytes

I know this can get shorter, just don't know where.. Requires input in form [#, #, #, #, ..., #].

l=sorted(input());s=`l[0]`;c=0;x=1
while x<len(l):y,z=l[x],l[x-1];s+=(('-'+`z`)*c+' '+`y`)*(y-z>1);c=(y-z<2);x+=1
print s

Answer 12

Java, 191 bytes

void f(int[]a){java.util.Arrays.sort(a);for(int b=a.length,c=b-1,i=0,j=a[0],l=j;++i<b;){if(a[i]!=++j||i==c){System.out.print((l+1==j?l+(i==c?" "+a[c]:""):l+"-"+(i==c?j:j-1))+" ");l=j=a[i];}}}

Checks for ranges and prints them accordingly. Unfortunately I had to make a special case for the last element in the array since the program would terminate without printing the last number or range.

Answer 13

Java, 171 162 bytes

String s(int[] n){Arrays.sort(n);int p=0,b=0;String r="",d="";for(int c:n){if(c==++p)b=1;else{if(b==1){r+="-"+--p+d+c;p=c;b=0;}else{r+=d+c;p=c;}d=" ";}}return r;}

Takes input as an int array, returns output as a space-separated String list

Answer 14

Japt -S, 17 16 bytes

ÍòÈnYÉÃ®é ¯2 Ôq-

Try it

Answer 15

Vyxal S, 120 bits^v1, 15 bytes

s:¯Ǐ⁽ṅḋ•ꜝƛ₍htU\-j

Try it Online!

Explained

s:¯Ǐ⁽ṅḋ•ꜝƛ₍htU\-j
s:                 # Push two copies of the input list but sorted
  ¯Ǐ               # Forward differences of items with the first item appended - this is for making sure the length of the deltas matches the length of the input
    ⁽ṅḋ            # Grouped by whether they are <= 1
       •           # Reshape the sorted input to that shape
        ꜝ          # and remove the 0
                   # the top of the stack will be a list of lists of numbers that are ranges
         ƛ         # to each range
          ₍htU     #   either get the first and last item or just the first
              \-j  #   join on "-"
# S flag joins the result on spaces

Answer 16

Haskell, 187 bytes

import Data.List
g p[x]=[[x]]
g p(a:b:c)|let(d:e)=g p(b:c)=if p a b then(a:d):e else[a]:(d:e)
p[x]=show x++" "
p x=show(head x)++"-"++show(last x)++" "
f=concatMap p.g(((-1==).).(-)).sort

Try it online!

Answer 17

Scala, 204 bytes

Modified from @steenslag's Ruby answer.

---

Golfed version. Try it online!

def s(a:Int*):Seq[String]={val s=a.sorted;(Seq[Seq[Int]](Seq(s(0)))/:s.sliding(2)){(c,p)=>if(p(0)+1==p(1))c.init:+(c.last:+p(1))else c:+Seq(p(1))}.map(r=>if(r.size<2)r.mkString else s"${r(0)}-${r.last}")}

Ungolfed version. Try it online!

object Main {
  def s(a: Int*): Unit = {
    val sorted = a.sorted
    val sortedRanges = sorted.sliding(2).foldLeft(List[List[Int]](List(sorted.head))) { (acc, pair) =>
      if (pair(0) + 1 == pair(1)) acc.init :+ (acc.last :+ pair(1))
      else acc :+ List(pair(1))
    }
    val ranges = sortedRanges.map(range => if (range.size < 2) range.mkString else s"${range.head}-${range.last}")
    println(ranges.mkString(" "))
  }

  def main(args: Array[String]): Unit = {
    s(9, 13, 3, 11, 8, 4, 10, 15, 6)
  }
}

Answer 18

Ly, 35 bytes

a0r[r0Ir::u[ps`=]pl~!['-olu!]p' o];

Try it online!

This is pretty brute force. It sorts the numbers then iterates until all the numbers have been consumed. After printing the "current" number on the stack, an inner loop consumes all the entries after that which are consequitive. Then it either appends a -# string or not before printing a space and iterating again.

# prep work... created sorted list of numbers with trailing "0"
a0r
a    - read numbers from STDIN, sort stack
 0   - push a "0"
  r  - reverse stack

# loop over all numbers, then exit
[                             ];
[                             ]   - iterate while top of stack not "0"
                               ;  - exit to avoid dumping junk on stack

# remember the current number for comparison later
r0Ir
r     - reverse stack
 0I   - copy bottom of stack entry to the top
   r  - reverse the stack

# print the current number, loop/consume all sequential nums on stack
::u[ps`=]p
::          - duplicate top of stack twice
  u         - print current number
   [    ]p  - loop until top of stack is "0"
    p       - delete previous number
     s      - save the current number
      `=    - increment current number, compare to next num on stack

# print "-X"  if needed to cover delete numbers, then print space    
l~!['-olu!]p' o
l                - load saved num (last number deleted)
 ~               - search stack for that number
  !              - negate result
   [      ]p     - "then" code block
    '-o          - print "-"
       lu        - load last num in sequence (last deleted)
         !       - flip top of stack to "0" to exit loop
            ' o  - print " "

Answer 19

Perl 5 -pa, 95 bytes

$_=join$",sort{$a-$b}@F;$b=$_,s/(\d+)\K (?=(\d+))/$2-$1-1?$":"-"/ge while$_ ne$b;s/(-\d+)+/$1/g

Try it online!