Perl Weekly Challenge: Week 66

I don't know why, all the permissions etc. have been checked and rechecked but for some reason last weeks post was not showing up for some people. It should hopefully be good now if you would care to take a look.

Challenge 1:

Divide Integer

You are given two integers $N and $S.

Write a script to divide the given two integers i.e. $M / $N without using multiplication, division and mod operator and return the floor of the result of the division.

Example 1

Input: $M = 5, $N = 2
Output: 2

Example 2

Input: $M = -5, $N = 2
Output: -3

Example 3

Input: $M = -5, $N = -2
Output: 2

This weeks challenges were very maths-intensive which is not so good for me. I kind of sort of knew how to solve this problem but some of the finer details eluded me and I ended up having to do some research on the Internet in order to get it right.

Case in point, I learned that if either $M or N is negative, the end result will be negative. If both are positive or both are negative, the answer will be positive. This line handles that.

my $negative = ($M < 0) ^ ($N < 0);

Instead of dealing with signs it is easier to use absolute values and worry about the sign at the end. Along the way we can use variable names which are more descriptive than $M and $N.

my $dividend = abs($M);
my $divisor = abs($N);
my $quotient = 0;

After that we emulate division by repeatedly subtracting the $divisor, adding 1 to the $quotient each time (this will be the final answer) until the $dividend is less than the $divisor. The $dividend might not necessarily equal 0 though. If it doesn't, it is the remainder.

while ($dividend >= $divisor) {
    $dividend -= $divisor;
    $quotient++;
}

Now, if we know the answer is going to be $negative we flip the sign of the $quotient. The spec says we have to return the floor of the result. This is only an issue if the answer is negative and there is a remainder. If both these criteria are true, subtracting one from the $quotient will provide the correct answer.

if ($negative) {
    $quotient = -$quotient;
    if ($dividend > 0) {
        $quotient--;
    }
}

say $quotient;

(Full code on Github.)

The Raku version is virtually the same. The only thing that tripped me up is that the XOR operator is now ^^ instead of Perls' ^.

my $negative = ($M < 0 ^^ $N < 0);
my $dividend = abs($M);
my $divisor = abs($N);
my $quotient = 0;

while $dividend >= $divisor {
    $dividend -= $divisor;
    $quotient++;
}

if $negative {
    $quotient = -$quotient;
    if $dividend > 0 {
        $quotient--;
    }
}

say $quotient;

(Full code on Github.)

Challenge 2:

Power Integers

You are given an integer $N.

Write a script to check if the given number can be expressed as mⁿ where m and n are positive integers. Otherwise print 0.

Please make sure m > 1 and n > 1.

BONUS: If there are more than one ways to express the given number then print all possible solutions.

Example 1

For given $N = 9, it should print 3² or 3^2.

Example 2

For given $N = 45, it should print 0.

Example 3

For given $N = 64, it should print all or one of 8^2 or 2^6 or 4^3.

If the first challenge was slightly confusing, I was completely at sea with the second challenge. Luckily I came across this article and it was very helpful. My code is mostly based on it, I just had to do some adaption for the bonus goal and to format the answers according to the spec.

sub isPower {
    my ($num) = @_;
    my @results;

    if ($num == 1) {
       push @results, join q{^}, (1, 1); 
    } else {
        for my $m (2 .. sqrt($num)) {
            my $n = 2; 
            my $p = $m ** $n; 

            while ($p <= $num && $p > 0) { 
                if ($p == $num) { 
                    push @results, join q{^}, ($m, $n);
                } 
                $n++; 
                $p = $m ** $n; 
            } 
        }
    } 

    return @results; 
}

my ($N) = @ARGV;

my @powers = isPower($N);
say scalar @powers ? (join q{, }, @powers) : 0;

(Full code on Github.)

This, without further comment, is the Raku version.

sub isPower($num) { 
    my @results;

    if $num == 1 {
        @results.push([1, 1].join(q{^})); 
    } else {
        for 2 .. sqrt($num) -> $m {
            my $n = 2; 
            my $p = $m ** $n; 

            while $p <= $num && $p > 0 { 
                if $p == $num { 
                    @results.push([$m, $n].join(q{^}));
                } 
                $n++; 
                $p = $m ** $n; 
            } 
        }
    } 

    return @results; 
}

my @powers = isPower($N);
say @powers.elems ?? @powers.join(q{, }) !! 0;

(Full code on Github.)