From 4629e3f70fdf73637dc6d6d14b797ba92d9ef0b0 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 25 Oct 2021 10:41:25 +0200 Subject: Task 1 done --- challenge-136/luca-ferrari/raku/ch-1.p6 | 5 +++++ 1 file changed, 5 insertions(+) create mode 100755 challenge-136/luca-ferrari/raku/ch-1.p6 diff --git a/challenge-136/luca-ferrari/raku/ch-1.p6 b/challenge-136/luca-ferrari/raku/ch-1.p6 new file mode 100755 index 0000000000..aa3bf36984 --- /dev/null +++ b/challenge-136/luca-ferrari/raku/ch-1.p6 @@ -0,0 +1,5 @@ +#!raku + +sub MAIN( Int $m where { $m > 0 }, Int $n where { $n > 0 } ) { + ( [gcd] $m, $n ) %% 2 ?? '1'.say !! '0'.say; +} -- cgit From a3a4eab6b572853c0b3c1a27f2d5b1e129173977 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 25 Oct 2021 11:04:49 +0200 Subject: Task 2 done --- challenge-136/luca-ferrari/raku/ch-2.p6 | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100755 challenge-136/luca-ferrari/raku/ch-2.p6 diff --git a/challenge-136/luca-ferrari/raku/ch-2.p6 b/challenge-136/luca-ferrari/raku/ch-2.p6 new file mode 100755 index 0000000000..83a5227a9d --- /dev/null +++ b/challenge-136/luca-ferrari/raku/ch-2.p6 @@ -0,0 +1,22 @@ +#!raku + +sub MAIN( Int $n where { $n > 1 } ) { + my @fibonacci; + @fibonacci.push: 1, 1; + my %solutions; + + # compute a reduced fibonacci sequence up to the sum of the number given + @fibonacci.push: @fibonacci[ * - 1 ] + @fibonacci[ * - 2 ] while $n > ( @fibonacci[ * - 1] + @fibonacci[ * - 2 ]); + + + # iterate over all the available numbers, and compute the sum + # and if the sum does match, add the array to the hash of solutions + # with a stringified key representation + %solutions{ $_.join( ' + ') } = $_ if ( ( [+] $_ ) == $n ) for @fibonacci.combinations.unique; + + # print the number of keys + say %solutions.keys.elems; + # and print all the sums + .join( " + " ).say for %solutions.values; + +} -- cgit From 9b6c375110f64e808302a72de1d63c41b1fd56b7 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Fri, 22 Oct 2021 16:23:23 +0100 Subject: Add Perl and Python solutions to challenge 130 --- challenge-094/paulo-custodio/perl/ch-2.pl | 9 +- challenge-130/paulo-custodio/perl/ch-1.pl | 23 ++++++ challenge-130/paulo-custodio/perl/ch-2.pl | 122 ++++++++++++++++++++++++++++ challenge-130/paulo-custodio/python/ch-1.py | 29 +++++++ challenge-130/paulo-custodio/python/ch-2.py | 110 +++++++++++++++++++++++++ challenge-130/paulo-custodio/t/test-1.yaml | 10 +++ challenge-130/paulo-custodio/t/test-2.yaml | 20 +++++ challenge-130/paulo-custodio/test.pl | 4 + 8 files changed, 324 insertions(+), 3 deletions(-) create mode 100644 challenge-130/paulo-custodio/perl/ch-1.pl create mode 100644 challenge-130/paulo-custodio/perl/ch-2.pl create mode 100644 challenge-130/paulo-custodio/python/ch-1.py create mode 100644 challenge-130/paulo-custodio/python/ch-2.py create mode 100644 challenge-130/paulo-custodio/t/test-1.yaml create mode 100644 challenge-130/paulo-custodio/t/test-2.yaml create mode 100644 challenge-130/paulo-custodio/test.pl diff --git a/challenge-094/paulo-custodio/perl/ch-2.pl b/challenge-094/paulo-custodio/perl/ch-2.pl index 3ca9551cb4..fccddc0ebc 100644 --- a/challenge-094/paulo-custodio/perl/ch-2.pl +++ b/challenge-094/paulo-custodio/perl/ch-2.pl @@ -47,7 +47,7 @@ sub parse_tree { chomp(my @lines = <>); @lines or die "malformed tree\n"; $lines[0] =~ /^( +)\d/ or die "malformed tree\n"; - $tree = parse_subtree(\@lines, 0, length($1)); + my $tree = parse_subtree(\@lines, 0, length($1)); return $tree; } @@ -62,12 +62,15 @@ sub parse_subtree { # parse children if ($row+2 <= $#{$lines}) { # parse left subtree - if ($col-2 >= 0 && $col-2 < length($lines->[$row+1]) && substr($lines->[$row+1], $col-1, 1) eq '/') { + if ($col-2 >= 0 && + $col-2 < length($lines->[$row+1]) && + substr($lines->[$row+1], $col-1, 1) eq '/') { my $child = parse_subtree($lines, $row+2, $col-2); $node->left($child); } # parse right subtree - if ($col+2 < length($lines->[$row+2]) && substr($lines->[$row+1], $col+1, 1) eq '\\') { + if ($col+2 < length($lines->[$row+2]) && + substr($lines->[$row+1], $col+1, 1) eq '\\') { my $child = parse_subtree($lines, $row+2, $col+2); $node->right($child); } diff --git a/challenge-130/paulo-custodio/perl/ch-1.pl b/challenge-130/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..c3cb2c7384 --- /dev/null +++ b/challenge-130/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,23 @@ +#!/usr/bin/env perl + +# TASK #1 > Odd Number +# Submitted by: Mohammad S Anwar +# You are given an array of positive integers, such that all the +# numbers appear even number of times except one number. +# +# Write a script to find that integer. +# +# Example 1 +# Input: @N = (2, 5, 4, 4, 5, 5, 2) +# Output: 5 as it appears 3 times in the array where as all other +# numbers 2 and 4 appears exactly twice. +# Example 2 +# Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4) +# Output: 4 + +use Modern::Perl; + +my @N = @ARGV; +my %count; +$count{$_}++ for @N; +say $_ for (grep {$count{$_}%2==1} keys %count); diff --git a/challenge-130/paulo-custodio/perl/ch-2.pl b/challenge-130/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..5c2f5180eb --- /dev/null +++ b/challenge-130/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,122 @@ +#!/usr/bin/env perl + +# TASK #2 > Binary Search Tree +# Submitted by: Mohammad S Anwar +# You are given a tree. +# +# Write a script to find out if the given tree is Binary Search Tree +# (BST). +# +# According to wikipedia, the definition of BST: +# +# A binary search tree is a rooted binary tree, whose internal nodes +# each store a key (and optionally, an associated value), and each has +# two distinguished sub-trees, commonly denoted left and right. The +# tree additionally satisfies the binary search property: the key in +# each node is greater than or equal to any key stored in the left +# sub-tree, and less than or equal to any key stored in the right +# sub-tree. The leaves (final nodes) of the tree contain no key and +# have no structure to distinguish them from one another. +# +# Example 1 +# Input: +# 8 +# / \ +# 5 9 +# / \ +# 4 6 +# +# Output: 1 as the given tree is a BST. +# Example 2 +# Input: +# 5 +# / \ +# 4 7 +# / \ +# 3 6 +# +# Output: 0 as the given tree is a not BST. + +use Modern::Perl; +use List::Util qw( min max ); + +# tree object +{ + package Tree; + use Object::Tiny::RW qw( value left right ); +} + +sub parse_tree { + chomp(my @lines = <>); + @lines or die "malformed tree\n"; + $lines[0] =~ /^( +)\d/ or die "malformed tree\n"; + my $tree = parse_subtree(\@lines, 0, length($1)); + return $tree; +} + +sub parse_subtree { + my($lines, $row, $col) = @_; + + # parse root + my $value = substr($lines->[$row], $col, 1); + $value =~ /\d/ or die "malformed tree\n"; + my $node = Tree->new(value => $value); + + # parse children + if ($row+2 <= $#{$lines}) { + # parse left subtree + if ($col-2 >= 0 && + $col-2 < length($lines->[$row+1]) && + substr($lines->[$row+1], $col-1, 1) eq '/') { + my $child = parse_subtree($lines, $row+2, $col-2); + $node->left($child); + } + # parse right subtree + if ($col+2 < length($lines->[$row+2]) && + substr($lines->[$row+1], $col+1, 1) eq '\\') { + my $child = parse_subtree($lines, $row+2, $col+2); + $node->right($child); + } + } + return $node; +} + +sub subtree_min { + my($node) = @_; + my $min = $node->value; + if ($node->left) { + $min = min($min, subtree_min($node->left)); + } + if ($node->right) { + $min = min($min, subtree_min($node->right)); + } + return $min; +} + +sub subtree_max { + my($node) = @_; + my $max = $node->value; + if ($node->left) { + $max = max($max, subtree_max($node->left)); + } + if ($node->right) { + $max = max($max, subtree_max($node->right)); + } + return $max; +} + +sub subtree_is_bst { + my($node) = @_; + if ($node->left) { + return 0 if !subtree_is_bst($node->left); + return 0 if subtree_max($node->left) > $node->value; + } + if ($node->right) { + return 0 if !subtree_is_bst($node->right); + return 0 if subtree_min($node->right) < $node->value; + } + return 1; +} + +my $tree = parse_tree(); +say subtree_is_bst($tree); diff --git a/challenge-130/paulo-custodio/python/ch-1.py b/challenge-130/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..00794b20da --- /dev/null +++ b/challenge-130/paulo-custodio/python/ch-1.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python3 + +# TASK #1 > Odd Number +# Submitted by: Mohammad S Anwar +# You are given an array of positive integers, such that all the +# numbers appear even number of times except one number. +# +# Write a script to find that integer. +# +# Example 1 +# Input: @N = (2, 5, 4, 4, 5, 5, 2) +# Output: 5 as it appears 3 times in the array where as all other +# numbers 2 and 4 appears exactly twice. +# Example 2 +# Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4) +# Output: 4 + +import sys + +N = sys.argv[1:] +count = {} +for n in N: + if n not in count: + count[n] = 1 + else: + count[n] += 1 +for n,count in count.items(): + if count%2==1: + print(n) diff --git a/challenge-130/paulo-custodio/python/ch-2.py b/challenge-130/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..e2e4f427f7 --- /dev/null +++ b/challenge-130/paulo-custodio/python/ch-2.py @@ -0,0 +1,110 @@ +#!/usr/bin/env python3 + +# TASK #2 > Binary Search Tree +# Submitted by: Mohammad S Anwar +# You are given a tree. +# +# Write a script to find out if the given tree is Binary Search Tree +# (BST). +# +# According to wikipedia, the definition of BST: +# +# A binary search tree is a rooted binary tree, whose internal nodes +# each store a key (and optionally, an associated value), and each has +# two distinguished sub-trees, commonly denoted left and right. The +# tree additionally satisfies the binary search property: the key in +# each node is greater than or equal to any key stored in the left +# sub-tree, and less than or equal to any key stored in the right +# sub-tree. The leaves (final nodes) of the tree contain no key and +# have no structure to distinguish them from one another. +# +# Example 1 +# Input: +# 8 +# / \ +# 5 9 +# / \ +# 4 6 +# +# Output: 1 as the given tree is a BST. +# Example 2 +# Input: +# 5 +# / \ +# 4 7 +# / \ +# 3 6 +# +# Output: 0 as the given tree is a not BST. + +import fileinput +import re + +class Node: + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def __repr__(self): + return "Node(value: {}, left: {}, right: {})" \ + .format(self.value, self.left, self.right) + +def read_input(): + lines = [] + for line in fileinput.input(): + lines.append(line) + return lines + +def parse_subtree(lines, row, col): + def ch(row, col): + if row < 0 or row >= len(lines) or \ + col < 0 or col >= len(lines[row]): + return ' ' + else: + return lines[row][col] + + tree = Node(int(lines[row][col])) + if ch(row + 1, col - 1) == '/': + tree.left = parse_subtree(lines, row + 2, col - 2) + if ch(row + 1, col + 1) == '\\': + tree.right = parse_subtree(lines, row + 2, col + 2) + + return tree + +def parse(lines): + found = re.search("^[ ]+\d", lines[0]) + col = found.span()[1] - 1 + return parse_subtree(lines, 0, col) + +def subtree_min(node): + min_value = node.value + if node.left: + min_value = min(min_value, subtree_min(node.left)) + if node.right: + min_value = min(min_value, subtree_min(node.right)) + return min_value + +def subtree_max(node): + max_value = node.value + if node.left: + max_value = max(max_value, subtree_max(node.left)) + if node.right: + max_value = max(max_value, subtree_max(node.right)) + return max_value + +def subtree_is_bst(node): + if node.left: + if not subtree_is_bst(node.left): + return 0 + if subtree_max(node.left) > node.value: + return 0 + if node.right: + if not subtree_is_bst(node.right): + return 0 + if subtree_min(node.right) < node.value: + return 0 + return 1 + +tree = parse(read_input()) +print(subtree_is_bst(tree)) diff --git a/challenge-130/paulo-custodio/t/test-1.yaml b/challenge-130/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..26d3ec1846 --- /dev/null +++ b/challenge-130/paulo-custodio/t/test-1.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: 2 5 4 4 5 5 2 + input: + output: 5 +- setup: + cleanup: + args: 1 2 3 4 3 2 1 4 4 + input: + output: 4 diff --git a/challenge-130/paulo-custodio/t/test-2.yaml b/challenge-130/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..514072061c --- /dev/null +++ b/challenge-130/paulo-custodio/t/test-2.yaml @@ -0,0 +1,20 @@ +- setup: + cleanup: + args: + input: | + | 8 + | / \ + | 5 9 + | / \ + | 4 6 + output: 1 +- setup: + cleanup: + args: + input: | + | 5 + | / \ + | 4 7 + | / \ + | 3 6 + output: 0 diff --git a/challenge-130/paulo-custodio/test.pl b/challenge-130/paulo-custodio/test.pl new file mode 100644 index 0000000000..ba6c37260b --- /dev/null +++ b/challenge-130/paulo-custodio/test.pl @@ -0,0 +1,4 @@ +#!/usr/bin/env perl +use Modern::Perl; +use Test::More; +require '../../challenge-001/paulo-custodio/test.pl'; -- cgit From 70813a96d94346e8e75ceb6c5f60f42d38e54524 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Mon, 25 Oct 2021 09:30:55 +0100 Subject: Add Perl and Python solutions to challenge 129 --- challenge-129/paulo-custodio/perl/ch-1.pl | 111 ++++++++++++++++++++++++++++ challenge-129/paulo-custodio/perl/ch-2.pl | 63 ++++++++++++++++ challenge-129/paulo-custodio/python/ch-1.py | 111 ++++++++++++++++++++++++++++ challenge-129/paulo-custodio/python/ch-2.py | 81 ++++++++++++++++++++ challenge-129/paulo-custodio/t/test-1.yaml | 90 ++++++++++++++++++++++ challenge-129/paulo-custodio/t/test-2.yaml | 10 +++ challenge-129/paulo-custodio/test.pl | 4 + 7 files changed, 470 insertions(+) create mode 100644 challenge-129/paulo-custodio/perl/ch-1.pl create mode 100644 challenge-129/paulo-custodio/perl/ch-2.pl create mode 100644 challenge-129/paulo-custodio/python/ch-1.py create mode 100644 challenge-129/paulo-custodio/python/ch-2.py create mode 100644 challenge-129/paulo-custodio/t/test-1.yaml create mode 100644 challenge-129/paulo-custodio/t/test-2.yaml create mode 100644 challenge-129/paulo-custodio/test.pl diff --git a/challenge-129/paulo-custodio/perl/ch-1.pl b/challenge-129/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..c5195f9e12 --- /dev/null +++ b/challenge-129/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,111 @@ +#!/usr/bin/env perl + +# TASK #1 > Root Distance +# Submitted by: Mohammad S Anwar +# You are given a tree and a node of the given tree. +# +# Write a script to find out the distance of the given node from the root. +# +# Example 1: +# Tree: +# 1 +# / \ +# 2 3 +# \ +# 4 +# / \ +# 5 6 +# +# Node: 6 +# Output: 3 as the distance of given node 6 from the root (1). +# +# Node: 5 +# Output: 3 +# +# Node: 2 +# Output: 1 +# +# Node: 4 +# Output: 2 +# Example 2: +# Tree: +# 1 +# / \ +# 2 3 +# / \ +# 4 5 +# \ / +# 6 7 +# / \ +# 8 9 +# +# Node: 7 +# Output: 3 as the distance of given node 6 from the root (1). +# +# Node: 8 +# Output: 4 +# +# Node: 6 +# Output: 3 + +use Modern::Perl; + +# tree object +{ + package Tree; + use Object::Tiny::RW qw( value left right ); +} + +sub parse_tree { + chomp(my @lines = ); + @lines or die "malformed tree\n"; + $lines[0] =~ /^( +)\d/ or die "malformed tree\n"; + my $tree = parse_subtree(\@lines, 0, length($1)); + return $tree; +} + +sub parse_subtree { + my($lines, $row, $col) = @_; + + # parse root + my $value = substr($lines->[$row], $col, 1); + $value =~ /\d/ or die "malformed tree\n"; + my $node = Tree->new(value => $value); + + # parse children + if ($row+2 <= $#{$lines}) { + # parse left subtree + if ($col-2 >= 0 && + $col-2 < length($lines->[$row+1]) && + substr($lines->[$row+1], $col-1, 1) eq '/') { + my $child = parse_subtree($lines, $row+2, $col-2); + $node->left($child); + } + # parse right subtree + if ($col+2 < length($lines->[$row+2]) && + substr($lines->[$row+1], $col+1, 1) eq '\\') { + my $child = parse_subtree($lines, $row+2, $col+2); + $node->right($child); + } + } + return $node; +} + +sub root_dist { + my($node, $value, $dist) = @_; + $dist ||= 0; + return $dist if $value == $node->value; + if ($node->left) { + my $found = root_dist($node->left, $value, $dist+1); + return $found if $found > 0; + } + if ($node->right) { + my $found = root_dist($node->right, $value, $dist+1); + return $found if $found > 0; + } + return -1; +} + +my $tree = parse_tree(); +my $value = shift||0; +say(root_dist($tree, $value)); diff --git a/challenge-129/paulo-custodio/perl/ch-2.pl b/challenge-129/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..949beebbab --- /dev/null +++ b/challenge-129/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,63 @@ +#!/usr/bin/env perl + +# TASK #2 > Add Linked Lists +# Submitted by: Mohammad S Anwar +# You are given two linked list having single digit positive numbers. +# +# Write a script to add the two linked list and create a new linked representing +# the sum of the two linked list numbers. The two linked lists may or may not +# have the same number of elements. +# +# HINT: Just a suggestion, feel free to come up with your own unique way to deal +# with the task. I am expecting a class representing linked list. It should have +# methods to create a linked list given list of single digit positive numbers +# and a method to add new member. Also have a method that takes 2 linked list +# objects and returns a new linked list. Finally a method to print the linked +# list object in a user friendly format. +# +# Example 1: +# Input: L1 = 1 -> 2 -> 3 +# L2 = 3 -> 2 -> 1 +# Output: 4 -> 4 -> 4 +# +# Example 2: +# Input: L1 = 1 -> 2 -> 3 -> 4 -> 5 +# L2 = 6 -> 5 -> 5 +# Output: 1 -> 3 -> 0 -> 0 -> 0 + +use Modern::Perl; +use HOP::Stream ':all'; + +use Data::Dump 'dump'; + +@ARGV==2 or die "Usage: ch-2.pl l1 l2\n"; +my $l1 = list_to_stream(split //, $ARGV[0]); +my $l2 = list_to_stream(split //, $ARGV[1]); +my $sum = add_streams($l1, $l2); +say show($sum); + +sub reverse_stream { + my($in) = @_; + my $out; + while ($in) { + my $n = drop($in); + $out = node($n, $out); + } + return $out; +} + +sub add_streams { + my($l1, $l2) = @_; + $l1 = reverse_stream($l1); + $l2 = reverse_stream($l2); + my($sum); + my $carry = 0; + while ($l1 || $l2 || $carry) { + my $n1 = drop($l1) // 0; + my $n2 = drop($l2) // 0; + my $s = $n1+$n2+$carry; + $sum = node($s % 10, $sum); + $carry = int($s / 10); + } + return $sum; +} diff --git a/challenge-129/paulo-custodio/python/ch-1.py b/challenge-129/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..78306de292 --- /dev/null +++ b/challenge-129/paulo-custodio/python/ch-1.py @@ -0,0 +1,111 @@ +#!/usr/bin/env python3 + +# TASK #1 > Root Distance +# Submitted by: Mohammad S Anwar +# You are given a tree and a node of the given tree. +# +# Write a script to find out the distance of the given node from the root. +# +# Example 1: +# Tree: +# 1 +# / \ +# 2 3 +# \ +# 4 +# / \ +# 5 6 +# +# Node: 6 +# Output: 3 as the distance of given node 6 from the root (1). +# +# Node: 5 +# Output: 3 +# +# Node: 2 +# Output: 1 +# +# Node: 4 +# Output: 2 +# Example 2: +# Tree: +# 1 +# / \ +# 2 3 +# / \ +# 4 5 +# \ / +# 6 7 +# / \ +# 8 9 +# +# Node: 7 +# Output: 3 as the distance of given node 6 from the root (1). +# +# Node: 8 +# Output: 4 +# +# Node: 6 +# Output: 3 + +import fileinput +import re +import sys + +class Node: + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def __repr__(self): + return "Node(value: {}, left: {}, right: {})" \ + .format(self.value, self.left, self.right) + +def read_input(): + lines = [] + for line in fileinput.input(): + lines.append(line) + return lines + +def parse_subtree(lines, row, col): + def ch(row, col): + if row < 0 or row >= len(lines) or \ + col < 0 or col >= len(lines[row]): + return ' ' + else: + return lines[row][col] + + tree = Node(int(lines[row][col])) + if ch(row + 1, col - 1) == '/': + tree.left = parse_subtree(lines, row + 2, col - 2) + if ch(row + 1, col + 1) == '\\': + tree.right = parse_subtree(lines, row + 2, col + 2) + + return tree + +def parse(lines): + found = re.search("^[ ]+\d", lines[0]) + col = found.span()[1] - 1 + return parse_subtree(lines, 0, col) + +def root_dist(tree, value): + def subtree_dist(node, value, dist): + if value == node.value: + return dist + if node.left: + found = subtree_dist(node.left, value, dist+1) + if found > 0: + return found + if node.right: + found = subtree_dist(node.right, value, dist+1) + if found > 0: + return found + return -1 + + return subtree_dist(tree, value, 0) + +value = int(sys.argv.pop()) +tree = parse(read_input()) +dist = root_dist(tree, value) +print(dist) diff --git a/challenge-129/paulo-custodio/python/ch-2.py b/challenge-129/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..8cf54a885f --- /dev/null +++ b/challenge-129/paulo-custodio/python/ch-2.py @@ -0,0 +1,81 @@ +#!/usr/bin/env python3 + +# TASK #2 > Add Linked Lists +# Submitted by: Mohammad S Anwar +# You are given two linked list having single digit positive numbers. +# +# Write a script to add the two linked list and create a new linked representing +# the sum of the two linked list numbers. The two linked lists may or may not +# have the same number of elements. +# +# HINT: Just a suggestion, feel free to come up with your own unique way to deal +# with the task. I am expecting a class representing linked list. It should have +# methods to create a linked list given list of single digit positive numbers +# and a method to add new member. Also have a method that takes 2 linked list +# objects and returns a new linked list. Finally a method to print the linked +# list object in a user friendly format. +# +# Example 1: +# Input: L1 = 1 -> 2 -> 3 +# L2 = 3 -> 2 -> 1 +# Output: 4 -> 4 -> 4 +# +# Example 2: +# Input: L1 = 1 -> 2 -> 3 -> 4 -> 5 +# L2 = 6 -> 5 -> 5 +# Output: 1 -> 3 -> 0 -> 0 -> 0 + +import sys + +def node(head, tail): + return [head, tail] + +def drop(strm): + if strm is None: + return None, strm + else: + head = strm[0] + tail = strm[1] + return head, tail + +def show_strm(strm): + if strm is None: + return "" + else: + n, strm = drop(strm) + return str(n) + " " + show_strm(strm) + +def list_to_stream(lst): + stream = None + while len(lst) > 0: + stream = node(lst.pop(), stream) + return stream + +def reverse_stream(in_strm): + out_strm = None + while in_strm: + n, in_strm = drop(in_strm) + out_strm = node(n, out_strm) + return out_strm + +def add_streams(s1, s2): + s1 = reverse_stream(s1) + s2 = reverse_stream(s2) + result = None + carry = 0 + while s1 or s2 or carry!=0: + n1, s1 = drop(s1) + if not n1: + n1 = 0 + n2, s2 = drop(s2) + if not n2: + n2 = 0 + s = n1+n2+carry + result = node(s % 10, result) + carry = int(s / 10) + return result + +l1 = list_to_stream([int(x) for x in sys.argv[1]]) +l2 = list_to_stream([int(x) for x in sys.argv[2]]) +s = add_streams(l1, l2) +print(show_strm(s)) diff --git a/challenge-129/paulo-custodio/t/test-1.yaml b/challenge-129/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..329a15501a --- /dev/null +++ b/challenge-129/paulo-custodio/t/test-1.yaml @@ -0,0 +1,90 @@ +- setup: + cleanup: + args: 6 + input: | + | 1 + | / \ + | 2 3 + | \ + | 4 + | / \ + | 5 6 + output: 3 +- setup: + cleanup: + args: 5 + input: | + | 1 + | / \ + | 2 3 + | \ + | 4 + | / \ + | 5 6 + output: 3 +- setup: + cleanup: + args: 2 + input: | + | 1 + | / \ + | 2 3 + | \ + | 4 + | / \ + | 5 6 + output: 1 +- setup: + cleanup: + args: 4 + input: | + | 1 + | / \ + | 2 3 + | \ + | 4 + | / \ + | 5 6 + output: 2 +- setup: + cleanup: + args: 7 + input: | + | 1 + | / \ + | 2 3 + | / \ + | 4 5 + | \ / + | 6 7 + | / \ + | 8 9 + output: 3 +- setup: + cleanup: + args: 8 + input: | + | 1 + | / \ + | 2 3 + | / \ + | 4 5 + | \ / + | 6 7 + | / \ + | 8 9 + output: 4 +- setup: + cleanup: + args: 6 + input: | + | 1 + | / \ + | 2 3 + | / \ + | 4 5 + | \ / + | 6 7 + | / \ + | 8 9 + output: 3 diff --git a/challenge-129/paulo-custodio/t/test-2.yaml b/challenge-129/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..8a84409b46 --- /dev/null +++ b/challenge-129/paulo-custodio/t/test-2.yaml @@ -0,0 +1,10 @@ +- setup: + cleanup: + args: 123 321 + input: + output: 4 4 4 +- setup: + cleanup: + args: 12345 655 + input: + output: 1 3 0 0 0 diff --git a/challenge-129/paulo-custodio/test.pl b/challenge-129/paulo-custodio/test.pl new file mode 100644 index 0000000000..ba6c37260b --- /dev/null +++ b/challenge-129/paulo-custodio/test.pl @@ -0,0 +1,4 @@ +#!/usr/bin/env perl +use Modern::Perl; +use Test::More; +require '../../challenge-001/paulo-custodio/test.pl'; -- cgit From 04934952e58ff73537ec24052be6c399748fb015 Mon Sep 17 00:00:00 2001 From: Scimon Date: Mon, 25 Oct 2021 10:23:27 +0100 Subject: Challenge 2 --- challenge-136/simon-proctor/raku/ch-2.p6 | 15 +++++++++++++++ 1 file changed, 15 insertions(+) create mode 100644 challenge-136/simon-proctor/raku/ch-2.p6 diff --git a/challenge-136/simon-proctor/raku/ch-2.p6 b/challenge-136/simon-proctor/raku/ch-2.p6 new file mode 100644 index 0000000000..da1b3028cb --- /dev/null +++ b/challenge-136/simon-proctor/raku/ch-2.p6 @@ -0,0 +1,15 @@ +#!/usr/bin/env raku + +my %*SUB-MAIN-OPTS = :named-anywhere; + +#| Given an integer N print the number of different combinations of Fibonacci numbers that sum to it. +sub MAIN ( UInt \N, + Bool :v($verbose) = False #= Print the list of values + ) { + my @res = (1,1,*+*...* > N).unique.combinations.grep( + -> @f { ([+] @f) == N } + ); + say @res.elems; + say '---' if $verbose; + (.join(", ").say for @res) if $verbose; +} -- cgit From c14a9b15d8439489c1a17c6088132880a0e567fb Mon Sep 17 00:00:00 2001 From: Scimon Date: Mon, 25 Oct 2021 10:35:55 +0100 Subject: Challenge 1 --- challenge-136/simon-proctor/raku/ch-2.p6 | 15 --------------- challenge-136/simon-proctor/raku/ch-2.raku | 15 +++++++++++++++ 2 files changed, 15 insertions(+), 15 deletions(-) delete mode 100644 challenge-136/simon-proctor/raku/ch-2.p6 create mode 100644 challenge-136/simon-proctor/raku/ch-2.raku diff --git a/challenge-136/simon-proctor/raku/ch-2.p6 b/challenge-136/simon-proctor/raku/ch-2.p6 deleted file mode 100644 index da1b3028cb..0000000000 --- a/challenge-136/simon-proctor/raku/ch-2.p6 +++ /dev/null @@ -1,15 +0,0 @@ -#!/usr/bin/env raku - -my %*SUB-MAIN-OPTS = :named-anywhere; - -#| Given an integer N print the number of different combinations of Fibonacci numbers that sum to it. -sub MAIN ( UInt \N, - Bool :v($verbose) = False #= Print the list of values - ) { - my @res = (1,1,*+*...* > N).unique.combinations.grep( - -> @f { ([+] @f) == N } - ); - say @res.elems; - say '---' if $verbose; - (.join(", ").say for @res) if $verbose; -} diff --git a/challenge-136/simon-proctor/raku/ch-2.raku b/challenge-136/simon-proctor/raku/ch-2.raku new file mode 100644 index 0000000000..da1b3028cb --- /dev/null +++ b/challenge-136/simon-proctor/raku/ch-2.raku @@ -0,0 +1,15 @@ +#!/usr/bin/env raku + +my %*SUB-MAIN-OPTS = :named-anywhere; + +#| Given an integer N print the number of different combinations of Fibonacci numbers that sum to it. +sub MAIN ( UInt \N, + Bool :v($verbose) = False #= Print the list of values + ) { + my @res = (1,1,*+*...* > N).unique.combinations.grep( + -> @f { ([+] @f) == N } + ); + say @res.elems; + say '---' if $verbose; + (.join(", ").say for @res) if $verbose; +} -- cgit From 80c7aaa118fea1298874620db78aaa163e5d4ee9 Mon Sep 17 00:00:00 2001 From: Scimon Date: Mon, 25 Oct 2021 10:36:26 +0100 Subject: Challenge 1 --- challenge-136/simon-proctor/raku/ch-1.raku | 7 +++++++ 1 file changed, 7 insertions(+) create mode 100644 challenge-136/simon-proctor/raku/ch-1.raku diff --git a/challenge-136/simon-proctor/raku/ch-1.raku b/challenge-136/simon-proctor/raku/ch-1.raku new file mode 100644 index 0000000000..71ac8237ac --- /dev/null +++ b/challenge-136/simon-proctor/raku/ch-1.raku @@ -0,0 +1,7 @@ +#!/usr/bin/env raku + +#| Given to Integers m and n find if they are friendly numbers +sub MAIN( UInt \m, UInt \n ) { + my \v = m gcd n; + (1,2,* * 2...* > v).first(* == v).Bool.Int.say; +} -- cgit From 3fb94d5d2b20c84f2c7ae2299a78dcb1da442131 Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 25 Oct 2021 12:30:25 +0200 Subject: Blog reerences. --- challenge-136/luca-ferrari/blog-1.txt | 1 + challenge-136/luca-ferrari/blog-2.txt | 1 + 2 files changed, 2 insertions(+) create mode 100644 challenge-136/luca-ferrari/blog-1.txt create mode 100644 challenge-136/luca-ferrari/blog-2.txt diff --git a/challenge-136/luca-ferrari/blog-1.txt b/challenge-136/luca-ferrari/blog-1.txt new file mode 100644 index 0000000000..0e141f1428 --- /dev/null +++ b/challenge-136/luca-ferrari/blog-1.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2021/10/25/PerlWeeklyChallenge136.html#task1 diff --git a/challenge-136/luca-ferrari/blog-2.txt b/challenge-136/luca-ferrari/blog-2.txt new file mode 100644 index 0000000000..99f4aed91f --- /dev/null +++ b/challenge-136/luca-ferrari/blog-2.txt @@ -0,0 +1 @@ +https://fluca1978.github.io/2021/10/25/PerlWeeklyChallenge136.html#task2 -- cgit From 03ae69ae56d77043a61a7a5747eb3fa05da50785 Mon Sep 17 00:00:00 2001 From: Mark <53903062+andemark@users.noreply.github.com> Date: Mon, 25 Oct 2021 11:30:07 +0000 Subject: Challenge 136 Solutions (Raku) --- challenge-136/mark-anderson/raku/ch-1.raku | 14 ++++++++++++++ challenge-136/mark-anderson/raku/ch-2.raku | 19 +++++++++++++++++++ 2 files changed, 33 insertions(+) create mode 100644 challenge-136/mark-anderson/raku/ch-1.raku create mode 100644 challenge-136/mark-anderson/raku/ch-2.raku diff --git a/challenge-136/mark-anderson/raku/ch-1.raku b/challenge-136/mark-anderson/raku/ch-1.raku new file mode 100644 index 0000000000..7fcc297121 --- /dev/null +++ b/challenge-136/mark-anderson/raku/ch-1.raku @@ -0,0 +1,14 @@ +#!/usr/bin/env raku + +use Test; +plan 3; + +is two-friendly(8, 24), 1, 'Example 1'; +is two-friendly(26, 39), 0, 'Example 2'; +is two-friendly(4, 10), 1, 'Example 3'; + +sub two-friendly($m, $n) +{ + my $gcd = $m gcd $n; + +(log2($gcd).narrow ~~ UInt); +} diff --git a/challenge-136/mark-anderson/raku/ch-2.raku b/challenge-136/mark-anderson/raku/ch-2.raku new file mode 100644 index 0000000000..dff7f97a72 --- /dev/null +++ b/challenge-136/mark-anderson/raku/ch-2.raku @@ -0,0 +1,19 @@ +#!/usr/bin/env raku + +use Test; +plan 3; + +for 16 => 4, 9 => 2, 15 => 2 +{ + is +fibonacci-sums(.key), .value, "Example " ~ ++$; +} + +sub fibonacci-sums($n) +{ + my $fib := 1, 2, { $^a + $^b } ... { $n - $^a < $^b }; + + gather for $fib.combinations.skip + { + .take if .sum == $n; + } +} -- cgit From adec2daa379ba2058fbe00b56f00188748d1b73b Mon Sep 17 00:00:00 2001 From: Roger Bell_West Date: Mon, 25 Oct 2021 12:34:30 +0100 Subject: Solutions for challenge #136 --- challenge-136/roger-bell-west/perl/ch-1.pl | 31 +++++++++++++++++ challenge-136/roger-bell-west/perl/ch-2.pl | 23 +++++++++++++ challenge-136/roger-bell-west/postscript/ch-1.ps | 41 ++++++++++++++++++++++ challenge-136/roger-bell-west/postscript/ch-2.ps | 29 ++++++++++++++++ challenge-136/roger-bell-west/python/ch-1.py | 29 ++++++++++++++++ challenge-136/roger-bell-west/python/ch-2.py | 25 ++++++++++++++ challenge-136/roger-bell-west/raku/ch-1.p6 | 21 +++++++++++ challenge-136/roger-bell-west/raku/ch-2.p6 | 22 ++++++++++++ challenge-136/roger-bell-west/ruby/ch-1.rb | 34 ++++++++++++++++++ challenge-136/roger-bell-west/ruby/ch-2.rb | 31 +++++++++++++++++ challenge-136/roger-bell-west/rust/ch-1.rs | 44 ++++++++++++++++++++++++ challenge-136/roger-bell-west/rust/ch-2.rs | 29 ++++++++++++++++ 12 files changed, 359 insertions(+) create mode 100755 challenge-136/roger-bell-west/perl/ch-1.pl create mode 100755 challenge-136/roger-bell-west/perl/ch-2.pl create mode 100644 challenge-136/roger-bell-west/postscript/ch-1.ps create mode 100644 challenge-136/roger-bell-west/postscript/ch-2.ps create mode 100755 challenge-136/roger-bell-west/python/ch-1.py create mode 100755 challenge-136/roger-bell-west/python/ch-2.py create mode 100755 challenge-136/roger-bell-west/raku/ch-1.p6 create mode 100755 challenge-136/roger-bell-west/raku/ch-2.p6 create mode 100755 challenge-136/roger-bell-west/ruby/ch-1.rb create mode 100755 challenge-136/roger-bell-west/ruby/ch-2.rb create mode 100755 challenge-136/roger-bell-west/rust/ch-1.rs create mode 100755 challenge-136/roger-bell-west/rust/ch-2.rs diff --git a/challenge-136/roger-bell-west/perl/ch-1.pl b/challenge-136/roger-bell-west/perl/ch-1.pl new file mode 100755 index 0000000000..f21d9316d8 --- /dev/null +++ b/challenge-136/roger-bell-west/perl/ch-1.pl @@ -0,0 +1,31 @@ +#! /usr/bin/perl + +use strict; + +use Test::More tests => 4; + +is(twofriendly(8,24),1,'example 1'); +is(twofriendly(26,39),0,'example 2'); +is(twofriendly(4,10),1,'example 3'); +is(twofriendly(1,2),0,'example 4'); + +sub gcd { + my ($m,$n)=@_; + while ($n!=0) { + ($m,$n)=($n,$m % $n); + } + return $m; +} + +sub ispower2 { + my $n=shift; + if ($n<2) { + return 0; + } + return ($n & ($n-1))==0; +} + +sub twofriendly { + my ($m,$n)=@_; + return ispower2(gcd($m,$n))?1:0; +} diff --git a/challenge-136/roger-bell-west/perl/ch-2.pl b/challenge-136/roger-bell-west/perl/ch-2.pl new file mode 100755 index 0000000000..dc0c011d56 --- /dev/null +++ b/challenge-136/roger-bell-west/perl/ch-2.pl @@ -0,0 +1,23 @@ +#! /usr/bin/perl + +use strict; + +use Test::More tests => 3; + +is(fibseq(16),4,'example 1'); +is(fibseq(9),2,'example 2'); +is(fibseq(15),2,'example 3'); + +sub fibseq { + my $m=shift; + return f($m,1,1); +} + +sub f { + my ($x,$y,$z)=@_; + if ($x < $y) { + return ($x==0)?1:0; + } else { + return f($x-$y,$y+$z,$y)+f($x,$y+$z,$y); + } +} diff --git a/challenge-136/roger-bell-west/postscript/ch-1.ps b/challenge-136/roger-bell-west/postscript/ch-1.ps new file mode 100644 index 0000000000..c7874180ff --- /dev/null +++ b/challenge-136/roger-bell-west/postscript/ch-1.ps @@ -0,0 +1,41 @@ +%!PS + +/gcd { + { + dup + 3 1 roll + mod + dup 0 eq { + pop exit + } if + } loop +} bind def + +48 18 gcd 6 eq { (Pass) } { (FAIL) } ifelse print ( ) print +18 48 gcd 6 eq { (Pass) } { (FAIL) } ifelse print ( ) print +24 54 gcd 6 eq { (Pass) } { (FAIL) } ifelse print ( ) print +54 24 gcd 6 eq { (Pass) } { (FAIL) } ifelse print ( ) print +12 8 gcd 4 eq { (Pass) } { (FAIL) } ifelse print ( ) print +8 12 gcd 4 eq { (Pass) } { (FAIL) } ifelse = + +/ispower2 { + dup 2 lt { + pop false + } { + dup 1 sub and 0 eq + } ifelse +} bind def + +1 ispower2 false eq { (Pass) } { (FAIL) } ifelse print ( ) print +2 ispower2 true eq { (Pass) } { (FAIL) } ifelse print ( ) print +17 ispower2 false eq { (Pass) } { (FAIL) } ifelse print ( ) print +16 ispower2 true eq { (Pass) } { (FAIL) } ifelse = + +/twofriendly { + gcd ispower2 +} bind def + +8 24 twofriendly true eq { (Pass) } { (FAIL) } ifelse print ( ) print +26 39 twofriendly false eq { (Pass) } { (FAIL) } ifelse print ( ) print +4 10 twofriendly true eq { (Pass) } { (FAIL) } ifelse print ( ) print +1 2 twofriendly false eq { (Pass) } { (FAIL) } ifelse = diff --git a/challenge-136/roger-bell-west/postscript/ch-2.ps b/challenge-136/roger-bell-west/postscript/ch-2.ps new file mode 100644 index 0000000000..6c65912987 --- /dev/null +++ b/challenge-136/roger-bell-west/postscript/ch-2.ps @@ -0,0 +1,29 @@ +%!PS + +/fibseq { + 1 1 f +} bind def + +/f { + 3 dict begin + /z exch def + /y exch def + /x exch def + x y lt { + x 0 eq { + 1 + } { + 0 + } ifelse + } { + x y sub y z add y f + x y z add y f + add + } ifelse + end +} bind def + +16 fibseq 4 eq { (Pass) } { (FAIL) } ifelse print ( ) print +9 fibseq 2 eq { (Pass) } { (FAIL) } ifelse print ( ) print +15 fibseq 2 eq { (Pass) } { (FAIL) } ifelse = + diff --git a/challenge-136/roger-bell-west/python/ch-1.py b/challenge-136/roger-bell-west/python/ch-1.py new file mode 100755 index 0000000000..2636b1661f --- /dev/null +++ b/challenge-136/roger-bell-west/python/ch-1.py @@ -0,0 +1,29 @@ +#! /usr/bin/python3 + +import unittest + +from math import gcd + +def ispower2(n): + if n<2: + return False + return (n & (n-1))==0 + +def twofriendly(m,n): + return 1 if ispower2(gcd(m,n)) else 0 + +class TestTwofriendly(unittest.TestCase): + + def test_ex1(self): + self.assertEqual(twofriendly(8,24),1,'example 1') + + def test_ex2(self): + self.assertEqual(twofriendly(26,39),0,'example 2') + + def test_ex3(self): + self.assertEqual(twofriendly(4,10),1,'example 3') + + def test_ex4(self): + self.assertEqual(twofriendly(1,2),0,'example 4') + +unittest.main() diff --git a/challenge-136/roger-bell-west/python/ch-2.py b/challenge-136/roger-bell-west/python/ch-2.py new file mode 100755 index 0000000000..bd1045ac5a --- /dev/null +++ b/challenge-136/roger-bell-west/python/ch-2.py @@ -0,0 +1,25 @@ +#! /usr/bin/python3 + +import unittest + +def fibseq(m): + return f(m,1,1) + +def f(x,y,z): + if x i32 { + let mut mm=m; + let mut nn=n; + while nn!=0 { + let t=mm; + mm=nn; + nn=t%nn; + } + mm +} + +fn ispower2(n: i32) -> bool { + if n<2 { + return false; + } + (n & (n-1))==0 +} + +fn twofriendly(m: i32, n: i32) -> u8 { + if ispower2(gcd(m,n)) { 1 } else { 0 } +} diff --git a/challenge-136/roger-bell-west/rust/ch-2.rs b/challenge-136/roger-bell-west/rust/ch-2.rs new file mode 100755 index 0000000000..f1b60fd19d --- /dev/null +++ b/challenge-136/roger-bell-west/rust/ch-2.rs @@ -0,0 +1,29 @@ +#! /bin/sh +//usr/bin/env rustc --test $0 -o ${0}x && ./${0}x; rm -f ${0}x ; exit + +#[test] +fn test_ex1() { + assert_eq!(fibseq(16),4); +} + +#[test] +fn test_ex2() { + assert_eq!(fibseq(9),2); +} + +#[test] +fn test_ex3() { + assert_eq!(fibseq(15),2); +} + +fn f (x: i32,y: i32,z: i32) -> i32 { + if x i32 { + f(m,1,1) +} -- cgit From 3597b04e7b51e87df46f2bae77e3421f694977f7 Mon Sep 17 00:00:00 2001 From: Mark <53903062+andemark@users.noreply.github.com> Date: Mon, 25 Oct 2021 11:57:49 +0000 Subject: Challenge 136 Solutions (Raku) --- challenge-136/mark-anderson/raku/ch-1.raku | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/challenge-136/mark-anderson/raku/ch-1.raku b/challenge-136/mark-anderson/raku/ch-1.raku index 7fcc297121..59f55c91a0 100644 --- a/challenge-136/mark-anderson/raku/ch-1.raku +++ b/challenge-136/mark-anderson/raku/ch-1.raku @@ -9,6 +9,5 @@ is two-friendly(4, 10), 1, 'Example 3'; sub two-friendly($m, $n) { - my $gcd = $m gcd $n; - +(log2($gcd).narrow ~~ UInt); + +(log2($m gcd $n).narrow ~~ UInt); } -- cgit From bd586bda68be6134c479217e3c42417bf960ff58 Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 25 Oct 2021 14:10:49 +0200 Subject: Tests for week 135 --- challenge-136/abigail/t/ctest.ini | 8 ++++++++ challenge-136/abigail/t/input-1-1 | 3 +++ challenge-136/abigail/t/input-2-1 | 3 +++ challenge-136/abigail/t/output-1-1.exp | 3 +++ challenge-136/abigail/t/output-2-1.exp | 3 +++ 5 files changed, 20 insertions(+) create mode 100644 challenge-136/abigail/t/ctest.ini create mode 100644 challenge-136/abigail/t/input-1-1 create mode 100644 challenge-136/abigail/t/input-2-1 create mode 100644 challenge-136/abigail/t/output-1-1.exp create mode 100644 challenge-136/abigail/t/output-2-1.exp diff --git a/challenge-136/abigail/t/ctest.ini b/challenge-136/abigail/t/ctest.ini new file mode 100644 index 0000000000..527781acbb --- /dev/null +++ b/challenge-136/abigail/t/ctest.ini @@ -0,0 +1,8 @@ +# +# Configuration file for running tests, using ctest. +# See https://github.com/Abigail/Misc/blob/master/ctest +# + +[names] +1-1 = Given Examples +2-1 = Given Examples diff --git a/challenge-136/abigail/t/input-1-1 b/challenge-136/abigail/t/input-1-1 new file mode 100644 index 0000000000..15032b5275 --- /dev/null +++ b/challenge-136/abigail/t/input-1-1 @@ -0,0 +1,3 @@ +8 24 +26 39 +4 10 diff --git a/challenge-136/abigail/t/input-2-1 b/challenge-136/abigail/t/input-2-1 new file mode 100644 index 0000000000..5a670722cb --- /dev/null +++ b/challenge-136/abigail/t/input-2-1 @@ -0,0 +1,3 @@ +16 +9 +15 diff --git a/challenge-136/abigail/t/output-1-1.exp b/challenge-136/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..16db301bb5 --- /dev/null +++ b/challenge-136/abigail/t/output-1-1.exp @@ -0,0 +1,3 @@ +1 +0 +1 diff --git a/challenge-136/abigail/t/output-2-1.exp b/challenge-136/abigail/t/output-2-1.exp new file mode 100644 index 0000000000..1a77ef09c7 --- /dev/null +++ b/challenge-136/abigail/t/output-2-1.exp @@ -0,0 +1,3 @@ +4 +2 +2 -- cgit From 2d5b702c9a348f2226fca9c981f0054c485aa1dd Mon Sep 17 00:00:00 2001 From: Luca Ferrari Date: Mon, 25 Oct 2021 14:28:41 +0200 Subject: Another implementation of the second task. --- challenge-136/luca-ferrari/raku/ch-2.p6 | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) diff --git a/challenge-136/luca-ferrari/raku/ch-2.p6 b/challenge-136/luca-ferrari/raku/ch-2.p6 index 83a5227a9d..6a606785ee 100755 --- a/challenge-136/luca-ferrari/raku/ch-2.p6 +++ b/challenge-136/luca-ferrari/raku/ch-2.p6 @@ -1,22 +1,28 @@ #!raku sub MAIN( Int $n where { $n > 1 } ) { - my @fibonacci; - @fibonacci.push: 1, 1; - my %solutions; + # my @fibonacci; + # @fibonacci.push: 1, 1; + # my %solutions; - # compute a reduced fibonacci sequence up to the sum of the number given - @fibonacci.push: @fibonacci[ * - 1 ] + @fibonacci[ * - 2 ] while $n > ( @fibonacci[ * - 1] + @fibonacci[ * - 2 ]); + # # compute a reduced fibonacci sequence up to the sum of the number given + # @fibonacci.push: @fibonacci[ * - 1 ] + @fibonacci[ * - 2 ] while $n > ( @fibonacci[ * - 1] + @fibonacci[ * - 2 ]); - # iterate over all the available numbers, and compute the sum - # and if the sum does match, add the array to the hash of solutions - # with a stringified key representation - %solutions{ $_.join( ' + ') } = $_ if ( ( [+] $_ ) == $n ) for @fibonacci.combinations.unique; + # # iterate over all the available numbers, and compute the sum + # # and if the sum does match, add the array to the hash of solutions + # # with a stringified key representation + # %solutions{ $_.join( ' + ') } = $_ if ( ( [+] $_ ) == $n ) for @fibonacci.combinations.unique; - # print the number of keys - say %solutions.keys.elems; - # and print all the sums - .join( " + " ).say for %solutions.values; + # # print the number of keys + # say %solutions.keys.elems; + # # and print all the sums + # .join( " + " ).say for %solutions.values; + + + my @fibonacci = 1, 1, * + * ... * > $n; + my @solutions = @fibonacci.unique.combinations.grep( *.sum == $n ); + @solutions.elems.say; + .join( ' + ' ).say for @solutions; } -- cgit From 2dbe6d2e70c029297f85d39fa0f7ce4363bf8d0d Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 25 Oct 2021 14:58:31 +0200 Subject: Perl solutions for week 135 --- challenge-136/abigail/README.md | 22 ----------------- challenge-136/abigail/perl/ch-1.pl | 50 ++++++++++++++++++++++++++++++++++++++ challenge-136/abigail/perl/ch-2.pl | 46 +++++++++++++++++++++++++++++++++++ 3 files changed, 96 insertions(+), 22 deletions(-) create mode 100644 challenge-136/abigail/perl/ch-1.pl create mode 100644 challenge-136/abigail/perl/ch-2.pl diff --git a/challenge-136/abigail/README.md b/challenge-136/abigail/README.md index 6178e463fe..aa835b7f1e 100644 --- a/challenge-136/abigail/README.md +++ b/challenge-136/abigail/README.md @@ -2,30 +2,8 @@ ## Part 1 -* [AWK](awk/ch-1.awk) -* [Bash](bash/ch-1.sh) -* [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) * [Perl](perl/ch-1.pl) -* [Python](python/ch-1.py) -* [Ruby](ruby/ch-1.rb) -* [Scheme](scheme/ch-1.scm) -* [Tcl](tcl/ch-1.tcl) ## Part 2 -* [AWK](awk/ch-2.awk) -* [Bash](bash/ch-2.sh) -* [C](c/ch-2.c) -* [Go](go/ch-2.go) -* [Java](java/ch-2.java) -* [Lua](lua/ch-2.lua) -* [Node.js](node/ch-2.js) * [Perl](perl/ch-2.pl) -* [Python](python/ch-2.py) -* [Ruby](ruby/ch-2.rb) -* [Scheme](scheme/ch-2.scm) -* [Tcl](tcl/ch-2.tcl) diff --git a/challenge-136/abigail/perl/ch-1.pl b/challenge-136/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..878aa3a81b --- /dev/null +++ b/challenge-136/abigail/perl/ch-1.pl @@ -0,0 +1,50 @@ +#!/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 +# + +# +# We need the GCD of two numbers. We did this in the past a few times, +# for instance in week 82. So, we copy-and-pasted the code from that week. +# +# We could write some code to check whether a number is a power of 2. +# But there are only 63 powers of 2 which fit in a 64 bit integer, one +# of them being 1. So, we can just precalculate the ones we're interested in. +# +my %power_of_2 = map {1 << $_ => 1} 1 .. 62; + +# +# Find the GCD, using Stein's algorithm +# (https://en.wikipedia.org/wiki/Binary_GCD_algorithm) +# +sub gcd; +sub gcd ($u, $v) { + return $u if $u == $v || !$v; + return $v if !$u; + my $u_odd = $u % 2; + my $v_odd = $v % 2; + return gcd ($u >> 1, $v >> 1) << 1 if !$u_odd && !$v_odd; + return gcd ($u >> 1, $v) if !$u_odd && $v_odd; + return gcd ($u, $v >> 1) if $u_odd && !$v_odd; + return gcd ($u - $v, $v) if $u > $v; + return gcd ($v - $u, $u); +} + +# +# Main program +# +say $power_of_2 {gcd split} || 0 while <>; diff --git a/challenge-136/abigail/perl/ch-2.pl b/challenge-136/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..d9a5e5ae13 --- /dev/null +++ b/challenge-136/abigail/perl/ch-2.pl @@ -0,0 +1,46 @@ +#!/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 +# + +# +# We will use a simple recursive function. +# The function takes three arguments: +# - The target number we like to sum to ($target) +# - The smallest Fibonnaci number we have not tried yet ($this_fib) +# - The Fibonacci number proceeding the one above. ($prev_fib) +# +# If $this_fib is larger than $target, we have to way to make the target +# number, so we return 0. +# If $this_fib is equal to $target, we can only make the target in one way, +# so we return 1. +# Else, we recurse. First, we count the number of ways to make +# $target - $this_fib with Fibonnaci numbers larger than $this_fib, then +# we count the number of ways making $target with Fibonnaci numbers larger +# than $this_fib. We return the sum of these counts. +# + +sub count; +sub count ($target, $this_fib = 1, $prev_fib = 1) { + $this_fib > $target ? 0 + : $this_fib == $target ? 1 + : count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) + + count ($target, $this_fib + $prev_fib, $this_fib) +} + + +say count $_ while <>; -- cgit From 102d2d087317bc309c78528411aec474ed93b8e2 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Mon, 25 Oct 2021 14:28:18 +0100 Subject: Add Perl and Python solutions to challenge 136 --- challenge-136/paulo-custodio/perl/ch-1.pl | 45 +++++++++++ challenge-136/paulo-custodio/perl/ch-2.pl | 72 ++++++++++++++++++ challenge-136/paulo-custodio/python/ch-1.py | 43 +++++++++++ challenge-136/paulo-custodio/python/ch-2.py | 112 ++++++++++++++++++++++++++++ challenge-136/paulo-custodio/t/test-1.yaml | 15 ++++ challenge-136/paulo-custodio/t/test-2.yaml | 15 ++++ challenge-136/paulo-custodio/test.pl | 4 + 7 files changed, 306 insertions(+) create mode 100644 challenge-136/paulo-custodio/perl/ch-1.pl create mode 100644 challenge-136/paulo-custodio/perl/ch-2.pl create mode 100644 challenge-136/paulo-custodio/python/ch-1.py create mode 100644 challenge-136/paulo-custodio/python/ch-2.py create mode 100644 challenge-136/paulo-custodio/t/test-1.yaml create mode 100644 challenge-136/paulo-custodio/t/test-2.yaml create mode 100644 challenge-136/paulo-custodio/test.pl diff --git a/challenge-136/paulo-custodio/perl/ch-1.pl b/challenge-136/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..fae0d5f06a --- /dev/null +++ b/challenge-136/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,45 @@ +#!/usr/bin/env perl + +# 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 + +use Modern::Perl; +use ntheory 'gcd'; + +say is_power_2(gcd(@ARGV)); + +sub is_power_2 { + my($n) = @_; + my $p = 2; + while ($p <= $n) { + return 1 if $p==$n; + $p *= 2; + } + return 0; +} diff --git a/challenge-136/paulo-custodio/perl/ch-2.pl b/challenge-136/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..fcbadd1cca --- /dev/null +++ b/challenge-136/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,72 @@ +#!/usr/bin/env perl + +# 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). + +use Modern::Perl; +use Math::Fibonacci 'term'; +use Math::Combinatorics; +use List::Util 'sum'; + +@ARGV or die "Usage: ch-2.pl n\n"; +my $n = shift; +my @fibs = fibonacci_upto($n); +say count_combin_sum($n, @fibs); + + +sub fibonacci_upto { + my($n) = @_; + my @fibs; + my $i = 2; # skip first '1' + do { + push @fibs, term($i++); + } while ($fibs[-1] < $n); + pop @fibs if $fibs[-1] > $n; + return @fibs; +} + +sub count_combin_sum { + my($n, @terms) = @_; + my $count = 0; + for my $k (1..@terms) { + my @combin = combine($k, @terms); + for (@combin) { + my @combo = @$_; + if (sum(@combo) == $n) { + $count++; + } + } + } + return $count; +} diff --git a/challenge-136/paulo-custodio/python/ch-1.py b/challenge-136/paulo-custodio/python/ch-1.py new file mode 100644 index 0000000000..2a65d9aa1d --- /dev/null +++ b/challenge-136/paulo-custodio/python/ch-1.py @@ -0,0 +1,43 @@ +#!/usr/bin/env python3 + +# 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 + +import sys +from math import gcd + +def is_power_2(n): + p = 2 + while p<=n: + if p==n: + return 1 + p *= 2 + return 0 + +print(is_power_2(gcd(int(sys.argv[1]), int(sys.argv[2])))) diff --git a/challenge-136/paulo-custodio/python/ch-2.py b/challenge-136/paulo-custodio/python/ch-2.py new file mode 100644 index 0000000000..092dd8df9d --- /dev/null +++ b/challenge-136/paulo-custodio/python/ch-2.py @@ -0,0 +1,112 @@ +#!/usr/bin/env python3 + +# 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). + +import sys +from itertools import combinations + +def fibonacci(n): + a = 0 + b = 1 + + # Check is n is less + # than 0 + if n < 0: + print("Incorrect input") + + # Check is n is equal + # to 0 + elif n == 0: + return 0 + + # Check if n is equal to 1 + elif n == 1: + return b + else: + for i in range(1, n): + c = a + b + a = b + b = c + return b + +def fibonacci_upto(n): + i = 2 # skip first '1' + fibs = [fibonacci(i)] + i += 1 + while fibs[-1] < n: + fibs.append(fibonacci(i)) + i += 1 + if fibs[-1] > n: + fibs.pop() + return fibs + +def count_combin_sum(n, terms): + count = 0 + for k in range(1, len(terms)+1): + for combin in combinations(terms, k): + if sum(combin)==n: + count += 1 + return count + +n = int(sys.argv[1]) +fibs = fibonacci_upto(n) +print(count_combin_sum(n, fibs)) + +# use Modern::Perl; +# use Math::Fibonacci 'term'; +# use Math::Combinatorics; +# use List::Util 'sum'; +# +# @ARGV or die "Usage: ch-2.pl n\n"; +# my $n = shift; +# my @fibs = fibs_upto($n); +# say count_combin_sum($n, @fibs); +# +# +# sub count_combin_sum { +# my($n, @fibs) = @_; +# my $count = 0; +# for my $k (1..@fibs) { +# my @combin = combine($k, @fibs); +# for (@combin) { +# my @combo = @$_; +# if (sum(@combo) == $n) { +# $count++; +# } +# } +# } +# return $count; +# } +# \ No newline at end of file diff --git a/challenge-136/paulo-custodio/t/test-1.yaml b/challenge-136/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..97ec6250bf --- /dev/null +++ b/challenge-136/paulo-custodio/t/test-1.yaml @@ -0,0 +1,15 @@ +- setup: + cleanup: + args: 8 24 + input: + output: 1 +- setup: + cleanup: + args: 26 39 + input: + output: 0 +- setup: + cleanup: + args: 4 10 + input: + output: 1 diff --git a/challenge-136/paulo-custodio/t/test-2.yaml b/challenge-136/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..a7d9e098ae --- /dev/null +++ b/challenge-136/paulo-custodio/t/test-2.yaml @@ -0,0 +1,15 @@ +- setup: + cleanup: + args: 16 + input: + output: 4 +- setup: + cleanup: + args: 9 + input: + output: 2 +- setup: + cleanup: + args: 15 + input: + output: 2 diff --git a/challenge-136/paulo-custodio/test.pl b/challenge-136/paulo-custodio/test.pl new file mode 100644 index 0000000000..ba6c37260b --- /dev/null +++ b/challenge-136/paulo-custodio/test.pl @@ -0,0 +1,4 @@ +#!/usr/bin/env perl +use Modern::Perl; +use Test::More; +require '../../challenge-001/paulo-custodio/test.pl'; -- cgit From e1d39a471bbb1231f02593283ade0b7d3072e778 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Mon, 25 Oct 2021 14:28:51 +0100 Subject: Merge instead of rebasing --- challenge-001/paulo-custodio/update.sh | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-001/paulo-custodio/update.sh b/challenge-001/paulo-custodio/update.sh index 83d7cebe71..b0079a2ebd 100644 --- a/challenge-001/paulo-custodio/update.sh +++ b/challenge-001/paulo-custodio/update.sh @@ -8,5 +8,5 @@ git push -u origin master git checkout devel git pull -git rebase master -git push --force -u origin devel +git merge master +git push -u origin devel -- cgit From 593e3b55cf0395b75891730d28f8a9eb7a26951a Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 25 Oct 2021 15:36:55 +0200 Subject: AWK solution for week 136 --- challenge-136/abigail/README.md | 2 ++ challenge-136/abigail/aw