From 09f7f9432bb8bb5dfe4f47e8d3ba00a2fe461f53 Mon Sep 17 00:00:00 2001 From: James Smith Date: Sun, 3 Apr 2022 22:31:58 +0100 Subject: Update README.md --- challenge-158/james-smith/README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-158/james-smith/README.md b/challenge-158/james-smith/README.md index 342202ccbf..a81bb61a28 100644 --- a/challenge-158/james-smith/README.md +++ b/challenge-158/james-smith/README.md @@ -94,7 +94,7 @@ sub additive_primes_split_sum0 { * `split` - 75% * `sum0 split` - 45% -# Challenge 2 - First series buban primes +# Challenge 2 - First series cuban primes ***Write a script to compute first series cuban primes <= 1000. (First series cuban primes have the form `((x+1)^3-x^3)/(x+1-x)` = `3x^2+3x+1`)*** -- cgit From 9bd3a76992e2c016e85625c4d94969ec05ca7a43 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 4 Apr 2022 07:32:24 +0100 Subject: 159 --- challenge-159/james-smith/README.md | 130 +++++++++------------------------ challenge-159/james-smith/blog.txt | 1 + challenge-159/james-smith/perl/ch-1.pl | 20 +++++ challenge-159/james-smith/perl/ch-2.pl | 39 ++++++++++ 4 files changed, 94 insertions(+), 96 deletions(-) create mode 100644 challenge-159/james-smith/blog.txt create mode 100644 challenge-159/james-smith/perl/ch-1.pl create mode 100644 challenge-159/james-smith/perl/ch-2.pl diff --git a/challenge-159/james-smith/README.md b/challenge-159/james-smith/README.md index 342202ccbf..cb08f40942 100644 --- a/challenge-159/james-smith/README.md +++ b/challenge-159/james-smith/README.md @@ -1,6 +1,6 @@ -[< Previous 157](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-157/james-smith) | -[Next 159 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-159/james-smith) -# The Weekly Challenge 158 +[< Previous 156](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-156/james-smith) | +[Next 160 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-160/james-smith) +# The Weekly Challenge 159 You can find more information about this weeks, and previous weeks challenges at: @@ -12,120 +12,58 @@ 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-158/james-smith +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-159/james-smith -# Challenge 1 - Additive primes +# Challenge 1 - Farey Sequence -***Additive primes are prime numbers for which the sum of their decimal digits are also primes.*** +*** You are given a positive number, `$n`. Write a script to compute Farey Sequence of the order `$n`. All rational numbers less than with with denominators less than `$n` ## The solution -We loop through each prime p, work out the digit sum (by repeated modulo 10/divide by 10) and check that it is prime. -We craft this as two loops - an outer `for` loop and an inner `do {} while`. - -```perl -use Math::Prime::Util qw(next_prime is_prime); - -sub additive_primes { - my @res; - for( - my $p = 2 ; - my $s = 0, ( my $q = $p ) <= $N; - (is_prime $s) && (push @res, $p), $p = next_prime $p - ) { - do { $s += $q % 10 } while $q = int $q / 10; - } - @res; -} -``` -## Output -``` -2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89 -``` -## Notes - * We use a C-style `for` loop, with it's three parts *initialization*, *condition* and *increment*. - * The *condition* and *increment* statements are complicated, each with two parts separated by `,`s. - * The *condition* block is called at the start of each loop, and so we use it to initialise the variables as the loop, as well as checking the condition. - * The *increment* block is called at the end of the loop and so stores the value of `$p` if it is an additive prime, then it increments the loop with the next prime. - * Rather than doing a split and sum we use repeated dividing and summing, as it is more efficient around 20-30% more efficient. The increased performance is probably due to avoiding the "duality" of perl variables storing numbers as numbers/strings. - -## Extra code - -Rewritten with single line `for` ... (the original version of the code) - -```perl -sub additive_primes_div { - my @res; - for(my$p=2; my$s=0,(my $q=$p)<=$N;(is_prime$s)&&(push@res,$p),$p=next_prime$p) { - do { $s += $q % 10 } while $q = int $q / 10; - } - @res; -} -``` - -Alternative form with `for split`: - ```perl -sub additive_primes_split { - my @res; - for( my $p = 2; my $s = 0, $p <= $N ; $p = next_prime $p ) { - $s+=$_ for split //, $p; - push @res, $p if is_prime $s; +sub farley { + my($n,%v) = shift; + for my $d (1..$n) { + $v{$_/$d}||="$_/$d" for 1..$d; } - @res; + map{$v{$_}}sort{$a<=>$b}keys%v; } ``` -And an alternate using `sum0`... - -```perl -sub additive_primes_split_sum0 { - my @res; - for( my $p = 2; $p <= $N ; $p = next_prime $p ) { - push @res, $p if is_prime sum0 split //, $p; - } - @res; -} -``` +# Challenge 2 - Moebius Number -### Relative performance +***You are given a positive number `$n`. Write a script to generate the Moebius Number for the given number (see defn below) - * `div`/`mod` method - 100% - * `split` - 75% - * `sum0 split` - 45% +## Definition -# Challenge 2 - First series buban primes +The value of the Moebius number is: -***Write a script to compute first series cuban primes <= 1000. (First series cuban primes have the form `((x+1)^3-x^3)/(x+1-x)` = `3x^2+3x+1`)*** + * `0` if `$n` has a prime factor + * `1` if the number has an even number of prime factors + * `-1` otherwise ## The solution -The solution is rather short. We try each of the value of the sequence `3*$x**2+3*$x+1` in turn up to the value of 1000 (`$N`). -We output each value which in turn is prime. - ```perl -(is_prime $_) && say while $N >= ($_ = 3*$x*++$x+1); -``` -## Output -``` -7, 19, 37, 61, 127, 271, 331, 397, 547, 631, 919 +sub moebius { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime($n); + $n%($p**2) ? ($n%$p && ($r=-$r)) : return 0 while ($p = next_prime $p) < $n; + $r; +} ``` -## Notes - * As we use `$_` as our temporary variable we can use `say` by itself to output it. - * We use our common trick of `(condition) && (command)` to work as an `command if(condition)` which can be embedded in a postfix loop. - * There is a "trick" as we increment `$x` half way through the calculation of `$_`. - * `$_ = 3*$x**2 + 3*$x + 1` => `$_ = 3 * $x * ($x+1) + 1` => `$_ = 3 * $x * ++$x + 1` - * We can replace the `$x+1` by the pre increment operator `++$x` so this becomes `3 * $x * ++$x + 1`. -## Aside +Expanding this out gives the more readable (but longer)... -Second series cuban primes have the form `((x+2)^3-x^3)/(x+2-x)` = `3x^2+3.2x+4`. We can tweak the code to give: - -```perl -(is_prime $_) && say while $N >= ($_ = 3 * $x * (2 + $x++) + 4); ``` +sub moebius_exp { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime($n); + while( ($p = next_prime $p ) < $n ) { + return 0 unless $n%($p**2); + $r=-$r unless $n%$p; + } + $r; +} -which outputs: -``` -13, 109, 193, 433, 769 ``` diff --git a/challenge-159/james-smith/blog.txt b/challenge-159/james-smith/blog.txt new file mode 100644 index 0000000000..e631de6584 --- /dev/null +++ b/challenge-159/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-159/james-smith diff --git a/challenge-159/james-smith/perl/ch-1.pl b/challenge-159/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..5f6402ec41 --- /dev/null +++ b/challenge-159/james-smith/perl/ch-1.pl @@ -0,0 +1,20 @@ +#!/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); + +say join ', ', farley( $_ ) for 1..10; + +sub farley { + my($n,%v) = shift; + for my $d (1..$n) { + $v{$_/$d}||="$_/$d" for 1..$d; + } + map{$v{$_}}sort{$a<=>$b}keys%v; +} + diff --git a/challenge-159/james-smith/perl/ch-2.pl b/challenge-159/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..5c86128a4d --- /dev/null +++ b/challenge-159/james-smith/perl/ch-2.pl @@ -0,0 +1,39 @@ +#!/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); +use Math::Prime::Util qw(next_prime is_prime); + +my @TESTS = ( + [ 5, -1 ], + [ 10, 1 ], + [ 20, 0 ], +); + +is( moebius( $_->[0]), $_->[1] ) foreach @TESTS; +is( moebius_exp($_->[0]), $_->[1] ) foreach @TESTS; + +done_testing(); + +sub moebius { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime($n); + $n%($p**2) ? ($n%$p && ($r=-$r)) : return 0 while ($p = next_prime $p) < $n; + $r; +} + +sub moebius_exp { + my ($n,$p,$r) = (shift,1,1); + return -1 if is_prime($n); + while( ($p = next_prime $p ) < $n ) { + return 0 unless $n%($p**2); + $r=-$r unless $n%$p; + } + $r; +} + -- cgit From c748d446c61a5f4c1923e88b09bebb75c26997c2 Mon Sep 17 00:00:00 2001 From: Mark <53903062+andemark@users.noreply.github.com> Date: Mon, 4 Apr 2022 06:34:44 +0000 Subject: Challenge 159 Solutions (Raku) --- challenge-159/mark-anderson/raku/ch-1.raku | 24 ++++++++++++++++++++++++ challenge-159/mark-anderson/raku/ch-2.raku | 14 ++++++++++++++ 2 files changed, 38 insertions(+) create mode 100644 challenge-159/mark-anderson/raku/ch-1.raku create mode 100644 challenge-159/mark-anderson/raku/ch-2.raku diff --git a/challenge-159/mark-anderson/raku/ch-1.raku b/challenge-159/mark-anderson/raku/ch-1.raku new file mode 100644 index 0000000000..652d28a6af --- /dev/null +++ b/challenge-159/mark-anderson/raku/ch-1.raku @@ -0,0 +1,24 @@ +#!/usr/bin/env raku + +use Test; + +is-deeply farey-seq(5), (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1), 'example 1'; + +is-deeply farey-seq(7), (0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1), 'example 2'; + +is-deeply farey-seq(4), (0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1), 'example 3'; + +is farey-seq(100).elems, 3045, 'https://oeis.org/A005728/b005728.txt'; + +sub farey-seq(\n) +{ + return 0/1, 1/n, { next-term($^f, $^s) } ... 1/1; + + sub next-term(\f, \s) + { + my (\a, \b) = f.nude; + my (\c, \d) = s.nude; + my \k = (n + b) div d; + (k * c - a) / (k * d - b) + } +} diff --git a/challenge-159/mark-anderson/raku/ch-2.raku b/challenge-159/mark-anderson/raku/ch-2.raku new file mode 100644 index 0000000000..5d69eda71d --- /dev/null +++ b/challenge-159/mark-anderson/raku/ch-2.raku @@ -0,0 +1,14 @@ +#!/usr/bin/env raku + +use Prime::Factor; +use Test; + +is-deeply ( 1..10)>>.&mobius, ( 1, -1, -1, 0, -1, 1, -1, 0, 0, 1); +is-deeply (11..20)>>.&mobius, (-1, 0, -1, 1, 1, 0, -1, 0, -1, 0); + +sub mobius(\n) +{ + my @a = prime-factors(n); + return 0 if @a.squish < @a; + return @a %% 2 ?? 1 !! -1; +} -- cgit From 14dda6355b6f7ee3734a67fa17f126bfc32e7efd Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 09:41:59 +0200 Subject: Task 1 done --- challenge-159/luca-ferrari/raku/ch-1.p6 | 16 ++++++++++++++++ challenge-159/luca-ferrari/raku/ch-2.p6 | 2 ++ 2 files changed, 18 insertions(+) create mode 100755 challenge-159/luca-ferrari/raku/ch-1.p6 create mode 100644 challenge-159/luca-ferrari/raku/ch-2.p6 diff --git a/challenge-159/luca-ferrari/raku/ch-1.p6 b/challenge-159/luca-ferrari/raku/ch-1.p6 new file mode 100755 index 0000000000..e8a45c1b94 --- /dev/null +++ b/challenge-159/luca-ferrari/raku/ch-1.p6 @@ -0,0 +1,16 @@ +#!raku +# Perl Weekly Challenge 159 + + +sub MAIN( Int $n where { $n > 0 } ) { + my $start = 0/1.Rat; + my $end = 1/1.Rat; + + my @farey = $start, $end; + + for 2 .. $n -> $denominator { + @farey.push( |( 1 .. $denominator ).map: * / $denominator ); + } + + @farey.unique.sort.map( *.nude.join( '/' ) ).say; +} diff --git a/challenge-159/luca-ferrari/raku/ch-2.p6 b/challenge-159/luca-ferrari/raku/ch-2.p6 new file mode 100644 index 0000000000..4f7c3ef22b --- /dev/null +++ b/challenge-159/luca-ferrari/raku/ch-2.p6 @@ -0,0 +1,2 @@ +#!raku +# Perl Weekly Challenge 159 -- cgit From b736fb2f6a230c678badabac696aa77ac0d6c3e1 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 10:05:53 +0200 Subject: Task 2 done --- challenge-159/luca-ferrari/raku/ch-2.p6 | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) mode change 100644 => 100755 challenge-159/luca-ferrari/raku/ch-2.p6 diff --git a/challenge-159/luca-ferrari/raku/ch-2.p6 b/challenge-159/luca-ferrari/raku/ch-2.p6 old mode 100644 new mode 100755 index 4f7c3ef22b..5f9a75537e --- a/challenge-159/luca-ferrari/raku/ch-2.p6 +++ b/challenge-159/luca-ferrari/raku/ch-2.p6 @@ -1,2 +1,30 @@ #!raku # Perl Weekly Challenge 159 + +sub prime-factors( Int $n ) { + my $number = $n; + my @factors; + + my $factor = 2; + while ( $number > 1 && $factor <= $number ) { + if ( $number %% $factor ) { + @factors.push: $factor; + $number /= $factor; + } + else { + $factor++; + } + } + + return @factors; +} + + +sub MAIN( Int $n where { $n > 0 } ) { + + my @prime-factors = prime-factors( $n ); + '0'.say and exit if @prime-factors.elems != @prime-factors.unique.elems; + '1'.say and exit if @prime-factors.unique.elems %% 2; + '-1'.say and exit; + +} -- cgit From b91c8355370302f29a2380e43685737ff644b9f2 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 10:21:30 +0200 Subject: Task 1 done in Pl/Perl --- challenge-159/luca-ferrari/postgresql/ch-1.plperl | 39 +++++++++++++++++++++++ challenge-159/luca-ferrari/postgresql/ch-1.sql | 1 + challenge-159/luca-ferrari/postgresql/ch-2.sql | 1 + 3 files changed, 41 insertions(+) create mode 100644 challenge-159/luca-ferrari/postgresql/ch-1.plperl create mode 100644 challenge-159/luca-ferrari/postgresql/ch-1.sql create mode 100644 challenge-159/luca-ferrari/postgresql/ch-2.sql diff --git a/challenge-159/luca-ferrari/postgresql/ch-1.plperl b/challenge-159/luca-ferrari/postgresql/ch-1.plperl new file mode 100644 index 0000000000..f14fe72613 --- /dev/null +++ b/challenge-159/luca-ferrari/postgresql/ch-1.plperl @@ -0,0 +1,39 @@ +CREATE SCHEMA IF NOT EXISTS pwc159; + +CREATE OR REPLACE FUNCTION +pwc159.farey( int ) +RETURNS SETOF text +AS $CODE$ + my ($n) = @_; + + my %farey; + + for my $denominator ( 2 .. $n ) { + for my $number ( 1 .. $denominator ) { + + # reduce things like 2/4 to 1/2 + ( $denominator, $number ) /= $number if ( $denominator % $number == 0 ); + ( $denominator, $number ) /= $denominator if ( $number % $denominator == 0 ); + + $farey{ $number/$denominator } = "$number/$denominator"; + } + } + + # bootstrap + return_next( '0/1' ); + + my %unique_counter; + for my $key ( sort keys( %farey ) ) { + # ensure only one item is printed out + $unique_counter{ $key }++; + next if $unique_counter{ $key } > 1; + next if $key == 1; # last term in the sequence + + return_next( $farey{ $key } ); + } + + # end term + return_next( '1/1' ); + return undef; +$CODE$ +LANGUAGE plperl; diff --git a/challenge-159/luca-ferrari/postgresql/ch-1.sql b/challenge-159/luca-ferrari/postgresql/ch-1.sql new file mode 100644 index 0000000000..da8824c0c2 --- /dev/null +++ b/challenge-159/luca-ferrari/postgresql/ch-1.sql @@ -0,0 +1 @@ +-- Perl Weekly Challenge 159 diff --git a/challenge-159/luca-ferrari/postgresql/ch-2.sql b/challenge-159/luca-ferrari/postgresql/ch-2.sql new file mode 100644 index 0000000000..da8824c0c2 --- /dev/null +++ b/challenge-159/luca-ferrari/postgresql/ch-2.sql @@ -0,0 +1 @@ +-- Perl Weekly Challenge 159 -- cgit From 8409efbb8a1f588f4bb1d0e4134cdc03b6c6d7f8 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 10:34:19 +0200 Subject: Task 1 done in plpgsql --- challenge-159/luca-ferrari/postgresql/ch-1.sql | 69 ++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) diff --git a/challenge-159/luca-ferrari/postgresql/ch-1.sql b/challenge-159/luca-ferrari/postgresql/ch-1.sql index da8824c0c2..1ebd6c5112 100644 --- a/challenge-159/luca-ferrari/postgresql/ch-1.sql +++ b/challenge-159/luca-ferrari/postgresql/ch-1.sql @@ -1 +1,70 @@ -- Perl Weekly Challenge 159 + + +CREATE SCHEMA IF NOT EXISTS pwc159; + + +CREATE OR REPLACE FUNCTION +pwc159.farey_not_unique( n int ) +RETURNS TABLE( f text, v numeric ) +AS $CODE$ +DECLARE + numerator int; + denominator int; + dd int; + nn int; +BEGIN + + -- bootstrap term + SELECT '0/1', 0 + INTO f, v; + + RETURN NEXT; + + + FOR denominator IN 2 .. n LOOP + FOR numerator IN 1 .. denominator LOOP + nn := numerator; + dd := denominator; + + IF dd % nn = 0 THEN + dd := dd / nn; + nn := 1; + END IF; + + IF nn % dd = 0 THEN + nn := nn / dd; + dd := 1; + END IF; + + IF nn / dd = 1 THEN + CONTINUE; + END IF; + + SELECT nn || '/' || dd, nn/dd::numeric + INTO f, v; + + RETURN NEXT; + + END LOOP; + END LOOP; + + -- end term + SELECT '1/1', 1 + INTO f, v; + + RETURN NEXT; + +RETURN; +END +$CODE$ +LANGUAGE plpgsql; + + +WITH farey AS ( + SELECT distinct( f ), v + FROM pwc159.farey_not_unique( 5 ) + ORDER BY v +) +SELECT f +FROM farey; -- cgit From fba5916d12a035d52cc82ced5536c6bcf531a22f Mon Sep 17 00:00:00 2001 From: Scimon Date: Mon, 4 Apr 2022 09:47:39 +0100 Subject: Challenge 1 --- challenge-159/simon-proctor/raku/ch-1.raku | 6 ++++++ 1 file changed, 6 insertions(+) create mode 100644 challenge-159/simon-proctor/raku/ch-1.raku diff --git a/challenge-159/simon-proctor/raku/ch-1.raku b/challenge-159/simon-proctor/raku/ch-1.raku new file mode 100644 index 0000000000..c94a0e7bb4 --- /dev/null +++ b/challenge-159/simon-proctor/raku/ch-1.raku @@ -0,0 +1,6 @@ +#!/usr/bin/env raku + +# Output the Farey Sequence of order n +sub MAIN ( Int \n ) { + ((0..n) X/ (1..n)).grep( * <= 1 ).unique.sort.map( *.nude ).map( { "@_[0]/@_[1]" } ).join(", ").say +} -- cgit From 13809215bbd6899853b500386805feffe995bbe4 Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 4 Apr 2022 09:49:42 +0100 Subject: Solutions for challenge #159 --- challenge-159/roger-bell-west/javascript/ch-1.js | 97 +++++++++ challenge-159/roger-bell-west/javascript/ch-2.js | 94 +++++++++ challenge-159/roger-bell-west/kotlin/ch-1.kt | 72 +++++++ challenge-159/roger-bell-west/kotlin/ch-2.kt | 94 +++++++++ challenge-159/roger-bell-west/lua/ch-1.lua | 104 +++++++++ challenge-159/roger-bell-west/lua/ch-2.lua | 97 +++++++++ challenge-159/roger-bell-west/perl/ch-1.pl | 56 +++++ challenge-159/roger-bell-west/perl/ch-2.pl | 78 +++++++ challenge-159/roger-bell-west/postscript/ch-1.ps | 256 +++++++++++++++++++++++ challenge-159/roger-bell-west/postscript/ch-2.ps | 217 +++++++++++++++++++ challenge-159/roger-bell-west/python/ch-1.py | 50 +++++ challenge-159/roger-bell-west/python/ch-2.py | 75 +++++++ challenge-159/roger-bell-west/raku/ch-1.p6 | 51 +++++ challenge-159/roger-bell-west/raku/ch-2.p6 | 74 +++++++ challenge-159/roger-bell-west/ruby/ch-1.rb | 52 +++++ challenge-159/roger-bell-west/ruby/ch-2.rb | 36 ++++ challenge-159/roger-bell-west/rust/ch-1.rs | 97 +++++++++ challenge-159/roger-bell-west/rust/ch-2.rs | 84 ++++++++ 18 files changed, 1684 insertions(+) create mode 100755 challenge-159/roger-bell-west/javascript/ch-1.js create mode 100755 challenge-159/roger-bell-west/javascript/ch-2.js create mode 100644 challenge-159/roger-bell-west/kotlin/ch-1.kt create mode 100644 challenge-159/roger-bell-west/kotlin/ch-2.kt create mode 100755 challenge-159/roger-bell-west/lua/ch-1.lua create mode 100755 challenge-159/roger-bell-west/lua/ch-2.lua create mode 100755 challenge-159/roger-bell-west/perl/ch-1.pl create mode 100755 challenge-159/roger-bell-west/perl/ch-2.pl create mode 100644 challenge-159/roger-bell-west/postscript/ch-1.ps create mode 100644 challenge-159/roger-bell-west/postscript/ch-2.ps create mode 100755 challenge-159/roger-bell-west/python/ch-1.py create mode 100755 challenge-159/roger-bell-west/python/ch-2.py create mode 100755 challenge-159/roger-bell-west/raku/ch-1.p6 create mode 100755 challenge-159/roger-bell-west/raku/ch-2.p6 create mode 100755 challenge-159/roger-bell-west/ruby/ch-1.rb create mode 100755 challenge-159/roger-bell-west/ruby/ch-2.rb create mode 100755 challenge-159/roger-bell-west/rust/ch-1.rs create mode 100755 challenge-159/roger-bell-west/rust/ch-2.rs diff --git a/challenge-159/roger-bell-west/javascript/ch-1.js b/challenge-159/roger-bell-west/javascript/ch-1.js new file mode 100755 index 0000000000..c18b03883d --- /dev/null +++ b/challenge-159/roger-bell-west/javascript/ch-1.js @@ -0,0 +1,97 @@ +#! /usr/bin/node + +function deepEqual(a,b) +{ + if( (typeof a == 'object' && a != null) && + (typeof b == 'object' && b != null) ) + { + var count = [0,0] + for( var key in a) count[0]++ + for( var key in b) count[1]++ + if( count[0]-count[1] != 0) {return false} + for( var key in a) + { + if(!(key in b) || !deepEqual(a[key],b[key])) {return false} + } + for( var key in b) + { + if(!(key in a) || !deepEqual(b[key],a[key])) {return false} + } + return true + } + else + { + return a === b + } +} + +function gcd (m0,n0) { + let m=m0 + let n=n0 + while (n != 0) { + [m,n]=[n,m % n] + } + return m +} + +function lcm (m,n) { + return m/gcd(m,n)*n +} + +function lcmseries(a0,b) { + let a=a0 + for (let i=a+1;i <= b;i++) { + a=lcm(a,i) + } + return a +} + +function farey (n) { + let l=lcmseries(2,n) + let d=new Map() + let s=[] + for (let i=1;i <= n;i++) { + let m=l/i + for (let j=0;j <= i;j++) { + let k=m*j + if (!d.has(k)) { + d.set(k,[j,i]) + s.push(k) + } + } + } + s.sort(function(a,b) { + return a-b; + }) + return s.map(i => d.get(i)) +} + +if (deepEqual(farey(5),[ + [0, 1], [1, 5], [1, 4], [1, 3], [2, 5], [1, 2], [3, 5], [2, 3], + [3, 4], [4, 5], [1, 1] +])) { + process.stdout.write("Pass") +} else { + process.stdout.write("FAIL") +} +process.stdout.write(" "); + +if (deepEqual(farey(7),[ + [0, 1], [1, 7], [1, 6], [1, 5], [1, 4], [2, 7], [1, 3], [2, 5], + [3, 7], [1, 2], [4, 7], [3, 5], [2, 3], [5, 7], [3, 4], [4, 5], + [5, 6], [6, 7], [1, 1] +])) { + process.stdout.write("Pass") +} else { + process.stdout.write("FAIL") +} +process.stdout.write(" "); + +if (deepEqual(farey(4),[ + [0, 1], [1, 4], [1, 3], [1, 2], [2, 3], [3, 4], [1, 1] +])) { + process.stdout.write("Pass") +} else { + process.stdout.write("FAIL") +} +process.stdout.write("\n"); diff --git a/challenge-159/roger-bell-west/javascript/ch-2.js b/challenge-159/roger-bell-west/javascript/ch-2.js new file mode 100755 index 0000000000..619b239213 --- /dev/null +++ b/challenge-159/roger-bell-west/javascript/ch-2.js @@ -0,0 +1,94 @@ +#! /usr/bin/node + +function genprimes(mx) { + let primesh=new Set([2,3]) + for (let i = 6; i <= mx; i += 6) { + for (let j = i-1; j <= i+1; j += 2) { + if (j <= mx) { + primesh.add(j); + } + } + } + let q=[2,3,5,7]; + let p=q.shift(); + let mr=Math.floor(Math.sqrt(mx)); + while (p <= mr) { + if (primesh.has(p)) { + let i=p*p + for (let i=p*p; i <= mx; i += p) { + primesh.delete(i); + } + } + if (q.length < 2) { + q.push(q[q.length-1]+4); + q.push(q[q.length-1]+2); + } + p=q.shift(); + } + let primes=[...primesh]; + primes.sort(function(a,b) { + return a-b; + }); + return primes; +} + +function primefactor (n) { + let f=new Map() + let m=n + for (let p of genprimes(Math.floor(Math.sqrt(n)))) { + while (m % p == 0) { + m=Math.floor(m/p) + if (f.has(p)) { + f.set(p,f.get(p)+1) + } else { + f.set(p,1) + } + if (m == 1) { + break + } + } + } + if (m > 1) { + if (f.has(m)) { + f.set(m,f.get(m)+1) + } else { + f.set(m,1) + } + } + return f +} + +function moebius (n) { + let z=0 + for (let v of primefactor(n).values()) { + if (v > 1) { + return 0 + } + z++ + } + if (z % 2 == 0) { + return 1 + } + return -1 +} + +if (moebius(5) == -1) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write(" "); + +if (moebius(10) == 1) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write(" "); + +if (moebius(20) == 0) { + process.stdout.write("Pass"); +} else { + process.stdout.write("FAIL"); +} +process.stdout.write("\n"); diff --git a/challenge-159/roger-bell-west/kotlin/ch-1.kt b/challenge-159/roger-bell-west/kotlin/ch-1.kt new file mode 100644 index 0000000000..362aa1c7f6 --- /dev/null +++ b/challenge-159/roger-bell-west/kotlin/ch-1.kt @@ -0,0 +1,72 @@ +import kotlin.math.* + +fun gcd(m0: Int,n0: Int): Int { + var m=m0 + var n=n0 + while (n != 0) { + val tmp=m % n + m = n + n = tmp + } + return m +} + +fun lcm(m: Int,n: Int): Int { + return m/gcd(m,n)*n +} + +fun lcmseries(s: List): Int { + return s.reduce { acc, x -> lcm(acc,x) } +} + +fun farey(n: Int): List> { + val l = lcmseries((2..n).toList()) + var d = mutableMapOf>() + var s = ArrayList() + for (i in 1..n) { + val m = l / i + for (j in 0..i) { + val k = m * j + if (!d.contains(k)) { + d[k]=Pair(j,i) + s.add(k) + } + } + } + s.sort() + return s.map {d[it]!!} +} + +fun main() { + if (farey(5) == listOf( + Pair(0, 1), Pair(1, 5), Pair(1, 4), Pair(1, 3), + Pair(2, 5), Pair(1, 2), Pair(3, 5), Pair(2, 3), + Pair(3, 4), Pair(4, 5), Pair(1, 1) + )) { + print("Pass") + } else { + print("FAIL") + } + print(" ") + if (farey(7) == listOf( + Pair(0, 1), Pair(1, 7), Pair(1, 6), Pair(1, 5), + Pair(1, 4), Pair(2, 7), Pair(1, 3), Pair(2, 5), + Pair(3, 7), Pair(1, 2), Pair(4, 7), Pair(3, 5), + Pair(2, 3), Pair(5, 7), Pair(3, 4), Pair(4, 5), + Pair(5, 6), Pair(6, 7), Pair(1, 1) + )) { + print("Pass") + } else { + print("FAIL") + } + print(" ") + if (farey(4) == listOf( + Pair(0, 1), Pair(1, 4), Pair(1, 3), Pair(1, 2), + Pair(2, 3), Pair(3, 4), Pair(1, 1) + )) { + print("Pass") + } else { + print("FAIL") + } + println("") +} diff --git a/challenge-159/roger-bell-west/kotlin/ch-2.kt b/challenge-159/roger-bell-west/kotlin/ch-2.kt new file mode 100644 index 0000000000..8cbe15e254 --- /dev/null +++ b/challenge-159/roger-bell-west/kotlin/ch-2.kt @@ -0,0 +1,94 @@ +import kotlin.math.* + +fun genprimes(mx: Int): ArrayList { + var primesh=mutableSetOf() + for (i in 2..3) { + primesh.add(i) + } + for (i in 6..mx+1 step 6) { + for (j in i-1..i+1 step 2) { + if (j <= mx) { + primesh.add(j) + } + } + } + var q=ArrayDeque(listOf(2,3,5,7)) + var p=q.removeFirst() + val mr=sqrt(mx.toDouble()).toInt() + while (p <= mr) { + if (primesh.contains(p)) { + for (i in p*p..mx step p) { + primesh.remove(i) + } + } + if (q.size < 2) { + q.add(q.last()+4) + q.add(q.last()+2) + } + p=q.removeFirst() + } + var primes=ArrayList(primesh.distinct()) + primes.sort() + return primes +} + +fun primefactor(n: Int): Map { + var f=mutableMapOf() + var m=n + for (p in genprimes(sqrt(m.toDouble()).toInt())) { + while (m % p == 0) { + m /= p + if (f.containsKey(p)) { + f[p] = f[p]!!+1 + } else { + f[p]=1 + } + } + if (m == 1) { + break + } + } + if (m > 1) { + if (f.containsKey(m)) { + f[m] = f[m]!!+1 + } else { + f[m]=1 + } + } + return f +} + +fun moebius(n: Int): Int { + var z: Int=0 + for (v in primefactor(n).values) { + if (v > 1) { + return 0 + } + z += 1 + } + if (z % 2 == 0) { + return 1 + } + return -1 +} + +fun main() { + if (moebius(5) == -1) { + print("Pass") + } else { + print("FAIL") + } + print(" ") + if (moebius(10) == 1) { + print("Pass") + } else { + print("FAIL") + } + print(" ") + if (moebius(20) == 0) { + print("Pass") + } else { + print("FAIL") + } + println("") +} diff --git a/challenge-159/roger-bell-west/lua/ch-1.lua b/challenge-159/roger-bell-west/lua/ch-1.lua new file mode 100755 index 0000000000..d10299f584 --- /dev/null +++ b/challenge-159/roger-bell-west/lua/ch-1.lua @@ -0,0 +1,104 @@ +#! /usr/bin/lua + +-- by Michael Anderson at +-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua +function recursive_compare(t1,t2) + -- Use usual comparison first. + if t1==t2 then return true end + -- We only support non-default behavior for tables + if (type(t1)~="table") then return false end + -- They better have the same metatables + local mt1 = getmetatable(t1) + local mt2 = getmetatable(t2) + if( not recursive_compare(mt1,mt2) ) then return false end + + -- Check each key-value pair + -- We have to do this both ways in case we miss some. + -- TODO: Could probably be smarter and not check those we've + -- already checked though! + for k1,v1 in pairs(t1) do + local v2 = t2[k1] + if( not recursive_compare(v1,v2) ) then return false end + end + for k2,v2 in pairs(t2) do + local v1 = t1[k2] + if( not recursive_compare(v1,v2) ) then return false end + end + + return true +end + +function gcd(m0,n0) + local m,n = m0,n0 + while n ~= 0 do + m,n = n,m % n + end + return m +end + +function lcm(m,n) + return m/gcd(m,n)*n +end + +function lcmseries(a,b) + local t=1 + for v = a,b do + t = lcm(t,v) + end + return t +end + +function farey(n) + local l=lcmseries(2,n) + local d={} + local s={} + for i = 1,n do + local m = l / i + for j = 0,i do + local k = m * j + if d[k] == nil then + d[k] = {j,i} + table.insert(s,k) + end + end + end + table.sort(s) + local out={} + for k,v in ipairs(s) do + table.insert(out,d[v]) + end + return out +end + +if recursive_compare(farey(5),{ + {0, 1}, {1, 5}, {1, 4}, {1, 3}, {2, 5}, + {1, 2}, {3, 5}, {2, 3}, {3, 4}, {4, 5}, + {1, 1} + }) then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if recursive_compare(farey(7),{ + {0, 1}, {1, 7}, {1, 6}, {1, 5}, {1, 4}, + {2, 7}, {1, 3}, {2, 5}, {3, 7}, {1, 2}, + {4, 7}, {3, 5}, {2, 3}, {5, 7}, {3, 4}, + {4, 5}, {5, 6}, {6, 7}, {1, 1} + }) then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if recursive_compare(farey(4),{ + {0, 1}, {1, 4}, {1, 3}, {1, 2}, {2, 3}, + {3, 4}, {1, 1} + }) then + io.write("Pass") +else + io.write("FAIL") +end +print("") diff --git a/challenge-159/roger-bell-west/lua/ch-2.lua b/challenge-159/roger-bell-west/lua/ch-2.lua new file mode 100755 index 0000000000..1e79067d53 --- /dev/null +++ b/challenge-159/roger-bell-west/lua/ch-2.lua @@ -0,0 +1,97 @@ +#! /usr/bin/lua + +function genprimes(mx) + local primesh = {} + for i = 2, 3 do + primesh[i] = true + end + for i = 6, mx, 6 do + for j = i-1, i+1, 2 do + if j <= mx then + primesh[j]=true + end + end + end + local q={2,3,5,7} + local p=table.remove(q,1) + local mr=math.floor(math.sqrt(mx)) + while p <= mr do + if primesh[p] ~= nil then + for i = p*p,mx,p do + primesh[i] = nil + end + end + if #q < 2 then + table.insert(q,q[#q]+4) + table.insert(q,q[#q]+2) + end + p=table.remove(q,1) + end + local primes = {} + for k,v in pairs(primesh) do + table.insert(primes,k) + end + table.sort(primes) + return primes +end + +function primefactor(n) + local f={} + local m=n + for k,p in pairs(genprimes(math.floor(math.sqrt(m)))) do + while m % p == 0 do + m=math.floor(m/p) + if f[p] == nil then + f[p]=1 + else + f[p] = f[p] + 1 + end + if m==1 then + break + end + end + end + if m>1 then + if f[m] == nil then + f[m]=1 + else + f[m] = f[m] + 1 + end + end + return f +end + +function moebius(n) + local z=0 + for k,v in pairs(primefactor(n)) do + if v > 1 then + return 0 + end + z = z + 1 + end + if z % 2 == 0 then + return 1 + end + return -1 +end + +if moebius(5) == -1 then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if moebius(10) == 1 then + io.write("Pass") +else + io.write("FAIL") +end +io.write(" ") + +if moebius(20) == 0 then + io.write("Pass") +else + io.write("FAIL") +end +print("") diff --git a/challenge-159/roger-bell-west/perl/ch-1.pl b/challenge-159/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..e99d1d11f3 --- /dev/null +++ b/challenge-159/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,56 @@ +#! /usr/bin/perl + +use strict; +use warnings; + +use Test::More tests => 3; +use List::Util qw(reduce); + +is_deeply(farey(5),[ + [0, 1], [1, 5], [1, 4], [1, 3], [2, 5], [1, 2], [3, 5], [2, 3], + [3, 4], [4, 5], [1, 1] + ],'example 1'); + +is_deeply(farey(7),[ + [0, 1], [1, 7], [1, 6], [1, 5], [1, 4], [2, 7], [1, 3], [2, 5], + [3, 7], [1, 2], [4, 7], [3, 5], [2, 3], [5, 7], [3, 4], [4, 5], + [5, 6], [6, 7], [1, 1] + ],'example 2'); + +is_deeply(farey(4),[ + [0, 1], [1, 4], [1, 3], [1, 2], [2, 3], [3, 4], [1, 1] + ],'example 3'); + +sub gcd { + my ($m,$n)=@_; + while ($n!=0) { + ($m,$n)=($n,$m % $n); + } + return $m; +} + +sub lcm { + my ($m,$n)=@_; + return $m/gcd($m,$n)*$n; +} + +sub lcmseries { + my $s=shift; + return reduce {lcm($a,$b)} @{$s}; +} + +sub farey { + my $n=shift; + my $l=lcmseries([2..$n]); + my %d; + foreach my $i (1..$n) { + my $m=$l/$i; + foreach my $j (0..$i) { + my $k=$m*$j; + unless (exists $d{$k}) { + $d{$k}=[$j,$i]; + } + } + } + return [map {$d{$_}} sort {$a <=> $b} keys %d]; +} diff --git a/challenge-159/roger-bell-west/perl/ch-2.pl b/challenge-159/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..4893c02740 --- /dev/null +++ b/challenge-159/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,78 @@ +#! /usr/bin/perl + +use strict; +use warnings; + +use Test::More tests => 3; + +is(moebius(5),-1,'example 1'); +is(moebius(10),1,'example 2'); +is(moebius(20),0,'example 3'); + +sub genprimes { + my $mx=shift; + my @primes; + { + my %primesh=map {$_ => 1} (2,3); + for (my $i=6;$i <= $mx+1; $i += 6) { + foreach my $j ($i-1,$i+1) { + if ($j <= $mx) { + $primesh{$j}=1; + } + } + } + my @q=(2,3,5,7); + my $p=shift @q; + my $mr=int(sqrt($mx)); + while ($p <= $mr) { + if ($primesh{$p}) { + my $i=$p*$p; + while ($i <= $mx) { + delete $primesh{$i}; + $i += $p; + } + } + if (scalar @q < 2) { + push @q,$q[-1]+4; + push @q,$q[-1]+2; + } + $p=shift @q; + } + @primes=sort {$a <=> $b} keys %primesh; + } + return \@primes; +} + +sub primefactor { + my $n=shift; + my %f; + my $m=$n; + foreach my $p (@{genprimes(int(sqrt($n)))}) { + while ($m % $p == 0) { + $f{$p}++; + $m=int($m/$p); + if ($m == 1) { + last; + } + } + } + if ($m > 1) { + $f{$m}++; + } + return \%f; +} + +sub moebius { + my $n=shift; + my $z=0; + foreach my $v (values %{primefactor($n)}) { + if ($v>1) { + return 0; + } + $z++; + } + if ($z % 2 == 0) { + return 1; + } + return -1; +} diff --git a/challenge-159/roger-bell-west/postscript/ch-1.ps b/challenge-159/roger-bell-west/postscript/ch-1.ps new file mode 100644 index 0000000000..30c9d167ab --- /dev/null +++ b/challenge-159/roger-bell-west/postscript/ch-1.ps @@ -0,0 +1,256 @@ +%!PS + +% begin library code + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cvs print + (/) print + test.count (...) cvs print + ( \() print + test.pass 100 mul test.count idiv (...) cvs print + (%\)) print + (\r\n) print + } if +} bind def + +/deepeq { + 2 dict begin + /a exch def + /b exch def + a type b type eq { + a type /dicttype eq { + a length b length eq { + << + a { + pop + true + } forall + b { + pop + true + } forall + >> + true exch + { + pop + dup a exch known { + dup b exch known { + dup a exch get exch b exch get deepeq not { + pop false + } if + } { + false + } ifelse + } { + false + } ifelse + } forall + } { + false + } ifelse + } { + a type dup /arraytype eq exch /stringtype eq or { + a length b length eq { + true + 0 1 a length 1 sub { + dup a exch get exch b exch get deepeq not { + pop false + exit + } if + } for + } { + false + } ifelse + } { + a b eq + } ifelse + } ifelse + } { + false + } ifelse + end +} bind def + +/quicksort { % [ a c b ] -> [ a b c ] + 1 dict begin + /arr exch def + 0 arr length 1 sub quicksort.main + arr + end +} bind def + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/reduce { % array proc -> value + 2 dict begin + /p exch def + /a exch def + a 0 get + 1 1 a length 1 sub { + a exch get + p + } for + end +} bind def + + +/apush { % [a b] c -> [a b c] + exch + [ exch aload length 2 add -1 roll ] +} bind def + +/map { % array proc -> array + 2 dict begin + /p exch def + [ exch + { + p + } forall + ] +} bind def + +/keys { % dict -> array of dict keys + [ exch + { + pop + } forall + ] +} bind def + +% end library code + +/gcd { + { + dup + 3 1 roll + mod + dup 0 eq { + pop exit + } if + } loop +} bind def + +/lcm { + dup 3 -1 roll + dup 4 -1 roll + gcd idiv mul +} bind def + +/lcmseries { + { lcm } reduce +} bind def + +/farey { + 7 dict begin + /n exch def + /l [ 2 1 n { } for ] lcmseries def + /d n dup mul dict def + 1 1 n { + /i exch def + /m l i idiv def + 0 1 i { + /j exch def + /k m j mul def + d k known not { + d k [ j i ] put + } if + } for + } for + d keys quicksort { d exch get } map + end +} bind def + +(farey) test.start + +5 farey +[ [0 1] [1 5] [1 4] [1 3] [2 5] [1 2] [3 5] [2 3] [3 4] [4 5] [1 1] ] +deepeq test + +7 farey +[ [0 1] [1 7] [1 6] [1 5] [1 4] [2 7] [1 3] [2 5] [3 7] [1 2] [4 7] + [3 5] [2 3] [5 7] [3 4] [4 5] [5 6] [6 7] [1 1] ] +deepeq test + +4 farey +[ [0 1] [1 4] [1 3] [1 2] [2 3] [3 4] [1 1] ] +deepeq test + +test.end diff --git a/challenge-159/roger-bell-west/postscript/ch-2.ps b/challenge-159/roger-bell-west/postscript/ch-2.ps new file mode 100644 index 0000000000..bfc28ad691 --- /dev/null +++ b/challenge-159/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,217 @@ +%!PS + +% begin library code + +/test { + /test.count test.count 1 add def + { + /test.pass test.pass 1 add def + } { + ( ) print + test.count (....) cvs print + (-fail) print + } ifelse +} bind def + +/test.start { + print (:) print + /test.pass 0 def + /test.count 0 def +} bind def + +/test.end { + ( ) print + test.count 0 gt { + (Passed ) print + test.pass (...) cvs print + (/) print + test.count (...) cvs print + ( \() print + test.pass 100 mul test.count idiv (...) cvs print + (%\)) print + (\r\n) print + } if +} bind def + +/quicksort { % [ a c b ] -> [ a b c ] + 1 dict begin + /arr exch def + 0 arr length 1 sub quicksort.main + arr + end +} bind def + +/quicksort.main { % lo hi -> (null) + 3 dict begin + /hi exch def + /lo exch def + /xit false def + lo 0 lt { + /xit true def + } if + hi 0 lt { + /xit true def + } if + lo hi ge { + /xit true def + } if + xit not { + /p quicksort.partition def + lo p quicksort.main + p 1 add hi quicksort.main + } if + end +} bind def + +/quicksort.partition { + 3 dict begin + /pivot arr hi lo add 2 idiv get def + /i lo 1 sub def + /j hi 1 add def + { + { + /i i 1 add def + arr i get pivot ge { + exit + } if + } loop + { + /j j 1 sub def + arr j get pivot le { + exit + } if + } loop + i j ge { + j + exit + } if + i j quicksort.swap + } loop + end +} bind def + +/quicksort.swap { + 2 dict begin + /bi exch def + /ai exch def + arr ai get + arr bi get + arr exch ai exch put + arr exch bi exch put + end +} bind def + +/apush { % [a b] c -> [a b c] + exch + [ exch aload length 2 add -1 roll ] +} bind def + +/values { % dict -> array of dict values + [ exch + { + exch pop + } forall + ] +} bind def + +% end library code + +/genprimes { + /mx exch def + /primesh mx dict def + 2 1 3 { + primesh exch true put + } for + 6 6 mx 1 add { + dup 1 sub exch 1 add 2 exch { + dup mx le { + primesh exch true put + } { + pop + } ifelse + } for + } for + /q [ 3 5 7 ] def + /qi 0 def + /p 2 def + /mr mx sqrt cvi def + { + p mr le not { + exit + } if + primesh p known { + p dup mul p mx { + primesh exch undef + } for + } if + q length qi sub 2 le { + /q q q q length 1 sub get 4 add apush def + /q q q q length 1 sub get 2 add apush def + } if + /p q qi get def + /qi qi 1 add def + } loop + [ primesh { pop } forall ] quicksort +} bind def + +/primefactor { + 4 dict begin + /n exch def + /f 1 dict def + /m n def + n sqrt cvi genprimes { + /p exch def + { + m p mod 0 eq { + f p known { + f p f p get 1 add put + } { + f p 1 put + } ifelse + /m m p idiv def + } { + exit + } ifelse + } loop + m 1 eq { + exit + } + } forall + m 1 gt { + f m known { + f m f m get 1 add put + } { + f m 1 put + } ifelse + } if + f + end +} bind def + +/moebius { + 1 dict begin + /z 0 def + primefactor values { + 1 gt { + /z 0 def + exit + } if + /z z 1 add def + } forall + z 0 eq { + 0 + } { + z 2 mod 0 eq { + 1 + } { + -1 + } ifelse + } ifelse + end +} bind def + +(moebius) test.start +5 moebius -1 eq test +10 moebius 1 eq test +20 moebius 0 eq test +test.end diff --git a/challenge-159/roger-bell-west/python/ch-1.py b/challenge-159/roger-bell-west/python/ch-1.py new file mode 100755 index 0000000000..d6e05acf97 --- /dev/null +++ b/challenge-159/roger-bell-west/python/ch-1.py @@ -0,0 +1,50 @@ +#! /usr/bin/python3 + +import unittest + +from math import gcd +from functools import reduce + +def lcm(m,n): + return m//gcd(m,n)*n + +def lcmseries(s): + return reduce(lcm, s) + +def farey(n): + l=lcmseries(range(2,n+1)) + d=dict() + s=[] + for i in range(1,n+1): + m=l // i + for j in range(0,i+1): + k=m*j + if not k in d: + d[k]=[j,i] + s.append(k) + s.sort() + return [d[i] for i in s] + +class TestFarey(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(farey(5), + [[0,1], [1,5], [1,4], [1,3], [2,5], [1,2], + [3,5], [2,3], [3,4], [4,5], [1,1]], + 'example 1') + + def test_ex2(self): + self.assertEqual(farey(7), + [[0,1], [1,7], [1,6], [1,5], [1,4], [2,7], + [1,3], [2,5], [3,7], [1,2], [4,7], [3,5], + [2,3], [5,7], [3,4], [4,5], [5,6], [6,7], + [1,1]], + 'example 2') + + def test_ex3(self): + self.assertEqual(farey(4), + [[0,1], [1,4], [1,3], [1,2], [2,3], [3,4], + [1,1]], + 'example 3') + +unittest.main() diff --git a/challenge-159/roger-bell-west/python/ch-2.py b/challenge-159/roger-bell-west/python/ch-2.py new file mode 100755 index 0000000000..125eed5e55 --- /dev/null +++ b/challenge-159/roger-bell-west/python/ch-2.py @@ -0,0 +1,75 @@ +#! /usr/bin/python3 + +import unittest + +from math import sqrt,floor,gcd +from collections import deque + +def genprimes(mx): + primesh=set(range(2,4)) + for i in range(6,mx+2,6): + for j in range(i-1,i+2,2): + if j <= mx: + primesh.add(j) + q=deque([2,3,5,7]) + p=q.popleft() + mr=floor(sqrt(mx)) + while p <= mr: + if p in primesh: + for i in range(p*p,mx+1,p): + primesh.discard(i) + if len(q) < 2: + q.append(q[-1]+4) + q.append(q[-1]+2) + p=q.popleft() + primes=list(primesh) + primes.sort() + return primes + +def primefactor(n): + f=dict() + m=n + for p in genprimes(floor(sqrt(n))): + while (m % p == 0): + m //= p + if p in f: + f[p] += 1 + else: + f[p] = 1 + if m==1: + break + if m > 1: + if m in f: + f[m] += 1 + else: + f[m] = 1 + return f + +def moebius(n): + z=0 + for k,v in primefactor(n).items(): + if v > 1: + return 0 + z += 1 + if z % 2 == 0: + return 1 + return -1 + +class TestMoebius(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(moebius(5), + -1, + 'example 1') + + def test_ex2(self): + self.assertEqual(moebius(10), + 1, + 'example 2') + + def test_ex3(self): + self.assertEqual(moebius(20), + 0, + 'example 3') + +unittest.main() diff --git a/challenge-159/roger-bell-west/raku/ch-1.p6 b/challenge-159/roger-bell-west/raku/ch-1.p6 new file mode 100755 index 0000000000..0c3dee4698 --- /dev/null +++ b/challenge-159/roger-bell-west/raku/ch-1.p6 @@ -0,0 +1,51 @@ +#! /usr/bin/perl6 + +use Test; + +plan 3; + +is-deeply(farey(5),( + 0 => 1, 1 => 5, 1 => 4, 1 => 3, 2 => 5, 1 => 2, 3 => 5, + 2 => 3, 3 => 4, 4 => 5, 1 => 1 + ),'example 1'); + +is-deeply(farey(7),( + 0 => 1, 1 => 7, 1 => 6, 1 => 5, 1 => 4, 2 => 7, 1 => 3, + 2 => 5, 3 => 7, 1 => 2, 4 => 7, 3 => 5, 2 => 3, 5 => 7, + 3 => 4, 4 => 5, 5 => 6, 6 => 7, 1 => 1 + ),'example 2'); + +is-deeply(farey(4),( + 0 => 1, 1 => 4, 1 => 3, 1 => 2, 2 => 3, 3 => 4, 1 => 1 + ),'example 3'); + +sub gcd($m0,$n0) { + my ($m,$n)=($m0,$n0); + while ($n != 0) { + ($m,$n)=($n,$m % $n); + } + return $m; +} + +sub lcm($m,$n) { + return $m/gcd($m,$n)*$n; +} + +sub lcmseries(@s) { + return floor(@s.reduce(&lcm)); +} + +sub farey($n) { + my $l=lcmseries([2..$n]); + my %d; + for (1..$n) -> $i { + my $m = $l div $i; + for (0..$i) -> $j { + my $k = $m * $j; + unless (%d{$k}:exists) { + %d{$k}=Pair.new($j,$i); + } + } + } + return map {%d{$_}}, sort { $^a <=> $^b }, %d.keys; +} diff --git a/challenge-159/roger-bell-west/raku/ch-2.p6 b/challenge-159/roger-bell-west/raku/ch-2.p6 new file mode 100755 index 0000000000..79211760a0 --- /dev/null +++ b/challenge-159/roger-bell-west/raku/ch-2.p6 @@ -0,0 +1,74 @@ +#! /usr/bin/perl6 + +use Test; + +plan 3; + +is(moebius(5),-1,'example 1'); +is(moebius(10),1,'example 2'); +is(moebius(20),0,'example 3'); + +sub genprimes($mx) { + my @primes; + { + my $primesh=(2,3).SetHash; + loop (my $i=6;$i <= $mx+1; $i += 6) { + for ($i-1,$i+1) -> $j { + if ($j <= $mx) { + $primesh{$j}=True; + } + } + } + my $p=2; + my @q=[2,3,5,7]; + my $mr=floor(sqrt($mx)); + while ($p <= $mr) { + if ($primesh{$p}:exists) { + my $i=$p*$p; + while ($i <= $mx) { + $primesh{$i}:delete; + $i += $p; + } + } + if (@q.elems < 2) { + @q.push(@q[*-1]+4); + @q.push(@q[*-1]+2); + } + $p=@q.shift; + } + @primes=$primesh.keys.sort; + } + return @primes; +} + +sub primefactor($n) { + my %f; + my $m=$n; + for genprimes(floor(sqrt($n))) -> $p { + while ($m % $p == 0) { + %f{$p}++; + $m=floor($m/$p); + } + if ($m == 1) { + last; + } + } + if ($m > 1) { + %f{$m}++; + } + return %f; +} + +sub moebius($n) { + my $z=0; + for primefactor($n).values -> $v { + if ($v > 1) { + return 0; + } + $z++; + } + if ($z % 2 == 0) { + return 1; + } + return -1; +} diff --git a/challenge-159/roger-bell-west/ruby/ch-1.rb b/challenge-159/roger-bell-west/ruby/ch-1.rb new file mode 100755 index 0000000000..593a5ac426 --- /dev/null +++ b/challenge-159/roger-bell-west/ruby/ch-1.rb @@ -0,0 +1,52 @@ +#! /usr/bin/ruby + +require 'test/unit' + +require 'set' +require 'prime' + +def lcmseries(s) + return s.inject {|a, b| a.lcm(b)} +end + +def farey(n) + l=lcmseries(2.upto(n)) + d={} + s=[] + 1.upto(n) do |i| + m = l / i + 0.upto(i) do |j| + k = m * j + if !d.has_key?(k) then + d[k]=[j,i] + s.push(k) + end + end + end + s.sort! + return s.map{|i| d[i]} +end + +class TestFarey < Test::Unit::TestCase + + def test_ex1 + assert_equal([[0, 1], [1, 5], [1, 4], [1, 3], [2, 5], [1, 2], + [3, 5], [2, 3], [3, 4], [4, 5], [1, 1]], + farey(5)) + end + + def test_ex2 + assert_equal([[0, 1], [1, 7], [1, 6], [1, 5], [1, 4], [2, 7], + [1, 3], [2, 5], [3, 7], [1, 2], [4, 7], [3, 5], + [2, 3], [5, 7], [3, 4], [4, 5], [5, 6], [6, 7], + [1, 1]], + farey(7)) + end + + def test_ex3 + assert_equal([[0, 1], [1, 4], [1, 3], [1, 2], [2, 3], [3, 4], + [1, 1]], + farey(4)) + end + +end diff --git a/challenge-159/roger-bell-west/ruby/ch-2.rb b/challenge-159/roger-bell-west/ruby/ch-2.rb new file mode 100755 index 0000000000..4d59457cba --- /dev/null +++ b/challenge-159/roger-bell-west/ruby/ch-2.rb @@ -0,0 +1,36 @@ +#! /usr/bin/ruby + +require 'test/unit' + +require 'set' +require 'prime' + +def moebius(n) + z=0 + for vv in n.prime_division do + if vv[1] > 1 then + return 0 + end + z += 1 + end + if z % 2 == 0 then + return 1 + end + return -1 +end + +class TestMoebius < Test::Unit::TestCase + + def test_ex1 + assert_equal(-1,moebius(5)) + end + + def test_ex2 + assert_equal(1,moebius(10)) + end + + def test_ex3 + assert_equal(0,moebius(20)) + end + +end diff --git a/challenge-159/roger-bell-west/rust/ch-1.rs b/challenge-159/roger-bell-west/rust/ch-1.rs new file mode 100755 index 0000000000..aee5bc331d --- /dev/null +++ b/challenge-159/roger-bell-west/rust/ch-1.rs @@ -0,0 +1,97 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit + +use std::collections::HashMap; + +#[test] +fn test_ex1() { + assert_eq!( + farey(5), + vec![ + [0, 1], + [1, 5], + [1, 4], + [1, 3], + [2, 5], + [1, 2], + [3, 5], + [2, 3], + [3, 4], + [4, 5], + [1, 1] + ] + ); +} + +#[test] +fn test_ex2() { + assert_eq!( + farey(7), + vec![ + [0, 1], + [1, 7], + [1, 6], + [1, 5], + [1, 4], + [2, 7], + [1, 3], + [2, 5], + [3, 7], + [1, 2], + [4, 7], + [3, 5], + [2, 3], + [5, 7], + [3, 4], + [4, 5], + [5, 6], + [6, 7], + [1, 1] + ] + ); +} + +#[test] +fn test_ex3() { + assert_eq!( + farey(4), + vec![[0, 1], [1, 4], [1, 3], [1, 2], [2, 3], [3, 4], [1, 1]] + ); +} + +fn gcd(m0: usize, n0: usize) -> usize { + let mut m = m0; + let mut n = n0; + while n != 0 { + let t = n; + n = m % n; + m = t; + } + m +} + +fn lcm(m: usize, n: usize) -> usize { + m / gcd(m, n) * n +} + +fn lcmseries(s: Vec) -> usize { + s.iter().fold(1, |acc, x| lcm(acc, *x)) +} + +fn farey(n: usize) -> Vec<[usize; 2]> { + let l = lcmseries((2..=n).collect::>()); + let mut d: HashMap = HashMap::new(); + let mut s = Vec::new(); + for i in 1..=n { + let m = l / i; + for j in 0..=i { + let k = m * j; + if !d.contains_key(&k) { + d.insert(k, [j, i]); + s.push(k); + } + } + } + s.sort(); + return s.iter().map(|i| d[i]).collect::>(); +} diff --git a/challenge-159/roger-bell-west/rust/ch-2.rs b/challenge-159/roger-bell-west/rust/ch-2.rs new file mode 100755 index 0000000000..106b67293d --- /dev/null +++ b/challenge-159/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,84 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x --nocapture; rm -f ${0}x ; exit + +use std::collections::{HashMap, HashSet, VecDeque}; +use std::iter::FromIterator; + +#[test] +fn test_ex1() { + assert_eq!(moebius(5), -1); +} + +#[test] +fn test_ex2() { + assert_eq!(moebius(10), 1); +} + +#[test] +fn test_ex3() { + assert_eq!(moebius(20), 0); +} + +fn genprimes(mx: usize) -> Vec { + let mut primesh: HashSet = HashSet::from_iter(2..=3); + for i in (6..=mx).step_by(6) { + for j in [i - 1, i + 1] { + if j < mx { + primesh.insert(j); + } + } + } + let mut q = VecDeque::from([2, 3, 5, 7]); + let mut p = q.pop_front().unwrap(); + let mr = (mx as f64).sqrt() as usize; + while p <= mr { + if primesh.contains(&p) { + for i in (p * p..=mx).step_by(p as usize) { + primesh.remove(&i); + } + } + if q.len() < 2 { + let t = q[0] + 4; + q.push_back(t); + q.push_back(t + 2); + } + p = q.pop_front().unwrap(); + } + let mut primes = primesh.iter().map(|i| *i).collect::>(); + primes.sort(); + primes +} + +fn primefactor(n: usize) -> HashMap { + let mut f: HashMap = HashMap::new(); + let mut m = n; + for p in genprimes((n as f64).sqrt() as usize).iter() { + while m % p == 0 { + m /= p; + let en = f.entry(*p).or_insert(0); + *en += 1; + } + if m == 1 { + break; + } + } + if m > 1 { + let en = f.entry(m).or_insert(0); + *en += 1; + } + f +} + +fn moebius(n: usize) -> isize { + let mut z=0; + for v in primefactor(n).values() { + if *v > 1 { + return 0; + } + z += 1; + } + if z % 2 == 0 { + return 1; + } + -1 +} -- cgit From afb541c10466df9d9ca45c17f3056fd11a016e47 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 10:53:44 +0200 Subject: Task 2 plperl --- challenge-159/luca-ferrari/postgresql/ch-2.plperl | 57 +++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 challenge-159/luca-ferrari/postgresql/ch-2.plperl diff --git a/challenge-159/luca-ferrari/postgresql/ch-2.plperl b/challenge-159/luca-ferrari/postgresql/ch-2.plperl new file mode 100644 index 0000000000..8dce608e5a --- /dev/null +++ b/challenge-159/luca-ferrari/postgresql/ch-2.plperl @@ -0,0 +1,57 @@ +CREATE SCHEMA IF NOT EXISTS pwc159; + +/** +testdb=> select pwc159.mobius( 5 ); + mobius +-------- + -1 +(1 row) + +*/ +CREATE OR REPLACE FUNCTION +pwc159.mobius( int ) +RETURNS int +AS $CODE$ + + my ( $n ) = @_; + + # a routine to compute the prime + # factors of the given number + my $prime_factors = sub { + my ( $number ) = @_; + my %factors; + + my $factor = 2; + while ( $number > 1 && $factor <= $number ) { + if ( $number % $factor == 0 ) { + $factors{ $factor }++; + $number /= $factor; + } + else { + $factor++; + } + } + + return %factors; + }; + + + my %prime_factors = $prime_factors->( $n ); + + # to get the unique prime factors I have to "count" + # them only once per key + my @unique_prime_factors; + my $occurrencies_prime_factors = 0; + for ( keys %prime_factors ) { + push @unique_prime_factors, $_; + $occurrencies_prime_factors += $prime_factors{ $_ }; + } + + + return 0 if @unique_prime_factors != $occurrencies_prime_factors; + return 1 if @unique_prime_factors % 2 == 0; + return -1; + + +$CODE$ +LANGUAGE plperl; -- cgit From d6c45c1e8fbd72ec613baff00a8214a270f3f6cb Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 11:06:28 +0200 Subject: Task 2 done in plpgsql --- challenge-159/luca-ferrari/postgresql/ch-2.sql | 42 ++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/challenge-159/luca-ferrari/postgresql/ch-2.sql b/challenge-159/luca-ferrari/postgresql/ch-2.sql index da8824c0c2..d165df2fed 100644 --- a/challenge-159/luca-ferrari/postgresql/ch-2.sql +++ b/challenge-159/luca-ferrari/postgresql/ch-2.sql @@ -1 +1,43 @@ -- Perl Weekly Challenge 159 + +CREATE SCHEMA IF NOT EXISTS pwc159; + +CREATE OR REPLACE FUNCTION +pwc159.prime_factors( n int ) +RETURNS SETOF int +AS $CODE$ +DECLARE + factor int; +BEGIN + factor := 2; + + WHILE ( factor <= n AND n > 1 ) LOOP + IF n % factor = 0 THEN + n := n / factor; + RETURN NEXT factor; + ELSE + factor := factor + 1; + END IF; + END LOOP; + + RETURN; +END +$CODE$ +LANGUAGE plpgsql; + + +\set n 5 + +WITH count_prime_factors( c, cc ) AS +( + SELECT count( distinct pf ), count( pf ) + FROM pwc159.prime_factors( :n ) pf +) +SELECT :n AS number, + CASE + WHEN c - cc <> 0 THEN 0 + WHEN c % 2 = 0 THEN 1 + ELSE -1 + END + +FROM count_prime_factors; -- cgit From 593f633c0d938cf962a5ffd4c99e4ed08acb9b99 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 4 Apr 2022 11:51:35 +0200 Subject: Blog references --- challenge-159/luca-ferrari/blog-1.txt | 1 + challenge-159/luca-ferrari/blog-2.txt | 1 + challenge-159/luca-ferrari/blog-3.txt | 1 + challenge-159/luca-ferrari/blog-4.txt | 1 + challenge-159/luca-ferrari/blog-5.txt | 1 + challenge-159/luca-ferrari/blog-6.txt | 1 + 6 files changed, 6 insertions(+) create mode 100644 challenge-159/luca-ferrari/blog-1.txt create mode 100644 challenge-159/luca-ferrari/blog-2.txt create mode 100644 challenge-159/luca-ferrari/blog-3.txt create mode 100644 challenge-159/luca-ferrari/blog-4.txt create mode 100644 challenge-159/luca-ferrari/blog-5.txt create mode 100644 challenge-159/luca-ferrari/blog-6.txt diff --git a/challenge-159/luca-ferrari/blog-1.txt b/challenge-159/luca-ferrari/blog-1.txt new file mode 100644 index 0000000000..adc4af027c --- /dev/null +++ b/challenge-159/luca-ferrari/blog-1.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2022/04/04/PerlWeeklyChallenge159.html#task1 diff --git a/challenge-159/luca-ferrari/blog-2.txt b/challenge-159/luca-ferrari/blog-2.txt new file mode 100644 index 0000000000..970839190a --- /dev/null +++ b/challenge-159/luca-ferrari/blog-2.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2022/04/04/PerlWeeklyChallenge159.html#task2 diff --git a/challenge-159/