Range expansion
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)
- The range syntax is to be used only for, and for every range that expands to more than two values.
Example
The list of integers:
- -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20
Is accurately expressed by the range expression:
- -6,-3-1,3-5,7-11,14,15,17-20
(And vice-versa).
The task
Expand the range description:
- -6,-3--1,3-5,7-11,14,15,17-20
Note that the second element above, is the range from minus 3 to minus 1.
C.f. Range extraction
ALGOL 68
<lang algol68>MODE YIELDINT = PROC(INT)VOID;
MODE RANGE = STRUCT(INT lwb, upb); MODE RANGEINT = UNION(RANGE, INT);
OP SIZEOF = ([]RANGEINT list)INT: (
- determine the length of the output array #
INT upb := LWB list - 1; FOR key FROM LWB list TO UPB list DO CASE list[key] IN (RANGE value): upb +:= upb OF value - lwb OF value + 1, (INT): upb +:= 1 ESAC OD; upb
);
PROC gen range expand = ([]RANGEINT list, YIELDINT yield)VOID:
FOR key FROM LWB list TO UPB list DO CASE list[key] IN (RANGE range): FOR value FROM lwb OF range TO upb OF range DO yield(value) OD, (INT int): yield(int) ESAC OD;
PROC range expand = ([]RANGEINT list)[]INT: (
[LWB list: LWB list + SIZEOF list - 1]INT out; INT upb := LWB out - 1;
- FOR INT value IN # gen range expand(list, # ) DO #
- (INT value)VOID:
out[upb +:= 1] := value
- OD #);
out
);
test:(
[]RANGEINT list = (-6, RANGE(-3, -1), RANGE(3, 5), RANGE(7, 11), 14, 15, RANGE(17, 20)); print((range expand(list), new line))
)</lang> Output:
-6 -3 -2 -1 +3 +4 +5 +7 +8 +9 +10 +11 +14 +15 +17 +18 +19 +20
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <stdarg.h>
- include <stdbool.h>
enum range_action { RANGE_NEW, RANGE_NEXT, RANGE_RESET, RANGE_FREE };
typedef struct range_s {
long int val; char *range; // private members size_t pos; size_t slen; long int clower; long int cupper; bool inrange;
} *range_t;
range_t range(enum range_action action, ...) {
range_t r; va_list al; char *ep, *tp;
va_start(al, action); switch(action) { case RANGE_NEW: r = malloc(sizeof(struct range_s)); if (r != NULL) { r->range = va_arg(al, char *); r->pos = 0; r->slen = strlen(r->range); r->inrange = false; } break; case RANGE_NEXT: r = va_arg(al, range_t); if ( r->inrange ) { if ( r->val < r->cupper ) {
r->val++; va_end(al); return r;
} else {
r->inrange = false;
} } if ( r->pos >= r->slen ) return NULL; r->val = strtol(r->range + r->pos, &ep, 10); if ( ep == (r->range + r->pos) ) return NULL; if ( *ep == '-' ) { r->clower = r->val; r->cupper = strtol(ep + 1, &tp, 10); if ( (ep+1) == tp ) return NULL; r->inrange = true; ep = tp; } // any other symbol works like , r->pos = ep+1 - r->range; break; case RANGE_RESET: r = va_arg(al, range_t); r->pos = 0; break; case RANGE_FREE: r = va_arg(al, range_t); free(r); return NULL; } va_end(al); return r;
}
// usage int main() {
range_t r = range(RANGE_NEW, "-6,-3--1,3-5,7-11,14,15,17-20");
while( range(RANGE_NEXT, r) != NULL ) { printf("%d ", r->val); }
printf("\n"); range(RANGE_FREE, r); return 0;
}</lang>
C++
<lang cpp>
- include <iostream>
- include <sstream>
- include <iterator>
- include <climits>
- include <deque>
// parse a list of numbers with ranges // // arguments: // is: the stream to parse // out: the output iterator the parsed list is written to. // // returns true if the parse was successful. false otherwise template<typename OutIter>
bool parse_number_list_with_ranges(std::istream& is, OutIter out)
{
int number; // the list always has to start with a number while (is >> number) { *out++ = number;
char c; if (is >> c) switch(c) { case ',': continue; case '-': { int number2; if (is >> number2) { if (number2 < number) return false; while (number < number2) *out++ = ++number; char c2; if (is >> c2) if (c2 == ',') continue; else return false; else return is.eof(); } else return false; } default: return is.eof(); } else return is.eof(); } // if we get here, something went wrong (otherwise we would have // returned from inside the loop) return false;
}
int main() {
std::istringstream example("-6,-3--1,3-5,7-11,14,15,17-20"); std::deque<int> v; bool success = parse_number_list_with_ranges(example, std::back_inserter(v)); if (success) { std::copy(v.begin(), v.end()-1, std::ostream_iterator<int>(std::cout, ",")); std::cout << v.back() << "\n"; } else std::cout << "an error occured.";
} </lang> Output:
-6,-3,-2,-1,3,4,5,7,8,9,10,11,14,15,17,18,19,20
Haskell
Given either of the below implementations of expandRange
:
<lang haskell>> expandRange "-6,-3--1,3-5,7-11,14,15,17-20" [-6,-3,-2,-1,3,4,5,7,8,9,10,11,14,15,17,18,19,20]</lang>
With conventional list processing
<lang haskell>expandRange :: String -> [Int] expandRange = concatMap f . split ','
where f str@(c : cs) | '-' `elem` cs = [read (c : a) .. read b] | otherwise = [read str] where (a, _ : b) = break (== '-') cs
split :: Eq a => a -> [a] -> a split delim [] = [] split delim l = a : split delim (dropWhile (== delim) b)
where (a, b) = break (== delim) l</lang>
With a parser
<lang haskell>import Control.Monad import Text.ParserCombinators.Parsec
expandRange :: String -> [Int] expandRange s = case parse rangeParser "" s of Right l -> l
rangeParser :: Parser [Int] rangeParser = liftM concat $ item `sepBy` char ','
where item = do n1 <- num n2 <- option n1 $ char '-' >> num return [n1 .. n2] num :: Parser Int num = liftM read $ liftM2 (++) (option "" $ string "-") (many1 digit)</lang>
Icon and Unicon
Icon
<lang Icon>procedure main() s := "-6,-3--1,3-5,7-11,14,15,17-20" write("Input string := ",s) write("Expanded list := ", list2string(range_expand(s)) | "FAILED") end
procedure range_expand(s) #: return list of integers extracted from an ordered string representation local R,low,high R := []
s ? until pos(0) do {
put(R,low := integer(tab(upto(',-')|0))| fail) # get lower bound if ="-" || (high := integer(tab(find(",")|0))|fail) then until low = high do put(R,low +:= 1) # find range ="," }
return R end
procedure list2string(L) #: helper function to convert a list to a string local s
every (s := "[ ") ||:= !L || " " return s || "]"
end</lang>
Sample output:
Input string := -6,-3--1,3-5,7-11,14,15,17-20 Expanded list := [ -6 -3 -2 -1 3 4 5 7 8 9 10 11 14 15 17 18 19 20 ]
Unicon
This Icon solution works in Unicon.
J
<lang j>require'strings' to=: (+ i.)/@:(0 1 + -~/\) num=: _&". normaliz=: rplc&(',-';',_';'--';'-_')@,~&',' lumps=:<@(num`([:to num;._1@,~&'-')@.('-'&e.));._1 rngexp=: ;@lumps@normaliz</lang>
Example: <lang j> rngexp '-6,-3--1,3-5,7-11,14,15,17-20' _6 _3 _2 _1 3 4 5 7 8 9 10 11 14 15 17 18 19 20</lang>
Java
<lang java>import java.util.*; import java.util.regex.*;
class Range implements Enumeration {
private int clower, cupper; private int value; private boolean inrange; private Scanner ps = null; private String ss;
private static String del = "\\s*,\\s*";
public Range(String s) { ss = s; reset(); }
public boolean hasMoreElements() { return (inrange && (value >= clower && value <= cupper)) || ps.hasNext(); }
public Object nextElement() throws NoSuchElementException { if ( ! hasMoreElements() ) throw new NoSuchElementException(); if ( inrange && (value >= clower && value <= cupper) ) { value++; return value-1; } if ( inrange ) inrange = false; String n = ps.next(); if ( n.matches("[+-]?\\d+-[+-]?\\d+") ) { Scanner ls = new Scanner(n); ls.findInLine("([+-]?\\d+)-([+-]?\\d+)"); MatchResult r = ls.match(); clower = Integer.parseInt(r.group(1)); cupper = Integer.parseInt(r.group(2)); value = clower+1; inrange = true; ls.close(); return clower; } return Integer.parseInt(n); } public void reset() { if ( ps != null) ps.close(); ps = new Scanner(ss).useDelimiter(del); inrange = false; }
protected void finalize() throws Throwable { ps.close(); super.finalize(); }
}
class rangexp {
public static void main(String[] args) { Range r = new Range("-6,-3--1,3-5,7-11,14,15,17-20"); while ( r.hasMoreElements() ) { System.out.print(r.nextElement() + " "); } System.out.println(); }
}</lang>
MUMPS
<lang MUMPS> RANGEXP(X) ;Integer range expansion
NEW Y,I,J,X1,H SET Y="" FOR I=1:1:$LENGTH(X,",") DO .S X1=$PIECE(X,",",I) FOR Q:$EXTRACT(X1)'=" " S X1=$EXTRACT(X1,2,$LENGTH(X1)) ;clean up leading spaces .SET H=$FIND(X1,"-")-1 .IF H=1 SET H=$FIND(X1,"-",(H+1))-1 ;If the first value is negative ignore that "-" .IF H<0 SET Y=$SELECT($LENGTH(Y)=0:Y_X1,1:Y_","_X1) .IF '(H<0) FOR J=+$EXTRACT(X1,1,(H-1)):1:+$EXTRACT(X1,(H+1),$LENGTH(X1)) SET Y=$SELECT($LENGTH(Y)=0:J,1:Y_","_J) KILL I,J,X1,H QUIT Y</lang>
Example:
USER>SET U="-6,-3--1,3-5,7-11,14,15,17-20" USER>WRITE $$RANGEXP^ROSETTA(U) -6,-3,-2,-1,3,4,5,7,8,9,10,11,14,15,17,18,19,20
OCaml
<lang ocaml>#load "str.cma"
let range a b =
if b < a then invalid_arg "range"; let rec aux i acc = if i = b then List.rev(i::acc) else aux (succ i) (i::acc) in aux a []
let parse_piece s =
try Scanf.sscanf s "%d-%d" (fun a b -> range a b) with _ -> [int_of_string s]
let range_expand rng =
let ps = Str.split (Str.regexp_string ",") rng in List.flatten (List.map parse_piece ps)
let () =
let rng = "-6,-3--1,3-5,7-11,14,15,17-20" in let exp = range_expand rng in List.iter (Printf.printf " %d") exp; print_newline()</lang>
Oz
<lang oz>declare
fun {Expand RangeDesc} {Flatten {Map {ParseDesc RangeDesc} ExpandRange}} end
fun {ParseDesc Txt} {Map {String.tokens Txt &,} ParseRange} end
fun {ParseRange R} if {Member &- R.2} then First Second in {String.token R.2 &- ?First ?Second} {String.toInt R.1|First}#{String.toInt Second} else Singleton = {String.toInt R} in Singleton#Singleton end end
fun {ExpandRange From#To} {List.number From To 1} end
in
{System.showInfo {Value.toVirtualString {Expand "-6,-3--1,3-5,7-11,14,15,17-20"} 100 100}}</lang>
Sample output (in Oz list syntax): <lang oz>[~6 ~3 ~2 ~1 3 4 5 7 8 9 10 11 14 15 17 18 19 20]</lang>
Perl
One-liner: <lang Perl>sub rangex {
map { /^(.*\d)-(.+)$/ ? $1..$2 : $_ } split /,/, shift
}
- Test and display
print join(',', rangex('-6,-3--1,3-5,7-11,14,15,17-20')), "\n";</lang>
Output:
-6,-3,-2,-1,3,4,5,7,8,9,10,11,14,15,17,18,19,20
Alternative: <lang Perl>sub rangex {
(my $range = shift) =~ s/(?<=\d)-/../g; eval $range;
}</lang>
PicoLisp
<lang PicoLisp>(de rangeexpand (Str)
(make (for S (split (chop Str) ",") (if (index "-" (cdr S)) (chain (range (format (head @ S)) (format (tail (- -1 @) S)) ) ) (link (format S)) ) ) ) )</lang>
Output:
: (rangeexpand "-6,-3--1,3-5,7-11,14,15,17-20") -> (-6 -3 -2 -1 3 4 5 7 8 9 10 11 14 15 17 18 19 20)
PureBasic
<lang PureBasic>Procedure rangeexpand(txt.s, List outputList())
Protected rangesCount = CountString(txt, ",") + 1 Protected subTxt.s, r, rangeMarker, rangeStart, rangeFinish, rangeIncrement, i LastElement(outputList()) For r = 1 To rangesCount subTxt = StringField(txt, r, ",") rangeMarker = FindString(subTxt, "-", 2) If rangeMarker rangeStart = Val(Mid(subTxt, 1, rangeMarker - 1)) rangeFinish = Val(Mid(subTxt, rangeMarker + 1)) If rangeStart > rangeFinish rangeIncrement = -1 Else rangeIncrement = 1 EndIf i = rangeStart - rangeIncrement Repeat i + rangeIncrement AddElement(outputList()): outputList() = i Until i = rangeFinish Else AddElement(outputList()): outputList() = Val(subTxt) EndIf Next
EndProcedure
Procedure outputListValues(List values())
Print("[ ") ForEach values() Print(Str(values()) + " ") Next PrintN("]")
EndProcedure
If OpenConsole()
NewList values() rangeexpand("-6,-3--1,3-5,7-11,14,15,17-20", values()) outputListValues(values()) Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf</lang> Sample output:
[ -6 -3 -2 -1 3 4 5 7 8 9 10 11 14 15 17 18 19 20 ]
Python
<lang python>def rangeexpand(txt):
lst = [] for r in txt.split(','): if '-' in r[1:]: r0, r1 = r[1:].split('-', 1) lst += range(int(r[0] + r0), int(r1) + 1) else: lst.append(int(r)) return lst
print(rangeexpand('-6,-3--1,3-5,7-11,14,15,17-20'))</lang>
Another variant, using regular expressions to parse the ranges:
<lang python>import re
def rangeexpand(txt):
lst = [] for rng in txt.split(','): start,end = re.match('^(-?\d+)(?:-(-?\d+))?$', rng).groups() if end: lst.extend(xrange(int(start),int(end)+1)) else: lst.append(int(start)) return lst</lang>
Sample output
[-6, -3, -2, -1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]
Ruby
<lang ruby>def range_expand(rng)
lst = rng.split(',').collect do |part| begin Integer(part) rescue ArgumentError if part.scan(/^(-?\d+)-(-?\d+)$/) ($1.to_i .. $2.to_i).to_a else raise ArgumentError, "Can't parse part of range: '#{part}'" end end end lst.flatten
end
p range_expand('-6,-3--1,3-5,7-11,14,15,17-20')</lang>
output:
[-6, -3, -2, -1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]
SNOBOL4
<lang SNOBOL4>* # Return range n1 .. n2
define('range(n1,n2)') :(range_end)
range range = range n1 ','; n1 = lt(n1,n2) n1 + 1 :s(range)
range rtab(1) . range :(return)
range_end
define('rangex(range)d1,d2') num = ('-' | ) span('0123456789') :(rangex_end)
rangex range num . d1 '-' num . d2 = range(d1,d2) :s(rangex)
rangex = range :(return)
rangex_end
- # Test and display
output = rangex('-6,-3--1,3-5,7-11,14,15,17-20')
end</lang>
Output:
-6,-3,-2,-1,3,4,5,7,8,9,10,11,14,15,17,18,19,20
Tcl
<lang tcl>proc rangeExpand desc {
set result {} foreach term [split $desc ","] {
set count [scan $term %d-%d from to] if {$count == 1} { lappend result $from } elseif {$count == 2} { for {set i $from} {$i <= $to} {incr i} {lappend result $i} }
} return $result
}
puts [rangeExpand "-6,-3--1,3-5,7-11,14,15,17-20"]</lang> Output:
-6 -3 -2 -1 3 4 5 7 8 9 10 11 14 15 17 18 19 20