Perl solution for week 082/part 1

11 files changed, 165 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/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__