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 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 30cdb0fab6ac66313d925f55769ece128b549ad4 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 10 Aug 2021 22:26:12 +0100 Subject: fixed - using walk - missed out an obvious ommission --- challenge-125/james-smith/perl/BinaryTree.pm | 19 +++++++------------ challenge-125/james-smith/perl/ch-2.pl | 27 ++++++++++++++++++++++++++- 2 files changed, 33 insertions(+), 13 deletions(-) diff --git a/challenge-125/james-smith/perl/BinaryTree.pm b/challenge-125/james-smith/perl/BinaryTree.pm index 1cbcbfc511..05703c9b26 100644 --- a/challenge-125/james-smith/perl/BinaryTree.pm +++ b/challenge-125/james-smith/perl/BinaryTree.pm @@ -32,18 +32,13 @@ sub depth { 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; + my $global = { 'diameter' => 0 }; + $self->walk( sub { + my $d = ($_[0]->has_left ? $_[0]->left->depth : 0 ) + + ($_[0]->has_right ? $_[0]->right->depth : 0 ); + $_[1]{'diameter'} = $d if $d > $_[1]->{'diameter'}; + }, $global ); + return $global->{'diameter'}; } sub value { diff --git a/challenge-125/james-smith/perl/ch-2.pl b/challenge-125/james-smith/perl/ch-2.pl index d4d2cb738d..71d510b253 100644 --- a/challenge-125/james-smith/perl/ch-2.pl +++ b/challenge-125/james-smith/perl/ch-2.pl @@ -72,6 +72,31 @@ $x->dump; say sprintf 'Max depth: %d, diameter %d', $x->depth, $x->diameter; say ''; +## 1 -> 2 -> 3 -> 4 -> 5 -> 6 +## `>10 `> 7 -> 8 -> 9 +## -------------------------- +## 9 -> 8 -> 7 -> 3 -> 4 -> 5 -> 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)->add_child_left( BinaryTree->new(9) ) + ) + ) + )->add_child_right( BinaryTree->new(10)) + ); + +say '4) 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 ''; + ## This time both child trees have depths longer than the number of ## ancestor nodes - so that is used to get the length... @@ -80,7 +105,7 @@ say ''; ## --------------------- ## 6 -> 5 -> 2 -> 3 -> 4 [ diameter 5 ] -say '4) Tree with node further down having two children - but distance from'; +say '5) 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( -- cgit From 851399b5d2e46d92aafc22871091dd4ac86f6cf8 Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Tue, 10 Aug 2021 23:32:55 +0100 Subject: Answers for challenge #125 (amended Tuesday evening) --- challenge-125/roger-bell-west/perl/ch-1.pl | 44 ++++++++++++++++++++ challenge-125/roger-bell-west/perl/ch-2.pl | 34 ++++++++++++++++ challenge-125/roger-bell-west/postscript/ch-2.ps | 48 ++++++++++++++++++++++ challenge-125/roger-bell-west/python/ch-1.py | 45 ++++++++++++++++++++ challenge-125/roger-bell-west/python/ch-2.py | 35 ++++++++++++++++ challenge-125/roger-bell-west/raku/ch-2.p6 | 32 +++++++++++++++ challenge-125/roger-bell-west/ruby/ch-1.rb | 51 +++++++++++++++++++++++ challenge-125/roger-bell-west/ruby/ch-2.rb | 39 ++++++++++++++++++ challenge-125/roger-bell-west/rust/ch-1.rs | 52 ++++++++++++++++++++++++ challenge-125/roger-bell-west/rust/ch-2.rs | 35 ++++++++++++++++ 10 files changed, 415 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 100644 challenge-125/roger-bell-west/postscript/ch-2.ps 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..0b7be33985 --- /dev/null +++ b/challenge-125/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,34 @@ +#! /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]),6,'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($depth[$a]+$depth[$b], + $diameter[$a], + $diameter[$b]); + } else { + $depth[$i]=1; + } + } + } + return $diameter[0]; +} 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..802e5c9dba --- /dev/null +++ b/challenge-125/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,48 @@ +%! no DSC + +/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 add + diameter a get + diameter b get + max2 max2 put + } { + depth 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 += 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..70df3a8337 --- /dev/null +++ b/challenge-125/roger-bell-west/python/ch-2.py @@ -0,0 +1,35 @@ +#! /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( + depth[a]+depth[b], + diameter[a], + diameter[b] + ) + else: + depth[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]),6,'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..ee5673dbc8 --- /dev/null +++ b/challenge-125/roger-bell-west/raku/ch-2.p6 @@ -0,0 +1,32 @@ +#! /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]),6,'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(@depth[$a]+@depth[$b], + @diameter[$a], + @diameter[$b]); + } else { + @depth[$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..dd58c18578 --- /dev/null +++ b/challenge-125/roger-bell-west/ruby/ch-2.rb @@ -0,0 +1,39 @@ +#! /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]=[ + depth[a]+depth[b], + diameter[a], + diameter[b], + ].max + else + depth[i]=1 + end + end + end + return diameter[0] +end + +require 'test/unit' + +class TestBtd < Test::Unit::TestCase + + def test_ex1 + assert_equal(6,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..b03513c684 --- /dev/null +++ b/challenge-125/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,35 @@ +#! /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 + ]),6); +} + +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]=*[ + depth[a]+depth[b], + diameter[a], + diameter[b] + ].iter().max().unwrap(); + } else { + depth[i]=1; + } + } + } + return diameter[0] +} -- cgit From 3160ed2946bd278c732873146f892ab4f80f8317 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Wed, 11 Aug 2021 09:23:30 +0100 Subject: - Added missing guest contributions by Laurent Rosenfeld. --- challenge-124/laurent-rosenfeld/go/ch-1.go | 12 ++++++++++++ challenge-124/laurent-rosenfeld/julia/ch-1.julia | 4 ++++ challenge-124/laurent-rosenfeld/nim/ch-1.nim | 4 ++++ 3 files changed, 20 insertions(+) create mode 100644 challenge-124/laurent-rosenfeld/go/ch-1.go create mode 100644 challenge-124/laurent-rosenfeld/julia/ch-1.julia create mode 100644 challenge-124/laurent-rosenfeld/nim/ch-1.nim diff --git a/challenge-124/laurent-rosenfeld/go/ch-1.go b/challenge-124/laurent-rosenfeld/go/ch-1.go new file mode 100644 index 0000000000..63ea60a848 --- /dev/null +++ b/challenge-124/laurent-rosenfeld/go/ch-1.go @@ -0,0 +1,12 @@ +package main +import "fmt" + +func main() { + lines := [5]string{" ^^^^^", " ^ ^", + " ^ ^", "^ ^", " ^"} + indexes := [18]int{0, 1, 2, 3, 3, 3, 3, 3, 3, 2, 1, 0, 4, 4, 4, 0, 4, 4} + + for i := 0; i < 18; i++ { + fmt.Printf("%s\n", lines[indexes[i]]) + } +} diff --git a/challenge-124/laurent-rosenfeld/julia/ch-1.julia b/challenge-124/laurent-rosenfeld/julia/ch-1.julia new file mode 100644 index 0000000000..6e89a46fd4 --- /dev/null +++ b/challenge-124/laurent-rosenfeld/julia/ch-1.julia @@ -0,0 +1,4 @@ +lines = [" ♀♀♀♀♀", " ♀ ♀", " ♀ ♀", "♀ ♀", " ♀"] +for i = [1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1, 5, 5, 5, 1, 5, 5] + println( lines[i] ) +end diff --git a/challenge-124/laurent-rosenfeld/nim/ch-1.nim b/challenge-124/laurent-rosenfeld/nim/ch-1.nim new file mode 100644 index 0000000000..be79490db0 --- /dev/null +++ b/challenge-124/laurent-rosenfeld/nim/ch-1.nim @@ -0,0 +1,4 @@ +let lines = [" #####", " # #", " # #", "# #", " #"] + +for i in [ 0, 1, 2, 3, 3, 3, 3, 3, 3, 2, 1, 0, 4, 4, 4, 0, 4, 4 ]: + echo lines[i] -- cgit From 835a0142c6c6c9ae6988c9417f6de38f9cd84df1 Mon Sep 17 00:00:00 2001 From: James Smith Date: Wed, 11 Aug 2021 09:27:47 +0100 Subject: Update README.md --- challenge-125/james-smith/README.md | 239 ++++-------------------------------- 1 file changed, 25 insertions(+), 214 deletions(-) diff --git a/challenge-125/james-smith/README.md b/challenge-125/james-smith/README.md index a639f2ace2..b363e138a8 100644 --- a/challenge-125/james-smith/README.md +++ b/challenge-125/james-smith/README.md @@ -1,4 +1,4 @@ -# Perl Weekly Challenge #124 +# Perl Weekly Challenge #125 You can find more information about this weeks, and previous weeks challenges at: @@ -10,233 +10,44 @@ 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-124/james-smith/perl +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-125/james-smith/perl -# Task 1 - Happy Women's Day +# Task 1 - Pythagorean Triples -***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 solution -We will first look at the symbol defined in the question... +# Task 2 - Binary Tree Diameter -``` - ^^^^^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^^^^^ - ^ - ^ - ^ - ^^^^^ - ^ - ^ -``` - -We note there are 3 types of rows: - - * Type I: a line of 5 symbols (centered) - * Type II: a single symbol in the middle of the row - * Type III: two symbols either side of the middle at a given distance. - -We encode these in an array -1 -> line of 5 symbols; 0 -> a single symbol at the centre; values > 0 - two points at the given distance away from the centre. The code becomes this: - -```perl -my @pts = qw(-1 3 4 5 5 5 5 5 4 3 -1 0 0 0 -1 0 0); -say $_ < 0 ? ' ^^^^^' - : !$_ ? ' ^' - : ' ' x (6-$_) . '^' . ' 'x($_*2-1) .'^' - foreach @pts; -``` - -### Now for a more generic solution! - -This symbol is just a circle and cross below. We can use trig to work out the points of the circle. To ensure we don't leave gaps we sweep the arcs away from the cardinal points (N,S,E,W) up to the ordinal points (NE,NW,SE,SW) - 8 different 45deg arcs. This way we just need to compute one point for each line and then compute the other co-ordinate using pythagorus' theorem. - -Why do we do this? If we just did 4 arcs of 90 degrees we would find that once we passed 45 degrees we would miss out points... - -Our process has 4 steps. - - 1. Create a blank canvas - 2. Draw the circle (note when we compute the y value we take half off the radius - this gives a better circle as we are tracing a line through the centre of the "squares"... - 3. Draw the cross - 4. Display the canvas... - -```perl -## Create the canvas.. -my @a = map { ' ' x ($radius*2+1) } 0..$radius*2+$cross; - -## Now we draw the circle... -foreach my $x (0 .. ceil($radius*0.71)) { - my $y = int sqrt( ($radius-.5)**2 - $x**2 ); - substr $a[ $radius - $x ],$radius-$y,1,'^'; - substr $a[ $radius + $x ],$radius-$y,1,'^'; - substr $a[ $radius - $x ],$radius+$y,1,'^'; - substr $a[ $radius + $x ],$radius+$y,1,'^'; - substr $a[ $radius - $y ],$radius-$x,1,'^'; - substr $a[ $radius + $y ],$radius-$x,1,'^'; - substr $a[ $radius - $y ],$radius+$x,1,'^'; - substr $a[ $radius + $y ],$radius+$x,1,'^'; -} - -## And the two parts of the cross... -substr $a[2*$radius+$_],$radius,1,'^' foreach 0..$cross; -substr $a[2*$radius+$cross/2],$radius-$cross/2,$cross+1,'^'x($cross+1); - -### Finally we render the canvas... -say $_ foreach @a; -``` - -Example output... -``` - ^^^^^^^^^ - ^^^ ^^^ - ^^ ^^ - ^^ ^^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^ ^ - ^^ ^^ - ^^ ^^ - ^^^ ^^^ - ^^^^^^^^^ - ^ - ^ - ^ - ^ - ^ - ^ - ^^^^^^^^^^^^^ - ^ - ^ - ^ - ^ - ^ - ^ -``` - -## Alternative languages - -As this was a script to generate an image - why not go back to learning languages after we had looked at CESIL, and visit the learning language of the 70s & 80s - LOGO. A graphic language where you drive a "turtle" around the screen. - -```logo -setpensize 4 -pendown - -;cross -back 300 -forward 150 -left 90 -forward 150 -back 300 -forward 150 -right 90 -forward 150 - -;circle -right 89 -repeat 180 [ - forward 10 - left 2 -] - -penup -``` - -You may ask why we only rotate right 89 to start the circle. If we start by rotating right then the circle will be off-set by "5" units to the right - we either have to do `right 90` `forward 5` `left 2` then `repeat` for `179`. And finish with another `right 5`. (This means the centre of one of the sides is at the top of the cross - or we can rotate the shape by 1 degree and have it stand on one of it's points) - -# Task 2 - Tug of War - -***You are given a set of `$n` integers `(n1, n2, n3, ...)`. 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`.*** +*** Write a script to find the diameter of the given binary tree. 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.*** ## Solution -We will use an iterative solution. We start by allocating person 1 to team 1, we then iterate down allocating each person to either team 1 or team 2. If either team gets too big we bomb out (this makes this solution more efficient than the non-iterative solution). As we go we keep a tally of the difference between the two teams weights. - -As we do a pre-allocation stage - we need to split the routine into two functions, the first function preps the data for interation and then handles the data at the end. The second does the interative step. +For any node - we can compute the longest tree which goes through the node itself - this is the sum of the maximum lengths of the left tree and the depth of the right. We do know that there will be trees for which this is not the diameter - there could be another node for which the left and right depths sum to a larger value... -At each step we need to know: - 1) What is the max-size of the group; - 2) Who is in team 1; - 3) Who is in team 2; - 4) What the difference in weight is; - 5) What is the smallest difference we have found; - 6) The weights of people left to be allocated. +So to compute the diameter of the tree we just choose the maximum value of the maximum lengths of the left/right sub tree. -So to start - we allocate person 1 to group 1, and set the difference to his weight. `$best` is an object to collect the information about the best allocation (the members of the two teams and the smallest difference)... +We will re-use the BinaryTree module from a previous challenge and so need to define walk functions to work out the maximum length of a subtree and consequently diameter... ```perl -sub match_teams { - my( $diff, @n ) = @_; - separate( 1 + int(@n/2), [$diff], [], $diff, my $best = [1e300], @n ); - return "Team 1: [@{$best->[1]}]; Team 2: [@{$best->[2]}]; difference $best->[0]"; +sub max_length { + my $self = shift; + my $d = 0; + $d = $self->left->max_length if $self->has_left; + return 1+$d unless $self->has_right; + my $t = $self->right->max_length; + return $t > $d ? 1+$t : 1+$d; } -sub separate { - my($maxsize,$team1,$team2,$diff,$be,@nums) = @_; - unless(@nums) { - @{$be} = ($team1, $team2, abs $diff) if $be->[0]>abs $diff; - return; - } - my $next = shift @nums; - separate( $maxsize, [@{$team1},$next], $team2, $diff+$next, $be, @nums ) if @{$team1} < $maxsize; - separate( $maxsize, $team1, [@{$team2},$next], $diff-$next, $be, @nums ) if @{$team2} < $maxsize; +sub diameter { + my $self = shift; + my $global = { 'diameter' => 0 }; + $self->walk( sub { + my $d = ($_[0]->has_left ? $_[0]->left->max_length : 0 ) + + ($_[0]->has_right ? $_[0]->right->max_length : 0 ); + $_[1]{'diameter'} = $d if $d > $_[1]->{'diameter'}; + }, $global ); + return $global->{'diameter'}; } ``` -### Notes: - * Notice the yoda inequality `$be->[0]>abs $diff` - it makes it clearer that you are only computing the absolute value of `$diff` not that of `$diff < $be->[0]`. - * `$team1` / `$team2` are refs - so when we update them we make copies `[@{$team2},$next]` rather than pushing to them. - * We keep the running total as it avoids the need to do the sum each time. - -### Timings - -| players | rate/time | -| ------- | --------: | -| 10 | 2,273/s | -| 12 | 598/s | -| 14 | 157/s | -| 16 | 41/s | -| 18 | 10/s | -| 20 | 2.68/s | -| 22 | 0.57/s | -| 24 | ~ 6s | -| 26 | ~ 23s | -| 28 | ~ 94s | -| 30 | ~ 365s | - -``` -- cgit From 5c61733c64454ff8d9bbd87f30a8d06284d49cf3 Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Wed, 11 Aug 2021 10:34:56 +0100 Subject: Blog post for challenge #125 --- challenge-125/roger-bell-west/blog.txt | 1 + 1 file changed, 1 insertion(+) create mode 100644 challenge-125/roger-bell-west/blog.txt diff --git a/challenge-125/roger-bell-west/blog.txt b/challenge-125/roger-bell-west/blog.txt new file mode 100644 index 0000000000..533245870e --- /dev/null +++ b/challenge-125/roger-bell-west/blog.txt @@ -0,0 +1 @@ +https://blog.firedrake.org/archive/2021/08/Perl_Weekly_Challenge_125__Pythagorean_Diameter.html -- cgit From 5c01e5e636203aa19e363b240e9d224b621571b4 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Wed, 11 Aug 2021 20:36:05 +0100 Subject: - Added solutions by Roger Bell_West. --- stats/pwc-challenge-124.json | 567 ++++ stats/pwc-current.json | 568 +--- stats/pwc-language-breakdown-summary.json | 86 +- stats/pwc-language-breakdown.json | 4933 +++++++++++++++-------------- stats/pwc-leaders.json | 766 ++--- stats/pwc-summary-1-30.json | 96 +- stats/pwc-summary-121-150.json | 112 +- stats/pwc-summary-151-180.json | 104 +- stats/pwc-summary-181-210.json | 110 +- stats/pwc-summary-211-240.json | 100 +- stats/pwc-summary-31-60.json | 102 +- stats/pwc-summary-61-90.json | 114 +- stats/pwc-summary-91-120.json | 30 +- stats/pwc-summary.json | 542 ++-- 14 files changed, 4162 insertions(+), 4068 deletions(-) create mode 100644 stats/pwc-challenge-124.json diff --git a/stats/pwc-challenge-124.json b/stats/pwc-challenge-124.json new file mode 100644 index 0000000000..e206671a14 --- /dev/null +++ b/stats/pwc-challenge-124.json @@ -0,0 +1,567 @@ +{ + "chart" : { + "type" : "column" + }, + "xAxis" : { + "type" : "category" + }, + "drilldown" : { + "series" : [ + { + "id" : "Abigail", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Blog", + 2 + ] + ], + "name" : "Abigail" + }, + { + "id" : "Arne Sommer", + "name" : "Arne Sommer", + "data" : [ + [ + "Raku", + 2 + ], + [ + "Blog", + 1 + ] + ] + }, + { + "id" : "Bruce Gray", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Raku", + 2 + ] + ], + "name" : "Bruce Gray" + }, + { + "data" : [ + [ + "Perl", + 1 + ] + ], + "name" : "Cheok-Yin Fung", + "id" : "Cheok-Yin Fung" + }, + { + "name" : "Colin Crain", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Raku", + 1 + ], + [ + "Blog", + 1 + ] + ], + "id" : "Colin Crain" + }, + { + "name" : "Dave Jacoby", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Blog", + 1 + ] + ], + "id" : "Dave Jacoby" + }, + { + "id" : "Duncan C. White", + "name" : "Duncan C. White", + "data" : [ + [ + "Perl", + 2 + ] + ] + }, + { + "id" : "E. Choroba", + "data" : [ + [ + "Perl", + 2 + ] + ], + "name" : "E. Choroba" + }, + { + "data" : [ + [ + "Perl", + 2 + ], + [ + "Raku", + 2 + ], + [ + "Blog", + 2 + ] + ], + "name" : "Flavio Poletti", + "id" : "Flavio Poletti" + }, + { + "id" : "Jaldhar H. Vyas", + "name" : "Jaldhar H. Vyas", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Raku", + 2 + ], + [ + "Blog", + 1 + ] + ] + }, + { + "name" : "James Smith", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Blog", + 1 + ] + ], + "id" : "James Smith" + }, + { + "id" : "Jan Krnavek", + "name" : "Jan Krnavek", + "data" : [ + [ + "Raku", + 1 + ] + ] + }, + { + "id" : "Jared Martin", + "name" : "Jared Martin", + "data" : [ + [ + "Perl", + 1 + ], + [ + "Blog", + 1 + ] + ] + }, + { + "id" : "Jorg Sommrey", + "name" : "Jorg Sommrey", + "data" : [ + [ + "Perl", + 2 + ] + ] + }, + { + "data" : [ + [ + "Perl", + 2 + ] + ], + "name" : "kjetillll", + "id" : "kjetillll" + }, + { + "id" : "Laurent Rosenfeld", + "name" : "Laurent Rosenfeld", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Raku", + 2 + ], + [ + "Blog", + 1 + ] + ] + }, + { + "data" : [ + [ + "Raku", + 2 + ], + [ + "Blog", + 2 + ] + ], + "name" : "Luca Ferrari", + "id" : "Luca Ferrari" + }, + { + "id" : "Mark Anderson", + "name" : "Mark Anderson", + "dat