RabbitFarm

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

Part 1

You are given a positive integer $N. Write a script to generate all Rare Numbers of size $N if any exist.

Solution

use strict;
use warnings;

use Thread;
use constant THREAD_COUNT => 4;

sub rare_number_check{
    my($lower, $upper) = @_;
    my @rares; 
    {
        my $r = $lower;
        my $r1 = reverse($r);  
        if($r > $r1){
            my $rs = sqrt($r + $r1);  
            my $r1s = sqrt($r - $r1);  
            if($rs !~ m/\./ && $r1s !~ m/\./){
                push @rares, $lower; 
            } 
        } 
        $lower++; 
        redo unless $lower > $upper;
    }  
    return \@rares;
}

sub rare_number{
    my($n) = @_;
    my @rares; 
    my $lower = "1" . 0 x ($n - 1);
    my $upper = "1" . 9 x ($n - 1);
    my $increment = $lower;
    {
        my @threads;
        for(1 .. THREAD_COUNT){
            my $t = Thread->new(\&rare_number_check, $lower, $upper); 
            push @threads, $t;
            $lower = $upper + 1;
            $upper = $lower + $increment - 1;  
            last if(length($upper) == ($n + 1)); 
        }
        foreach my $t (@threads){
            my $rares = $t->join();
            push @rares, @{$rares}; 
        }  
        redo unless(length($upper) == ($n + 1)); 
    }
    return \@rares;  
}

MAIN:{
    my($N);
    $N=2;
    my $rares = rare_number($N); 
    print "$N digits: " . join(" ", @{$rares}) . "\n";
    $N=6;
    $rares = rare_number($N); 
    print "$N digits: " . join(" ", @{$rares}) . "\n";
    $N=9;
    $rares = rare_number($N); 
    print "$N digits: " . join(" ", @{$rares}) . "\n";
} 

Sample Run

$ perl perl/ch-1.pl
2 digits: 65
6 digits: 621770
9 digits: 281089082

Notes

My approach here is brute force, but with a slight twist. I parallelize the computations by using Threads. I’ve used Threads in the past, for example in Challenge 008 Threads were used to compute Perfect Numbers. The search for Perfect Numbers bears enough similarity to the current problem with Rare Numbers that the code from Challenge 008 will also be similar to this week’s code.

There are four CPU cores on the system I am running this code on. We can create any number of Threads that we need, of course, but Perl Threads are a special sort of “thread” in that they create new copies of the running interpreter and so consume a bit more memory than the sort of light weight threads you may learn about in C or Java. In the interest of conserving memory, and to avoid having multiple interpreter threads running on the same core we’ll just create no more than four Threads at a time. Note: Ultimately it is the OS which schedules where things run but, generally speaking, four threads on a four core system will each run on individual cores.

We can demonstrate this to ourselves by increasing the number of threads beyond the number of cores and not seeing an improvement in execution time.

Each Thread will get a slice of the search space. Each slice is of size 10 ** ($N - 1). Threads run sub rare_number_check which implements the definition of a Rare Number.

• I chose to use a bare block with redo. This is purely a matter of style and aesthetics. I’d argue that in this case it is more readable than the equivalent for or while loops would be.
• sub rare_number which generates and co-ordinates the Threads also uses redo for similar reasons.
• Interestingly Perl is clever enough to return a integer with no decimal part in the case of a perfect square! Checking to see if we have a perfect square then becomes a matter of checking to see if the value returned by sqrt contains a decimal.

Part 2

You are given a positive integer $N. Write a script to produce hash counting string of that length.

Solution

use strict;
use warnings;

sub hash_counting_string{
    my($n) = @_;
    return "" if $n == 0; 
    return "#" if $n == 1; 
    my $h = "$n#";  
    return hash_counting_string($n - length($h)) . $h;  
}

MAIN:{
    print hash_counting_string(1). "\n";
    print hash_counting_string(2). "\n";
    print hash_counting_string(3). "\n";
    print hash_counting_string(10). "\n";
    print hash_counting_string(14). "\n";
}

Sample Run

$ perl perl/ch-2.pl 
#
2#
#3#
#3#5#7#10#
2#4#6#8#11#14#

Notes

This is what I consider to be a nice clean recursive implementation. When I first saw Part 2 it seemed a bit more complicated than it would later prove to be. My thought process was along the lines of “I am not sure how I would do this in Perl, and I have no idea of how this would go in Prolog either!” Often times I will rely on the insights gained by doing it in one to aid the implementation of the other. In times like this, with no immediately clear solution, I prefer to start off in Perl, and write it in a way which would allow for reproduction in Prolog. Then, as necessary, remove any vestiges of the solution’s origins by conforming to idiomatic Prolog by ensuring things are done declaratively, logically.

This is actually a long acknowledged use of Perl: algorithm development. If you see the Prolog solution for Part 2 you can detect the obvious origins!

As far as this solution in Perl, perhaps the main “trick” is that we must account for the length of the numeral. So, for example, “14#” consumes three characters and so the next time through we need to generate the hash count for 11 = 14 - 3.

References

Challenge 102