PWC 217

PWC 217

Challenge 1 (Sorted Matrix)

We are given a n by n matrix of numbers, and asked to report the third-smallest number in the matrix. 

The specification seems to allow arbitrary non-numeric elements too, but since all the test examples are numeric, I will restrict to numeric matrices. PDL is of course the go-to tool for this.

The core subroutine:

sub sorted_matrix {my ($pdl)=@_; $pdl=$pdl->flat->qsort; $pdl(2);}
 
The flat method flattens the matrix piddle to a vector piddle, qsort sorts the vector in ascending order, then we just return the third element.
 

Challenge 2 (Max Number)

We are given a list of positive integers of arbitrary lengths, and asked to concatenate them so as to produce the largest possible concatenated number. Thus, given 1 and 23, we would produce 231, not 123. 

To solve this, we exploit the fact that Perl can treat the elements interchangeably as numbers or as strings. We first sort the numbers using a routine that puts $b before $a if $b.$a is greater than $a.$b. Thus, we would sort (1,23) as (23,1) because 231 > 123.

The core snippet:

join '', sort { $b.$a <=> $a.$b } @list;

A simpler approach suggests itself as just the straight descending lexical sort {$b cmp $a}. But this fails for example with (1,10), which would be sorted as 10,1 not the desired 1,10.

The comparison function in sort

Let me briefly explain my own understanding of how comparison functions work in sort. The documentation can be a bit cryptic.

The general syntax of sort is:

sort f($a,$b) @list;

Here f($a,$b) is the comparison function. A comparison function can return -1, 0, or 1. Here $a and $b are standard package variables (global variables) that temporarily store two list elements being compared during the sort process.

If f($a,$b) returns -1, $a is placed before $b in the sorted list.

If f($a, $b) returns 1, $a is placed after $b in the sorted list.

If f($a,$b) returns 0, $a and $b would be tied in the sorted list (in any order in the sorted list but adjacent to each other or to other elements that return 0 when compared to either of them).

With the spaceship operator <=>:  $x<=>$y returns -1 if $x is less than $y, 1 if $x is greater than $y, and 0 if $x is numerically equal (==) to $y.

So setting f($a,$b) to $a <=> $b will sort in ascending order, while setting f($a,$b) to $b <=> $a will sort in descending order.

With the string comparison operator cmp: $x cmp $y returns -1 if $x is before $y in the dictionary ($x lt $y), 1 if  $x is after $y in the dictionary ($x gt $y), and 0 if the value of $x is the same string as the value of $y ($x eq $y).

We could rewrite the core snippet above as follows to make the logic more clear:

sub f {my ($x,$y)=@_; $y.$x <=> $x.$y}
join '', sort &f($a,$b) @list;

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