diff options
| -rwxr-xr-x | challenge-056/user-person/perl/ch-1.pl | 51 | ||||
| -rwxr-xr-x | challenge-056/user-person/perl/ch-2.pl | 90 | ||||
| -rwxr-xr-x | challenge-056/user-person/python/ch-1.py | 51 | ||||
| -rwxr-xr-x | challenge-056/user-person/python/ch-2.py | 79 |
4 files changed, 271 insertions, 0 deletions
diff --git a/challenge-056/user-person/perl/ch-1.pl b/challenge-056/user-person/perl/ch-1.pl new file mode 100755 index 0000000000..5bc01d279d --- /dev/null +++ b/challenge-056/user-person/perl/ch-1.pl @@ -0,0 +1,51 @@ +#!/usr/bin/env perl + +########################################################################### +# script name: ch-1.pl # +# # +# https://github.com/user-person # +# # +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/ # +# # +# Diff-K # +# You are given an array @N of positive integers (sorted) and another # +# non negative integer k. # +# Write a script to find if there exists 2 indices i and j such that # +# A[i] - A[j] = k and i != j. # +# # +# It should print the pairs of indices, if any such pairs exist. # +# # +# Example: # +# # +# @N = (2, 7, 9) # +# $k = 2 # +# # +# Output : 2,1 # +# # +########################################################################### + +use strict; +use warnings; + +my @n = (2, 7, 9); +my $k = 2; +my @match = (); + +for (my $i = $#n;$i > 0; --$i) { + + my $diff = $n[$i] - $k; + + for (my $j = $i-1; $n[$j] >= $diff ; --$j) { + if ($n[$j] == $diff && $i != $j) { + push @match, "($i, $j)"; + } + } +} + +print "$_ " foreach reverse @match; +print "\n"; + +__END__ +output: + +(2, 1) diff --git a/challenge-056/user-person/perl/ch-2.pl b/challenge-056/user-person/perl/ch-2.pl new file mode 100755 index 0000000000..c3870cff3c --- /dev/null +++ b/challenge-056/user-person/perl/ch-2.pl @@ -0,0 +1,90 @@ +#!/usr/bin/env perl + +########################################################################### +# script name: ch-2.pl # +# # +# https://github.com/user-person # +# # +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/ # +# # +# Path Sum # +# You are given a binary tree and a sum, write a script to find if # +# the tree has a path such that adding up all the values along the path # +# equals the given sum. Only complete paths (from root to leaf node) may # +# be considered for a sum. # +# # +# Example # +# Given the below binary tree and sum = 22, # +# # +# 5 # +# / \ # +# 4 8 # +# / / \ # +# 11 13 9 # +# / \ \ # +# 7 2 1 # +# # +# For the given binary tree, the partial path sum 5 -> 8 -> 9 = 22 is # +# not valid. # +# The script should return the path 5 -> 4 -> 11 -> 7 whose sum is 22 # +# # +########################################################################### + +use strict; +use warnings; + +use Tree::Binary; + +my($btree) = Tree::Binary -> new('5') + -> setLeft( + Tree::Binary -> new('4') + -> setLeft ( + Tree::Binary -> new('11') + -> setLeft (Tree::Binary -> new('7')) + -> setRight(Tree::Binary -> new('2')) + ) + ) + -> setRight ( + Tree::Binary -> new('8') + -> setLeft (Tree::Binary -> new('13')) + -> setRight ( + Tree::Binary -> new('9') + -> setRight ( + Tree::Binary -> new('1')) + ) + ); + +my @branchMemory = (); +my $k = 22; +my $match = 0; +my $toLeafSum = 0; + +$btree -> traverse + ( + sub + { + my($tree) = @_; + $toLeafSum += $tree -> getNodeValue; + + if ( $tree -> hasLeft and $tree -> hasRight ) { + push @branchMemory, $toLeafSum; + } + + if ( $tree->isLeaf) { + ++$match if $toLeafSum == $k; + $toLeafSum = pop @branchMemory; + } + }); + +if ($match == 0 ) { + print "No branch equals $k\n"; +} elsif ($match == 1) { + print "1 branch equals $k\n"; +} else { + print "$match branches equal $k\n"; +} + +__END__ +output: + +1 branch equals 22 diff --git a/challenge-056/user-person/python/ch-1.py b/challenge-056/user-person/python/ch-1.py new file mode 100755 index 0000000000..c0f385a916 --- /dev/null +++ b/challenge-056/user-person/python/ch-1.py @@ -0,0 +1,51 @@ +#!/usr/bin/env python3 + +########################################################################### +# script name: ch-1.py # +# # +# https://github.com/user-person # +# # +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/ # +# # +# Diff-K # +# You are given an array @N of positive integers (sorted) and another # +# non negative integer k. # +# Write a script to find if there exists 2 indices i and j such that # +# A[i] - A[j] = k and i != j. # +# # +# It should print the pairs of indices, if any such pairs exist. # +# # +# Example: # +# # +# @N = (2, 7, 9) # +# $k = 2 # +# # +# Output : 2,1 # +# # +########################################################################### + +n = [2, 7, 9] +k = 2 +match = [] + +i = len(n)-1 + +while i > 0: + j = i-1 + diff = n[i] - k + + while n[j] >= diff: + if n[j] == diff: + match.append('({}, {})'.format(i,j)) + j -= 1 + i -= 1 + +if len(match): + match.reverse() + for x in match: + print(x,end=" ") + print() + +# output: +# +# (2, 1) diff --git a/challenge-056/user-person/python/ch-2.py b/challenge-056/user-person/python/ch-2.py new file mode 100755 index 0000000000..3d7c61b445 --- /dev/null +++ b/challenge-056/user-person/python/ch-2.py @@ -0,0 +1,79 @@ +#!/usr/bin/env python3 + +########################################################################### +# script name: ch-2.py # +# # +# https://github.com/user-person # +# # +# https://perlweeklychallenge.org/blog/perl-weekly-challenge-056/ # +# # +# Path Sum # +# You are given a binary tree and a sum, write a script to find if # +# the tree has a path such that adding up all the values along the path # +# equals the given sum. Only complete paths (from root to leaf node) may # +# be considered for a sum. # +# # +# Example # +# Given the below binary tree and sum = 22, # +# # +# 5 # +# / \ # +# 4 8 # +# / / \ # +# 11 13 9 # +# / \ \ # +# 7 2 1 # +# # +# For the given binary tree, the partial path sum 5 -> 8 -> 9 = 22 is # +# not valid. # +# The script should return the path 5 -> 4 -> 11 -> 7 whose sum is 22 # +# # +########################################################################### + +class Node: + def __init__(self,key): + self.left = None + self.right = None + self.val = key + +branchMemory = [] +k = 22 +match = 0 + +def preOrder(root, toLeafSum): + if root: + toLeafSum += root.val + if root.left != None and root.right != None: + branchMemory.append(toLeafSum) + if root.left == None and root.right == None: + if toLeafSum == k: + global match + match += 1 + if len(branchMemory) > 0: + toLeafSum = branchMemory.pop() + preOrder(root.left, toLeafSum) + preOrder(root.right, toLeafSum) + +bTree = Node(5) +bTree.left = Node(4) +bTree.left.left = Node(11) +bTree.left.left.left = Node(7) +bTree.left.left.right = Node(2) +bTree.right = Node(8) +bTree.right.left = Node(13) +bTree.right.right = Node(9) +bTree.right.right.right = Node(1) + +tLS = 0 +preOrder(bTree,tLS) + +if match == 0: + print('No branch equals', k) +elif match == 1: + print('1 branch equals', k) +else: + print(match, 'branches equal', k) + +# output: +# +# 1 branch equals 22 |