Raku: 解 Fibonacci Sum

Fibonacci Sum 是個從 Perl Weekly Challenge 那裡看來的題目。輸入為整數 `\$N`，目標為找出所有總和為 `\$N` 之費波納契數集合，且集合內數字不重複。

``````my @fib = 1, 2, { \$^a + \$^b } ... *;
``````

``````my @subfib = @fib[0 ... @fib.first({ \$^fib > \$n }, :k)-1];
``````

``````sumsearch(\$n, @subfib);
``````

``````sub sumsearch (Int \$n, @nums) {
my @solutions = [];

if \$n == 0 {
@solutions.push([]);
return @solutions;
}

if @nums.elems == 0 || \$n < 0 {
return @solutions;
}

my \$firstNum = @nums.pop();
my @s1 = sumsearch(\$n, @nums);
my @s2 = sumsearch(\$n - \$firstNum, @nums).map({ \$_.prepend(\$firstNum) });
@nums.push(\$firstNum);

@solutions.append(@s1);
@solutions.append(@s2);

return @solutions;
}
``````

``````# raku fibsum.raku 8192
... subfib = 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
|fibsum(8192)| = 81

8192
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 8
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 8
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 2584 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 8
= 4181 + 2584 + 987 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 55 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 55 + 8
= 4181 + 2584 + 987 + 377 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 377 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 377 + 34 + 21 + 8
= 4181 + 2584 + 987 + 377 + 55 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 55 + 5 + 3
= 4181 + 2584 + 987 + 377 + 55 + 8
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 6765 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 6765 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 55 + 8
= 6765 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 8
= 6765 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 34 + 21 + 5 + 3
= 6765 + 987 + 233 + 144 + 34 + 21 + 8
= 6765 + 987 + 233 + 144 + 55 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 55 + 5 + 3
= 6765 + 987 + 233 + 144 + 55 + 8
= 6765 + 987 + 377 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 377 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 377 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 377 + 34 + 21 + 5 + 3
= 6765 + 987 + 377 + 34 + 21 + 8
= 6765 + 987 + 377 + 55 + 5 + 2 + 1
= 6765 + 987 + 377 + 55 + 5 + 3
= 6765 + 987 + 377 + 55 + 8
``````

``````# for n in {1..8192}; raku fibsum.raku \$n | grep fibsum | grep '= 1\$'
|fibsum(1)| = 1
|fibsum(2)| = 1
|fibsum(4)| = 1
|fibsum(7)| = 1
|fibsum(12)| = 1
|fibsum(20)| = 1
|fibsum(33)| = 1
|fibsum(54)| = 1
|fibsum(88)| = 1
|fibsum(143)| = 1
|fibsum(232)| = 1
|fibsum(376)| = 1
|fibsum(609)| = 1
|fibsum(986)| = 1
|fibsum(1596)| = 1
^C
``````