Ok, I don’t get to choose what music my brain pushes at me when I look at these challenges. Because my wife is performing in a production of Beehive: The 60’s Musical, one of the songs she gets to do is Try by Janis Joplin.
My wife does Janis proud.
But on to this week’s Challenge!
Task 1: Count Smaller
You are given an array of integers.
Write a script to calculate the number of integers smaller than the integer at each index.
Example 1
Input: @int = (8, 1, 2, 2, 3)
Output: (4, 0, 1, 1, 3)
For index = 0, count of elements less 8 is 4.
For index = 1, count of elements less 1 is 0.
For index = 2, count of elements less 2 is 1.
For index = 3, count of elements less 2 is 1.
For index = 4, count of elements less 3 is 3.
Example 2
Input: @int = (6, 5, 4, 8)
Output: (2, 1, 0, 3)
Example 3
Input: @int = (2, 2, 2)
Output: (0, 0, 0)
Approach
This is another double-loop over a single array, like last week. The outer loop (let’s call it the i loop) iterates over each of the elements in the array to produce the count for that index. The inner (j) loop iterates over each of the elements again and compares them to the i element. Easy-peasy.
Raku
sub countSmaller(@int) {
my @counts;
for 0 .. @int.elems - 1 -> $i {\
for 0 .. @int.elems - 1 -> $j {
@counts[$i]++ if @int[$j] < @int[$i];
}
}
return @counts;
}
But when I ran this, I got
$ raku/ch-1.raku
Example 1:
Input: @int = (8, 1, 2, 2, 3)
Use of uninitialized value @output of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful.
in sub solution at raku/ch-1.raku line 17
Output: (4, , 1, 1, 3)
Example 2:
Input: @int = (6, 5, 4, 8)
Use of uninitialized value @output of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful.
in sub solution at raku/ch-1.raku line 17
Output: (2, 1, , 3)
Example 3:
Input: @int = (2, 2, 2)
Output: ()
What was going on here? Time to add some debugging:
sub countSmaller(@int) {
my @counts;
for 0 .. @int.elems - 1 -> $i {
for 0 .. @int.elems - 1 -> $j {
@counts[$i]++ if @int[$j] < @int[$i];
}
}
say @counts.raku;
return @counts;
}
$ raku/ch-1.raku
Example 1:
Input: @int = (8, 1, 2, 2, 3)
[4, Any, 1, 1, 3]
Use of uninitialized value @output of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful.
in sub solution at raku/ch-1.raku line 18
Output: (4, , 1, 1, 3)
Example 2:
Input: @int = (6, 5, 4, 8)
[2, 1, Any, 3]
Use of uninitialized value @output of type Any in string context.
Methods .^name, .raku, .gist, or .say can be used to stringify it to something meaningful.
in sub solution at raku/ch-1.raku line 18
Output: (2, 1, , 3)
Example 3:
Input: @int = (2, 2, 2)
[]
Output: ()
Ahhh! I see what’s happening: because I’m only incrementing the @counts[$i] value if @counts[$j] is smaller, then if none of the values are smaller, I never autovivified the value for that element. In Perl, the value would be undef, but in Raku, it’s Any. There’s an easy way to fix this: just initialize @counts[$i] to 0 before the $j loop:
sub countSmaller(@int) {
my @counts;
for 0 .. @int.elems - 1 -> $i {
@counts[$i] = 0;
for 0 .. @int.elems - 1 -> $j {
@counts[$i]++ if @int[$j] < @int[$i];
}
}
return @counts;
}
But something was bothering me. Coming from Perl, I have to say I like $#int better than @int.elems - 1. There should be a Raku-ish way to get the index of the last element in a list. I seem to recall seeing it once. And, after a bit of searching, I found it again: .end.
sub countSmaller(@int) {
my @counts;
for 0 .. @int.end -> $i {
@counts[$i] = 0;
for 0 .. @int.end -> $j {
@counts[$i]++ if @int[$j] < @int[$i];
}
}
return @counts;
}
Then I saw there’s something even BETTER: .keys! I’d never thought to get the keys of a list, only of a hash. But of course this should work in Raku!
sub countSmaller(@int) {
my @counts;
for @int.keys -> $i {
@counts[$i] = 0;
for @int.keys -> $j {
@counts[$i]++ if @int[$j] < @int[$i];
}
}
return @counts;
}
View the entire Raku script for this task on GitHub.
Perl
sub countSmaller {
my @int = @_;
my @counts;
foreach my $i ( 0 .. $#int ) {
$counts[$i] = 0;
for my $j ( 0 .. $#int ) {
$counts[$i]++ if $int[$j] < $int[$i];
}
}
return @counts;
}
View the entire Perl script for this task on GitHub.
Python
Ooh. I just ran across a nifty Python built-in, enumerate:
def countSmaller(arr):
counts = []
for i, i_val in enumerate(arr):
counts[i] = 0
for j, j_val in enumerate(arr):
if j_val < i_val:
counts[i] += 1
return counts
$ python/ch-1.py
Example 1:
Input: @int = (8, 1, 2, 2, 3)
Traceback (most recent call last):
File "/Users/packy/git/perlweeklychallenge-club/challenge-244/packy-anderson/python/ch-1.py", line 22, in <module>
solution([8, 1, 2, 2, 3])
File "/Users/packy/git/perlweeklychallenge-club/challenge-244/packy-anderson/python/ch-1.py", line 18, in solution
output = countSmaller(arr)
File "/Users/packy/git/perlweeklychallenge-club/challenge-244/packy-anderson/python/ch-1.py", line 7, in countSmaller
counts[i] = 0
IndexError: list assignment index out of range
Oh, right. You can’t just add elements to a Python array by assigning to its index. You need to .append() to the array:
def countSmaller(arr):
counts = []
for i, i_val in enumerate(arr):
counts.append(0)
for j, j_val in enumerate(arr):
if j_val < i_val:
counts[i] += 1
return counts
View the entire Python script for this task on GitHub.
Task 2: Group Hero
You are given an array of integers representing the strength.
Write a script to return the sum of the powers of all possible combinations; power is defined as the square of the largest number in a sequence, multiplied by the smallest.
Example 1
Input: @nums = (2, 1, 4)
Output: 141
Group 1: (2) => square(max(2)) * min(2) => 4 * 2 => 8
Group 2: (1) => square(max(1)) * min(1) => 1 * 1 => 1
Group 3: (4) => square(max(4)) * min(4) => 16 * 4 => 64
Group 4: (2,1) => square(max(2,1)) * min(2,1) => 4 * 1 => 4
Group 5: (2,4) => square(max(2,4)) * min(2,4) => 16 * 2 => 32
Group 6: (1,4) => square(max(1,4)) * min(1,4) => 16 * 1 => 16
Group 7: (2,1,4) => square(max(2,1,4)) * min(2,1,4) => 16 * 1 => 16
Sum: 8 + 1 + 64 + 4 + 32 + 16 + 16 => 141
Approach
Ok, I feel like there are a bunch of pieces here, and the clearest way to tackle the problem is to attack each of the pieces individually:
First, we need a function that, given a list, calculates the power for that list. The meat of that abstracts out to square(max(list)) * min(list). Then we need to generate lists of all the combinations of our list of numbers, push each of those through our power function, and then sum those results.
Raku
Fortunately, in Raku, getting the max and min values of a list are easy:
sub power(@nums) {
return( (@nums.max ** 2) * @nums.min );
}
And getting all the possible combinations for a list is easy, too: .combinations.
sub groupHero(@nums) {
my $sum = 0;
for @nums.combinations: 1 .. @nums.elems -> @list {
$sum += power(@list);
}
return $sum;
}
But wait! I’m just adding things up? That sounds like… Raku’s Reduction Metaoperator, [ ]! All I have to do is put what I’m summing in a list…
sub groupHero(@nums) {
return [+] (
power($_) for @nums.combinations: 1 .. @nums.elems
);
}
View the entire Raku script for this task on GitHub.
Perl
In Perl, not everything is built in, but that’s where the power of CPAN comes in: List::Util and its min, max, and sum functions, and Algorithm::Combinatorics’ combinations function.
use Algorithm::Combinatorics qw( combinations );
use List::Util qw( min max sum );
sub power {
my $list = shift;
return( (max(@$list) ** 2) * min(@$list) );
}
sub groupHero(@nums) {
return sum(
# generate the list of powers for each combination
map { power($_) }
# generate the list of combinations
map { combinations(\@nums, $_) } 1 .. scalar(@nums)
);
}
View the entire Perl script for this task on GitHub.
Python
from itertools import combinations
def power(arr):
return( (max(arr) ** 2) * min(arr) )
def groupHero(nums):
# generate a list of combinations
comb = []
for i in range(1, len(nums)+1):
for c in combinations(nums, i):
comb.append(c)
return sum(
# generate the list of powers for each combination
[ power(x) for x in comb ]
)
I tried to not build the list of combinations with two loops and an intermediate array object, but I kept getting a list of iterables passed to power, so I got tired…
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-244/packy-anderson