diff options
39 files changed, 15978 insertions, 2016 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/blog.txt b/challenge-136/abigail/blog.txt new file mode 100644 index 0000000000..448683a85d --- /dev/null +++ b/challenge-136/abigail/blog.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-136-1.html diff --git a/challenge-136/abigail/blog1.txt b/challenge-136/abigail/blog1.txt new file mode 100644 index 0000000000..91c59e8448 --- /dev/null +++ b/challenge-136/abigail/blog1.txt @@ -0,0 +1 @@ +https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-136-2.html 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/pascal/ch-2.p b/challenge-136/abigail/pascal/ch-2.p index 6515b4e5ca..30d4539a6a 100644 --- a/challenge-136/abigail/pascal/ch-2.p +++ b/challenge-136/abigail/pascal/ch-2.p @@ -8,12 +8,17 @@ Program XXX; (* Run as: fpc -och-2.out ch-2.p; ./ch-2.out < input-file *) (* *) -function count (target, this_fib, prev_fib: integer): integer; +function _count (target, this_fib, prev_fib: integer): integer; begin - if target < this_fib then count := 0 - else if target = this_fib then count := 1 - else count := count (target - this_fib, this_fib + prev_fib, this_fib) + - count (target, this_fib + prev_fib, this_fib); + if target < this_fib then _count := 0 + else if target = this_fib then _count := 1 + else _count := _count (target - this_fib, this_fib + prev_fib, this_fib) + + _count (target, this_fib + prev_fib, this_fib) + end; + +function count (target: integer): integer; + begin + count := _count (target, 1, 1); end; var @@ -22,6 +27,6 @@ var begin while (not eof) do begin readln (n); - writeln (count (n, 1, 1)); + writeln (count (n)); end end. 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/t/ctest.ini b/challenge-136/abigail/t/ctest.ini index faa58e9882..60c99e97bc 100644 --- a/challenge-136/abigail/t/ctest.ini +++ b/challenge-136/abigail/t/ctest.ini @@ -6,6 +6,10 @@ [names]
1-1 = Given Examples
2-1 = Given Examples
+2-2 = OEIS list up to 6765
[languages/bc]
add_to_input = 0
+
+[2-2/bc,r,scheme]
+skip = No cache for this language
diff --git a/challenge-136/abigail/t/input-2-2 b/challenge-136/abigail/t/input-2-2 new file mode 100644 index 0000000000..e68294114c --- /dev/null +++ b/challenge-136/abigail/t/input-2-2 @@ -0,0 +1,6765 @@ +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15 +16 +17 +18 +19 +20 +21 +22 +23 +24 +25 +26 +27 +28 +29 +30 +31 +32 +33 +34 +35 +36 +37 +38 +39 +40 +41 +42 +43 +44 +45 +46 +47 +48 +49 +50 +51 +52 +53 +54 +55 +56 +57 +58 +59 +60 +61 +62 +63 +64 +65 +66 +67 +68 +69 +70 +71 +72 +73 +74 +75 +76 +77 +78 +79 +80 +81 +82 +83 +84 +85 +86 +87 +88 +89 +90 +91 +92 +93 +94 +95 +96 +97 +98 +99 +100 +101 +102 +103 +104 +105 +106 +107 +108 +109 +110 +111 +112 +113 +114 +115 +116 +117 +118 +119 +120 +121 +122 +123 +124 +125 +126 +127 +128 +129 +130 +131 +132 +133 +134 +135 +136 +137 +138 +139 +140 +141 +142 +143 +144 +145 +146 +147 +148 +149 +150 +151 +152 +153 +154 +155 +156 +157 +158 +159 +160 +161 +162 +163 +164 +165 +166 +167 +168 +169 +170 +171 +172 +173 +174 +175 +176 +177 +178 +179 +180 +181 +182 +183 +184 +185 +186 +187 +188 +189 +190 +191 +192 +193 +194 +195 +196 +197 +198 +199 +200 +201 +202 +203 +204 +205 +206 +207 +208 +209 +210 +211 +212 +213 +214 +215 +216 +217 +218 +219 +220 +221 +222 +223 +224 +225 +226 +227 +228 +229 +230 +231 +232 +233 +234 +235 +236 +237 +238 +239 +240 +241 +242 +243 +244 +245 +246 +247 +248 +249 +250 +251 +252 +253 +254 +255 +256 +257 +258 +259 +260 +261 +262 +263 +264 +265 +266 +267 +268 +269 +270 +271 +272 +273 +274 +275 +276 +277 +278 +279 +280 +281 +282 +283 +284 +285 +286 +287 +288 +289 +290 +291 +292 +293 +294 +295 +296 +297 +298 +299 +300 +301 +302 +303 +304 +305 +306 +307 +308 +309 +310 +311 +312 +313 +314 +315 +316 +317 +318 +319 +320 +321 +322 +323 +324 +325 +326 +327 +328 +329 +330 +331 +332 +333 +334 +335 +336 +337 +338 +339 +340 +341 +342 +343 +344 +345 +346 +347 +348 +349 +350 +351 +352 +353 +354 +355 +356 +357 +358 +359 +360 +361 +362 +363 +364 +365 +366 +367 +368 +369 +370 +371 +372 +373 +374 +375 +376 +377 +378 +379 +380 +381 +382 +383 +384 +385 +386 +387 +388 +389 +390 +391 +392 +393 +394 +395 +396 +397 +398 +399 +400 +401 +402 +403 +404 +405 +406 +407 +408 +409 +410 +411 +412 +413 +414 +415 +416 +417 +418 +419 +420 +421 +422 +423 +424 +425 +426 +427 +428 +429 +430 +431 +432 +433 +434 +435 +436 +437 +438 +439 +440 +441 +442 +443 +444 +445 +446 +447 +448 +449 +450 +451 +452 +453 +454 +455 +456 +457 +458 +459 +460 +461 +462 +463 +464 +465 +466 +467 +468 +469 +470 +471 +472 +473 +474 +475 +476 +477 +478 +479 +480 +481 +482 +483 +484 +485 +486 +487 +488 +489 +490 +491 +492 +493 +494 +495 +496 +497 +498 +499 +500 +501 +502 +503 +504 +505 +506 +507 +508 +509 +510 +511 +512 +513 +514 +515 +516 +517 +518 +519 +520 +521 +522 +523 +524 +525 +526 +527 +528 +529 +530 +531 +532 +533 +534 +535 +536 +537 +538 +539 +540 +541 +542 +543 +544 +545 +546 +547 +548 +549 +550 +551 +552 +553 +554 +555 +556 +557 +558 +559 +560 +561 +562 +563 +564 +565 +566 +567 +568 +569 +570 +571 +572 +573 +574 +575 +576 +577 +578 +579 +580 +581 +582 +583 +584 +585 +586 +587 +588 +589 +590 +591 +592 +593 +594 +595 +596 +597 +598 +599 +600 +601 +602 +603 +604 +605 +606 +607 +608 +609 +610 +611 +612 +613 +614 +615 +616 +617 +618 +619 +620 +621 +622 +623 +624 +625 +626 +627 +628 +629 +630 +631 +632 +633 +634 +635 +636 +637 +638 +639 +640 +641 +642 +643 +644 +645 +646 +647 +648 +649 +650 +651 +652 +653 +654 +655 +656 +657 +658 +659 +660 +661 +662 +663 +664 +665 +666 +667 +668 +669 +670 +671 +672 +673 +674 +675 +676 +677 +678 +679 +680 +681 +682 +683 +684 +685 +686 +687 +688 +689 +690 +691 +692 +693 +694 +695 +696 +697 +698 +699 +700 +701 +702 +703 +704 +705 +706 +707 +708 +709 +710 +711 +712 +713 +714 +715 +716 +717 +718 +719 +720 +721 +722 +723 +724 +725 +726 +727 +728 +729 +730 +731 +732 +733 +734 +735 +736 +737 +738 +739 +740 +741 +742 +743 +744 +745 +746 +747 +748 +749 +750 +751 +752 +753 +754 +755 +756 +757 +758 +759 +760 +761 +762 +763 +764 +765 +766 +767 +768 + |