adamcrussell (adamcrussell) wrote,
adamcrussell
adamcrussell

Perl Weekly Challenge 009

This week's Perl Weekly Challenge presented a problem I hadn't really thought of before: how to do a ranking or what is mathematically referred to as a weak ordering.

Part 1



Sample Run
$ perl perl5/ch-1.pl
First square with five distinct digits: 12769 (= 113 * 113)



I think this was straightforward enough of a problem with a straightforward solution: start iterating through integers until you find one that has the property we want. The number must have a square root of at least 100 since it has at least five digits so that is our starting point. Counting the unique digits (see line 12) is done using a clever trick suggested by Prakash Kailasa via a Gabor Szabo Perl Maven blog. The trick is to create an anonymous hash with the values from the array as the keys. This will remove the duplicates since hash keys must be unique. Originally this could be done without the %{} around the map {$_ => 1} because for a time keys() could be applied to a hash reference however this is no longer allowed in perl-5.28.0 (I think it was removed in perl-5.14.0?).

Part 2

Sample Run

$ perl perl5/ch-2.pl
Name Score Rank
NEH 2 1
FED 3 2
OKN 3 2
DRZ 4 4
NPK 5 5
XRK 5 5
WXV 7 7
QHC 9 8
IEE 10 9
CYP 10 9
================
NEH 2 1
FED 3 3
OKN 3 3
DRZ 4 4
NPK 5 6
XRK 5 6
WXV 7 7
QHC 9 8
IEE 10 10
CYP 10 10
================
NEH 2 1
OKN 3 2
FED 3 2
DRZ 4 3
XRK 5 4
NPK 5 4
WXV 7 5
QHC 9 6
CYP 10 7
IEE 10 7




This presented some nice opportunities for creativity. It's a standing rule, as far as I know, that if a challenge statement has any ambiguity than you can simply interpret it as you like. This leads to solutions having a variety of styles and flavors. The problem statement didn't suggest what in particular we should rank so I decided to do a ranking of basic Perl objects. These are stored in an array, sorted, and then sent to the ranking functions. The sorting and ranking functions were written as generically as possible to allow for any sort of object as long as it has an accessor that returns a single numeric value. A rare bit of explicitly polymorphic code in Perl.

I think that the ranking logic would have been a little less convoluted with a better choice of data structures. I think a doubly linked list (i.e. with forward and previous references) would have been best. Still, the Standard and Dense rankings did not cause too much trouble to implement. The Modified ranking was the most complex. A concise definition from Wikipedia is that, for the Modified ranking, each item's ranking number is equal to the number of items ranked equal to it or above it. But what about ties for first place? And multi-way ties? Based on the sample output shown I think I achieved all the goals of the modified ranking but this is a good example of having someone else check your work! Especially a domain expert, someone who may have worked with this ranking many times in the past. Some searches didn't reveal much use of the Modified ranking. I did find a suggestion on how to address ties for first in Modifed Ranking here. Overall documentation of examples implementing the Modified ranking was otherwise not turning up in my searches.

I did make use of a core module which I do not ordinarily use, Tie::RefHash. For this particular problem I found it convenient to use the object references as hash keys and to do so requires the use of this module.

Tags: #perl
Subscribe
Comments for this post were disabled by the author