Improve performance.

Our initial implementation of part 2 of week 82 has an exponential
worst case time complexity. By introducing caching and using pointers
instead of copying strings, we now have a quadratic worst case
time complexity (and a quadratic space requirement).

1 files changed, 47 insertions, 32 deletions

diff --git a/challenge-082/abigail/perl/ch-2.pl b/challenge-082/abigail/perl/ch-2.pl
index 8a176e1e79..821b05b26e 100644
--- a/challenge-082/abigail/perl/ch-2.pl
+++ b/challenge-082/abigail/perl/ch-2.pl
@@ -23,41 +23,56 @@ chomp (my $A = <>);
 chomp (my $B = <>);
 chomp (my $C = <>);
 
+#
+# $A, $B, $C are arrays, containing the single characters of
+# the input strings. $ai, $bi, $ci are indices into the arrays
+# (and can be seen as pointers into the strings). 
+#
+# Invariants:  - $ai + $bi == $ci
+#              - @$C [0 .. $ci - 1] is an interleaving of
+#                @$A [0 .. $ai - 1] and @$B [0 .. $bi - 1]
+#
 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);
+sub is_interleaved ($A, $B, $C, $ai = 0, $bi = 0, $ci = 0) {
+    state $cache;
+    local $" = "";
+    $$cache [$ai] [$bi] //= do {
+        #
+        # If we have reached the end of either $A or $B,
+        # what is remaining in the other string, must
+        # match the unmatched part in $C.
+        # 
+        return "@$A[$ai..$#$A]" eq "@$C[$ci..$#$C]" if $bi == @$B;
+        return "@$B[$bi..$#$B]" eq "@$C[$ci..$#$C]" if $ai == @$A;
+
+        #
+        # Now we can recurse; if the first character of unmatched
+        # part of C matches the first character of the unmatched 
+        # part of either A or B, we match the first character of C
+        # and the first character of either A or B, and recurse.
+        # If the first character of the unmatched part of C matches
+        # the first character of unmatched parts of both A and B,
+        # we first recurse first by matching against A, and if this
+        # doesn't provide a match, we recurse by matching against B.
+        #
+
+        return $$A [$ai] eq $$C [$ci] &&
+                     is_interleaved ($A, $B, $C, $ai + 1, $bi,     $ci + 1) ||
+               $$B [$bi] eq $$C [$ci] &&
+                     is_interleaved ($A, $B, $C, $ai,     $bi + 1, $ci + 1);
+    }
 }
 
-say is_interleaved ($A, $B, $C) ? 1 : 0;
+#
+# Check lengths; if the length of C isn't equal to the length of A
+# plus the length of B, we cannot have a match. If the lengths check
+# out, recursively check whether the strings are interleafed.
+#
+
+say length ($A) + length ($B) == length ($C) &&
+    is_interleaved ([split // => $A],
+                    [split // => $B],
+                    [split // => $C]) ? 1 : 0;
 
 
 __END__