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 4d42c4dcace76e2674662bc863116ac638cc5b8e Mon Sep 17 00:00:00 2001 From: Dave Jacoby Date: Mon, 9 Aug 2021 16:14:01 -0400 Subject: Trees && Triples --- challenge-125/dave-jacoby/blog.txt | 1 + challenge-125/dave-jacoby/perl/ch-1.pl | 86 ++++++++++++++++ challenge-125/dave-jacoby/perl/ch-2.pl | 174 +++++++++++++++++++++++++++++++++ 3 files changed, 261 insertions(+) create mode 100644 challenge-125/dave-jacoby/blog.txt create mode 100644 challenge-125/dave-jacoby/perl/ch-1.pl create mode 100644 challenge-125/dave-jacoby/perl/ch-2.pl diff --git a/challenge-125/dave-jacoby/blog.txt b/challenge-125/dave-jacoby/blog.txt new file mode 100644 index 0000000000..0a0ccddd87 --- /dev/null +++ b/challenge-125/dave-jacoby/blog.txt @@ -0,0 +1 @@ +https://jacoby.github.io/2021/08/09/trees-and-triples-the-perl-weekly-challenge-125.html diff --git a/challenge-125/dave-jacoby/perl/ch-1.pl b/challenge-125/dave-jacoby/perl/ch-1.pl new file mode 100644 index 0000000000..717d608a68 --- /dev/null +++ b/challenge-125/dave-jacoby/perl/ch-1.pl @@ -0,0 +1,86 @@ +#!/usr/bin/env perl + +use feature qw{say state signatures}; +use strict; +use warnings; +use utf8; +no warnings qw{ experimental }; + +use List::Util qw{ uniq }; +use JSON; +use Carp; +use Getopt::Long; +my $json = JSON->new->canonical->space_after; + +my $n = 5; +GetOptions( 'n=i' => \$n, ); + +carp 'out of range' if $n <= 0; + +my $p = pythagorean_triples($n); +say <<"END"; + + INPUT: $n + OUTPUT: $p + +END + +sub pythagorean_triples( $n ) { + my @output; + push @output, pt_a($n); + push @output, pt_c($n); + @output = sort grep { defined } @output; + return join ", ", @output if @output; + return -1; +} + +sub pt_a ($n ) { + my @output; + my $n2 = $n**2; + + for my $b1 ( 1 .. $n2 ) { + my $b2 = $b1**2; + my $c2 = $n2 + $b2; + my $c = sqrt $c2; + next unless int $c == $c; + my @x = sort { $a <=> $b } map { int $_ } $n, $b1, $c; + push @output, $json->encode( \@x ); + } + return uniq @output if @output; + return undef; +} + +sub pt_c ($n ) { + my @output; + my $n2 = $n**2; + + for my $b1 ( 1 .. $n2 ) { + my $b2 = $b1**2; + my $a2 = $n2 - $b2; + next unless $a2 > 0; + my $a1 = sqrt $a2; + next unless int $a1 == $a1; + my @x = sort { $a <=> $b } map { int $_ } $n, $b1, $a1; + push @output, $json->encode( \@x ); + } + return uniq @output if @output; + return undef; + + # my @output; + # my $n2 = $n**2; + + # for my $a1 ( 1 .. $n2 ) { + # my $a2 = $a1**2; + # for my $b1 ( 1 .. $n2 ) { + # my $b2 = $b1**2; + # my $c2 = $a2 + $b2; + # next if $c2 > $n2; + # if ( $n2 == $c2 ) { + # my @x = sort { $a <=> $b } map { int $_ } $a1, $b1, $n; + # push @output, $json->encode( \@x ); + # } + # } + # } + # return uniq @output if @output; + # return undef; +} diff --git a/challenge-125/dave-jacoby/perl/ch-2.pl b/challenge-125/dave-jacoby/perl/ch-2.pl new file mode 100644 index 0000000000..b6e5e97817 --- /dev/null +++ b/challenge-125/dave-jacoby/perl/ch-2.pl @@ -0,0 +1,174 @@ +#!/usr/bin/env perl + +use feature qw{say state signatures}; +use strict; +use warnings; +use utf8; +no warnings qw{ experimental }; + +use List::Util qw{ max }; +use JSON; +my $json = JSON->new->space_after->canonical; + +my %nodes; +for my $n ( 1 .. 10 ) { + my $node = Node->new($n); + $nodes{$n} = $node; +} + +$nodes{1}->left( $nodes{2} ); +$nodes{1}->right( $nodes{5} ); +$nodes{2}->left( $nodes{3} ); +$nodes{2}->right( $nodes{4} ); +$nodes{5}->left( $nodes{6} ); +$nodes{5}->right( $nodes{7} ); +$nodes{7}->left( $nodes{8} ); +$nodes{7}->right( $nodes{10} ); +$nodes{8}->left( $nodes{9} ); + +my @diameters; +for my $node ( sort values %nodes ) { + my $v = $node->value(); + my $l = $node->is_leaf(); + push @diameters, btd($node) if $l; +} + +my $max = max map { scalar $_->@* } @diameters; +my $done; + +@diameters = + grep { + my $s1 = join ' ', $_->@*; + my $s2 = join ' ', reverse $_->@*; + $done->{$s1}++; + $done->{$s2}++; + $done->{$s1} < 2; + } + grep { scalar $_->@* == $max } + sort { scalar $b->@* <=> scalar $a->@* } @diameters; + +say join "\n", map { join " ", ( scalar $_->@* ), ':', $_->@* } + + @diameters; + +sub btd ( $node, $path = [] ) { + my @output; + my $v = $node->value(); + push $path->@*, $v; + + my @options; + if ( defined $node->parent() ) { + my $p = $node->parent(); + my $pv = $p->value(); + my $is = grep /$pv/, $path->@* ? 1 : 0; + if ( !grep /$pv/, $path->@* ) { + push @options, 'parent'; + } + } + if ( defined $node->left() ) { + my $p = $node->left(); + my $pv = $p->value(); + my $is = grep /$pv/, $path->@* ? 1 : 0; + if ( !grep /$pv/, $path->@* ) { + push @options, 'left'; + } + } + if ( defined $node->right() ) { + my $p = $node->right(); + my $pv = $p->value(); + my $is = grep /$pv/, $path->@* ? 1 : 0; + if ( !grep /$pv/, $path->@* ) { + push @options, 'right'; + } + } + + if (@options) { + for my $option (@options) { + if ( $option eq 'parent' ) { + my $p = $node->parent(); + my $path2->@* = map { int } $path->@*; + push @output, btd( $p, $path2 ); + } + if ( $option eq 'left' ) { + my $p = $node->left(); + my $path2->@* = map { int } $path->@*; + push @output, btd( $p, $path2 ); + } + if ( $option eq 'right' ) { + my $p = $node->right(); + my $path2->@* = map { int } $path->@*; + push @output, btd( $p, $path2 ); + } + } + } + else { + push @output, [ map { int } $path->@* ]; + } + + return @output; +} + +package Node; + +sub new ( $class, $value = 0 ) { + my $self = {}; + $self->{value} = $value; + $self->{left} = undef; + $self->{right} = undef; + $self->{horizontal} = undef; + $self->{parent} = undef; + return bless $self, $class; +} + +sub value ( $self, $value = undef ) { + if ( defined $value ) { + $self->{value} = $value; + } + else { + return $self->{value}; + } +} + +sub is_root ( $self ) { + return defined $self->{parent} ? 0 : 1; +} + +sub is_leaf ( $self ) { + return ( !defined $self->{left} && !defined $self->{right} ) + ? 1 + : 0; +} + +sub left ( $self, $node = undef ) { + if ( defined $node ) { + $self->{left} = $node; + $node->{parent} = $self; + } + else { + return $self->{left}; + } +} + +sub right ( $self, $node = undef ) { + if ( defined $node ) { + $self->{right} = $node; + $node->{parent} = $self; + } + else { + return $self->{right}; + } +} + +sub horizontal ( $self, $node = undef ) { + if ( defined $node ) { + $self->{horizontal} = $node; + $node->{parent} = $self; + } + else { + return $self->{horizontal}; + } +} + +sub parent ($self ) { + return $self->{parent}; +} -- cgit From 3b86d11379632b17ca5328d8b92756e4950f0bfc Mon Sep 17 00:00:00 2001 From: Abigail Date: Tue, 10 Aug 2021 01:15:28 +0200 Subject: Tests for week 125, part 1 --- challenge-125/abigail/t/ctest.ini | 10 + challenge-125/abigail/t/input-1-1 | 3 + challenge-125/abigail/t/input-1-2 | 2 + challenge-125/abigail/t/input-1-3 | 98 +++++++++ challenge-125/abigail/t/input-1-4 | 143 ++++++++++++ challenge-125/abigail/t/output-1-1.exp | 5 + challenge-125/abigail/t/output-1-2.exp | 2 + challenge-125/abigail/t/output-1-3.exp | 391 +++++++++++++++++++++++++++++++++ challenge-125/abigail/t/output-1-4.exp | 212 ++++++++++++++++++ 9 files changed, 866 insertions(+) create mode 100644 challenge-125/abigail/t/ctest.ini create mode 100644 challenge-125/abigail/t/input-1-1 create mode 100644 challenge-125/abigail/t/input-1-2 create mode 100644 challenge-125/abigail/t/input-1-3 create mode 100644 challenge-125/abigail/t/input-1-4 create mode 100644 challenge-125/abigail/t/output-1-1.exp create mode 100644 challenge-125/abigail/t/output-1-2.exp create mode 100644 challenge-125/abigail/t/output-1-3.exp create mode 100644 challenge-125/abigail/t/output-1-4.exp diff --git a/challenge-125/abigail/t/ctest.ini b/challenge-125/abigail/t/ctest.ini new file mode 100644 index 0000000000..44057cf8e4 --- /dev/null +++ b/challenge-125/abigail/t/ctest.ini @@ -0,0 +1,10 @@ +# +# Configuration file for running tests, using ctest. +# See https://github.com/Abigail/Misc/blob/master/ctest +# + +[names] +1-1 = Given examples +1-2 = No solutions +1-3 = Up to 100 +1-4 = Primes up to 1000 diff --git a/challenge-125/abigail/t/input-1-1 b/challenge-125/abigail/t/input-1-1 new file mode 100644 index 0000000000..48685feaae --- /dev/null +++ b/challenge-125/abigail/t/input-1-1 @@ -0,0 +1,3 @@ +5 +13 +1 diff --git a/challenge-125/abigail/t/input-1-2 b/challenge-125/abigail/t/input-1-2 new file mode 100644 index 0000000000..1191247b6d --- /dev/null +++ b/challenge-125/abigail/t/input-1-2 @@ -0,0 +1,2 @@ +1 +2 diff --git a/challenge-125/abigail/t/input-1-3 b/challenge-125/abigail/t/input-1-3 new file mode 100644 index 0000000000..3758ba5b23 --- /dev/null +++ b/challenge-125/abigail/t/input-1-3 @@ -0,0 +1,98 @@ +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15 +16 +17 +18 +19 +20 +21 +22 +23 +24 +25 +26 +27 +28 +29 +30 +31 +32 +33 +34 +35 +36 +37 +38 +39 +40 +41 +42 +43 +44 +45 +46 +47 +48 +49 +50 +51 +52 +53 +54 +55 +56 +57 +58 +59 +60 +61 +62 +63 +64 +65 +66 +67 +68 +69 +70 +71 +72 +73 +74 +75 +76 +77 +78 +79 +80 +81 +82 +83 +84 +85 +86 +87 +88 +89 +90 +91 +92 +93 +94 +95 +96 +97 +98 +99 +100 diff --git a/challenge-125/abigail/t/input-1-4 b/challenge-125/abigail/t/input-1-4 new file mode 100644 index 0000000000..0aa2bff2b8 --- /dev/null +++ b/challenge-125/abigail/t/input-1-4 @@ -0,0 +1,143 @@ +101 +103 +107 +109 +113 +127 +131 +137 +139 +149 +151 +157 +163 +167 +173 +179 +181 +191 +193 +197 +199 +211 +223 +227 +229 +233 +239 +241 +251 +257 +263 +269 +271 +277 +281 +283 +293 +307 +311 +313 +317 +331 +337 +347 +349 +353 +359 +367 +373 +379 +383 +389 +397 +401 +409 +419 +421 +431 +433 +439 +443 +449 +457 +461 +463 +467 +479 +487 +491 +499 +503 +509 +521 +523 +541 +547 +557 +563 +569 +571 +577 +587 +593 +599 +601 +607 +613 +617 +619 +631 +641 +643 +647 +653 +659 +661 +673 +677 +683 +691 +701 +709 +719 +727 +733 +739 +743 +751 +757 +761 +769 +773 +787 +797 +809 +811 +821 +823 +827 +829 +839 +853 +857 +859 +863 +877 +881 +883 +887 +907 +911 +919 +929 +937 +941 +947 +953 +967 +971 +977 +983 +991 +997 diff --git a/challenge-125/abigail/t/output-1-1.exp b/challenge-125/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..c81387014a --- /dev/null +++ b/challenge-125/abigail/t/output-1-1.exp @@ -0,0 +1,5 @@ +5 12 13 +3 4 5 +13 84 85 +5 12 13 +-1 diff --git a/challenge-125/abigail/t/output-1-2.exp b/challenge-125/abigail/t/output-1-2.exp new file mode 100644 index 0000000000..343ee5c2f6 --- /dev/null +++ b/challenge-125/abigail/t/output-1-2.exp @@ -0,0 +1,2 @@ +-1 +-1 diff --git a/challenge-125/abigail/t/output-1-3.exp b/challenge-125/abigail/t/output-1-3.exp new file mode 100644 index 0000000000..d1717d0529 --- /dev/null +++ b/challenge-125/abigail/t/output-1-3.exp @@ -0,0 +1,391 @@ +3 4 5 +4 3 5 +5 12 13 +3 4 5 +6 8 10 +7 24 25 +8 6 10 +8 15 17 +9 12 15 +9 40 41 +10 24 26 +6 8 10 +11 60 61 +12 5 13 +12 9 15 +12 16 20 +12 35 37 +13 84 85 +5 12 13 +14 48 50 +15 8 17 +15 20 25 +15 36 39 +15 112 113 +9 12 15 +16 12 20 +16 30 34 +16 63 65 +17 144 145 +8 15 17 +18 24 30 +18 80 82 +19 180 181 +20 15 25 +20 21 29 +20 48 52 +20 99 101 +12 16 20 +21 20 29 +21 28 35 +21 72 75 +21 220 221 +22 120 122 +23 264 265 +24 7 25 +24 10 26 +24 18 30 +24 32 40 +24 45 51 +24 70 74 +24 143 145 +25 60 65 +25 312 313 +7 24 25 +15 20 25 +26 168 170 +10 24 26 +27 36 45 +27 120 123 +27 364 365 +28 21 35 +28 45 53 +28 96 100 +28 195 197 +29 420 421 +20 21 29 +30 16 34 +30 40 50 +30 72 78 +30 224 226 +18 24 30 +31 480 481 +32 24 40 +32 60 68 +32 126 130 +32 255 257 +33 44 55 +33 56 65 +33 180 183 +33 544 545 +34 288 290 +16 30 34 +35 12 37 +35 84 91 +35 120 125 +35 612 613 +21 28 35 +36 15 39 +36 27 45 +36 48 60 +36 77 85 +36 105 111 +36 160 164 +36 323 325 +37 684 685 +12 35 37 +38 360 362 +39 52 65 +39 80 89 +39 252 255 +39 760 761 +15 36 39 +40 9 41 +40 30 50 +40 42 58 +40 75 85 +40 96 104 +40 198 202 +40 399 401 +24 32 40 +41 840 841 +9 40 41 +42 40 58 +42 56 70 +42 144 150 +42 440 442 +43 924 925 +44 33 55 +44 117 125 +44 240 244 +44 483 485 +45 24 51 +45 28 53 +45 60 75 +45 108 117 +45 200 205 +45 336 339 +45 1012 1013 +27 36 45 +46 528 530 +47 1104 1105 +48 14 50 +48 20 52 +48 36 60 +48 55 73 +48 64 80 +48 90 102 +48 140 148 +48 189 195 +48 286 290 +48 575 577 +49 168 175 +49 1200 1201 +50 120 130 +50 624 626 +14 48 50 +30 40 50 +51 68 85 +51 140 149 +51 432 435 +51 1300 1301 +24 45 51 +52 39 65 +52 165 173 +52 336 340 +52 675 677 +20 48 52 +53 1404 1405 +28 45 53 +54 72 90 +54 240 246 +54 728 730 +55 48 73 +55 132 143 +55 300 305 +55 1512 1513 +33 44 55 +56 33 65 +56 42 70 +56 90 106 +56 105 119 +56 192 200 +56 390 394 +56 783 785 +57 76 95 +57 176 185 +57 540 543 +57 1624 1625 +58 840 842 +40 42 58 +59 1740 1741 +60 11 61 +60 25 65 +60 32 68 +60 45 75 +60 63 87 +60 80 100 +60 91 109 +60 144 156 +60 175 185 +60 221 229 +60 297 303 +60 448 452 +60 899 901 +36 48 60 +61 1860 1861 +11 60 61 +62 960 962 +63 16 65 +63 60 87 +63 84 105 +63 216 225 +63 280 287 +63 660 663 +63 1984 1985 +64 48 80 +64 120 136 +64 252 260 +64 510 514 +64 1023 1025 +65 72 97 +65 156 169 +65 420 425 +65 2112 2113 +16 63 65 +25 60 65 +33 56 65 +39 52 65 +66 88 110 +66 112 130 +66 360 366 +66 1088 1090 +67 2244 2245 +68 51 85 +68 285 293 +68 576 580 +68 1155 1157 +32 60 68 +69 92 115 +69 260 269 +69 792 795 +69 2380 2381 +70 24 74 +70 168 182 +70 240 250 +70 1224 1226 +42 56 70 +71 2520 2521 +72 21 75 +72 30 78 +72 54 90 +72 65 97 +72 96 120 +72 135 153 +72 154 170 +72 210 222 +72 320 328 +72 429 435 +72 646 650 +72 1295 1297 +73 2664 2665 +48 55 73 +74 1368 1370 +24 70 74 +75 40 85 +75 100 125 +75 180 195 +75 308 317 +75 560 565 +75 936 939 +75 2812 2813 +21 72 75 +45 60 75 +76 57 95 +76 357 365 +76 720 724 +76 1443 1445 +77 36 85 +77 264 275 +77 420 427 +77 2964 2965 +78 104 130 +78 160 178 +78 504 510 +78 1520 1522 +30 72 78 +79 3120 3121 +80 18 82 +80 39 89 +80 60 100 +80 84 116 +80 150 170 +80 192 208 +80 315 325 +80 396 404 +80 798 802 +80 1599 1601 +48 64 80 +81 108 135 +81 360 369 +81 1092 1095 +81 3280 3281 +82 1680 1682 +18 80 82 +83 3444 3445 +84 13 85 +84 35 91 +84 63 105 +84 80 116 +84 112 140 +84 135 159 +84 187 205 +84 245 259 +84 288 300 +84 437 445 +84 585 591 +84 880 884 +84 1763 1765 +85 132 157 +85 204 221 +85 720 725 +85 3612 3613 +13 84 85 +36 77 85 +40 75 85 +51 68 85 +86 1848 1850 +87 116 145 +87 416 425 +87 1260 1263 +87 3784 3785 +60 63 87 +88 66 110 +88 105 137 +88 165 187 +88 234 250 +88 480 488 +88 966 970 +88 1935 1937 +89 3960 3961 +39 80 89 +90 48 102 +90 56 106 +90 120 150 +90 216 234 +90 400 410 +90 672 678 +90 2024 2026 +54 72 90 +91 60 109 +91 312 325 +91 588 595 +91 4140 4141 +35 84 91 +92 69 115 +92 525 533 +92 1056 1060 +92 2115 2117 +93 124 155 +93 476 485 +93 1440 1443 +93 4324 4325 +94 2208 2210 +95 168 193 +95 228 247 +95 900 905 +95 4512 4513 +57 76 95 +96 28 100 +96 40 104 +96 72 120 +96 110 146 +96 128 160 +96 180 204 +96 247 265 +96 280 296 +96 378 390 +96 572 580 +96 765 771 +96 1150 1154 +96 2303 2305 +97 4704 4705 +65 72 97 +98 336 350 +98 2400 2402 +99 20 101 +99 132 165 +99 168 195 +99 440 451 +99 540 549 +99 1632 1635 +99 4900 4901 +100 75 125 +100 105 145 +100 240 260 +100 495 505 +100 621 629 +100 1248 1252 +100 2499 2501 +28 96 100 +60 80 100 diff --git a/challenge-125/abigail/t/output-1-4.exp b/challenge-125/abigail/t/output-1-4.exp new file mode 100644 index 0000000000..1038f1ac74 --- /dev/null +++ b/challenge-125/abigail/t/output-1-4.exp @@ -0,0 +1,212 @@ +101 5100 5101 +20 99 101 +103 5304 5305 +107 5724 5725 +109 5940 5941 +60 91 109 +113 6384 6385 +15 112 113 +127 8064 8065 +131 8580 8581 +137 9384 9385 +88 105 137 +139 9660 9661 +149 11100 11101 +51 140 149 +151 11400 11401 +157 12324 12325 +85 132 157 +163 13284 13285 +167 13944 13945 +173 14964 14965 +52 165 173 +179 16020 16021 +181 16380 16381 +19 180 181 +191 18240 18241 +193 18624 18625 +95 168 193 +197 19404 19405 +28 195 197 +199 19800 19801 +211 22260 22261 +223 24864 24865 +227 25764 25765 +229 26220 26221 +60 221 229 +233 27144 27145 +105 208 233 +239 28560 28561 +241 29040 29041 +120 209 241 +251 31500 31501 +257 33024 33025 +32 255 257 +263 34584 34585 +269 36180 36181 +69 260 269 +271 36720 36721 +277 38364 38365 +115 252 277 +281 39480 39481 +160 231 281 +283 40044 40045 +293 42924 42925 +68 285 293 +307 47124 47125 +311 48360 48361 +313 48984 48985 +25 312 313 +317 50244 50245 +75 308 317 +331 54780 54781 +337 56784 56785 +175 288 337 +347 60204 60205 +349 60900 60901 +180 299 349 +353 62304 62305 +225 272 353 +359 64440 64441 +367 67344 67345 +373 69564 69565 +252 275 373 +379 71820 71821 +383 73344 73345 +389 75660 75661 +189 340 389 +397 78804 78805 +228 325 397 +401 80400 80401 +40 399 401 +409 83640 83641 +120 391 409 +419 87780 87781 +421 88620 88621 +29 420 421 +431 92880 92881 +433 93744 93745 +145 408 433 +439 96360 96361 +443 98124 98125 +449 100800 100801 +280 351 449 +457 104424 104425 +168 425 457 +461 106260 106261 +261 380 461 +463 107184 107185 +467 109044 109045 +479 114720 114721 +487 118584 118585 +491 120540 120541 +499 124500 124501 +503 126504 126505 +509 129540 129541 +220 459 509 +521 135720 135721 +279 440 521 +523 136764 136765 +541 146340 146341 +341 420 541 +547 149604 149605 +557 155124 155125 +165 532 557 +563 158484 158485 +569 161880 161881 +231 520 569 +571 163020 163021 +577 166464 166465 +48 575 577 +587 172284 172285 +593 175824 175825 +368 465 593 +599 179400 179401 +601 180600 180601 +240 551 601 +607 184224 184225 +613 187884 187885 +35 612 613 +617 190344 190345 +105 608 617 +619 191580 191581 +631 199080 199081 +641 205440 205441 +200 609 641 +643 206724 206725 +647 209304 209305 +653 213204 213205 +315 572 653 +659 217140 217141 +661 218460 218461 +300 589 661 +673 226464 226465 +385 552 673 +677 229164 229165 +52 675 677 +683 233244 233245 +691 238740 238741 +701 245700 245701 +260 651 701 +709 251340 251341 +259 660 709 +719 258480 258481 +727 264264 264265 +733 268644 268645 +108 725 733 +739 273060 273061 +743 276024 276025 +751 282000 282001 +757 286524 286525 +468 595 757 +761 289560 289561 +39 760 761 +769 295680 295681 +481 600 769 +773 298764 298765 +195 748 773 +787 309684 309685 +797 317604 317605 +555 572 797 +809 327240 327241 +280 759 809 +811 328860 328861 +821 337020 337021 +429 700 821 +823 338664 338665 +827 341964 341965 +829 343620 343621 +540 629 829 +839 351960 351961 +853 363804 363805 +205 828 853 +857 367224 367225 +232 825 857 +859 368940 368941 +863 372384 372385 +877 384564 384565 +348 805 877 +881 388080 388081 +369 800 881 +883 389844 389845 +887 393384 393385 +907 411324 411325 +911 414960 414961 +919 422280 422281 +929 431520 431521 +129 920 929 +937 438984 438985 +215 912 937 +941 442740 442741 +580 741 941 +947 448404 448405 +953 454104 454105 +615 728 953 +967 467544 467545 +971 471420 471421 +977 477264 477265 +248 945 977 +983 483144 483145 +991 491040 491041 +997 497004 497005 +372 925 997 -- cgit From c976e26a845911cf0226844acfc1e4c0e497c8c1 Mon Sep 17 00:00:00 2001 From: Scimon Date: Tue, 10 Aug 2021 17:16:20 +0100 Subject: Updatred based on changed definition --- challenge-125/simon-proctor/raku/ch-2.raku | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-125/simon-proctor/raku/ch-2.raku b/challenge-125/simon-proctor/raku/ch-2.raku index 2ab4173e5a..45a70774c7 100644 --- a/challenge-125/simon-proctor/raku/ch-2.raku +++ b/challenge-125/simon-proctor/raku/ch-2.raku @@ -146,10 +146,10 @@ multi sub MAIN( *@data ) { say $tree; my $long = shift @routes; - my $result = $long.elems; + my $result = $long.elems - 1; for @routes -> $pos { if ($long (&) $pos).elems == 1 { - $result = $long.elems + $pos.elems - 1; + $result = $long.elems + $pos.elems - 2; last; } } -- cgit From 9fc9a8a98be3336fb1bd9fb909c68af45186744e Mon Sep 17 00:00:00 2001 From: Abigail Date: Wed, 11 Aug 2021 00:33:29 +0200 Subject: Solutions in 6 languages for week 125, part 1 --- challenge-125/abigail/README.md | 23 ------------ challenge-125/abigail/c/ch-1.c | 52 +++++++++++++++++++++++++++ challenge-125/abigail/lua/ch-1.lua | 48 +++++++++++++++++++++++++ challenge-125/abigail/node/ch-1.js | 47 ++++++++++++++++++++++++ challenge-125/abigail/perl/ch-1.pl | 69 ++++++++++++++++++++++++++++++++++++ challenge-125/abigail/python/ch-1.py | 41 +++++++++++++++++++++ challenge-125/abigail/ruby/ch-1.rb | 45 +++++++++++++++++++++++ 7 files changed, 302 insertions(+), 23 deletions(-) create mode 100644 challenge-125/abigail/c/ch-1.c create mode 100644 challenge-125/abigail/lua/ch-1.lua create mode 100644 challenge-125/abigail/node/ch-1.js create mode 100644 challenge-125/abigail/perl/ch-1.pl create mode 100644 challenge-125/abigail/python/ch-1.py create mode 100644 challenge-125/abigail/ruby/ch-1.rb diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index 155bfc8302..f8c6f2595b 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -29,35 +29,12 @@ Output: -1 ~~~~ ### Solutions -* [AWK](awk/ch-1.awk) -* [Bash](bash/ch-1.sh) -* [Basic](basic/ch-1.bas) -* [bc](bc/ch-1.bc) -* [Befunge-93](befunge-93/ch-1.bf93) * [C](c/ch-1.c) -* [Cobol](cobol/ch-1.cb) -* [Csh](csh/ch-1.csh) -* [Erlang](erlang/ch-1.erl) -* [Forth](forth/ch-1.fs) -* [Fortran](fortran/ch-1.f90) -* [Go](go/ch-1.go) -* [Java](java/ch-1.java) * [Lua](lua/ch-1.lua) -* [m4](m4/ch-1.m4) -* [MMIX](mmix/ch-1.mms) * [Node.js](node/ch-1.js) -* [Ocaml](ocaml/ch-1.ml) -* [Pascal](pascal/ch-1.p) * [Perl](perl/ch-1.pl) -* [Php](php/ch-1.php) -* [Postscript](postscript/ch-1.ps) * [Python](python/ch-1.py) -* [R](r/ch-1.r) -* [Rexx](rexx/ch-1.rexx) * [Ruby](ruby/ch-1.rb) -* [Scheme](scheme/ch-1.scm) -* [SQL](sql/ch-1.sql) -* [Tcl](tcl/ch-1.tcl) ### Blog [Perl Weekly Challenge 125: Pythagorean Triples][blog1] diff --git a/challenge-125/abigail/c/ch-1.c b/challenge-125/abigail/c/ch-1.c new file mode 100644 index 0000000000..63b3a67db1 --- /dev/null +++ b/challenge-125/abigail/c/ch-1.c @@ -0,0 +1,52 @@ +# include +# include +# include +# include + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file + */ + +typedef long long number; + +number introot (number square) { + return ((number) floorl (.4 + sqrt (square))); +} + +int main (void) { + number n; + + while (scanf ("%lld", &n) == 1) { + if (n <= 2) { + printf ("-1\n"); + continue; + } + + number n_sq = n * n; + number c = n + 1; + number c_sq = n_sq + 2 * n + 1; + while (2 * c - 1 <= n_sq) { + number b_sq = c_sq - n_sq; + number b = introot (b_sq); + if (b_sq == b * b) { + printf ("%lld %lld %lld\n", n, b, c); + } + c_sq += 2 * c ++ + 1; + } + + number max_a = (number) floorl (n / sqrt (2)); + for (number a = 3; a <= max_a; a ++) { + number b_sq = n_sq - a * a; + number b = introot (b_sq); + if (b_sq == b * b) { + printf ("%lld %lld %lld\n", a, b, n); + } + } + } + + return (0); +} diff --git a/challenge-125/abigail/lua/ch-1.lua b/challenge-125/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..1a0efb40c8 --- /dev/null +++ b/challenge-125/abigail/lua/ch-1.lua @@ -0,0 +1,48 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-1.lua < input-file +-- + +function introot (square) + return (math . floor (.4 + math . sqrt (square))) +end + + +for line in io . lines () do + local n = tonumber (line) + if n <= 2 then + print (-1) + goto end_loop + end + + local n_sq = n * n + local c = n + 1 + local c_sq = n_sq + 2 * n + 1 + while 2 * c - 1 <= n_sq do + local b_sq = c_sq - n_sq + local b = introot (b_sq) + + if b_sq == b * b then + print (n .. " " .. b .. " " .. c) + end + + c_sq = c_sq + 2 * c + 1 + c = c + 1 + end + + local max_a = math . floor (n / math . sqrt (2)) + for a = 3, max_a do + local b_sq = n_sq - a * a + local b = introot (b_sq) + if b_sq == b * b then + print (a .. " " .. b .. " " .. n) + end + end + + ::end_loop:: +end diff --git a/challenge-125/abigail/node/ch-1.js b/challenge-125/abigail/node/ch-1.js new file mode 100644 index 0000000000..a8c8c9c2c4 --- /dev/null +++ b/challenge-125/abigail/node/ch-1.js @@ -0,0 +1,47 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', line => main (+ line)) + +function introot (square) { + return (Math . floor (.4 + Math . sqrt (square))) +} + +function main (n) { + if (n <= 2) { + console . log (-1) + return + } + + let n_sq = n * n + let c = n + 1 + let c_sq = n_sq + 2 * n + 1 + while (2 * c - 1 <= n_sq) { + let b_sq = c_sq - n_sq + let b = introot (b_sq) + + if (b_sq == b * b) { + console . log (n + " " + b + " " + c) + } + + c_sq += 2 * c ++ + 1 + } + + let max_a = Math . floor (n / Math . sqrt (2)) + for (let a = 3; a <= max_a; a ++) { + let b_sq = n_sq - a * a + let b = introot (b_sq) + if (b_sq == b * b) { + console . log (a + " " + b + " " + n) + } + } +} diff --git a/challenge-125/abigail/perl/ch-1.pl b/challenge-125/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..c62b9b92d3 --- /dev/null +++ b/challenge-125/abigail/perl/ch-1.pl @@ -0,0 +1,69 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-1.pl < input-file +# + +sub introot ($square) { + # + # Return the largest integer less than, or equal to the + # square root of $square. + # + int (.4 + sqrt ($square)); +} + + + +while (my $n = <>) { + chomp ($n); + say (-1), next if $n <= 2; + # + # First case, $n is not the hypothenuse; wlog, assume n = a. + # + # Then, we start searching from c = n + 1 until + # c^2 - (c - 1)^2 > n^2. Note that c^2 - (c - 1)^2 = 2c - 1 + # In each iteration, we calculate b^2 = c^2 - n^2. If b^2 is + # a proper square, we have a Pythagorian triple. + # + my $n_sq = $n * $n; + + my $c = $n + 1; + my $c_sq = $n_sq + 2 * $n + 1; + while (2 * $c - 1 <= $n_sq) { + # + # We now have a^2 (n_sq) and c^2. We can calculate b^2 (b_sq) + # and check whether this is a proper square. + # + my $b_sq = $c_sq - $n_sq; + my $b = introot ($b_sq); + + say "$n $b $c" if $b_sq == $b * $b; + $c_sq += 2 * $c ++ + 1; # (c + 1)^2 == c^2 + 2 * c + 1 + } + + # + # Handle the case $n is the hypothenuse, so $n == c. + # + # We now need to search for a, b such that a^2 + b^2 = c^2 ($n_sq). + # Wlog, assume a < b (a == b cannot happen). Then a < c / sqrt (2). + # + my $max_a = int ($n / sqrt (2)); + for (my $a = 3; $a <= $max_a; $a ++) { + my $b_sq = $n_sq - $a * $a; + my $b = introot ($b_sq); + say "$a $b $n" if $b_sq == $b * $b; + } +} diff --git a/challenge-125/abigail/python/ch-1.py b/challenge-125/abigail/python/ch-1.py new file mode 100644 index 0000000000..f8c07799b3 --- /dev/null +++ b/challenge-125/abigail/python/ch-1.py @@ -0,0 +1,41 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-1.py < input-file +# + +import fileinput +import math + +def introot (square): + return math . floor (.4 + math . sqrt (square)) + +for line in fileinput . input (): + n = int (line) + if n <= 2: + print (-1) + continue + + n_sq = n * n + c = n + 1 + c_sq = n_sq + 2 * n + 1 + while 2 * c - 1 <= n_sq: + b_sq = c_sq - n_sq + b = introot (b_sq) + + if b_sq == b * b: + print (str (n) + " " + str (b) + " " + str (c)) + + c_sq = c_sq + 2 * c + 1 + c = c + 1 + + max_a = math . floor (n / math . sqrt (2)) + for a in range (3, max_a + 1): + b_sq = n_sq - a * a + b = introot (b_sq) + if b_sq == b * b: + print (str (a) + " " + str (b) + " " + str (n)) diff --git a/challenge-125/abigail/ruby/ch-1.rb b/challenge-125/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..91518fc95e --- /dev/null +++ b/challenge-125/abigail/ruby/ch-1.rb @@ -0,0 +1,45 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-1.rb < input-file +# + +def introot (square) + return Math . sqrt(square) . floor() +end + +ARGF . each_line do + |n| + n = n . to_i + if (n <= 2) then + puts (-1) + end + + n_sq = n * n + c = n + 1 + c_sq = n_sq + 2 * n + 1 + while (2 * c - 1 <= n_sq) do + b_sq = c_sq - n_sq + b = introot (b_sq) + + if (b_sq == b * b) then + puts (n . to_s + " " + b . to_s + " " + c . to_s) + end + + c_sq += 2 * c + 1 + c += 1 + end + + max_a = (n / Math . sqrt(2)) . floor() + for a in 3 .. max_a do + b_sq = n_sq - a * a + b = introot (b_sq) + if (b_sq == b * b) then + puts (a . to_s + " " + b . to_s + " " + n . to_s) + end + end +end -- cgit From f42d586e285b5fb1694d33320380589b7709d579 Mon Sep 17 00:00:00 2001 From: Abigail Date: Wed, 11 Aug 2021 00:33:51 +0200 Subject: A solution for week 125, part 2, for some definition of solution. Once again, the problem does not specify how to binary tree input is going to look like. All we can deduce from the single example input is that is absolutly won't scale beyond utter trivial sizes. So, we will just die on any input which isn't exactly the one case which is specified. --- challenge-125/abigail/perl/ch-2.pl | 60 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 challenge-125/abigail/perl/ch-2.pl diff --git a/challenge-125/abigail/perl/ch-2.pl b/challenge-125/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..11b81d43d2 --- /dev/null +++ b/challenge-125/abigail/perl/ch-2.pl @@ -0,0 +1,60 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-2.pl < input-file +# + +# +# Once again, the weekly challenge cannot be bothered to specify how +# the input looks like when the exercises is about binary trees; +# there's only a single example tree, of which it's clear it will not +# scale beyond anything trivial. +# +# As such, the best we can do is recognize the one example, while being +# lenient if there is surplus white space. We'll print the answer if +# the example tree is given as input, and die on anything else, as nothing +# else is specified. +# + +undef $/; +my $input = <>; + +# +# Remove blank lines +# +$input =~ s/^\s+$//gm; + +# +# Remove trailing whitespace from each line. +# +$input =~ s/\h+$//mg; + +# +# Remove leading whitespace +# +$input =~ s/^ //gm while $input !~ /^\S/m; + +if ($input eq << '--') {say 7} else {die "Unrecognized input"} + 1 + / \ + 2 5 + / \ / \ +3 4 6 7 + / \ + 8 10 + / + 9 +-- -- cgit From 525d5e4033d2a97406ecf9b4fbc52902c8e2210d Mon Sep 17 00:00:00 2001 From: Abigail Date: Wed, 11 Aug 2021 19:11:21 +0200 Subject: Different approach for week 125, part 2. Incomplete program, due to lack of specification. --- challenge-125/abigail/perl/ch-2.pl | 92 +++++++++++++++++++++++--------------- 1 file changed, 55 insertions(+), 37 deletions(-) diff --git a/challenge-125/abigail/perl/ch-2.pl b/challenge-125/abigail/perl/ch-2.pl index 11b81d43d2..29d0c71c02 100644 --- a/challenge-125/abigail/perl/ch-2.pl +++ b/challenge-125/abigail/perl/ch-2.pl @@ -17,44 +17,62 @@ use experimental 'lexical_subs'; # Run as: perl ch-2.pl < input-file # -# -# Once again, the weekly challenge cannot be bothered to specify how -# the input looks like when the exercises is about binary trees; -# there's only a single example tree, of which it's clear it will not -# scale beyond anything trivial. -# -# As such, the best we can do is recognize the one example, while being -# lenient if there is surplus white space. We'll print the answer if -# the example tree is given as input, and die on anything else, as nothing -# else is specified. -# +package Tree { + use Hash::Util::FieldHash qw [fieldhash]; + use List::Util qw [max]; -undef $/; -my $input = <>; + fieldhash my %left; + fieldhash my %right; + + sub new ($class) {bless do {\my $var} => $class} -# -# Remove blank lines -# -$input =~ s/^\s+$//gm; + sub init ($self, $input) { + # + # Initialize a tree given the input following the + # specification of how we're given a tree. + # -# -# Remove trailing whitespace from each line. -# -$input =~ s/\h+$//mg; + ...; # <-- This is the yada, yada, yada operator, typically + # a placeholder for code which still needs to be written. + # Perfect! Once we have a specification of how the + # the input is structured (other than a single example + # of which anyone can instantly see it doesn't scale + # beyond trivial sizes), we can replace this piece of code. + # + # This does mean though, that rest of the code is largely + # untested. "It compiles" is the best we can do. + # -# -# Remove leading whitespace -# -$input =~ s/^ //gm while $input !~ /^\S/m; - -if ($input eq << '--') {say 7} else {die "Unrecognized input"} - 1 - / \ - 2 5 - / \ / \ -3 4 6 7 - / \ - 8 10 - / - 9 --- + $self; + } + + # + # Get the left and right child of a tree. Leaves obviously + # don't have children. + # + sub left ($self) {$self && $left {$self}} + sub right ($self) {$self && $right {$self}} + + sub diameter ($self) { + ($self -> _diameter ($self)) [1] + } + + sub _diameter ($self) { + # + # Given a tree, return a tuple ($depth, $diameter), where + # first element is the depth of a tree (longest path to a leaf), + # and second the diameter (longest path in the tree). + # + # Depth of a tree is 1 + max (depth left child, depth right child) + # Diameter of a tree is max (diameter left child, + # diameter right child, 1 + depth left child + depth right child). + # + return (0, 0) unless $self; # Leaves have no depth nor diameter. + my ($ldp, $ldm) = $self -> left -> _diameter; + my ($rdp, $rdm) = $self -> right -> _diameter; + (max ($ldp, $rdp), max ($ldm, $rdm, 1 + $ldp + $rdp)) + } +} + + +say Tree:: -> new -> init (do {local $/; <>}) -> diameter; -- cgit From 989dcde471a30935b8e51c557b971496963caffc Mon Sep 17 00:00:00 2001 From: Dave Jacoby Date: Wed, 11 Aug 2021 16:19:43 -0400 Subject: Edges, Not Nodes --- challenge-125/dave-jacoby/perl/ch-1.pl | 18 ------------------ challenge-125/dave-jacoby/perl/ch-2.pl | 4 +++- 2 files changed, 3 insertions(+), 19 deletions(-) diff --git a/challenge-125/dave-jacoby/perl/ch-1.pl b/challenge-125/dave-jacoby/perl/ch-1.pl index 717d608a68..29f99b60d3 100644 --- a/challenge-125/dave-jacoby/perl/ch-1.pl +++ b/challenge-125/dave-jacoby/perl/ch-1.pl @@ -65,22 +65,4 @@ sub pt_c ($n ) { } return uniq @output if @output; return undef; - - # my @output; - # my $n2 = $n**2; - - # for my $a1 ( 1 .. $n2 ) { - # my $a2 = $a1**2; - # for my $b1 ( 1 .. $n2 ) { - # my $b2 = $b1**2; - # my $c2 = $a2 + $b2; - # next if $c2 > $n2; - # if ( $n2 == $c2 ) { - # my @x = sort { $a <=> $b } map { int $_ } $a1, $b1, $n; - # push @output, $json->encode( \@x ); - # } - # } - # } - # return uniq @output if @output; - # return undef; } diff --git a/challenge-125/dave-jacoby/perl/ch-2.pl b/challenge-125/dave-jacoby/perl/ch-2.pl index b6e5e97817..8dd5fb4268 100644 --- a/challenge-125/dave-jacoby/perl/ch-2.pl +++ b/challenge-125/dave-jacoby/perl/ch-2.pl @@ -47,7 +47,9 @@ my $done; grep { scalar $_->@* == $max } sort { scalar $b->@* <=> scalar $a->@* } @diameters; -say join "\n", map { join " ", ( scalar $_->@* ), ':', $_->@* } +# DIAMETER refers to the edge count, not the node count, +# so the it's the node count minus one +say join "\n", map { join " ", ( -1 + scalar $_->@* ), ':', $_->@* } @diameters; -- cgit From a1e6d2389d3af8169fe5076b00f928d153c69ce7 Mon Sep 17 00:00:00 2001 From: Abigail Date: Thu, 12 Aug 2021 17:50:45 +0200 Subject: AWK and Go solutions for week 125, part 1. --- challenge-125/abigail/README.md | 2 ++ challenge-125/abigail/awk/ch-1.awk | 44 +++++++++++++++++++++++++++ challenge-125/abigail/go/ch-1.go | 61 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 107 insertions(+) create mode 100644 challenge-125/abigail/awk/ch-1.awk create mode 100644 challenge-125/abigail/go/ch-1.go diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index f8c6f2595b..85399168ce 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -29,7 +29,9 @@ Output: -1 ~~~~ ### Solutions +* [AWK](awk/ch-1.awk) * [C](c/ch-1.c) +* [Go](go/ch-1.go) * [Lua](lua/ch-1.lua) * [Node.js](node/ch-1.js) * [Perl](perl/ch-1.pl) diff --git a/challenge-125/abigail/awk/ch-1.awk b/challenge-125/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..1758b7d64d --- /dev/null +++ b/challenge-125/abigail/awk/ch-1.awk @@ -0,0 +1,44 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-1.awk < input-file +# + +function introot (square) { + return (int (.4 + sqrt (square))) +} + + +$1 <= 2 { + print (-1) + next +} + + +{ + n = $1 + n_sq = n * n + c = n + 1 + c_sq = n_sq + 2 * n + 1 + while (2 * c - 1 <= n_sq) { + b_sq = c_sq - n_sq + b = introot(b_sq) + if (b_sq == b * b) { + print n, b, c + } + c_sq += 2 * c ++ + 1 + } + + max_a = int (n / sqrt (2)) + for (a = 3; a <= max_a; a ++) { + b_sq = n_sq - a * a + b = introot(b_sq) + if (b_sq == b * b) { + print a, b, n + } + } +} diff --git a/challenge-125/abigail/go/ch-1.go b/challenge-125/abigail/go/ch-1.go new file mode 100644 index 0000000000..f69846b7ed --- /dev/null +++ b/challenge-125/abigail/go/ch-1.go @@ -0,0 +1,61 @@ +package main + +// +// See ../README.md +// + +// +// Run as: go run ch-1.go +// + +import ( + "fmt" + "math" +) + +func introot (square int) int { + return (int (math . Round (math . Sqrt (float64 (square))))); +} + +func main () { + for { + var n, n_sq, a, max_a, b, b_sq, c, c_sq int; + var count, err = fmt . Scanf ("%d", &n); + if (err != nil || count != 1) { + break; + } + + if (n <= 2) { + fmt . Println ("-1"); + continue; + } + + n_sq = n * n; + c = n + 1; + c_sq = n_sq + 2 * n + 1; + + for 2 * c - 1 <= n_sq { + b_sq = c_sq - n_sq; + b = introot (b_sq); + + if (b_sq == b * b) { + fmt . Printf ("%d %d %d\n", n, b, c); + } + + c_sq += 2 * c + 1; + c += 1; + } + + max_a = int (float64 (n) / math . Sqrt (float64 (2))); + + a = 3; + for a <= max_a { + b_sq = n_sq - a * a + b = introot (b_sq) + if (b_sq == b * b) { + fmt . Printf ("%d %d %d\n", a, b, n); + } + a += 1; + } + } +} -- cgit From 5d3b637c1812e4d1534a72f5ab834dd7c88b6665 Mon Sep 17 00:00:00 2001 From: Abigail Date: Fri, 13 Aug 2021 18:59:21 +0200 Subject: Java and Pascal solutions for week 125, part 1 --- challenge-125/abigail/README.md | 2 ++ challenge-125/abigail/java/ch-1.java | 52 +++++++++++++++++++++++++++++++ challenge-125/abigail/pascal/ch-1.p | 59 ++++++++++++++++++++++++++++++++++++ 3 files changed, 113 insertions(+) create mode 100644 challenge-125/abigail/java/ch-1.java create mode 100644 challenge-125/abigail/pascal/ch-1.p diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index 85399168ce..edbb6b6ea7 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -32,8 +32,10 @@ Output: -1 * [AWK](awk/ch-1.awk) * [C](c/ch-1.c) * [Go](go/ch-1.go) +* [Java](java/ch-1.java) * [Lua](lua/ch-1.lua) * [Node.js](node/ch-1.js) +* [Pascal](pascal/ch-1.p) * [Perl](perl/ch-1.pl) * [Python](python/ch-1.py) * [Ruby](ruby/ch-1.rb) diff --git a/challenge-125/abigail/java/ch-1.java b/challenge-125/abigail/java/ch-1.java new file mode 100644 index 0000000000..722b6d0f81 --- /dev/null +++ b/challenge-125/abigail/java/ch-1.java @@ -0,0 +1,52 @@ +// +// See ../README.md +// + +// +// Run as: ln ch-1.java ch1.java; javac ch1.java; java ch1 < input-file +// + +import java.util.*; + +public class ch1 { + public static long introot (long square) { + return ((long) Math . floor (Math . sqrt (square))); + } + + public static void main (String [] args) { + Scanner scanner = new Scanner (System . in); + while (scanner . hasNextInt ()) { + long n = scanner . nextInt (); + if (n <= 2) { + System . out . println ("-1"); + continue; + } + + long n_sq = n * n; + long c = n + 1; + long c_sq = n_sq + 2 * n + 1; + + while (2 * c - 1 <= n_sq) { + long b_sq = c_sq - n_sq; + long b = introot (b_sq); + + if (b_sq == b * b) { + System . out . printf ("%d %d %d\n", n, b, c); + } + + c_sq += 2 * c + 1; + c += 1; + } + + long max_a = (long) Math . floor (n / Math . sqrt (2)); + long a = 3; + for (a = 3; a <= max_a; a ++) { + long b_sq = n_sq - a * a; + long b = introot (b_sq); + if (b_sq == b * b) { + System . out . printf ("%d %d %d\n", a, b, n); + } + } + } + } +} diff --git a/challenge-125/abigail/pascal/ch-1.p b/challenge-125/abigail/pascal/ch-1.p new file mode 100644 index 0000000000..f6e2d93fb5 --- /dev/null +++ b/challenge-125/abigail/pascal/ch-1.p @@ -0,0 +1,59 @@ +Program XXX; + +(* *) +(* See ../README.md *) +(* *) + +(* *) +(* Run as: fpc -och-1.out ch-1.p; ./ch-1.out < input-file *) +(* *) + +uses + math; + +var + n, n_sq, a, max_a, b, b_sq, c, c_sq: int64; + +function introot (square: int64): int64; +begin + introot := round (sqrt (square)); +end; + + +begin + while (not eof) do begin + readln (n); + if n <= 2 then begin + writeln (-1); + continue; + end; + + n_sq := n * n; + c := n + 1; + c_sq := n_sq + 2 * n + 1; + + while (2 * c - 1 <= n_sq) do begin + b_sq := c_sq - n_sq; + b := introot (b_sq); + if b_sq = b * b then begin + writeln (n, ' ', b, ' ', c); + end; + c_sq := c_sq + 2 * c + 1; + c := c + 1; + end; + + max_a := floor (n / sqrt (2)); + for a := 3 to max_a do begin + b_sq := n_sq - a * a; + if b_sq < 0 then begin + writeln ('n = ', n, '; a = ', a, '; b_sq = ', b_sq); + continue; + end; + + b := introot (b_sq); + if b_sq = b * b then begin + writeln (a, ' ', b, ' ', n); + end; + end; + end; +end. -- cgit From 1f8d3b4f7da48be8efcf216eca31ba62f21f372d Mon Sep 17 00:00:00 2001 From: Abigail Date: Fri, 13 Aug 2021 22:24:55 +0200 Subject: R solution for week 125, part 1 --- challenge-125/abigail/README.md | 1 + challenge-125/abigail/r/ch-1.r | 54 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 55 insertions(+) create mode 100644 challenge-125/abigail/r/ch-1.r diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index edbb6b6ea7..8fb1acbf4d 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -38,6 +38,7 @@ Output: -1 * [Pascal](pascal/ch-1.p) * [Perl](perl/ch-1.pl) * [Python](python/ch-1.py) +* [R](r/ch-1.r) * [Ruby](ruby/ch-1.rb) ### Blog diff --git a/challenge-125/abigail/r/ch-1.r b/challenge-125/abigail/r/ch-1.r new file mode 100644 index 0000000000..bd64758e3f --- /dev/null +++ b/challenge-125/abigail/r/ch-1.r @@ -0,0 +1,54 @@ +# +# See ../README.md +# + +# +# Run as: Rscript ch-1.r < input-file +# + +introot <- function (square) { + return (floor (sqrt (square))) +} + +stdin <- file ('stdin', 'r') +repeat { + n <- readLines (stdin, n = 1) + if (length (n) == 0) { + break + } + n <- as.integer (n) + if (n <= 2) { + cat ("-1\n") + next + } + + n_sq <- n * n + c <- n + 1 + c_sq <- n_sq + 2 * n + 1 + + while (2 * c - 1 <= n_sq) { + b_sq <- c_sq - n_sq + b <- introot (b_sq) + + if (b_sq == b * b) { + cat (n, b, c, "\n") + } + + c_sq <- c_sq + 2 * c + 1 + c <- c + 1 + } + + max_a = floor (n / sqrt (2)) + if (max_a < 3) { + next + } + for (a in 3 : max_a) { + # cat ("a = ", a, "\n") + b_sq <- n_sq - a * a + b <- introot (b_sq) + + if (b_sq == b * b) { + cat (a, b, n, "\n") + } + } +} -- cgit From 26018e17bb38f61027306864c9b9a63063b7f089 Mon Sep 17 00:00:00 2001 From: Abigail Date: Sat, 14 Aug 2021 02:29:05 +0200 Subject: Tcl solution for week 125, part 1 --- challenge-125/abigail/README.md | 1 + challenge-125/abigail/tcl/ch-1.tcl | 45 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 46 insertions(+) create mode 100644 challenge-125/abigail/tcl/ch-1.tcl diff --git a/challenge-125/abigail/README.md b/challenge-125/abigail/README.md index 8fb1acbf4d..677f80fccf 100644 --- a/challenge-125/abigail/README.md +++ b/challenge-125/abigail/README.md @@ -40,6 +40,7 @@ Output: -1 * [Python](python/ch-1.py) * [R](r/ch-1.r) * [Ruby](ruby/ch-1.rb) +* [Tcl](tcl/ch-1.tcl) ### Blog [Perl Weekly Challenge 125: Pythagorean Triples][blog1] diff --git a/challenge-125/abigail/tcl/ch-1.tcl b/challenge-125/abigail/tcl/ch-1.tcl new file mode 100644 index 0000000000..172dd391ef --- /dev/null +++ b/challenge-125/abigail/tcl/ch-1.tcl @@ -0,0 +1,45 @@ +# +# See ../README.md +# + +# +# Run as: tclsh ch-1.tcl < input-file +# + +proc introot {square} { + return [expr int (.4 + sqrt ($square))] +} + + + +while {[gets stdin n] >= 0} { + if {$n <= 2} { + puts "-1" + continue + } + set n_sq [expr $n * $n] + set c [expr $n + 1] + set c_sq [expr $n_sq + 2 * $n + 1] + + while {2 * $c - 1 <= $n_sq} { + set b_sq [expr $c_sq - $n_sq] + set b [introot $b_sq] + + if {$b_sq == [expr $b * $b]} { + puts "$n $b $c" + } + + set c_sq [expr $c_sq + 2 * $c + 1] + set c [expr $c + 1] + } + + set max_a [expr int ($n / sqrt (2))] + for {set a 3} {$a <= $max_a} {incr a} { + set b_sq [expr $n_sq - $a * $a] + set b [introot $b_sq] + + if {$b_sq == [expr $b * $b]} { + puts "$a $b $n" + } + } +} -- cgit From 34aa316cdbeb0e57f530089e366856b7f86b72cc Mon Sep 17 00:00:00 2001 From: Abigail Date: Sun, 15 Aug 2021 17:59:44 +0200 Subject: Fix calculation of diameter passing through root --- challenge-125/abigail/perl/ch-2.pl | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-125/abigail/perl/ch-2.pl b/challenge-125/abigail/perl/ch-2.pl index 29d0c71c02..45806530f7 100644 --- a/challenge-125/abigail/perl/ch-2.pl +++ b/challenge-125/abigail/perl/ch-2.pl @@ -65,12 +65,12 @@ package Tree { # # Depth of a tree is 1 + max (depth left child, depth right child) # Diameter of a tree is max (diameter left child, - # diameter right child, 1 + depth left child + depth right child). + # diameter right child, depth left child + depth right child). # return (0, 0) unless $self; # Leaves have no depth nor diameter. my ($ldp, $ldm) = $self -> left -> _diameter; my ($rdp, $rdm) = $self -> right -> _diameter; - (max ($ldp, $rdp), max ($ldm, $rdm, 1 + $ldp + $rdp)) + (max ($ldp, $rdp), max ($ldm, $rdm, $ldp + $rdp)) } } -- cgit From 0f9be85222718e52bf5db9f85c3ab70bc35b29dc Mon Sep 17 00:00:00 2001 From: Abigail Date: Sun, 15 Aug 2021 22:49:29 +0200 Subject: Handle leaves better --- challenge-125/abigail/perl/ch-2.pl | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/challenge-125/abigail/perl/ch-2.pl b/challenge-125/abigail/perl/ch-2.pl index 45806530f7..06006dbe58 100644 --- a/challenge-125/abigail/perl/ch-2.pl +++ b/challenge-125/abigail/perl/ch-2.pl @@ -50,8 +50,9 @@ package Tree { # Get the left and right child of a tree. Leaves obviously # don't have children. # - sub left ($self) {$self && $left {$self}} - sub right ($self) {$self && $right {$self}} + sub left ($self) {!$self -> isleaf && $left {$self}} + sub right ($self) {!$self -> isleaf && $right {$self}} + sub isleaf ($self) {!$left {$self} || !$right {$self}} sub diameter ($self) { ($self -> _diameter ($self)) [1] @@ -67,7 +68,7 @@ package Tree { # Diameter of a tree is max (diameter left child, # diameter right child, depth left child + depth right child). # - return (0, 0) unless $self; # Leaves have no depth nor diameter. + return (0, 0) if $self -> isleaf; # Leaves have no depth nor diameter. my ($ldp, $ldm) = $self -> left -> _diameter; my ($rdp, $rdm) = $self -> right -> _diameter; (max ($ldp, $rdp), max ($ldm, $rdm, $ldp + $rdp)) -- cgit From 0dfc1786c2ab2282b265ba90fe18aa32dc33e3fb Mon Sep 17 00:00:00 2001 From: Abigail Date: Sun, 15 Aug 2021 22:50:29 +0200 Subject: Links to blogs --- challenge-125/abigail/blog.txt | 1 + challenge-125/abigail/blog1.txt | 1 + 2 files changed, 2 insertions(+) create mode 100644 challenge-125/abigail/blog.txt create mode 100644 challenge-125/abigail/blog1.txt diff --git a/challenge-125/abigail/blog.txt b/challenge-125/abigail/blog.txt new file mode 100644 index 0000000000..79e86ddc80 --- /dev/null +++ b/challenge-125/abigail/blog.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-125-1.html diff --git a/challenge-125/abigail/blog1.txt b/challenge-125/abigail/blog1.txt new file mode 100644 index 0000000000..ce0adcab58 --- /dev/null +++ b/challenge-125/abigail/blog1.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-125-2.html -- cgit From da70a324b81ad87a740e110a491c9487d27f733a Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Sun, 15 Aug 2021 21:59:38 +0100 Subject: - Added solutions by Abigail. --- stats/pwc-current.json | 341 ++++++------ stats/pwc-language-breakdown-summary.json | 70 +-- stats/pwc-language-breakdown.json | 892 +++++++++++++++--------------- stats/pwc-leaders.json | 450 +++++++-------- stats/pwc-summary-1-30.json | 48 +- stats/pwc-summary-121-150.json | 38 +- stats/pwc-summary-151-180.json | 26 +- stats/pwc-summary-181-210.json | 106 ++-- stats/pwc-summary-211-240.json | 92 +-- stats/pwc-summary-31-60.json | 36 +- stats/pwc-summary-61-90.json | 104 ++-- stats/pwc-summary-91-120.json | 104 ++-- stats/pwc-summary.json | 34 +- 13 files changed, 1180 insertions(+), 1161 deletions(-) diff --git a/stats/pwc-current.json b/stats/pwc-current.json index 604eee1074..ba35feb11b 100644 --- a/stats/pwc-current.json +++ b/stats/pwc-current.json @@ -1,139 +1,31 @@ { - "title" : { - "text" : "The Weekly Challenge - 125" - }, "tooltip" : { - "headerFormat" : "{series.name}
", "followPointer" : 1, + "headerFormat" : "{series.name}
", "pointFormat" : "{point.name}: {point.y:f}
" }, - "subtitle" : { - "text" : "[Champions: 18] Last updated at 2021-08-15 18:02:59 GMT" - }, - "legend" : { - "enabled" : 0 - }, - "chart" : { - "type" : "column" - }, "xAxis" : { "type" : "category" }, - "yAxis" : { - "title" : { - "text" : "Total Solutions" - } - }, - "series" : [ - { - "data" : [ - { - "name" : "Arne Sommer", - "drilldown" : "Arne Sommer", - "y" : 3 - }, - { - "y" : 2, - "drilldown" : "Cheok-Yin Fung", - "name" : "Cheok-Yin Fung" - }, - { - "drilldown" : "Colin Crain", - "name" : "Colin Crain", - "y" : 5 - }, - { - "drilldown" : "E. Choroba", - "name" : "E. Choroba", - "y" : 2 - }, - { - "y" : 6, - "drilldown" : "Flavio Poletti", - "name" : "Flavio Poletti" - }, - { - "y" : 3, - "name" : "James Smith", - "drilldown" : "James Smith" - }, - { - "y" : 1, - "drilldown" : "Jan Krnavek", - "name" : "Jan Krnavek" - }, - { - "drilldown" : "Jorg Sommrey", - "name" : "Jorg Sommrey", - "y" : 2 - }, - { - "drilldown" : "Kai Burgdorf", - "name" : "Kai Burgdorf", - "y" : 1 - }, - { - "y" : 2, - "name" : "Mark Anderson", - "drilldown" : "Mark Anderson" - }, - { - "y" : 2, - "name" : "Matthew Neleigh", - "drilldown" : "Matthew Neleigh" - }, - { - "y" : 1, - "name" : "Pete Houston", - "drilldown" : "Pete Houston" - }, - { - "y" : 4, - "drilldown" : "Roger Bell_West", - "name" : "Roger Bell_West" - }, - { - "y" : 2, - "name" : "Simon Proctor", - "drilldown" : "Simon Proctor" - }, - { - "y" : 4, - "name" : "Stuart Little", - "drilldown" : "Stuart Little" - }, - { - "y" : 2, - "name" : "Ulrich Rieke", - "drilldown" : "Ulrich Rieke" - }, - { - "y" : 3, - "name" : "W. Luis Mochan", - "drilldown" : "W. Luis Mochan" - }, - { - "y" : 1, - "name" : "Wanderdoc", - "drilldown" : "Wanderdoc" - } - ], - "name" : "The Weekly Challenge - 125", - "colorByPoint" : 1 - } - ], - "plotOptions" : { - "series" : { - "dataLabels" : { - "format" : "{point.y}", - "enabled" : 1 - }, - "borderWidth" : 0 - } - }, "drilldown" : { "series" : [ { + "name" : "Abigail", + "id" : "Abigail", + "data" : [ + [ + "Perl", + 2 + ], + [ + "Blog", + 2 + ] + ] + }, + { + "name" : "Arne Sommer", + "id" : "Arne Sommer", "data" : [ [ "Raku", @@ -143,9 +35,7 @@ "Blog", 1 ] - ], - "name" : "Arne Sommer", - "id" : "Arne Sommer" + ] }, { "data" : [ @@ -154,12 +44,10 @@ 2 ] ], - "name" : "Cheok-Yin Fung", - "id" : "Cheok-Yin Fung" + "id" : "Cheok-Yin Fung", + "name" : "Cheok-Yin Fung" }, { - "id" : "Colin Crain", - "name" : "Colin Crain", "data" : [ [ "Perl", @@ -173,19 +61,23 @@ "Blog", 1 ] - ] + ], + "name" : "Colin Crain", + "id" : "Colin Crain" }, { - "name" : "E. Choroba", "data" : [ [ "Perl", 2 ] ], + "name" : "E. Choroba", "id" : "E. Choroba" }, { + "id" : "Flavio Poletti", + "name" : "Flavio Poletti", "data" : [ [ "Perl", @@ -199,11 +91,10 @@ "Blog", 2 ] - ], - "name" : "Flavio Poletti", - "id" : "Flavio Poletti" + ] }, { + "id" : "James Smith", "name" : "James Smith", "data" : [ [ @@ -214,40 +105,41 @@ "Blog", 1 ] - ], - "id" : "James Smith" + ] }, { + "name" : "Jan Krnavek", "id" : "Jan Krnavek", "data" : [ [ "Raku", 1 ] - ], - "name" : "Jan Krnavek" + ] }, { + "name" : "Jorg Sommrey", + "id" : "Jorg Sommrey", "data" : [ [ "Perl", 2 ] - ], - "name" : "Jorg Sommrey", - "id" : "Jorg Sommrey" + ] }, { + "name" : "Kai Burgdorf", "id" : "Kai Burgdorf", "data" : [ [ "Perl", 1 ] - ], - "name" : "Kai Burgdorf" + ] }, { + "id" : "Mark Anderson", + "name" : "Mark Anderson", "data" : [ [ "Perl", @@ -257,32 +149,29 @@ "Raku", 1 ] - ], - "name" : "Mark Anderson", - "id" : "Mark Anderson" + ] }, { -