RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

Write a script to declare a variable or constant and print it’s location in the memory.

Solution

use strict;
use warnings;
use Devel::Peek;
use Capture::Tiny q/capture_stderr/;
use constant A => "test";
my $a = 1;    
my $address;  
my $stderr = capture_stderr {
    Dump(A)
};
$stderr =~ m/at\s(0x.*\n).*/;
$address = $1;  
chomp($address);
print "Address of constant A: $address\n"; 
$stderr = capture_stderr {
    Dump($a)
};
$stderr =~ m/at\s(0x.*\n).*/;
$address = $1;  
chomp($address);
print "Address of \$a: $address\n";

Sample Run

$ perl perl/ch-1.pl
Address of constant A: 0xfd31ae90
Address of $a: 0xfdb2f770

Notes

This is a somewhat unusual challenge for Perl. Sometimes these challenges allow for a certain amount of interpretation. For example, under the hood, the representation of Perl data in memory involves more complicated data structures. I think it is in the spirit of this challenge to demonstrate access to this, without necessarily implementing complete and fully generalized solution.

Here I use Devel::Peek in order to get a report on the underlying memory usage of the given variables. The Dump function only prints a memory report to STDERR, so in order to obtain the information we seek Capture::Tiny is used to encapsulate the STDERR output and save it to a variable. A regex is then used to pull out the memory address which is then printed.

The memory address printed here is the reference address. For additional details on Perl’s core see the perlguts documentation.

Part 2

Write a script to display the first 10 Bell Numbers.

Solution

use strict;
use warnings;

sub bell_triangle{
    my($n) = @_; 
    my @bell_numbers = ([]);
    $bell_numbers[0]->[0] = 1;
    for (my $i=1; $i<=$n; $i++) {
      $bell_numbers[$i]->[0] = $bell_numbers[$i-1]->[$i-1];
      for (my $j=1; $j<=$i; $j++){  
          $bell_numbers[$i]->[$j] = $bell_numbers[$i-1]->[$j-1] + $bell_numbers[$i]->[$j-1];
       }
   }
   return $bell_numbers[$n]->[0];
}

MINA:{
    for my $b (0 .. 9){  
        print "B_$b: " . bell_triangle($b) . "\n";  
    } 
}

Sample Run

$ perl perl/ch-2.pl
B_0: 1
B_1: 1
B_2: 2
B_3: 5
B_4: 15
B_5: 52
B_6: 203
B_7: 877
B_8: 4140
B_9: 21147

Notes

This is an interesting problem. At first glance one might be tempted to proceed and compute the partitions and then take the total number of them all. Instead, it turns out that there is a simpler closed form solution whereby we can compute the Bell Triangle and then take the values on the leftmost diagonal to be the Bell Numbers as required.

For fun the Prolog solution does indeed compute the partitions instead of simply using the Bell Triangle!

References

Challenge 108

perlguts

Bell Numbers

Bell Triangle

The examples used here are from the weekly challenge problem statement and demonstrate the working solution. Also, the challenge statements are given in a Perl context although for Prolog solutions some adjustments are made to account for the differing semantics between the two languages.

Part 1

Write a script to declare a variable or constant and print it’s location in the memory.

Notes

This is a strange thing to do in Prolog since the very idea of a “variable” is dissimilar to that of imperative programming languages. Still, it is possible to do, especially with Gnu Prolog’s foreign/2, part of the Foreign Language Interface. This requires us to write some code in C and in this way we can surely report on the memory address used by whatever Prolog variable we want to examine. I will admit to being intrigued by this but at present did not have the opportunity to explore this. For now I am leaving these notes here as a placeholder to investigate this further if/when the opportunity allows.

Part 2

Write a script to display the first 10 Bell Numbers.

Solution

:-initialization(main).

addElement(Element, [FirstList | OtherLists], [ [Element|FirstList] | OtherLists]).
addElement(Element, [FirstList | OtherLists], [ FirstList | Temp] ):- 
    addElement(Element, OtherLists, Temp).

partition([Single], [[Single]]).
partition([First|Others], [[First] | Result]) :-
    partition(Others, Result).
partition([First|Others], Result) :-
    partition(Others, Temp),
    addElement(First, Temp, Result).

bell_numbers(N):-
    \+ N == 0,  
    N < 10,
    length(L0, N), 
    setof(P, partition(L0, P), Partitions), 
    length(Partitions, L),
    write('B_'), write(N), write(': '), write(L), nl,
    N0 is N + 1, 
    bell_numbers(N0).   
bell_numbers(N):-
    N == 0,
    write('B_'), write(N), write(': '), write(1), nl,
    N0 is N + 1,
    bell_numbers(N0).     
bell_numbers(_).   

main:-
    bell_numbers(0), 
    halt.    

Sample Run

$ gplc ch-2.p 
$ prolog/ch-2
B_0: 1
B_1: 1
B_2: 2
B_3: 5
B_4: 15
B_5: 52
B_6: 203
B_7: 877
B_8: 4140
B_9: 21147

Notes

This code uses a known Prolog idiom for computing partitions of the list for each Bell Number. It is, of course, possible to simply compute these using a closed form approach as I did for the Perl solution for this same problem. Since this is Prolog I figured this method may be a bit more fun!

Since we don’t really care about what is in the list, only that the elements be unique to allow for proper partitioning, that a list of uninstantiated variables works just fine.

And yeah, probably I should have started computing the numbers with 10 instead of 0 and used format/2 instead of a bunch of write/1s, but this code was just a quick bit of fun.

References

Challenge 108

Bell Numbers

Bell Triangle