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 258

PWC 258 Last week (#257) I finished challenge 2 and my blog post for challenge 257 late last week, so had only submitted challenge 1. Here is my blog post for PWC 257 , including the full code for my challenge 2 solution. This week, I have done both challenges in perl 4.019 on DOSBOX. Both scripts also work fine on the latest Perl 5.38. I also did the challenges in Raku, where they are one-liners.  Challenge 1 (Count Even Digits Number) We are given a list of integers, and asked to count the number of elements whose base-10 representation has an even number of digits. In Raku , this is a one-liner. Here it is: raku -e 'say +@*ARGS.grep({$_.chars %% 2})' $@ It could be a one-liner in Perl 4 too, but since I run it on DOSBOX, my script would not be a bash shell script. Here is the short subroutine that does the job.  sub count_even_digits {  scalar( grep( ((length($_) % 2) == 0), @_) ); } The full code is here . Challenge 2 (Sum of values) We are given an integer k  and a list 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

PWC 253

PWC 253 I do both challenges this week using old software on DOSBOX: perl 4.019, and for comparison, also python 1.4 beta. My solutions also work on the current versions of Perl 5 (5.38) and Python 2 (2.7.18) respectively. Challenge 1 (Split Strings) Links to code: perl4.019 python1.4b We are given a list of strings, and a single character say sep . We are asked to return the list, with the strings split into component substrings using sep as a separator. We should not include any empty strings in the output. In perl 4, I first stick a backslash in front of the separator character, so that it is escaped if entered in a regex. This is because the perl split function takes a regex as its first argument indicating the separator. If we have a character like '$' or ',', we want to escape it so that it is read literally when parsing the regex. Here is the key subroutine:   sub split_strings {  local ($separator, @words)=@_;  local (@retval)=(); #array to be returned  #  #--
Read more