Merge pull request #2514 from Abigail/abigail/week-082

Abigail/week 082

21 files changed, 330 insertions, 0 deletions

diff --git a/challenge-082/abigail/input-1-1 b/challenge-082/abigail/input-1-1
new file mode 100644
index 0000000000..7a951c42f0
--- /dev/null
+++ b/challenge-082/abigail/input-1-1
@@ -0,0 +1,2 @@
+12
+18
diff --git a/challenge-082/abigail/input-1-2 b/challenge-082/abigail/input-1-2
new file mode 100644
index 0000000000..9ea77d94dc
--- /dev/null
+++ b/challenge-082/abigail/input-1-2
@@ -0,0 +1,2 @@
+18
+23
diff --git a/challenge-082/abigail/input-1-3 b/challenge-082/abigail/input-1-3
new file mode 100644
index 0000000000..f9a24944c8
--- /dev/null
+++ b/challenge-082/abigail/input-1-3
@@ -0,0 +1,2 @@
+125
+925
diff --git a/challenge-082/abigail/input-1-4 b/challenge-082/abigail/input-1-4
new file mode 100644
index 0000000000..75d6512f93
--- /dev/null
+++ b/challenge-082/abigail/input-1-4
@@ -0,0 +1,2 @@
+1022844169
+1465155161
diff --git a/challenge-082/abigail/input-1-5 b/challenge-082/abigail/input-1-5
new file mode 100644
index 0000000000..fbc5debc20
--- /dev/null
+++ b/challenge-082/abigail/input-1-5
@@ -0,0 +1,2 @@
+10619968034
+11935716286
diff --git a/challenge-082/abigail/input-2-1 b/challenge-082/abigail/input-2-1
new file mode 100644
index 0000000000..f2469bebef
--- /dev/null
+++ b/challenge-082/abigail/input-2-1
@@ -0,0 +1,3 @@
+XY
+X
+XXY
diff --git a/challenge-082/abigail/input-2-2 b/challenge-082/abigail/input-2-2
new file mode 100644
index 0000000000..d294e4dd65
--- /dev/null
+++ b/challenge-082/abigail/input-2-2
@@ -0,0 +1,3 @@
+XXY
+XXZ
+XXXXZY
diff --git a/challenge-082/abigail/input-2-3 b/challenge-082/abigail/input-2-3
new file mode 100644
index 0000000000..6e8b1c35e5
--- /dev/null
+++ b/challenge-082/abigail/input-2-3
@@ -0,0 +1,3 @@
+YX
+X
+XXY
diff --git a/challenge-082/abigail/input-2-4 b/challenge-082/abigail/input-2-4
new file mode 100644
index 0000000000..19c0d3d76c
--- /dev/null
+++ b/challenge-082/abigail/input-2-4
@@ -0,0 +1,3 @@
+FOO BAR 1 HELLO
+FOO BAR 2 WORLD
+FOO BAR 2 FOO BAR 1 WORLDHELLO
diff --git a/challenge-082/abigail/output-1-1.exp b/challenge-082/abigail/output-1-1.exp
new file mode 100644
index 0000000000..10cb11b9af
--- /dev/null
+++ b/challenge-082/abigail/output-1-1.exp
@@ -0,0 +1,5 @@
+# Simple example
+1
+2
+3
+6
diff --git a/challenge-082/abigail/output-1-2.exp b/challenge-082/abigail/output-1-2.exp
new file mode 100644
index 0000000000..7eda1a7f91
--- /dev/null
+++ b/challenge-082/abigail/output-1-2.exp
@@ -0,0 +1,2 @@
+# No common factors other than 1
+1
diff --git a/challenge-082/abigail/output-1-3.exp b/challenge-082/abigail/output-1-3.exp
new file mode 100644
index 0000000000..a271d88974
--- /dev/null
+++ b/challenge-082/abigail/output-1-3.exp
@@ -0,0 +1,4 @@
+# GCD is a perfect square
+1
+5
+25
diff --git a/challenge-082/abigail/output-1-4.exp b/challenge-082/abigail/output-1-4.exp
new file mode 100644
index 0000000000..6d0a6cea95
--- /dev/null
+++ b/challenge-082/abigail/output-1-4.exp
@@ -0,0 +1,3 @@
+# GCD is a large prime
+1
+27644437
diff --git a/challenge-082/abigail/output-1-5.exp b/challenge-082/abigail/output-1-5.exp
new file mode 100644
index 0000000000..d8fa058fcf
--- /dev/null
+++ b/challenge-082/abigail/output-1-5.exp
@@ -0,0 +1,65 @@
+# Lots of factors
+1
+2
+13
+17
+19
+26
+31
+34
+38
+62
+221
+247
+323
+361
+403
+442
+494
+527
+589
+646
+722
+806
+1054
+1178
+4199
+4693
+6137
+6851
+6859
+7657
+8398
+9386
+10013
+11191
+12274
+13702
+13718
+15314
+20026
+22382
+79781
+89167
+116603
+130169
+145483
+159562
+178334
+190247
+212629
+233206
+260338
+290966
+380494
+425258
+1515839
+2473211
+2764177
+3031678
+3614693
+4946422
+5528354
+7229386
+46991009
+93982018
diff --git a/challenge-082/abigail/output-2-1.exp b/challenge-082/abigail/output-2-1.exp
new file mode 100644
index 0000000000..3b20e34eeb
--- /dev/null
+++ b/challenge-082/abigail/output-2-1.exp
@@ -0,0 +1,2 @@
+# Very simple match
+1
diff --git a/challenge-082/abigail/output-2-2.exp b/challenge-082/abigail/output-2-2.exp
new file mode 100644
index 0000000000..d58ab7476b
--- /dev/null
+++ b/challenge-082/abigail/output-2-2.exp
@@ -0,0 +1,2 @@
+# Another simple match
+1
diff --git a/challenge-082/abigail/output-2-3.exp b/challenge-082/abigail/output-2-3.exp
new file mode 100644
index 0000000000..64d32460c4
--- /dev/null
+++ b/challenge-082/abigail/output-2-3.exp
@@ -0,0 +1,2 @@
+# No match
+0
diff --git a/challenge-082/abigail/output-2-4.exp b/challenge-082/abigail/output-2-4.exp
new file mode 100644
index 0000000000..96e3e6efa7
--- /dev/null
+++ b/challenge-082/abigail/output-2-4.exp
@@ -0,0 +1,2 @@
+# Backtracking required
+1
diff --git a/challenge-082/abigail/perl/ch-1.pl b/challenge-082/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..34db614e9b
--- /dev/null
+++ b/challenge-082/abigail/perl/ch-1.pl
@@ -0,0 +1,76 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# Challenge
+#
+#   You are given 2 positive numbers $M and $N.
+#
+#   Write a script to list all common factors of the given numbers.
+#
+
+#
+# All common factors are the factors of the greatest common divider (gcd)
+# Find the gcd is easy, Euclid already had an algorithm.
+#
+
+#
+# However, finding all factors of a given number is a HARD PROBLEM.
+# Easy to brute force for small numbers, but we'd need a sieve to
+# do this for some what larger numbers. For most numbers, even a sieve
+# will be unwieldy.
+#
+# Let's hope we only get smallish numbers...
+#
+
+#
+# Get the two numbers
+#
+chomp (my $M = <>);
+chomp (my $N = <>);
+
+
+#
+# Find the GCD, using Stein's algorithm
+#    (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
+#
+sub stein;
+sub stein ($u, $v) {
+    return $u if $u == $v || !$v;
+    return $v if             !$u;
+    my $u_odd = $u % 2;
+    my $v_odd = $v % 2;
+    return stein ($u >> 1, $v >> 1) << 1 if !$u_odd && !$v_odd;
+    return stein ($u >> 1, $v)           if !$u_odd &&  $v_odd;
+    return stein ($u,      $v >> 1)      if  $u_odd && !$v_odd;
+    return stein ($u - $v, $v)           if  $u     >   $v;
+    return stein ($v - $u, $u);
+}
+
+
+my $gcd = stein $M, $N;
+
+#
+# Brute force finding all factors
+#
+my $max = int sqrt $gcd;
+my @small;   # All factors <= sqrt ($gcd);
+my @large;   # All factors >  sqrt ($gcd);
+for (my $i = 1; $i <= $max; $i ++) {
+    next if $gcd % $i;
+    push @small => $i;
+    # If $gcd is a perfect square, we should not report
+    # its square root twice.
+    push @large => $gcd / $i unless $gcd / $i == $i;
+}
+say for @small, reverse @large;
+
+__END__
diff --git a/challenge-082/abigail/perl/ch-2.pl b/challenge-082/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..8a176e1e79
--- /dev/null
+++ b/challenge-082/abigail/perl/ch-2.pl
@@ -0,0 +1,63 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# Challenge
+#
+#   You are given 3 strings; $A, $B and $C.
+#   
+#   Write a script to check if $C is created by interleave $A and $B.
+#   
+#   Print 1 if check is success otherwise 0.
+#
+
+chomp (my $A = <>);
+chomp (my $B = <>);
+chomp (my $C = <>);
+
+sub is_interleaved;
+sub is_interleaved ($A, $B, $C) {
+    #
+    # If $A or $B is empty, the other should equal $C.
+    # This also takes care of the situation where all strings
+    # are empty (which means, they are interleaved).
+    # 
+    return $A eq $C if !length $B;
+    return $B eq $C if !length $A;
+
+    #
+    # The length of $C must equal the length of $A plus the
+    # length of $B, else $C cannot be an interleaving of $A and $B.
+    #
+    return unless length ($A) + length ($B) == length ($C);
+
+    #
+    # Now, let $A = a . A', $B = b . B', $C = c . C', where
+    # a, b, and c are the first characters of the strings 
+    # $A, $B, $C, and A', B', C' the rest of the strings.
+    # $C is an interleaving of $A and $B if one of the following
+    # statements is true:
+    #    * a eq c, and C' is an interleaving of  A' and $B.
+    #    * b eq c, and C' is an interleaving of $A  and  B'.
+    #
+    # Note that at this point, none of the strings $A, $B or $C are empty.
+    #
+    my ($a, $A_prime) = $A =~ /^(.)(.*)$/;
+    my ($b, $B_prime) = $B =~ /^(.)(.*)$/;
+    my ($c, $C_prime) = $C =~ /^(.)(.*)$/;
+    return $a eq $c && is_interleaved ($A_prime, $B,       $C_prime) ||
+           $b eq $c && is_interleaved ($A,       $B_prime, $C_prime);
+}
+
+say is_interleaved ($A, $B, $C) ? 1 : 0;
+
+
+__END__
diff --git a/challenge-082/abigail/test.pl b/challenge-082/abigail/test.pl
new file mode 100755
index 0000000000..aa84e275d5
--- /dev/null
+++ b/challenge-082/abigail/test.pl
@@ -0,0 +1,82 @@
+#!/opt/perl/bin/perl
+
+#
+# Test the solutions. Either call it with the directory name you
+# want to test in, or call it as "../test.pl" from within the directory.
+#
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+chdir ".." if -f "../test.pl";
+
+use experimental 'signatures';
+
+use Test::More;
+
+
+my %languages = (
+    Perl        =>   {
+        exe     =>   "/opt/perl/bin/perl",
+        ext     =>   "pl",
+    },
+    JavaScript  =>   {
+        exe     =>   "/usr/local/bin/node",
+        ext     =>   "js",
+        dir     =>   "node",
+    },
+    bc          =>   {
+        exe     =>   "/usr/bin/bc",
+        ext     =>   "bc",
+        filter  =>   's/.*/main($&)/',
+    },
+    awk         =>   {
+        exe     =>   "/usr/bin/awk",
+        ext     =>   "awk",
+        args    =>   ["-f"],
+    },
+);
+
+my $perl_exe = $languages {Perl} {exe};
+
+foreach my $challenge (1, 2) {
+    my @inputs = <input-$challenge-*> or next;
+    subtest "Challenge $challenge" => sub {
+        foreach my $language (sort keys %languages) {
+            my $info     =   $languages {$language};
+            my $exe      =   $$info {exe};
+            my $ext      =   $$info {ext};
+            my $dir      =   $$info {dir}    // lc $language;
+            my @args     = @{$$info {args}   // []};
+            my $filter   =   $$info {filter} // '';
+            my $solution =  "$dir/ch-$challenge.$ext";
+            next unless -r $solution;
+
+            subtest $language => sub {
+                foreach my $input (@inputs) {
+                    my $output_exp = ($input =~ s/input/output/r) . ".exp";
+                    my $exp        = `cat $output_exp`;
+
+                    my $name = $input;
+                    if ($exp =~ s/^\s*#\s*(.*)\n//) {
+                        $name = $1;
+                    }
+
+                    my $got = `$perl_exe -ple '$filter' $input |\
+                               $exe @args ./$solution`;
+
+                    s/\h+$//gm for $exp, $got;
+                    is $got, $exp, $name;
+                }
+            }
+        }
+    }
+}
+
+done_testing;
+
+
+__END__