From 89a78cb5d9b17a7b840c3d8de465dff4bafcee39 Mon Sep 17 00:00:00 2001 From: Jan Krňávek Date: Sat, 23 Oct 2021 15:59:05 +0200 Subject: 1-Z needs 36 base --- challenge-135/wambash/raku/ch-2.raku | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-135/wambash/raku/ch-2.raku b/challenge-135/wambash/raku/ch-2.raku index d8fe6da3c8..721c149ae2 100644 --- a/challenge-135/wambash/raku/ch-2.raku +++ b/challenge-135/wambash/raku/ch-2.raku @@ -24,7 +24,7 @@ class Validate-SEDOL { } method char ($/) { - make $/.Str.parse-base(35) + make $/.Str.parse-base(36) } } -- cgit From baad1c27d1e0f4945733ad51fb5fb10694f55540 Mon Sep 17 00:00:00 2001 From: Dave Jacoby Date: Mon, 25 Oct 2021 19:21:45 -0400 Subject: Challenge 136 --- challenge-136/dave-jacoby/blog.txt | 1 + challenge-136/dave-jacoby/perl/ch-1.pl | 38 +++++++++++++++++++ challenge-136/dave-jacoby/perl/ch-2.pl | 67 ++++++++++++++++++++++++++++++++++ 3 files changed, 106 insertions(+) create mode 100644 challenge-136/dave-jacoby/blog.txt create mode 100644 challenge-136/dave-jacoby/perl/ch-1.pl create mode 100644 challenge-136/dave-jacoby/perl/ch-2.pl diff --git a/challenge-136/dave-jacoby/blog.txt b/challenge-136/dave-jacoby/blog.txt new file mode 100644 index 0000000000..4820c56511 --- /dev/null +++ b/challenge-136/dave-jacoby/blog.txt @@ -0,0 +1 @@ +https://jacoby.github.io/2021/10/25/the-sequential-friendly-book-the-weekly-challenge-136.html diff --git a/challenge-136/dave-jacoby/perl/ch-1.pl b/challenge-136/dave-jacoby/perl/ch-1.pl new file mode 100644 index 0000000000..67eece6bc7 --- /dev/null +++ b/challenge-136/dave-jacoby/perl/ch-1.pl @@ -0,0 +1,38 @@ +#!/usr/bin/env perl + +use strict; +use warnings; +use feature qw{ say state postderef signatures }; +no warnings qw{ experimental }; + +my @examples = ( [ 8, 24 ], [ 26, 39 ], [ 4, 10 ], [ 24, 40 ] ); + +for my $i (@examples) { + my ( $m, $n ) = $i->@*; + my $o = two_friendly( $i->@* ); + say <<"END"; + Input: \$m = $m \$n = $n + Output: $o +END +} + +# "Two-Friendly" means the greatest common +# denominator is a power of two. + +# Greatest common denomonator is the product +# of all the common denominators. + +# So, the moment you get a common denominator +# that is NOT zero, you have a two-unfriendly +# number and can securely return 0 +sub two_friendly ( $m = 8, $n = 16 ) { + my ($lower) = sort { $a <=> $b } $m, $n; + for my $i ( 2 .. $lower ) { + while ( $m % $i == 0 && $n % $i == 0 ) { + $m /= $i; + $n /= $i; + return 0 if $i != 2; + } + } + return 1; +} diff --git a/challenge-136/dave-jacoby/perl/ch-2.pl b/challenge-136/dave-jacoby/perl/ch-2.pl new file mode 100644 index 0000000000..57f66a430a --- /dev/null +++ b/challenge-136/dave-jacoby/perl/ch-2.pl @@ -0,0 +1,67 @@ +#!/usr/bin/env perl + +use strict; +use warnings; +use feature qw{ say postderef signatures state }; +no warnings qw{ experimental }; + +use JSON; +use List::Util qw{ sum0 uniq }; +my $json = JSON->new->pretty->canonical; + +my @examples = qw{16 9 15}; + +for my $n (@examples) { + my @o = solve_task($n); + my $o = scalar @o; + my $oo = join ",\n ", map { ($_) } @o; + + say <<"END"; + Input: \$n = $n + Output: $o + $oo +END +} + +sub solve_task ($n) { + my @fib = grep { $_ < $n } map { fib($_) } 1 .. $n; + my @sequences = recursion( $n, \@fib ); + return @sequences; +} + +# Let's call it what it is +sub recursion ( $n, $ref, $x = [] ) { + my @output; + my $depth = 1 + scalar $x->@*; + my $sum = sum0 $x->@*; + my $nex->@* = sort $ref->@*; + + return undef if $sum > $n; + + if ( $sum == $n ) { + $x->@* = sort { $a <=> $b } map { int $_ } $x->@*; + my $answer = join ' + ', $x->@*; + return $answer; + } + + for my $i ( 1 .. scalar $nex->@* ) { + my $v = shift $nex->@*; + my $y->@* = $x->@*; + push $y->@*, $v; + + my @return = recursion( $n, $nex, $y ); + push @output, @return; + push $nex->@*, $v; + } + return uniq sort grep { defined } @output; +} + +sub fib ($n) { + state $fib; + $fib->{0} = 1; + $fib->{1} = 1; + if ( $fib->{$n} ) { + return $fib->{$n}; + } + $fib->{$n} = fib( $n - 1 ) + fib( $n - 2 ); +} -- cgit From 1c83475aade8956c9ef0de26484981e6e93d73fa Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Fri, 29 Oct 2021 10:55:09 +0100 Subject: Add Perl and Pyhton solutions to challenge 122 --- challenge-001/paulo-custodio/brainfuck/ch-2.pl | 24 +++++------ challenge-122/paulo-custodio/Makefile | 2 + challenge-122/paulo-custodio/perl/ch-1.pl | 26 ++++++++++++ challenge-122/paulo-custodio/perl/ch-2.pl | 55 ++++++++++++++++++++++++++ challenge-122/paulo-custodio/python/ch-1.py | 25 ++++++++++++ challenge-122/paulo-custodio/python/ch-2.py | 52 ++++++++++++++++++++++++ challenge-122/paulo-custodio/t/test-1.yaml | 23 +++++++++++ challenge-122/paulo-custodio/t/test-2.yaml | 30 ++++++++++++++ 8 files changed, 225 insertions(+), 12 deletions(-) create mode 100644 challenge-122/paulo-custodio/Makefile create mode 100644 challenge-122/paulo-custodio/perl/ch-1.pl create mode 100644 challenge-122/paulo-custodio/perl/ch-2.pl create mode 100644 challenge-122/paulo-custodio/python/ch-1.py create mode 100644 challenge-122/paulo-custodio/python/ch-2.py create mode 100644 challenge-122/paulo-custodio/t/test-1.yaml create mode 100644 challenge-122/paulo-custodio/t/test-2.yaml diff --git a/challenge-001/paulo-custodio/brainfuck/ch-2.pl b/challenge-001/paulo-custodio/brainfuck/ch-2.pl index 7ef784110a..65b62fd55a 100644 --- a/challenge-001/paulo-custodio/brainfuck/ch-2.pl +++ b/challenge-001/paulo-custodio/brainfuck/ch-2.pl @@ -14,18 +14,18 @@ use Modern::Perl; my $text = ""; for my $n (1..20) { - if ($n%15==0) { - $text .= "fizzbuzz\n"; - } - elsif ($n%3==0) { - $text .= "fizz\n"; - } - elsif ($n%5==0) { - $text .= "buzz\n"; - } - else { - $text .= "$n\n"; - } + if ($n%15==0) { + $text .= "fizzbuzz\n"; + } + elsif ($n%3==0) { + $text .= "fizz\n"; + } + elsif ($n%5==0) { + $text .= "buzz\n"; + } + else { + $text .= "$n\n"; + } } for (split //, $text) { diff --git a/challenge-122/paulo-custodio/Makefile b/challenge-122/paulo-custodio/Makefile new file mode 100644 index 0000000000..6316089eb8 --- /dev/null +++ b/challenge-122/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-122/paulo-custodio/perl/ch-1.pl b/challenge-122/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..ea7ea0371a --- /dev/null +++ b/challenge-122/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,26 @@ +#!/usr/bin/env perl + +# TASK #1 > Average of Stream +# Submitted by: Mohammad S Anwar +# You are given a stream of numbers, @N. +# +# Write a script to print the average of the stream at every point. +# +# Example +# Input: @N = (10, 20, 30, 40, 50, 60, 70, 80, 90, ...) +# Output: 10, 15, 20, 25, 30, 35, 40, 45, 50, ... +# +# Average of first number is 10. +# Average of first 2 numbers (10+20)/2 = 15 +# Average of first 3 numbers (10+20+30)/3 = 20 +# Average of first 4 numbers (10+20+30+40)/4 = 25 and so on. + +use Modern::Perl; + +my $sum = 0; +my $count = 0; +while (<>) { + $sum += $_; + $count++; + say sprintf("%.2f", $sum/$count); +} diff --git a/challenge-122/paulo-custodio/perl/ch-2.pl b/challenge-122/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..de1bfb1ee4 --- /dev/null +++ b/challenge-122/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,55 @@ +#!/usr/bin/env perl + +# TASK #2 > Basketball Points +# Submitted by: Mohammad S Anwar +# You are given a score $S. +# +# You can win basketball points e.g. 1 point, 2 points and 3 points. +# +# Write a script to find out the different ways you can score $S. +# +# Example +# Input: $S = 4 +# Output: 1 1 1 1 +# 1 1 2 +# 1 2 1 +# 1 3 +# 2 1 1 +# 2 2 +# 3 1 +# +# Input: $S = 5 +# Output: 1 1 1 1 1 +# 1 1 1 2 +# 1 1 2 1 +# 1 1 3 +# 1 2 1 1 +# 1 2 2 +# 1 3 1 +# 2 1 1 1 +# 2 1 2 +# 2 2 1 +# 2 3 +# 3 1 1 +# 3 2 + +use Modern::Perl; +use List::Util 'sum'; + +my $N = shift||0; +show_scores($N); + +sub show_scores { + my($N, @points) = @_; + my $s = @points ? sum(@points) : 0; + if ($s > $N) { + } + elsif ($s == $N) { + say "@points"; + } + else { + show_scores($N, @points, 1); + show_scores($N, @points, 2); + show_scores($N, @points, 3); + } +} diff --git a/challenge-122/paulo-custodio/python/ch-1.py b/challenge-122/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..ab54b706fa --- /dev/null +++ b/challenge-122/paulo-custodio/python/ch-1.py @@ -0,0 +1,25 @@ +#!/usr/bin/env python3 + +# TASK #1 > Average of Stream +# Submitted by: Mohammad S Anwar +# You are given a stream of numbers, @N. +# +# Write a script to print the average of the stream at every point. +# +# Example +# Input: @N = (10, 20, 30, 40, 50, 60, 70, 80, 90, ...) +# Output: 10, 15, 20, 25, 30, 35, 40, 45, 50, ... +# +# Average of first number is 10. +# Average of first 2 numbers (10+20)/2 = 15 +# Average of first 3 numbers (10+20+30)/3 = 20 +# Average of first 4 numbers (10+20+30+40)/4 = 25 and so on. + +import sys + +sum = 0 +count = 0 +for line in sys.stdin: + sum += int(line) + count += 1 + print("{:.2f}".format(sum/count)) diff --git a/challenge-122/paulo-custodio/python/ch-2.py b/challenge-122/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..0556080767 --- /dev/null +++ b/challenge-122/paulo-custodio/python/ch-2.py @@ -0,0 +1,52 @@ +#!/usr/bin/env python3 + +# TASK #2 > Basketball Points +# Submitted by: Mohammad S Anwar +# You are given a score $S. +# +# You can win basketball points e.g. 1 point, 2 points and 3 points. +# +# Write a script to find out the different ways you can score $S. +# +# Example +# Input: $S = 4 +# Output: 1 1 1 1 +# 1 1 2 +# 1 2 1 +# 1 3 +# 2 1 1 +# 2 2 +# 3 1 +# +# Input: $S = 5 +# Output: 1 1 1 1 1 +# 1 1 1 2 +# 1 1 2 1 +# 1 1 3 +# 1 2 1 1 +# 1 2 2 +# 1 3 1 +# 2 1 1 1 +# 2 1 2 +# 2 2 1 +# 2 3 +# 3 1 1 +# 3 2 + +import sys + +def show_scores(N): + def scores(N, points): + s = sum(points) + if s > N: + pass + elif s == N: + print(" ".join([str(x) for x in points])) + else: + scores(N, [*points, 1]) + scores(N, [*points, 2]) + scores(N, [*points, 3]) + scores(N, []) + +N = int(sys.argv[1]) +show_scores(N) diff --git a/challenge-122/paulo-custodio/t/test-1.yaml b/challenge-122/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..e62a1cd366 --- /dev/null +++ b/challenge-122/paulo-custodio/t/test-1.yaml @@ -0,0 +1,23 @@ +- setup: + cleanup: + args: + input: | + 10 + 20 + 30 + 40 + 50 + 60 + 70 + 80 + 90 + output: | + 10.00 + 15.00 + 20.00 + 25.00 + 30.00 + 35.00 + 40.00 + 45.00 + 50.00 diff --git a/challenge-122/paulo-custodio/t/test-2.yaml b/challenge-122/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..df6bd41cc9 --- /dev/null +++ b/challenge-122/paulo-custodio/t/test-2.yaml @@ -0,0 +1,30 @@ +- setup: + cleanup: + args: 4 + input: + output: | + 1 1 1 1 + 1 1 2 + 1 2 1 + 1 3 + 2 1 1 + 2 2 + 3 1 +- setup: + cleanup: + args: 5 + input: + output: | + 1 1 1 1 1 + 1 1 1 2 + 1 1 2 1 + 1 1 3 + 1 2 1 1 + 1 2 2 + 1 3 1 + 2 1 1 1 + 2 1 2 + 2 2 1 + 2 3 + 3 1 1 + 3 2 -- cgit From 3942303512e3ac0e48e57a2e9e8c2ef2a5e8cb6e Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Fri, 29 Oct 2021 13:39:49 +0100 Subject: Add Python solutions to challenge 121 --- challenge-121/paulo-custodio/Makefile | 2 + challenge-121/paulo-custodio/python/ch-1.py | 30 +++++++++++++++ challenge-121/paulo-custodio/python/ch-2.py | 57 +++++++++++++++++++++++++++++ challenge-121/paulo-custodio/test.pl | 4 -- 4 files changed, 89 insertions(+), 4 deletions(-) create mode 100644 challenge-121/paulo-custodio/Makefile create mode 100644 challenge-121/paulo-custodio/python/ch-1.py create mode 100644 challenge-121/paulo-custodio/python/ch-2.py delete mode 100644 challenge-121/paulo-custodio/test.pl diff --git a/challenge-121/paulo-custodio/Makefile b/challenge-121/paulo-custodio/Makefile new file mode 100644 index 0000000000..6316089eb8 --- /dev/null +++ b/challenge-121/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-121/paulo-custodio/python/ch-1.py b/challenge-121/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..c4f5276926 --- /dev/null +++ b/challenge-121/paulo-custodio/python/ch-1.py @@ -0,0 +1,30 @@ +#!/usr/bin/env python3 + +# Challenge 121 +# +# TASK #1 > Invert Bit +# Submitted by: Mohammad S Anwar +# You are given integers 0 <= $m <= 255 and 1 <= $n <= 8. +# +# Write a script to invert $n bit from the end of the binary representation of +# $m and print the decimal representation of the new binary number. +# +# Example +# Input: $m = 12, $n = 3 +# Output: 8 +# +# Binary representation of $m = 00001100 +# Invert 3rd bit from the end = 00001000 +# Decimal equivalent of 00001000 = 8 +# +# Input $m = 18, $n = 4 +# Output: 26 +# +# Binary representation of $m = 00010010 +# Invert 4th bit from the end = 00011010 +# Decimal equivalent of 00011010 = 26 + +import sys + +m, n = int(sys.argv[1]), int(sys.argv[2]) +print(m ^ (1 << (n-1))) diff --git a/challenge-121/paulo-custodio/python/ch-2.py b/challenge-121/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..7a3b6f4443 --- /dev/null +++ b/challenge-121/paulo-custodio/python/ch-2.py @@ -0,0 +1,57 @@ +#!/usr/bin/env python3 + +# Challenge 121 +# +# TASK #2 > The Travelling Salesman +# Submitted by: Jorg Sommrey +# You are given a NxN matrix containing the distances between N cities. +# +# Write a script to find a round trip of minimum length visiting all N cities +# exactly once and returning to the start. +# +# Example +# Matrix: [0, 5, 2, 7] +# [5, 0, 5, 3] +# [3, 1, 0, 6] +# [4, 5, 4, 0] +# +# Output: +# length = 10 +# tour = (0 2 1 3 0) + +import sys + +def read_dist(): + dist = [] + for line in sys.stdin: + row = [int(x) for x in line.split()] + dist.append(row) + return dist + +def shortest_tour(dist): + short_length = 100000 + short_path = [] + + def tour(length, path): + nonlocal short_length, short_path + + cities = list(set(range(0, len(dist))) - set(path)) + cities.sort() + + if len(cities)==0: + # no more cities to visit + length += dist[path[-1]][path[0]] + path.append(path[0]) + if length < short_length: + short_length, short_path = length, path + else: + # try each city + for city in cities: + tour(length + dist[path[-1]][city], [*path, city]) + + tour(0, [0]) + return (short_length, short_path) + +length, path = shortest_tour(read_dist()) +print("length =", length) +print("tour = ("+ " ".join([str(x) for x in path]) + ")") diff --git a/challenge-121/paulo-custodio/test.pl b/challenge-121/paulo-custodio/test.pl deleted file mode 100644 index ba6c37260b..0000000000 --- a/challenge-121/paulo-custodio/test.pl +++ /dev/null @@ -1,4 +0,0 @@ -#!/usr/bin/env perl -use Modern::Perl; -use Test::More; -require '../../challenge-001/paulo-custodio/test.pl'; -- cgit From f58e9e88056887a42482592154c1c7cbe03e61cb Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Fri, 29 Oct 2021 14:40:28 +0100 Subject: Fix 64-bit portability --- challenge-118/paulo-custodio/d/ch_2.d | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-118/paulo-custodio/d/ch_2.d b/challenge-118/paulo-custodio/d/ch_2.d index 122b253812..eed57ac24d 100644 --- a/challenge-118/paulo-custodio/d/ch_2.d +++ b/challenge-118/paulo-custodio/d/ch_2.d @@ -227,7 +227,7 @@ Move[] next_moves(Game* game) { for (int i = 0; i < moves.length; i++) { Move[] temp_moves; try_num_moves(&temp_moves, game, moves[i].row, moves[i].col); - moves[i].num_moves = temp_moves.length; + moves[i].num_moves = cast(int)temp_moves.length; if (min_moves > moves[i].num_moves) min_moves = moves[i].num_moves; } -- cgit From bf8032b503c262609b9b77e60ed56864a4546aed Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Fri, 29 Oct 2021 14:41:00 +0100 Subject: Add Python solution --- challenge-118/paulo-custodio/Makefile | 2 ++ challenge-118/paulo-custodio/python/ch-1.py | 27 +++++++++++++++++++++++++++ challenge-118/paulo-custodio/test.pl | 4 ---- 3 files changed, 29 insertions(+), 4 deletions(-) create mode 100644 challenge-118/paulo-custodio/Makefile create mode 100644 challenge-118/paulo-custodio/python/ch-1.py delete mode 100644 challenge-118/paulo-custodio/test.pl diff --git a/challenge-118/paulo-custodio/Makefile b/challenge-118/paulo-custodio/Makefile new file mode 100644 index 0000000000..c3c762d746 --- /dev/null +++ b/challenge-118/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-118/paulo-custodio/python/ch-1.py b/challenge-118/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..b7652634d3 --- /dev/null +++ b/challenge-118/paulo-custodio/python/ch-1.py @@ -0,0 +1,27 @@ +#!/usr/bin/env python3 + +# Challenge 118 +# +# TASK #1 - Binary Palindrome +# Submitted by: Mohammad S Anwar +# You are given a positive integer $N. +# +# Write a script to find out if the binary representation of the given integer +# is Palindrome. Print 1 if it is otherwise 0. +# +# Example +# Input: $N = 5 +# Output: 1 as binary representation of 5 is 101 which is Palindrome. +# +# Input: $N = 4 +# Output: 0 as binary representation of 4 is 100 which is NOT Palindrome. + +import sys + +N = int(sys.argv[1]) +bits = "{:b}".format(N) +rbits = bits[::-1] +if bits==rbits: + print(1) +else: + print(0) diff --git a/challenge-118/paulo-custodio/test.pl b/challenge-118/paulo-custodio/test.pl deleted file mode 100644 index ba6c37260b..0000000000 --- a/challenge-118/paulo-custodio/test.pl +++ /dev/null @@ -1,4 +0,0 @@ -#!/usr/bin/env perl -use Modern::Perl; -use Test::More; -require '../../challenge-001/paulo-custodio/test.pl'; -- cgit From 4a2405f3765c0c9494656c716a03d39075fce490 Mon Sep 17 00:00:00 2001 From: Abigail Date: Fri, 29 Oct 2021 17:13:44 +0200 Subject: Check for even numbers. In week 136, part 1, if one or both numbers are odd, the pair cannot be two-friendly. --- challenge-136/abigail/awk/ch-1.gawk | 4 ++++ challenge-136/abigail/bash/ch-1.sh | 6 +++++- challenge-136/abigail/bc/ch-1.bc | 8 ++++++-- challenge-136/abigail/c/ch-1.c | 4 ++++ challenge-136/abigail/go/ch-1.go | 4 ++++ challenge-136/abigail/java/ch-1.java | 5 +++++ challenge-136/abigail/lua/ch-1.lua | 9 ++++++++- challenge-136/abigail/node/ch-1.js | 4 ++++ challenge-136/abigail/pascal/ch-1.p | 12 ++++++++---- challenge-136/abigail/perl/ch-1.pl | 4 +++- challenge-136/abigail/python/ch-1.py | 13 +++++++++---- challenge-136/abigail/r/ch-1.r | 15 ++++++++++----- challenge-136/abigail/ruby/ch-1.rb | 8 ++++++-- challenge-136/abigail/scheme/ch-1.scm | 12 ++++++++++-- challenge-136/abigail/tcl/ch-1.tcl | 12 ++++++++---- 15 files changed, 94 insertions(+), 26 deletions(-) diff --git a/challenge-136/abigail/awk/ch-1.gawk b/challenge-136/abigail/awk/ch-1.gawk index 12f563a4ea..0e8eb7d22a 100644 --- a/challenge-136/abigail/awk/ch-1.gawk +++ b/challenge-136/abigail/awk/ch-1.gawk @@ -37,6 +37,10 @@ function is_power_of_2 (number) { return is_power_of_n(number, 2) } +$1 % 2 || $2 % 2 { + print 0 + next +} { r = gcd($1, $2) diff --git a/challenge-136/abigail/bash/ch-1.sh b/challenge-136/abigail/bash/ch-1.sh index 857e3b7f7e..e965cbd96a 100644 --- a/challenge-136/abigail/bash/ch-1.sh +++ b/challenge-136/abigail/bash/ch-1.sh @@ -45,7 +45,11 @@ set -f while read n m -do gcd $n $m +do if ((n % 2 == 1 || m % 2 == 1)) + then echo 0 + continue + fi + gcd $n $m is_power_of_2 $gcd if ((gcd > 1 && is_power_of_2 == 1)) then echo 1 diff --git a/challenge-136/abigail/bc/ch-1.bc b/challenge-136/abigail/bc/ch-1.bc index 9a0c347386..a32d801dd8 100644 --- a/challenge-136/abigail/bc/ch-1.bc +++ b/challenge-136/abigail/bc/ch-1.bc @@ -28,8 +28,12 @@ define q (n) { while (1) { n = read (); if (n == 0) {break} m = read (); if (m == 0) {break} - r = g (n, m) - r > 1 && q (r) + if (n % 2 == 1 || m % 2 == 1) { + 0 + } else { + r = g (n, m) + r > 1 && q (r) + } } quit diff --git a/challenge-136/abigail/c/ch-1.c b/challenge-136/abigail/c/ch-1.c index d6fcc4d898..3c169dd635 100644 --- a/challenge-136/abigail/c/ch-1.c +++ b/challenge-136/abigail/c/ch-1.c @@ -45,6 +45,10 @@ int main (void) { long long n, m; while (scanf ("%lld %lld", &n, &m) == 2) { + if (n % 2 || m % 2) { + printf ("0\n"); + continue; + } long long r = gcd (n, m); printf ("%d\n", r > 1 && is_power_of_2 (r) ? 1 : 0); } diff --git a/challenge-136/abigail/go/ch-1.go b/challenge-136/abigail/go/ch-1.go index 6c9e59ab1b..18e85a5dba 100644 --- a/challenge-136/abigail/go/ch-1.go +++ b/challenge-136/abigail/go/ch-1.go @@ -46,6 +46,10 @@ func main () { if c != 2 || err != nil { break; } + if n % 2 == 1 || m % 2 == 1 { + fmt . Print ("0\n") + continue + } if r := gcd (m, n); r > 1 && is_power_of_2 (r) { fmt . Print ("1\n") } else { diff --git a/challenge-136/abigail/java/ch-1.java b/challenge-136/abigail/java/ch-1.java index 4fbc1db180..639ef643ca 100644 --- a/challenge-136/abigail/java/ch-1.java +++ b/challenge-136/abigail/java/ch-1.java @@ -46,6 +46,11 @@ public class ch1 { while (scanner . hasNextInt ()) { int n = scanner . nextInt (); int m = scanner . nextInt (); + + if (n % 2 == 1 || m % 2 == 1) { + System . out . println ("0"); + continue; + } int r = gcd (n, m); diff --git a/challenge-136/abigail/lua/ch-1.lua b/challenge-136/abigail/lua/ch-1.lua index 44ea00f251..369ee72246 100644 --- a/challenge-136/abigail/lua/ch-1.lua +++ b/challenge-136/abigail/lua/ch-1.lua @@ -31,10 +31,17 @@ end for line in io . lines () do local _, _, n, m = line : find ("([0-9]+)%s+([0-9]+)") - local r = gcd (tonumber (n), tonumber (m)) + n = tonumber (n) + m = tonumber (m) + if n % 2 == 1 or m % 2 == 1 then + print (0) + goto continue + end + local r = gcd (n, m) if r > 1 and is_power_of_2 (r) then print (1) else print (0) end + ::continue:: end diff --git a/challenge-136/abigail/node/ch-1.js b/challenge-136/abigail/node/ch-1.js index af49fa3977..4398a98d5a 100644 --- a/challenge-136/abigail/node/ch-1.js +++ b/challenge-136/abigail/node/ch-1.js @@ -33,6 +33,10 @@ function is_power_of_2 (number) { . createInterface ({input: process . stdin}) . on ('line', line => { let [m, n] = line . trim () . split (' ') . map (x => +x) + if (n % 2 == 1 || m % 2 == 1) { + console . log (0) + return + } let r = gcd (m, n) if (r > 1 && is_power_of_2 (r)) { console . log (1) diff --git a/challenge-136/abigail/pascal/ch-1.p b/challenge-136/abigail/pascal/ch-1.p index 391a4fe69f..08004bf17b 100644 --- a/challenge-136/abigail/pascal/ch-1.p +++ b/challenge-136/abigail/pascal/ch-1.p @@ -55,10 +55,14 @@ var begin while (not eof) do begin readln (m, n); - r := gcd (m, n); - if (r > 1) and is_power_of_2 (r) then - writeln (1) - else + if (n mod 2 = 1) or (m mod 2 = 1) then writeln (0) + else begin + r := gcd (m, n); + if (r > 1) and is_power_of_2 (r) then + writeln (1) + else + writeln (0) + end end end. diff --git a/challenge-136/abigail/perl/ch-1.pl b/challenge-136/abigail/perl/ch-1.pl index ac0b598577..0c060f0299 100644 --- a/challenge-136/abigail/perl/ch-1.pl +++ b/challenge-136/abigail/perl/ch-1.pl @@ -59,6 +59,8 @@ sub is_power_of_2 ($number) { # Main program # while (<>) { - my $r = gcd split; + my ($n, $m) = split; + say (0), next if ($n % 2) || ($m % 2); + my $r = gcd $n, $m; say $r > 1 && is_power_of_2 ($r) ? 1 : 0 } diff --git a/challenge-136/abigail/python/ch-1.py b/challenge-136/abigail/python/ch-1.py index 0c27429811..231e541d93 100644 --- a/challenge-136/abigail/python/ch-1.py +++ b/challenge-136/abigail/python/ch-1.py @@ -25,8 +25,13 @@ def is_power_of_2 (number): for line in fileinput . input (): m, n = line . strip () . split (' ') - r = math . gcd (int (m), int (n)) - if r > 1 and is_power_of_2 (r): - print (1) - else: + m = int (m) + n = int (n) + if m % 2 or n % 2: print (0) + else: + r = math . gcd (m, n) + if r > 1 and is_power_of_2 (r): + print (1) + else: + print (0) diff --git a/challenge-136/abigail/r/ch-1.r b/challenge-136/abigail/r/ch-1.r index 1231a1c2a8..851c753f4e 100644 --- a/challenge-136/abigail/r/ch-1.r +++ b/challenge-136/abigail/r/ch-1.r @@ -42,12 +42,17 @@ repeat { m <- as.numeric (parts [[1]] [[1]]) n <- as.numeric (parts [[1]] [[2]]) - r <- gcd (n, m) - - if (r > 1 & is_power_of_2 (r)) { - cat ("1\n") + if (n %% 2 == 1 | m %% 2 == 1) { + cat ("0\n") } else { - cat ("0\n") + r <- gcd (n, m) + + if (r > 1 & is_power_of_2 (r)) { + cat ("1\n") + } + else { + cat ("0\n") + } } } diff --git a/challenge-136/abigail/ruby/ch-1.rb b/challenge-136/abigail/ruby/ch-1.rb index aa050a843e..37e005400c 100644 --- a/challenge-136/abigail/ruby/ch-1.rb +++ b/challenge-136/abigail/ruby/ch-1.rb @@ -22,6 +22,10 @@ end ARGF . each_line do | line | m, n = line . split . map {|x| x . to_i} - r = m . gcd (n) - puts (r > 1 && is_power_of_2(r) ? 1 : 0) + if n % 2 == 1 || m % 2 == 1 then + puts (0) + else + r = m . gcd (n) + puts (r > 1 && is_power_of_2(r) ? 1 : 0) + end end diff --git a/challenge-136/abigail/scheme/ch-1.scm b/challenge-136/abigail/scheme/ch-1.scm index d537b754e0..aa6b75705a 100644 --- a/challenge-136/abigail/scheme/ch-1.scm +++ b/challenge-136/abigail/scheme/ch-1.scm @@ -44,8 +44,16 @@ (define r) (if (not (eof-object? m)) (begin - (set! r (gcd m n)) - (display (if (and (> r 1) (is-power-of-2 r)) 1 0)) + (display (cond ((= (modulo n 2) 1) 0) + ((= (modulo m 2) 1) 0) + (else + (begin + (set! r (gcd m n)) + (if (and (> r 1) (is-power-of-2 r)) 1 0) + ) + ) + ) + ) (newline) (main) ) diff --git a/challenge-136/abigail/tcl/ch-1.tcl b/challenge-136/abigail/tcl/ch-1.tcl index 39210c7e16..af5a72a3ea 100644 --- a/challenge-136/abigail/tcl/ch-1.tcl +++ b/challenge-136/abigail/tcl/ch-1.tcl @@ -47,10 +47,14 @@ proc is_power_of_2 {number} { while {[gets stdin line] >= 0} { lassign [split $line " "] m n - set r [gcd $m $n] - if {$r > 1 && [is_power_of_2 $r]} { - puts 1 - } else { + if {[expr $m % 2] == 1 || [expr $n % 2] == 1} { puts 0 + } else { + set r [gcd $m $n] + if {$r > 1 && [is_power_of_2 $r]} { + puts 1 + } else { + puts 0 + } } } -- cgit From b90fe902e06fa33e66b75c3408a988812f93c3ed Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Fri, 29 Oct 2021 18:36:57 +0200 Subject: Task solved as PostgreSQL functions --- challenge-136/luca-ferrari/postgresql/ch-1.sql | 24 +++++++++++++++++++ challenge-136/luca-ferrari/postgresql/ch-2.sql | 33 ++++++++++++++++++++++++++ 2 files changed, 57 insertions(+) create mode 100644 challenge-136/luca-ferrari/postgresql/ch-1.sql create mode 100644 challenge-136/luca-ferrari/postgresql/ch-2.sql diff --git a/challenge-136/luca-ferrari/postgresql/ch-1.sql b/challenge-136/luca-ferrari/postgresql/ch-1.sql new file mode 100644 index 0000000000..ed1f0c71a0 --- /dev/null +++ b/challenge-136/luca-ferrari/postgresql/ch-1.sql @@ -0,0 +1,24 @@ +/* +testdb=> SELECT FRIENDLY( 26, 39 ); +friendly +---------- +0 +(1 row) + +testdb=> SELECT FRIENDLY( 26, 52 ); +friendly +---------- +1 +(1 row) + +*/ +CREATE OR REPLACE FUNCTION friendly( m int, n int ) +RETURNS int +AS $CODE$ + SELECT + CASE gcd( m, n ) % 2 + WHEN 0 THEN 1 + ELSE 0 + END; +$CODE$ +LANGUAGE SQL; diff --git a/challenge-136/luca-ferrari/postgresql/ch-2.sql b/challenge-136/luca-ferrari/postgresql/ch-2.sql new file mode 100644 index 0000000000..e1f6439ec0 --- /dev/null +++ b/challenge-136/luca-ferrari/postgresql/ch-2.sql @@ -0,0 +1,33 @@ +CREATE OR REPLACE FUNCTION fibonacci_sum( l int DEFAULT 16 ) +RETURNS bigint +AS $CODE$ + +WITH RECURSIVE +fibonacci( n, p ) AS +( + SELECT 1, 1 + UNION + SELECT p + n, n + FROM fibonacci + WHERE n < l +) +, permutations AS +( + SELECT n::text AS current_value, n as total_sum + FROM fibonacci + UNION + SELECT current_value || ',' || n, total_sum + n + FROM permutations, fibonacci + WHERE + position( n::text in current_value ) = 0 + AND n > ALL( string_to_array( current_value, ',' )::int[] ) + + +) +SELECT count(*) +FROM permutations +WHERE total_sum = l +; + +$CODE$ +LANGUAGE SQL; -- cgit From 70cd62f9a8258b22cd2d385fa65c265e6f6423f1 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Fri, 29 Oct 2021 18:57:00 +0200 Subject: Blog references to the PostgreSQL solutions --- challenge-136/luca-ferrari/blog-3.txt | 1 + challenge-136/luca-ferrari/blog-4.txt | 1 + 2 files changed, 2 insertions(+) create mode 100644 challenge-136/luca-ferrari/blog-3.txt create mode 100644 challenge-136/luca-ferrari/blog-4.txt diff --git a/challenge-136/luca-ferrari/blog-3.txt b/challenge-136/luca-ferrari/blog-3.txt new file mode 100644 index 0000000000..fd8dbeb710 --- /dev/null +++ b/challenge-136/luca-ferrari/blog-3.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2021/10/29/PerlWeeklyChallenge136PostgreSQL.html#task1 diff --git a/challenge-136/luca-ferrari/blog-4.txt b/challenge-136/luca-ferrari/blog-4.txt new file mode 100644 index 0000000000..f9b68dd456 --- /dev/null +++ b/challenge-136/luca-ferrari/blog-4.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2021/10/29/PerlWeeklyChallenge136PostgreSQL.html#task2 -- cgit From 0eda758bb14b0a50fcbced7b0c19fb6cfb291761 Mon Sep 17 00:00:00 2001 From: "E. Choroba" Date: Fri, 29 Oct 2021 20:41:21 +0200 Subject: Add DP solution to 136/2 --- challenge-136/e-choroba/perl/ch-2.pl | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) diff --git a/challenge-136/e-choroba/perl/ch-2.pl b/challenge-136/e-choroba/perl/ch-2.pl index 475a906652..40a1f711e7 100755 --- a/challenge-136/e-choroba/perl/ch-2.pl +++ b/challenge-136/e-choroba/perl/ch-2.pl @@ -5,7 +5,7 @@ use strict; use List::Util qw{ sum }; my @F = (1, 2); -sub fibonacci_sequence { +sub fibonacci_sequence_indicator { my ($n) = @_; my $count = 0; my $indicator = 1; @@ -21,8 +21,30 @@ sub fibonacci_sequence { return $count } +my %fs = (1 => [[1]], 2 => [[2]]); +sub fs_dynamic { + my ($n) = @_; + return @{ $fs{$n} } if exists $fs{$n}; + + push @F, $F[-2] + $F[-1] while $F[-1] < $n; + my @result; + for my $f (grep $_ <= $n, @F) { + no warnings 'recursion'; + my @without = grep { ! grep $_ == $f, @$_ } fs_dynamic($n - $f); + next if @without && $f < $without[0][0]; + + push @result, map [$f, @$_], @without; + push @result, [$f] if $n == $f; + } + return @{ $fs{$n} = \@result } +} + +sub fibonacci_sequence { + scalar fs_dynamic(@_) +} + use Test2::V0; -plan 52; +plan 118; is fibonacci_sequence(16), 4, 'Example 1'; is fibonacci_sequence(9), 2, 'Example 2'; @@ -47,6 +69,7 @@ is fibonacci_sequence(29), 5, 'Check 29'; is fibonacci_sequence(30), 3, 'Check 30'; is fibonacci_sequence(31), 3, 'Check 31'; is fibonacci_sequence(32), 4, 'Check 32'; + is fibonacci_sequence(33), 1, 'Check 33'; is fibonacci_sequence(34), 4, 'Check 34'; is fibonacci_sequence(35), 4, 'Check 35'; @@ -80,3 +103,6 @@ is fibonacci_sequence(62), 3, 'Check 62'; is fibonacci_sequence(63), 8, 'Check 63'; is fibonacci_sequence(64), 5, 'Check 64'; is fibonacci_sequence(65), 5, 'Check 65'; + +is fibonacci_sequence($_), fibonacci_sequence_indicator($_), "same $_" + for 1 .. 65, 1234; -- cgit From 14a1b81924ec23b65d4d1da7ca6f742b8494ebed Mon Sep 17 00:00:00 2001 From: Abigail Date: Fri, 29 Oct 2021 20:46:03 +0200 Subject: Use longint instead integer. Integers can be as small as 16bits; longints are 32bits. --- challenge-136/abigail/pascal/ch-1.p | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/challenge-136/abigail/pascal/ch-1.p b/challenge-136/abigail/pascal/ch-1.p index 08004bf17b..7c3e122dee 100644 --- a/challenge-136/abigail/pascal/ch-1.p +++ b/challenge-136/abigail/pascal/ch-1.p @@ -12,7 +12,7 @@ Program XXX; (* Find the GCD, using Stein's algorithm *) (* (https://en.wikipedia.org/wiki/Binary_GCD_algorithm) *) (* *) -function gcd (u, v: integer): integer; +function gcd (u, v: longint): longint; var u_odd, v_odd: boolean; @@ -34,7 +34,7 @@ function gcd (u, v: integer): integer; (* Return true if number is a power of n, that is, number == n ^ p *) (* for some non-negative integer p. Return false otherwise. *) (* *) -function is_power_of_n (number, n: integer): boolean; +function is_power_of_n (number, n: longint): boolean; begin if number < 1 then is_power_of_n := false else if number = 1 then is_power_of_n := true @@ -42,7 +42,7 @@ function is_power_of_n (number, n: integer): boolean; else is_power_of_n := is_power_of_n (number div n, n); end; -function is_power_of_2 (number: integer): boolean; +function is_power_of_2 (number: longint): boolean; begin is_power_of_2 := is_power_of_n (number, 2); end; @@ -50,7 +50,7 @@ function is_power_of_2 (number: integer): boolean; var - m, n, r: integer; + m, n, r: longint; begin while (not eof) do begin -- cgit From 8d617f0b82a667a72a48233d2bde1bdd6bc1144d Mon Sep 17 00:00:00 2001 From: PerlMonk-Athanasius Date: Sat, 30 Oct 2021 22:05:06 +1000 Subject: Perl & Raku solutions to Tasks 1 & 2 of the Perl Weekly Challenge #136 --- challenge-136/athanasius/perl/ch-1.pl | 157 +++++++++++++++++++++++ challenge-136/athanasius/perl/ch-2.pl | 213 ++++++++++++++++++++++++++++++++ challenge-136/athanasius/raku/ch-1.raku | 122 ++++++++++++++++++ challenge-136/athanasius/raku/ch-2.raku | 176 ++++++++++++++++++++++++++ 4 files changed, 668 insertions(+) create mode 100644 challenge-136/athanasius/perl/ch-1.pl create mode 100644 challenge-136/athanasius/perl/ch-2.pl create mode 100644 challenge-136/athanasius/raku/ch-1.raku create mode 100644 challenge-136/athanasius/raku/ch-2.raku diff --git a/challenge-136/athanasius/perl/ch-1.pl b/challenge-136/athanasius/perl/ch-1.pl new file mode 100644 index 0000000000..f76757eb3f --- /dev/null +++ b/challenge-136/athanasius/perl/ch-1.pl @@ -0,0 +1,157 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 136 +========================= + +TASK #1 +------- +*Two Friendly* + +Submitted by: Mohammad S Anwar + +You are given 2 positive numbers, $m and $n. + +Write a script to find out if the given two numbers are Two Friendly. + + Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^ p where + p > 0. The greatest common divisor (gcd) of a set of numbers is the largest + positive number that divides all the numbers in the set without remainder. + +Example 1 + + Input: $m = 8, $n = 24 + Output: 1 + + Reason: gcd(8,24) = 8 => 2 ^ 3 + +Example 2 + + Input: $m = 26, $n = 39 + Output: 0 + + Reason: gcd(26,39) = 13 + +Example 3 + + Input: $m = 4, $n = 10 + Output: 1 + + Reason: gcd(4,10) = 2 => 2 ^ 1 + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2021 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Interface +--------- +Include the flag "--verbose" (or just "-v") on the command line to display an +explanation of the output. + +Implementation +-------------- +Calculation of the greatest common divisor is delegated to the gcd() subroutine +in the ntheory (aka Math::Prime::Util) module. + +=cut +#============================================================================== + +use strict; +use warnings; +use Const::Fast; +use Getopt::Long; +use ntheory qw( gcd ); +use Regexp::Common qw( number ); + +const my $USAGE => +"Usage: + perl $0 [--verbose|-v] + + --verbose Explain the output? + An integer > 0 + An integer > 0\n"; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 136, Task #1: Two Friendly (Perl)\n\n"; +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my ($verbose, $m, $n) = parse_command_line(); + + print "Input: \$m = $m, \$n = $n\n"; + + my $friendly = 0; + my $reason = 'not a power of 2'; + my $gcd = gcd( $m, $n ); + + if ($gcd == 1) + { + $reason = '2 ^ 0'; + } + else + { + my $log2 = int( (log( $gcd ) / log( 2 )) + 0.5 ); + + if ($gcd == 2 ** $log2) + { + $friendly = 1; + $reason = "2 ^ $log2"; + } + } + + printf "Output: %d\n", $friendly ? 1 : 0; + + print "\nReason: gcd($m, $n) = $gcd which is $reason\n" if $verbose; +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + my $verbose = 0; + + GetOptions( verbose => \$verbose ) + or error( 'Invalid command line flag' ); + + my $args = scalar @ARGV; + $args == 2 + or error( "Expected 2 command line arguments, found $args" ); + + my ($m, $n) = @ARGV; + + for ($m, $n) + { + / ^ $RE{num}{int} $ /x + or error( qq["$_" is not a valid integer] ); + + $_ > 0 or error( qq["$_" is not greater than zero] ); + } + + return ($verbose, $m, $n); +} + +#------------------------------------------------------------------------------ +sub error +#------------------------------------------------------------------------------ +{ + my ($message) = @_; + + die "ERROR: $message\n$USAGE"; +} + +############################################################################### diff --git a/challenge-136/athanasius/perl/ch-2.pl b/challenge-136/athanasius/perl/ch-2.pl new file mode 100644 index 0000000000..ed97d62121 --- /dev/null +++ b/challenge-136/athanasius/perl/ch-2.pl @@ -0,0 +1,213 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 136 +========================= + +TASK #2 +------- +*Fibonacci Sequence* + +Submitted by: Mohammad S Anwar + +You are given a positive number $n. + +Write a script to find how many different sequences you can create using +Fibonacci numbers where the sum of unique numbers in each sequence are the same +as the given number. + + Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89, … + +Example 1 + + Input: $n = 16 + Output: 4 + + Reason: There are 4 possible sequences that can be created using Fibonacci + numbers i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8). + +Example 2 + + Input: $n = 9 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci + numbers i.e. (1 + 3 + 5) and (1 + 8). + +Example 3 + + Input: $n = 15 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci + numbers i.e. (2 + 5 + 8) and (2 + 13). + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2021 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Interface +--------- +Include the flag "--verbose" (or just "-v") on the command line to display an +explanation of the output. + +Algorithm +--------- +1. Find the set F of Fibonacci numbers less than or equal to $n +2. Calculate the power set P(F) of all subsets of F +3. For each subset S in P(F), sum the elements of S and add S to the solution + set iff the sum equals $n + +Note: This algorithm works well for smaller values of $n, but will not scale +well for larger values. + +Implementation +-------------- +Calculation of the power set is delegated to the subsets() subroutine of module +Algorithm::Combinatorics. See: + https://rosettacode.org/wiki/Power_set#Module:_Algorithm::Combinatorics + +=cut +#============================================================================== + +use strict; +use warnings; +use Algorithm::Combinatorics qw( subsets ); +use Const::Fast; +use Getopt::Long; +use Regexp::Common qw( number ); + +const my $USAGE => +"Usage: + perl $0 [--verbose|-v] + + --verbose Explain the output? + An integer > 0\n"; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 136, Task #2: Fibonacci Sequence (Perl)\n\n"; +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my ($verbose, $n) = parse_command_line(); + + print "Input: \$n = $n\n"; + + my $seqs = find_fib_seqs( $n ); + my $count = scalar @$seqs; + + print "Output: $count\n"; + + if ($verbose) + { + if ($count == 0) + { + print "\nReason: There are no possible sequences summing to $n" . + "\n\tthat can be created using unique Fibonacci numbers\n"; + } + elsif ($count == 1) + { + printf "\nReason: There is one possible sequence summing to %d" . + "\n\tthat can be created using unique Fibonacci numbers:" . + "\n\t(%s)\n", $n, join ' + ', @{ $seqs->[ 0 ] }; + } + else + { + printf "\nReason: There are %d possible sequences summing to %d" . + "\n\tthat can be created using unique Fibonacci numbers:\n", + $count, $n; + + printf "\t(%s)\n", join ' + ', @$_ for @$seqs; + } + } +} + +#------------------------------------------------------------------------------ +sub find_fib_seqs +#------------------------------------------------------------------------------ +{ + my ($n) = @_; + my @seqs; + my $fibs = get_fib_nums( $n ); + my $iter = subsets( $fibs ); + + while (my $p = $iter->next) + { + my $sum = 0; + $sum += $_ for @$p; + + push @seqs, $p if $sum == $n; + } + + return \@seqs; +} + +#------------------------------------------------------------------------------ +sub get_fib_nums +#------------------------------------------------------------------------------ +{ + my ($n) = @_; + my @fibs = (1); + my ($x, $y) = (1, 1); + + while ($fibs[ -1 ] < $n) + { + my $z = $x + $y; + push @fibs, $z; + $x = $y; + $y = $z; + } + + pop @fibs if $fibs[ -1 ] > $n; + + return \@fibs; +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + my $verbose = 0; + + GetOptions( verbose => \$verbose ) + or error( 'Invalid command line flag' ); + + my $args = scalar @ARGV; + $args == 1 + or error( "Expected 1 command line argument, found $args" ); + + my $n = $ARGV[ 0 ]; + + $n =~ / ^ $RE{num}{int} $ /x + or error( qq["$n" is not a valid integer] ); + + $n > 0 or error( qq["$n" is not greater than zero] ); + + return ($verbose, $n); +} + +#------------------------------------------------------------------------------ +sub error +#------------------------------------------------------------------------------ +{ + my ($message) = @_; + + die "ERROR: $message\n$USAGE"; +} + +############################################################################### diff --git a/challenge-136/athanasius/raku/ch-1.raku b/challenge-136/athanasius/raku/ch-1.raku new file mode 100644 index 0000000000..8aed05ef23 --- /dev/null +++ b/challenge-136/athanasius/raku/ch-1.raku @@ -0,0 +1,122 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 136 +========================= + +TASK #1 +------- +*Two Friendly* + +Submitted by: Mohammad S Anwar + +You are given 2 positive numbers, $m and $n. + +Write a script to find out if the given two numbers are Two Friendly. + + Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^ p where + p > 0. The greatest common divisor (gcd) of a set of numbers is the largest + positive number that divides all the numbers in the set without remainder. + +Example 1 + + Input: $m = 8, $n = 24 + Output: 1 + + Reason: gcd(8,24) = 8 => 2 ^ 3 + +Example 2 + + Input: $m = 26, $n = 39 + Output: 0 + + Reason: gcd(26,39) = 13 + +Example 3 + + Input: $m = 4, $n = 10 + Output: 1 + + Reason: gcd(4,10) = 2 => 2 ^ 1 + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2021 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Interface +--------- +Include the flag "--verbose" on the command line to display an explanation of +the output. + +Implementation +-------------- +Calculation of the greatest common divisor is performed by Raku's inbuilt infix +operator "gcd". + +=end comment +#============================================================================== + +subset Positive of Int where * > 0; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 136, Task #1: Two Friendly (Raku)\n".put; +} + +#============================================================================== +sub MAIN +( + Positive:D $m, #= An integer > 0 + Positive:D $n, #= An integer > 0 + Bool:D :$verbose = False #= Explain the output? +) +#============================================================================== +{ + "Input: \$m = $m, \$n = $n".put; + + my Bool $friendly = False; + my Str $reason = 'not a power of 2'; + my Positive $gcd = $m gcd $n; + + if $gcd == 1 + { + $reason = '2 ^ 0'; + } + else + { + my Int $log2 = ($gcd.log2 + 0.5).Int; + + if $gcd == 2 ** $log2 + { + $friendly = True; + $reason = "2 ^ $log2"; + } + } + + "Output: %d\n".printf: $friendly ?? 1 !! 0; + + "\nReason: gcd($m, $n) = $gcd which is $reason".put if $verbose; +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/; + + $usage.put; +} + +############################################################################## diff --git a/challenge-136/athanasius/raku/ch-2.raku b/challenge-136/athanasius/raku/ch-2.raku new file mode 100644 index 0000000000..653d86afe8 --- /dev/null +++ b/challenge-136/athanasius/raku/ch-2.raku @@ -0,0 +1,176 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 136 +========================= + +TASK #2 +------- +*Fibonacci Sequence* + +Submitted by: Mohammad S Anwar + +You are given a positive number $n. + +Write a script to find how many different sequences you can create using +Fibonacci numbers where the sum of unique numbers in each sequence are the same +as the given number. + + Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89, … + +Example 1 + + Input: $n = 16 + Output: 4 + + Reason: There are 4 possible sequences that can be created using Fibonacci + numbers i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8). + +Example 2 + + Input: $n = 9 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci + numbers i.e. (1 + 3 + 5) and (1 + 8). + +Example 3 + + Input: $n = 15 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci + numbers i.e. (2 + 5 + 8) and (2 + 13). + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2021 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Interface +--------- +Include the flag "--verbose" on the command line to display an explanation of +the output. + +Algorithm +--------- +1. Find the set F of Fibonacci numbers less than or equal to $n +2. Calculate the power set P(F) of all subsets of F +3. For each subset S in P(F), sum the elements of S and add S to the solution + set iff the sum equals $n + +Note: This algorithm works well for smaller values of $n, but will not scale +well for larger values. + +Implementation +-------------- +Calculation of the power set is performed by Raku's inbuilt combinations() +method. + +=end comment +#============================================================================== + +subset Pos of Int where * > 0; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 136, Task #2: Fibonacci Sequence (Raku)\n".put; +} + +#============================================================================== +sub MAIN +( + Pos:D $n, #= An integer > 0 + Bool:D :$verbose = False #= Explain the output? +) +#============================================================================== +{ + "Input: \$n = $n".put; + + my Array[Pos] @seqs = find-fib-seqs( $n ); + my UInt $count = @seqs.elems; + + "Output: $count".put; + + if $verbose + { + if $count == 0 + { + ("\nReason: There are no possible sequences summing to $n" ~ + "\n\tthat can be created using unique Fibonacci numbers").put; + } + elsif $count == 1 + { + ("\nReason: There is one possible sequence summing to $n" ~ + "\n\tthat can be created using unique Fibonacci numbers:" ~ + "\n\t(%s)\n").printf: @seqs[ 0 ].join: ' + '; + } + else + { + ("\nReason: There are $count possible sequences summing to $n" ~ + "\n\tthat can be created using unique Fibonacci numbers:").put; + + "\t(%s)\n".printf: $_.join: ' + ' for @seqs; + } + } +} + +#------------------------------------------------------------------------------ +sub find-fib-seqs( Pos:D $n --> Array:D[Array:D[Pos:D]] ) +#------------------------------------------------------------------------------ +{ + my Array[Pos] @seqs; + my Array[Pos] $fibs = get-fib-nums( $n ); + + for $fibs.combinations: 1 .. * -> List $c + { + my UInt $sum = [+] @$c; # Sum using reduction metaoperator + + @seqs.push: Array[Pos].new: @$c if $sum == $n; + } + + return @seqs; +} + +#------------------------------------------------------------------------------ +sub get-fib-nums( Pos:D $n --> Array:D[Pos:D] ) +#------------------------------------------------------------------------------ +{ + my Pos @fibs = 1; + my Pos ($x, $y) = (1, 1); + + while @fibs[ *-1 ] < $n + { + my Pos $z = $x + $y; + + @fibs.push: $z; + + $x = $y; + $y = $z; + } + + @fibs.pop if @fibs[ *-1 ] > $n; + + return @fibs; +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/; + $usage.put; +} + +############################################################################## -- cgit From 9890eb4d1023c0a56da3652c1c60128b5a84eee8 Mon Sep 17 00:00:00 2001 From: James Smith Date: Sat, 30 Oct 2021 16:05:28 +0100 Subject: Create blog.txt --- challenge-134/james-smith/blog.txt | 1 + 1 file changed, 1 insertion(+) create mode 100644 challenge-134/james-smith/blog.txt diff --git a/challenge-134/james-smith/blog.txt b/challenge-134/james-smith/blog.txt new file mode 100644 index 0000000000..515dacf030 --- /dev/null +++ b/challenge-134/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/tree/master/challenge-134/james-smith -- cgit From 9c34496daf88ee295dc4e14d8afb9569560d632e Mon Sep 17 00:00:00 2001 From: Matthew Neleigh Date: Sat, 30 Oct 2021 12:24:36 -0400 Subject: new file: challenge-136/mattneleigh/perl/ch-1.pl --- challenge-136/mattneleigh/perl/ch-1.pl | 84 ++++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) create mode 100755 challenge-136/mattneleigh/perl/ch-1.pl diff --git a/challenge-136/mattneleigh/perl/ch-1.pl b/challenge-136/mattneleigh/perl/ch-1.pl new file mode 100755 index 0000000000..31a755832a --- /dev/null +++ b/challenge-136/mattneleigh/perl/ch-1.pl @@ -0,0 +1,84 @@ +#!/usr/bin/perl + +use strict; +use warnings; +use English; + +################################################################################ +# Begin main execution +################################################################################ + +my @pairs = ( + [ 8, 24 ], + [ 26, 39 ], + [ 4, 10 ] +); +my $pair; + +foreach $pair (@pairs){ + print(" Input: \$m = $pair->[0], \$n = $pair->[1]\n"); + print(" Output: ", two_friendly(@{$pair}), "\n\n\n"); +} + +exit(0); +################################################################################ +# End main execution; subroutines follow +################################################################################ + + + +################################################################################ +# Determine of two integers are Two Friendly (their Greatest Common Divisor is +# a Power of Two) +# Takes two arguments: +# * An integer M +# * An integer N +# Returns: +# * 1 if M and N are Two Friendly +# * 0 if M and N are NOT Two Friendly +################################################################################ +sub two_friendly{ + my $m = int(shift()); + my $n = int(shift()); + + my $power_two; + + # Compute the power of two of the greatest + # common divisor + $power_two = log(gcd($m, $n)) / log(2); + + # If $power_two looks like an integer + # (accounting for round-off error...) then + # the GCD of $m and $n was a power of two + if(abs($power_two - int($power_two)) < 0.0000000001){ + return(1); + } else{ + return(0); + } + +} + + + +################################################################################ +# Compute the Greatest Common Denominator (GCD) of two integers +# Takes two arguments: +# * An integer A +# * An integer B +# Returns: +# * The GCD of A and B +################################################################################ +sub gcd{ + my $a = shift(); + my $b = shift(); + + if($b){ + return(gcd($b, $a % $b)); + } else{ + return($a); + } + +} + + + -- cgit From c0c3c19fee82da1d819b3c8a61a6c45e48449c75 Mon Sep 17 00:00:00 2001 From: dcw Date: Sat, 30 Oct 2021 21:57:43 +0100 Subject: imported my solutions to this week's challenges; two nice tasks --- challenge-136/duncan-c-white/README | 75 +++++++++++------- challenge-136/duncan-c-white/perl/ch-1.pl | 74 ++++++++++++++++++ challenge-136/duncan-c-white/perl/ch-2.pl | 124 ++++++++++++++++++++++++++++++ 3 files changed, 246 insertions(+), 27 deletions(-) create mode 100755 challenge-136/duncan-c-white/perl/ch-1.pl create mode 100755 challenge-136/duncan-c-white/perl/ch-2.pl diff --git a/challenge-136/duncan-c-white/README b/challenge-136/duncan-c-white/README index 9e73de07f7..c41627048b 100644 --- a/challenge-136/duncan-c-white/README +++ b/challenge-136/duncan-c-white/README @@ -1,56 +1,77 @@ -TASK #1 - Middle 3-digits +TASK #1 - Two Friendly -You are given an integer. +You are given 2 positive numbers, $m and $n. -Write a script find out the middle 3-digits of the given integer, if -possible otherwise throw sensible error. +Write a script to find out if the given two numbers are Two Friendly. + +Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^ +p where p > 0. The greatest common divisor (gcd) of a set of numbers +is the largest positive number that divides all the numbers in the set +without remainder. Example 1 - Input: $n = 1234567 - Output: 345 + Input: $m = 8, $n = 24 + Output: 1 + + Reason: gcd(8,24) = 8 => 2 ^ 3 Example 2 - Input: $n = -123 - Output: 123 + Input: $m = 26, $n = 39 + Output: 0 -Example 3 + Reason: gcd(26,39) = 13 - Input: $n = 1 - Output: too short +Example 3 -Example 4 + Input: $m = 4, $n = 10 + Output: 1 - Input: $n = 10 - Output: even number of digits + Reason: gcd(4,10) = 2 => 2 ^ 1 -MY NOTES: Pretty easy, although it's not clear how to always treat negative numbers. -Assume abs() them. +MY NOTES: Pretty easy. Euclid's GCD algorithm, then check if the result is a power of 2. -TASK #2 - Validate SEDOL +TASK #2 - Fibonacci Sequence -You are given 7-characters alphanumeric SEDOL. +You are given a positive number $n. -Write a script to validate the given SEDOL. Print 1 if it is a valid SEDOL otherwise 0. +Write a script to find how many different sequences you can create using +Fibonacci numbers where the sum of unique numbers in each sequence are +the same as the given number. -For more information about SEDOL, please checkout https://en.wikipedia.org/wiki/SEDOL + Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89,.. Example 1 - Input: $SEDOL = '2936921' - Output: 1 + Input: $n = 16 + Output: 4 + + Reason: There are 4 possible sequences that can be created using Fibonacci numbers + i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8). Example 2 - Input: $SEDOL = '1234567' - Output: 0 + Input: $n = 9 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci numbers + i.e. (1 + 3 + 5) and (1 + 8). Example 3 - Input: $SEDOL = 'B0YBKL9' - Output: 1 + Input: $n = 15 + Output: 2 + + Reason: There are 2 possible sequences that can be created using Fibonacci numbers + i.e. (2 + 5 + 8) and (2 + 13). -MY NOTES: Pretty easy +MY NOTES: Pretty easy - find subsets of the first few Fibonacci numbers that sum to N. +How many Fibonacci numbers should we consider? Those <= N. Then, how do we sum subsets +of them? Two obvious ways: +1. recursive function, iterating over the Fibonacci values: each value is either in the + subset or not, try both possibilities. +2. binary-counting method, iterate over every combination C from 1 .. 2**(number values)-1, + then sum up only the elements where the corresponding bit in C is true. diff --git a/challenge-136/duncan-c-white/perl/ch-1.pl b/challenge-136/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..08e3486f2a --- /dev/null +++ b/challenge-136/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,74 @@ +#!/usr/bin/perl +# +# TASK #1 - Two Friendly +# +# You are given 2 positive numbers, $m and $n. +# +# Write a script to find out if the given two numbers are Two Friendly. +# +# Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^ +# p where p > 0. The greatest common divisor (gcd) of a set of numbers +# is the largest positive number that divides all the numbers in the set +# without remainder. +# +# Example 1 +# +# Input: $m = 8, $n = 24 +# Output: 1 +# +# Reason: gcd(8,24) = 8 => 2 ^ 3 +# +# Example 2 +# +# Input: $m = 26, $n = 39 +# Output: 0 +# +# Reason: gcd(26,39) = 13 +# +# Example 3 +# +# Input: $m = 4, $n = 10 +# Output: 1 +# +# Reason: gcd(4,10) = 2 => 2 ^ 1 +# +# MY NOTES: Pretty easy. Euclid's GCD algorithm, then check if the result is a power of 2. +# + +use strict; +use warnings; +use feature 'say'; +use Getopt::Long; +use Function::Parameters; +#use Data::Dumper; + + +# +# my $gcd = gcd( $a, $b ); +# Compute and return the GCD (Greatest Common Denominator) of $a and $b. +# +fun gcd( $a, $b ) +{ + while( $b != 0 ) + { + ( $a, $b ) = ( $b, $a % $b ); + } + return $a; +} + + +my $debug=0; +die "Usage: 2-friendly N M\n" unless + GetOptions( "debug"=>\$debug ) && @ARGV==2; +my( $n, $m ) = @ARGV; + +my $gcd = gcd( $n, $m ); +say "gcd is $gcd" if $debug; + +my $ispower = 0; +for( my $twop = 2; $twop <= $gcd; $twop *= 2 ) +{ + $ispower++ if $twop == $gcd; +} + +say $ispower; diff --git a/challenge-136/duncan-c-white/perl/ch-2.pl b/challenge-136/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..d3a4cd88e7 --- /dev/null +++ b/challenge-136/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,124 @@ +#!/usr/bin/perl +# +# TASK #2 - Fibonacci Sequence +# +# You are given a positive number $n. +# +# Write a script to find how many different sequences you can create using +# Fibonacci numbers where the sum of unique numbers in each sequence are +# the same as the given number. +# +# Fibonacci Numb