From b842af30d05d67f5d492653a8c80a935b313a301 Mon Sep 17 00:00:00 2001 From: James Smith Date: Mon, 20 Jun 2022 06:03:38 +0100 Subject: Update README.md --- challenge-169/james-smith/README.md | 1 + 1 file changed, 1 insertion(+) diff --git a/challenge-169/james-smith/README.md b/challenge-169/james-smith/README.md index 5c699ca4f3..9593e23f10 100644 --- a/challenge-169/james-smith/README.md +++ b/challenge-169/james-smith/README.md @@ -236,6 +236,7 @@ Some examples for larger values of `n` are: | 300,000 | 69,976,609,587 | 33.509092 | | 325,000 | 81,981,196,443 | 33.551032 | | 350,000 | 94,917,245,000 | 23.54.43572 | +| 375,000 | 108,802,180,800 | 26.35.52.234 | And these are the first numbers with `n` digits... -- cgit From a818c40db77724861b0d645d0b205ba993c58a87 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 20 Jun 2022 07:30:26 +0100 Subject: soln v1 for 170 --- challenge-170/james-smith/README.md | 291 +++++---------------------------- challenge-170/james-smith/blog.txt | 2 + challenge-170/james-smith/perl/ch-1.pl | 20 +++ challenge-170/james-smith/perl/ch-2.pl | 22 +++ 4 files changed, 83 insertions(+), 252 deletions(-) create mode 100644 challenge-170/james-smith/blog.txt create mode 100644 challenge-170/james-smith/perl/ch-1.pl create mode 100644 challenge-170/james-smith/perl/ch-2.pl diff --git a/challenge-170/james-smith/README.md b/challenge-170/james-smith/README.md index 5c699ca4f3..c5bec6d217 100644 --- a/challenge-170/james-smith/README.md +++ b/challenge-170/james-smith/README.md @@ -1,7 +1,7 @@ -[< Previous 168](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-168/james-smith) | -[Next 170 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/james-smith) +[< Previous 169](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-169/james-smith) | +[Next 171 >](https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-171/james-smith) -# The Weekly Challenge 169 +# The Weekly Challenge 170 You can find more information about this weeks, and previous weeks challenges at: @@ -13,279 +13,66 @@ 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-169/james-smith +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/james-smith -# Challenge 1 - Brilliant numbers +# Challenge 1 - Primordial Numbers -***Write a script to generate first 20 Brilliant Numbers. Brilliant numbers are numbers with two prime factors of the same length. The number should have exactly two prime factors, i.e. it’s the product of two primes of the same length.*** +***Write a script to generate first 10 Primorial Numbers - like factorials but multiply by succesive primes*** ## Solution -Again our favoured prime package `Math::Prime::Util` has the method we need `factor` which returns a list of prime factors, and its fast - especially for the magnitude of numbers we are looking at. - -We loop through all numbers, checking to see if (a) the number has exactly 2 prime factors and they are the same length. - -For flexibility we define the max count `$MAX` as the command-line argument if one is supplied (or 100 if not). - ```perl -for( my( $MAX, $c, $n, @f ) = ($ARGV[0] // 1e2, 0); $c<$MAX; ) { - printf "%8d: %10d = %5d x %d\n", ++$c, $n, @f if 2 == ( @f = factor ++$n ) && length $f[0] == length $f[1] -} -``` +my(@x)= my $p = 1; -This logic is wrapped up in the single `if`. As we check the number of factors, we store these in an array, so that we can check the 2nd condition. +push @x, $x[-1] * ($p = next_prime $p) for 1..100; -The output in each row is the brilliant number and the two primes which are it's factors. +say sprintf '%300s', th($_) for @x; -**Note:** Both in this and the next challenge we utilise a classic "c-style" `for`-loop. This construct allows us to combine the variable initialized (and declaration), the end condition, and the increment of the number into a single statement. We code rewrite this a postfix `for(each)` in this case, but would need an declaration/initialisation statement for `$n` and `@f` anyway. Also in challenge 2 it isn't possible to use a postfix for `for` as this doesn't allow us to use the `next` trick to short cut the `grep` inside the `gcd` call. +sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } +``` -**Note:** to make the code easier to read we use a *Yoda* condition, where we reverse the value and the code evaluation - so instead if say `$a == 2` we say `2 == $a`. +# Challenge 2 - Kronecker Product -**Moan:** Why is there no `sayf` function similar to `printf` - using `say sprintf` is just "messy" each time... +***Write a script to implement Kronecker Product on the given 2 matrices. e.g.*** -The first 50 brilliant numbers are: +## Example +Hard to describe - but here is an example.... see https://en.wikipedia.org/wiki/Kronecker_product ``` - 1: 4 = 2 x 2 - 2: 6 = 2 x 3 - 3: 9 = 3 x 3 - 4: 10 = 2 x 5 - 5: 14 = 2 x 7 - 6: 15 = 3 x 5 - 7: 21 = 3 x 7 - 8: 25 = 5 x 5 - 9: 35 = 5 x 7 - 10: 49 = 7 x 7 - 11: 121 = 11 x 11 - 12: 143 = 11 x 13 - 13: 169 = 13 x 13 - 14: 187 = 11 x 17 - 15: 209 = 11 x 19 - 16: 221 = 13 x 17 - 17: 247 = 13 x 19 - 18: 253 = 11 x 23 - 19: 289 = 17 x 17 - 20: 299 = 13 x 23 - 21: 319 = 11 x 29 - 22: 323 = 17 x 19 - 23: 341 = 11 x 31 - 24: 361 = 19 x 19 - 25: 377 = 13 x 29 - 26: 391 = 17 x 23 - 27: 403 = 13 x 31 - 28: 407 = 11 x 37 - 29: 437 = 19 x 23 - 30: 451 = 11 x 41 - 31: 473 = 11 x 43 - 32: 481 = 13 x 37 - 33: 493 = 17 x 29 - 34: 517 = 11 x 47 - 35: 527 = 17 x 31 - 36: 529 = 23 x 23 - 37: 533 = 13 x 41 - 38: 551 = 19 x 29 - 39: 559 = 13 x 43 - 40: 583 = 11 x 53 - 41: 589 = 19 x 31 - 42: 611 = 13 x 47 - 43: 629 = 17 x 37 - 44: 649 = 11 x 59 - 45: 667 = 23 x 29 - 46: 671 = 11 x 61 - 47: 689 = 13 x 53 - 48: 697 = 17 x 41 - 49: 703 = 19 x 37 - 50: 713 = 23 x 31 -``` -### Removing pretty print - -If we remove the pretty print this reduces to: - -```perl -for( my( $c, $n, @f ) = 100; $c; ) { - $c--, say $n if 2 == ( @f = factor ++$n ) && length $f[0] == length $f[1] -} +A = [ 1 2 ] + [ 3 4 ] + +B = [ 5 6 ] + [ 7 8 ] + +A x B = [ 1 x [ 5 6 ] 2 x [ 5 6 ] ] + [ [ 7 8 ] [ 7 8 ] ] + [ 3 x [ 5 6 ] 4 x [ 5 6 ] ] + [ [ 7 8 ] [ 7 8 ] ] + + = [ 1x5 1x6 2x5 2x6 ] + [ 1x7 1x8 2x7 2x8 ] + [ 3x5 3x6 4x5 4x6 ] + [ 3x7 3x8 4x7 4x8 ] + + = [ 5 6 10 12 ] + [ 7 8 14 16 ] + [ 15 18 20 24 ] + [ 21 24 28 32 ] ``` -**Notes:** As well as moving the pretty print (and the $MAX for simplicity) we do three things: - * We start $c at the number of entries we want, and decrement the counter each time - the end condition is then simple `$c == 0` or as we write a "continue" condition that is just `$c`. - * As above we remove the increment from the `for()` to the entry - in this case ++$n. As we don't initialize `$n`, we have to "pre-increment" so that `$n` is defined when factor is called. - * Finally to display the brilliant number AND decrement `$c`, we separate the two commands with a `,` as `$c--, say $n`. - -# Challenge 2 - Achilles Number - -***Write a script to generate first 20 Achilles Numbers. An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.*** - -*A positive integer `n` is a powerful number if, for every prime factor `p` of `n`, `p^2` is also a divisor.* - -*A number is a perfect power if it has any integer ropts ( square, cube, ... ) i.e. can be written in the form `n^m`.* - -*An imperfect number is one which can't be - now this means that if we make a prime factorization of the form `p1^k1 . p2^k2 . p3^k3 ....` then the greatest common divisor is 1. As if greater than 1 then we could write this as `( p1^k1/gcd . p2^k2/gcd . p3^k3/gcd . ... )^gcd` and so would be perfect. - ## Solution -Again `Math::Prime::Util` has the two methods we need `factor_exp` and `gcd`. The former a modification to `factor` returns a list of tuples, each containing the prime and its exponent so rather than returning say `2, 2, 2, 3, 3` it returns `[2, 3], [3, 2]`. The latter a function we haven't used before takes a list of numbers and computes there greatest common divisor. This simplfies the problem... for each value we generate a hash of their prime factors, the key being the prime and the value the power (using `factor`) - -We then check to see if any of the factors does not have its square as a factor. We do this in the grep - by using `next` we jump out of the `map` back to the next entry in the `for` loop. - -We then compute the `gcd` of these powers - if it is 1 then we display the result - our output is index, value and the prime factorisation, most of the loop is for the pretty print. ```perl -for( my( $MAX, $c, $n, @f ) = ($ARGV[0] // 1e2, 0); $c<$MAX; ) { - printf "%6d: %15d = %s\n", ++$c, $n, join ' . ', map { join '^', @$_ } @f - if 1 == gcd map { $_->[1] < 2 ? next : $_->[1] } @f = factor_exp ++$n +sub k_product { + [ map { my$r = $_; map { my$t = $_; [ map { my$s=$_; map { $s*$_ } @{$t} } @{$r} ] } @{$_[1]} } @{$_[0]} ] } -``` -The following are the first 50 achilles numbers. - -| Index | Value | Factors | -| -----------: | -------------------: | ------------------------------------------------------------ | -| 1 | 72 | 23.32 | -| 2 | 108 | 22.33 | -| 3 | 200 | 23.52 | -| 4 | 288 | 25.32 | -| 5 | 392 | 23.72 | -| 6 | 432 | 24.33 | -| 7 | 500 | 22.53 | -| 8 | 648 | 23.34 | -| 9 | 675 | 33.52 | -| 10 | 800 | 25.52 | -| 11 | 864 | 25.33 | -| 12 | 968 | 23.112 | -| 13 | 972 | 22.35 | -| 14 | 1,125 | 32.53 | -| 15 | 1,152 | 27.32 | -| 16 | 1,323 | 33.72 | -| 17 | 1,352 | 23.132 | -| 18 | 1,372 | 22.73 | -| 19 | 1,568 | 25.72 | -| 20 | 1,800 | 23.32.52 | -| 21 | 1,944 | 23.35 | -| 22 | 2,000 | 24.53 | -| 23 | 2,312 | 23.172 | -| 24 | 2,592 | 25.34 | -| 25 | 2,700 | 22.33.52 | -| 26 | 2,888 | 23.192 | -| 27 | 3,087 | 32.73 | -| 28 | 3,200 | 27.52 | -| 29 | 3,267 | 33.112 | -| 30 | 3,456 | 27.33 | -| 31 | 3,528 | 23.32.72 | -| 32 | 3,872 | 25.112 | -| 33 | 3,888 | 24.35 | -| 34 | 4,000 | 25.53 | -| 35 | 4,232 | 23.232 | -| 36 | 4,500 | 22.32.53 | -| 37 | 4,563 | 33.132 | -| 38 | 4,608 | 29.32 | -| 39 | 5,000 | 23.54 | -| 40 | 5,292 | 22.33.72 | -| 41 | 5,324 | 22.113 | -| 42 | 5,400 | 23.33.52 | -| 43 | 5,408 | 25.132 | -| 44 | 5,488 | 24.73 | -| 45 | 6,075 | 35.52 | -| 46 | 6,125 | 53.72 | -| 47 | 6,272 | 27.72 | -| 48 | 6,728 | 23.292 | -| 49 | 6,912 | 28.33 | -| 50 | 7,200 | 25.32.52 | - - -Some examples for larger values of `n` are: - -| Index | Value | Factors | -| -----------: | -------------------: | ------------------------------------------------------------ | -| 100 | 21,600 | 25.33.52 | -| 200 | 66,248 | 23.72.132 | -| 300 | 136,107 | 33.712 | -| 400 | 225,000 | 23.32.55 | -| 500 | 333,396 | 22.35.73 | -| 600 | 464,648 | 23.2412 | -| 700 | 617,400 | 23.32.52.73 | -| 800 | 784,000 | 27.53.72 | -| 900 | 969,624 | 23.33.672 | -| 1,000 | 1,179,648 | 217.32 | -| 2,000 | 4,255,443 | 33.3972 | -| 3,000 | 9,082,800 | 24.33.52.292 | -| 4,000 | 15,635,232 | 25.32.2332 | -| 5,000 | 23,876,179 | 193.592 | -| 6,000 | 33,818,428 | 22.73.1572 | -| 7,000 | 45,489,708 | 22.33.112.592 | -| 8,000 | 58,752,800 | 25.52.2712 | -| 9,000 | 73,641,248 | 25.372.412 | -| 10,000 | 90,209,312 | 25.232.732 | -| 20,000 | 344,478,752 | 25.172.1932 | -| 30,000 | 758,595,456 | 27.35.293 | -| 40,000 | 1,330,259,301 | 33.73.3792 | -| 50,000 | 2,057,748,300 | 22.37.52.972 | -| 60,000 | 2,941,077,600 | 25.37.52.412 | -| 70,000 | 3,978,593,667 | 33.612.1992 | -| 80,000 | 5,171,352,984 | 23.35.72.2332 | -| 90,000 | 6,518,604,456 | 23.32.72.133.292 | -| 100,000 | 8,017,975,944 | 23.33.113.1672 | -| 125,000 | 12,437,566,904 | 23.73.21292 | -| 150,000 | 17,810,638,848 | 211.32.9832 | -| 175,000 | 24,140,196,992 | 27.312.4432 | -| 200,000 | 31,413,171,744 | 25.32.173.1492 | -| 225,000 | 39,636,156,125 | 53.178072 | -| 250,000 | 48,804,377,888 | 25.74.7972 | -| 275,000 | 58,919,206,088 | 23.858192 | -| 300,000 | 69,976,609,587 | 33.509092 | -| 325,000 | 81,981,196,443 | 33.551032 | -| 350,000 | 94,917,245,000 | 23.54.43572 | - -And these are the first numbers with `n` digits... - -| Index | Value | Factors | -| -----------: | -------------------: | ------------------------------------------------------------ | -| 1 | 72 | 23.32 | -| 2 | 108 | 22.33 | -| 14 | 1,125 | 32.53 | -| 61 | 10,125 | 34.53 | -| 253 | 100,352 | 211.72 | -| 917 | 1,000,188 | 22.36.73 | -| 3,159 | 10,011,125 | 53.2832 | -| 10,554 | 100,018,800 | 24.36.52.73 | -| 34,562 | 1,000,042,200 | 23.36.52.193 | -| 111,892 | 10,000,373,888 | 27.88392 | -| 359,341 | 100,001,075,328 | 27.32.72.116 | - -### Github formatting script.... - -To convert from the human readable text file generated by the script to github markup I wrote this script: - -```perl -head(); -while( <> ) { - head(), next unless /\S/; - my ($c,$n,$p) = m{(\d+):\s+(\d+)\s+=\s+(.*)$}; - printf "| %12s | %20s | %-60s |\n", th($c), th($n), - join q(.), map { sprintf '%d%d', split /\^/ } split / \. /, $p -} - -sub head { print "\n| Index | Value | Factors | -| -----------: | -------------------: | ------------------------------------------------------------ |\n" } -sub th { scalar reverse ( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } ``` -### Removing pretty print - -If we remove the pretty print this reduces to: +A slightly more compact version (73 characters!) ```perl -for( my( $c, $n ) = 100; $c; ) { - $c--, say $n if 1 == gcd map{ $_->[1] < 2 ? next : $_->[1] } factor_exp ++$n -} +sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} ``` - -# Note - product vs factor - -There is a different method which is to generate a list of numbers for both problems from a list of primes. - -For both challenges I looked at this "product" version of the code (generate a list of primes) and multiplying - rather the factor method. This proved to be slower than the loop through all values of `$n` and filter by factoring. Whether this continues for larger values of `$n` I don't know by I know that producing the first 1 million of each number it was slower, and at that point the product methods then started to hit memory problems. - -One of the memory issues is the `sort` a list issue - having to keep multiple large lists in memory. There are work arounds (like using a modified merge sort) but again these have their coding overheads. - -If I had to roll my own "factor" code it would almost certainly have been a better option - but the `Math::Prime::Util` methods are plenty fast enough. diff --git a/challenge-170/james-smith/blog.txt b/challenge-170/james-smith/blog.txt new file mode 100644 index 0000000000..8ea28b1f8c --- /dev/null +++ b/challenge-170/james-smith/blog.txt @@ -0,0 +1,2 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/james-smith + diff --git a/challenge-170/james-smith/perl/ch-1.pl b/challenge-170/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..5a2bc9c4ea --- /dev/null +++ b/challenge-170/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 Math::Prime::Util qw(next_prime); +use Data::Dumper qw(Dumper); +use bigint; + +my(@x)= my $p = 1; + +push @x, $x[-1] * ($p = next_prime $p) for 1..100; + +say sprintf '%300s', th($_) for @x; + +sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } + diff --git a/challenge-170/james-smith/perl/ch-2.pl b/challenge-170/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..475733ada1 --- /dev/null +++ b/challenge-170/james-smith/perl/ch-2.pl @@ -0,0 +1,22 @@ +#!/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 $m1 = [ [1,2],[3,4] ]; +my $m2 = [ [5,6],[7,8] ]; + +print Dumper( k_product( $m1, $m2 ) ); +print Dumper( k( $m1, $m2 ) ); +sub k_product { + [ map { my$r = $_; map { my$t = $_; [ map { my$s=$_; map { $s*$_ } @{$t} } @{$r} ] } @{$_[1]} } @{$_[0]} ] +} +#----|----#----|----#----|----#----|----#----|----#----|----#----|----#-- +#73 chars... +sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} + -- cgit From 496829c0819e672fafd561c22d39d89e63ceecee Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 20 Jun 2022 09:10:34 +0100 Subject: fixed code in a different way using forprimes --- challenge-170/james-smith/perl/ch-1.pl | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/challenge-170/james-smith/perl/ch-1.pl b/challenge-170/james-smith/perl/ch-1.pl index 5a2bc9c4ea..c1592956e2 100644 --- a/challenge-170/james-smith/perl/ch-1.pl +++ b/challenge-170/james-smith/perl/ch-1.pl @@ -6,15 +6,13 @@ use warnings; use feature qw(say); use Test::More; use Benchmark qw(cmpthese timethis); -use Math::Prime::Util qw(next_prime); +use Math::Prime::Util qw(nth_prime forprimes); use Data::Dumper qw(Dumper); -use bigint; +use bignum; -my(@x)= my $p = 1; +my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime ($ARGV[0]//10); -push @x, $x[-1] * ($p = next_prime $p) for 1..100; - -say sprintf '%300s', th($_) for @x; +say sprintf '%'.int(2+4/3*log($x[-1])/log 10).'s', th($_) for @x; sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } -- cgit From d3452f5e619eb5643419ef7798a3a4f98e08471a Mon Sep 17 00:00:00 2001 From: James Smith Date: Mon, 20 Jun 2022 09:41:06 +0100 Subject: Update README.md --- challenge-170/james-smith/README.md | 58 ++++++++++++++++++++----------------- 1 file changed, 31 insertions(+), 27 deletions(-) diff --git a/challenge-170/james-smith/README.md b/challenge-170/james-smith/README.md index c5bec6d217..b07dc7b7c9 100644 --- a/challenge-170/james-smith/README.md +++ b/challenge-170/james-smith/README.md @@ -19,15 +19,18 @@ https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/ja ***Write a script to generate first 10 Primorial Numbers - like factorials but multiply by succesive primes*** - ## Solution -```perl -my(@x)= my $p = 1; +Another prime problem, in this one we revert to using next_prime to get successive primes. We use a couple more of the methods from `Math::Prime::Util`, `nth_prime` and `forprimes`. + +`forprimes {block} $n` executes `{block}` with primes up to and including `$n`. This isn't quite what we want as we want to have `$n` primes - we can get the *n*th prime with suprisingly `nth_prime`. Combining the two gices us `forprimes {block} nth_prime $n`. -push @x, $x[-1] * ($p = next_prime $p) for 1..100; +We use `bignum` to allow arbitrary integers, so can compute the primordial numbers for large `$n`. In this case to pretty print we use the `commify` method from the perl cookbook {here renamed `th`}. To pretty print the numbers. To right align these numbers we need the maximum length of the numbers - which is `log($x[-1])/log(10)` to get the digits and multiple by 4/3 to add the commas and add 2 for good measure... + +```perl +my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime ($ARGV[0]//10); -say sprintf '%300s', th($_) for @x; +say sprintf '%'.int(2+4/3*log($x[-1])/log 10).'s', th($_) for @x; sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } ``` @@ -40,39 +43,40 @@ sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } Hard to describe - but here is an example.... see https://en.wikipedia.org/wiki/Kronecker_product ``` -A = [ 1 2 ] - [ 3 4 ] - -B = [ 5 6 ] - [ 7 8 ] - -A x B = [ 1 x [ 5 6 ] 2 x [ 5 6 ] ] - [ [ 7 8 ] [ 7 8 ] ] - [ 3 x [ 5 6 ] 4 x [ 5 6 ] ] - [ [ 7 8 ] [ 7 8 ] ] - - = [ 1x5 1x6 2x5 2x6 ] - [ 1x7 1x8 2x7 2x8 ] - [ 3x5 3x6 4x5 4x6 ] - [ 3x7 3x8 4x7 4x8 ] - - = [ 5 6 10 12 ] - [ 7 8 14 16 ] - [ 15 18 20 24 ] - [ 21 24 28 32 ] +A = [ 1 2 ] B = [ 5 6 ] + [ 3 4 ] [ 7 8 ] + +A x B = [ 1 x [ 5 6 ] 2 x [ 5 6 ] ] = [ 1x5 1x6 2x5 2x6 ] = [ 5 6 10 12 ] + [ [ 7 8 ] [ 7 8 ] ] [ 1x7 1x8 2x7 2x8 ] [ 7 8 14 16 ] + [ 3 x [ 5 6 ] 4 x [ 5 6 ] ] [ 3x5 3x6 4x5 4x6 ] [ 15 18 20 24 ] + [ [ 7 8 ] [ 7 8 ] ] [ 3x7 3x8 4x7 4x8 ] [ 21 24 28 32 ] ``` ## Solution +Arrays are just lists of lists, and so we can use constructs like `map` and `for` to process these. +In this case we don't need to use `for`s as we can use `map` in all cases. + +This is one of those cases where writing the code is easier than explaining what it does. + +We have 4 `map`s... The outer two loop over the rows of `A` and `B` respectively, the inner two loop over +the entries in those rows (from matricies `A` and `B` respectively. Because the "loop variable" is `$_` +for each `map` the first thing we do in all but the inner loop is assign it to another variable. ```perl sub k_product { - [ map { my$r = $_; map { my$t = $_; [ map { my$s=$_; map { $s*$_ } @{$t} } @{$r} ] } @{$_[1]} } @{$_[0]} ] + [ map { my $r = $_; map { my $t = $_; [ map { my $s=$_; map { $s*$_ } @{$t} } @{$r} ] } @{$_[1]} } @{$_[0]} ] } ``` -A slightly more compact version (73 characters!) +Now we can use some of our "optimization" techniques to make this slightly smaller. Firstly we use +special variables, `$a`, `$b` and `$'` to replace the variables `$r`, `$s`, `$t` above. We also assign `$_` +to `$'` using the regex trick `//` which does this under the hood. We also remove the optional brackets +around `{$a}` & `{$b}` where dererencing. + +This gives a slightly more compact version (73 characters!) + ```perl sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} ``` -- cgit From c0f90e4df4028f1f8983b0015ebfce6f846589cf Mon Sep 17 00:00:00 2001 From: James Smith Date: Mon, 20 Jun 2022 10:18:57 +0100 Subject: Update README.md --- challenge-169/james-smith/README.md | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) diff --git a/challenge-169/james-smith/README.md b/challenge-169/james-smith/README.md index 9593e23f10..686f887107 100644 --- a/challenge-169/james-smith/README.md +++ b/challenge-169/james-smith/README.md @@ -240,19 +240,19 @@ Some examples for larger values of `n` are: And these are the first numbers with `n` digits... -| Index | Value | Factors | -| -----------: | -------------------: | ------------------------------------------------------------ | -| 1 | 72 | 23.32 | -| 2 | 108 | 22.33 | -| 14 | 1,125 | 32.53 | -| 61 | 10,125 | 34.53 | -| 253 | 100,352 | 211.72 | -| 917 | 1,000,188 | 22.36.73 | -| 3,159 | 10,011,125 | 53.2832 | -| 10,554 | 100,018,800 | 24.36.52.73 | -| 34,562 | 1,000,042,200 | 23.36.52.193 | -| 111,892 | 10,000,373,888 | 27.88392 | -| 359,341 | 100,001,075,328 | 27.32.72.116 | +| Digits | Index | Value | Factors | +| ------ | -----------: | -------------------: | ------------------------------------------------------------ | +| 2 | 1 | 72 | 23.32 | +| 3 | 2 | 108 | 22.33 | +| 4 | 14 | 1,125 | 32.53 | +| 5 | 61 | 10,125 | 34.53 | +| 6 | 253 | 100,352 | 211.72 | +| 7 | 917 | 1,000,188 | 22.36.73 | +| 8 | 3,159 | 10,011,125 | 53.2832 | +| 9 | 10,554 | 100,018,800 | 24.36.52.73 | +| 10 | 34,562 | 1,000,042,200 | 23.36.52.193 | +| 11 | 111,892 | 10,000,373,888 | 27.88392 | +| 12 | 359,341 | 100,001,075,328 | 27.32.72.116 | ### Github formatting script.... -- cgit From 7163d586d6d8bc8dc3747ee295baaa4948447c6e Mon Sep 17 00:00:00 2001 From: James Smith Date: Mon, 20 Jun 2022 10:19:41 +0100 Subject: Update README.md --- challenge-169/james-smith/README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-169/james-smith/README.md b/challenge-169/james-smith/README.md index 686f887107..fb95af0dfc 100644 --- a/challenge-169/james-smith/README.md +++ b/challenge-169/james-smith/README.md @@ -241,7 +241,7 @@ Some examples for larger values of `n` are: And these are the first numbers with `n` digits... | Digits | Index | Value | Factors | -| ------ | -----------: | -------------------: | ------------------------------------------------------------ | +| -----: | -----------: | -------------------: | ------------------------------------------------------------ | | 2 | 1 | 72 | 23.32 | | 3 | 2 | 108 | 22.33 | | 4 | 14 | 1,125 | 32.53 | -- cgit From 414d13aa64234592c387ada15a4a9573b1153f12 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 20 Jun 2022 13:26:06 +0100 Subject: added in short version of ch-1.pl --- challenge-170/james-smith/README.md | 10 ++++++++++ challenge-170/james-smith/perl/ch-1.pl | 7 ++++++- 2 files changed, 16 insertions(+), 1 deletion(-) diff --git a/challenge-170/james-smith/README.md b/challenge-170/james-smith/README.md index b07dc7b7c9..72ed1b2578 100644 --- a/challenge-170/james-smith/README.md +++ b/challenge-170/james-smith/README.md @@ -35,6 +35,16 @@ say sprintf '%'.int(2+4/3*log($x[-1])/log 10).'s', th($_) for @x; sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } ``` +### Short version.... + +A short version of this - we remove the flexibility of using the parameters (`N=10`) and instead of working out he 9th prime in code replacing it with 23, gives, the 30 byte code.. + +```perl +say$a=1;forprimes{say$a*=$_}nth_prime($ARGV[0]//10)-1 # 53 bytes +say$a=1;forprimes{say$a*=$_}nth_prime 9 # 39 bytes +say$a=1;forprimes{say$a*=$_}23 # 30 bytes +``` + # Challenge 2 - Kronecker Product ***Write a script to implement Kronecker Product on the given 2 matrices. e.g.*** diff --git a/challenge-170/james-smith/perl/ch-1.pl b/challenge-170/james-smith/perl/ch-1.pl index c1592956e2..9109ba2161 100644 --- a/challenge-170/james-smith/perl/ch-1.pl +++ b/challenge-170/james-smith/perl/ch-1.pl @@ -10,9 +10,14 @@ use Math::Prime::Util qw(nth_prime forprimes); use Data::Dumper qw(Dumper); use bignum; -my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime ($ARGV[0]//10); +my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime($ARGV[0]//10)-1; say sprintf '%'.int(2+4/3*log($x[-1])/log 10).'s', th($_) for @x; sub th { scalar reverse( (reverse $_[0]) =~ s/(\d\d\d)(?=\d)(?!\d*\.)/$1,/gr ) } + +#----|----#----|----#----|----#----|----#----|----#----|---- +say$a=1;forprimes{say$a*=$_}nth_prime($ARGV[0]//10)-1; +say$a=1;forprimes{say$a*=$_}nth_prime 9; +say$a=1;forprimes{say$a*=$_}23 -- cgit From e3ed838e776b2217f5ecf7beb7064077864fe44d Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 20 Jun 2022 14:36:08 +0100 Subject: add pretty print table --- challenge-170/james-smith/perl/ch-2.pl | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) diff --git a/challenge-170/james-smith/perl/ch-2.pl b/challenge-170/james-smith/perl/ch-2.pl index 475733ada1..02aab70ed4 100644 --- a/challenge-170/james-smith/perl/ch-2.pl +++ b/challenge-170/james-smith/perl/ch-2.pl @@ -4,15 +4,12 @@ use strict; use warnings; use feature qw(say); -use Test::More; -use Benchmark qw(cmpthese timethis); -use Data::Dumper qw(Dumper); -my $m1 = [ [1,2],[3,4] ]; -my $m2 = [ [5,6],[7,8] ]; +my $m1=[[1,2],[3,4]]; +my $m2=[[5,6],[7,8]]; + +d($_) foreach $m1, $m2, k_product($m1,$m2), k($m1,$m2); -print Dumper( k_product( $m1, $m2 ) ); -print Dumper( k( $m1, $m2 ) ); sub k_product { [ map { my$r = $_; map { my$t = $_; [ map { my$s=$_; map { $s*$_ } @{$t} } @{$r} ] } @{$_[1]} } @{$_[0]} ] } @@ -20,3 +17,5 @@ sub k_product { #73 chars... sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} +sub d{say'|',(map{sprintf' %6d',$_}@{$_}),' |'for@{$_[0]};say''} + -- cgit From 8a34b706635f3faa3e241d9b193d218503d0db2e Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 20 Jun 2022 14:45:14 +0100 Subject: document pretty print method --- challenge-170/james-smith/README.md | 28 ++++++++++++++++++++++++++++ challenge-170/james-smith/perl/ch-2.pl | 2 +- 2 files changed, 29 insertions(+), 1 deletion(-) diff --git a/challenge-170/james-smith/README.md b/challenge-170/james-smith/README.md index 72ed1b2578..26b3330934 100644 --- a/challenge-170/james-smith/README.md +++ b/challenge-170/james-smith/README.md @@ -90,3 +90,31 @@ This gives a slightly more compact version (73 characters!) ```perl sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} ``` + +### Pretty print dumper... + +To display the data we have a lightweight pretty print function which displays the matricies: + +```perl +sub d{say'[',(map{sprintf' %6d',$_}@{$_}),' ]'for@{$_[0]};say''} +``` + +Example output for the matrices A & B above, along with the output of `k_product` and the shorter `k`. + +``` +[ 1 2 ] +[ 3 4 ] + +[ 5 6 ] +[ 7 8 ] + +[ 5 6 10 12 ] +[ 7 8 14 16 ] +[ 15 18 20 24 ] +[ 21 24 28 32 ] + +[ 5 6 10 12 ] +[ 7 8 14 16 ] +[ 15 18 20 24 ] +[ 21 24 28 32 ] +``` diff --git a/challenge-170/james-smith/perl/ch-2.pl b/challenge-170/james-smith/perl/ch-2.pl index 02aab70ed4..0f551ca2c2 100644 --- a/challenge-170/james-smith/perl/ch-2.pl +++ b/challenge-170/james-smith/perl/ch-2.pl @@ -17,5 +17,5 @@ sub k_product { #73 chars... sub k{[map{$b=$_;map{$a=$_;[map{//;map{$'*$_}@$a}@$b]}@{$_[1]}}@{$_[0]}]} -sub d{say'|',(map{sprintf' %6d',$_}@{$_}),' |'for@{$_[0]};say''} +sub d{say'[',(map{sprintf' %6d',$_}@{$_}),' ]'for@{$_[0]};say''} -- cgit From 7a4f95407d5160e901dfbe3e42c9c727c61eb5e9 Mon Sep 17 00:00:00 2001 From: James Smith Date: Tue, 21 Jun 2022 12:19:20 +0100 Subject: Update README.md --- challenge-170/james-smith/README.md | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/challenge-170/james-smith/README.md b/challenge-170/james-smith/README.md index 26b3330934..629ef1711c 100644 --- a/challenge-170/james-smith/README.md +++ b/challenge-170/james-smith/README.md @@ -15,20 +15,20 @@ You can find the solutions here on github at: https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-170/james-smith -# Challenge 1 - Primordial Numbers +# Challenge 1 - Primorial Numbers -***Write a script to generate first 10 Primorial Numbers - like factorials but multiply by succesive primes*** +***Write a script to generate first 10 Primorial Numbers - like factorials but multiply by succesive primes.*** ## Solution Another prime problem, in this one we revert to using next_prime to get successive primes. We use a couple more of the methods from `Math::Prime::Util`, `nth_prime` and `forprimes`. -`forprimes {block} $n` executes `{block}` with primes up to and including `$n`. This isn't quite what we want as we want to have `$n` primes - we can get the *n*th prime with suprisingly `nth_prime`. Combining the two gices us `forprimes {block} nth_prime $n`. +`forprimes {block} $n` executes `{block}` with primes up to and including `$n`. This isn't quite what we want as we want to have `$n` primes - we can get the *n*th prime with suprisingly `nth_prime`. Combining the two gives us `forprimes {block} nth_prime $n`. -We use `bignum` to allow arbitrary integers, so can compute the primordial numbers for large `$n`. In this case to pretty print we use the `commify` method from the perl cookbook {here renamed `th`}. To pretty print the numbers. To right align these numbers we need the maximum length of the numbers - which is `log($x[-1])/log(10)` to get the digits and multiple by 4/3 to add the commas and add 2 for good measure... +We use `bignum` to allow arbitrary integers, so can compute the primorial numbers for large `$n`. In this case to pretty print we use the `commify` method from the perl cookbook {here renamed `th`}. To right align these numbers we need the maximum length of the numbers - which is given by `log($x[-1])/log(10)` to get the digits and multiple by 4/3 to add the commas and add 2 for good measure... ```perl -my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime ($ARGV[0]//10); +my @x = (1); forprimes { push @x, $x[-1] * $_ } nth_prime (($ARGV[0]//10)-1); say sprintf '%'.int(2+4/3*log($x[-1])/log 10).'s', th($_) for @x; -- cgit