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
|
#!/usr/bin/perl -s
use v5.16;
use Math::Prime::Util qw(todigits lucasu);
use List::MoreUtils 'reduce_0';
use Memoize qw(memoize flush_cache);
use Benchmark 'cmpthese';
use Test2::V0;
use experimental 'signatures';
our ($tests, $examples, $benchmark);
memoize('count_fib_seq');
run_tests() if $tests || $examples || $benchmark; # does not return
die <<EOS unless @ARGV;
usage: $0 [-examples] [-tests] [-benchmark] [N]
-examples
run the examples from the challenge
-tests
run some tests
-benchmark
compare a recursive counting implementation with a brute force scan.
N
Count Fibonacci subsequences that give a sum of N.
EOS
### Input and Output
say count_fib_seq($ARGV[0]);
### Implementation
# Try Fibonacci numbers F(k) starting with the k-th element, utilizing
# F(k) == lucas_u(1, -1, k):
# - Return the count if if F(k) is larger than or equal to N.
# - Add to the count the number of Fibonacci sequences that give a sum
# of N - F(k), starting with F(k + 1) by recursion.
# Note: The XS implementation of "lucasu" is much faster than its
# memoizing counterpart.
sub count_fib_seq ($n, $k = 2) {
my $count = 0;
while () {
my $fib = lucasu 1, -1, $k;
return $count + ($fib == $n) if $fib >= $n;
$count += count_fib_seq($n - $fib, ++$k);
}
}
# An alternative brute force approach:
# Try all Fibonacci subsequences for a matching sum. Taking the binary
# digits of the iterator variable as selectors for corresponding
# Fibonacci numbers.
# This was intended as a cross check for the counting implementation.
sub scan_fib_seq ($n) {
my (@fib, $f) = (1, 1);
push @fib, $f while ($f = $fib[-2] + $fib[-1]) <= $n;
shift @fib;
scalar grep {
$n == reduce_0 {$a += $fib[$_] * $b} todigits($_, 2, @fib)
} 1 .. 2 ** @fib - 1;
}
### Examples and tests
sub run_tests {
SKIP: {
skip "examples" unless $examples;
is count_fib_seq(16), 4, 'example 1';
is count_fib_seq(9), 2, 'example 2';
is count_fib_seq(15), 2, 'example 3';
}
SKIP: {
skip "tests" unless $tests;
grep {
count_fib_seq($_) != scan_fib_seq($_) and !fail "$_ failed";
} 0 .. 100 or pass 'cross check';
}
SKIP: {
skip "benchmark" unless $benchmark;
cmpthese(0, {
scan => sub {scan_fib_seq(1000)},
count => sub {
flush_cache('count_fib_seq');
count_fib_seq(1000);
}
});
}
done_testing;
exit;
}
|
