From 324bcc1de2a7f771da7b70cdaef60403936adc4a Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Sun, 11 Oct 2020 14:06:07 +0200
Subject: Perl solution week 81/part 1.

---
 challenge-081/abigail/input-1-1      |  2 ++
 challenge-081/abigail/input-1-2      |  2 ++
 challenge-081/abigail/output-1-1.exp |  2 ++
 challenge-081/abigail/output-1-2.exp |  1 +
 challenge-081/abigail/perl/ch-1.pl   | 37 ++++++++++++++++++++++++++++++++++++
 5 files changed, 44 insertions(+)
 create mode 100644 challenge-081/abigail/input-1-1
 create mode 100644 challenge-081/abigail/input-1-2
 create mode 100644 challenge-081/abigail/output-1-1.exp
 create mode 100644 challenge-081/abigail/output-1-2.exp
 create mode 100644 challenge-081/abigail/perl/ch-1.pl

diff --git a/challenge-081/abigail/input-1-1 b/challenge-081/abigail/input-1-1
new file mode 100644
index 0000000000..bcb118a7c2
--- /dev/null
+++ b/challenge-081/abigail/input-1-1
@@ -0,0 +1,2 @@
+abcdabcd
+abcdabcdabcdabcd
diff --git a/challenge-081/abigail/input-1-2 b/challenge-081/abigail/input-1-2
new file mode 100644
index 0000000000..0917019ba6
--- /dev/null
+++ b/challenge-081/abigail/input-1-2
@@ -0,0 +1,2 @@
+aaa
+aa
diff --git a/challenge-081/abigail/output-1-1.exp b/challenge-081/abigail/output-1-1.exp
new file mode 100644
index 0000000000..ddf5cedb9f
--- /dev/null
+++ b/challenge-081/abigail/output-1-1.exp
@@ -0,0 +1,2 @@
+abcdabcd
+abcd
diff --git a/challenge-081/abigail/output-1-2.exp b/challenge-081/abigail/output-1-2.exp
new file mode 100644
index 0000000000..7898192261
--- /dev/null
+++ b/challenge-081/abigail/output-1-2.exp
@@ -0,0 +1 @@
+a
diff --git a/challenge-081/abigail/perl/ch-1.pl b/challenge-081/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..840fc865f9
--- /dev/null
+++ b/challenge-081/abigail/perl/ch-1.pl
@@ -0,0 +1,37 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+chomp (my $str1 = <>);
+chomp (my $str2 = <>);
+
+#
+# Sort the strings by lenght, so $str1 isn't longer than $str2.
+#
+($str1, $str2) = ($str2, $str1) if length $str2 < length $str1;
+
+#
+# Find a substring which cannot be part of either string,
+# nor of its concatenation.
+#
+my $sep = "\x00" x (1 + length ($str1) + length ($str2));
+
+#
+# Now, use a regular expression to find common base strings.
+#
+$_ = "$str1$sep$str2";
+/^ (.+) \1*     # Find base strings of $str1
+   $sep         # Match the separator
+   \1+ $        # Must be base string for $str2
+   (?{say $1})  # Print it
+   (*FAIL)      # Backtrack so we can try other base strings.
+/x;
+
+__END__
-- 
cgit 


From 8c2055832821dd32c01d778b60edeb527321dd0d Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 13 Oct 2020 22:36:14 +0200
Subject: Copy test file from previous week.

---
 challenge-082/abigail/test.pl | 77 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100755 challenge-082/abigail/test.pl

