18
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ The first sentence is really confusing. I'd recommend saying "output the shortest list of the longest possible ranges of sequential integers". Otherwise, nice challenge! \$\endgroup\$ – Nathan Merrill Jun 26 '15 at 19:16
  • 2
    \$\begingroup\$ I'm pretty sure we've had this challenge before, but I'm not coming up with the right search terms. Anyone remember? \$\endgroup\$ – xnor Jun 26 '15 at 19:28
  • 4
    \$\begingroup\$ @CoreyOgburn By the way, what prompted you to post on PPCG? We're trying to figure out why we got a whole bunch of new users coming in. \$\endgroup\$ – xnor Jun 26 '15 at 19:32
  • 2
    \$\begingroup\$ @xnor I've kept an eye on the site for months. None of the languages I use are usually good candidates for answers and I've never had a question to post until today. \$\endgroup\$ – Corey Ogburn Jun 26 '15 at 19:35
  • 1
    \$\begingroup\$ @xnor: It's similar to Maltysen's homework list one but not identical. \$\endgroup\$ – Alex A. Jun 26 '15 at 19:39

11 Answers 11

9
\$\begingroup\$

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:])

\$\endgroup\$
  • \$\begingroup\$ You can change str(n) to `n` to save a few bytes, if you switch to Python 2. \$\endgroup\$ – mbomb007 Jun 26 '15 at 21:25
  • \$\begingroup\$ You can also create a function that takes a list as input instead of using raw_input(), and you can change '-'+`n` to `-n`. And since you're now using Python 2, you can remove the parentheses after the print. \$\endgroup\$ – mbomb007 Jun 26 '15 at 21:38
  • \$\begingroup\$ Generating the string piece by piece is clever. For byte saving, it's generally shorter to do conditionals by list selection or arithmetic, like def f(N):print''.join([' '+`n`,`-n`*(n+1 not in N)][n-1 in N]for n in sorted(N))[1:](which can be golfed further). \$\endgroup\$ – xnor Jun 27 '15 at 8:25
  • \$\begingroup\$ You might be able to use set(N) instead of sorted(N); this will correctly iterate from smallest to lowest when using cPython but is not guaranteed to work for all implementations so there is some question about whether or not this is valid. \$\endgroup\$ – KSab Jun 29 '15 at 0:18
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ n.split with no parentheses is totally new to me! But [...n] is better \$\endgroup\$ – edc65 Jun 29 '15 at 20:52
  • \$\begingroup\$ @edc65 Thanks, never thought of unpacking the string like that. \$\endgroup\$ – rink.attendant.6 Jun 29 '15 at 20:58
  • \$\begingroup\$ Have a look at this codegolf.stackexchange.com/questions/37624/… \$\endgroup\$ – edc65 Jun 29 '15 at 21:04
  • \$\begingroup\$ ... but ... does it work with any of the examples? there are multidigit numbers, so you need a split on a " "(blank space) not "" (empty string). I probably gave you the wrong tip \$\endgroup\$ – edc65 Jun 29 '15 at 21:14
  • \$\begingroup\$ @edc65 I thought something looked different then I realized the test cases failed. Still good to learn something new though \$\endgroup\$ – rink.attendant.6 Jun 29 '15 at 21:28
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ That's a clever use of RLE! By borrowing the range handling and input format from my answer, you can get down to 34 bytes: l~$_,,.-e`{~T+\_T+:T;,f+(\W>Wf*S}/ \$\endgroup\$ – Dennis Jun 28 '15 at 14:25
  • \$\begingroup\$ When I had originally looked at your solution, I was kind of mystified how you got a - into the output without it showing up in the code, and without a condition. Now I get it: It comes from turning the end value into a negative number! I never would have come up with this, so I would feel bad about copying it. I'll try to learn from it for next time! :) \$\endgroup\$ – Reto Koradi Jun 28 '15 at 15:31
  • \$\begingroup\$ Fair enough. How about l~$_,,.-e{~T+_T+:T;(_2$+W*Q?S}/` though? That's a lot more similar to your own code and weighs only 33 bytes. \$\endgroup\$ – Dennis Jun 28 '15 at 18:37
  • \$\begingroup\$ @Dennis Ok, if you insist. :) Actually, taking the key idea of generating a negative value for the interval end, this looks like a reasonably straightforward way of implementing it. Thanks. \$\endgroup\$ – Reto Koradi Jun 28 '15 at 23:25
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You seem to find solutions with exec quite often. \$\endgroup\$ – mbomb007 Jun 26 '15 at 21:23
  • \$\begingroup\$ @mbomb007 You might be thinking of xnor :) And I think in this situation looping might be the same length, even shorter (haven't played around with it enough yet). \$\endgroup\$ – Kade Jun 26 '15 at 21:49
  • 1
    \$\begingroup\$ You should be able to replace while x<len(l) with while l[x:] to save a few bytes. \$\endgroup\$ – mathmandan Jun 27 '15 at 5:35
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.