RabbitFarm

The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.

Part 1

You are given positive integers, $m and $n. Write a script to find total count of divisors of $m having last digit $n.

Solution

use strict;
use warnings;
sub factor{
    my($n) = @_;
    my @factors = (1);
    foreach  my $j (2 .. sqrt($n)){
        push @factors, $j if $n % $j == 0;
        push @factors, ($n / $j) if $n % $j == 0 && $j ** 2 != $n;
    }
    return @factors;  
}

sub divisors_last_digit{
    my($m, $n) = @_;
    my @divisors;   
    my @factors = factor($m);
    {
        my $factor = pop @factors;
        push @divisors, $factor if $n == substr($factor, -1);    
        redo  if @factors;  
    }    
    return sort {$a <=> $b} @divisors;   
}

MAIN:{
    my($m, $n); 
    my @divisors;
    ($m, $n) = (24, 2); 
    @divisors = divisors_last_digit($m, $n);
    print "($m, $n): " . @divisors . " --> " . join(", ", @divisors) . "\n";  
    ($m, $n) = (75, 5); 
    @divisors = divisors_last_digit($m, $n);
    print "($m, $n): " . @divisors . " --> " . join(", ", @divisors) . "\n";  
    ($m, $n) = (30, 5); 
    @divisors = divisors_last_digit(30, 5);
    print "($m, $n): " . @divisors . " --> " . join(", ", @divisors) . "\n";  
}

Sample Run

$ perl perl/ch-1.pl
(24, 2): 2 --> 2, 12
(75, 5): 3 --> 5, 15, 25
(30, 5): 2 --> 5, 15

Part 2

Implement Sleep Sort.

Solution

use strict;
use warnings;
use Thread::Pool;

sub create_workers{
    my @numbers = @_; 
    my $count = @numbers; 
    my $workers = new Thread::Pool({
        optimize => "cpu", 
        do => \&sleeper, 
        workers => $count,
        maxjobs => $count, 
        minjobs => $count 
    });
    return $workers;
}

sub sleeper{
    my($n) = @_; 
    sleep($n);
    return $n;   
}

sub sleep_sort{
    my($numbers, $workers) = @_; 
    my @jobs;
    my @sorted;   
    for my $n (@{$numbers}){
        my $job_id = $workers->job($n);
        push @jobs, $job_id;   
    } 
    {
        my $job = pop @jobs;     
        my @result = $workers->result_any(\$job);
        if(!@result){    
            push @jobs, $job;  
        }
        else{
            push @sorted, $result[0]; 
        }
        redo if @jobs; 
    }
    $workers->shutdown; 
    return @sorted;   
}

MAIN:{
    my @numbers;
    my @sorted; 
    @numbers = map{int(rand($_) + 1)} (0 .. 9);  
    print join(", ", @numbers) . "\n"; 
    @sorted = sleep_sort(\@numbers, create_workers(@numbers));  
    print join(", ", @sorted) . "\n"; 
}  

Sample Run

$ perl perl/ch-2.pl
1, 1, 1, 3, 2, 3, 4, 7, 8, 6
1, 1, 1, 2, 3, 3, 4, 6, 7, 8
$ perl perl/ch-2.pl
1, 1, 1, 2, 2, 5, 5, 2, 1, 9
1, 1, 1, 1, 2, 2, 2, 5, 5, 9

Notes

I hope participants in The Weekly Challenge enjoyed this! After I saw Jort Sort in Challenge 139 I was reminded of other joke sorts and suggested this as a future challenge. Happily the suggestion was accepted!

Threading is easy in Perl, which uses an "Interpreter Threads" ("ithreads") model. Node.js programmers will find this model familiar as it is exactly what that language uses. Unfortunately Perl's documentation writers are not as familiar with concurrent and parallel programming topics and some of the official documentation needs updating. Unfortunately, this is a bizarrely contentious issue.

To ensure you are using a perl interpreter with proper ithreads support try this one-liner: $ perl -Mthreads -e 0. If that runs without error you are good to go! If you get an error you'll need to install a new perl. One convenient option is to use Perlbrew. After installing perlbrew you'll need to invoke it like this perlbrew install perl-5.34.0 -Dusethreads. Please see the Perlbrew documentation for additional (straightforward) details if you decide to undertake this.

Here rather than use threads directly Thread::Pool is used. This is a convenient pattern for using Perl's ithreads. Since each ithread is really a new perl interpreter process this allows for some fine tuning of the number of ithreads created to help conserve memory usage. In this case the memory conservation is actually somewhat minimal since Sleep Sort requires us to start a new ithread for each element of the array to be sorted. Amusingly, because of the process based threading model, we can quickly crash the program by attempting to sort an array whose size causes the system to exceed the number of allowed processes. Remember, this is a joke sort, right!?!?

Typically you'd create a pool of workers whose number matched the number of CPU cores available. That way each core could be tasked by the OS for whatever CPU intensive code you'd care to run without the ithreads competing too badly with each other.

Concurrent and parallel programming issues are somewhat advanced. Excellent documentation exists that is both Perl specific and more general. Be sure to understand the difference between ithreads and so called "co-operative thread" models (as used in modules such as Coro. The "advanced" nature of this topic is due to understanding the various trade-offs at play. Deep understanding usually comes from experience of implementing solutions this way and study of the underlying Operating System concepts. Even the most modest modern computer systems systems available have multiple cores at your disposal as a programmer so this effort is certainly worthwhile! The bibliography of perlthrtut is an excellent starting point.

References

Challenge 142

Sleep Sort

perlthrtut

Thread::Pool

Node.js Workers