Rank? Take note, this is probably the only time I’m evoking Lynyrd Skynyrd.
Onward to Perl Weekly Challenge 260!
Task 1: Unique Occurrences
You are given an array of integers, @ints.
Write a script to return 1 if the number of occurrences of each value in the given array is unique or 0 otherwise.
Example 1
Input: @ints = (1,2,2,1,1,3)
Output: 1
The number 1 occurred 3 times.
The number 2 occurred 2 times.
The number 3 occurred 1 time.
All occurrences are unique, therefore the output is 1.
Example 2
Input: @ints = (1,2,3)
Output: 0
Example 3
Input: @ints = (-2,0,1,-2,1,1,0,1,-2,9)
Output: 1
Approach
This immediately says hashes to me: a hash to count the number of times each integer occurs, and another hash to track whether a particular integer count occurs more than once.
Raku
sub uniqueOccurrences(@ints) {
my %counts;
for @ints -> $i {
# count how many time each int occurs
%counts{$i}++;
}
my %seen;
for %counts.kv -> $i, $c {
# if we've seen this count before, return 0
return 0 if %seen{$c}:exists;
%seen{$c} = $i;
}
# each count was unique
return 1;
}
$ raku/ch-1.raku
Example 1:
Input: @ints = (1, 2, 2, 1, 1, 3)
Output: 1
Example 2:
Input: @ints = (1, 2, 3)
Output: 0
Example 3:
Input: @ints = (-2, 0, 1, -2, 1, 1, 0, 1, -2, 9)
Output: 1
View the entire Raku script for this task on GitHub.
Perl
The big change from Raku to Perl is going from for %counts.kv -> $i, $c to while ( my($i, $c) = each %counts ):
sub uniqueOccurrences(@ints) {
my %counts;
foreach my $i ( @ints ) {
# count how many time each int occurs
$counts{$i}++;
}
my %seen;
while ( my($i, $c) = each %counts ) {
# if we've seen this count before, return 0
return 0 if exists $seen{$c};
$seen{$c} = $i;
}
# each count was unique
return 1;
}
View the entire Perl script for this task on GitHub.
Python
As always, when I’m counting things in Python, I use the Counter type in the collections module.
from collections import Counter
def uniqueOccurrences(ints):
counts = Counter()
for i in ints:
# count how many time each int occurs
counts[i] += 1
seen = {}
for i, c in counts.items():
# if we've seen this count before, return 0
if c in seen: return 0
seen[c] = i
# each count was unique
return 1
View the entire Python script for this task on GitHub.
Task 2: Dictionary Rank
You are given a word, $word.
Write a script to compute the dictionary rank of the given word.
Example 1
Input: $word = 'CAT'
Output: 3
All possible combinations of the letters:
CAT, CTA, ATC, TCA, ACT, TAC
Arrange them in alphabetical order:
ACT, ATC, CAT, CTA, TAC, TCA
CAT is the 3rd in the list.
Therefore the dictionary rank of CAT is 3.
Example 2
Input: $word = 'GOOGLE'
Output: 88
Example 3
Input: $word = 'SECRET'
Output: 255
Approach
This feels akin to the first task: operate on the list (of characters, this time) to produce another list, and the analyze the second list in some way. Here, we’re breaking a string into characters, producing all the permutations of those characters as new strings, then sorting them and seeing how far down the sorted list the original string appears.
Raku
In Raku, there’s a permutations method on the List type to do the heavy lifting:
sub dictionaryRank($word) {
# split the string into an array of characters
my @letters = $word.split('', :skip-empty);
# find the permutations of the letters
my @perms;
for @letters.permutations -> @l {
@perms.append(@l.join(''));
}
# find where in the sorted list of
# permutations the word is
my $rank = 1;
for @perms.unique.sort -> $p {
return $rank if $p eq $word;
$rank++;
}
}
$ raku/ch-2.raku | less
Example 1:
Input: $word = 'CAT'
Output: 3
Example 2:
Input: $word = 'GOOGLE'
Output: 349
Example 3:
Input: $word = 'SECRET'
Output: 509
But wait! GOOGLE and SECRET are supposed to be 88 and 255, not 349 and 509. What gives? Let’s look at what @perms.sort looks like by adding say @perms.sort.raku; right after we build the array…
Example 2:
Input: $word = 'GOOGLE'
("EGGLOO", "EGGLOO", "EGGLOO", "EGGLOO", "EGGOLO", "EGGOLO",
"EGGOLO", "EGGOLO", "EGGOOL", "EGGOOL", "EGGOOL", "EGGOOL",
"EGLGOO", "EGLGOO", "EGLGOO", "EGLGOO", "EGLOGO", "EGLOGO",
"EGLOGO", "EGLOGO", "EGLOOG", "EGLOOG", "EGLOOG", "EGLOOG",
"EGOGLO", "EGOGLO", "EGOGLO", "EGOGLO", "EGOGOL", "EGOGOL",
...
Oh! I see what’s happening! It wants all the unique combinations! Fortunately, Raku has a unique method for just that.
sub dictionaryRank($word) {
# split the string into an array of characters
my @letters = $word.split('', :skip-empty);
# find the permutations of the letters
my @perms;
for @letters.permutations -> @l {
@perms.append(@l.join(''));
}
# find where in the sorted list of
# UNIQUE permutations the word is
my $rank = 1;
for @perms.unique.sort -> $p {
return $rank if $p eq $word;
$rank++;
}
}
$ raku/ch-2.raku | less
Example 1:
Input: $word = 'CAT'
Output: 3
Example 2:
Input: $word = 'GOOGLE'
Output: 88
Example 3:
Input: $word = 'SECRET'
Output: 255
View the entire Raku script for this task on GitHub.
Perl
Perl, however, doesn’t have the same built-in features, so we need to rely on CPAN modules. For uniqueness, I’m using uniq from List::Util, and for permutations, I’m using Algorithm::Combinatorics’ permutations function, like I did back in PWC 244.
use Algorithm::Combinatorics qw( permutations );
use List::Util qw( uniq );
sub dictionaryRank($word) {
# split the string into an array of characters
my @letters = split //, $word;
# find the permutations of the letters
my @perms;
foreach my $l ( permutations(\@letters) ) {
push @perms, join('', @$l);
}
# find where in the sorted list of
# UNIQUE permutations the word is
my $rank = 1;
foreach my $p ( sort { $a cmp $b } uniq @perms ) {
return $rank if $p eq $word;
$rank++;
}
}
View the entire Perl script for this task on GitHub.
Python
Again, like I did in PWC 244, I’m using itertools, but this time it’s the permutations function.
def dictionaryRank(word):
# we don't need to split the string, because
# permutations() will accept a string as a parameter
#
# set() produces a set of unique elements
#
# sorted() returns a sorted list
perms = sorted(
set([ ''.join(l) for l in permutations(word) ])
)
rank = 1
for p in perms:
if p == word: return rank
rank += 1
View the entire Python script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-260/packy-anderson