Merge pull request #1580 from kevincolyer/branch-056

Branch 056

3 files changed, 109 insertions, 0 deletions

diff --git a/challenge-056/kevin-colyer/raku/ch-1.p6 b/challenge-056/kevin-colyer/raku/ch-1.p6
new file mode 100644
index 0000000000..220851bd36
--- /dev/null
+++ b/challenge-056/kevin-colyer/raku/ch-1.p6
@@ -0,0 +1,32 @@
+#!perl6
+# Task 1 Challenge 056 Solution by kevincolyer
+# 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
+
+
+sub findIndiceDiff(@N, $k) {
+    for ^(@N.elems-1) -> $j {
+        for $j+1..^@N.elems -> $i {
+            next if $i == $j;
+            # Returns solution if found
+            return $i,$j if @N[$i]-@N[$j] == $k;
+            # abort if diff is >k as will never get less...
+            last if @N[$i]-@N[$j] > $k;
+        }
+    }
+    # fail
+    return 0,0;
+}
+
+use Test;
+is findIndiceDiff( (2,7,9), 2 ), (2,1), "Example solved";
+is findIndiceDiff( (2,7,9), 3 ), (0,0), "Example should not solve";
+is findIndiceDiff( (2,7,9), 5 ), (1,0), "Example modified solved";
+is findIndiceDiff( (2,3,4,5,6,7,14), 7 ), (6,5), "Longer Example modified solved";
diff --git a/challenge-056/kevin-colyer/raku/ch-2.p6 b/challenge-056/kevin-colyer/raku/ch-2.p6
new file mode 100644
index 0000000000..ae5fa2ef8b
--- /dev/null
+++ b/challenge-056/kevin-colyer/raku/ch-2.p6
@@ -0,0 +1,76 @@
+#!perl6
+# Task 2 Challenge 056 Solution by kevincolyer
+# 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.
+# ExampleGiven 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.
+
+class node {
+    has Int $.value;
+    has node $.left;
+    has node $.right;
+}
+
+my $root = node.new(value => 5, 
+    left => node.new(value => 4, left => node.new(value =>11, left=>node.new(value=>7),right => node.new(value => 2))),
+    right => node.new(value=>8,left=>node.new(value=>13),right=> node.new(value=>9,right=> node.new(value=>1)))
+    );
+
+
+sub dfs($node,$target,$new=True) {
+    state $found=False;
+    state @values;
+    if $new { 
+        @values = Empty; 
+        $found=False; 
+    }
+    my $siblings=0;
+    @values.push: $node.value;
+
+    if $node.left:defined { 
+        $siblings++;
+        dfs($node.left, $target,False);
+        return @values if $found;
+    }
+
+    if $node.right:defined { 
+        $siblings++;
+        dfs($node.right,$target,False);
+        return @values if $found;
+    } 
+    
+    # lone leaf
+    if $siblings==0 and @values.sum==$target {
+        $found=True;
+        return @values;
+    }
+    
+    # not found so back track
+    @values.pop;
+    return Empty;
+}
+multi MAIN('test') {
+    dfs($root,$_).say for 15..30;
+}
+
+multi MAIN(Int $target where * > 0) {
+    my @values=dfs($root,$target);
+    if @values == Empty {
+        say "Target sum [$target] not found in tree";
+        exit;
+    }
+    say @values.join(" -> ") ~ " = $target";
+}
diff --git a/challenge-056/kevincolyer b/challenge-056/kevincolyer
new file mode 120000
index 0000000000..8fc47c15c2
--- /dev/null
+++ b/challenge-056/kevincolyer
@@ -0,0 +1 @@
+kevin-colyer
\ No newline at end of file