RabbitFarm

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

Part 1

You are given an array of integers @N. Write a script to display the maximum difference between two successive elements once the array is sorted.

Solution

use strict;
use warnings;
sub max_difference_sorted{
    my(@sorted) = @_;
    return 0 if(@sorted == 1);
    my $x = $sorted[1] - $sorted[0];  
    my $y = max_difference_sorted(@sorted[1 .. @sorted - 1]);   
    return ($x > $y)? $x: $y; 
}

sub max_difference{
    my (@numbers) = @_;
    return max_difference_sorted(
        sort { $a <=> $b } @numbers
    ); 
}

MAIN:{
    my (@N);
    @N = (2, 9, 3, 5);
    print max_difference(@N) . "\n"; 
    @N = (1, 3, 8, 2, 0); 
    print max_difference(@N) . "\n"; 
    @N = (5);
    print max_difference(@N) . "\n"; 
}

Sample Run

$ perl perl/ch-1.pl
4
5
0

Notes

I believe this code is straightforward enough! max_difference performs the sort and max_difference_sorted recursively finds the largest difference as required.

Part 2

You are given numerator and denominator i.e. $N and $D. Write a script to convert the fraction into decimal string. If the fractional part is recurring then put it in parenthesis.

Solution

use strict;
use warnings;
use boolean;

sub divide{
    my($n, $d) = @_; 
    my @remainders;
    my $q = (int($n / $d)) . ".";
    my $r = $n % $d; 
    push @remainders, $r; 
    my @a;
    for (0 .. $d){
        $q .= int($r*10 / $d);  
        $r = $r*10 % $d;
        @a = grep { $remainders[$_] == $r } (0 .. @remainders - 1);
        last if(@a); 
        push @remainders, $r; 
    }
    my $r_i = $a[0];
    my $i = index($q, ".");
    my $decimal_part = substr($q, $i+1); 
    return substr($q, 0, $i + 1) . substr($decimal_part, 0, $r_i) . "(" . substr($q, $i + $r_i + 1) . ")";  
}   

sub prime_factor{
    my $x = shift(@_); 
    my @factors;    
    for (my $y = 2; $y <= $x; $y++){
        next if $x % $y;
        $x /= $y;
        push @factors, $y;
        redo;
    }
    return @factors;  
}

sub nd2decimal{
    my($n, $d) = @_;
    my $max_repetend = $d - 1; 
    my $repeats = false; 
    my @factors = prime_factor($d);
    for my $factor (@factors){
        $repeats = true if($factor != 2 && $factor != 5); 
    } 
    unless($repeats){ 
        return sprintf("%0.${max_repetend}g", $n / $d); 
    }
    else{
        my $x = divide($n, $d, [], []); 
        return $x; 
    }  
}

MAIN:{
    my($N, $D);
    ($N, $D) = (1, 3);
    print nd2decimal($N, $D) . "\n";  
    ($N, $D) = (1, 2);
    print nd2decimal($N, $D) . "\n";  
    ($N, $D) = (5, 66);
    print nd2decimal($N, $D) . "\n";  
    ($N, $D) = (1, 6);
    print nd2decimal($N, $D) . "\n";  
    ($N, $D) = (1, 8);
    print nd2decimal($N, $D) . "\n";  
}

Sample Run

$ perl perl/ch-2.pl
0.(3)
0.5
0.0(75)
0.1(6)
0.125

Notes

Part 2 is a bit trickier than the first part. The approach here is as follows:

• determine if it is a repeated decimal by checking if $d has prime factors other than 2 or 5
• if it is not a repeated decimal then this is quick work, divide and display the solution
• in the case of repeated decimals we essentially implement grade school long division in the divide function and keep track of remainders. When a remainder is repeated we know that we have found the cycle.

There are some interesting theoretical properties to repeat decimals but none are particularly helpful in actually computing them. One observation is that the length of the cycle must be smaller than the value of the denominator, whence the use of $d in the main loop in the divide function.

I’m re-using the same prime_factors function that I used in Challenge 041.

References

Challenge 106

Repeating Decimal