Perl Weekly Challenge 108: Locate Memory and Bell Numbers
These are some answers to the Week 108 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few days (April 18, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Locate Memory
Write a script to declare a variable or constant and print it’s location in the memory.
Locate Memory in Raku
In languages such as Perl and C, it is a fairly common task to take a reference or a pointer to a variable, and a reference or a pointer are essentially the memory addresses of such a variable (for some definition of memory address). In Raku, using the memory address of a variable is almost never necessary (except possibly for low-level debugging purpose). Actually, I originally wasn’t even completely sure I was going to find a way of doing that in Raku. However, the Metaobject Protocol (MOP) offers some metamethods, which are introspective macros that provide information about objects (including variables). One such metamethod is WHERE, which returns an Int representing the memory address of the object. Once we know that, the task is very easy:
my $i = 42;
say $i.WHERE;
This small script displays the following output:
$ raku memory.raku
41688736
Locate Memory in Perl
As mentioned before, taking a reference to a variable is very common in Perl. And a reference is in effect a memory address. So the task is very easy in Perl:
use strict;
use warnings;
use feature "say";
my $i = 42;
say \$i;
This displays the following output:
$ perl memory.pl
SCALAR(0x600079020)
If we want to get rid of irrelevant information and print out only the memory address, we can just extract the address, for example with a regular expression:
use strict;
use warnings;
use feature "say";
my $i = 42;
my $ref = \$i;
my $addr = $1 if $ref =~ /\((0x\w+)/;
say $addr;
which prints only the memory address:
$ perl memory.pl
0x600079020
Locate Memory in Other Languages
Memory Address in the C Programming Language
In C, & is the “address-of” operator:
#include <stdio.h>
int main () {
int val = 42;
printf("Memory location of val is: %p", &val);
return 0;
}
Output:
$ ./a.out
Memory location of val is: 0xffffcc1c
Memory Address in C++
Rather than copying almost verbatim the C program above, we’ll use the fact that C and C++ array names are actually pointers to memory locations:
#include <iostream>
using namespace std;
int main() {
int array[4] = {42, 43, 44, 45};
cout << "Memory address of the array is: " << array;
return 0;
}
Output:
Memory address of the array is: 0x7ffc3775ad50
Memory Address in the D Programming Language
D pointers are similar to C’s. So we can do basically the same as in C:
import std.stdio;
void main () {
int val = 42;
writeln("Address of val is: ", &val);
}
Output:
Address of val is: 7FFD967574F8
Memory Address in Python
Python doesn’t really have pointers, but we can still retrieve the integer representation of the address of a Python object with the id built-in:
i = 42
print("Address of variable i is: ", id(i))
Output:
Address of variable i is: 9786208
Memory Address in Go
In Go, & is the “address-of” operator:
package main
import "fmt"
func main() {
i := 42
fmt.Println("Address of vaiable i is: ", &i)
}
Output:
Address of vaiable i is: 0xc000018050
Memory Address in Julia
In Julia, we’ll use an array. The pointer built-in function returns a pointer to the array:
arr = [1, 2, 3, 7]
p_arr = pointer(arr)
println("Memory address of arr is: ", p_arr)
Output:
Memory address of arr is: Ptr{Int64} @0x00007f70a29334d0
Memory Address in Rust
In Rust, & is the “address-of” operator as in C:
fn main() {
let val: i32 = 42;
println!("Memory locacion of variable val is: {:p}", &val);
}
Output:
Memory location of variable val is: 0x7fff4b32e2fc
Memory Address in Pascal
Last time I used Pascal was in the first year of my CS curriculum, back in 1990. As you might imagine, I don’t remember much of the syntax. It did not even remember that Pascal had pointers, except that, thinking about it, I remembered that we had to implement linked lists or trees, something that probably required some form of pointer. The big difference between now and then, of course, is that it wasn’t possible at the time to look up on the Internet. So you needed to buy books, as well as the software (a Turbo-Pascal compiler from Borland at the time). Pascal might not be the most modern language, but it has a clean and clear syntax, so that it turned out to be quite simple to write this little program. The only thing that seems to be missing from Niklaus Wirth’s brainchild programming language is a good harmless goto statement. ;-). But it’s OK, I did not need it.
program memAddress;
var
value: integer;
intPtr: ^integer;
result: ^word;
begin
value := 42;
intPtr := @value;
result := addr(intPtr);
writeln('Memory address of value is: ', result^);
end.
Output:
Memory address of value is: 23008
Pascal lets you easily use pointers to access the data itself. But, if, for some reason, you want to work with the memory address itself, you need to store it in a word type variable (the result variable in the program above).
Task 2: Bell Numbers
Write a script to display top 10 Bell Numbers. Please refer to Wikipedia page for more informations.
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}
The Bell numbers count the possible partitions of a set. There are various ways to compute the Bell numbers, but one of the most common ones is to construct the Bell triangle, which may be displayed as follows:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
The Bell triangle may be constructed by placing the number 1 in its first position. After that placement, the leftmost value in each row of the triangle is filled by copying the rightmost value in the previous row. The remaining positions in each row are filled by a rule very similar to that for Pascal’s triangle: they are the sum of the two values to the left and upper left of the position.
Thus, after the initial placement of the number 1 in the top row, it is the last position in its row and is copied to the leftmost position in the next row. The third value in the triangle, 2, is the sum of the two previous values above-left and left of it. As the last value in its row, the 2 is copied into the third row, and the process continues in the same way.
The first (and last) item on each row provides the individual Bell numbers:
1 1 2 5 15 52 203 877 ...
There may be faster ways to compute Bell numbers, but since we are requested to compute only the first 10 Bell numbers, this will be amply sufficient.
Bell Numbers in Raku
We just build the Bell triangle (the tr array of arrays) and extract the Bell numbers from it:
constant \MAX = 9;
my @tr;
@tr[0][0] = 1;
for 1..MAX -> $row {
@tr[$row][0] = @tr[$row - 1][*-1];
for 1..$row -> $i {
@tr[$row][$i] = @tr[$row][$i-1] + @tr[$row - 1][$i-1];
}
}
say join " ", map { @tr[$_][0] }, 0..@tr.end;
This script displays the first 10 Bell numbers:
$ raku bell.raku
1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in Perl
As in Raku, we build the Bell triangle and extract the Bell numbers:
use strict;
use warnings;
use feature "say";
use constant MAX => 9;
my @tr;
$tr[0][0] = 1;
for my $row (1..MAX) {
$tr[$row][0] = $tr[$row - 1][-1];
for my $i (1..$row) {
$tr[$row][$i] = $tr[$row][$i-1] + $tr[$row - 1][$i-1];
}
}
say join " ", map { $tr[$_][0] } 0..$#tr;
And we obtain the same output as in Raku:
$ perl bell.pl
1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in Other Languages
Bell numbers in Scala
This is essentially the same algorithm using the Bell triangle in Scala. The slight difference is that the Bell triangle is mapped on a square matrix, with only the items of the triangular area actually defined.
object bellNum extends App {
val max = 10
var tr = Array.ofDim[Int](max, max)
tr(0)(0) = 1
for (row <- 1 until max) {
tr(row)(0) = tr(row - 1)(row - 1)
for (i <- 1 until row + 1) {
tr(row)(i) = tr(row)(i - 1) + tr(row - 1)(i - 1)
}
}
val result = for (i <- 0 until max) yield tr(i)(0)
println (s"Bell numbers: ${result.mkString(" ")}")
}
Output:
Bell numbers = 1 1 2 5 15 52 203 877 4140 21147
Bell numbers in Python
Same algorithm again. As in Scala, the Bell triangle is mapped on a square matrix, with only the items of the triangular area actually relevant (other positions are set to 0).
max = 10
tr = [[0] * max for i in range(max)]
tr[0][0] = 1
for row in range(1, max):
tr[row][0] = tr[row - 1][row - 1]
for i in range(1, row+1):
tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];
print( [row[0] for row in tr] )
Output:
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]
Bell numbers in Julia
We also allocate a square matrix and populate it with 0’s. Only the items of the triangular area are relevant. A slight difference is that we populate a result array when we compute the first item of each row.
max = 10
tr = zeros(Int32, max, max)
tr[1, 1] = 1
results = ones(Int32, max)
for row = 2:max
res = tr[row - 1, row - 1]
tr[row, 1] = res
results[row] = res
for i = 2:row
tr[row, i] = tr[row, i-1] + tr[row - 1, i-1]
end
end
for n in results print("$n ") end
Output:
$ julia bell.jl
1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in C
We also allocate a square matrix. Only the items of the triangular area are populated and relevant. We also populate a result array when we compute the first item of each row.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int main() {
int tr[MAX][MAX];
tr[0][0] = 1;
int results[MAX] = {1};
for (int row = 1; row < MAX; row++) {
int res = tr[row - 1][row - 1];
tr[row][0] = res;
results[row] = res;
for (int i = 1; i <= row; i++) {
tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];
}
}
printf("The ten first Bell numbers are: %i ", (results[0]));
for (int i = 1; i < MAX; i++) {
printf("%d ", results[i]);
}
printf("\n");
return 0;
}
Output:
$ ./a.out
The ten first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in Awk
Just as in Julia and in C, we also allocate a square matrix. Only the items of the triangular area are populated and relevant. We also populate a result array when we compute the first item of each row.
BEGIN {
max = 10
tr[0, 0] = 1
results[0] = 1
for (row = 1; row < max; row++) {
res = tr[row -1, row -1]
tr[row, 0] = res
results[row] = res
for (i = 1; i <= row; i++) {
tr[row, i] = tr[row, i-1] + tr[row - 1, i-1]
}
}
printf("First Bell numbers are: %d ", results[0])
for (i = 1; i < max; i++) printf ("%d ", results[i])
printf("\n");
}
Output:
$ awk -f bell.awk
First Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in Ruby
I had some trouble getting the syntax right for declaring bi-dimensional arrays (and the error messages are less than awesome). But it eventually worked. Note that Ruby has this nice feature that you can use the #{ ... } to interpolate some code (e.g. the result of an expression) within a string.
max = 9
tr = Array.new(max+1){Array.new(max+1)}
tr[0][0] = 1
results = [1]
for row in 1..max
tr[row][0] = tr[row - 1][row -1]
results << tr[row][0]
for i in 1..row
tr[row][i] = tr[row][i-1] + tr[row - 1][i-1]
end
end
puts "The #{max+1} first Bell numbers are: #{results.join(" ")}"
Output:
The 10 first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147
Note: I tried to initialize max to 15 in order to generate the first 16 Bell numbers and check the program’s correctness, and the output shows that Bell numbers are growing very rapidly (faster than a geometric progression):
The 16 first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 1382958545
Bell Numbers in Pascal
As mentioned above, I took up Pascal for the first time since 1990 for task # 1. So I thought I could implement tack # 2 also in Pascal and it turned out to be quite easy:
program bell;
const
max = 9;
var
tr: array [0..max, 0..max] of integer;
row, i : integer;
begin
tr[0, 0] := 1;
for row := 1 to max do
begin
tr[row, 0] := tr[row - 1, row -1];
for i := 1 to row do
tr[row, i] := tr[row, i-1] + tr[row - 1, i-1];
end;
write('The first Bell numbers are: ');
for row :=0 to max do
write(tr[row, 0], ' ');
writeln;
end.
Output:
The first Bell numbers are: 1 1 2 5 15 52 203 877 4140 21147
Bell Numbers in D
This program is quite similar to the C program, with only a few syntax variations:
import std.stdio;
void main() {
enum MAX = 10;
int tr[MAX][MAX];
tr[0][0] = 1;
int results[MAX] = 1;
for (int row = 1; row < MAX; row++) {
tr[row][0] = tr[row - 1][row - 1];
results[row] = tr[row][0];
for (int i = 1; i <= row; i++) {
tr[row][i] = tr[row][i-1] + tr[row - 1][i-1];
}
}
writeln("The first 10 Bell numbers are: ", results);
}
Output:
The first 10 Bell numbers are: [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]
Bell Numbers in Go
Except for small syntactic differences, the program is again quite similar to the C or D implementations.
package main
import "fmt"
func main() {
const MAX int = 10
var tr [MAX][MAX]int
tr[0][0] = 1
var results [MAX]int
for row := 1; row < MAX; row++ {
tr[row][0] = tr[row-1][row-1]
results[row] = tr[row][0]
for i := 1; i <= row; i++ {
tr[row][i] = tr[row][i-1] + tr[row-1][i-1]
}
}
fmt.Println("The first Bell numbers are: ", results)
}
Output:
The first Bell numbers are: [0 1 2 5 15 52 203 877 4140 21147]
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, April 25, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Leave a comment