Range expansion

From Rosetta Code
Revision as of 16:28, 18 July 2010 by rosettacode>ShinTakezou (→‎{{header|OCaml}}: works already, just changed the range expr)
Task
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

This example is incorrect. Please fix the code and remove this message.
Details: The task example was modified after discussion in the talk page.
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
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

<lang algol68>MODE YIELDINT = PROC(INT)VOID;

MODE RANGE = STRUCT(INT lwb, upb); MODE RANGEINT = UNION(RANGE, INT);

OP SIZEOF = ([]RANGEINT list)INT: (

  1. 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;
  1. FOR INT value IN # gen range expand(list, # ) DO #
    1. (INT value)VOID:
   out[upb +:= 1] := value
  1. 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>

  1. include <stdlib.h>
  2. include <string.h>
  3. include <stdarg.h>
  4. 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>

  1. include <iostream>
  2. include <sstream>
  3. include <iterator>
  4. include <climits>
  5. 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) = if '-' `elem` cs
           then let (a, _ : b) = break (== '-') cs
                in  [read (c : a) .. read b]
           else [read str]

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>

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

<lang Perl>sub rangex {

   (my $range = shift) =~ s/(?<=\d)-/../g;
   return eval $range;

}

  1. 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

alternately: <lang Perl>sub rangex {

   map { /([+-]?\d+)-([+-]?\d+)/ ? $1..$2 : $_ } split /,/, shift

}</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

This example is incorrect. Please fix the code and remove this message.
Details: The task example was modified after discussion in the talk page.

<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, 0, 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