Perl Weekly Challenge: Week 140
Challenge 1:
Add Binary
You are given two decimal-coded binary numbers,
$aand$b.Write a script to simulate the addition of the given binary numbers.
The script should simulate something like
$a + $b. (operator overloading)
Example 1
Input: $a = 11; $b = 1;
Output: 100
Example 2
Input: $a = 101; $b = 1;
Output: 110
Example 3
Input: $a = 100; $b = 11;
Output: 111
Is operator overloading really necessary? Raku atleast has everything needed for binary addition. We could solve this challenge with a one-liner like this:
(@*ARGS[0].parse-base(2) + @*ARGS[1].parse-base(2)).base(2).say;
However the spec suggests we do in fact overload the + operator. I was surprised at how easy (with one caveat) this is to do in Raku.
An overloaded operator is a subroutine which like any other subroutine is created with the sub keyword. Because we are overloading
an operator which already exists in Raku we also need the multi keyword. infix indicates what type of operator this is. You
can also use prefix, postfix etc. Then between <> you have the actual name of the operator.
multi sub infix:<+>(
This is the bit that gave me pause. I was getting errors because my code was calling Rakus' version of + in MAIN() and converting
the operands to Ints. By changing the parameters of my subroutine to IntStr I ensured that it got called first. I've added
a line that prints 'overload!' to verify that it is indeed my operator + that is being used. One more thing to point out is that
the type specifier has :D on the end. I'm not 100% but what I think it is for is to ensure that we get an instance of IntStr not
the type itself.
IntStr:D $a,
IntStr:D $b
) {
say 'overload!';
The heart of the function is the same as the one-liner above.
return ($a.parse-base(2) + $b.parse-base(2)).base(2);
}
Perl is, as often is the case, a little more difficult. As far as I can tell, there is no way to globally override an operator,
only on a per-package basis. So my solution introduces a simple class called Binary. You would do binary addition with it
like this:
say Binary->new($a) + Binary->new($b);
The package uses the overload pragma to special + for Binary values. As we shall see, we will also need to overload
the "" operator in order to make Binarys out of strings and to output them again. Each overloaded operator is backed by
a subroutine.
package Binary;
use overload '+' => 'add';
use overload '""' => 'toString';
But first let's look at the constructor. This is plain vanilla Perl OOP. The constructor takes one value which it makes
into a binary value by prepending 0b and stores it.
sub new {
my ($class, $str) = @_;
my $self = \"0b$str";
bless $self, $class;
return $self;
}
The add() function takes two parameters. The first is the object itself. This will be the first operand of the addition.
The second parameter is a reference to the second operand which should also be a Binary object. A real Binary type would deal
with all kinds of other scenarios such as adding a Binary to a scalar, adding it to undef etc. but in this small example I
haven't bothered with any of that.
Because Perl doesn't have a straightforward method of converting between bases like Raku, I used the combination of sprintf()
and the woefully misnamed oct() functions to convert the operands from strings to decimal numbers. These were added and then
sprintf() was used again to convert back into a binary string which was then used to create a new Binary as the output.
Also as in the Raku version, I am outputting "overload!" to make sure my version of + is being used.
sub add {
my ($self, $other) = @_;
say "overload!";
return Binary->new(
sprintf '%b', (sprintf '%d', oct $$self) + (sprintf '%d', oct $$other)
);
}
This function stringifies the Binary object using the sprintf()/oct() method. It is a little more complex than it
needs to be only for the sake of removing the 0b prefix.
sub toString {
my ($self) = @_;
return sprintf '%b', oct $$self;
}
Challenge 2:
You are given 3 positive integers,
$i,$jand$k.Write a script to print the
$kth element in the sorted multiplication table of$iand$j.
Example 1
Input: $i = 2; $j = 3; $k = 4
Output: 3
Since the multiplication of 2 x 3 is as below:
1 2 3
2 4 6
The sorted multiplication table:
1 2 2 3 4 6
Now the 4th element in the table is "3".
Example 2
Input: $i = 3; $j = 3; $k = 6
Output: 4
Since the multiplication of 3 x 3 is as below:
1 2 3
2 4 6
3 6 9
The sorted multiplication table:
1 2 2 3 3 4 6 6 9
Now the 6th element in the table is "4".
This is another challenge that can be solved with a one-liner in Raku. The X operator provides the cross product
of two lists. The two lists in question are the range of 1 to $i (or @*ARGS[0] as we are taking arguments from the command
line.) and the range of 1 to $j (@*ARGS[1].) The result is a list of two-element lists. X* applies the multiplication
operator to these lists which, in the case of example 1, would give us (1 2 3 2 4 6). This list is sorted and the $k - 1
(@*ARGS[2] - 1) is selected and printed. (You have to subtract 1 to get the right answer because arrays start from 0.)
(1 .. @*ARGS[0] X* 1 .. @*ARGS[1]).sort({$^a <=> $^b})[@*ARGS[2] - 1].say;
Perl doesn't have X* so we simulate it with a double for loop.
my @table;
for my $i (1 .. $ARGV[0]) {
for my $j (1 .. $ARGV[1]) {
push @table, $i * $j;
}
}
say 0+(sort { $a <=> $b } @table)[$ARGV[2] - 1];