1
\$\begingroup\$

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
\$\endgroup\$
  • 6
    \$\begingroup\$ How are you going to measure 'fastest-code'? The trivial implementation is O(n) already, and I don't see a way to make it less than O(n), because you have to process the entire list anyway. \$\endgroup\$ – marinus Jan 2 '14 at 15:36
  • 1
    \$\begingroup\$ Perhaps better suited for golfing? \$\endgroup\$ – Yves Klett Jan 2 '14 at 17:39
  • \$\begingroup\$ I second the golfing idea. \$\endgroup\$ – Tim Seguine Jan 2 '14 at 22:19
  • \$\begingroup\$ Yes fair comment. An implementation of this might need to be run thousands of times for a large or broad-range catalogue, but I suppose it wouldn't be possible to decrease the complexity of processing each entry. \$\endgroup\$ – Tom Dudman Jan 3 '14 at 8:21
  • 1
    \$\begingroup\$ @TomDudman I gues for a few thousand entries, all but the most horrible implementations will work very quickly (you could post a test set). \$\endgroup\$ – Yves Klett Jan 3 '14 at 9:15
1
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ For me, this is a very elegant, human-readable, self-contained function which can be easily translated into other languages. \$\endgroup\$ – Tom Dudman Jan 3 '14 at 15:56
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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])));
\$\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.