Merge pull request #1634 from user-person/branch-for-challenge-057

User-person's solutions for challenge 57.

3 files changed, 292 insertions, 0 deletions

diff --git a/challenge-057/user-person/perl/ch-1.pl b/challenge-057/user-person/perl/ch-1.pl
new file mode 100755
index 0000000000..cf133edfcf
--- /dev/null
+++ b/challenge-057/user-person/perl/ch-1.pl
@@ -0,0 +1,139 @@
+#!/usr/bin/env perl
+
+###########################################################################
+# script name: ch-1.pl                                                    #
+#                                                                         #
+# https://github.com/user-person                                          #
+#                                                                         #
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-057/         #
+#                                                                         #
+# 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                                                        #
+#                                                                         #
+###########################################################################
+
+use strict;
+use warnings;
+
+use tree::binary;
+use tree::binary::visitor::breadthfirsttraversal;
+
+# Not pretty for trees a depth > 3.
+sub printPretty {
+    my $tree = $_[0];
+    my $height = $tree -> height;
+    my $edge = $height;
+
+    my $visitor = Tree::Binary::Visitor::BreadthFirstTraversal -> new;
+    $tree -> accept($visitor);
+
+    my @nodes = ($visitor -> getResults);
+    my $i = 0;
+    my $leadPos = $height + 2;
+    my $leadingSpace = ' ' x $leadPos;
+    my $spaceBetween = ' ';
+
+    for (my $level = 0; $level < $height; ++$level) {
+        $leadingSpace = ' ' x $leadPos;
+
+        if ($level > 0) {
+            print $leadingSpace;
+            my $betweenLines = ' ';
+            for (my $lineSets = (2**$level) / 2 ; $lineSets > 0; --$lineSets) {
+                print '/' . $betweenLines . '\\' . $betweenLines;
+            }
+
+            print "\n";
+            --$leadPos;
+            $leadingSpace = ' ' x $leadPos;
+       }
+
+        print $leadingSpace;
+        --$leadPos;
+
+        for (my $k = 0; $k < 2**$level; ++$k) {
+            if ( $level == 1) {
+                $spaceBetween = ' ' x 2;
+            } elsif ($level == 2) {
+                $spaceBetween = ' ' x 1;
+            }
+            print $nodes[$i++] . $spaceBetween;
+            print ' ' if $k % 2 == 0;
+        }
+
+        print "\n";
+    }
+    print "\n";
+}
+
+my($bTree) = Tree::Binary -> new('1')
+    -> setLeft(
+        Tree::Binary -> new('2')
+              -> setLeft (
+                  Tree::Binary -> new('4')
+              )
+              -> setRight(Tree::Binary -> new('5')
+              )
+    )
+    -> setRight (
+        Tree::Binary -> new('3')
+              -> setLeft (
+                  Tree::Binary -> new('6')
+              )
+              -> setRight (
+                      Tree::Binary -> new('7')
+              )
+    );
+
+
+printPretty $bTree;
+
+$bTree->mirror();               # The module method does all the work for the inversion.
+
+printPretty $bTree;
+
+__END__
+output:
+
+     1  
+    / \ 
+   2   3  
+  / \ / \ 
+ 4  5 6  7 
+
+     1  
+    / \ 
+   3   2  
+  / \ / \ 
+ 7  6 5  4 
+
diff --git a/challenge-057/user-person/perl/ch-2.pl b/challenge-057/user-person/perl/ch-2.pl
new file mode 100755
index 0000000000..eacaedfa57
--- /dev/null
+++ b/challenge-057/user-person/perl/ch-2.pl
@@ -0,0 +1,81 @@
+#!/usr/bin/env perl
+
+###########################################################################
+# script name: ch-2.pl                                                    #
+#                                                                         #
+# https://github.com/user-person                                          #
+#                                                                         #
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-057/         #
+#                                                                         #
+# Shortest Unique Prefix                                                  #
+# Write a script to find the shortest unique prefix for each each word    #
+# in the given list. The prefixes will not necessarily be of the same     #
+# length.                                                                 #
+#                                                                         #
+# Sample Input                                                            #
+# [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ]         #
+# Expected Output                                                         #
+# [ "alph", "b", "car", "cadm", "cade", "alpi" ]                          #
+#                                                                         #
+###########################################################################
+
+use strict;
+use warnings;
+
+sub charsMatch {
+    my $string1 = $_[0];
+    my $string2 = $_[1];
+    my $count   = 0;
+    my $limit   = 0;
+    my @s1 = split m{}, $string1;
+    my @s2 = split m{}, $string2;
+
+    if ( @s2 > @s1 ) {
+        $limit = $#s1;
+    } else {
+        $limit = $#s2;
+    }
+
+  LETTER_BY_LETTER:
+    for (my $i = 0; $i <= $limit; ++$i) {
+        if ( $s1[$i] eq $s2[$i] ) {
+            ++$count;
+        } else {
+            last LETTER_BY_LETTER;
+        }
+    }
+
+    ++$count if $count + 1 <= $limit;
+    return $count
+}
+
+my @unSorted = qw{ alphabet book carpet cadmium cadeau alpine };
+my %prefix = ();
+
+my @sorted = sort @unSorted;
+my $diff = 0;
+
+for (my $i = 0; $i <= $#sorted; ++$i) {
+    if ( $i == 0 ) {
+       $diff = charsMatch $sorted[0], $sorted[1];
+    } elsif ($i == $#sorted ) {
+       $diff =  charsMatch( $sorted[ $#sorted - 1 ] , $sorted[ $#sorted ] );
+    } else {
+        my $before = charsMatch( $sorted[$i-1] , $sorted[$i]   );
+        my $after  = charsMatch( $sorted[$i]   , $sorted[$i+1] );
+        $diff = $before > $after ? $before : $after;
+    }
+    $prefix{ $sorted[$i] } = substr $sorted[$i], 0, $diff;
+}
+
+print "[ ";
+for ( my $j = 0; $j <=  $#unSorted; ++$j ) {
+    print ", " if $j > 0;
+    print '"' . $prefix{ $unSorted[$j] } . '"';
+}
+print " ]\n";
+
+__END__
+output:
+
+[ "alph", "b", "car", "cadm", "cade", "alpi" ]
diff --git a/challenge-057/user-person/python/ch-2.py b/challenge-057/user-person/python/ch-2.py
new file mode 100755
index 0000000000..793e3f0dc0
--- /dev/null
+++ b/challenge-057/user-person/python/ch-2.py
@@ -0,0 +1,72 @@
+#!/usr/bin/env python3
+
+###########################################################################
+# script name: ch-2.py                                                    #
+#                                                                         #
+# https://github.com/user-person                                          #
+#                                                                         #
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-057/         #
+#                                                                         #
+# Shortest Unique Prefix                                                  #
+# Write a script to find the shortest unique prefix for each each word    #
+# in the given list. The prefixes will not necessarily be of the same     #
+# length.                                                                 #
+#                                                                         #
+# Sample Input                                                            #
+# [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ]         #
+# Expected Output                                                         #
+# [ "alph", "b", "car", "cadm", "cade", "alpi" ]                          #
+#                                                                         #
+###########################################################################
+
+def charsMatch(string1, string2):
+    count = 0
+    limit = 0
+    s1 = list(string1) 
+    s2 = list(string2) 
+    
+    if len(s2) > len(s1):
+        limit = len(s1)
+    else:
+        limit = len(s2)
+
+    for i in range(limit-1):
+        if s1[i] == s2[i]:
+            count += 1
+        else:
+            break
+    if count + 1 < limit:
+        count += 1
+        
+    return count
+
+unSorted = ['alphabet', 'book', 'carpet', 'cadmium', 'cadeau', 'alpine']
+prefix = {}
+
+sortedList = sorted(unSorted)
+diff = 0
+
+for i in range(len(sortedList)):
+    if i == 0:
+        diff = charsMatch( sortedList[i], sortedList[i+1] )
+    elif i == len(sortedList)-1:
+        diff = charsMatch( sortedList[ len(sortedList)-2 ], sortedList[ len(sortedList)-1 ] )
+    else:
+        before = charsMatch( sortedList[i-1], sortedList[i] )
+        after  = charsMatch( sortedList[i],   sortedList[i+1] )
+        if before > after:
+            diff = before
+        else:
+            diff = after
+    prefix[ sortedList[i] ] = sortedList[i][:diff] 
+
+print('[ ',end='')
+for j in range(len(unSorted)):
+    if j > 0:
+        print(', ', end='')
+    print('"' + prefix[ unSorted[j] ] + '"', end='')
+print(']')
+
+# output:
+#
+# [ "alph", "b", "car", "cadm", "cade", "alpi"]