From d338fa3ebab0eb4c9d10bf525770175f8fca5bc6 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 9 Aug 2021 10:56:43 +0100 Subject: first challenge - will need to dig out binary tree code to get diameter --- challenge-125/james-smith/perl/ch-1.pl | 48 ++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100644 challenge-125/james-smith/perl/ch-1.pl diff --git a/challenge-125/james-smith/perl/ch-1.pl b/challenge-125/james-smith/perl/ch-1.pl new file mode 100644 index 0000000000..7227b26068 --- /dev/null +++ b/challenge-125/james-smith/perl/ch-1.pl @@ -0,0 +1,48 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Test::More; +use Benchmark qw(cmpthese timethis); +use Data::Dumper qw(Dumper); + +my @TESTS = ( + [ 0, 1 ], +); + +say $_,' > ', get_triples($_) foreach 1..100; + +sub get_triples { + my $n = shift; + return $n < 3 ? -1 : join '; ', map { sprintf '(%s)', join ', ', @{$_} } + ( + grep { $_->[1] == int $_->[1] } ## Check if all int + map { [ $_, sqrt($n**2-$_**2), $n ] } ## Generate triple + 3 .. sqrt($n**2/2) ## Shortest side ($n is hypotenuse) + ),( + map { $_->[0]>$_->[1] ? [@{$_}[1,0,2]] : $_ } ## put in numerical order + grep { $_->[1] == int $_->[1] } ## Check all int + map { [ $n, sqrt($_**2-$n**2), $_ ] } ## Generate triple + ($n+1) .. ($n**2/2+1) ## Hypotenuse ($n is one of other two sides) + ); +} + +## Notes: + +# Except for $n < 3 there is always a solution +# * If $n is odd then it can always be the short side of a triangle where the +# other sides are ($n^2-1)/2 or ($n^2+1)/2 +# * If $n has an odd factor - then we can rewrite $n as $o * $m +# we can use the same trick to get sides of $m($o^2-1)/2 & $m($o^2+1)/2 +# * This only leaves us with numbers of the form 2^n - but we know that 4 can be part of a Pyth.Triple +# and so any number of the form 2^($n+2) in a triple of the form ( 3.2^$n, 4.2^$n, 5.2^$n ). +# +# * We have two cases where $n is the hypotenuse and where it is a shorter side. +# * With the former we need to look at the shorter sides these can be 3 -> n-1 +# but to avoid dupes we limit our search to sqrt(n^2/2)... +# * The latter is more complex to work out the range +# But we note that the difference between two consecutive squares is ($m+1)^2-($m)^2 = 2m + 1 +# So the largest value for the hypotenuse is therefore (n^2+1)/2 + -- cgit 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 a33edce979ce6b299a1df1640a83dc67231a14bd Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 9 Aug 2021 15:37:01 +0100 Subject: part II now added --- challenge-125/james-smith/perl/BinaryTree.pm | 170 +++++++++++++++++++++++++++ challenge-125/james-smith/perl/ch-1.pl | 2 +- challenge-125/james-smith/perl/ch-2.pl | 89 ++++++++++++++ 3 files changed, 260 insertions(+), 1 deletion(-) create mode 100644 challenge-125/james-smith/perl/BinaryTree.pm create mode 100644 challenge-125/james-smith/perl/ch-2.pl diff --git a/challenge-125/james-smith/perl/BinaryTree.pm b/challenge-125/james-smith/perl/BinaryTree.pm new file mode 100644 index 0000000000..1cbcbfc511 --- /dev/null +++ b/challenge-125/james-smith/perl/BinaryTree.pm @@ -0,0 +1,170 @@ +package BinaryTree; + +use strict; +use warnings; +use Data::Dumper qw(Dumper); +use feature qw(say); + +## The tree is stored in an array ref +# The first element is the value of the node +# The remainder of the array are child sub-trees +# +# Methods: +# ->add_child( $child_tree ) +# ->flatten -- flatten list to array. +# + +sub new { + my $class = shift; + my $value = shift; + my $self = [ $value, undef, undef ]; + bless $self, $class; +} + +sub depth { + my $self = shift; + my $d = 0; + $d = $self->left->depth if $self->has_left; + return 1+$d unless $self->has_right; + my $t = $self->right->depth; + return $t > $d ? 1+$t : 1+$d; +} + +sub diameter { + my $self = shift; + return 1 + $self->left->depth + $self->right->depth if $self->has_left && $self->has_right; + + my $diameter = $self->depth; ## Case 1 has a single depth.... + my $t = $self->has_left ? $self->left : $self->right; + while( $t->has_left || $t->has_right ) { + if( $t->has_left && $t->has_right ) { + my $d = 1 + $t->left->depth + $t->right->depth; + return $d > $diameter ? $d : $diameter; + } + $t = $t->has_left ? $t->left : $t->right; + } + return $diameter; +} + +sub value { + my $self = shift; + return $self->[0]; +} + +sub left { + my $self = shift; + return $self->[1]; +} + +sub right { + my $self = shift; + return $self->[2]; +} + +sub has_left { + my $self = shift; + return defined $self->[1]; +} + +sub has_right { + my $self = shift; + return defined $self->[2]; +} + +sub update { + my( $self, $val ) = @_; + $self->[0] = $val; + return $self; +} + +sub add_child_left { + my( $self,$child ) = @_; + $self->[1] = $child; + return $self; +} + +sub add_child_right { + my( $self,$child ) = @_; + $self->[2] = $child; + return $self; +} + +## Define walk method.... +sub walk { + my $self = shift; + $self->walk_pre( @_ ); + return; +} + +## +## Pre-order walk process node then the left and right sub-trees +## + +sub walk_pre { + my( $self, $fn, $global, $local, $dir ) = @_; + $local = $fn->( $self, $global, $local, $dir||'' ); + $self->left->walk_pre( $fn, $global, $local, 'left' ) if $self->has_left; + $self->right->walk_pre( $fn, $global, $local, 'right' ) if $self->has_right; + return; +} + +## +## In-order walk process left sub-tree, then the node and finally the right sub-tree +## + +sub walk_in { + my( $self, $fn, $global, $local, $dir ) = @_; + $self->left->walk_in( $fn, $global, $local, 'left' ) if $self->has_left; + $local = $fn->( $self, $global, $local, $dir||'' ); + $self->right->walk_in( $fn, $global, $local, 'right' ) if $self->has_right; + return; +} + +## +## Reverse-order walk process right sub-tree, then the node and finally the left sub-tree +## + +sub walk_reverse { + my( $self, $fn, $global, $local, $dir ) = @_; + $self->right->walk_reverse( $fn, $global, $local, 'right' ) if $self->has_right; + $local = $fn->( $self, $global, $local, $dir||'' ); + $self->left->walk_reverse( $fn, $global, $local, 'left' ) if $self->has_left; + return; +} + +## +## Post-order walk the left and right subtrees before processing the node... +## + +sub walk_post { + my( $self, $fn, $global, $local, $dir ) = @_; + $self->left->walk_post( $fn, $global, $local, 'left' ) if $self->has_left; + $self->right->walk_post( $fn, $global, $local, 'right' ) if $self->has_right; + $local = $fn->( $self, $global, $local, $dir||'' ); + return; +} + +sub flatten { + my( $self,$dump_fn, $method ) = @_; + $dump_fn ||= sub { $_[0] }; + $method = $self->can( 'walk_'.($method||'pre') ) || 'walk'; + my $arrayref = []; + $self->$method( sub { + my($node,$global) = @_; + push @{$global}, $dump_fn->( $node->value ); + }, $arrayref ); + return @{$arrayref}; +} + +sub dump { + my( $self, $dump_fn ) = @_; + $dump_fn ||= sub { $_[0] }; + $self->walk( sub { + my( $node, $global, $local, $dir ) = @_; + say join '', $local||'', $dir eq 'left' ? '<' : $dir eq 'right' ? '>' : ' ', ' ', $dump_fn->($node->value); + return $local .= ' '; + }, {}, '', '' ); + return; +} + +1; diff --git a/challenge-125/james-smith/perl/ch-1.pl b/challenge-125/james-smith/perl/ch-1.pl index 7227b26068..c0bf708d10 100644 --- a/challenge-125/james-smith/perl/ch-1.pl +++ b/challenge-125/james-smith/perl/ch-1.pl @@ -12,7 +12,7 @@ my @TESTS = ( [ 0, 1 ], ); -say $_,' > ', get_triples($_) foreach 1..100; +say $_,' > ', get_triples($_) foreach 1..500; sub get_triples { my $n = shift; diff --git a/challenge-125/james-smith/perl/ch-2.pl b/challenge-125/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..451047c0cb --- /dev/null +++ b/challenge-125/james-smith/perl/ch-2.pl @@ -0,0 +1,89 @@ +#!/usr/local/bin/perl + +use strict; + +use warnings; +use feature qw(say); +use Test::More; +use lib '.'; +use BinaryTree; + +say ''; + +## Node has both left and right trees - the diameter is 1 + depth of the two child trees. + +## 1 -> 2 -> 3 +## | `> 4 +## `> 5 -> 6 +## `> 7 -> 8 -> 9 [ depth 5 ] +## `> 10 +## ------------------------------- +## 9 -> 8 -> 7 -> 5 -> 1 -> 2 -> 3 [ diameter 7 ] + +my $x = BinaryTree->new(1)->add_child_left( + BinaryTree->new(2)->add_child_left( BinaryTree->new(3) )->add_child_right( BinaryTree->new(4) ) + )->add_child_right( + BinaryTree->new(5)->add_child_left( BinaryTree->new(6))->add_child_right( + BinaryTree->new(7)->add_child_left( BinaryTree->new(8)->add_child_left(BinaryTree->new(9)) )->add_child_right(BinaryTree->new(10)) + )); +$x->dump; +say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; +say ''; +## No node has 2 children - the diameter is the depth... + +## 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 [ depth 7 ] +## ------------------------------- +## 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 [ diameter 7 ] +$x = BinaryTree->new(1)->add_child_left( + BinaryTree->new(2)->add_child_left( + BinaryTree->new(3)->add_child_right( + BinaryTree->new(4)->add_child_left( + BinaryTree->new(5)->add_child_right( + BinaryTree->new(6)->add_child_left( + BinaryTree->new(7) + )))))); + +$x->dump; +say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; +say ''; +## We have a node with two children - but there is a sequence of nodes +## leading up to this node which is longer than the depth of the child trees. +## so diameter is just depth. + +## 1 -> 2 -> 3 -> 4 -> 5 -> 6 [ depth 6] +## `> 7 -> 8 +## -------------------------- +## 6 -> 5 -> 4 -> 3 -> 2 -> 1 [ diameter 6 ] +$x = BinaryTree->new(1)->add_child_left( + BinaryTree->new(2)->add_child_left( + BinaryTree->new(3)->add_child_left( + BinaryTree->new(4)->add_child_left( + BinaryTree->new(5)->add_child_left( BinaryTree->new(6) ) + )->add_child_right( + BinaryTree->new(7)->add_child_left( BinaryTree->new(8) ) + ) + ))); + +$x->dump; +say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; +say ''; + +## This time both child trees have depths longer than the number of +## ancestor nodes - so that is used to get the length... + +## 1 -> 2 -> 3 -> 4 [ depth 4] +## `> 5 -> 6 +## --------------------- +## 6 -> 5 -> 2 -> 3 -> 4 [ diameter 5 ] + +$x = BinaryTree->new(1)->add_child_left( + BinaryTree->new(2)->add_child_left( + BinaryTree->new(3)->add_child_left( BinaryTree->new(4) ) + )->add_child_right( + BinaryTree->new(5)->add_child_left( BinaryTree->new(6) ) + ) + ); + +$x->dump; +say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; +say ''; -- cgit From 6fddb13683f2f163aa9a83ea21230b1a07cc7fcf Mon Sep 17 00:00:00 2001 From: drbaggy Date: Mon, 9 Aug 2021 15:46:59 +0100 Subject: there is one more thing I've got to add as I don't think 2 is done exhaustively enough yet... --- challenge-125/james-smith/perl/ch-2.pl | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/challenge-125/james-smith/perl/ch-2.pl b/challenge-125/james-smith/perl/ch-2.pl index 451047c0cb..d4d2cb738d 100644 --- a/challenge-125/james-smith/perl/ch-2.pl +++ b/challenge-125/james-smith/perl/ch-2.pl @@ -26,6 +26,7 @@ my $x = BinaryTree->new(1)->add_child_left( BinaryTree->new(5)->add_child_left( BinaryTree->new(6))->add_child_right( BinaryTree->new(7)->add_child_left( BinaryTree->new(8)->add_child_left(BinaryTree->new(9)) )->add_child_right(BinaryTree->new(10)) )); +say '1) Tree with root node having both left and right children!'; $x->dump; say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; say ''; @@ -43,6 +44,7 @@ $x = BinaryTree->new(1)->add_child_left( BinaryTree->new(7) )))))); +say '2) Tree with no node having two children'; $x->dump; say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; say ''; @@ -64,6 +66,8 @@ $x = BinaryTree->new(1)->add_child_left( ) ))); +say '3) Tree with node further down having two children - but distance from'; +say ' root to node is greater than the depth of either child'; $x->dump; say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; say ''; @@ -76,6 +80,8 @@ say ''; ## --------------------- ## 6 -> 5 -> 2 -> 3 -> 4 [ diameter 5 ] +say '4) Tree with node further down having two children - but distance from'; +say ' root to node is less than the depth of both children'; $x = BinaryTree->new(1)->add_child_left( BinaryTree->new(2)->add_child_left( BinaryTree->new(3)->add_child_left( BinaryTree->new(4) ) -- cgit From da9333b5b848624319742346d77d09cf35ec3e6a Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 9 Aug 2021 16:21:34 +0100 Subject: Solutions for challenge #125 --- challenge-125/roger-bell-west/perl/ch-1.pl | 44 +++++++++++++++++++++++ challenge-125/roger-bell-west/perl/ch-2.pl | 35 +++++++++++++++++++ challenge-125/roger-bell-west/python/ch-1.py | 45 ++++++++++++++++++++++++ challenge-125/roger-bell-west/python/ch-2.py | 36 +++++++++++++++++++ challenge-125/roger-bell-west/raku/ch-2.p6 | 33 ++++++++++++++++++ challenge-125/roger-bell-west/ruby/ch-1.rb | 51 +++++++++++++++++++++++++++ challenge-125/roger-bell-west/ruby/ch-2.rb | 40 +++++++++++++++++++++ challenge-125/roger-bell-west/rust/ch-1.rs | 52 ++++++++++++++++++++++++++++ challenge-125/roger-bell-west/rust/ch-2.rs | 36 +++++++++++++++++++ 9 files changed, 372 insertions(+) create mode 100755 challenge-125/roger-bell-west/perl/ch-1.pl create mode 100755 challenge-125/roger-bell-west/perl/ch-2.pl create mode 100755 challenge-125/roger-bell-west/python/ch-1.py create mode 100755 challenge-125/roger-bell-west/python/ch-2.py create mode 100755 challenge-125/roger-bell-west/raku/ch-2.p6 create mode 100755 challenge-125/roger-bell-west/ruby/ch-1.rb create mode 100755 challenge-125/roger-bell-west/ruby/ch-2.rb create mode 100755 challenge-125/roger-bell-west/rust/ch-1.rs create mode 100755 challenge-125/roger-bell-west/rust/ch-2.rs diff --git a/challenge-125/roger-bell-west/perl/ch-1.pl b/challenge-125/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..4c09301883 --- /dev/null +++ b/challenge-125/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,44 @@ +#! /usr/bin/perl + +use strict; + +use List::Util qw(min); + +use Test::More tests => 3; + +is_deeply(pt(5),[[3,4,5],[5,12,13]],'example 1'); +is_deeply(pt(13),[[5,12,13],[13,84,85]],'example 2'); +is_deeply(pt(1),[],'example 3'); + +sub pt { + my $n=shift; + my @out; + my @tri=([3,4,5]); + while (@tri) { + my $t=shift @tri; + foreach my $i (0..2) { + if ($n % $t->[$i] == 0) { + my $k=$n/$t->[$i]; + push @out,[map {$_*$k} @{$t}]; + } + } + unless (min(@{$t}) > $n) { + push @tri,[ + $t->[0]-2*$t->[1]+2*$t->[2], + 2*$t->[0]-1*$t->[1]+2*$t->[2], + 2*$t->[0]-2*$t->[1]+3*$t->[2], + ]; + push @tri,[ + $t->[0]+2*$t->[1]+2*$t->[2], + 2*$t->[0]+1*$t->[1]+2*$t->[2], + 2*$t->[0]+2*$t->[1]+3*$t->[2], + ]; + push @tri,[ + -$t->[0]+2*$t->[1]+2*$t->[2], + -2*$t->[0]+1*$t->[1]+2*$t->[2], + -2*$t->[0]+2*$t->[1]+3*$t->[2], + ]; + } + } + return \@out; +} diff --git a/challenge-125/roger-bell-west/perl/ch-2.pl b/challenge-125/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..684604b182 --- /dev/null +++ b/challenge-125/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,35 @@ +#! /usr/bin/perl + +use strict; + +use Test::More tests => 1; +use List::Util qw(max); + +is(btd([1, + 2,5, + 3,4,6,7, + 0,0,0,0,0,0,8,10, + 0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),7,'example 1'); + +sub btd { + my $tree=shift; + my $st=scalar @{$tree}; + my @depth=(0) x $st; + my @diameter=(0) x $st; + for (my $i=$st-1;$i>=0;$i--) { + if ($tree->[$i] != 0) { + my $a=$i*2+1; + my $b=$a+1; + if ($b < $st) { + $depth[$i]=1+max($depth[$a],$depth[$b]); + $diameter[$i]=max(1+$depth[$a]+$depth[$b], + $diameter[$a], + $diameter[$b]); + } else { + $depth[$i]=1; + $diameter[$i]=1; + } + } + } + return $diameter[0]; +} diff --git a/challenge-125/roger-bell-west/python/ch-1.py b/challenge-125/roger-bell-west/python/ch-1.py new file mode 100755 index 0000000000..4fab2618f2 --- /dev/null +++ b/challenge-125/roger-bell-west/python/ch-1.py @@ -0,0 +1,45 @@ +#! /usr/bin/python3 + +import unittest +from collections import deque + +def pt(n): + out=[] + tri=deque() + tri.append([3,4,5]) + while len(tri)>0: + t=tri.popleft() + for i in range(3): + dm=divmod(n,t[i]) + if dm[1]==0: + out.append([i*dm[0] for i in t]) + if min(t) <= n: + tri.append([ + t[0]-2*t[1]+2*t[2], + 2*t[0]-1*t[1]+2*t[2], + 2*t[0]-2*t[1]+3*t[2], + ]) + tri.append([ + t[0]+2*t[1]+2*t[2], + 2*t[0]+1*t[1]+2*t[2], + 2*t[0]+2*t[1]+3*t[2], + ]) + tri.append([ + -t[0]+2*t[1]+2*t[2], + -2*t[0]+1*t[1]+2*t[2], + -2*t[0]+2*t[1]+3*t[2], + ]) + return out + +class TestPt(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(pt(5),[[3,4,5],[5,12,13]],'example 1') + + def test_ex2(self): + self.assertEqual(pt(13),[[5,12,13],[13,84,85]],'example 2') + + def test_ex3(self): + self.assertEqual(pt(1),[],'example 3') + +unittest.main() diff --git a/challenge-125/roger-bell-west/python/ch-2.py b/challenge-125/roger-bell-west/python/ch-2.py new file mode 100755 index 0000000000..b03a09c4e0 --- /dev/null +++ b/challenge-125/roger-bell-west/python/ch-2.py @@ -0,0 +1,36 @@ +#! /usr/bin/python3 + +import unittest + +from math import degrees,atan2 + +def btd(tree): + st=len(tree) + depth=[0]*st + diameter=[0]*st + for i in range(st-1,-1,-1): + if tree[i] != 0: + a=i*2+1 + b=a+1 + if b < st: + depth[i]=1+max(depth[a],depth[b]) + diameter[i]=max( + 1+depth[a]+depth[b], + diameter[a], + diameter[b] + ) + else: + depth[i]=1 + diameter[i]=1 + return diameter[0] + +class TestBtd(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(btd([1, + 2,5, + 3,4,6,7, + 0,0,0,0,0,0,8,10, + 0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),7,'example 1') + +unittest.main() diff --git a/challenge-125/roger-bell-west/raku/ch-2.p6 b/challenge-125/roger-bell-west/raku/ch-2.p6 new file mode 100755 index 0000000000..0014033351 --- /dev/null +++ b/challenge-125/roger-bell-west/raku/ch-2.p6 @@ -0,0 +1,33 @@ +#! /usr/bin/perl6 + +use Test; + +plan 1; + +is(btd([1, + 2,5, + 3,4,6,7, + 0,0,0,0,0,0,8,10, + 0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0]),7,'example 1'); + +sub btd(@tree) { + my $st=@tree.elems; + my @depth=(0) xx $st; + my @diameter=(0) xx $st; + loop (my $i=$st-1;$i>=0;$i--) { + if (@tree[$i] != 0) { + my $a=$i*2+1; + my $b=$a+1; + if ($b < $st) { + @depth[$i]=1+max(@depth[$a],@depth[$b]); + @diameter[$i]=max(1+@depth[$a]+@depth[$b], + @diameter[$a], + @diameter[$b]); + } else { + @depth[$i]=1; + @diameter[$i]=1; + } + } + } + return @diameter[0]; +} diff --git a/challenge-125/roger-bell-west/ruby/ch-1.rb b/challenge-125/roger-bell-west/ruby/ch-1.rb new file mode 100755 index 0000000000..6ac3537985 --- /dev/null +++ b/challenge-125/roger-bell-west/ruby/ch-1.rb @@ -0,0 +1,51 @@ +#! /usr/bin/ruby + +def pt(n) + out=[] + tri=[[3,4,5]] + while (tri.length>0) do + t=tri.shift + 0.upto(2) do |i| + dm=n.divmod(t[i]) + if dm[1]==0 then + out.push(t.map{|i| i*dm[0]}) + end + end + if t.min <= n then + tri.push([ + t[0]-2*t[1]+2*t[2], + 2*t[0]-1*t[1]+2*t[2], + 2*t[0]-2*t[1]+3*t[2], + ]) + tri.push([ + t[0]+2*t[1]+2*t[2], + 2*t[0]+1*t[1]+2*t[2], + 2*t[0]+2*t[1]+3*t[2], + ]) + tri.push([ + -t[0]+2*t[1]+2*t[2], + -2*t[0]+1*t[1]+2*t[2], + -2*t[0]+2*t[1]+3*t[2], + ]) + end + end + return out +end + +require 'test/unit' + +class TestPt < Test::Unit::TestCase + + def test_ex1 + assert_equal([[3,4,5],[5,12,13]],pt(5)) + end + + def test_ex2 + assert_equal([[5,12,13],[13,84,85]],pt(13)) + end + + def test_ex3 + assert_equal([],pt(1)) + end + +end diff --git a/challenge-125/roger-bell-west/ruby/ch-2.rb b/challenge-125/roger-bell-west/ruby/ch-2.rb new file mode 100755 index 0000000000..36bd3ce90c --- /dev/null +++ b/challenge-125/roger-bell-west/ruby/ch-2.rb @@ -0,0 +1,40 @@ +#! /usr/bin/ruby + +def btd(tree) + st=tree.length + depth=Array.new(st,0) + diameter=Array.new(st,0) + (st-1).downto(0) do |i| + if tree[i] != 0 then + a=i*2+1 + b=a+1 + if b < st then + depth[i]=1+[depth[a],depth[b]].max + diameter[i]=[ + 1+depth[a]+depth[b], + diameter[a], + diameter[b], + ].max + else + depth[i]=1 + diameter[i]=1 + end + end + end + return diameter[0] +end + +require 'test/unit' + +class TestBtd < Test::Unit::TestCase + + def test_ex1 + assert_equal(7,btd([1, + 2,5, + 3,4,6,7, + 0,0,0,0,0,0,8,10, + 0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0 + ])) + end + +end diff --git a/challenge-125/roger-bell-west/rust/ch-1.rs b/challenge-125/roger-bell-west/rust/ch-1.rs new file mode 100755 index 0000000000..f1a6ecb665 --- /dev/null +++ b/challenge-125/roger-bell-west/rust/ch-1.rs @@ -0,0 +1,52 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit + +use std::collections::VecDeque; + +#[test] +fn test_ex1() { + assert_eq!(pt(5),vec![vec![3,4,5],vec![5,12,13]]); +} + +#[test] +fn test_ex2() { + assert_eq!(pt(13),vec![vec![5,12,13],vec![13,84,85]]); +} + +#[test] +fn test_ex3() { + assert_eq!(pt(1),Vec::>::new()); +} + +fn pt(n: i64) -> Vec> { + let mut out=vec![]; + let mut tri: VecDeque>=VecDeque::new(); + tri.push_back(vec![3,4,5]); + while tri.len()>0 { + let t=tri.pop_front().unwrap(); + for i in 0..=2 { + if n % t[i] == 0 { + let k=n/t[i]; + out.push(t.iter().map(|j| j*k).collect()); + } + } + if t.iter().min().unwrap() <= &n { + tri.push_back(vec![ + t[0]-2*t[1]+2*t[2], + 2*t[0]-1*t[1]+2*t[2], + 2*t[0]-2*t[1]+3*t[2], + ]); + tri.push_back(vec![ + t[0]+2*t[1]+2*t[2], + 2*t[0]+1*t[1]+2*t[2], + 2*t[0]+2*t[1]+3*t[2], + ]); + tri.push_back(vec![ + -t[0]+2*t[1]+2*t[2], + -2*t[0]+1*t[1]+2*t[2], + -2*t[0]+2*t[1]+3*t[2], + ]); + } + } + return out; +} diff --git a/challenge-125/roger-bell-west/rust/ch-2.rs b/challenge-125/roger-bell-west/rust/ch-2.rs new file mode 100755 index 0000000000..ddd67a4a27 --- /dev/null +++ b/challenge-125/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,36 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit + +#[test] +fn test_ex1() { + assert_eq!(btd(vec![1, + 2,5, + 3,4,6,7, + 0,0,0,0,0,0,8,10, + 0,0,0,0,0,0,0,0,0,0,0,0,9,0,0,0 + ]),7); +} + +fn btd(tree: Vec) -> u64 { + let st=tree.len(); + let mut depth: Vec=vec![0;st]; + let mut diameter: Vec=vec![0;st]; + for i in (0..st).rev() { + if tree[i]!=0 { + let a=i*2+1; + let b=a+1; + if b < st { + depth[i]=1+[depth[a],depth[b]].iter().max().unwrap(); + diameter[i]=*[ + 1+depth[a]+depth[b], + diameter[a], + diameter[b] + ].iter().max().unwrap(); + } else { + depth[i]=1; + diameter[i]=1; + } + } + } + return diameter[0] +} -- cgit From 7114102c500fcc0ce6e7d9340bad7ba3407b175b Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 9 Aug 2021 18:28:34 +0100 Subject: Addendum, PostScript answer to part 2 --- challenge-125/roger-bell-west/postscript/ch-2.ps | 73 ++++++++++++++++++++++++ 1 file changed, 73 insertions(+) create mode 100644 challenge-125/roger-bell-west/postscript/ch-2.ps diff --git a/challenge-125/roger-bell-west/postscript/ch-2.ps b/challenge-125/roger-bell-west/postscript/ch-2.ps new file mode 100644 index 0000000000..94731bac34 --- /dev/null +++ b/challenge-125/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,73 @@ +%! no DSC + +% def btd(tree) +% st=tree.length +% depth=Array.new(st,0) +% diameter=Array.new(st,0) +% (st-1).downto(0) do |i| +% if tree[i] != 0 then +% a=i*2+1 +% b=a+1 +% if b < st then +% depth[i]=1+[depth[a],depth[b]].max +% diameter[i]=[ +% 1+depth[a]+depth[b], +% diameter[a], +% diameter[b], +% ].max +% else +% depth[i]=1 +% diameter[i]=1 +% end +% end +% end +% return diameter[0] +% end + +/max2 { + dup % a b b + 3 2 roll % b b a + dup % b b a a + 3 1 roll % b a b a + lt { exch} if + pop +} def + +/btd { + /tree exch def + /st tree length def + /depth st array def + /diameter st array def + 0 1 st 1 sub { + dup + depth exch 0 put + diameter exch 0 put + } for + st 1 sub 1 neg 0 { + /i exch def + tree i get 0 ne { + /a i 2 mul 1 add def + /b a 1 add def + b st lt { + depth i depth a get depth b get max2 1 add put + diameter i + depth a get depth b get 1 add add + diameter a get + diameter b get + max2 max2 put + } { + depth i 1 put + diameter i 1 put + } ifelse + } if + } for + diameter 0 get +} def + +[ 1 + 2 5 + 3 4 6 7 + 0 0 0 0 0 0 8 10 + 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 ] +btd += -- cgit From 62886f842bcb91f8367217da8b9662cefbd3088f Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 9 Aug 2021 18:29:58 +0100 Subject: syntax --- challenge-125/roger-bell-west/postscript/ch-2.ps | 24 ------------------------ 1 file changed, 24 deletions(-) diff --git a/challenge-125/roger-bell-west/postscript/ch-2.ps b/challenge-125/roger-bell-west/postscript/ch-2.ps index 94731bac34..175b9e02ef 100644 --- a/challenge-125/roger-bell-west/postscript/ch-2.ps +++ b/challenge-125/roger-bell-west/postscript/ch-2.ps @@ -1,29 +1,5 @@ %! no DSC -% def btd(tree) -% st=tree.length -% depth=Array.new(st,0) -% diameter=Array.new(st,0) -% (st-1).downto(0) do |i| -% if tree[i] != 0 then -% a=i*2+1 -% b=a+1 -% if b < st then -% depth[i]=1+[depth[a],depth[b]].max -% diameter[i]=[ -% 1+depth[a]+depth[b], -% diameter[a], -% diameter[b], -% ].max -% else -% depth[i]=1 -% diameter[i]=1 -% end -% end -% end -% return diameter[0] -% end - /max2 { dup % a b b 3 2 roll % b b a -- 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