From a49fd6757614fffec4d45a2b8962b40aa406fad8 Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 9 Aug 2021 14:27:18 +0200 Subject: README --- challenge-125/abigail/README.md | 95 ++++++++++++++++++++++++----------------- 1 file changed, 55 insertions(+), 40 deletions(-) diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index c116d92523..155bfc8302 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -1,27 +1,31 @@ # Solutions by Abigail -## [Happy Women Day][task1] +## [Pythagorean Triples][task1] -> Write a script to print the Venus Symbol, international gender symbol -> for women. Please feel free to use any character. +> You are given a positive integer `$N`. +> +> Write a script to print all Pythagorean Triples containing $N as +> a member. Print `-1` if it can't be a member of any. +> +> Triples with the same set of elements are considered the same, +> i.e. if your script has already printed `(3, 4, 5)`, `(4, 3, 5)` should +> not be printed. +> +> > The famous Pythagorean theorem states that in a right angle +> > triangle, the length of the two shorter sides and the length of the +> > longest side are related by `a^2+b^2 = c^2`. +### Example ~~~~ - ^^^^^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^^^^^ - ^ - ^ - ^ - ^^^^^ - ^ - ^ +Input: $N = 5 +Output: (3, 4, 5) + (5, 12, 13) + +Input: $N = 13 +Output: (5, 12, 13) + (13, 84, 85) + +Input: $N = 1 +Output: -1 ~~~~ ### Solutions @@ -56,40 +60,51 @@ * [Tcl](tcl/ch-1.tcl) ### Blog -[Perl Weekly Challenge 124: Happy Women Day][blog1] +[Perl Weekly Challenge 125: Pythagorean Triples][blog1] + +## [Binary Tree Diameter][task2] -## [Tug of War][task2] +> You are given binary tree as below: -> You are given a set of $n integers `(n1, n2, n3, ...)`. +~~~~ + 1 + / \ + 2 5 + / \ / \ +3 4 6 7 + / \ + 8 10 + / + 9 +~~~~ + +> Write a script to find the diameter of the given binary tree. > -> Write a script to divide the set in two subsets of `n/2` sizes each -> so that the difference of the sum of two subsets is the least. If -> `$n` is even then each subset must be of size `$n/2` each. In case $n -> is odd then one subset must be `($n-1)/2` and other must be `($n+1)/2`. +> > The diameter of a binary tree is the length of the longest path +> > between any two nodes in a tree. It doesn't have to pass +> > through the root. + +For the above given binary tree, possible diameters (7) are: -### Examples ~~~~ -Input: Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100) -Output: Subset 1 = (30, 40, 60, 70, 80) - Subset 2 = (10, 20, 50, 90, 100) +3, 2, 1, 5, 7, 8, 9 ~~~~ +or + ~~~~ -Input: Set = (10, -15, 20, 30, -25, 0, 5, 40, -5) - Subset 1 = (30, 0, 5, -5) - Subset 2 = (10, -15, 20, -25, 40) +4, 2, 1, 5, 7, 8, 9 ~~~~ ### Solutions * [Perl](perl/ch-2.pl) -* [Python](python/ch-2.py) ### Blog -[Perl Weekly Challenge 124: Tug of War][blog2] +[Perl Weekly Challenge 125: Binary Tree Diameter][blog2] -[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-124/#TASK1 -[task2]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-124/#TASK2 -[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-124-1.html -[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-124-2.html +[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-125/#TASK1 +[task2]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-125/#TASK2 +[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-125-1.html +[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-125-2.html -- cgit From 2fd3284b4fe1fff4704852af151b0efcecad2d2c Mon Sep 17 00:00:00 2001 From: Scimon Proctor Date: Mon, 9 Aug 2021 14:12:10 +0100 Subject: Simon reads wikipedia time is over --- challenge-125/simon-proctor/raku/ch-1.raku | 39 ++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 challenge-125/simon-proctor/raku/ch-1.raku diff --git a/challenge-125/simon-proctor/raku/ch-1.raku b/challenge-125/simon-proctor/raku/ch-1.raku new file mode 100644 index 0000000000..bf36282fe4 --- /dev/null +++ b/challenge-125/simon-proctor/raku/ch-1.raku @@ -0,0 +1,39 @@ +#!/usr/bin/env raku + +my @odds = (1,*+2...*).cache; + +multi sub MAIN('test') is hidden-from-USAGE { + use Test; + + is py-triples(3), ( (3,4,5) ); + is py-triples(4), ( (3,4,5) ); + is py-triples(5), ( (3,4,5), (5,12,13) ); + is py-triples(6), (); + is py-triples(13), ( (5,12,13), (13, 84, 85) ); + + done-testing; +} + +#| Given a positive Integer $N print the pythagorean triples it's found in or -1 if there are none +multi sub MAIN(UInt $N where * > 0) { + my @trips = py-triples( $N ); + say -1 unless +@trips; + .join(",").say for @trips; +} + +sub py-triples(UInt $N) { + my @out; + + my @odds = (1,*+2...* >= $N).cache; + + my @pairs = (@odds X, @odds).grep( -> ($m, $n) { $m > $n } ); + + for @pairs -> ( $m, $n ) { + if ( $N ~~ $m * $n || $N ~~ ($m²-$n²)/2 || $N ~~ ($m² + $n²)/2 ) { + push @out, $ = ( ($m * $n), ( ($m²-$n²)/2), ( ($m² + $n²)/2 ) ); + } + } + + return @out; +} + -- cgit From 12dd93a4a9defb89724f216bb360689ff3fd1b9e Mon Sep 17 00:00:00 2001 From: Scimon Proctor Date: Mon, 9 Aug 2021 14:15:15 +0100 Subject: Tidying up a bit --- challenge-125/simon-proctor/raku/ch-1.raku | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/challenge-125/simon-proctor/raku/ch-1.raku b/challenge-125/simon-proctor/raku/ch-1.raku index bf36282fe4..e5dc16521a 100644 --- a/challenge-125/simon-proctor/raku/ch-1.raku +++ b/challenge-125/simon-proctor/raku/ch-1.raku @@ -29,8 +29,9 @@ sub py-triples(UInt $N) { my @pairs = (@odds X, @odds).grep( -> ($m, $n) { $m > $n } ); for @pairs -> ( $m, $n ) { - if ( $N ~~ $m * $n || $N ~~ ($m²-$n²)/2 || $N ~~ ($m² + $n²)/2 ) { - push @out, $ = ( ($m * $n), ( ($m²-$n²)/2), ( ($m² + $n²)/2 ) ); + my $pos = ( ($m * $n), ( ($m²-$n²)/2), ( ($m² + $n²)/2 ) ); + if ( $N ~~ $pos.any ) { + push @out, $pos; } } -- cgit From f6f9fa776f9dc5bd59f7d63ff97625fbea3c3f1a Mon Sep 17 00:00:00 2001 From: Scimon Proctor Date: Mon, 9 Aug 2021 14:54:59 +0100 Subject: Hyper for the win --- challenge-125/simon-proctor/raku/ch-1.raku | 11 +---------- 1 file changed, 1 insertion(+), 10 deletions(-) diff --git a/challenge-125/simon-proctor/raku/ch-1.raku b/challenge-125/simon-proctor/raku/ch-1.raku index e5dc16521a..5caf5d2c2d 100644 --- a/challenge-125/simon-proctor/raku/ch-1.raku +++ b/challenge-125/simon-proctor/raku/ch-1.raku @@ -26,15 +26,6 @@ sub py-triples(UInt $N) { my @odds = (1,*+2...* >= $N).cache; - my @pairs = (@odds X, @odds).grep( -> ($m, $n) { $m > $n } ); - - for @pairs -> ( $m, $n ) { - my $pos = ( ($m * $n), ( ($m²-$n²)/2), ( ($m² + $n²)/2 ) ); - if ( $N ~~ $pos.any ) { - push @out, $pos; - } - } - - return @out; + return (@odds X, @odds).hyper.grep( -> ($m, $n) { $m > $n } ).map( -> ( $m, $n ) { ( ($m * $n), ( ($m²-$n²)/2), ( ($m² + $n²)/2 ) ) } ).grep( -> $pos { $N ~~ $pos.any; } ); } -- cgit From 4fb773b850b3327ac01eb409f24184b21984fa85 Mon Sep 17 00:00:00 2001 From: Scimon Proctor Date: Mon, 9 Aug 2021 16:25:11 +0100 Subject: Binary tree stuff. --- challenge-125/simon-proctor/raku/ch-2.raku | 156 +++++++++++++++++++++++++++++ 1 file changed, 156 insertions(+) create mode 100644 challenge-125/simon-proctor/raku/ch-2.raku diff --git a/challenge-125/simon-proctor/raku/ch-2.raku b/challenge-125/simon-proctor/raku/ch-2.raku new file mode 100644 index 0000000000..2c11ae1465 --- /dev/null +++ b/challenge-125/simon-proctor/raku/ch-2.raku @@ -0,0 +1,156 @@ +#!/usr/bin/env raku + +grammar BTreeGrammar { + token TOP { }; + token tree { ["(" $= ")"]? ["(" $= ")"]? }; + regex value { <-[()]>+ } +} + +class BTreeRep {...} + +role BTree[::T] { + has T $.value is required; + has BTree @!nodes[2]; + + submethod BUILD ( T() :$value, :@nodes ) { + $!value = $value; + @!nodes = @nodes; + } + + method Str( ) { + ( $!value , |@.nodes.map( { "({$_})" } ) ).join(""); + } + + method COERCE( Str:D $str --> BTree ) { + return ::?CLASS.from-Str( $str ); + } + + method nodes() { + @!nodes.grep({defined $_}); + } + + method children() { + @.nodes.elems; + } + + method gist() { + BTreeRep.new( tree=>self ).gist(); + } + + method raku() { + "{self.^name}.new( {("value => {$!value}", self.nodes ?? "nodes => {(self.nodes.map(*.raku)).join(", ")}" !! Empty).join(", ")} )"; + } + + method traverse() { + gather { + if ( self.children ) { + for @.nodes -> $n { + for $n.traverse -> @t { + take ($!value, |@t); + } + } + } else { + take ( $!value, ); + } + } + } + + multi method reverse( ::?CLASS:D: ) { + self.new( + value => $!value, + nodes => @.nodes.reverse.map( *.reverse ) + ) + } + + multi method from-Str('') { BTree } + + multi method from-Str( ::?CLASS:U: Str $in ) { + my $match = BTreeGrammar.parse( $in ); + if ( $match ) { + self.new( + value => $match.Str, + nodes => [ + self.from-Str( $match ?? $match.Str !! '' ), + self.from-Str( $match ?? $match.Str !! '' ) + ] + ); + } else { + die "Unable to Parse $in"; + } + + } +} + +class BTreeRep { + has @.data; + has UInt $.join-point; + + multi submethod BUILD ( BTree :$tree where { ! $tree.children } ) { + @!data = [$tree.value.Str]; + $!join-point = $tree.value.Str.codes div 2; + } + + multi submethod BUILD ( BTree :$tree ) { + my ( $left, $right, $left-width, $right-width ); + my ( @ldata, @rdata, $left-pad, $right-pad ); + + my $mid-string = '┘'; + $left = BTreeRep.new( tree => $tree.nodes[0] ); + $left-width = $left.data[0].codes; + @ldata = $left.data; + @ldata.unshift( (" " x $left.join-point) ~ "┌" ~ ("─" x ($left-width - 1 - $left.join-point) ) ); + + if ( $tree.children == 2 ) { + my $right = BTreeRep.new( tree => $tree.nodes[1] ); + $mid-string = '┴'; + @rdata = $right.data; + $right-width = @rdata[0].codes; + @rdata.unshift( ( "─" x ( $right.join-point ) ~ '┐' ~ ( " " x $right-width - 1 - $right.join-point ) ) ); + } else { + $right-width = 1; + @rdata = @ldata.map( { " " } ); + } + + if ( $left-width + $right-width + 1 < $tree.value.codes ) { + $left-pad = 0; + $right-pad = 0; + my $extra = $tree.value.codes - ($left-width + $right-width + 1); + @ldata = @ldata.map( { ( " " x ( $extra div 2 ) ) ~ $_ } ); + @rdata = @rdata.map( { $_ ~ ( " " x ( $extra div 2 + $extra % 2 ) ) } ); + } else { + $left-pad = $left-width - ($tree.value.codes div 2); + $right-pad = ($left-width + $right-width + 1) - $left-pad - $tree.value.codes; + } + my $top = ( " " x $left-pad ) ~ $tree.value ~ ( " " x $right-pad ); + my $left-fill = gather { for @ldata.elems^..@rdata.elems { take " " x $left-width } }; + my $right-fill = gather { for @rdata.elems^..@ldata.elems { take " " x $right-width } }; + + @!data = $top, |( ( (|@ldata, |$left-fill) Z, (|@rdata, |$right-fill) ).map( { state $i=0;$_.join($i++??" "!!$mid-string) } ) ); + $!join-point = $left-pad + ( $tree.value.Str.codes div 2); + } + + method gist { + @.data.join("\n"); + } + +} + +multi sub MAIN( 'example' ) { + MAIN('1(2(3)(4))(5(6)(7(8(9))(10)))'); +} + +multi sub MAIN( *@data ) { + my BTree[Any](Str) $tree = @data.join(""); + my @routes = $tree.traverse.sort( -*.elems ); + + my $long = shift @routes; + my $result = $long.elems; + for @routes -> $pos { + if ($long (&) $pos).elems == 1 { + $result = $long.elems + $pos.elems - 1; + last; + } + } + say $result; +} + -- cgit From df64daf6d419ae5be1a3f7f2c23ab4c3181d568e Mon Sep 17 00:00:00 2001 From: Scimon Proctor Date: Mon, 9 Aug 2021 16:27:32 +0100 Subject: Make the Str Rep Object a passable --- challenge-125/simon-proctor/raku/ch-2.raku | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/challenge-125/simon-proctor/raku/ch-2.raku b/challenge-125/simon-proctor/raku/ch-2.raku index 2c11ae1465..2ab4173e5a 100644 --- a/challenge-125/simon-proctor/raku/ch-2.raku +++ b/challenge-125/simon-proctor/raku/ch-2.raku @@ -8,7 +8,7 @@ grammar BTreeGrammar { class BTreeRep {...} -role BTree[::T] { +role BTree[::T,::R=BTreeRep] { has T $.value is required; has BTree @!nodes[2]; @@ -34,7 +34,7 @@ role BTree[::T] { } method gist() { - BTreeRep.new( tree=>self ).gist(); + R.new( tree=>self ).gist(); } method raku() { @@ -143,6 +143,8 @@ multi sub MAIN( *@data ) { my BTree[Any](Str) $tree = @data.join(""); my @routes = $tree.traverse.sort( -*.elems ); + say $tree; + my $long = shift @routes; my $result = $long.elems; for @routes -> $pos { -- cgit From 5f09f670cc58cb94b6a36599ecf5e580484e6759 Mon Sep 17 00:00:00 2001 From: chirvasitua Date: Mon, 9 Aug 2021 17:18:10 -0400 Subject: 1st commit on 125_raku --- challenge-125/stuart-little/raku/ch-1.raku | 21 ++++++++++++ challenge-125/stuart-little/raku/ch-2.raku | 55 ++++++++++++++++++++++++++++++ 2 files changed, 76 insertions(+) create mode 100755 challenge-125/stuart-little/raku/ch-1.raku create mode 100755 challenge-125/stuart-little/raku/ch-2.raku diff --git a/challenge-125/stuart-little/raku/ch-1.raku b/challenge-125/stuart-little/raku/ch-1.raku new file mode 100755 index 0000000000..4799cc37c4 --- /dev/null +++ b/challenge-125/stuart-little/raku/ch-1.raku @@ -0,0 +1,21 @@ +#!/usr/bin/env raku +use v6; + +# run