Implement caching for week 136/part 2.

For those language for which it was easy to make use of an associative
array/hash/mapping: AWK, Bash, Go, Java, Lua, Node.js, Perl, Python,
Ruby and Tcl.

Implementations left without caching: bc, C, Pascal, R, and Scheme.

10 files changed, 129 insertions, 52 deletions

diff --git a/challenge-136/abigail/awk/ch-2.awk b/challenge-136/abigail/awk/ch-2.awk
index 2df5623041..48fc14d332 100644
--- a/challenge-136/abigail/awk/ch-2.awk
+++ b/challenge-136/abigail/awk/ch-2.awk
@@ -8,13 +8,18 @@
 # Run as: awk -f ch-2.awk < input-file
 #
 
-function count (target, this_fib, prev_fib) {
+
+function count (target, this_fib, prev_fib, key) {
     if (!this_fib) {this_fib = 1}
     if (!prev_fib) {prev_fib = 1}
-    return target <  this_fib ? 0                                    \
-         : target == this_fib ? 1                                    \
-         : count(target - this_fib, this_fib + prev_fib, this_fib) + \
-           count(target,            this_fib + prev_fib, this_fib)
+    key = target ";" this_fib
+    if (!(key in cache)) {
+        cache [key] = target <  this_fib ? 0                                   \
+                    : target == this_fib ? 1                                   \
+                    : count(target - this_fib, this_fib + prev_fib, this_fib) +\
+                      count(target,            this_fib + prev_fib, this_fib)
+    }
+    return cache [key]
 }
 
 {
diff --git a/challenge-136/abigail/bash/ch-2.sh b/challenge-136/abigail/bash/ch-2.sh
index 1a291d7d18..e46d5920e8 100644
--- a/challenge-136/abigail/bash/ch-2.sh
+++ b/challenge-136/abigail/bash/ch-2.sh
@@ -10,20 +10,28 @@
 
 set -f
 
+declare -A cache
+
 function count () {
     local target=$1
     local this_fib=${2:-1}
     local prev_fib=${3:-1}
 
-    if   ((target <  this_fib))
-    then count=0
-    elif ((target == this_fib))
-    then count=1
-    else count $((target - this_fib)) $((this_fib + prev_fib)) $this_fib
-         local sum=$count
-         count $target                $((this_fib + prev_fib)) $this_fib
-         count=$((count + sum))
+    local key=$target";"$this_fib
+
+    if [ ! -v 'cache[$key]' ]
+    then if   ((target <  this_fib))
+         then cache[$key]=0
+         elif ((target == this_fib))
+         then cache[$key]=1
+         else count $((target - this_fib)) $((this_fib + prev_fib)) $this_fib
+              local sum=$count
+              count $target                $((this_fib + prev_fib)) $this_fib
+              cache[$key]=$((count + sum))
+         fi
     fi
+
+    count=${cache[$key]}
 }
 
 while read target
diff --git a/challenge-136/abigail/go/ch-2.go b/challenge-136/abigail/go/ch-2.go
index adff1db0df..684e65974b 100644
--- a/challenge-136/abigail/go/ch-2.go
+++ b/challenge-136/abigail/go/ch-2.go
@@ -12,11 +12,27 @@ import (
     "fmt"
 )
 
+var cache map [int] map [int] int
+
 func _count (target int, this_fib int, prev_fib int) int {
-    if target <  this_fib {return 0}
-    if target == this_fib {return 1}
-    return _count (target - this_fib, this_fib + prev_fib, this_fib) +
-           _count (target,            this_fib + prev_fib, this_fib)
+    if _, ok := cache [target]; !ok {
+        cache [target] = make (map [int] int)
+    }
+
+    if _, ok := cache [target] [this_fib]; !ok {
+        var result int
+               if target <  this_fib {
+            result = 0
+        } else if target == this_fib {
+            result = 1
+        } else {
+            result = _count (target - this_fib, this_fib + prev_fib, this_fib) +
+                     _count (target,            this_fib + prev_fib, this_fib)
+        }
+        cache [target] [this_fib] = result
+    }
+
+    return cache [target] [this_fib]
 }
 
 func count (target int) int {
@@ -24,6 +40,7 @@ func count (target int) int {
 }
 
 func main () {
+    cache = make (map [int] map [int] int)
     for {
         var n int
         c, err := fmt . Scanf ("%d", &n)
diff --git a/challenge-136/abigail/java/ch-2.java b/challenge-136/abigail/java/ch-2.java
index f08384cf95..9b7bb38935 100644
--- a/challenge-136/abigail/java/ch-2.java
+++ b/challenge-136/abigail/java/ch-2.java
@@ -7,13 +7,23 @@
 //
 
 import java.util.*;
+import java.util.Hashtable;
+import java.util.Map;
 
 public class ch2 {
+    static Map <String, Integer> cache = new Hashtable <String, Integer> ();
+
     public static int count (int target, int this_fib, int prev_fib) {
-        return target <  this_fib ? 0
-             : target == this_fib ? 1
-             : count (target - this_fib, this_fib + prev_fib, this_fib) +
-               count (target,            this_fib + prev_fib, this_fib);
+        String key = target + ";" + this_fib;
+        if (!cache . containsKey (key)) {
+            cache . put (key,
+                    target <  this_fib ? 0
+                  : target == this_fib ? 1
+                  : count (target - this_fib, this_fib + prev_fib, this_fib) +
+                    count (target,            this_fib + prev_fib, this_fib)
+            );
+        }
+        return cache . get (key);
     }
 
     public static int count (int target) {
diff --git a/challenge-136/abigail/lua/ch-2.lua b/challenge-136/abigail/lua/ch-2.lua
index 06d92984f4..e955e8cc81 100644
--- a/challenge-136/abigail/lua/ch-2.lua
+++ b/challenge-136/abigail/lua/ch-2.lua
@@ -8,11 +8,19 @@
 -- Run as: lua ch-2.lua < input-file
 --
 
+local cache = {}
+
 function _count (target, this_fib, prev_fib)
-    if target <  this_fib then return 0 end
-    if target == this_fib then return 1 end
-    return (_count (target - this_fib, this_fib + prev_fib, this_fib) +
-            _count (target,            this_fib + prev_fib, this_fib))
+    local key = target .. ";" .. this_fib
+    if cache [key] == nil then
+            if target <  this_fib then cache [key] = 0
+        elseif target == this_fib then cache [key] = 1
+        else                           cache [key] =
+              _count (target - this_fib, this_fib + prev_fib, this_fib) +
+              _count (target,            this_fib + prev_fib, this_fib)
+        end
+    end
+    return cache [key]
 end
 
 function count (target)
diff --git a/challenge-136/abigail/node/ch-2.js b/challenge-136/abigail/node/ch-2.js
index eaf2a426a0..f74073f555 100644
--- a/challenge-136/abigail/node/ch-2.js
+++ b/challenge-136/abigail/node/ch-2.js
@@ -8,13 +8,19 @@
 // Run as: node ch-2.js < input-file
 //
 
+let cache = {}
+
 function count (target, this_fib, prev_fib) {
     if (!this_fib) {this_fib = 1}
     if (!prev_fib) {prev_fib = 1}
-    return target <  this_fib ? 0
-         : target == this_fib ? 1
-         : count (target - this_fib, this_fib + prev_fib, this_fib) +
-           count (target,            this_fib + prev_fib, this_fib)
+    let key = target + ";" + this_fib
+    if (!(key in cache)) {
+        cache [key] = target <  this_fib ? 0
+                    : target == this_fib ? 1
+                    : count (target - this_fib, this_fib + prev_fib, this_fib) +
+                      count (target,            this_fib + prev_fib, this_fib)
+    }
+    return cache [key]
 }
 
 
diff --git a/challenge-136/abigail/perl/ch-2.pl b/challenge-136/abigail/perl/ch-2.pl
index d9a5e5ae13..61511a38cc 100644
--- a/challenge-136/abigail/perl/ch-2.pl
+++ b/challenge-136/abigail/perl/ch-2.pl
@@ -33,13 +33,17 @@ use experimental 'lexical_subs';
 # we count the number of ways making $target with Fibonnaci numbers larger
 # than $this_fib. We return the sum of these counts.
 #
+# We also cache the results, to reduce the number of recursive calls.
+#
 
 sub count;
 sub count ($target, $this_fib = 1, $prev_fib = 1) {
-      $this_fib >  $target ? 0
-    : $this_fib == $target ? 1
-    : count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) +
-      count ($target,             $this_fib + $prev_fib, $this_fib)
+      state $cache = {};
+      $$cache {$target, $this_fib} //=
+          $this_fib >  $target ? 0
+        : $this_fib == $target ? 1
+        : count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) +
+          count ($target,             $this_fib + $prev_fib, $this_fib)
 }
 
 
diff --git a/challenge-136/abigail/python/ch-2.py b/challenge-136/abigail/python/ch-2.py
index 88960021ef..d114bfdfba 100644
--- a/challenge-136/abigail/python/ch-2.py
+++ b/challenge-136/abigail/python/ch-2.py
@@ -8,13 +8,21 @@
 # Run as: python ch-2.py < input-file
 #
 
+cache = {}
+
 def _count (target, this_fib, prev_fib):
-    if target <  this_fib:
-        return (0)
-    if target == this_fib:
-        return (1)
-    return (_count (target - this_fib, this_fib + prev_fib, this_fib) +
-            _count (target,            this_fib + prev_fib, this_fib))
+    key = str (target) + ";" + str (this_fib)
+    if not (key in cache):
+        if target <  this_fib:
+            cache [key] = 0
+        elif target == this_fib:
+            cache [key] = 1
+        else:
+            cache [key] = \
+                _count (target - this_fib, this_fib + prev_fib, this_fib) + \
+                _count (target,            this_fib + prev_fib, this_fib)
+
+    return cache [key]
 
 def count (target):
     return (_count (target, 1, 1))
diff --git a/challenge-136/abigail/ruby/ch-2.rb b/challenge-136/abigail/ruby/ch-2.rb
index 24e129a00d..630b4e3dd0 100644
--- a/challenge-136/abigail/ruby/ch-2.rb
+++ b/challenge-136/abigail/ruby/ch-2.rb
@@ -8,11 +8,15 @@
 # Run as: ruby ch-2.rb < input-file
 #
 
+$cache = {}
+
 def _count (target, this_fib, prev_fib)
-    return target <  this_fib ? 0
-         : target == this_fib ? 1
-         : _count(target - this_fib, this_fib + prev_fib, this_fib) +
-           _count(target,            this_fib + prev_fib, this_fib)
+    key = target . to_s + ";" + this_fib . to_s
+    $cache [key] ||= target <  this_fib ? 0
+                   : target == this_fib ? 1
+                   : _count(target - this_fib, this_fib + prev_fib, this_fib) +
+                     _count(target,            this_fib + prev_fib, this_fib)
+    return $cache [key]
 end
 
 def count (target)
diff --git a/challenge-136/abigail/tcl/ch-2.tcl b/challenge-136/abigail/tcl/ch-2.tcl
index 6062392bce..d74df5d583 100644
--- a/challenge-136/abigail/tcl/ch-2.tcl
+++ b/challenge-136/abigail/tcl/ch-2.tcl
@@ -6,17 +6,24 @@
 # Run as: tclsh ch-2.tcl < input-file
 #
 
+set cache [dict create]
+
 proc _count {target this_fib prev_fib} {
-    if {$target <  $this_fib} {
-        return 0
-    }
-    if {$target == $this_fib} {
-        return 1
+    global cache
+    if {![dict exists $cache $target $this_fib]} {
+        if {$target <  $this_fib} {
+            set result 0
+        } elseif {$target == $this_fib} {
+            set result 1
+        } else {
+            set result [expr [_count [expr $target   - $this_fib]              \
+                                     [expr $this_fib + $prev_fib] $this_fib] + \
+                             [_count       $target                             \
+                                     [expr $this_fib + $prev_fib] $this_fib]]
+        }
+        dict set cache $target $this_fib $result
     }
-    return [expr [_count [expr $target - $this_fib]                  \
-                         [expr $this_fib + $prev_fib] $this_fib] +   \
-                 [_count       $target                               \
-                         [expr $this_fib + $prev_fib] $this_fib]]
+    return [dict get $cache $target $this_fib]
 }
 
 proc count {target} {