Merge pull request #1606 from adamcrussell/challenge-056

solution for challenge-056

5 files changed, 170 insertions, 0 deletions

diff --git a/challenge-056/adam-russell/blog.txt b/challenge-056/adam-russell/blog.txt
new file mode 100644
index 0000000000..4f188236d7
--- /dev/null
+++ b/challenge-056/adam-russell/blog.txt
@@ -0,0 +1 @@
+https://adamcrussell.livejournal.com/15709.html
diff --git a/challenge-056/adam-russell/ch-2.dot b/challenge-056/adam-russell/ch-2.dot
new file mode 100644
index 0000000000..e4f9e91e48
--- /dev/null
+++ b/challenge-056/adam-russell/ch-2.dot
@@ -0,0 +1,25 @@
+digraph GRAPH_0 {
+
+  // Generated by Graph::Easy 0.76 at Sun Apr 19 18:11:09 2020
+
+  edge [ arrowhead=open ];
+  graph [ rankdir=LR ];
+  node [
+    fillcolor=white,
+    fontsize=11,
+    shape=box,
+    style=filled ];
+
+  "11*" -> "6*" [ color="#000000:#000000" ]
+  "11*" -> 19 [ color="#000000:#000000" ]
+  19 -> 43 [ color="#000000:#000000" ]
+  19 -> 17 [ color="#000000:#000000" ]
+  "6*" -> 4 [ color="#000000:#000000" ]
+  "6*" -> "8*" [ color="#000000:#000000" ]
+  43 -> 49 [ color="#000000:#000000" ]
+  43 -> 31 [ color="#000000:#000000" ]
+  4 -> 5 [ color="#000000:#000000" ]
+  "8*" -> "10*" [ color="#000000:#000000" ]
+
+}
+
diff --git a/challenge-056/adam-russell/ch-2.png b/challenge-056/adam-russell/ch-2.png
new file mode 100644
index 0000000000..bc5dfddea4
--- /dev/null
+++ b/challenge-056/adam-russell/ch-2.png
diff --git a/challenge-056/adam-russell/perl/ch-1.pl b/challenge-056/adam-russell/perl/ch-1.pl
new file mode 100644
index 0000000000..972c64a8d5
--- /dev/null
+++ b/challenge-056/adam-russell/perl/ch-1.pl
@@ -0,0 +1,30 @@
+use strict;
+use warnings;
+##
+# You are given an array @N of positive 
+# integers (sorted) and another non negative integer k.
+# Write a script to find if there exists two indices 
+# i and j such that A[i] - A[j] = k and i != j.
+# Print the pairs of indices, if any such pairs exist.
+my @N = (2, 7, 9);
+my $k = 2;
+my @pairs; 
+for my $i (0 .. @N - 1){
+    for my $j (0 .. @N - 1){
+        push @pairs, [$i, $j] if($N[$i] - $N[$j] == $k && $i != $j);  
+    }
+}
+if(!@pairs){
+    print "No matching pairs\n";     
+}
+elsif(@pairs == 1){
+    print "Matching Pair: "; 
+    print "(" . join(",", @{$pairs[0]}) . ")\n"; 
+}
+else{
+    print "Matching Pairs: "; 
+    for my $i (0 .. @pairs - 2){
+        print "(" . join(",", @{$pairs[$i]}) . "), "; 
+    }
+    print "(" . join(",", @{$pairs[@pairs - 1]}) . ")\n"; 
+}
diff --git a/challenge-056/adam-russell/perl/ch-2.pl b/challenge-056/adam-russell/perl/ch-2.pl
new file mode 100644
index 0000000000..f0d116921d
--- /dev/null
+++ b/challenge-056/adam-russell/perl/ch-2.pl
@@ -0,0 +1,114 @@
+use strict;
+use warnings;
+##
+# 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 
+# Only complete paths (from root to leaf node)
+# may be considered for a sum.
+##
+use Graph;
+use boolean; 
+use Graph::Easy::Parser;
+
+use constant SUM => 35;
+
+sub insert{
+    my($graph, $root, $next) = @_;
+    if(!$graph->vertices()){
+        $graph->add_vertex($next);
+        $graph->set_edge_attribute($next, "left", "left", true);
+        $graph->set_edge_attribute($next, "right", "right", true);
+        return $next; 
+    } 
+    if($root > $next){
+        if($graph->has_edge_attribute($root, "left", "left")){
+            $graph->delete_edge_attributes($root, "left");
+            $graph->set_edge_attribute($root, $next, "left", true);
+            $graph->set_edge_attribute($next, "left", "left", true);
+            $graph->set_edge_attribute($next, "right", "right", true);
+        } 
+        my @successors = $graph->successors($root);
+        for my $s (@successors){
+            if($graph->has_edge_attribute($root, $s, "left")){
+                insert($graph, $s, $next); 
+            }  
+        } 
+    }  
+    if($root < $next){
+        if($graph->has_edge_attribute($root, "right", "right")){
+            $graph->delete_edge_attributes($root, "right");
+            $graph->set_edge_attribute($root, $next, "right", true);
+            $graph->set_edge_attribute($next, "left", "left", true);
+            $graph->set_edge_attribute($next, "right", "right", true);
+        } 
+        my @successors = $graph->successors($root);
+        for my $s (@successors){
+            if($graph->has_edge_attribute($root, $s, "right")){
+                insert($graph, $s, $next); 
+            }  
+        } 
+    }  
+}
+
+sub find_path_sum{
+    my($graph, $sum, $path) = @_;
+    my $parent = $path->[-1];
+    my @children = $graph->successors($parent); 
+    for my $v (@children){
+        push @{$path}, $v;
+        my $total = unpack("%32C*", pack("C*", @{$path})); 
+        if($total == $sum && $graph->is_sink_vertex($v)){
+            return $path; 
+        }
+        else{
+            my @p = @{$path};
+            $path = find_path_sum($graph, $sum, \@p) if @p;  
+            if($path){
+                my $total = unpack("%32C*", pack("C*", @{$path})); 
+                return $path if $total == $sum;
+            }
+        }
+    }  
+}
+
+sub display_path{
+    my($graph, $path) = @_;
+    my $s = $graph->stringify();
+    for my $v (@{$path}){
+        my $v_ = "$v*"; 
+        $s =~ s/$v/$v_/g; 
+    } 
+    my @s = split(/,/, $s); 
+    my @lines;
+    for my $n (@s){
+        my @a = split(/-/, $n);
+        push @lines, "[ $a[0] ] => [ $a[1] ]";  
+    } 
+    my $parser = new Graph::Easy::Parser(); 
+    my $graph_viz = $parser->from_text(join("", @lines));
+    print $graph_viz->as_ascii(); 
+    #print $graph_viz->as_graphviz(); 
+}
+
+MAIN:{
+    my $graph = new Graph(multivertexed => true);
+    my @a = (11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31);
+    my $root;
+    for my $a (@a){ 
+        if(!$root){
+            $root = insert($graph, $root, $a)
+        }
+        else{
+            insert($graph, $root, $a)
+        }
+    }
+    while($graph->has_vertex("left") && $graph->has_vertex("right")){
+        $graph->delete_vertices("left", "right");
+    }
+    my $path = find_path_sum($graph, SUM, [$root]);
+    display_path($graph, $path); 
+}
+
+__END__
+11*-19,11-6*,19-17,19-43,4-5,43-31,43-49,6-4,6-8*,8-10*