# 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