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\$
8
  • 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
    Commented Jan 2, 2014 at 15:36
  • 1
    \$\begingroup\$ Perhaps better suited for golfing? \$\endgroup\$
    – Yves Klett
    Commented Jan 2, 2014 at 17:39
  • \$\begingroup\$ I second the golfing idea. \$\endgroup\$ Commented Jan 2, 2014 at 22:19
  • 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
    Commented Jan 3, 2014 at 9:15
  • 1
    \$\begingroup\$ I’m voting to close this question it's tagged fastest-code but is missing details about the specs of the computer on which answers are timed etc \$\endgroup\$ Commented Mar 30, 2022 at 3:34

4 Answers 4

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

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