Range expansion

From Rosetta Code
Revision as of 16:26, 18 July 2010 by rosettacode>ShinTakezou (→‎{{header|ALGOL 68}}: RANGE(-3, -1) but no msg removed since it does not parse the range, it "encodes" it instead)
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

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 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
Retrieved from "https://rosettacode.org/wiki/Range_expansion?oldid=152344"