RabbitFarm
2021-04-04
Recursion and Repeated Decimals: The Weekly Challenge 106
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
posted at: 17:04 by: Adam Russell | path: /perl | permanent link to this entry