PWC 249

Challenge 1 (Equal pairs)

We are given a list of integers with an even number of elements.

We are asked to check if the list can be completely divided into sub-lists of size 2 with each sub-list containing the same integer repeated, like say (2,2). If so, we are asked to return the list of such sub-lists.

This is straightforward in Perl 5. I use modern conveniences this time, though it could be done using only primitive Perl 4 syntax. Here is my subroutine. It returns a list of array references.

local *equal_pairs = sub {
    #-- return () if input is of odd length
    ((scalar(@_) % 2) > 0) && (return ());
    
    #-- count number of occurrences of each element using a hash
    local %_ = ();
    map {$_{$_}++} @_;
    
    #-- if any element occurs an odd number of times, return ()
    (grep {($_{$_} % 2) > 0} keys %_) && (return ());
    
    #-- loop thru %_ keys, returning pairs of such keys
    map {
        my $k=$_;
        my $num_pairs=( ($_{$k}) / 2 );
        map {
            [$k, $k]
        } 1 .. $num_pairs;    
    }
    keys %_;    
};

Challenge 2 (DI string match)

We are given a string say str consisting only of the letters 'D' or 'I'. We are asked to create a list of the numbers between 0 and length(str) inclusive, say perm, such that for perm[i] for i between 0 and length(str)-1:

(substr(str,i,1) eq 'D') && (perm[i] > perm[i+1]);

(substr(str,i,1) eq 'I')  && (perm[i] < perm[i+1]);

Probably D and I are meant as mnemonics for 'Decreasing' and 'Increasing' order respectively.

To solve this challenge, we loop through the indices i, keeping track at each step of the highest and lowest number respectively that can be assigned to perm[i]. 

If the character at position i in str is 'D', we assign to perm[i] the highest available number, guaranteeing that the number to be assigned to perm[i+1] in the next step will be lower. We then decrement by 1 the temporary variable tracking the highest available number.

Conversely, if the character at position i in str is 'I', we assign to perm[i] the lowest available number, guaranteeing that the number to be assigned to perm[i+1] in the next step will be higher. We then increment by 1 the temporary variable tracking the lowest available number.

Since our output list perm has a length that is one more than the length of str, we will have one extra step, where we just push to the last position in str the current highest or lowest available number (which should both be the same number at this point).

Here is my subroutine. Again, I do not stick to Perl 4 syntax this time.

local *DI_string_match = sub {
    my $str = $_[0];
    
    #-- return 0 (error) if input is not D or I only
    ($str =~ /^[DI]+$/) || (return 0);

    #-- create mutable temp vars containing highest and lowest indices
    my ($lowest,$highest)=(0, length($str));
    
    #-- loop through $str indices,
    # if str[i] is 'D', assign highest in output[i] and decrement it
    # if str[i] is 'I', assign lowest in output[i] and increment it

    my @retval = (); #-- return value
    map {
        (substr($str,$_,1) eq 'D') ?

        ($retval[$_] = $highest--) :
        ($retval[$_] = $lowest++);
    }
    0 .. length($str)-1;
    ($lowest==$highest) || die "Something wrong ...$!";
    $retval[length($str)] = $highest; #-- last item left
    @retval;
};