From 21af5125a68724d6a49a4a6522daed767749aab9 Mon Sep 17 00:00:00 2001 From: Abigail Date: Tue, 15 Sep 2020 18:34:06 +0200 Subject: JavaScript solutions for week 77, part 1. --- challenge-077/abigail/Part1/solution.js | 97 +++++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) create mode 100644 challenge-077/abigail/Part1/solution.js (limited to 'challenge-077/abigail/Part1/solution.js') diff --git a/challenge-077/abigail/Part1/solution.js b/challenge-077/abigail/Part1/solution.js new file mode 100644 index 0000000000..6a3d839342 --- /dev/null +++ b/challenge-077/abigail/Part1/solution.js @@ -0,0 +1,97 @@ +// +// Exercise: +// 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. +// + +// +// Note: +// The "Print 0 if none found." is irrelevant. There is always at +// least one way to write any positive integer as a sum of distinct +// Fibonacci Numbers. (Zeckendorf's theorem states: "very positive +// integer can be represented uniquely as the sum of one or more +// distinct Fibonacci numbers in such a way that the sum does not +// include any two consecutive Fibonacci numbers") +// + +// +// Read the input number from STDIN +// +let fs = require ("fs"); +let N = +fs . readFileSync (0) . toString () . trim (); + +// +// Generate a list of Fibonacci numbers, starting with (1, 2), +// up to the target number. Store this in FIB. +// +let FIB = [1, 2]; +while (FIB [FIB . length - 1] + FIB [FIB . length - 2] < N) { + FIB . push (FIB [FIB . length - 1] + FIB [FIB . length - 2]); +} + +// +// Recursive function to find the sums. First argument is the target +// number, second argument is the index of smallest number which can +// be used. +// +function solutions (target, index = 0) { + let output = []; + // + // Iterate over the list of Fibonacci numbers, looking for + // candidates. We're starting with the given index. + // + for (let i = index; i < FIB . length; i ++) { + let fib = FIB [i]; + if (fib > target) { + // + // If the candidate is larger than the target number, + // we can stop looking, as each subsequent number will + // be larger. + // + break; + } + if (fib == target) { + // + // If the candidate is equal to the target number, + // then it's a trivial solution (a sum of 1 number). + // Add it to the list of possibilities, and stop + // searching. + // + output . push ([fib]); + break; + } + else { + // + // Find solutions for the difference between the + // candidate and the target number, with the restriction + // that each number in that sum is larger than the numbers + // used so far. + // + let rec_solutions = solutions (target - fib, i + 1); + + // + // For each solution found in recursion, we have a solution + // for this call, by adding the candidate to it. + // + for (let j = 0; j < rec_solutions . length; j ++) { + output . push ([fib] . concat (rec_solutions [j])); + } + } + } + return output; +} + +// +// Find the solutions +// +let sols = solutions (N); + +// +// And print the results +// +for (let i = 0; i < sols . length; i ++) { + console . log (sols [i] . join (" + ") + " = " + N); +} -- cgit From d36cbe639e0dffeb2fd168576ea19570c9fb687d Mon Sep 17 00:00:00 2001 From: Abigail Date: Tue, 15 Sep 2020 19:50:36 +0200 Subject: Fix off-by-one error. We need all the Fibonacci numbers up to and including $N, else we will miss out on a solution if $N is a Fibonacci number. --- challenge-077/abigail/Part1/solution.js | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'challenge-077/abigail/Part1/solution.js') diff --git a/challenge-077/abigail/Part1/solution.js b/challenge-077/abigail/Part1/solution.js index 6a3d839342..f2d7173403 100644 --- a/challenge-077/abigail/Part1/solution.js +++ b/challenge-077/abigail/Part1/solution.js @@ -28,7 +28,7 @@ let N = +fs . readFileSync (0) . toString () . trim (); // up to the target number. Store this in FIB. // let FIB = [1, 2]; -while (FIB [FIB . length - 1] + FIB [FIB . length - 2] < N) { +while (FIB [FIB . length - 1] + FIB [FIB . length - 2] <= N) { FIB . push (FIB [FIB . length - 1] + FIB [FIB . length - 2]); } -- cgit