March 2020 – Programming Excursions in Perl and Raku

THE WEEKLY CHALLENGE – PERL & RAKU #53

TASK #1

Rotate Matrix

Write a script to rotate the followin matrix by given 90/180/270 degrees clockwise.

[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]

For example, if you rotate by 90 degrees then expected result should be like below

[ 7, 4, 1 ]
[ 8, 5, 2 ]
[ 9, 6, 3 ]

Method

The are two basic ways to proceed with this challenge, to either write three routines to perform each of the three actions, or write one routine to rotate the matrix 90° clockwise and apply it one, two or three times.

As both require a routine to rotate 90° clockwise, I started there. As we are given a 3×3 matrix written in brackets, we could just encode the matrix as an array with 9 elements and use a fixed mapping of the indices to indicate where to move each element into a new output list in a single pass over the data. This method would be quite fast if we need to do this transform many times or over a large matrix. For a 3×3 it seems a bit like cheating, so I chose to use loops to read and rewrite the data in a structured way.

It appears that the matrix is given as an array of arrays, so we’ll use that. What we need to do resembles a zip routine, taking first the first element of each array, then the second, etc, and rewriting each set to a new row. Pushing the data onto a new row results in an incorrect, reversed mapping, but if we use unshift instead, we write the new rows from the end first and the elements end up in the right order.

This code is clean and tight, but is it wasteful to both loop through each element of each sub array and then repeat this again and possibly a third time depending on how far we wish to rotate? Unable to resolve this existential crisis I have decided to impliment both methods, and see what the differences are in the routines.

To rotate 270°, or 90° CCW, it turns out we need to write the rows using push, but build the array of completed rows from the end, using unshift. Thus the rows are forward, but the columns reversed.

To rotate 180°, we don’t need the zip behavior, and only need to reverse each row as is and unshift these rows onto the output, which reverses the columns.

As now the work is done it seems there’s no harm in keeping all three routines around to perform exactly the transformations we require.

Perl Solution

[colincrain:~/PWC]$  perl 53_1_rotator.pl 
 start:

1, 2, 3
4, 5, 6
7, 8, 9

 once:

7, 4, 1
8, 5, 2
9, 6, 3

 twice:

9, 8, 7
6, 5, 4
3, 2, 1

 thrice:

3, 6, 9
2, 5, 8
1, 4, 7

 180:

9, 8, 7
6, 5, 4
3, 2, 1

 270:

3, 6, 9
2, 5, 8
1, 4, 7

use warnings;
use strict;
use feature ":5.26";


## ## ## ## ## MAIN:

my $matrix = [  [ 1, 2, 3 ], 
                [ 4, 5, 6 ],
                [ 7, 8, 9 ]   ];

## do a variety of transformation options
my $once     = rotate90( $matrix );
my $twice    = rotate90(rotate90($matrix));
my $thrice   = rotate90(rotate90(rotate90($matrix)));

my $oneeight = rotate180( $matrix );
my $twoseven = rotate270( $matrix );

## some overtly, perhaps overly, verbose reporting of the results:
say " start:\n";
say (join ', ', $_->@*) for $matrix->@*;

say "\n once:\n";
show_matrix( $once );

say "\n twice:\n";
show_matrix( $twice );

say "\n thrice:\n";
show_matrix( $thrice );

say "\n 180:\n";
show_matrix( $oneeight );

say "\n 270:\n";
show_matrix( $twoseven );


## ## ## ## ## SUBS:

sub rotate90 {
## matrix is an array ref of array refs
## zip and reverse subarray elements
    my $matrix = shift;
    my $output;
    
    my $cols = scalar $matrix->[0]->@*;  ## subarray elements, or num of cols
    my $rows = scalar $matrix->@*;       ## array elements,    or num of rows
    
    for my $idx ( 0..$cols-1 ) {         ## for each index in a row
        my @newrow; 
        for my $row ( 0..$rows-1 ) {     ## for each row
            unshift @newrow, $matrix->[$row]->[$idx];        ## reverse rows
        }
        push $output->@*, \@newrow;                          ## forward cols
    }    
    return $output;    
}

sub rotate180 {
## matrix is an array ref of array refs
## reverse each subarray, then reverse the outer array
    my $matrix = shift;
    my $output;
        
    for my $row ( $matrix->@* ) {           
        my @newrow = reverse $row->@*;        
        unshift $output->@*, \@newrow;
    }    
    return $output;    

}

