[Purdue-pm] take 2: challenge problem solution

Mark Senn mark at purdue.edu
Sat Mar 27 17:42:20 PDT 2010


Sorry for zero-length attachment in previous message.

Below is my solution to the latest challenge problem.
It assumes that all input to the two subs we were
asked to write is sanity checked outside of of those subs.

-mark

#!/usr/bin/perl

use Modern::Perl;

#
#  From http://perl.plover.com/qotw/r/006 retrieved on 2010-03-27:
#
#      Write a function, format_number_list, whose argument is a list of
#      integers.  It then returns a string which represents the input list in
#      compact, human-readable form.
#
#      For example,
#
#               format_number_list(1, 2, 4, 5, 6, 7, 9, 13, 24, 25, 26, 27)
#
#      will return
#
#              "1-2, 4-7, 9, 13, 24-27"
#
#      Also write a function, 'expand_number_list', which does the conversion
#      in the opposite direction, so that
#
#              expand_number_list("1-2, 4-7, 9, 13, 24-27")
#
#      will return
#
#              (1, 2, 4, 5, 6, 7, 9, 13, 24, 25, 26, 27)
#
#  From Michael Gribskov on 2010-03-24 (slightly edited to keep most lines
#  less than 80 characters):
#
#      my @datalist = ( [],
#          [1, 4, 5, 6, 9, 13, 21, 22, 23, 25, 26, 27],
#          [1, 2, 3, 5, 6, 7, 9, 13, 15, 16, 17, 27],
#          [-27, -17, -16, -15, -13, -9, -7, -6, -5, -3, -2, -1],
#          [-27, -26, -25, -23, -22, -21, -13, -9, -6, -5, -4, -1],
#          [-8, -6, -5, -4, 9, 13, 21, 22, 23, 25, 26, 27],
#          [-6, -5, -4, 5, 6, 7, 9, 13, 15, 16, 17, 27],
#          [-8, -6, -5, -4, 0, 9, 13, 21, 22, 23, 25, 26, 27],
#          [-6, -5, -4, 5, 9, 6, 7, 9, 13, 15, 16, 17, 27]
#      );
#      my @datacomment = ( 'null list',
#          'begins with singleton, ends with range',
#          'begins with range, ends with singleton',
#          'negative numbers, begin with singleton, end with range',
#          'negative numbers, begin with range, end with singleton',
#          'negative & positive numbers, begin with singleton, end with range',
#          'negative & positive numbers, begin with range, end with singleton',
#          'negative & positive numbers & zero, begin with singleton, end with range',
#          'negative & positive numbers & zero, begin with range, end with singleton',
#      );
#      foreach my $d ( 0 .. $#datalist ) {
#          my @data = @{$datalist[$d]};
#          print "\ntest $d: $datacomment[$d]\n";
#          print "    data = [ @data ]\n";
#          print "      original number list: @data\n";
#          my $numstring = formatNumberList( @data );
#          print "     formatted number list: $numstring\n";
#          my @newlist = expandNumberList( $numstring );
#          print "    converted back to list: @newlist\n";
#
#      }
#
#  I think the time and space needed for the program below are both order n,
#  assuming perl's range operator is implemented reasonably.
#


#
#  Pair - format a begin/end pair
#
#  Return "", "$begin", or "$begin-$end"
#  depending on values of $begin and $end.
#

sub Pair
{
    my ($begin, $end) = @_;
    my $r = $begin // '';
    ($end != $begin)  and  $r .= "-$end";
    return $r;
}


#
#  expand_number_list - expand number list to array
#
#  Expand, for example,
#      "1-2, 4-7, 9, 13, 24-27"
#  to
#      (1, 2, 4, 5, 6, 7, 9, 13, 24, 25, 26, 27)
#
#  VARIABLE    DESCRIPTION
#  $begin      value that starts a singleton or a range
#  $end        value that ends a singleton or a range
#  @r          resulting components, 1, 2, 4, ... in above example
#

sub expand_number_list
{
    my @item = split /,\s*/, $_[0];
    my ($begin, $end);
    my @r = ();
    foreach (@item)
    {
        (/^(-?\d+)$/)          and  $begin = $1, $end = $1;
        (/^(-?\d+)-(-?\d+)$/)  and  $begin = $1, $end = $2;
        push @r, $begin..$end;
    }
    return @r;
}


#
#  format_number_list - reduce an array to a number list
#
#  Reduce, for example,
#      (1, 2, 4, 5, 6, 7, 9, 13, 24, 25, 26, 27)
#  to
#      "1-2, 4-7, 9, 13, 24-27"
#
#  I used the nested ternary operators instead of nested if-then-else's
#  because I thought that was more readable.  Using if-then-else's would
#  have buried the actions to take in a lot more syntax.
#
#  VARIABLE    DESCRIPTION
#  $begin      value that starts a singleton or a range
#  $end        value that ends a singleton or a range
#  @r          resulting components, "1-2", "4-7", "9", ... in above example
#

sub format_number_list
{
    my @r = ();
    my $begin = my $end = undef;
    foreach (@_)
    {
        (defined $begin)
            ?  ($_ == $end+1)
                   ?  do {  $end = $_;                                        }
                   :  do {  push @r, Pair $begin, $end;  $begin = $end = $_;  }
            :  do {  $begin = $end = $_;  }
    }
    (defined $begin)  and  push @r, Pair $begin, $end;
    return join ', ', @r;
}


#
#  main program
#

my $sepline = '-' x 40;  # line to separate lines of output
while (<DATA>)
{
    chomp;
    my @data0 = split /,\s*/;
    my $data1 = format_number_list @data0;
    my @data2 = expand_number_list $data1;
    say $sepline;
    say "data read:                @data0";
    say "after expand number_list: @data2";
    say "after format_number_list: $data1";
    ((join ' ', @data0) ne (join ' ', @data2))
        and  die "data0 and data2 are different";
    say $sepline;
}


#
#  All of this data except the last two lines is from Michael Gribskov.
#

__DATA__

1, 4, 5, 6, 9, 13, 21, 22, 23, 25, 26, 27
1, 2, 3, 5, 6, 7, 9, 13, 15, 16, 17, 27
-27, -17, -16, -15, -13, -9, -7, -6, -5, -3, -2, -1
-27, -26, -25, -23, -22, -21, -13, -9, -6, -5, -4, -1
-8, -6, -5, -4, 9, 13, 21, 22, 23, 25, 26, 27
-6, -5, -4, 5, 6, 7, 9, 13, 15, 16, 17, 27
-8, -6, -5, -4, 0, 9, 13, 21, 22, 23, 25, 26, 27
-6, -5, -4, 5, 9, 6, 7, 9, 13, 15, 16, 17, 27
-1, 0, 1
0


More information about the Purdue-pm mailing list