diff --git a/challenge-082/abigail/test.pl b/challenge-082/abigail/test.pl
new file mode 100755
index 0000000000..310382b62b
--- /dev/null
+++ b/challenge-082/abigail/test.pl
@@ -0,0 +1,77 @@
+#!/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 $got = `$perl_exe -ple '$filter' $input |\
+                               $exe @args ./$solution`;
+
+                    s/\h+$//gm for $exp, $got;
+                    is $got, $exp, $input;
+                }
+            }
+        }
+    }
+}
+
+done_testing;
+
+
+__END__
-- 
cgit 


From 451aa794bc362387e18b8cb71a6978f87db09b46 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 13 Oct 2020 23:46:05 +0200
Subject: Optional test names.

---
 challenge-082/abigail/test.pl | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/challenge-082/abigail/test.pl b/challenge-082/abigail/test.pl
index 310382b62b..349ee00c1e 100755
--- a/challenge-082/abigail/test.pl
+++ b/challenge-082/abigail/test.pl
@@ -60,11 +60,16 @@ foreach my $challenge (1, 2) {
                     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, $input;
+                    is $got, $exp, $name;
                 }
             }
         }
-- 
cgit 


From a2517c19f86c51a4e071f832c90c332ecd48d9ec Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 13 Oct 2020 23:46:46 +0200
Subject: Perl solution for week 082/part 1

---
 challenge-082/abigail/input-1-1      |  2 +
 challenge-082/abigail/input-1-2      |  2 +
 challenge-082/abigail/input-1-3      |  2 +
 challenge-082/abigail/input-1-4      |  2 +
 challenge-082/abigail/input-1-5      |  2 +
 challenge-082/abigail/output-1-1.exp |  5 +++
 challenge-082/abigail/output-1-2.exp |  2 +
 challenge-082/abigail/output-1-3.exp |  4 ++
 challenge-082/abigail/output-1-4.exp |  3 ++
 challenge-082/abigail/output-1-5.exp | 65 ++++++++++++++++++++++++++++++
 challenge-082/abigail/perl/ch-1.pl   | 76 ++++++++++++++++++++++++++++++++++++
 11 files changed, 165 insertions(+)
 create mode 100644 challenge-082/abigail/input-1-1
 create mode 100644 challenge-082/abigail/input-1-2
 create mode 100644 challenge-082/abigail/input-1-3
 create mode 100644 challenge-082/abigail/input-1-4
 create mode 100644 challenge-082/abigail/input-1-5
 create mode 100644 challenge-082/abigail/output-1-1.exp
 create mode 100644 challenge-082/abigail/output-1-2.exp
 create mode 100644 challenge-082/abigail/output-1-3.exp
 create mode 100644 challenge-082/abigail/output-1-4.exp
 create mode 100644 challenge-082/abigail/output-1-5.exp
 create mode 100644 challenge-082/abigail/perl/ch-1.pl

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/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/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__
-- 
cgit 


From 753d64f20e66f7dcba008dac11b2d6f05d4bfb38 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Wed, 14 Oct 2020 00:15:12 +0200
Subject: Perl solution for week 82/part 2

---
 challenge-082/abigail/input-2-1      |  3 ++
 challenge-082/abigail/input-2-2      |  3 ++
 challenge-082/abigail/input-2-3      |  3 ++
 challenge-082/abigail/input-2-4      |  3 ++
 challenge-082/abigail/output-2-1.exp |  2 ++
 challenge-082/abigail/output-2-2.exp |  2 ++
 challenge-082/abigail/output-2-3.exp |  2 ++
 challenge-082/abigail/output-2-4.exp |  2 ++
 challenge-082/abigail/perl/ch-2.pl   | 63 ++++++++++++++++++++++++++++++++++++
 9 files changed, 83 insertions(+)
 create mode 100644 challenge-082/abigail/input-2-1
 create mode 100644 challenge-082/abigail/input-2-2
 create mode 100644 challenge-082/abigail/input-2-3
 create mode 100644 challenge-082/abigail/input-2-4
 create mode 100644 challenge-082/abigail/output-2-1.exp
 create mode 100644 challenge-082/abigail/output-2-2.exp
 create mode 100644 challenge-082/abigail/output-2-3.exp
 create mode 100644 challenge-082/abigail/output-2-4.exp
 create mode 100644 challenge-082/abigail/perl/ch-2.pl

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-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-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__
-- 
cgit 


From dcbd9bc6855cb3e0e7eff458518a793408e0cfa1 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Wed, 14 Oct 2020 00:17:06 +0200
Subject: Whitespace

---
 challenge-082/abigail/test.pl | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/challenge-082/abigail/test.pl b/challenge-082/abigail/test.pl
index 349ee00c1e..aa84e275d5 100755
--- a/challenge-082/abigail/test.pl
+++ b/challenge-082/abigail/test.pl
@@ -50,7 +50,7 @@ foreach my $challenge (1, 2) {
             my $exe      =   $$info {exe};
             my $ext      =   $$info {ext};
             my $dir      =   $$info {dir}    // lc $language;
-            my @args     = @{$$info {args} // []};
+            my @args     = @{$$info {args}   // []};
             my $filter   =   $$info {filter} // '';
             my $solution =  "$dir/ch-$challenge.$ext";
             next unless -r $solution;
-- 
cgit