Range extraction

From Rosetta Code
Revision as of 05:13, 16 July 2010 by rosettacode>Paddy3118 (→‎{{header|Python}}: Add sample output.)
Task
Range extraction
You are encouraged to solve this task according to the task description, using any language you may know.

A format for expressing an ordered list of integers is to use a comma separated list of either

  • individual integers
  • Or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, '-'. (The range includes all integers in the interval including both endpoints)

So the list of integers: 1, 2, 3, 6, 7, 9 could be written as: 1-3,6-7,9 or as 1-3,6,7,9 or as ...

We add a further rule:

  • The range syntax is to be used only for, and for every range that expands to more than two values.

This means that the above example could only become: 1-3,6,7,9

The task is to create a function that takes a list of integers and returns a correctly formatted string in the range format. Use the function to compute and print the range formatted version of the following ordered list of integers: 

    0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39


C.f. Range expansion

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

The following code includes a set of helper functions that can be used to manipulate a lists of ranges. They can manipulate either arrays or iterator. And they can handle data of type int or range and both these types unioned.

Note: The closest concept that Algol 68 has to duck typing is the tagged union. If duck typing was available it could reduced the size of the code specimen, but would have lost some of Algol 68's strong type data security. <lang algol68>MODE YIELDINT = PROC(INT)VOID; MODE INTLIST = FLEX[0]INT;

  2. Declarations for manipulating lists of range pairs [lwb:upb] #

MODE RANGE = STRUCT(INT lwb, upb); MODE RANGELIST = FLEX[0]RANGE; MODE YIELDRANGE = PROC(RANGE)VOID;

PROC range repr = (RANGE range)STRING: 

 whole(lwb OF range,0)+
   IF lwb OF range = upb OF range THEN "" ELSE ":"+whole(upb OF range,0) FI;
  1. OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #
  2. Declarations for manipulating lists containing pairs AND lone INTs #

MODE RANGEINT = UNION(INT, RANGE); MODE RANGEINTLIST = FLEX[0]RANGEINT; MODE YIELDRANGEINT = PROC(RANGEINT)VOID;

PROC range int repr = (RANGEINT range int)STRING: 

 CASE range int IN
   (RANGE range): range repr(range),
   (INT int): whole(int,0)
 ESAC;

OP REPR = (RANGEINT range int)STRING: range int repr(range int);

  1. The closest thing ALGOL 68 has to inheritance is the union #

MODE RANGEINTLISTINIT = UNION(RANGEINTLIST, RANGELIST, INTLIST);

  1. Note: Algol 68RS cannot handle LWB and UPB of a UNION in the following: #

PROC gen range = (RANGEINTLISTINIT range int list, YIELDRANGE yield range)VOID: 

 FOR key FROM LWB range int list TO UPB range int list DO
   RANGEINT value = CASE range int list IN 
                      (INTLIST list):list[key],
                      (RANGELIST list):list[key],
                      (RANGEINTLIST list):list[key]
                    ESAC;
   yield range(
     CASE value IN
       (RANGE range): range,
       (INT value): (value, value)
     ESAC
   )
 OD;

PROC gen range merge = (RANGEINTLISTINIT range int list, YIELDRANGE yield range)VOID: ( 

 UNION(VOID, RANGE) prev range := EMPTY;
  1. FOR RANGE next range IN # gen range(range int list, # ) DO #
    1. (RANGE next range)VOID:
  2. if the ranges cannot be merge, then yield 1st, and return 2nd #
   prev range := 
     CASE prev range IN
       (VOID): next range,
       (RANGE prev range): 
         IF upb OF prev range + 1 = lwb OF next range THEN
           RANGE(lwb OF prev range, upb OF next range) # merge the range #
         ELSE
           IF lwb OF prev range <= upb OF prev range THEN
             yield range(prev range)
           FI;
           next range
         FI
       OUT SKIP
     ESAC
  1. OD # );
 CASE prev range IN (RANGE last range): yield range(last range) ESAC

);

PROC gen range int merge = (RANGEINTLISTINIT range int list, YIELDRANGEINT yield range int)VOID: (

  1. FOR RANGE range IN # gen range merge(range int list, # ) DO #
    1. (RANGE range)VOID:
   yield range int(
     IF lwb OF range = upb OF range THEN lwb OF range ELSE range FI
   )
  1. OD # )

);

PROC range int list init = (RANGEINTLISTINIT range int list)RANGEINTLIST: ( 

 [LWB range int list: UPB range int list]RANGEINT out range int list;
 INT upb out range int list := LWB out range int list - 1;
  1. FOR RANGEINT range int IN # gen range int merge(range int list, # ) DO #
    1. (RANGEINT range int)VOID:
   out range int list[upb out range int list+:=1] := range int
  1. OD # );
 out range int list[:upb out range int list]

);

PROC range int list repr = (RANGEINTLIST range int list)STRING: ( 

 STRING out := "(", sep := "";
 FOR key FROM LWB range int list TO UPB range int list DO
   out +:= sep + REPR range int list[key];
   sep := ", "
 OD;
 out+")"

);

OP REPR = (RANGEINTLIST range int list)STRING: range int list repr(range int list);

  2. do some simple test cases: #

test: BEGIN 

 []INT int list = (
   0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39);
 
 []RANGE range list = ( # unnormalised #
   (0,0),  (1,1),  (2,2),  (4,4),  (6,6),  (7,7),  (8,8), (11,11), (12,12), (14,14),
   (15,15), (16,16), (17,17), (18,18), (19,19), (20,20), (21,21), (22,22), (23,23), (24,24),
   (25,25), (27,27), (28,28), (29,29), (30,30), (31,31), (32,32), (33,33), (35,35), (36,36),
   (37,37), (38,38), (39,39));
 
 []RANGEINT list a = (RANGE(0,2), 4, RANGE(6,8), RANGE(11,12), RANGE(14,25), RANGE(27,33), RANGE(35,39));

 []RANGEINT list b = ( # unnormalised #
   0,  1,  2,  4,  6,  7,  8, 11, 12, 14,
   15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
   25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
   37, 38, 39);

 FLEX[0]RANGEINT list c := range int list init(list b); # normalised #
  1. compare manipulation of various types of argument lists #
 print((REPR range int list init(int list), new line));
 print((REPR range int list init(range list), new line));
 print((REPR list a, new line));
 print((REPR(range int list init(list b)), new line));
 print((REPR list c, new line))

END</lang> Output: 

(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)
(0:2, 4, 6:8, 11:12, 14:25, 27:33, 35:39)

Python

<lang python>#import random

def rangeextract(lst): 

   lenlst = len(lst)
   i, ranges = 0, []
   while i< lenlst:
       low = lst[i]
       while i <lenlst-1 and lst[i]+1 == lst[i+1]: i +=1
       hi = lst[i]
       ranges.append(
           '%i-%i'  % (low, hi) if hi - low >= 2 else
           ('%i,%i' % (low, hi) if hi - low == 1 else
            '%i' % low) )
       i += 1
   return ','.join(ranges)
  1. lst = sorted(random.sample(list(range(40)), 33))
  2. print (lst)

lst = [ 0, 1, 2, 4, 6, 7, 8, 11, 12, 14, 

      15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
      25, 27, 28, 29, 30, 31, 32, 33, 35, 36,
      37, 38, 39]

print(rangeextract(lst))</lang>

Sample output 

0-2,4,6-8,11,12,14-25,27-33,35-39
Retrieved from "https://rosettacode.org/wiki/Range_extraction?oldid=151871"