The first task of this week’s challenge is similar to the task from the previous week, but while I skipped last week, I can still re-use my partial code that I started last week 🙂
The task today is:
You are given a positive integer $N. Write a script to find out all possible combination of Fibonacci Numbers required to get $N on addition. You are NOT allowed to repeat a number. Print 0 if none found.
Let me immediately simplify the task. First of all, there are only two repeated numbers in the Fibonacci sequence itself: 1, 1, 2, 3, 5, …. So, we can start from the second number to remove the potential duplicate number. Second, it looks like you can represent any positive integer with a sum of Fibonacci numbers. I have the feeling because of the nature of the sequence, but you can also prove it. So, no need to check if you can find the solution.
Finally, here is my solution:
my $n = @*ARGS[0] // 42;
my @fib = 1, 2, * + * ...^ * > $n;
"$_.join(' + ') = $n".put for @fib.combinations.grep(*.sum == $n);
We take $n from command line and generate a sequence that does not exceed that number. Notice that unlike a proper Fibonacci sequence, I force it to start with the numbers 1 and 2.
Then, the numbers are mixed in all possible combinations and finally filtered so that their sum is correct.
And that’s it. Run the program with different arguments to see the results.
$ raku ch-1.raku 22 1 + 21 = 22 1 + 8 + 13 = 22 1 + 3 + 5 + 13 = 22
* * *
→ GitHub repository
→ Navigation to the Raku challenges post series