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
Note: The following Iterative code specimen is the "unrolled" version of the Generative code specimen below. Together they provided as a comparison of the two different methods.
Iterative
- The closest concept that Algol 68 has to duck typing is the tagged union. This is used to define mode rangeint = union(int, struct(int lwb, upb)). If duck typing was available it could reduced the size of the code specimen, but would have lost some of Algol 68s strong type data security.
<lang algol68>MODE INTLIST = FLEX[0]INT; MODE YIELDINT = PROC(INT)VOID;
- 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;
- OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #
- 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);
- The closest thing ALGOL 68 has to inheritance is the union #
MODE RANGEINTLISTINIT = UNION(RANGEINTLIST, RANGELIST, INTLIST);
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);
- 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;
- FOR RANGE next range IN # gen range(range int list, # ) DO #
- (RANGE next range)VOID:
- 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
- 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: (
- FOR RANGE range IN # gen range merge(range int list, # ) DO #
- (RANGE range)VOID:
yield range int( IF lwb OF range = upb OF range THEN lwb OF range ELSE range FI )
- 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;
- FOR RANGEINT range int IN # gen range int merge(range int list, # ) DO #
- (RANGEINT range int)VOID:
out range int list[upb out range int list+:=1] := range int
- OD # );
out range int list[:upb out range int list]
);
- 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 #
- 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)
Generative
- The following code a set of helper functions/generators 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.
<lang algol68>MODE INTLIST = FLEX[0]INT; MODE YIELDINT = PROC(INT)VOID;
- 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;
- OP REPR = (RANGE range)STRING: range repr(range); firmly related to RANGEINT #
- 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);
- The closest thing ALGOL 68 has to inheritance is the union #
MODE RANGEINTLISTINIT = UNION(RANGEINTLIST, RANGELIST, INTLIST);
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);
- 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;
- FOR RANGE next range IN # gen range(range int list, # ) DO #
- (RANGE next range)VOID:
- 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
- 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: (
- FOR RANGE range IN # gen range merge(range int list, # ) DO #
- (RANGE range)VOID:
yield range int( IF lwb OF range = upb OF range THEN lwb OF range ELSE range FI )
- 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;
- FOR RANGEINT range int IN # gen range int merge(range int list, # ) DO #
- (RANGEINT range int)VOID:
out range int list[upb out range int list+:=1] := range int
- OD # );
out range int list[:upb out range int list]
);
- 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 #
- 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)
- lst = sorted(random.sample(list(range(40)), 33))
- 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