laurent_r

These are some answers to the Week 2 of the Perl Weekly Challenge organized by the hugely prolific CPAN author (and, besides, very nice chap) Mohammad S. Anwar.

Challenge #1: Removing Leading 0's

Write a script or one-liner to remove leading zeros from positive numbers.

A Perl 5 One-Liner

This uses a simple regular expression to remove zeros from the start of the string. Here, we're just using bash for piping four lines with input numbers to a very simple 7-character Perl 5 one-liner.

$ echo '0456
> 0007865
> 8976
> 0000123456' | perl -pe 's/^0+//'
456
7865
8976
123456

Nothing complicated. The s/^0+// regular expression substitution looks for one or more zeroes at the beginning of the string and replaces them with nothing.

Perl 6 Solution under the REPL

I could basically use the same one-liner in Perl 6, but decided instead to simply use the prefix + operator to numify the strings containing the numbers into actual numbers, thereby removing leading 0's (the number is in fact converted back to a string by the say built-in, but that's immaterial). So the P6 solution under the REPL (Read Evaluate Print Loop) is dead simple:

> say +$_ for  qw /0456 0007865 8976 0000123456/;
456
7865
8976
123456

Challenge #2: Convert Numbers into Base-35 Representations

Write a script that can convert integers to and from a base35 representation, using the characters 0-9 and A-Y.

A Perl 5 Conversion Subroutine

To perform such a conversion, we need to apply a series of integer division (also known as Euclidean division) and modulo.

Take any number, say 342 . What does the number 342 mean? Well in our number representation system, it is 3 * 100 + 4 * 10 + 2 * 1. Suppose we want to convert 342 into a base 10 representation, which is of course a trivial problem since 342 is already represented in base 10. We start by dividing 342 by the target base, 10, and we get a result of 34 and a remainder of 2. Next, we divide the previous result 34 by 10, and get 3 and a remainder of 4. Finally, we divide the previous result 3 by 10 and get a result of 0 and a remainder of 2. Notice that the series of remainders is 2, 4 and 3; when flipped around, this series of remainders gives 342, i.e. the original number converted to base 10.

As a further simple example, suppose we want to convert 11 into a binary representation. We start by dividing 11 by 2 (with integer division): the result is 5 and the remainder 1. Next, we divide 5 by 2; the result is 2 and the remainder 1. Next, we divide 2 by 2, the result is 1 and the remainder 0. Finally, we divide 1 by 2, the result is now 0 and the remainder 1. Since we've reached 0, the process is now completed. We now know that :

11 = (1 * 2 ** 3 ) +  (0 * 2 ** 2) + (1 * 2 ** 1 ) +  (1 * 2 ** 0 ).

If we flip around the series of remainders (1, 1, 0, and 1), we get 1011, which is the binary representation of 11.

Hopefully, these examples make the algorithm of the convert_base subroutine below clear.

The Perl 5 convert_base subroutine below should be able to convert positive integers to any base between 2 and 36:

use strict;
use warnings;
use feature "say";
use constant lookup => ('0'..'9','A'..'Z');

sub convert_base {
    my ($num, $base) = @_;
    my $result = "";
    do {
        $result .= (lookup)[$num % $base];
        $num = int ($num/$base);
    } while $num > 0;
    $result = reverse $result;
}
for my $number (0..45, qw/1757 533 658467/) {
    say "$number\t:\t", convert_base $number, 35;
}

Note that I'm using here a do {...} while loop, a syntactic construct that I rather rarely use. My initial coding attempt had a simple while loop, but that meant that the number 0 would not be properly converted (I would get an empty string). I felt that using a do ... while loop to fix the problem was somewhat nicer than making 0 a special case (for example simply returning 0 if the first input parameter is 0).

Of course, in real production code, we would need to check the validity of the input parameters (arity, type and range) of the convert_base subroutine. That's left as an exercise for the reader.

Result:

$ perl  convert.pl
0       :       0
1       :       1
2       :       2
3       :       3
    ... some output lines omitted for brevity ...
28      :       S
29      :       T
30      :       U
31      :       V
32      :       W
33      :       X
34      :       Y
35      :       10
36      :       11
37      :       12
38      :       13
39      :       14
40      :       15
41      :       16
42      :       17
43      :       18
44      :       19
45      :       1A
1757    :       1F7
533     :       F8
658467  :       FCIC

Note that I chose here to manually implement the full algorithm to perform the conversion because this is a coding challenge, after all (it is an interesting exercise in its own right and, since I had not done any base-conversion algorithm for a number of years, it took me a few minutes to figure out how to do it), but there is at least half a dozen CPAN modules that can do the conversion such as Math::Int2Base, Math::BaseCalc, etc. I haven't really checked how they're implemented, but I would suppose that they do the right input parameter checks.

I've just noticed at the eleventh hour that I missed part of the original requirement: write a script that can convert integers to and from a base35 representation: I actually missed the and from requirement in the solution I originally submitted for the challenge a few days ago. That a fairly easy-to-solve problem:

use strict;
use warnings;
use feature "say";
my $c = 0;
my %lookup = map {$_ => $c++} ("0".."9","A".."Z");

