Perl Weekly Challenge: Week 301
Challenge 1:
Largest Number
You are given a list of positive integers,
@ints.Write a script to arrange all the elements in the given list such that they form the largest number and return it.
Example 1
Input: @ints = (20, 3)
Output: 320
Example 2
Input: @ints = (3, 30, 34, 5, 9)
Output: 9534330
This sounded really easy but it atually took me three attempts to get it right.
This is my first version:
@*ARGS.sort({ $^b <=> $^a }).join.say
The command-line arguments are .sort()ed in numeric order, largest first, then mashed together with
.join()and printed with .say(). It's wrong though. For example 1 we get 203 instead of the clearly
better 320. So I changed the code to this:
@*ARGS.sort({ $^b cmp $^a }).join.say
Now we are sorting lexically instead of numerically. Now 3 comes before 20 so we get 320 as we should. But example 2 still gives the wrong answer. We get 9534303 which is almost correct but not quite. The problem is 3 should come before 30, not the other way around.
So after thinking about this a bit I realized that we have to look at two elements at a time and reverse them in the sort if they are in the wrong order. It looks like this:
@*ARGS.sort({ "$^b$^a" cmp "$^a$^b" }).join.say
Rather than use the concatenation operator, I saved a couple of characters by interpolating two elements into a string. This string is then compared that to the string of the same pair reversed. This gives the correct answer for both examples.
Here is the final version in Perl:
say join q{}, sort { "$b$a" cmp "$a$b" } @ARGV
Challenge 2:
Hamming Distance
You are given an array of integers,
@ints.Write a script to return the sum of
Hammingdistances between all the pairs of the integers in the given array of integers.The Hamming distance between two integers is the number of places in which their binary representations differ.
Example 1
Input: @ints = (4, 14, 2)
Output: 6
Binary representation:
4 => 0100
14 => 1110
2 => 0010
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Example 2
Input: @ints = (4, 14, 4)
Output: 4
Because we will be working with binary numbers, the first order of business will be to take the
command-line arguments and convert them to a binary representation with .base(2). We are going to
look at individual bits so we split the binary number up with .comb() and convert the resulting
Sequence to a List with .List. This is assigned to @hamming.
my @hamming = @ints.map({ $_.base(2).comb.List });
In order to properly compare the integers they must all be the same size. To achieve this, the shorter ones must be padded to the same size as the longest one with preceding 0's.
So first we find the length of the longest binary integer.
my $length = @hamming».elems.max;
And then we add the extra '0's. Because $_ inside .map() is immutable, the padding is added
to a temporary array which then replaces the original.
@hamming = @hamming.map({
my @padded = @$_;
while @padded.elems < $length {
@padded.unshift('0');
}
@padded;
});
We assign a place to store the total Hamming distances.
my $total = 0;
For each combination of two integers...
for @hamming.combinations(2) -> [$a, $b] {
We count how many bits in each position in the two arrays are not the same (i.e. not both 1 or both 0.).
You can "zip" through two arrays applying an operator (in this case ne) to the pair of elements at each index with Z. The count is added to $total.
$total += (@$a Zne @$b).grep({ $_ == True }).elems;
}
Finally we print the $total.
say $total;
As usual, translating the Raku code to Perl is mostly an exercise in replacing functionality from the Raku standard library.
For instance in lieu of .base(2), we use sprintf("%b").
my @hamming = map { [ split //, sprintf("%b", $_) ] } @ints;
And this slightly more complicated code avoids the need for .max().
my $length = (sort { $b <=> $a } map { scalar @{$_} } @hamming)[0];
@hamming = map {
my @padding = @{$_};
while (scalar @padding < $length) {
unshift @padding, '0';
}
\@padding;
} @hamming;
my $total = 0;
I have a replacement for .combinations() which has been used in many previous challenges.
for my $combo (combinations(\@hamming, 2)) {
for my $i (keys @{$combo->[0]}) {
I also had a replacement for Z but the usage here is simple enough to code
it inline.
if ($combo->[0][$i] ne $combo->[1][$i]) {
$total++;
}
}
}
say $total;