Flip-Flops Leaving a Trail of Zeros

Wherein we walk down to the beach, looking at the lines in the sand, and contemplate the absences at the end that somehow seem to matter most…

THE WEEKLY CHALLENGE – PERL & RAKU #72


TASK #1 › Trailing Zeroes

Submitted by: Mohammad S Anwar

You are given a positive integer $N (<= 10).

Write a script to print number of trailing zeroes in $N!

Example 1
Input: $N = 10
Output: 2 as $N! = 3628800 has 2 trailing zeroes
Example 2
Input: $N = 7
Output: 1 as $N! = 5040 has 1 trailing zero
Example 3
Input: $N = 4
Output: 0 as $N! = 24 has 0 trailing zero


Method

I must admit when I first read this I thought Mohammad was just being exuberant. Go out and find those zeros! Yay zeros! Then I read things more carefully and realized what was really being asked. It was a ridiculous moment, but really amused me for some reason.

Yay zeros!

With that out of the way, it looks like we’re going to need a factorial function. As we’re only counting to ten for some reason pretty much any one will do. Then we can strip the zeros from the end with a regular expression, capture the match and count the digits. Three steps, pretty straightforward and I’m not sure how much more complicated I can make it. But don’t worry, I’ll try.

PERL 5 SOLUTION

Following the steps outlined above, for our factorial I started with a simple recursive routine.

sub fact {
    my $n = shift;
    return 1 if $n == 1;
    return $n * fact ($n - 1);
}

Later, after writing the Raku solution, I went back rewrote that as an iterator over a range with an accumulator.

sub fact {
    my $end = shift;
    my $acc = 1;
    $acc *= $_ for (2..$end);
    return $acc;
}

I could have brought in reduce from List::Util, or perhaps even rolled my own, but there are limits to my whimsy.

sub fact { return reduce { $a * $b } (1..$_[0]) }

Ok, on further reflection, perhaps there are not in fact limits to my whimsy. That works, incidentally, but actually it was even more whimsy that was responsible for my continuing to use the accumulator version, but we’ll get to that.

Feeling oddly constrained by the upper bound of 10 on our input, I wrote a loop to just look at all the values at once. I recklessly began to use larger numbers, just to see how the sequence progresses. That’s just how I roll, you know? I couldn’t get enough. I quickly “ran out of integer” when the numbers became too large; undeterred I added the bigint pragma.

It seems reduce didn’t play well with bigint and I was still stuck at 20; I went back to the accumulator version of the function and I was free! Free again! I was hooked — I was flying! 30! 40! 50!1 I couldn’t stop. At 88 I ran out of terminal, which seems oddly appropriate because “Roads? We don’t need roads where we’re going”. Deft at the wheel, I refused to stop.

I added a memoizing hash to keep computed factorials as I created them, greatly reducing calculation time for the next one. Anyway, to cut a very long number short, there are 2499 trailing zeros on 10000!.

And I know this because I counted them.


1 Yes this was all to make an elaborate mathematical pun. I feel comforted by the fact that most of you don’t know where I live.

[colincrain:~/PWC]$  perl 72_1_trail_of_zeros.pl 20
there are 0 trailing zeros on  1! = 1
there are 0 trailing zeros on  2! = 2
there are 0 trailing zeros on  3! = 6
there are 0 trailing zeros on  4! = 24
there is  1 trailing zero  on  5! = 120
there is  1 trailing zero  on  6! = 720
there is  1 trailing zero  on  7! = 5040
there is  1 trailing zero  on  8! = 40320
there is  1 trailing zero  on  9! = 362880
there are 2 trailing zeros on 10! = 3628800
there are 2 trailing zeros on 11! = 39916800
there are 2 trailing zeros on 12! = 479001600
there are 2 trailing zeros on 13! = 6227020800
there are 2 trailing zeros on 14! = 87178291200
there are 3 trailing zeros on 15! = 1307674368000
there are 3 trailing zeros on 16! = 20922789888000
there are 3 trailing zeros on 17! = 355687428096000
there are 3 trailing zeros on 18! = 6402373705728000
there are 3 trailing zeros on 19! = 121645100408832000
there are 4 trailing zeros on 20! = 2432902008176640000
use warnings;
use strict;
use feature ":5.26";

use bigint;

## ## ## ## ## MAIN:

## we're going to ignore the directive and just 
## print them all from 1 to $n 

my $n = shift @ARGV // 30;

