Merge pull request #1632 from aliciabielsa/branch-for-challenge-057

challenge 057 perl

3 files changed, 180 insertions, 0 deletions

diff --git a/challenge-057/alicia-bielsa/perl/ch-1.pl b/challenge-057/alicia-bielsa/perl/ch-1.pl
new file mode 100644
index 0000000000..97283b64b9
--- /dev/null
+++ b/challenge-057/alicia-bielsa/perl/ch-1.pl
@@ -0,0 +1,73 @@
+use strict;
+use warnings;
+use Data::Dumper;
+use lib 'lib';
+use Moose;
+use BinaryTreeNode;
+use BinaryTree;
+
+
+
+#TASK #1 › Invert Tree
+#You are given a full binary tree of any height, similar to the one below:
+
+
+#       1              
+#      /  \
+#     2    3             
+#    / \  / \
+#   4   5 6  7           
+
+#Write a script to invert the tree, by mirroring the children of every node, from left to right.
+# The expected output from the tree above would be:
+
+
+#      1
+#     /  \
+#    3    2
+#   / \  / \
+#  7   6 5  4
+
+#The input can be any sensible machine-readable binary tree format of your choosing, and the output should be the same format.
+
+#BONUS
+#In addition to the above, you may wish to pretty-print your binary tree in a human readable text-based format similar to the following:
+
+#       1
+#     /  \
+#    3    2
+#   / \  / \
+#  7   6 5  4
+
+my @aValuesTree  =(1 , 2 ,3,4,5,6,7);
+my $nimberValuesTree = scalar( @aValuesTree);
+my $heightBinaryTree =  getHeightFullBinaryTree( $nimberValuesTree);
+
+unless ($heightBinaryTree){
+    die "$nimberValuesTree is not a valid number of values for a full binary tree\n";
+}
+
+my $oBinaryTree = BinaryTree->new( height => $heightBinaryTree);
+$oBinaryTree->addValues(@aValuesTree);
+$oBinaryTree->drawBinaryTree();
+$oBinaryTree->mirrorTree();
+$oBinaryTree->drawBinaryTree();
+
+
+sub getHeightFullBinaryTree {
+    my $numberValues = shift;
+    my $height = 1;
+    my $total = 1;
+    my $valorAnterior =1;
+    while  ($numberValues >= $total ){
+       $total = $total + $valorAnterior * 2 ;       
+       $valorAnterior = $valorAnterior * 2;
+       $height++;
+       if ($total == $numberValues){
+            return $height;  
+       }
+    }
+    return 0;
+}
+
+
diff --git a/challenge-057/alicia-bielsa/perl/lib/BinaryTree.pm b/challenge-057/alicia-bielsa/perl/lib/BinaryTree.pm
new file mode 100644
index 0000000000..0a76ee19f7
--- /dev/null
+++ b/challenge-057/alicia-bielsa/perl/lib/BinaryTree.pm
@@ -0,0 +1,94 @@
+package BinaryTree;
+use Moose;
+use BinaryTreeNode;
+use Data::Dumper;
+
+has 'height' => (is => 'rw', isa => 'Int');
+has 'root' =>   (is => 'rw', isa => 'BinaryTreeNode');
+ 
+
+sub addValues {
+    my $self = shift;
+    my @aValues = @_;
+    $self->{root} = BinaryTreeNode->new( level => 1 );
+    $self->_addValues( $self->{root}, @aValues );
+}
+
+
+
+sub _addValues {
+    my $self = shift;
+    my $node = shift;
+    my @aValues = @_;
+    
+    my @aCurrentNodes = ($node);
+    while(scalar(@aCurrentNodes)){
+        my @aNextNodes =();
+         foreach my $node (@aCurrentNodes){
+            $node->{value} = shift(@aValues);
+            unless ($node->{level} == $self->{height}){
+                $node->{left} = BinaryTreeNode->new(root => 0, level => $node->{level} +1 );
+                $node->{right} = BinaryTreeNode->new(root => 0, level => $node->{level} +1 );
+                push (@aNextNodes, $node->{left});
+                push (@aNextNodes, $node->{right});
+            }
+        }
+        @aCurrentNodes = @aNextNodes;
+    }  
+}
+
+
+sub mirrorTree {
+    my $self = shift;
+    my @aCurrentNodes = ($self->{root}->{left},$self->{root}->{right});
+    while(scalar(@aCurrentNodes)){
+        my @aNextNodes =();
+        my @aValues =();
+        foreach my $node (@aCurrentNodes){
+            push(@aValues, $node->{value});
+        }
+        foreach my $node (@aCurrentNodes){
+            $node->{value} =  pop @aValues;
+            unless ($node->{level} == $self->{height}){
+                push (@aNextNodes, $node->{left});
+                push (@aNextNodes, $node->{right});
+            }
+        }
+        @aCurrentNodes = @aNextNodes;
+    }
+}
+
+
+sub drawBinaryTree {
+    my $self = shift;
+    my $textToPrint ='';
+    my @aCurrentNodes = ($self->{root});
+    while(scalar(@aCurrentNodes)){
+        my @aNextNodes =();
+        my $treeDown = "";
+        foreach my $node (@aCurrentNodes){
+           my $spaces = ($self->{height} * $self->{height} )/ scalar(@aCurrentNodes) ;
+            $textToPrint .= " " x $spaces  ;
+            $textToPrint .= $node->{value};
+            $textToPrint .= " " x  $spaces  ;
+            $treeDown .= " " x  ( $spaces - 1) ;
+            $treeDown .= "/ \\"  ;
+            $treeDown .= " " x  $spaces ;
+            unless ($node->{level} == $self->{height}){
+                push (@aNextNodes, $node->{left});
+                push (@aNextNodes, $node->{right});
+            }
+        }
+        $textToPrint .= "\n";
+        if (@aNextNodes){
+            $textToPrint .= $treeDown;
+            $textToPrint .=  "\n";
+        }
+        @aCurrentNodes = @aNextNodes;
+    }
+    print $textToPrint;
+}
+
+
+
+1;
\ No newline at end of file
diff --git a/challenge-057/alicia-bielsa/perl/lib/BinaryTreeNode.pm b/challenge-057/alicia-bielsa/perl/lib/BinaryTreeNode.pm
new file mode 100644
index 0000000000..ddddc28d85
--- /dev/null
+++ b/challenge-057/alicia-bielsa/perl/lib/BinaryTreeNode.pm
@@ -0,0 +1,13 @@
+package BinaryTreeNode;
+use Moose;
+use Data::Dumper;
+
+has 'value' => (is => 'rw', isa => 'Str');
+has 'left' => (is => 'rw', isa => 'BinaryTreeNode' );
+has 'right' => (is => 'rw', isa => 'BinaryTreeNode' );
+has 'level' => (is => 'rw', isa => 'Int');
+has 'root' => (is => 'rw', isa => 'Bool', default => 0);
+
+
+
+1;
\ No newline at end of file