Perl Weekly Challenge: Week 146
Challenge 1:
10001st Prime Number
Write a script to generate the
10001stprime number
Because Raku has an .is-prime() method, this is a one-liner.
say (1 .. *).grep({ .is-prime })[10_000]
(1 .. *) is the list of all integers. We pick out the primes using .grep() and print the 10,001st one.
On my first attempt, I made an embarassingly basic mistake and selected index 10,001 forgetting that array indexes start from 0 so actually I need index 10,000. Duh!
Perl doesn't have any inbuilt facilities for dealing with prime numbers but I've developed some code to remedy the lack as they've come up before in previous challenges, most recently Week 133. So the solution looks like this:
my $prime;
my $count = 1;
do {
$prime = nextPrime();
} while ($count++ < 10_001);
say $prime;
nextPrime() utilizes a function called isPrime() and as the name suggests, returns the next prime number. So calling it 10,001 times gives the required result. Despite the wordier code, this runs just as fast as the Raku version.
The 10,001st prime number is 104,743 by the way.
Challenge 2:
Curious Fraction Tree
Consider the following
Curious Fraction Tree:
1/1
|
+---------------+---------------+
| |
1/2 2/1
| |
+-------+-------+ +-------+-------+
| | | |
1/3 3/2 2/3 3/1
| | | |
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | |
1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
You are given a fraction, member of the tree created similar to the above sample.
Write a script to find out the parent and grandparent of the given member.
Example 1
Input: $member = '3/5';
Output: parent = '3/2' and grandparent = '1/2'
Example 2
Input: $member = '4/3';
Output: parent = '1/3' and grandparent = '1/2'
I have to admit that I couldn't make head nor tail of this. Luckily, we have Google now; it directed
me to this page and I was enlightened. If
we describe a node as a/b, the left child node is a/a+b and the right child node is a+b/a. So once we know if a node is
a left child or right child, we can reverse engineer the value of its' parent.
sub parent(Str $fraction) {
I made a function to work this out which takes a string representing a fraction as its' only parameter.
my ($numerator, $denominator) = $fraction.split(q{/}).map({ .Int(); });
The fraction is split into a numerator and denominstor and both are convered into integers.
unless ($numerator ~~ Int) && ($denominator ~~ Int) {
return q{};
}
Some basic validation is done. If the numerator or denominator are not integers the function fails. (i.e. returns an empty string.)
if $numerator < $denominator {
return "$numerator/{($denominator - $numerator).abs}";
If the numerator is smaller than the denominator, we are dealing with a left child. The parent is calculated with the
formula a/(b-a) Because b-a could result in a negative value, it is run through .abs() to get the absolute value.
} elsif $numerator > $denominator {
return "{($denominator - $numerator).abs}/$denominator";
If the numerator is larger than the denominatior, this is a right child. The parent is (b-a)/a.
} else {
return q{};
}
}
The final possibility is that the numerator and denominator are equal. In reality, this can only happen at the very top of
the tree which will always be 1/1 but it could be the result of garbage input. In any case, there is no parent to such a node
so an empty string is returned.
With this function we can find the parent with parent($member) and the grandparent by calling the function twice i.e.
parent(parent($member)).
The Perl version is mostly the same minus the usual syntactic differences.
sub parent {
my ($fraction) = @_;
my ($numerator, $denominator) = split m{/}, $fraction;
unless (defined $numerator && $numerator =~ /^\d+$/ && defined $denominator
&& $denominator =~ /^\d+$/) {
return q{};
}
Perl doesn't have a simple way of finding if a value is an integer so I just used a regular expression to check that a string
contained only digits. Also in order to make sure split() has returned valid values, we check if $numerator and $denominator are not undef.
if ($numerator < $denominator) {
return "$numerator/" . abs($denominator - $numerator);
} elsif ($numerator > $denominator) {
return abs($denominator - $numerator). "/$denominator";
} else {
return q{};
}
}