Perfect Indentation with Raku

[12] Published 14. May 2019

Perl 6 → Raku

This article has been moved from «perl6.eu» and updated to reflect the language rename in 2019.

This is my response to the Perl Weekly Challenge #8.

Challenge #8.1: Perfect Numbers

Write a script that computes the first five perfect numbers. A perfect number is an integer that is the sum of its positive proper divisors (all divisors except itself). Please check Wiki for more information. This challenge was proposed by Laurent Rosenfeld.

I'll start with a program that prints the divisors (excluding the number itself) for a given number:

File: perfect-divisors

sub MAIN ($number)
{
  say "Divisors (excluding the number itself): " ~ proper-divisors($number);
}

multi proper-divisors (2) { return (1); }                 # [1]

multi proper-divisors (Int $number where $number > 2)     # [2]
{
  return (1) if $number.is-prime;                         # [3]

  my @divisors = (1);                                     # [4]
  for 2 .. ($number -1) -> $candidate                     # [5]
  {
    @divisors.push: $candidate if $number %% $candidate;  # [5a]
  }
  return @divisors;
}

[1] This variant is called for the value 2.

[2] This variant is called when the value is 3 or greater. (Note that integers less than 2, as well as non-integers, give a runtime error.)

[3] Prime numbers don't have divisors, so avoid trying to compute them.

[4] The first divisor is always 1.

[5] Looping through the possible values, we add it to the list if it is a divisor (5a). Note that we could have written this line like this instead:

  for 2 ..^ $number -> $candidate

Testing it:

$ raku perfect-divisors 2
Divisors (excluding the number itself): 1

$ raku perfect-divisors 3
Divisors (excluding the number itself): 1

$ raku perfect-divisors 4
Divisors (excluding the number itself): 1 2

$ raku perfect-divisors 12
Divisors (excluding the number itself): 1 2 3 4 6

Extending (and renaming) the program with code to check if the number is a perfect number:

File: perfect-numbers-test

sub MAIN ($number)
{
  say "Divisors (excluding the number itself): " ~ proper-divisors($number);

  say "Is the number perfect: " ~ is-perfect($number);
}

multi proper-divisors (2) { return (1); }

multi proper-divisors (Int $number where $number > 2)
{
  return (1) if $number.is-prime;

  my @divisors = (1);
  for 2 .. ($number -1) -> $candidate
  {
    @divisors.push: $candidate if $number %% $candidate;
  }
  return @divisors;
}

sub is-perfect ($number)
{
  return $number == proper-divisors($number).sum;  # [1]
}

[1] Checking if the number is a Perfect Number is easy. Just add the divisors and compare the sum with the number itself.

And finally as a program that prints the first 5 perfect numbers (or whatever other number we specify on the command line):

File: perfect-numbers

sub MAIN (Int $count where $count > 0 = 5)  # [1]
{
  my $numbers := gather                     # [2]
  {
    for 2..Inf                              # [3]
    {
      take $_ if is-perfect($_);            # [3]
    }
  }

  say "The first $count perfect numbers: "
    ~ $numbers[0 .. $count -1].join(', ') ~ ".";  # [4]
}

multi proper-divisors (2) { return (1); }

multi proper-divisors (Int $number where $number > 2)
{
  return (1) if $number.is-prime;

  my @divisors = (1);
  for 2 .. ($number -1) -> $candidate
  {
    @divisors.push: $candidate if $number %% $candidate;
  }
  return @divisors;
}

sub is-perfect ($number)
{
  return $number == proper-divisors($number).sum;
}

[1] A positive integer, with 5 as default value.

[2] You may have noticed (from my other articles) that I have a fondness for «gather»/«take».

[3] Setting up the values.

[4] Fetching the first «$count» number of values.

Problems

Searching for the five first perfect numbers is extremely slow, as the fifth number is «33550336» (Source: wikipedia).

Count	Time	Values
1	0,163s	6
2	0,173s	6,28
3	0,249	6,28,496
4	11,919s	6,28,496,8128
5	???	6,28,496,8128,33550336

It is actually so slow that I gave up after the program had been running for about one day. So I haven't actually verified that the program gives the correct answer.

A Dead End?

We can halve the number of computations, as the largest possible divisor must be less or equal to half the number:

File: perfect-numbers2 (partial)

multi proper-divisors (Int $number where $number > 2)
{
  return (1) if $number.is-prime;
  
  my @divisors = (1);
  for 2 .. ($number / 2) -> $candidate
  {
    @divisors.push: $candidate if $number %% $candidate;
  }
  return @divisors.sort;
}

Timing it with the value 4 gives us 17,649s, so this version is actually slower than the original one (adding about 50% to the time used).

It turns out that the problem is the upper limit for the Range in the «for» loop. If we ensure that the upper limit is an integer, e.g. by using integer division with div (instead of /), the time is as low as 5,723s:

File: perfect-numbers2b (changes only)

  for 2 .. ($number div 2) -> $candidate

See docs.raku.org/routine/div for more information about «div».

Challenge #8.2. Center

Write a function, ‘center’, whose argument is a list of strings, which will be lines of text. The function should insert spaces at the beginning of the lines of text so that if they were printed, the text would be centered, and return the modified lines.

For example,

center("This", "is", "a test of the", "center function");

should return the list:

"     This", "      is", " a test of the", "center function"

because if these lines were printed, they would look like:

       This
        is
   a test of the
  center function

The procedure is quite simple, and looks like this:

sub center (@strings)                                            # [1]
{
  my $max-length = @strings>>.chars.max;                         # [2]
  return @strings.map({ .indent(($max-length - .chars) /2) });   # [3]
}

[1] Pass the strings.

[2] Compute the length of the longest string (by computing all, and taking the largest value).

If you don't like the >>. syntax, use map instead:

  my $max-length = @strings.map(*.chars).max;

[3] If we indent by the max length minus the length of the actual string, we get right tabulated output. Half the value gives centered output.

See docs.raku.org/routine/indent for more information about «indent».

Here it is, as a program. Specify the arguments on the command line.

File: center

sub MAIN (*@strings)
{
  .say for center(@strings);
}

sub center (@strings)
{
  my $max-length = @strings>>.chars.max;
  return @strings.map({ .Str.indent(($max-length - .chars) / 2) });
}

Note the coersion to a string with «Str», as «indent» is only implemented for strings. This isn't a problem when getting the values from the command line (as integers will be of the «IntStr» type), but is a problem if used on integers specified in a program.

See my Raku From Zero to 35 or docs.raku.org/type/IntStr for more information about «IntStr».

Running it:

$ raku center "123" "111111111111111111111111111111" "111111" "1"
             123
111111111111111111111111111111
            111111
              1

$ raku center "123" "111111111111111" "111111" "1"
      123
111111111111111
    111111
       1

Note that a string with an even number of characters will be placed wrong in a mathematical sense, as we cannot indent by half a space:

$ raku center "123" "11" "1"
123
11
 1

$ raku center "1234" "11" "1"
1234
 11
 1

Not quite...

Note that the sample procedure call in the challenge doesn't work, because my procedure requires a list. This can be remedied by using a slurpy argument, as already done on «MAIN»:

File: center (changes only)

sub center (*@strings)

This change makes it possible to use both individual arguments (the first line), or a list (the second line) - or any combinations (but please don't):

say center(1, 2222222222222222222222222222, 33333333333333333333);
say center([1,22222,3]);

And that's it.