Week 151: No recursion for part 2

2 files changed, 40 insertions, 24 deletions

diff --git a/challenge-151/abigail/awk/ch-2.awk b/challenge-151/abigail/awk/ch-2.awk
index 3eb76a8e05..73d9b19812 100644
--- a/challenge-151/abigail/awk/ch-2.awk
+++ b/challenge-151/abigail/awk/ch-2.awk
@@ -8,21 +8,19 @@
 # Run as: awk -f ch-2.awk < input-file
 #
 
-function best (i, max, sum, k) {
-    if (!(i in cache)) {
-        max = 0
-        for (k = i + 2; k <= NF; k ++) {
-            sum = best(k)
-            if (sum > max) {
-                max = sum
-            }
-        }
-        cache [i] = $i + max
-    }
-    return cache [i]
+function max (a, b) {
+    return a < b ? b : a
 }
 
 {
-    delete cache
-    print best(1)
+    delete best
+    for (i = NF; i > 0; i --) {
+        best [i] = NF <= 2     ? $i                                     \
+                 : i == NF     ? $i                                     \
+                 : i == 1      ? $i     + best [i + 2]                  \
+                 : i == NF - 1 ? max($i,  best [i + 1])                 \
+                 :               max($i + best [i + 2], best [i + 1])
+    }
+    print best [1]
 }
+
diff --git a/challenge-151/abigail/perl/ch-2.pl b/challenge-151/abigail/perl/ch-2.pl
index 263bede352..5f5519381f 100644
--- a/challenge-151/abigail/perl/ch-2.pl
+++ b/challenge-151/abigail/perl/ch-2.pl
@@ -20,17 +20,35 @@ use experimental 'lexical_subs';
 use List::Util qw [max];
 
 #
-# An algorithm we've seen many times before. For each house, we either
-# rob it, or skip it. And we always have to skip the next house.
-# Skipping more than two houses in succession is never a good idea, but
-# work we'll do extra in the beginning (by skipping more than two house)
-# we get back later on, as we're caching all results.
+# We'll calculate the best way to rob the houses by working backwards.
+# For each house, there are two options: rob the house, or skip it.
+# The maximum value we get for robbing the house is the sum of
+# the value of the current house, plus the maximum we can get
+# if we started two houses down. The maximum value we can get by
+# not robbing this house is the best we can get by starting from
+# the next house.
 #
-sub best;
-sub best ($vals, $i = 0) {
-    state $cache;
-    $i or $cache = [];
-    $$cache [$i] ||= $$vals [$i] + max 0, map {best $vals, $_} $i + 2 .. $#$vals
+# We need some fiddling around the edges:
+#    - Maximizing the value starting from the last house is by robbing it.
+#    - Maximizing the value starting from the penultimate house is
+#      robbing the most valuable of the last two houses.
+#    - If there are only two houses, rob the current house.
+#    - The first house should always be robbed (a requirement); the
+#      maximum value which can be achieved we get by starting from the
+#      third house, adding the value of the first.
+#
+
+sub best ($houses) {
+    my @best;
+    foreach my $i (reverse keys @$houses) {
+        $best [$i] = @$houses < 2        ?     $$houses [$i]
+                   : $i == $#$houses     ?     $$houses [$i]
+                   : $i == 0             ?     $$houses [$i] + $best [$i + 2]
+                   : $i == $#$houses - 1 ? max $$houses [$i],  $best [$i + 1]
+                   :                       max $$houses [$i] + $best [$i + 2],
+                                                               $best [$i + 1];
+    }
+    $best [0];
 }