Perl Weekly Challenge 108
Task 1 this week is kind of a joke, but task 2 was interesting!
Task 1: Locate Memory
Write a script to declare a variable or constant and print its location in the memory.
Solution
See below for explanation and any implementation-specific comments.
sub challenge(Any $variable) returns Int {
$variable.WHERE;
}
sub MAIN {
my $variable = rand; # [1][2]
say challenge($variable);
}
This program runs as such:
$ raku ch-1.raku
140444494947864
Explanation
Raku has the WHERE
method built into it that “Returns an Int
representing the memory address of the object,” we simply need to utilize that.
Specific comments
rand
is a built-in subroutine that returns a random integer.- Following the Scala style, I would normally use parentheses for subroutines that are not “pure” and write this as
rand()
, but Raku complains with the following error:Unsupported use of rand(). In Raku please use: rand.
Task 2: Bell Numbers
Write a script to display top 10 Bell Numbers. Please refer to the Wikipedia page for more information.
Example
- B0: 1, as you can only have one partition of zero element set.
- B1: 1, as you can only have one partition of one element set
{a}
. -
B2: 2
{a}{b} {a,b}
-
B3: 5
{a}{b}{c} {a,b}{c} {a}{b,c} {a,c}{b} {a,b,c}
-
B4: 15
{a}{b}{c}{d} {a,b,c,d} {a,b}{c,d} {a,c}{b,d} {a,d}{b,c} {a,b}{c}{d} {a,c}{b}{d} {a,d}{b}{c} {b,c}{a}{d} {b,d}{a}{c} {c,d}{a}{b} {a}{b,c,d} {b}{a,c,d} {c}{a,b,d} {d}{a,b,c}
Solution
See below for explanation and any implementation-specific comments.
use experimental :cached;
sub challenge(Int $n where $n >= 0) is cached returns Int { # [1]
given $n {
when 0|1 { 1 }
default {
my $n-minus-one = $n - 1;
gather for (0..$n-minus-one) -> $k { # [2]
take (^$n-minus-one).combinations($k) * challenge($k); # [2]
}.sum
}
}
}
sub MAIN(Int $n = 10) {
say (^$n).map(&challenge);
}
This program runs as such:
$ raku ch-2.raku
(1 1 2 5 15 52 203 877 4140 21147)
Explanation
Note: The question asks for the “top 10 Bell Numbers.” Since this is an ever-increasing sequence, there is no “top,” so I interpreted that to mean first 10 Bell numbers.
At first glance, this code has nothing to do with the input sequences, but digging into the above-linked Wikipedia entry, we find this equation:
$ B_{n+1} = \sum_{k=0}^{n}{n \choose k}B_{k} $
This tells us that each Bell number is built upon by the previous Bell numbers. And we know the first two Bell numbers, so we can follow this.
Let’s re-write this to calculate $ B_{2} $ and see how it works; remember, since we are calculating for $ B_{n+1} $, we use $ n = 1 $.
$ B_{2} = \sum_{k=0}^{1}{1 \choose k}B_{k} $
Which can be expanded as:
$ B_{2} = {1 \choose 0}B_{0} + {1 \choose 1}B_{1} $
Which can be reduced to:
$ B_{2} = (1)(1) + (1)(1) = 2 $
So $ B_{2} = 2 $ and we can use that to calculate $ B_{3} $ and so on.
Now that we have the algorithm figured out, and decided we are going to apply it to the first 10 terms, it’s a simple matter to map
the function over the sequence from 0 (inclusive) to 10 (exclusive).
Specific Comments
- Since this is a recursive function, once we calculate $ B_{2} $ we will use it in $ B_{3} $, $ B_{4} $ and so on. No use re-calculating it every time, so we memoize this function using the
is cached
trait. - gather/take is a construct to build up a sequence using a
Supply
(in this case, thefor
loop).
Final Thoughts
I love me some pattern matching and recursion, coming from a Scala day job, so it is fun to use those constructs in other languages, especially Raku. 🙂