for my $n (1..$n) {
    my $fact    = fact($n);
    my ($zeros) = $fact =~ m/.*?(0*)$/;
    my $count   = @{[split //, $zeros]}; ## baby cart operator

    my @plurals = $count == 1 ? ("is ", " ") : ("are", "s");
    
    say "there $plurals[0] $count trailing zero${plurals[1]} on " 
            . (sprintf "%2d! = ", $n) . $fact;
}


## ## ## ## ## SUBS:


sub fact {
## final form: memoized accumulator
## does reduction using a for loop
    state %memo;

    my $end = shift;
    if (exists $memo{ $end - 1 }) {
        $memo{ $end } = $memo{ $end - 1 } * $end;
        return $memo{ $end }
    }
    my $acc = 1;
    $acc *= $_ for (2..$end);
    $memo{ $end } = $acc;
    return $acc;
}
raku solution

In Raku the reduction metaoperator makes a factorial function so easy I just inlined it. Delirious with excess after my breathless Perl excursion, I decided it was time to settle down and refocus on the simple things in life.

sub MAIN (Int $n where $n > 0 = 20) {
    for 1..30 {
        ## factorial function
        my $fact = [*] 2..$_;   
        
        ## match object captures are in a list. 
        ## Take match object [0], apply comb() 
        ## then elems() to count the zeros

        my $zeros = ($fact ~~ /.*?(0*)$/)[0]
                    .comb.elems;
        my @pl = $zeros == 1 ?? ('is ', '') 
                             !! ('are', 's') ;
        say "there are $zeros trailing zeros on {$_}! = $fact";
    }
}

TASK #2 › Lines Range

Submitted by: Mohammad S Anwar

You are given a text file name $file and range $A –  $B where $A <= $B.

Write a script to display lines range $A and $B in the given file.

Example
Input:
    $ cat input.txt
    L1
    L2
    L3
    L4
    ...
    ...
    ...
    ...
    L100
$A = 4 and $B = 12
Output:
    L4
    L5
    L6
    L7
    L8
    L9
    L10
    L11
    L12

Method

“[Perl] combines (in the author’s opinion, anyway) some of the best features of C, sed, awk, and sh, so people familiar with those languages should have little difficulty with it.”

So wrote Larry Wall in the Perl 1.0 release manpage back in 1987. When Larry Wall originally came up with the Perl language, he shamelessly borrowed ideas from the tools he was using, glueing them together in much the same way the Perl itself would come to glue together the disparate components of the internet a decade later.

Take, for example, the “stream editor’ sed. That tool was designed to read through a text file, find some specified text and do some combination of extraction and transformation on it. As such it acquired the need to specify where exactly to look in the file, and to do that it had a mechanism to specify a range of line numbers, separated by a comma. In using it, you might end up with command line constructs that look like

sed '4,17s/hello/world/' input.txt > output.txt

This command will substitute ‘world’ for the first instance of the text ‘hello’ on lines 4 through 17 of the file input.txt and write the whole thing to output.txt. And yes, that substitution should look quite familiar as well. See what I was talking about?

The comma in this example serves as a range operator for the specified action: don’t act until the first specified line number is reached, then act until the second. This idea was lifted wholesale and generalized into the flip-flop version of Perl’s own range operator ‘..‘ In addition to its normal sequence defining behavior, the idea of describing a list from start to end was generalized into a boolean operator the returned true from here to there. It starts returning false, returns true after the left side evaluates to true, continues that way until the right side evaluates to true, after which it returns false again. It’s a neat little operator and very useful in the right context, and that’s what we’re going to use to meet this challenge.

PERL 5 SOLUTION

Perl is full of little special cases and custom tweaks to make common jobs easier, and in the case of the flip-flop operator several of these hacks come together to make the flowing construct work:

while (<>) {
  print if 3..5
}

which prints lines 3 through 5 of the input file.

Here the diamond operator, without a file handle specified, looks to either open a file at @ARGV or alternately read from STDIN and then read one line, while the flip-flop condition is automatically applied to the line number of that file. That’s a lot of special-case behavior but it does dispatch the task with a minimum of fuss.

I keep mentioning the shortcut hack aspect because the thing about special cases is, once you stray too far from the specific criteria things generally don’t work the way you want them to. Such is the case with respect to the flip-flop automatically referencing the input line number. Apparently Perl needs to recognize a constant on both sides of the operator to do the sed-like magic and a variable just won’t do. So, in the course of figuring this out, I found a clarification on the PerlMonks site by our own Choroba. With that guidance I carried on. Credit where credit is due; thanks for the tip.

Unless of course by some coincidence there are two Perlesque Chorobas out there, an E. Choroba and a just plain Choroba. I mean, it is quite likely there are more than one, after all. That in turn might be cause for worry as someday they might meet up and attempt to take over the world. We’ll have to watch for that.

Now the code, fixed, refers explicitly to $. , also known as $INPUT_LINE_NUMBER, defined as “Current line number for the last filehandle accessed.”

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:

## remove these from @ARGV first
my $from = shift @ARGV;
my $to   = shift @ARGV;

## need to use $. the line number special variable
while (<>) {
    print if $. == $from .. $. == $to;

}
raku solution

The problem with doing a complete rewrite to make things make more sense is that if done well, things make more sense. So in Raku, the flip-flop operator remains, but not much of the Perl hackery carries over. The diamond operator is replaced by the sensible casting to an IO object, which opens the file for reading; lines() delivers the lines as a sequence; pairs() accesses those sequence elements with a key/value tuple. The flipping and flopping operator gets it’s own name, appropriately called ff, and because we’re referencing sequence indices rather than cardinal line numbers we’re counting from 0 and need to subtract 1.

As far as learning more Raku style I did a few things differently. I wanted to make a subset of the Int type for cardinal numbers to consolidate the type constraints, which is sweet and I will continue to do more of, and on the advice of Andrew Shitov now I’m playing around with the

unit sub MAIN;

construction. Once we do that then everything in the script is considered to be within the MAIN block, so it cleans up the outermost brackets nicely.

subset Cardinal of Int where * > 0;

unit sub MAIN ( Cardinal $from = 3, 
                Cardinal $to = 6, 
                Str $file = $*PROGRAM-NAME);
    
## iterate through lines of $file as (key, value) pairs,
## output if line number flip-flop over $from to $to
## line numbers are indexes and are 0-based so we need to correct

.value.say if .key == $from-1 ff .key == $to-1 for $file.IO.lines.pairs;


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://perlweeklychallenge.org

One thought on “Flip-Flops Leaving a Trail of Zeros

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s