Perl Weekly Challenge: Week 153

Challenge 1:

Left Factorials

Write a script to compute Left Factorials of 1 to 10. Please refer OEIS A003422 for more information.

Expected Output:

1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114

A left factorial for a particular integer is the sum of all factorials upto that number. The typical way they teach you to compute factorials in university is with a recursive function like this:

sub factorial($n) {
    return $n == 0 ?? 1 !! $n * factorial($n - 1);
}

$n == 0 is the base case; if $n is 0, we just return 1. Otherwise we recursively call factorial().

You can substantially improve the efficiency of this kind of recursive function with a technique called "memoization" which caches intermediate results. In Raku you can memoize a function by adding the attribute is cached after its' signature like this:

sub factorial($n) is cached {
    ...
}

As this is still considered an experimental feature, you have to opt in by adding

use experimental :cached;

at the top of your script.

Now the core of the script is one line. ^10 gives us a Sequence of integers from 0 to 9. For each number in this sequence, we add its' factorial to $sum. $sum is a state variable so it is initialized (to 0) the first time it is used and maintains its' value during repeated calls to the function it is in. We end up with a sequence of left factorials which are .join()ed togeth with commas and spaces and printed with .say().

(^10).map({ state $sum = 0; $sum += factorial($_) }).join(q{, }).say;

This works but I had time and I knew Raku is versatile in that way so I thought why not create a custom factorial operator so we can use the standard mathematical notation !. There is a 'Creating Operators' tutorial in the Raku documentation. It actually has a factorial operator as one of the examples which looks like this:

sub postfix:<!>( Int $num where * >= 0 ) { [*] 1..$num }

This is a bit slower than my memoized recursive version so I rewrote it like this:

sub postfix:<!>($n) is cached { $n == 0 ?? 1 !! $n * postfix:<!>($n - 1) }

Now instead of e.g. factorial(5) we can write 5! which looks much better.

Our revised script line looks like this:

(^10).map({ state $sum = 0; $sum += $_! }).join(q{, }).say;

(Full code on Github.)

We can't create custom operators in Perl so I wrote factorial() the old-fashioned way.

sub factorial($n) {
    return ($n == 0) ? 1 : $n * factorial($n - 1);
}

In Perl, you can memoize a function using the Memoize module;

use Memoize;

Then you call memoize() to cache a particular function.

memoize('factorial');

The main part of the script looks like this:

say join q{, }, map { state $sum = 0; $sum += factorial($_) } 0 .. 9;

(Full code on Github.)

Challenge 2:

Factorions

You are given an integer, $n.

Write a script to figure out if the given integer is factorion.

A factorion is a natural number that equals the sum of the factorials of its digits.

Example 1

Input: $n = 145
Output: 1

    Since 1! + 4! + 5! => 1 + 24 + 120 = 145

Example 2

Input: $n = 123
Output: 0

    Since 1! + 2! + 3! => 1 + 2 + 6 <> 123

First we split $n into its' individual digits with .comb(). Then using .map(), we replace each digit with its factorial using the factorial operator we developed previously. Then we add all the factorials together with .sum(). If this equals $n, we output 1 otherwise 0.

say $n.comb.map({ $_! }).sum == $n ?? 1 !! 0;

(Full code on Github.)

For Perl, we need a replacement sum() and the factorial() function from before.

The rest is very similar to Raku.

say sum(map { factorial($_) } split //, $n) == $n ? 1 : 0;

(Full code on Github.)