diff options
| -rw-r--r-- | challenge-139/james-smith/README.md | 86 |
1 files changed, 86 insertions, 0 deletions
diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index ae4b2357ff..c648fd5c73 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -18,9 +18,95 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-139/ja ## The solution +This challenge is relatively easy - to see if the list of numbers if monotonically increasing we just have to check that each entry is bigger than the one before. + +* We start by shifting the first number of the list passeda (this is the *previous number*); +* The loop through the rest comparing the current number against the previous number. + * If the number is less than the previous number we return `0`; + * Otherwise we set previous number `$p` to the current number and continue +* If we get to the end of the list then the list is sorted and we return `1`. + +``` +sub in_order { + my $p = shift; + ($p>$_) ? (return 0) : ($p=$_) for @_; + return 1; +} +``` + +**Notes:** + +* We can rewrite the `if( $x ) { y } else { z }` and `($x) ? (y) : (z)`. Why is this useful - well we can then use the brace less postfix `for` for the loop rather than having to use braces. This means the loop becomes 1 line, rather than the longer 7 line version using K&R braces. If you don't cuddle your braces it is even longer! + +``` + for (@_) { + if( $p>$_ ) { + return 0; + } else { + $p = $_; + } + } +``` + +Admittedly there is an intermediate version... That uses the exit early approach.. + +``` + for (@_) { + return 0 if $p>$_; + $p = $_; + } +``` +that has only 4-lines. + # Task 2 - Long Primes ***Write a script to generate first 5 Long Primes. A prime number `p` is called Long Prime if `1/p` has an infinite decimal expansion repeating every `p-1` digits.*** ## Solution +Now this challenge is not so easy - but those of us who have been working on the challenges for more than 6 months would have already worked out parts of fractions which are recursive. There were many solutions for this - if you didn't do the challenge. + +You can see mine at: + +https://github.com/drbaggy/perlweeklychallenge-club/blob/master/challenge-106/james-smith/perl/ch-2.pl + +Now we don't require the actual part of the number repeats which makes the function simpler, and we know explicitly that the numerator is going to be 1. + +This gives us the function below to get the length of the recurring sequence. + +``` +sub rec_len { + my( $D, $N, $s ) = ( shift, 1, '' ); + ($s,$N) = $D>$N ? ($s.0, $N.0) + : ($s.int($N/$D),($N%$D).0) for 0 .. 2*$D; + $s =~ m{(\d+?)\1+$}; + length $1; +} +``` + +* We compute twice the number of digits than the denominator, we generate this as a string but using long-division to compute each digit. + +* We then see if there is any repeating sequence (tied to the end of the sting we generate). We then get the length of this recurrent string. + +So now we have this function we can look at computing the long primes. We know that `1/2` doesn't recur so we can rule this out - that means we are only considering odd primes. + +Therefore we loop through all the odd numbers checking to see if the number is a prime, if it is we then check for the property that the recurring sequence has `$p-1` digits. + +``` +O: for( my $p=3; @long_primes<$N; $p+=2 ) { + ($p % $_) || (next O) for @primes; + push @primes, $p; + push @long_primes, $p if $p - rec_len($p) == 1; +} +``` +We will now break this down. +* The `for` line is obvious - repeat increasing `$p` by two until we have sufficient long primes. +* The next line loops through all current known primes to see if they are factor of `$p` - if yes skips to the next outer loop. + * We use `next O` to jump out of the inner `for` loop, and to the start of the next outer `for` loop - labelled `O`. + * We again use a trick to flatten the loop with a conditional: `($p % $_) || (next O)` if the first part is true the "or" `||` is true, so we don't evaluate the second part. But it `$_` is a factor of `$p` the left hand side is `0` (false) and so we need to evaluate it to see if the right hand side is true - and in the evaluation - skips to the start of the loop by executing `next O`. +* We know it has no known prime factors in line 3 so we add it to the list of primes. +* Then we use our `rec_len` function to see if the number is in fact a long prime. + + + + |