spurperl has asked for the wisdom of the Perl Monks concerning the following question:

Fellow monks,

I found myself in a need to implement a custom subrange from an array (in C++, but a Perl solution should be similar). It's an interesting challenge, and I wonder if there exists a really elegant solution to it:

Input: an array of some length and a pair of numbers that spacify its range. For example you get an array with 4 elementsand the pair is (5, 8) - that is, the 0th array value has a subscript of 5, the last of 8. This range can be descending ! You also receive a subrange that should be extracted from the array.

To formalize, here's the input to your function:

{ arr => \@the_array, arr_range => [from, to], subrange => [subfrom, subto] }

The returned value should be the sub-array of the_array in the range subfrom-subto, in the correct sub-order (ascending or descending). For example you get:

{ arr => [cero, uno, dos, tres], range => [5, 8], subrange => [6, 5] }

You should return: [uno, cero]

You're also required to report if some of the requested subrange elements are out of the array range, i.e. if in the example you'd be asked for subrange (6, 4) it's an error since 4 is not in the array range (5, 8).

This is simple to implement in a straightforward way - 4 cases (range ascending + subrange descending, range descending + subrange descending ...), but I wonder if there's really an elegant solution ?!

Enjoy !

P.S: Naturally, golf answers will be also interesting.

Replies are listed 'Best First'.
Re: Code challenge: array subrange (updated with golf and corrections)
by demerphq (Chancellor) on Jan 13, 2005 at 09:54 UTC

    Heres my go. Im not sure i want to think about golfing while it needs to handle error cases. If we can assume that all inputs are valid (and a better input format) then golfing it might be interesting.

    Update: I didnt test my original solution properly. Its actually broken. Ive stuck it in a comment if you want to see my foolishness and i've posted a new version.

    The updated code. Ive posted it three times, pre-golf, golf with error handling, and golf without error handling. golf with error handling (including error message) is 180 chars, golf without error handling is 126. Ive not counted the sub declaration itself. (ie the sub NAME { } is excluded for the count)

    use strict; use warnings; use Data::Dumper; use Carp; sub subrange_pre_golf { my ($r1,$r2,$ary,$s,$f)=@_; ($s,$f)=(0,$#$ary) unless $s && $f; ($_<$s && $_<$f or $_>$s && $_>$f) and die "Bad range!" for $r1,$r2; my ($dx,$idx,@ret)=($r2 <=> $r1); $idx=($s < $f) ? -$s+$r1 : ($dx=-$dx,$s-$r1); while ( @ret <= abs($r2-$r1) ) { push @ret,$ary->[$idx]; $idx+=$dx; } return @ret; } # Excluding sub {} wrapper its 126 bytes. # 1 2 3 4 5 6 +7 #123456789012345678901234567890123456789012345678901234567890123456789 +012345678 sub subrange_no_error { my($p,$q,$Y,$s,$f)=@_;my($d,$i,@r)=($q<=>$p);$i=($s<$f)?-$s+$p:($d=-$ +d,$s-$p); push(@r,$Y->[$i]),$i+=$d while@r<=abs($q-$p);@r; } #180 bytes (counting newline used as mandatory whitespace as one char) sub subrange_golf_error { my($p,$q,$Y,$s,$f)=@_;my($d,$i,@r)=($q<=>$p);$i=($s<$f)?-$s+$p:($d=-$ +d,$s-$p); ($_<$s&&$_<$f||$_>$s&&$_>$f)&&die"Bad range!"for$p,$q;push(@r,$Y->[$i +]),$i+=$d while@r<=abs($q-$p);@r; } # this is now just a wrapper to subrange. Its just for testing and int +erface # compatibility sub arrange { my $href=shift; my @ret= subrange_golf_error(@{$href->{subrange}},$href->{arr},@{$hr +ef->{range}}); $href->{ret}=\@ret; unless (defined wantarray) { my $idx=$href->{range}[0]; my $dx=$href->{range}[1] <=> $href->{range}[0]; print "Subrange @{$href->{subrange}} of Array [". join(", ", map{ my $r="$idx:$_"; $idx+=$dx; $r } @{$href->{a +rr}}) ."] is <@ret>\n"; } else{ return wantarray ? @ret : \@ret; } } foreach my $t ([5,8],[8,5],[6,5],[6,7],[5,6],[7,6],[1,2],[8,9]) { foreach my $r ([8,5],[5,8]) { eval { arrange({ arr => [qw(cero uno dos tres)], range => $r, subrange =>$t }); 1 } or warn "Test @$t failed on range @$r:\n$@"; } }

    Cheers

    ---
    demerphq

Re: Code challenge: array subrange
by thor (Priest) on Jan 13, 2005 at 11:29 UTC
    Here's my stab:
    use strict; use warnings; print join(" ", array_range(['cero', 'uno', 'dos', 'tres'], [5, 8], [6, 5]) ), "\n"; sub array_range { my ($array, $range, $subrange) = @_; return () unless scalar(@$range) == 2; return () unless scalar(@$subrange) == 2; return () unless scalar(@$array) == $range->[1] - $range->[0] + 1; my $ascending = $subrange->[0] < $subrange->[1]; my @subrange = map {$_-$range->[0]} sort {$a <=> $b} @$subrange; my @subarray = @{$array}[ $subrange[0] .. $subrange[1] ]; return $ascending == 1 ? @subarray : reverse @subarray; }
    You may want to do something other than return an empty list on failure, but you get the idea.

    thor

    Feel the white light, the light within
    Be your own disciple, fan the sparks of will
    For all of us waiting, your kingdom will come

Re: Code challenge: array subrange
by Anonymous Monk on Jan 13, 2005 at 15:07 UTC
    sub extract { my %args = @_; my @arr = @{$args{arr}}; my ($bf, $bt) = @{$args{range}}; if ($bf > $bt) { ($bf, $bt) = ($bt, $bf); @arr = reverse @arr; } die "Out of range" unless @arr == $bt - $bf + 1; my ($from, $to) = @{$args{subrange}}; my @range = $from <= $to ? $from..$to : reverse($to..$from); die "Out of range" if $range[0] < $bf || $range[0] > $bt || $range[-1] < $bf || $range[-1] > $bt; local $" = ", "; my @a = eval "local \$[ = $bf; \@arr[@range]"; die $@ if $@; \@a; } my $a = extract arr => [qw /cero uno dos tres/], range => [5, 8], subrange => [6, 5]; print "$_\n" for @$a; __END__ uno cero
Re: Code challenge: array subrange
by dragonchild (Archbishop) on Jan 13, 2005 at 14:09 UTC
    sub ranger { my ($arr, $r, $sr) = @_; # Unneeded, plus it doesn't work. #local $[ = $r->[0]; $sr->[$_] -= $r->[0] for 0 .. 1; ($sr->[0] < $sr->[1]) ? @{$arr}[$sr->[0] .. $sr->[1]] : reverse( @{$arr}[$sr->[1] .. $sr->[0]] ); }

    Update: Upon actually trying the above code, I found it doesn't work like I thought it would. However, I found that I didn't need $[ at all.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

      local $[ = $r->[0]

      I had the same thought; localize $[ and let it do the work, and probably ran into the same problem. That sent me diving back into perlvar.

      We've had drilled into our heads not to use $[ with such a strong emphasis on DON'T that I at least had completely forgotten...

      As of release 5 of Perl, assignment to $[ is treated as a compiler directive, and cannot influence the behavior of any other file. (That's why you can only assign compile-time constants to it.)


      Dave

        Actually, $[ = $r->[0]; will work, but it required more work than I cared to do.
        sub ranger { my @arr = @{$_[0]}; my ($r1, $r2) = @{$_[1]}; my ($sr1, $sr2) = @{$_[2]}; my @v = eval <<__END_EVAL__; \$[ = $r1; ($sr1 < $sr2) ? \@arr[ $sr1 .. $sr2 ] : reverse \@arr[ $sr2 .. $sr1 ]; __END_EVAL__ return @v; }

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Re: Code challenge: array subrange
by Jasper (Chaplain) on Jan 13, 2005 at 12:49 UTC
    First stab with no error checking
    sub righter {$_[0]..$_[1],reverse(pop..pop)} sub array_range {
    sub righter {$_[0]..$_1,reverse(pop..pop)}
    $h = pop; @rel{ righter @{$h->{range}} } = @{$h->{arr}}; [@rel{ righter@{ $h->{subrange}} }] }
    Well, I didn't really consider where I was putting the sub - moved it outside to appease demerphq ;).

      You really shouldn't be declaring named subs inside of named subs in perl. Subs only nest properly in perl if the inner subs are anonymous.

      ---
      demerphq

      And with range checking (just got around to this now)
      sub r {$_[0]..$_[1],reverse(pop..pop)} sub array_range { $h=pop; @rel{ r@{ $h->{range} } } = @{ $h->{arr} }; [grep { defined() ? $_ : die "out of range" } @rel{ r@{ $h->{subra +nge}} }]; }
Re: Code challenge: array subrange
by Anonymous Monk on Jan 13, 2005 at 08:00 UTC
    Traditionally code challenges come with the issuer's solution, so where is yours?
      Mine is written in C++ so I didn't see it fit to put it here. Besides, as I mentioned my implementation is the straightforward one, so it's not really interesting.

      The algorithm is:

      1. Find how many elements to return in subrange. This is simply the abs() of the difference between the requested range's indices.
      2. Find out from which element of the original vector to start copying. This is the hairy one: 4 cases (array ascending & subrange descending, array descending & subrange ascending, etc.) In each case assert on range compatibility.
      3. Copy - a simple substring copy from the array to the returned array, starting with element from (1), the amount of chars from (2)