sub convert_back {
    my ($num, $base) = @_;
    my $result = 0;
    for my $i (split //, uc $num) {
        $result = $base * $result + $lookup{$i};
    }
    return $result;
}
say convert_back $_, 35 for qw/ 10 1A 1F7 F8 FCIC/;

The results are consistent with what we obtained with the convert-base subroutine:

35
45
1757
533
658467

Perl 6 Number Conversion

We could easily roll out the same algorithm in Perl 6 with just a few changes. Although, as we'll see below, this is useless work, let's do it just for the sake of showing how it might look like in Perl 6:

sub convert-base (Int $num is copy where * >= 0, Int $base where 1 < * < 37) {
    constant @lookup = flat('0'..'9','A'..'Z');
    my $result = "";
    repeat {
        $result ~= @lookup[$num % $base];
        $num = floor $num/$base;
    } while $num > 0;
    return $result.flip;
}
say "$_\t", convert-base($_, 35) for flat(0..40);

There are a few minor syntactic changes compared to the P5 version, but the most important difference is that the convert-base subroutine signature does all the input parameter validation that is needed for robust code: we need two arguments, a non-negative integer for the number to be converted, and an integer between 2 and 36 for the base. The subroutine will fail with an explicit type check error if we pass a negative integer or a rational number for any of the two arguments.

This is not what I did, however, in the answer I submitted for the challenge, because it is a bit silly: Perl 6 has a built-in base method for such base conversions. This is my submitted one-line solution in Perl 6 under the REPL:

> say "$_\t", $_.base(35) for flat(0..45, 1757, 533, 658467);
0       0
1       1
2       2
3       3
    ... some output lines omitted for brevity ...
28      S
29      T
30      U
31      V
32      W
33      X
34      Y
35      10
36      11
37      12
38      13
39      14
40      15
41      16
42      17
43      18
44      19
45      1A
1757    1F7
533     F8
658467  FCIC

As mentioned previously, I missed the and from requirement in my submitted solution. In Perl 6, there is a parse-base built-in that does the reciprocal conversion of parse:

> say "$_\t", $_.parse-base(35) for qw/10 20 FCIC/
10      35
20      70
FCIC    658467

Note that, in the various code examples above, I implemented manually a number of test cases. It may be argued that it would be better to use the P6 Test module (and, similarly, one of the numerous P5 test modules such as the Test core module or, possibly better, Test::More for the P5 implementation). Well, yes, but I felt too lazy to calculate by hand beforehand the 35-base values of such numerous test cases, and there is a relatively high chance of making mistakes in such manual computations. In this specific case, I'm happy enough to check the general consistency of the results (for example that 35 base 35 is 10) and to verify that my P5 algorithm and the P6 built-in base function yield the same results.

While We Are Speaking About Testing...

This is a very short and incomplete example of how you could use the Test module of Perl 6 to verify that the built-in base function works as expected:

use v6;
use Test;
plan 8;

is 4.base(2), "100", "4 base 2";
is 15.base(16), 'F', "15 base 15";
is $_.base($_), "10", "$_ base $_ is 10" for 2, 8, 10, 16, 35; 
is 70.base(35), "20", "70 base 35";

Presumably, the base built-in subroutine of Perl 6 has much more thorough tests than the above. Our aim here is just to very briefly illustrate how this works. The first line ensures that we are using Perl 6. The second line, with the plan keyword says that we are going to run 8 tests (the third test line is testing 5 cases and counts as 5 tests). And each of the test line starting with the is keyword does a string comparison between the result of the i.base(k) statement and the expected result. A string comparison is the right thing to do here because we are not comparing numbers but strings representing the base k of some numbers. The last (and optional) argument to the is subroutine is just a comment, more precisely a short description of the test that can help make tests interpretation a bit easier when any of the tests fails.

Running this test program produces the following output:

1..8
ok 1 - 4 base 2
ok 2 - 15 base 15
ok 3 - 2 base 2 is 10
ok 4 - 8 base 8 is 10
ok 5 - 10 base 10 is 10
ok 6 - 16 base 16 is 10
ok 7 - 35 base 35 is 10
ok 8 - 70 base 35

If one of the tests had failed, the result might have had something like this:

...
# Failed test '70 base 35'
# at test_base.pl line 8
# expected: '21'
#      got: '20'
# Looks like you failed 1 test of 8

If you want to know more about testing in Perl 6, please look at the https://docs.perl6.org/language/testing tutorial, the https://docs.perl6.org/type/Test module documentation, or the Debugging section of Chapter 14 of my Perl 6 book (https://github.com/LaurentRosenfeld/thinkperl6/raw/master/PDF/thinkperl6.pdf). Hopefully, one of the next Perl Weekly Challenges will provide the opportunity to cover Perl 6 testing in a more detailed fashion.

Wrapping up

The next week Perl Weekly Challenge is due to start very soon. If you're interested in participating in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 6 p.m. BST (British summer time) on next Sunday, April, 14. And, please, also spread the word about the Perl Weekly Challenge if you can.