Perl Weekly Challenge: Week 133

Challenge 1:

Integer Square Root

You are given a positive integer $N.

Write a script to calculate the integer square root of the given number.

Please avoid using built-in function. Find out more about it here.

Examples

Input: $N = 10
Output: 3

Input: $N = 27
Output: 5

Input: $N = 85
Output: 9

Input: $N = 101
Output: 10

The wikipedia link provided gives an algorithm and example C code for solving this problem and my solution is just a straight translation. Here's the Perl version:

sub squareRoot {
    my ($n) = @_;

    my $firstTry = $n >> 1;

    if ( $firstTry ) {
        my $nextTry = ( $firstTry + $n / $firstTry) >> 1;

        while ( $nextTry < $firstTry) {
            $firstTry = $nextTry;
            $nextTry = ( $firstTry + $n / $firstTry) >> 1;
        }

        return $firstTry;
    } else {
        return $n;
    }
}

(Full code on Github.)

And this is the Raku version. The funky right bit shift operator +> was the only stumbling block.

sub squareRoot(Int $n) {
    my $firstTry = $n +> 1;

    if $firstTry {
        my $nextTry = ( $firstTry + $n / $firstTry) +> 1;

        while $nextTry < $firstTry {
            $firstTry = $nextTry;
            $nextTry = ( $firstTry + $n / $firstTry) +> 1;
        }

        return $firstTry;
    } else {
        return $n;
    }
}

(Full code on Github.)

Challenge 2:

Smith Numbers

Write a script to generate first 10 Smith Numbers in base 10.

According to Wikipedia:

In number theory, a Smith number is a composite number for which, in a given number base, the sum of its digits is equal to the sum of the digits in its prime factorization in the given number base.

I love the challenges where we can reuse code from previous weeks. I used the code I developed for prime factorization most recently in Challenge 123 but it goes way back before that. It is used to create an isSmith() function that return true or false if its' input is a Smith Number. In Perl looks it like this:

sub isSmith {
    my ($n) = @_;
    my @digits = split //, $n;

    my @primeFactors;
    factorize($n, \@primeFactors);

If we only have 1 prime factor or 0 (can that actually happen?) it's not going to be a Smith number so we can just stop here. Because Perl doesn't have actual true and false literals, we return undef to signify false.

    if (scalar @primeFactors < 2) {
        return undef;
    }

Initially I got some weird answers and then I realized that if the prime factors themselves have multiple digits, they also have to be summed. The line below takes care of that. Incidently, sum() is another function I had created earlier and reused.

    @primeFactors = map { my @d = split //, $_; sum(\@d); } @primeFactors;

    return sum(\@digits) == sum(\@primeFactors);
}

(Full code on Github.)

This is the Raku version. The [+] hyperoperator for summing a list or array is one of my favorite features of the language.

sub isSmith($n) {
    my @digits = $n.comb;

    my @primeFactors;
    factorize($n, @primeFactors);
    if @primeFactors.elems < 2 {
        return;
    }

    @primeFactors = @primeFactors.map({ [+] $_.comb; });

    if ([+] @digits) == ([+] @primeFactors) {
        take $n;
    }
}

Initially I wrote this to return true or false like the Perl version and it worked but was slower than Perl. (Though not too shabby I must say.) I took another stab at it and refactored it to use take to return valid Smith numbers. This can be used together with gather like this:

my @smiths = lazy gather {
    for 1 .. * -> $n {
        isSmith($n)
    }
}

@smiths[^10].join(', ').say;

(Full code on Github.)

...to create a lazy list. This actually runs faster than Perl, the first time I've seen non-trivial Raku code do that.