sub rotate270 {
## matrix is an array ref of array refs
## zip and reverse subarrays in outer array
    my $matrix = shift;
    my $output;
    
    my $cols = scalar $matrix->[0]->@*;  ## subarray elements, or num of cols
    my $rows = scalar $matrix->@*;       ## array elements, or num of rows
    
    for my $idx ( 0..$cols-1 ) {            
        my @newrow; 
        for my $row ( 0..$rows-1 ) {        
            push @newrow, $matrix->[$row]->[$idx];     ## forward rows   
        }
        unshift $output->@*, \@newrow;                 ## reverse cols
    }   
    return $output;    
}

sub show_matrix { 
## print the array data structure in grid form
    say (join ', ', $_->@*) for $_[0]->@* 
}

Raku Solution

Raku has powerful list routines built in so we can use those instead of the explicit loops in the Perl example. I love working with lists as a functional unit, I really do. The list processing functions are absurdly powerful and a joy to use.

Between zip, map, reverse and the reduction metaoperator we can perform any of the required rotation operations quite succinctly.

90°: To rotate 90° CW, we need to swap rows and columns, then reverse the column order. So we need to take the first elements of each subarray, a column, and make a new subarray, or row out of them, and apply this to each set of elements in turn. We will use a combination of infix Z, the reduction metaoperator [] and the list operator (,) to construct a combined “superoperator” (not a real term) [Z,] that does everything we want. Sort of. Applying just this step to our starting matrix results in

1  4  7
2  5  8
3  6  9

which is close but our column order is reversed.

[Z,] $matrix.reverse

reversed our rows first, which later become our columns, and solves that problem nicely.

180°: To rotate 180°, we need to reverse each row, then reverse the columns. So no zipping is required, and we already have the subarrays we will need. We will need to look at each subarray and reverse it, so we will use map with a reverse to do this. Then we can reverse the outer array, which nicely chains to:

$matrix.map({.reverse}).reverse

270°: To rotate 90° CCW, again we need to swap row and columns, but in this case we will leave the column order as is and reverse the column data. We do this by reversing the individual subarrays first using map, much as we did for 180°. We then apply the combined metaoperator [Z,] as we did for 90°. Putting it all together results in

[Z,] $matrix.map:{.reverse}

Which does what we need.

sub MAIN () {

    my $matrix = [  [ 1, 2, 3 ], 
                    [ 4, 5, 6 ],
                    [ 7, 8, 9 ]   ];

    'start'.say;
    show-matrix $matrix;
        
    ''.say;
    '90'.say;
    show-matrix [Z,] $matrix.reverse;

    ''.say;
    '180'.say;
    show-matrix $matrix.map({.reverse}).reverse;
    
    ''.say;
    '270'.say;
    show-matrix [Z,] $matrix.map:{.reverse};
    

} 

sub show-matrix ( $matrix ) { 
    .join('  ').say for $matrix.list;
}

TASK #2

Vowel Strings

Write a script to accept an integer 1 <= N <= 5 that would print all possible strings of size N formed by using only vowels (a, e, i, o, u).

The string should follow the following rules:

‘a’ can only be followed by ‘e’ and ‘i’.
‘e’ can only be followed by ‘i’.
‘i’ can only be followed by ‘a’, ‘e’, ‘o’, and ‘u’.
‘o’ can only be followed by ‘a’ and ‘u’.
‘u’ can only be followed by ‘o’ and ‘e’.

For example, if the given integer N = 2 then script should print the following strings:

ae
ai
ei
ia
io
iu
ie
oa
ou
uo
ue

Method

Well just to get this out of the way:

chaos, audio, teal, video, deuce, poet, coin, dual, guide

not to mention

bazaar, teen, skiing, cool, and vacuum

The practical upshot being, the rules stated in the challenge are just rules that resemble the way vowels group in English, and don’t really reflect the way this crazy mixed-up language actually works. But this is all just in fun, right? So who cares? In any case a part of me needed to make that list, just to be clear that up.

Incidently, it was only the ‘aa’ combination that was difficult to come up with, avoiding obscure loan words (think Dutch, or, you know, Afrikaans). So “krall” almost made the cut, because I know some South Africans (think “corral”). “Aarkvark” is also Afrikaans but rather more well-known. “Bazaar” has remarkably been around since the 16th century and is part of the name of a popular magazine, so that wins out. It may well be the only candidate that fits those criteria.

