diff options
| -rw-r--r-- | challenge-056/paulo-custodio/Makefile | 2 | ||||
| -rw-r--r-- | challenge-056/paulo-custodio/README | 1 | ||||
| -rw-r--r-- | challenge-056/paulo-custodio/perl/ch-1.pl | 31 | ||||
| -rw-r--r-- | challenge-056/paulo-custodio/perl/ch-2.pl | 85 | ||||
| -rw-r--r-- | challenge-056/paulo-custodio/t/test-1.yaml | 5 | ||||
| -rw-r--r-- | challenge-056/paulo-custodio/t/test-2.yaml | 12 |
6 files changed, 136 insertions, 0 deletions
diff --git a/challenge-056/paulo-custodio/Makefile b/challenge-056/paulo-custodio/Makefile new file mode 100644 index 0000000000..c3c762d746 --- /dev/null +++ b/challenge-056/paulo-custodio/Makefile @@ -0,0 +1,2 @@ +all: + perl ../../challenge-001/paulo-custodio/test.pl diff --git a/challenge-056/paulo-custodio/README b/challenge-056/paulo-custodio/README new file mode 100644 index 0000000000..87dc0b2fbd --- /dev/null +++ b/challenge-056/paulo-custodio/README @@ -0,0 +1 @@ +Solution by Paulo Custodio diff --git a/challenge-056/paulo-custodio/perl/ch-1.pl b/challenge-056/paulo-custodio/perl/ch-1.pl new file mode 100644 index 0000000000..886f866b18 --- /dev/null +++ b/challenge-056/paulo-custodio/perl/ch-1.pl @@ -0,0 +1,31 @@ +#!/usr/bin/env perl + +# Challenge 056 +# +# TASK #1 +# 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 Modern::Perl; + +my($k, @n) = @ARGV; + +for my $i (0 .. $#n-1) { + for my $j ($i+1 .. $#n) { + if (abs($n[$i]-$n[$j])==$k) { + say "$i,$j"; + } + } +} diff --git a/challenge-056/paulo-custodio/perl/ch-2.pl b/challenge-056/paulo-custodio/perl/ch-2.pl new file mode 100644 index 0000000000..cdb3bdba5e --- /dev/null +++ b/challenge-056/paulo-custodio/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/usr/bin/env perl + +# Challenge 056 +# +# TASK #2 +# 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 ? 2 whose sum is 22. + +use Modern::Perl; +use List::Util qw( sum ); + +# tree object +{ + package Tree; + use Object::Tiny::RW qw( value left right ); +} + +my $sum = shift; +my $tree = parse_tree(); +path_sum([], $sum, $tree); + +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 path_sum { + my($path, $sum, $tree) = @_; + my @path = @$path; + push @path, $tree->value; + + if (!$tree->left && !$tree->right) { + say "@path" if sum(@path)==$sum; + } + else { + path_sum([@path], $sum, $tree->left) if $tree->left; + path_sum([@path], $sum, $tree->right) if $tree->right; + } +} diff --git a/challenge-056/paulo-custodio/t/test-1.yaml b/challenge-056/paulo-custodio/t/test-1.yaml new file mode 100644 index 0000000000..96371c5594 --- /dev/null +++ b/challenge-056/paulo-custodio/t/test-1.yaml @@ -0,0 +1,5 @@ +- setup: + cleanup: + args: 2 2 7 9 + input: + output: 1,2 diff --git a/challenge-056/paulo-custodio/t/test-2.yaml b/challenge-056/paulo-custodio/t/test-2.yaml new file mode 100644 index 0000000000..34676690bf --- /dev/null +++ b/challenge-056/paulo-custodio/t/test-2.yaml @@ -0,0 +1,12 @@ +- setup: + cleanup: + args: 12 + input: | + | 5 + | / \ + | 4 8 + | / / \ + | 1 3 9 + | / \ \ + | 7 2 1 + output: 5 4 1 2 |