From eedc578f69cb138d999c39d29d3084a21d48b770 Mon Sep 17 00:00:00 2001 From: aliciabielsa Date: Sun, 26 Apr 2020 18:05:17 +0200 Subject: challenge 057 perl --- challenge-057/alicia-bielsa/perl/ch-1.pl | 73 +++++++++++++++++ challenge-057/alicia-bielsa/perl/lib/BinaryTree.pm | 94 ++++++++++++++++++++++ .../alicia-bielsa/perl/lib/BinaryTreeNode.pm | 13 +++ 3 files changed, 180 insertions(+) create mode 100644 challenge-057/alicia-bielsa/perl/ch-1.pl create mode 100644 challenge-057/alicia-bielsa/perl/lib/BinaryTree.pm create mode 100644 challenge-057/alicia-bielsa/perl/lib/BinaryTreeNode.pm 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 -- cgit