Creating a catalogue index

Question

You have a program which creates an index for a catalogue. The last step is missing: it must find and consolidate page ranges within the list of pages for each entry.

Each entry is currently an array of unique integers in order, e.g:

[18,19,20,21,22,47,56,57,62,67,68,69,70]

Write a function which returns a consolidated array of ranges and individual pages as appropriate.

Individual pages can be converted to strings or remain as integers. Either of these would be valid results from the example input:

["18-22",47,"56-57",62,"67-70"] // valid
["18-22","47","56-57","62","67-70"] // valid

Answer 1

In JavaScript,

function catalogue(arr) {
    if (!arr.length) return [];
    for (var cat = [], first, prev = first = arr[0], i = 1, l = arr.length; i <= l; ++i) {
        i === l || prev + 1 !== arr[i]
            ? (cat.push(first + (first === prev ? "" : "-" + prev)), prev = first = arr[i])
            : ++prev;
    }
    return cat;
}
catalogue([18, 19, 20, 21, 22, 47, 56, 57, 62, 67, 68, 69, 70]);
    // ["18-22","47","56-57","62","67-70"]

Minified version (153 characters):

function f(b){if(!b.length)return[];for(var g=[],e,c=e=b[0],d=1,h=b.length;d<=h;++d)d===h||c+1!==b[d]?(g.push(e+(e===c?"":"-"+c)),c=e=b[d]):++c;return g}

Answer 2

Mathematica, 74

Assuming that replacing [] with {} in I/O is allowed:

t=ToString;f=Split[#,#2<#+2&]/.{s_Integer,___,e_}:>t@s<>"-"<>t@e/.{x_}:>x&

f[{18, 19, 20, 21, 22, 47, 56, 57, 62, 67, 68, 69, 70}]

{"18-22", 47, "56-57", 62, "67-70"}

The Split part should be quite fast (because someone else probably spent a lot of time optimizing) - the pattern matching part might be a bit slower in comparison. If speed is the main criterium, then there will be other ways to process the Split result (let´s see how the Q develops). For an input of 10^6 entries this takes about 2.7s on my (average) laptop (2.2GHz i7), of which about 1s goes to Split.

Answer 3

Javascript 271 bytes

A relatively simple application of reduce. If we are going to golf it, it minifies down to 271 chars.

Minified:

function f(a){function d(a,b,c){c=(a+"").split("-");return 2>c.length?a+1==b?[!1,a+"-"+b]:[!0,b]:+c.pop()+1==b?[!1,c[0]+"-"+b]:[!0,b]}return a.reduce(function(a,b,c,e){if("number"==typeof a)return[d(a,b)[1]];e=a.length-1;c=d(a[e],b);c[0]?a[e+1]=c[1]:a[e]=c[1];return a})}

Unminified

function g(p,c,i){
    i=(p+"").split("-");
    if(i.length==1) return (p+1==c)?[false,p+"-"+c]:[true,c];
    return ((+i[i.length-1])+1==c)?[false,i[0]+"-"+c]:[true,c];
}

function f(arr){
return arr.reduce(function(p,c,i){
    if ( typeof p =="number") {
        return [g(p,c)[1]];
    }
    else {
        i=g(p[p.length-1],c);
        if (i[0])
            p[p.length]=i[1];
        else
            p[p.length-1]=i[1];
        return p;
    }
});
}
alert(JSON.stringify(f([18,19,20,21,22,47,56,57,62,67,68,69,70])));

Answer 4

Haskell

module Pages (ranges) where

ranges =
  let f (a, b) | a == b = show a
               | a /= b = show a ++ "-" ++ show b
  in map f . ranges'

ranges' [] = []
ranges' (h:t) =
  unpack (range h h t)
  where unpack (t, l) = t : ranges' l

range :: Int -> Int -> [Int] -> ((Int, Int), [Int])
range a b [] = ((a, b), [])
range a b l@(h:t) | b+1 == h = range a h t
                  | otherwise = ((a, b), l)