From 61b0eefa32e40d06de6dd0ab71c5079b9c9c5b6d Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 07:10:11 +0000 Subject: sol to 139 --- challenge-139/james-smith/README.md | 88 +++------------------------------- challenge-139/james-smith/blog.txt | 1 + challenge-139/james-smith/perl/ch-1.pl | 25 ++++++++++ challenge-139/james-smith/perl/ch-2.pl | 25 ++++++++++ 4 files changed, 57 insertions(+), 82 deletions(-) create mode 100644 challenge-139/james-smith/blog.txt create mode 100644 challenge-139/james-smith/perl/ch-1.pl create mode 100644 challenge-139/james-smith/perl/ch-2.pl diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index fa191ce639..ae4b2357ff 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #138 +# Perl Weekly Challenge #139 You can find more information about this weeks, and previous weeks challenges at: @@ -10,93 +10,17 @@ 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-138/james-smith/perl +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-139/james-smith/perl -# Task 1 - Workdays +# Task 1 - JortSort -***Write a script to calculate the total number of workdays in the given year. (Monday to Friday) - -## Notes - -There are either 260, 261, 262 workdays in a calendar year. - -* In a normal year there is 261 workdays unless the year both starts and finishes on a weekend (i.e. there are 260 workdays if the year starts on a Saturday or Sunday); -* In a leap year there is only 260 working days if Jan 1st is a Saturday & Dec 31st is a Sunday; 261 if Jan 1st is a Sunday or Dec 31st is a Saturday, 262 otherwise. +***You are given a list of numbers. Write a script to implement JortSort. It should return true/false depending if the given list of numbers are already sorted.*** ## The solution -So we basically need 2 pieces of information given a year? - - * Is it a leap year - * What is the first day of the year. - -We can then use a look up table which stores the number of working days (over 260) for non leap years and for leap years: - -| | Sun | Mon | Tue | Wed | Thu | Fri | Sat | -| ----------------------- | --: | --: | --: | --: | --: | --: | --: | -| **day no** | 0 | 1 | 2 | 3 | 4 | 5 | 6 | -| **#days non-leap year** | 0 | 1 | 1 | 1 | 1 | 1 | 0 | -| **#days leap year** | 1 | 2 | 2 | 2 | 2 | 1 | 0 | - -We break this calculation into 3 functions: - - * `work_days` - this does the look up - * `leap_year` - tests for leap year - * `zellers_congruence_jan_1` - uses Zeller's congruence to work out first day of the year {works for the Gregorian calendar} - -All of which -```perl -my @EXTRA_WORKDAYS = ( [0,1,1,1,1,1,0], [1,2,2,2,2,1,0] ); - -sub leap_year { - $_[0]&3 || (!($_[0]%100) && $_[0]%400) ? 0 : 1; -} -sub zellers_congruence_jan_1 { - ( 1 + $_[0]%100 + ($_[0]%100>>2) - ($_[0]/100<<1) + ($_[0]/400>>0) ) % 7; -} - -sub work_days { - 260 + $EXTRA_WORKDAYS[ leap_year $_[0] ][ zellers_congruence_jan_1 $_[0] - 1 ]; -} +# Task 2 - Long Primes -``` - -# Task 2 - Split Number - -***You are given a perfect square, Write a script to figure out if the square root the given number is same as sum of 2 or more splits of the given number.*** +***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 -We use recursion to simplify the problem - first we note that for the sqrt to be the sum of splits of the number then there are always 2 sums except in two trivial cases 0 & 1 (`n^2 = n`) so we can check this in the first wrapper function. - -As the first stage in the loop requires some "setup" - we write a wrapper function that: - - * Checks for the edge case of 0/1; - * Passes in the square root of `$n` as the total we need to compare against in the more generic `split_no` function which works out if there is a way of summing groups of digits. - -`split_no` does all the hard work. - -It takes 2 parameters - the sum required add a string of digits. We call the function recursively - - * If the the string of digits is empty we have reached the end - and check to see if the remaining sum is zero. - * If sum is less than 0 then we return 0 - no match. - * If not we split the string into 2 pieces in all ways possible and call the function. - * We reduce the sum required by the first part of the string; - * And pass the second part of the string as the string of digits. - -```perl -sub check_square { - return $_[0] <= 1 ? 0 : split_no( sqrt($_[0]), $_[0] ); -} - -sub split_no { - my( $sum, $str ) = @_; - return 0 if $sum < 0; - return 0 if $str eq '' && $sum; - return 1 if $str eq ''; - return 1 if grep { split_no( ($sum - substr $str,$_) , substr $str, 0, $_ ) } - 0 .. -1 + length $str; - return 0; -} - -``` diff --git a/challenge-139/james-smith/blog.txt b/challenge-139/james-smith/blog.txt new file mode 100644 index 0000000000..6a2d58b005 --- /dev/null +++ b/challenge-139/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/new/master/challenge-139/james-smith diff --git a/challenge-139/james-smith/perl/ch-1.pl b/challenge-139/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..2a4f349ec4 --- /dev/null +++ b/challenge-139/james-smith/perl/ch-1.pl @@ -0,0 +1,25 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Test::More; +use Benchmark qw(cmpthese timethis); +use Data::Dumper qw(Dumper); + +my @TESTS = ( + [ [1..5], 1 ], + [ [1,3,2,4,5], 0 ], +); + +is( in_order(@{$_->[0]}), $_->[1] ) foreach @TESTS; + +done_testing(); + +sub in_order { + my $p = shift; + ($p>$_) ? (return 0) : ($p=$_) foreach @_; + return 1; +} + diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..5f3150a086 --- /dev/null +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -0,0 +1,25 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); + +my( $N, $p, @primes, @long_primes ) = + ( @ARGV ? $ARGV[0] : 5, 1, 2 ); + +O: while( (@long_primes < $N) && ($p += 2) ) { + ($p % $_) || (next O) for @primes; ## next if not prime... + push @long_primes, $p if $p - rec_len($p) == 1; + push @primes, $p; +} + +say $_ for @long_primes; + +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; +} -- cgit From ecfcca386aec6e8f1ebcf35dd175bf7b6bbea09f Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 07:41:23 +0000 Subject: change while to for --- challenge-139/james-smith/perl/ch-2.pl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 5f3150a086..85c743084c 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -8,7 +8,7 @@ use feature qw(say); my( $N, $p, @primes, @long_primes ) = ( @ARGV ? $ARGV[0] : 5, 1, 2 ); -O: while( (@long_primes < $N) && ($p += 2) ) { +O: for( my $p=3; @long_primes<$N; $p+=2 ) { ($p % $_) || (next O) for @primes; ## next if not prime... push @long_primes, $p if $p - rec_len($p) == 1; push @primes, $p; -- cgit From bf73c0e75e253966ca632ff8d5252a4faed944d7 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 07:43:22 +0000 Subject: fixed variables --- challenge-139/james-smith/perl/ch-2.pl | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 85c743084c..674112f00e 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -5,11 +5,10 @@ use strict; use warnings; use feature qw(say); -my( $N, $p, @primes, @long_primes ) = - ( @ARGV ? $ARGV[0] : 5, 1, 2 ); +my( $N, @primes, @long_primes ) = ( $ARGV[0]||5, 2 ); O: for( my $p=3; @long_primes<$N; $p+=2 ) { - ($p % $_) || (next O) for @primes; ## next if not prime... + ($p % $_) || (next O) for @primes; ## next if !prime push @long_primes, $p if $p - rec_len($p) == 1; push @primes, $p; } -- cgit From bf9b3ce83d660eb72c996774e08c33778211f374 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 10:48:11 +0000 Subject: updated readme --- challenge-139/james-smith/README.md | 86 +++++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) 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. + + + + -- cgit From ca3d27889cdf87d4610a0acfbb29e83baa0c5b3d Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 11:59:37 +0000 Subject: fixed a typo --- challenge-139/james-smith/README.md | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index c648fd5c73..99f1355dc8 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #139 +# Perl Weekly Challenge #139 - "Whats recurring" You can find more information about this weeks, and previous weeks challenges at: @@ -20,7 +20,7 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-139/ja 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*); +* We start by shifting the first number of the list passed (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 @@ -62,7 +62,7 @@ that has only 4-lines. ***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 +## The 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. @@ -85,8 +85,7 @@ sub rec_len { ``` * 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. +* 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. (If you don't include the `\1+` you could end up with a shorter match as "3333" would be picked up as "33" recurring rather than "3" recurring. 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. -- cgit From a9c4e94bdbbf5ab9ffacc09b6b98300bad6945c3 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 14:15:15 +0000 Subject: remove tertiary op --- challenge-139/james-smith/perl/ch-2.pl | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 674112f00e..3c71e9fc28 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -17,8 +17,7 @@ say $_ for @long_primes; 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,$N) = ( $s.int($N/$D), ($N%$D).0 ) for 0 .. 2*$D; $s =~ m{(\d+?)\1+$}; length $1; } -- cgit From e11898347c4bba484bc44cd6b7c1ac41beeb1b45 Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 16 Nov 2021 14:16:40 +0000 Subject: Update README.md --- challenge-139/james-smith/README.md | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index 99f1355dc8..9daa5abd0d 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -77,8 +77,7 @@ 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, $N ) = ( $s.int($N/$D), ($N%$D).0 ) for 0 .. 2*$D; $s =~ m{(\d+?)\1+$}; length $1; } -- cgit From 16ecb9d62685bca3a3f7fb5257711f250ed11c61 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 14:18:05 +0000 Subject: white-space --- challenge-139/james-smith/perl/ch-1.pl | 1 - challenge-139/james-smith/perl/ch-2.pl | 1 - 2 files changed, 2 deletions(-) diff --git a/challenge-139/james-smith/perl/ch-1.pl b/challenge-139/james-smith/perl/ch-1.pl index 2a4f349ec4..481893063d 100644 --- a/challenge-139/james-smith/perl/ch-1.pl +++ b/challenge-139/james-smith/perl/ch-1.pl @@ -1,7 +1,6 @@ #!/usr/local/bin/perl use strict; - use warnings; use feature qw(say); use Test::More; diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 3c71e9fc28..8eea2a8664 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -1,7 +1,6 @@ #!/usr/local/bin/perl use strict; - use warnings; use feature qw(say); -- cgit From 45c65f5a0c94cb0d4f8b4e4e423ba7a417ef871b Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 14:44:49 +0000 Subject: save a line! --- challenge-139/james-smith/perl/ch-2.pl | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 8eea2a8664..663dab1aa6 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -7,7 +7,7 @@ use feature qw(say); my( $N, @primes, @long_primes ) = ( $ARGV[0]||5, 2 ); O: for( my $p=3; @long_primes<$N; $p+=2 ) { - ($p % $_) || (next O) for @primes; ## next if !prime + ($p % $_) || (next O) for @primes; push @long_primes, $p if $p - rec_len($p) == 1; push @primes, $p; } @@ -17,6 +17,5 @@ say $_ for @long_primes; sub rec_len { my( $D, $N, $s ) = ( shift, 1, '' ); ($s,$N) = ( $s.int($N/$D), ($N%$D).0 ) for 0 .. 2*$D; - $s =~ m{(\d+?)\1+$}; - length $1; + $s =~ /(\d+?)\1+$/ ? length $1 : 0; } -- cgit From 4221056afa7ce74e354cab181df7d026c00fc037 Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 16 Nov 2021 14:45:14 +0000 Subject: Update README.md --- challenge-139/james-smith/README.md | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index 9daa5abd0d..997f3d064b 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -78,8 +78,7 @@ 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 ) = ( $s.int($N/$D), ($N%$D).0 ) for 0 .. 2*$D; - $s =~ m{(\d+?)\1+$}; - length $1; + $s =~ /(\d+?)\1+$/ ? length $1 : 0; } ``` -- cgit From 02836f9e03621f41a745e26c7a8f357872538923 Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 16 Nov 2021 14:47:14 +0000 Subject: Update README.md --- challenge-139/james-smith/README.md | 2 ++ 1 file changed, 2 insertions(+) diff --git a/challenge-139/james-smith/README.md b/challenge-139/james-smith/README.md index 997f3d064b..b1e418d85e 100644 --- a/challenge-139/james-smith/README.md +++ b/challenge-139/james-smith/README.md @@ -90,6 +90,8 @@ So now we have this function we can look at computing the long primes. We know t 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. ``` +my( $N, @primes, @long_primes ) = ( $ARGV[0]||5 ); + O: for( my $p=3; @long_primes<$N; $p+=2 ) { ($p % $_) || (next O) for @primes; push @primes, $p; -- cgit From 454ddcad98dd9c64107406d66e4498e2266c3c7f Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 16 Nov 2021 14:50:38 +0000 Subject: don't initialise @primes - don't need to --- challenge-139/james-smith/perl/ch-2.pl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-139/james-smith/perl/ch-2.pl b/challenge-139/james-smith/perl/ch-2.pl index 663dab1aa6..8311c8a438 100644 --- a/challenge-139/james-smith/perl/ch-2.pl +++ b/challenge-139/james-smith/perl/ch-2.pl @@ -4,7 +4,7 @@ use strict; use warnings; use feature qw(say); -my( $N, @primes, @long_primes ) = ( $ARGV[0]||5, 2 ); +my( $N, @primes, @long_primes ) = ( $ARGV[0]||5 ); O: for( my $p=3; @long_primes<$N; $p+=2 ) { ($p % $_) || (next O) for @primes; -- cgit