So the rules are just some rules, but that doesn’t make them less important; they define connections of the data set. We start with the five most common vowels, as apparently we’re ignoring “y” and “w” as well.* Moving on, moving on…

The problem becomes, like many, a problem of structuring data. The core components are a list of vowel combinations and a mapping of letters to an array of next letter possibilities. We transverse the list, shifting off elements of a given length and looking at the last letter in the string, adding new combinations to the end of the list as we go. By carefully keeping track of the indices, we can shift off a complete set of strings of a given length, then repeat the process to add another letter until our output strings are the desired length.

The method works for any positive vowel string length, not just 1 <= n <= 5 as required, but as the output grows exponentially, things get out of hand quickly.

comment: The question of how the list of solutions grows is an interesting one. I made a little meta-analytical loop wrapper and solved for 1..15, only counting the solutions rather than printing them out, with results summarized below:

 n     clusters
----+--------                
 1     5 
 2     11 
 3     23 
 4     50 
 5     107 
 6     230 
 7     494 
 8     1061 
 9     2279 
10     4895 
11     10514 
12     22583 
13     48506 
14     104186 
15     223781

The sequence is clearly exponential, but exactly how that growth progresses is not obvious.

One fairly expeditious way to proceed is to just give WolframAlpha the data and have it do a least-squares fit:

exponential fit 5,11,23,50,107,230,494,1061,2279,4895,10514,22583,48506,104186,223781

through which we find a good approximation can be made by the equation:

f(x) = 2.34215 e^0.76449x

R² = 1.

So:

f(20) = 10,230,300 to 6 significant digits
clusters(20) = 10,239,398 the actual count computed

With a little over 10 million results for n=20 the computational effort is becoming impractical. However if we double the length to n=40 things have just exploded:

f(40) = 44,685,500,000,000

It does seem exponential growth is all the rage these days, no?

For the record, I look forward to day I figure out how to use “cwtch” in a sentence in an unforced manner. “Why” you ask? See what I did there? Why does only “y” get the love? Cwtch has been in the OED since 2005. Unlike “cwm”, being a rather obscure name for the rounded divit at the end of a valley, a cwtch means the special comfort of a hug from a loved one. Now there’s a word the world needs if I ever heard one.

Perl Solution

[colincrain:~/PWC]$  perl 53_2_vowel_wow_wow.pl 3
aei
aia
aie
aio
aiu
eia
eie
eio
eiu
iae
iai
iei
ioa
iou
iuo
iue
oae
oai
ouo
oue
uoa
uou
uei

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

my $length = shift @ARGV || 20;

my @output = qw( a e i o u );
my %following = (  a => [ qw( e i     ) ],
                   e => [ qw( i       ) ],
                   i => [ qw( a e o u ) ],
                   o => [ qw( a u     ) ],
                   u => [ qw( o e     ) ]     );
my $count = 1;

while ($count < $length)    {
    my $num_clusters = scalar @output;              ## memoize this now because we will add elements
    for (1..$num_clusters) {
        my $vowel_cluster = shift @output;          ## shift off a cluster
        my $vowel = substr $vowel_cluster, -1, 1;   ## get the last letter
        for ($following{$vowel}->@*) {              ## build new combinations from that letter
            push @output, "$vowel_cluster" . "$_";  ## and add them to the end of the list
        }
    }
    $count++;                                       ## keep track of the cluster length
}

say $_ for @output;

Raku Solution

sub MAIN (Int:D $length where {$length > 0} = 3) {
    my @output    = qw< a e i o u >;
    my %following =  a => qw< e i     > ,
                     e => qw< i       > ,
                     i => qw< a e o u > ,
                     o => qw< a u     > ,
                     u => qw< o e     > ;
    my $count = 1;
    
    while $count < $length {
        my $num_clusters = @output.elems; 
        for ^$num_clusters {
            my $vowel_cluster = @output.shift;
            my $vowel = substr $vowel_cluster, *-1, 1;
            for %following{$vowel}.list {
                @output.push: $vowel_cluster ~ $_;
            }
        }
        $count++;
    
    }

    .say for @output;
}

Month: March 2020

Spinning Matrices, Stringing Vowels

THE WEEKLY CHALLENGE – PERL & RAKU #53

TASK #1

Rotate Matrix

Method

Perl Solution

Raku Solution

TASK #2

Vowel Strings

Method

Perl Solution

Raku Solution