diff options
| -rw-r--r-- | challenge-136/james-smith/README.md | 98 |
1 files changed, 37 insertions, 61 deletions
diff --git a/challenge-136/james-smith/README.md b/challenge-136/james-smith/README.md index abbce3740c..b0b3dc8889 100644 --- a/challenge-136/james-smith/README.md +++ b/challenge-136/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #135 +# Perl Weekly Challenge #136 You can find more information about this weeks, and previous weeks challenges at: @@ -10,88 +10,64 @@ submit solutions in whichever language you feel comfortable with. You can find the solutions here on github at: -https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-135/james-smith/perl +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-136/james-smith/perl -# Task 1 - Middle three digits +# Task 1 - Two friendly -***You are given an integer. Write a script find out the middle 3-digits of the given integer, if possible otherwise throw sensible error.*** +***You are given 2 positive numbers, `$m` and `$n`. Write a script to find out if the given two numbers are "Two friendly".*** -## The solution +*Two positive numbers, `m` and `n` are two friendly when `gcd(m, n) = 2 ^ p` where `p > 0`. The greatest common divisor (gcd) of a set of numbers is the largest positive number that divides all the numbers in the set without remainder.* -Obviously using `substr $n, ??, 3` will give a 3-digit chunk of a number - so what are the errors... +## The solution - * Not an integer - doesn't match `/^-?\d+$/` - * Less than 3 digits - length less than 3 - * Does not have a unique "central 3-digits" *i.e.* has even length +The logic of our solution is (1) find the GCD; (2) check they are not co-prime (GCD = 1); (3) The GCD is a power of 2 -The value of the `??` is the expression above - `( length number - 3 ) / 2` +We can test the last case by converting the GCD into binary - and checking to see if it has the form `10+`. Alternatively we can use `&` and `>>=` to remove trailing zeros. All that gives us the simple function.... ```perl -sub middle3 { - my $n = shift; - return 'Not a number' unless $n =~ m{^-?\d+$}; - my $l = length( $n = abs $n ); - return $l < 3 ? 'Too short' - : $l % 2 ? substr $n, ( $l - 3 ) / 2, 3 - : 'Even digits' - ; +sub friendly { + my($a,$b) = @_; + ($a,$b) = ($b,$a%$b) while $b; ## Compute GCD + return 0 if $a == 1; ## Co-prime not friendly + $a>>=1 until $a&1; ## Remove trailing 0s + return $a == 1 ? 1 : 0; ## Friendly iff } -``` - -It is possible to compact this slightly - buy 1 - assuming `$n` is an integer, and then rewriting `($l-3)/2` as `$l/2-1` - which is good enough for the `substr` to work. -```perl -sub middle3compact { - my$l=length(my$n=abs$_[0]); - $l<3?'Too short':$l%2?substr$n,$l/2-1,3:'Even digits' -} ``` -# Task 2 - Validate SEDOL +# Task 2 - Fibonacci Sequence -***You are given 7-characters alphanumeric SEDOL. Write a script to validate the given SEDOL. Print 1 if it is a valid SEDOL otherwise 0.*** +***You are given a positive number `$n`. Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number. *** ## Solution -You find about SEDOL (Stock Exchange Daily Official List) numbers on Wikipedia at https://en.wikipedia.org/wiki/SEDOL. - -The consist of 6 digits/consonants + a checksum digit. The weighted sum of the 6 digits + the checksum is a multiple of 10. -The weights are 1, 3, 1, 7, 3 and 9 for the six digits and 1 for the checksum. - -We have to: - * validate the number is of valid format for a SEDOL number - 6 numbers or consonants & a single number. - * compute the weighted sum (using ord to convert the B-Z characters to their numeric equivalends) - * check to see if it is a multiple of 10 - +There are two bits to this: + * get a list of fibonacci numbers `<= $n`. Easier to find list up to the first fibonnaci number `> $n`. + * We have a cache of the fibonnaci numbers - we just need to extend it to include all those fibonnaci numbers below `$n` (if required). + * get a list of sums of these numbers which equal `$n` + * We call a generic "get-sum" method where we pass in our target number and array of fibonacci numbers + * this get-sum method is then call recursively to count the number of totals + ```perl -sub is_sedol { -## Check correct format... numbers and consonants only - return 0 unless $_[0] =~ m{^[0-9B-HJ-NP-TW-Z]{6}\d$}; - -## Accumulator and weights for each character - my( $t, @w ) = qw(0 1 3 1 7 3 9 1); -## Calculate SEDOL sum... note YODA sum -55 + ord $_ to avoid precedence issue - $t += ( /\d/ ? $_ : -55 + ord $_ ) * shift @w for split //, $_[0]; +my @fib; -## Return true (1) if total modulo 10 is 0, and false (0) otherwise - return $t % 10 ? 0 : 1; +sub fib_sum { + my $n = shift; + push @fib, $fib[-1] + $fib[-2] while $n > $fib[-1]; + return sum( $n, grep { $_ <= $n } @fib ); } -``` -Again we can compact the code - by removing spaces and a couple of rewrites: - - * replace `unless $x=~//` with `if $x!~//`; - * flip `@w` and use `pop`. - * Note `0if` expands as `0 if`. - -```perl -sub is_sedol_compact { - return 0if$_[0]!~/^[\dB-HJ-NP-TW-Z]{6}\d$/; - my($t,@w)=qw(0 1 9 3 7 1 3 1); - $t+=(/\d/?$_:-55+ord$_)*pop@w for split//,$_[0]; - $t%10?0:1 +sub sum { + local $_; + my ( $t, @n ) = @_; + return 1 unless $t; + return 0 if $t < 0; + my $c = 0; + $c += sum( $t - $_, @n ) while $_ = shift @n; + return $c; } + ``` |