From d8c7f4a22934aef0f6359788cebacada3afe70ea Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Mon, 15 Jul 2019 22:19:10 -0400
Subject: Notes for w15

---
 challenge-015/michael-hamlin/README | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/challenge-015/michael-hamlin/README b/challenge-015/michael-hamlin/README
index 4314e219f4..c5737036e7 100644
--- a/challenge-015/michael-hamlin/README
+++ b/challenge-015/michael-hamlin/README
@@ -1 +1,7 @@
 Solutions by Michael Hamlin.
+
+
+Notes:
+
+* the Vigenere encoder/decoder supports multiple keys
+* don't forget that modular operator `%` does not do what you want with negative integers!
-- 
cgit 


From 03ac841beabdc070b314c7b0e6765cd82bfae8c2 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Tue, 16 Jul 2019 22:36:20 -0400
Subject: simple approach to ackermann

---
 challenge-017/michael-hamlin/perl5/ch-1.pl         |  1 +
 .../michael-hamlin/perl5/t1-ackermann-simple.pl    | 35 ++++++++++++++++++++++
 2 files changed, 36 insertions(+)
 create mode 120000 challenge-017/michael-hamlin/perl5/ch-1.pl
 create mode 100644 challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl

diff --git a/challenge-017/michael-hamlin/perl5/ch-1.pl b/challenge-017/michael-hamlin/perl5/ch-1.pl
new file mode 120000
index 0000000000..157cbc0453
--- /dev/null
+++ b/challenge-017/michael-hamlin/perl5/ch-1.pl
@@ -0,0 +1 @@
+t1-ackermann-simple.pl
\ No newline at end of file
diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl
new file mode 100644
index 0000000000..02e03a644f
--- /dev/null
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl
@@ -0,0 +1,35 @@
+#! /usr/bin/env perl
+#
+
+use 5.22.0;
+use warnings;
+use feature 'signatures';
+no warnings 'experimental::signatures';
+use integer;
+
+# really need the big integers when $m >= 4
+# use bigint lib => 'GMP';
+
+no warnings 'recursion';
+
+my $count = 0;
+
+sub _ack( $m, $n ) {
+    $count++;
+    if ($m > 0) {
+        return _ack( $m - 1, 1 ) unless $n;
+        return _ack( $m - 1, _ack( $m, $n - 1));
+    } else {
+        return $n + 1;
+    }
+}
+sub ack ( $m, $n ) {
+    die "the function is not defined for negative parameters" if $m < 0 || $n < 0;
+    return _ack($m, $n);
+}
+
+die "must give two nonnegative integers as input" unless @ARGV > 1;
+
+$" = ', ';
+say "A( @ARGV ) = ", ack(@ARGV), "  ...after $count calls.";
+
-- 
cgit 


From 45c08f99aa00713944a4c145a37d289897b0b537 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Tue, 16 Jul 2019 22:45:38 -0400
Subject: remember previous evaluations

which avoids a lot of calls.  previously:

A( 3, 10 ) = 8189  ...after 44698325 calls.

becomes:

A( 3, 10 ) = 8189  ...after 24584 calls.
---
 challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl
index 02e03a644f..406fe6073e 100644
--- a/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-simple.pl
@@ -15,13 +15,13 @@ no warnings 'recursion';
 my $count = 0;
 
 sub _ack( $m, $n ) {
+    state @known;
     $count++;
-    if ($m > 0) {
-        return _ack( $m - 1, 1 ) unless $n;
-        return _ack( $m - 1, _ack( $m, $n - 1));
-    } else {
-        return $n + 1;
-    }
+    return $known[$m][$n] ||= do {
+        !$m ? $n + 1 :
+        !$n ? _ack($m - 1, 1) :
+        _ack($m - 1, _ack($m, $n - 1));
+    };
 }
 sub ack ( $m, $n ) {
     die "the function is not defined for negative parameters" if $m < 0 || $n < 0;
-- 
cgit 


From 8d9de0e82ebe13b4a1a89cb59a7da4730ad06651 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Thu, 18 Jul 2019 09:02:38 -0400
Subject: improved solution using hyper operator

---
 challenge-017/michael-hamlin/perl5/ch-1.pl         |  2 +-
 .../michael-hamlin/perl5/t1-ackermann-two.pl       | 87 ++++++++++++++++++++++
 2 files changed, 88 insertions(+), 1 deletion(-)
 create mode 100644 challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl

diff --git a/challenge-017/michael-hamlin/perl5/ch-1.pl b/challenge-017/michael-hamlin/perl5/ch-1.pl
index 157cbc0453..bc89ccf6fc 120000
--- a/challenge-017/michael-hamlin/perl5/ch-1.pl
+++ b/challenge-017/michael-hamlin/perl5/ch-1.pl
@@ -1 +1 @@
-t1-ackermann-simple.pl
\ No newline at end of file
+t1-ackermann-two.pl
\ No newline at end of file
diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
new file mode 100644
index 0000000000..8fc4ca80a0
--- /dev/null
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
@@ -0,0 +1,87 @@
+#! /usr/bin/env perl
+#
+
+use 5.22.0;
+use warnings;
+use feature 'signatures';
+no warnings 'experimental::signatures';
+
+# really need the big integers when $m >= 4
+# unfortunately the function grows so quickly even this doesnt help a lot
+use bigint lib => 'GMP';
+
+my $trace = 0;
+
+# compute 2 ^($n) $b, where ^($n) is the knuth up-arrow notation
+# $n is the number of knuth up-arrows, a degree of "hyperness"
+# $b is the repetition argument (how many 2's are iterated)
+sub _twoknuth( $n, $b ) {
+    my $result = 2;
+    if ($n == 1) {
+        # exponentiation is iterated multiplication
+        $result **= $b;
+    } elsif ($b == 0) {
+        $result = 1;
+    } elsif ($b == 1) {
+        # result is just 2
+    } elsif ($n == 2) {
+        # tetration is iterated exponentiation
+        for (2 .. $b) { $result = 2 ** $result }
+    } else {
+        # iterated hyper...
+        $result = _twoknuth( $n - 1, 2 );
+        if ($b > 2) {
+            for (3 .. $b) { $result = _twoknuth( $n - 1, $result ) }
+        }
+    }
+    say "2knuth( $n, $b ) = ", $result if $trace;
+    return $result;
+}
+# the hyper function, H_$n($a, $b), with $a = 2:
+sub _twohyper( $n, $b ) {
+    my $result = 2;
+    if ($n == 0) {
+        $result = $b + 1;
+    } elsif ($b == 0) {
+        # shortcut this?  but never happens in our problem
+        $result = $n == 1 ? 2 :
+            $n == 2 ? 0 : 1;
+    } elsif ($n == 1) {
+        $result += $b;
+    } elsif ($n == 2) {
+        $result *= $b;
+    } elsif ($b == 0) {
+        $result = 1;
+    } elsif ($b == 1) {
+        # result is just 2
+    } elsif ($n == 3) {
+        # exponentiation is iterated multiplication
+        $result **= $b;
+    } elsif ($n == 4) {
+        # tetration is iterated exponentiation
+        for (2 .. $b) { $result = 2 ** $result }
+    } else {
+        # $n > 4 means iterated hyper...
+        $result = _twohyper( $n - 1, 2 );
+        if ($b > 2) {
+            for (3 .. $b) { $result = _twohyper( $n - 1, $result ) }
+        }
+    }
+    say "2hyper( $n, $b ) = ", $result if $trace;
+    return $result;
+}
+sub ack2 ( $m, $n ) {
+    die "the function is not defined for negative parameters" if $m < 0 || $n < 0;
+    warn "this may run out of memory..." if $m > 4 || $m == 4 && $n >= 3;
+    return _twohyper($m, $n + 3) - 3;
+}
+
+die "must give two nonnegative integers as input" unless @ARGV > 1;
+
+$" = ', ';
+my $result = ack2(@ARGV);
+my $desc = $result->length < 78 ? $result :
+    sprintf 'int with %u digits', length($result);
+say "A( @ARGV ) = ", $desc;
+
+
-- 
cgit 


From 7f1a486a41d2de4343b423091644d163f5a4a218 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Thu, 18 Jul 2019 09:20:58 -0400
Subject: use bitshift instead of exponentation

---
 challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
index 8fc4ca80a0..0424ac782b 100644
--- a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
@@ -56,10 +56,10 @@ sub _twohyper( $n, $b ) {
         # result is just 2
     } elsif ($n == 3) {
         # exponentiation is iterated multiplication
-        $result **= $b;
+        $result = 1 << $b;  # 2 ** $b
     } elsif ($n == 4) {
         # tetration is iterated exponentiation
-        for (2 .. $b) { $result = 2 ** $result }
+        for (2 .. $b) { $result = 1 << $result }    # 2 ** $result
     } else {
         # $n > 4 means iterated hyper...
         $result = _twohyper( $n - 1, 2 );
-- 
cgit 


From d10c5f0195d2ab291371711784373421081f268b Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Thu, 18 Jul 2019 09:08:46 -0400
Subject: eliminate twoknuth

---
 .../michael-hamlin/perl5/t1-ackermann-two.pl       | 25 ----------------------
 1 file changed, 25 deletions(-)

diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
index 0424ac782b..a93cb0e43b 100644
--- a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
@@ -12,31 +12,6 @@ use bigint lib => 'GMP';
 
 my $trace = 0;
 
-# compute 2 ^($n) $b, where ^($n) is the knuth up-arrow notation
-# $n is the number of knuth up-arrows, a degree of "hyperness"
-# $b is the repetition argument (how many 2's are iterated)
-sub _twoknuth( $n, $b ) {
-    my $result = 2;
-    if ($n == 1) {
-        # exponentiation is iterated multiplication
-        $result **= $b;
-    } elsif ($b == 0) {
-        $result = 1;
-    } elsif ($b == 1) {
-        # result is just 2
-    } elsif ($n == 2) {
-        # tetration is iterated exponentiation
-        for (2 .. $b) { $result = 2 ** $result }
-    } else {
-        # iterated hyper...
-        $result = _twoknuth( $n - 1, 2 );
-        if ($b > 2) {
-            for (3 .. $b) { $result = _twoknuth( $n - 1, $result ) }
-        }
-    }
-    say "2knuth( $n, $b ) = ", $result if $trace;
-    return $result;
-}
 # the hyper function, H_$n($a, $b), with $a = 2:
 sub _twohyper( $n, $b ) {
     my $result = 2;
-- 
cgit 


From ac7e397b968aa71ff5380565e0c973f2e9d0c5a2 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Thu, 18 Jul 2019 10:21:03 -0400
Subject: add test function

---
 .../michael-hamlin/perl5/t1-ackermann-two.pl       | 24 +++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)

diff --git a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
index a93cb0e43b..bdb6ce5e2a 100644
--- a/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
+++ b/challenge-017/michael-hamlin/perl5/t1-ackermann-two.pl
@@ -11,6 +11,10 @@ no warnings 'experimental::signatures';
 use bigint lib => 'GMP';
 
 my $trace = 0;
+my %limits = (
+    5 => 0,
+    4 => 2,
+);
 
 # the hyper function, H_$n($a, $b), with $a = 2:
 sub _twohyper( $n, $b ) {
@@ -47,10 +51,16 @@ sub _twohyper( $n, $b ) {
 }
 sub ack2 ( $m, $n ) {
     die "the function is not defined for negative parameters" if $m < 0 || $n < 0;
-    warn "this may run out of memory..." if $m > 4 || $m == 4 && $n >= 3;
+    if (defined my $nlimit = $limits{$m}) {
+        warn "this may run out of memory..." if $n > $nlimit;
+    }
     return _twohyper($m, $n + 3) - 3;
 }
 
+unless (@ARGV) {
+    _test();
+    exit(0);
+}
 die "must give two nonnegative integers as input" unless @ARGV > 1;
 
 $" = ', ';
@@ -60,3 +70,15 @@ my $desc = $result->length < 78 ? $result :
 say "A( @ARGV ) = ", $desc;
 
 
+sub _test {
+    for my $m (0 .. 5) {
+        my $nlimit = $limits{$m} // 5;
+        for my $n (0 .. $nlimit) {
+            my $result = ack2($m, $n);
+            my $desc = $result->length < 78 ? $result :
+                sprintf 'int with %u digits', length($result);
+            say "A( $m, $n ) = ", $desc;
+        }
+    }
+}
+
-- 
cgit 


From e2e7c76c65c5b341cf15926ca4f5600949250aa1 Mon Sep 17 00:00:00 2001
From: Michael Hamlin <1197072+myrrhlin@users.noreply.github.com>
Date: Thu, 18 Jul 2019 10:22:22 -0400
Subject: comment on ch-1.pl

---
 challenge-017/michael-hamlin/README | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/challenge-017/michael-hamlin/README b/challenge-017/michael-hamlin/README
index 4314e219f4..3c1a735306 100644
--- a/challenge-017/michael-hamlin/README
+++ b/challenge-017/michael-hamlin/README
@@ -1 +1,5 @@
 Solutions by Michael Hamlin.
+
+ch-1.pl  the Ackermann function grows so rapidly that I dont think I can
+test the real hyperness of my code, even with GMP.
+
-- 
cgit