Merge pull request #4110 from E7-87-83/newt

submission for Week 113

3 files changed, 190 insertions, 0 deletions

diff --git a/challenge-113/cheok-yin-fung/blog.txt b/challenge-113/cheok-yin-fung/blog.txt
new file mode 100644
index 0000000000..90ee3dcca1
--- /dev/null
+++ b/challenge-113/cheok-yin-fung/blog.txt
@@ -0,0 +1 @@
+http://e7-87-83.github.io/coding/challenge_113.html
diff --git a/challenge-113/cheok-yin-fung/perl/ch-1.pl b/challenge-113/cheok-yin-fung/perl/ch-1.pl
new file mode 100644
index 0000000000..6197890686
--- /dev/null
+++ b/challenge-113/cheok-yin-fung/perl/ch-1.pl
@@ -0,0 +1,103 @@
+#!/usr/bin/perl
+# The Weekly Challenge 113
+# Task 1 Represent Integer
+use strict;
+use warnings;
+
+my $_N = $ARGV[0];
+my $_D = $ARGV[1];
+
+die "Usage: ch-1.pl [a positive integer] [a digit]\n" 
+    unless $_N && $_N =~ /^\d+$/ && $_D =~ /^\d$/;
+
+print representable($_N, $_D), "\n";
+
+
+
+sub representable {
+    my $N = $_[0];
+    my $D = $_[1];
+    
+    if ($D == 0) {
+        if ($N >= 100 || $N % 10 == 0) {
+            return 1;
+        }
+        else {
+            return 0;
+        }
+    }
+    
+    return 1 if $N >= 10*$D;   
+    # important line; below we deal with $N < 10*$D only
+
+    return 1 if $N % $D == 0;  # $N = $D + $D + ... + $D, esp $D == 1
+    return 0 if $D == 2 || $D == 5;
+
+    if ($D == 4 && $N > 10) {
+        if ($N % 2 == 0) {
+            return 1;
+        } 
+        else {
+            return 0;
+        }
+    }
+
+    if ($D == 8 && $N >= 40) {
+        if ($N % 2 == 0) {
+            return 1;
+        }
+        else {
+            return 0;
+        }
+    }
+
+    if ($D == 6) {
+        return 0 if $N % 2 != 0;
+    }
+ #   check on $D == 3, 7, 9 or remaining cases for $D == 4, 6 , 8
+    return step_down($D, $N); # can be replaced by &last_digit
+}
+
+sub step_down {
+    # Example   I: if N = 82, D = 9, it hints 82 = 9*7+19
+    # Example  II: if N = 64, D = 7, it hints 64 = 7*1+57
+    # Example III: if N = 30, D = 8, the set {8, 18, 28} ...
+    # Example  IV: if N = 44, D = 6, it hints 44 = 6*3+26
+    my $digit = $_[0];
+    my $short = $_[1];
+    my $temp_short = $short;
+    do {
+        return 1 if $temp_short =~ /$digit/;
+        $temp_short -= $digit;
+    } while ($temp_short > 0);   
+    return 0;
+}
+
+sub last_digit {
+    # Example   I: if N = 82, D = 9, it hints 82 = 72+10 = 9*8+10 = 9*7+19
+    # Example  II: if N = 64, D = 7, it hints 64 = 14+50 = 7*2+50 = 7*1+57
+    # Example III: if N = 30, D = 8, the set {8, 18, 28} ...
+    # Example  IV: if N = 44, D = 6, it hints 44 = 24+20 = 6*4+20 = 6*3+26
+    my $digit = $_[0];
+    my $short = $_[1];
+    my $last_digit_of_short = $short % 10;
+    my $i = 1;
+    while ($digit*$i < $short) {
+        if ($digit*$i % 10  == $last_digit_of_short ) {
+            return 1;
+        }
+        $i++;
+    }
+    return 0;
+}
+
+
+=pod
+ Testing:
+ for (my $i = 10; $i < 70; $i++) {
+     print $i," " , representable($i, 7) , "\n";
+ }
+ for (my $i = 10; $i < 90; $i++) {
+     print $i," " , representable($i, 9) , "\n";
+ }
+=cut
diff --git a/challenge-113/cheok-yin-fung/perl/ch-2.pl b/challenge-113/cheok-yin-fung/perl/ch-2.pl
new file mode 100644
index 0000000000..d371237f53
--- /dev/null
+++ b/challenge-113/cheok-yin-fung/perl/ch-2.pl
@@ -0,0 +1,86 @@
+#!/usr/bin/perl
+# The Weekly Challenge 113
+# Task 2 Recreate Binary Tree
+use strict;
+use warnings;
+use Data::Dumper; # use for print_pretty_tree
+
+die <<FOO
+Incorrect input format.
+Usage: ch-2.pl [binary tree in array format, \'x\' for null nodes]
+for example, \$ ch-2.pl 2 3 5 x 7
+
+    2 
+   / \\
+  3   5
+   \\
+    7
+FOO
+    unless consistency(@ARGV);
+
+my @tree = map { $_ eq 'x' ? undef : $_ } @ARGV;
+
+my $sum = 0;
+
+for (@tree) {
+    $sum += $_ if defined($_);
+}
+
+for (@tree) {
+    $_ = $sum - $_ if defined($_);
+}
+
+print_tree(@tree);
+print_pretty_tree(@tree);
+
+
+sub consistency {
+    my @t = @_;
+    return 0 if !defined($t[0]) || ($t[0] !~ /^\d+$/ && $t[0] ne 'x');
+    for my $ind (1..$#t) { 
+        if ($t[$ind] =~ /^\d+$/) {
+            if ($t[($ind-1)/2] eq 'x') {
+                return 0;
+            }
+        } 
+        elsif ($t[$ind] ne 'x') {
+            return 0;
+        }
+    }
+    return 1;
+}
+
+sub print_tree {
+    print "Output in Array Format:\n";
+    for my $v (@_) {
+        if (defined($v)) {
+            print $v, " ";
+        } 
+        else {
+            print 'x', " ";
+        }
+    }
+    print "\n";
+}
+
+
+sub print_pretty_tree {
+    my @tr = @_;
+    my $hash_tree = tree_build( \@tr, 0);
+
+    $Data::Dumper::Terse = 1; 
+    $Data::Dumper::Indent = 2;
+    $Data::Dumper::Sortkeys = 1;
+    print "\n"; 
+    print "Output in Hash Format:\n";
+    print Dumper $hash_tree; 
+}
+
+sub tree_build {        # use for print_pretty_tree
+    my @t = @{$_[0]};
+    my $ind = $_[1]; 
+    my %leaf = ( "v" => $t[$ind] );
+    $leaf{"l"} = tree_build(\@t, $ind*2+1) if defined($t[$ind*2+1]);
+    $leaf{"r"} = tree_build(\@t, $ind*2+2) if defined($t[$ind*2+2]);
+    return \%leaf;
+}