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

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

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

Solution

:-initialization(main).

perfect_square(N):-
    A is floor(sqrt(N)), 
    N is A * A.

rare(N, N, Rares, Rares). 
rare(Lower, Upper, RareAccum, Rares):-
    number_codes(Lower, C),
    reverse(C, CR), 
    number_codes(R1, CR),
    X0 is Lower + R1,
    X1 is Lower - R1,
    perfect_square(X0),
    perfect_square(X1),
    Next is Lower + 1,
    rare(Next, Upper, [Lower|RareAccum], Rares).
rare(Lower, Upper, RareAccum, Rares):-
    Next is Lower + 1,
    rare(Next, Upper, RareAccum, Rares).

rare_numbers(N, Rares):-
    Lower is 10 ^ (N - 1),   
    Upper is (10 ^ N) - 1,
    rare(Lower, Upper, [], Rares). 

main:-
    rare_numbers(2, Rares2),
    write(Rares2), nl, 
    rare_numbers(6, Rares6),
    write(Rares6), nl, 
    rare_numbers(9, Rares9),
    write(Rares9), nl,
    halt.

Sample Run

$ gplc prolog/ch-1.p
$ prolog/ch-1
[65]
[621770]
[281089082]

Notes

This is maybe straightforward bit of Prolog with arithmetic. One might say that I missed an opportunity to use between/3 but, in fact, I was happy to terminate the recursion of rare/4 by identifying the case where the first two arguments (Lower and Upper) are equal.

Part 2

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

Solution

:-initialization(main).

hcs(0, String, String).
hcs(1, StringAccum, String):-
    hcs(0, [35|StringAccum], String). 
hcs(N, StringAccum, String):-
    number_codes(N, C),
    append(C, "#", Accum), 
    length(Accum, L),
    N0 is N - L, 
    append(Accum, StringAccum, StringAccum0), 
    hcs(N0, StringAccum0, String). 

hash_counting_string(N, String):-
    hcs(N, [], S),
    atom_codes(String, S).

main:-
    hash_counting_string(1, String1), 
    write(String1), nl,
    hash_counting_string(2, String2), 
    write(String2), nl, 
    hash_counting_string(3, String3), 
    write(String3), nl, 
    hash_counting_string(10, String10), 
    write(String10), nl, 
    hash_counting_string(14, String14), 
    write(String14), nl,
    halt.

Sample Run

$ gplc ch-2.p 
$ prolog/ch-2
#
2#
#3#
#3#5#7#10#
2#4#6#8#11#14#

Notes

As mentioned elsewhere I first wrote a solution to this in Perl. This code, follows pretty directly from that, a clean bit of recursion. Probably we should prefer a more prological piece of code versus this which is more …what should we call it…procursive? That is, recursive fairly functional style code which does not make much use of the power of Prolog backtracking.

Time is running out to submit solutions for Weekly Challenge 102, but I can imagine a solution which uses DCGs perhaps? The hash counting string being assembled by processing a list of success numbers which in turn generate the appropriate characters. I’ll update this article if I get a chance.

References

Challenge 102 Rare Numbers