PWC 235

I tried to restrict to Perl 4 syntax for both challenges this week, as documented in Rex Swain's Perl 4 reference or the 1st edition of Programming perl. I do use nested subroutines, which I am not sure would actually work in Perl 4, though they comply with the syntax. My programs are tested on Perl 5.38. (The -l in the shebang line works only in Perl 5. The Perl 4 equivalent was -L012 [in Unix], which is no longer available.) 

Update and disclaimer: These programs will not work on Perl 4 as I discovered later when I found and installed a Perl 4.019 executable. For one thing, the ability to assign a subroutine to a locally scoped typeglob was not available in Perl 4.

My solutions to this week's challenges highlight the usefulness of the splice array operator.

Challenge 1 (Remove One)

We are given an array of integers and asked to verify if removing any one element will leave the remaining elements in monotonically ascending order.

A helper sub-subroutine &ascending checks if a particular array is in ascending order, by comparing it element-by-element to its sorted version. Here it is:

    local *ascending = sub {
        local @ascending=(sort {$a <=> $b} @_);
        foreach (0 .. $#_) {($_[$_]==$ascending[$_]) || (return 0)}
        return 1;
    };

Then the main part of the subroutine. This loops through the indices of the input array, using splice to delete the current element from a temporary copy of the input, and then checks if the result is in ascending order by calling &ascending. If it is, then we are through and return 1. If we have looped through the whole array without success, we return 0.

sub remove_one {
    #-- helper sub
    ...

    #-- trunk of sub
    foreach (0 .. $#_){
        local @remove_one = @_;
        splice(@remove_one,$_,1);
        &ascending(@remove_one) && (return 1);
    }
    return 0;
}

Challenge 2 (Duplicate Zeros)

We are given a list of integers of length n. We are asked to duplicate every instance of zero in the input list, and return the first n items in the resulting list.

Again, splice comes in handy. Here is my subroutine.

sub duplicate_zeros {
    local $duplicate_zeros = $#_;
    local @duplicate_zeros = ();
    foreach (0 .. $#_){($_[$_]==0) && (push @duplicate_zeros,$_) }

    foreach (0 .. $#duplicate_zeros) {
        ($_ > $duplicate_zeros) && (last);
        splice(@_,$duplicate_zeros[$_],0,0);
        foreach ($_ .. $#duplicate_zeros) {
            $duplicate_zeros[$_]++;
        }
    }
    @_[0 .. $duplicate_zeros];
}

We create a list @duplicate_zeros that stores the indices of all the zero-valued elements in the input array. Then we loop through @duplicate_zeros, at each step $_ using splice to insert an additional zero in the input array at the $_ position, and then incrementing all the remaining elements in @duplicate_zeros by 1 (to reflect the index for a zero moving to the right in the input array). Finally, we return the required sub-list. We had stored the length of the original input array at the start.