Perl Weekly Challenge: Week 386
Challenge 1:
Reverse Base
You are given a string representing a number, and an integer specifying the base of that representation.
Write a function to convert this string to an integer. (For bases greater than 10, use characters A-Z, a-z, + and / in that order.)
Example 1
Input: $num = "101010", $base = 2
Output: 42
Example 2
Input: $num = "EEADEE", $base = 16
Output: 15642094
Example 3
Input: $num = "755", $base = 8
Output: 493
Example 4
Input: $num = "1BRJB", $base = 36
Output: 2228519
Example 5
Input: $num = "7MyqL", $base = 64
Output: 123456789
This problem is the inverse of the first challenge in PWC 384 Instead of Int.parse(), we can
use Str.parse-base() .parse-base() has the same limitation as .parse(); it only
works up to base 36.
So once again I solved it by repurposing and extending Perl code from PWC 379 to create a wrapper using the Meta Object Protocol which would deal with bases greater than 36 while falling back to the original function for base 36 or less. However I ran into a weird problems which I still don't understand.
As in my previous effort, the basic architecture of the wrapper function was like this:
if $base <= 36 {
# fall back to the standard library .parse-base()
} elsif $number == 0 {
# this results in 0 in every base so dealt with seperately
} else {
# my code for dealing with bases > 36
}
But for example 5 I got the error message:
Cannot convert string to number: trailing characters after number in '7⏏MyqL'
which is what you eould expect from the standard .parse-base() even though that
shouldn't be called for base 64. It only worked correctly after I changed the conditional
branches around like this:
if $base > 36 {
# my code for dealing with bases > 36
} elsif $number == 0 {
# this results in 0 in every base so dealt with seperately
} else {
# fall back to the standard library .parse-base()
}
Most perplexing. I am going to ask about this and will update the post if I get an explanation.
This is what I finally came up with.
Using the Meta Object Protocol, we create a wrapper as a lambda. We convert
the arguments to Strings and create storage for the $result.
Str.^lookup('parse-base').wrap(-> |args {
my ($number, $base) = args».Str;
my $return;
A quick check to see if the base is within bounds.
if $base !~~ 2 .. 64 {
die "base $base is out of range";
}
Contrary to my pseudocode above, I put the check for 0 first. It doesn't make a difference either way.
if $number == 0 {
$return = '0';
The order of the other two options does.
First is my code to deal with bases greater than 36.
} elsif $base > 36 {
The $magnitude is the number of digits except units.
my $magnitude = $number.chars - 1;
We create a hash that maps digits to their value in base-10.
my %digits =
([0 ..9], ['A' .. 'Z'], ['a' .. 'z'], ['+', '/']).flat
Z=>
(0 ..^ $base);
We break the number into digits and add calculate each digits base-10 value which
is then added to return. $magnitude is decremented.
for $number.comb -> $digit {
my $base10 = %digits{$digit} //
die "malformed base-$base number\n";
$return += $base10 * $base ** $magnitude;
$magnitude--;
}
In the case of a base between 2 and 36, we simply use the original .parse-base()
to provide $result.
} else {
$return = callsame;
}
No matter how we computed it, we return $return.
$return;
});
Now MAIN() is just a single line.
$num.parse-base($base).say;
In the Perl version we handle all the bases ourselves as Perl does not have a
parse-base() to fall back on.
sub fromBase($number, $base) {
if ($base < 2 || $base > 64) {
die "base $base is out of range\n";
}
my $scale = (length $number) - 1;
my %digits;
@digits{0..9, 'A'..'Z', 'a'..'z', '+', '/'} = 0 .. $base - 1;
my $result;
for my $digit (split //, $number) {
my $base10 = $digits{$digit} // die "malformed base-$base number\n";
$result += $base10 * $base ** $scale;
$scale--;
}
return $result;
}
say fromBase($number, $base);
Challenge 2:
Rational Numbers
You are given two strings representing non-negative rational numbers.
Write a script to return true if the two given rational numbers are same otherwise false.
Example 1
Input: $rat1 = "0.(12)"
$rat2 = "0.(121)"
Output: false
Expansion of "0.(12)" = 0.12 12 12 12
Expansion of "0.(121)" = 0.121 121 121
Example 2
Input: $rat1 = "0.1(23)"
$rat2 = "0.12(32)"
Output: true
Expansion of "0.1(23)" = 0.1 23 23 23
Expansion of "0.12(32)" = 0.12 32 32 32
Example 3
Input: $rat1 = "0.1(234)"
$rat2 = "0.12(342)"
Output: true
Expansion of "0.1(234)" = 0.1 234 234 234
Expansion of "0.12(342)" = 0.12 342 342 342
Example 4
Input: $rat1 = "12.99(99)"
$rat2 = "13."
Output: true
Example 5
Input: $rat1 = "0.(123)"
$rat2 = "0.1(231)"
Output: true
I had to do some research to figure out how to compare two potentially infinitely repeating rational numbers and it seems the answer is to convert them to fractions and compare thosr. How do you do that? This page was helpful to me.
I decided to make a Fraction class. With it my MAIN() function looks very simple
like this:
my $fraction1 = Fraction.new($rat1);
my $fraction2 = Fraction.new($rat2);
say $fraction1 == $fraction2;
Let's look at the Fraction class.
class Fraction {
It has two data fields to hold the fractions' numerator and denominator. They are private but Raku will create accessor methods in the class so they can be read.
has $.numerator;
has $.denominator;
Typically the constructor of a naku class will taked named parameters but I didn't
want that so I had to create a custom .new() method to make the parameter positional.
This is just boilerplate so I don't know why Raku can't just handle it for me but it
doesn't.
method new($rat) {
self.bless(:$rat);
}
The .BUILD() submethod is called from .bless() it allows us to customize the
construction of a Fraction object. We use it to call the .parse() method.
submethod BUILD(:$rat) {
self!parse($rat);
}
What does .parse() do? First of all note the ! in front of the name. This
indicates that .parse() is a private method which will not be usable outside
the class. It takes a string representing a rational number and parses it into
a fraction.
method !parse($rat) {
First it splits the rational number into two parts; the bit before the decimal
point which I am calling $integer and the bit after the decimal point which I
am calling $decimal.
my ($integer, $decimal) = $rat.split('.');
One of these might not exist ($rat2 in example 4 for instance.) so we set them
to defaults if that is the case.
$integer //= '0';
$decimal //= q{};
The $decimal part may also be divided into two. A repeating part enclosed in
parentheses in the input and a possible non-repeating part before it.
my $nonRepeating = q{};
my $repeating = q{};
if $decimal ~~ /^(.*)\((.*)\)$/ {
$nonRepeating = $0.Str;
$repeating = $1.Str;
If $decimal does not follow that format, it is considered the non-repeating part
and $repeating is an empty string.
} else {
$nonRepeating = $decimal;
$repeating = '';
}
These three parts $integer, $nonRepeating and $repeating are passed to
the .makeFraction() method which will be discussed next.
self!makeFraction($integer, $nonRepeating, $repeating);
}
.makeFraction() is also a private method.
method !makeFraction($integer, $nonRepeating, $repeating) {
It uses the $integer, $nonRepeating and $repeating passed to it to create
variables $a, $n and $m which will be used to create the numerator and denominator
of the fraction.
my $a = $integer.Int;
my $n = $nonRepeating.chars;
my $m = $repeating.chars;
my $numerator;
my $denominator;
When there's no repeating part, the numerator is constructed by combining the integer part with the non-repeating decimal digits. The denominator is simply 10 to the power of $n.
if $m == 0 {
We make $bs default 0 to handle the case of there being no decimal digits at all.
(Like example 4.)
my $b = ($nonRepeating || '0').Int;
$numerator = $a * (10 ** $n) + $b;
$denominator = 10 ** $n;
If there is a repeating part, it's a bit more complicated.
} else {
We construct two numbers. $full represents all digits concatenated together (integer + non-repeating + one cycle of repeating), and $partial represents everything up to but not including the repeating part.
my $full = ($integer ~ $nonRepeating ~ $repeating).Int;
my $partial = ($integer ~ $nonRepeating).Int;
$shifts1 shifts past the non-repeating decimals, while $shifts2 shifts past both non-repeating and repeating sections.
my $shifts1 = 10 ** $n;
my $shifts2 = 10 ** ($n + $m);
We can use all these to create the numerator and denominator of the fraction while eliminating the repeating cycle.
$numerator = $full - $partial;
$denominator = $shifts2 - $shifts1;
}
The last step is to reduce the numerator and denominator to their simplest forms
by using the gcd operator to find the greatest common denominator and dividing
both by it. These are then assigned to the objects $numerator and $denominator
fields.
my Int $g = $numerator gcd $denominator;
$!numerator = $numerator div $g;
$!denominator = $denominator div $g;
}
}
To compare two Fractions, we can override the == operator. We compare the
two numerators and the two denominators for equality and return the result.
multi infix:<==> (Fraction $a, Fraction $b) {
return $a.numerator == $b.numerator && $a.denominator == $b.denominator;
}
For the Perl version I used the new class syntax in the most recent versions. Unfortunately it is still very much a work in progress. Most of my effort in translating from Raku was in working around missing features.
class Fraction {
Object data is marked by the field keyword. The :reader attribute autogenerates
an accessor.
field $numerator :reader;
field $denominator :reader;
As well as the numerator and denominator, I had to add a third field $rat to
be able to use the rational number in ADJUST (see below.) It has the :param
attribute so it can be used as a named parameter to the constructor.
field $rat :param;
An ADJUST block is the Perl equivalent to a Raku classes' .BUILD(). Unfortunately
it cannot take arguments from the construction which is why we needed the $rat field.
ADJUST {
$self->parse($rat);
}
methods cannot be made private.
method parse($rat) {
my ($integer, $decimal) = split /\./, $rat;
$integer //= '0';
$decimal //= q{};
my $nonRepeating = q{};
my $repeating = q{};
if ($decimal =~ /^(.*)\((.*)\)$/) {
$nonRepeating = $1;
$repeating = $2;
} else {
$nonRepeating = $decimal;
$repeating = q{};
}
$self->makeFraction($integer, $nonRepeating, $repeating);
}
method makeFraction($integer, $nonRepeating, $repeating) {
my $a = $integer;
my $n = length $nonRepeating;
my $m = length $repeating;
my $num;
my $den;
if ($m == 0) {
my $b = $nonRepeating || '0';
$num = $a * (10 ** $n) + $b;
$den = 10 ** $n;
} else {
my $full = $integer . $nonRepeating . $repeating;
my $partial = $integer . $nonRepeating;
my $shifts1 = 10 ** $n;
my $shifts2 = 10 ** ($n + $m);
$num = $full - $partial;
$den = $shifts2 - $shifts1;
}
my $g = $self->gcd($num, $den);
$numerator = int($num / $g);
$denominator = int($den / $g);
}
I don't think there is an easy way to overload operators that works with the new
classes. So I just made a method .equalTo() that does the same thing.
method equalTo($other) {
return $self->numerator == $other->numerator &&
$self->denominator == $other->denominator;
}
We also need a replacement for gcd.
method gcd($a, $b) {
if ($b == 0) {
return $a;
}
$self->gcd($b, $a % $b);
}
}
The main Perl code looks like this which is pretty good but not as concise as Raku.
my $fraction1 = Fraction->new(rat => $rat1);
my $fraction2 = Fraction->new(rat => $rat2);
say $fraction1->equalTo($fraction2) ? 'true' : 'false';