From 0e0421f1df534125181a91bb6fe51093d90a7f94 Mon Sep 17 00:00:00 2001 From: Abigail Date: Wed, 27 Oct 2021 20:01:33 +0200 Subject: 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. --- challenge-136/abigail/lua/ch-2.lua | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'challenge-136/abigail/lua/ch-2.lua') 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) -- cgit