PWC 191

This was a busy week at work again. I managed to do both challenges in Perl 5 and Raku (I skipped Julia this time). But like last week, these are minimal contributions that just satisfy the test examples. Particularly in Challenge 2, my solution is not efficient with a bigger input. I discuss briefly here how my solutions could be improved, but haven't had time to actually attempt the better solutions.

Challenge 1 (Twice largest)

We are given a list of integers, and asked to find if the biggest integer in the list is weakly more than twice the second-biggest integer. 

This is easily done. Sort the list using a numeric sort, and then, if sorted in descending order as I did it, compare the first element in the sorted list with the second.

Here is my Perl 5 subroutine to do this:

sub twice_largest {
    my (@list)=@_;
    my @sorted_list = sort {$b <=> $a} @list;
    (($sorted_list[0]) >= (2*$sorted_list[1]))  ? 1 : (-1);
}

And here is the Raku version:

sub twice-largest (@list) {
    my @sorted_list = @list.sort({$^b <=> $^a});
    ((@sorted_list[0]) >= (2*@sorted_list[1]))  ?? 1 !! (-1);
} 

I would think that the implementation of sort in both languages is highly efficient. But if the input list is truly ginormous, the overhead from sorting and copying the list could become too much. In that case, a better solution (not attempted by me) would be to use PDL with the input as a piddle. Use the PDL built-in max method to get the max of the input piddle say $max, and then use it again to get the second-biggest element as the max of the sub-piddle where elements are strictly less than $max.  

$max=$a->max()

$second_biggest=$a->where($a<$max)->max()

Regretfully, I had no time to do it in Julia, so let me point to the Julia solution from Robert diCicco.

 

Here is my Perl 5 solution.

Here is my Raku solution. 

 

Challenge 2 (Cute list)

We are given an integer $n say between 1 and 15 inclusive. We are asked to find the number of orderings of the list (1 .. $n) that satisfy the restriction (in Raku syntax):

(@ordering[$i-1] %% $i) || ($i %% @ordering[$i-1])

for all $i, where @ordering is the candidate ordering being considered, and $i is an index between 1 and $n inclusive.

We can use the permutations routine in Raku, or the Algorithm::Permute package in Perl 5, to generate all the orderings for a list. Then we can iterate through these orderings, counting the ones that meet the condition.

This is the approach I follow. But it is not efficient as I discuss briefly below.

Here is my Raku subroutine:

sub cute-list (Int $n) {
    my @list=(1 .. $n);
    my $ctr=0;
    for (@list.permutations) -> @i {
        for (1 .. @i.elems) -> $j {
            ((@i[$j-1] %% $j) || ($j %% @i[$j-1])) || last;
            ($j==$n) && ($ctr++);
        }   
    }
    $ctr;
}

Here is the Perl 5 equivalent (using permute from Algorithm::Permute)

sub cute_list {
    my ($n)=@_;
    my @list=(1 .. $n);
    my $ctr=0;
    
    permute {
        for my $j (1 .. $n) {
            (( ($list[$j-1] % $j) == 0) || ( ($j % $list[$j-1]) == 0)) || last;
            ($j==$n) && ($ctr++);
        }   
    } @list;
    $ctr;
}

The reason why this straightforward approach is not efficient is because the number of permutations blows up real fast. My programs choke at around $n=13 for Perl 5, and Raku is worse.

A better approach (regretfully not attempted) is to directly construct and iterate through only orderings that satisfy the restriction, the number of which is far smaller than the  number of all permutations. 

An even better approach (also not attempted) could be to use that old-fashioned device called pencil and paper, with the Perls as calculation aids at most. For each index $i, we know the specific elements of (1 .. $n) that satisfy the restriction, and their number, say n[$i]. We can then use the well-known mathematics of permutations to compute, possibly in closed-form, the number of orderings that satisfy the restriction, say n[0]*n[1] ... minus the number of orderings that contain repeated numbers.

Here is my Perl 5 solution

Here is my Raku solution

Regretfully no Julia from me, so let me point again to Robert diCicco's Julia solution.