Perfect Indentation with Perl 6

by Arne Sommer

Perfect Indentation with Perl 6

Published 14. May 2019

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

Challenge #8.1

«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;  # [5]
  }
  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

Testing it:

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

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

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

$ perl6 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
10,163s6
20,173s6,28
30,2496,28,496
411,919s6,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 coerce the value to an integer, the time is as low as 5,723s:

File: perfect-numbers2b (changes only)
  for 2 .. ($number / 2).Int -> $candidate

Challenge #8.2

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).

[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.perl6.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({ .indent(($max-length - .chars) / 2) });
}

Running it:

$ perl6 center "123" "111111111111111111111111111111" "111111" "1"
             123
111111111111111111111111111111
            111111
              1

$ perl6 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:

$ perl6 center "123" "11" "1"
123
11
 1

$ perl6 center "1234" "11" "1"
1234
 11
 1

And that's it.