Merge pull request #1633 from manfredi/challenge-057

Added solutions for challenge-057

3 files changed, 147 insertions, 0 deletions

diff --git a/challenge-057/manfredi/perl/ch-1.pl b/challenge-057/manfredi/perl/ch-1.pl
new file mode 100755
index 0000000000..a8dff31545
--- /dev/null
+++ b/challenge-057/manfredi/perl/ch-1.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+
+# breadth-first search
+sub bfs {
+	my @ret;
+	my @a = shift;
+	while (@a) {
+		my $v = shift @a or next;
+		push @ret, $v->[0];
+		push @a, @{$v}[1,2];
+	}
+	return @ret;
+}
+
+
+sub invert {
+	my @ret;
+	my @a = shift;
+	while (@a) {
+		my $v = shift @a or next;
+		push @ret, $v->[0];
+		push @a, @{$v}[2,1];
+	}
+	return @ret;
+}
+
+
+
+# Full Binary Tree
+my $tree = [1,[2,[4],[5]],[3,[6],[7]]];
+# my $tree = [1,[2,[4,[8],[9]],[5,[10],[11]]],[3,[6,[12],[13]],[7,[14],[15]]]];
+
+my @bfs = bfs($tree);
+print "Full Binary Tree: [@bfs]\n";
+&pretty_print(\@bfs);
+
+my @inverted = invert($tree);
+print "Full Binary Tree Inverted: [@inverted]\n";
+&pretty_print(\@inverted);
+
+
+# Geometric series, Power of two:
+sub pretty_print($) {
+	my @tree = @{+shift};
+	my $i = 0;
+	while(1) {
+		my $items = 2**$i;
+		my @row = splice @tree, 0, $items;
+		last unless @row;
+		print "| @row\n";
+		$i++;
+	}
+}
+
+
+__END__
+$ ./ch-1.pl
+Full Binary Tree: [1 2 3 4 5 6 7]
+| 1
+| 2 3
+| 4 5 6 7
+Full Binary Tree Inverted: [1 3 2 7 6 5 4]
+| 1
+| 3 2
+| 7 6 5 4
diff --git a/challenge-057/manfredi/perl/ch-2.pl b/challenge-057/manfredi/perl/ch-2.pl
new file mode 100755
index 0000000000..411a456ed7
--- /dev/null
+++ b/challenge-057/manfredi/perl/ch-2.pl
@@ -0,0 +1,54 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+
+sub count($$) {
+    my ($instr, $sub) = @_;
+    my $pos = 0;
+    my $cnt = 0;
+    while ( ($pos = index($instr, $sub, $pos) ) > -1 ) {
+        $pos++;
+        $cnt++;
+    }
+    $cnt;
+}
+
+my %abbr = ();
+my $input = [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ];
+# my $input = [ "alphabet", "car", "carboxy", "book", "carpet", "cadmium", "cadeau", "alpine" ];
+
+# for cases when a starting substring is inside of another string
+my $instr = ':' . join ':', sort @{$input};
+
+my $max = (sort map { length $_ } @{$input})[-1];
+
+for my $length (1..$max) {
+
+    for my $word (@$input) {
+        next if defined $abbr{$word};
+
+        # for cases when $word_a is a starting substring of $word_b, eg. car carpet
+        $abbr{$word} = $word and next if length($word) == $length;
+
+        my $sub = ':' . substr($word, 0, $length);
+        
+        #my $found = () = $instr =~ /$sub/g; # benchmark: slower than "index" version
+        my $found = count($instr, $sub);     # benchmark: about double faster then "regexp" version
+        
+        if ($found == 1) {
+            $sub =~ tr/://d;
+            $abbr{$word} = $sub;
+        }
+    }
+}
+
+my $in  = join ', ',  map { '"'.$_.'"' }        @{$input};
+my $out = join ', ',  map { '"'.$abbr{$_}.'"' } @{$input};
+
+print "Input  [ $in ]\n";
+print "Output [ $out ]\n";
+
+__END__
+$ ./ch-2.pl
+Input  [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ]
+Output [ "alph", "b", "car", "cadm", "cade", "alpi" ]
diff --git a/challenge-057/manfredi/python/ch-2.py b/challenge-057/manfredi/python/ch-2.py
new file mode 100755
index 0000000000..40eccbe644
--- /dev/null
+++ b/challenge-057/manfredi/python/ch-2.py
@@ -0,0 +1,26 @@
+#!/usr/bin/env python3
+
+abbr = {}
+input = [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ]
+# input = [ "alphabet", "car", "carboxy", "book", "carpet", "cadmium", "cadeau", "alpine" ]
+instr = ':' + ':'.join(input)
+max = sorted([ len(s) for s in input])[-1]
+
+for length in range(1, max + 1):
+
+    for word in input:
+        if word in abbr: 
+            continue
+        if len(word) == length:
+            abbr[word] = word
+            continue
+        sub = ':' + word[0:length]
+        found = instr.count(sub)
+
+        if found == 1:
+            abbr[word] = sub.lstrip(':')
+
+output = [ abbr[o] for o in input] 
+print("Input  {}".format(input))
+print("Output {}".format(output))
+