Merge branch 'master' into devel

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