The Weekly Challenge : Week 133 in Raku

Back to the Challenges

So it's been a while since I blogged about the Weekly Challenges. Heck I've been a bit up and down due to everything going on and haven't even done them every week.

But I'm back on the wagon off to the races or something, so lets look at this weeks challenges.

Challenge 1

Now Raku doesn't have a isqrt functions built in and the challenge states not to use built in functions. Still if we were allowed it it's pretty simple.

sub isqrt( UInt \n ) { \n.sqrt.Int() }

Cue discussion in /r/rakulang about which method I should have used to round the value off. It's beside the point for the case in point because we're here to talk about how to calculate it without using built in functions.

One thing to note, on my laptop doing iqsrt(999999999999999) using that method takes about 0.14 seconds.

So there's lots of Maths on Wikipedia dealing with calculating integer square roots but as is my wont I figured lets try something simple. Count from 1 to Infinity until I find a number that when squared is bigger than the number I'm looking for. The number before it will be the integer square root.

Sure for a human that's insanely tedious but doing insanely tedious counting is what we invented computers for. Here's the code for that :

sub isqrt(UInt \n) {
    (1..*).first( { $_ * $_ > n } ) - 1;
};

So... make the Range 1 to Infinity (here denoted by a * but I could use the ∞ symbol if I wanted. I tend to not use Unicode much though as it's a pain to type) and find the first value that when squared is bigger that the target. (I love first it's like grep but when you just want the first thing. Then we just subtract one and return. Simples.

(And yes $_² or $_ ** 2 would work too... but... does it make a huge difference? I don't think so.)

And there we go. Interesting thing to note if you time iqsrt(999999999999999) using this method it's about .2s. Not too bad (though... it's not a linear progression... add 5 more 9's and it's slows to just over a second).

Another method I saw was to use a Sequence with the check in the terminator, something like this :

sub isqrt(UInt \n) {
    (1...*² > n)[*-2]
}

(See I can use fancy unicode stuff if I want to). And that works except... it takes over 1 second to calculate iqsrt(999999999999999) and for 15 9's I get bored waiting. (I do get bored easily though).

So... yeah, Sequences are fun but a whole bunch slower than a Range.

Challenge 2

So this challenges is about Smith Numbers and a quick look at the Wikipedia page we see that we need prime factors. Luckily if you've been doing the Weekly challenge (almost every week...) then this is not your prime factor rodeo. Challenge 41 required to find prime factors so a quick duck into the archives and I find this:

use experimental :cached;

sub prime-factors( Int $n is copy --> Array ) is pure {
    my @factors;
    while ! $n.is-prime {
        my \s = smallest-factor( $n );
        @factors.push(s);
        $n = $n div s;
    }
    @factors.push($n);
    return @factors;
}

sub smallest-factor( Int \n --> Int ) is pure is cached {
    for (2..(n div 2)).grep(*.is-prime) {
        return $_ if n %% $_;
    }
    die "Something went wrong";
}

So here we do recursive sub division of a number to find the smallest prime factor and put them into a list. (This is made a lot easier by is-prime and %%. So now we want to find the Smith numbers, specifically the first ten. In my (get computers to count lots for you) way I figure this is a job for a Range and grep!

Generally I find many things I attempt are a job for map, grep and reduce.

So here's our Main sub:

sub MAIN ( UInt \n = 10 ) {
    .say for (2..*).grep( { is-smith-number($_) } )[^n];
}

Simple right...

...

Oh... you want to see what is-smith-number has in it. Well there are two possibilities. Firstly the number is prime in which case it's not a Smith number so that's simple :

multi sub is-smith-number( Int \n where n.is-prime --> False ) {}

Here I'm using a trick I picked up for this sort of case to put the return directly into the signature which feels Rakuish.

And then there's the case where it isn't prime. Here we sum the values of the number and for each factor sum the sum of each value... Look here's the code hopefully it will make sense :

multi sub is-smith-number( Int \n --> Bool ) is pure {
    my @factors = prime-factors( n );
    ([+] n.comb) == ([+] @factors.map( { [+] $_.comb } ));
}

[+] $var.comb casts a number to a string and then splits it it's individual values and then does a recursive addition to get the sum. If the sun of the values equals the sum of the sum of the values of each factor then it's a Smith number.

As I mentioned timings before that takes about 0.3s to calculate the first 10 Smith Numbers (and 0.5s for the first 100). Once the new-disp branch has been released as stable I'll maybe run it again and see if it changes at all (the multi call should hopefully be a bit faster).

Anyway, there we go, enjoy the challenge, hopefully I'll write more next week.