PWC 220

PWC 220

I switched to Raku this week. Both challenges are easier to tackle with Raku.

Challenge 1 (Common characters)

We are given a list of words, and asked to return a sorted list of the characters that are found in every word in the list (ignoring case). Here is the subroutine:

sub common_characters( @words ) {
    [(&)] @words.map( {$_.lc.comb.Set} )
}

For each word in @words, lowercase it, then split into characters, then store each unique character in a set. Then working on the resulting list of sets, call the reduce meta-operator [..] on the set intersection "(&)" operator, i.e., call [(&)] or "reduce using intersection" on the list of sets, to get the intersection of every set, or the characters that are found in every set. This returns a set, whose say method automatically prints the elements in sorted order (one of the task specifications).

Challenge 2 (Squareful)

We are given a list of integers @ints say. We are asked to identify every permutation of the list where every pair of adjacent elements adds up to a perfect square.

One could use an easy-to-code brute force approach where we check the condition for every possible permutation, though this is O(N!) and does not scale well. Somewhat more difficult is an O(N^2) approach that finds every pair of elements in @ints that adds up to a perfect square, and then uses this to construct the required permutations. 

I use the easy approach since all the test examples have just 3 elements, though I explicitly restrict my Raku subroutine to lists with three elements, to signal that the approach will not scale up. Here is my squareful subroutine with a couple of helper subroutines:

multi sub is_perfect_square( Int $a, Int $b ) {
    ($a+$b).sqrt %% 1;
}

multi sub is_perfect_square( @ints ) {
    ( [&&] (0 .. @ints-2).map( {&is_perfect_square( @ints[$_], @ints[$_+1] ) } ) );   
}

sub squareful (@ints where @ints.elems==3) {
    @ints.permutations.unique( :with(&[eqv]) ).grep( {$_.&is_perfect_square} );
}

The subroutine &is_perfect_square taking two integer arguments checks if their sum is a perfect square. The subroutine &is_perfect_square taking an array as argument checks if every pair of adjacent elements adds up to a perfect square (by calling &is_perfect_square on each pair of adjacent elements). Finally, the subroutine &squareful calls &is_perfect_square on every permutation of @ints, and returns a list of those permutations that return True. This list can potentially contain duplicates, since the Raku permutations operator treats identical elements of a list as if they are different elements, so that for example,  (2,2,2).permutations returns six (identical) permutations rather than just a single permutation. So we call unique to eliminate duplicates.


Comments

Post a Comment

Popular posts from this blog

PWC 227

PWC 227 Challenge 1 (Friday 13th) This challenge requires us to count the number of times Friday 13th occurs in a particular year. I use Date::Manip. This module probably has easier ways to do this using a Date Range, but my approach is easy enough. My &friday_13th subroutine takes the year as input, throws an exception if it is outside the specified range (1753 to 9999), and then cycles through the 13th of each month, counting the Fridays. use Date::Manip; my $dateobj=Date::Manip::Date->new(); sub friday_13th {     my ($year)=@_;     my $retval=0;     ( ($year > 9999) || ($year < 1753) ) &&         die "Year should be between 1753 and 9999";     map {         ( ($dateobj->new_date("$year-$_-13")->printf('%w') ) == 5 ) &&             $retval++;     }     1 .. 12;          $retval; }   Challenge 2 (Roman Maths) This challenge requires us to implement a calculator that parses infix math operations using roman numerals.  There
Read more

PWC 234

PWC 234 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.) As I have mentioned before, my aims in using the old syntax are just mild nostalgia plus to add a bit of additional challenge to the task. I know that this is not the most efficient or idiomatic way to do things today. But I should observe that it is really cool that I am able to write code using 30-year old syntax, and run it unmodified on the latest Perl 5.38. You cannot do this with Python 3 for example. This very deep backward compatibility is one of those unsung underappreciated beauties of Perl 5. In my opinion, it is a very cool thing in
Read more

PWC 249

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}
Read more