The Weekly Challenge in Raku : Week 72 (Part 1)

This weeks challenge is not going to be too taxing. There are a few fun little bits we can do though.

Part 1 : Trailing Zeros

In this challenge we're to find the number of trailing Zero's in $N! where $N <= 10 so really it's a two part challenge, find $N! and count trailing zeros.

Finding Factorials

First thing to note is we can define the ! factorial operator quite easily :

sub postfix:<!> (UInt $N) {...}

We'll cover the ... bit in a sec but this defines ! as a postfix operator that requires and Unsigned Integer in front of it. Thing is I won't be using this in my challenge because right now defining operators directly in scripts really slows down parsing (if you put them in Modules you get them precompiled but generally I don't make a module for the challenges).

Still it's nice to know you can do it. Anyway lets say we instead make a fact($N) sub how hard is that?

Personally I can think of three different ways of doing it off the top of my head, all of which are quite Rakuish so lets cover them each.

Sequences are fun

A Raku Seq is a iterable object that returns values that are generally calculated as required. There's a couple of sequences that can provide factorials. This first uses the ... Sequence operator

@F = (1,{$_ * $++}...*)

Here we define our starting condition @F[0] == 1 then our iterator in this $_ is given the value of the previous item in the list and $ is a local state variable. This will be 1 in the first iteration so @F[1] == 1 and then 2, 3 and so on. We use * as the final condition meaning we will keep generating values forever, but as sequences are lazy this doesn't cause our code to die.

Another way to create a Sequence would be to use [gather and take]{https://docs.raku.org/syntax/gather%20take} to explictly define it :

my @F = lazy gather { 
    my $idx = 1; 
    my $val = 1; 
    loop {
        take $val;
        $val *= $idx++; 
    }
};

A bit more wordy but sometimes this can be good. For a simple sequence like this it's probably over kill but in other cases you may fine it useful.

Recursion is fun too

A classic way to do factorials (and in some languages the only way) is to use recursion. Raku lends itself to this with multi subs for example :

multi sub fact( 0 ) { 1 }

multi sub fact( UInt $N ) { $N * fact( $N - 1 ) }

Here fact will recursively call itself until $N is 1 at which point the fact(0) call will match and the stack can unroll.

This is probably safe to do as in this challenge $N can't go over 10 but it's dangerous to rely on otherwise as you may get stack overflows. Still nice to know it's easy enough.

Meta Ops are your friends

When I did the challenge my first thought was to turn to Meta Operators. As 5! can be written as 1 * 2 * 3 * 4 * 5 this looks to me like a reduction on the list (1,2,3,4,5) with the * operator. the [] reduction metaoperator lets you write this like so :

sub fact(UInt $N) { [*] (1..$N) }

Note this works for 0 as the Range 1..0 is the list (1).

Finding the Trailing Zeros.

So we've got our factorial using one of the above options how do we find trailing zeros? Well as an old school Perl dev the first thing that comes to my mind is to use a Regex. The expression 0*$ will match 0 or more 0's at the end of a string. We then can count the length of this match and return it:

say (fact($N) ~~ m!(0*)$!)[0].Str.codes;

We get a Match object and can get it's zeroth value which is the first capture (here's a difference in Raku Regexes, captures start at 0). We coerce this to a Str and then count the code points. And Bingo, the count of trailing 0's.

And here's Part 2