Merge remote-tracking branch 'upstream/master'

10 files changed, 190 insertions, 0 deletions

diff --git a/challenge-077/abigail/Part1/input1 b/challenge-077/abigail/Part1/input1
new file mode 100644
index 0000000000..1e8b314962
--- /dev/null
+++ b/challenge-077/abigail/Part1/input1
@@ -0,0 +1 @@
+6
diff --git a/challenge-077/abigail/Part1/input2 b/challenge-077/abigail/Part1/input2
new file mode 100644
index 0000000000..ec635144f6
--- /dev/null
+++ b/challenge-077/abigail/Part1/input2
@@ -0,0 +1 @@
+9
diff --git a/challenge-077/abigail/Part1/input3 b/challenge-077/abigail/Part1/input3
new file mode 100644
index 0000000000..83b33d238d
--- /dev/null
+++ b/challenge-077/abigail/Part1/input3
@@ -0,0 +1 @@
+1000
diff --git a/challenge-077/abigail/Part1/input4 b/challenge-077/abigail/Part1/input4
new file mode 100644
index 0000000000..66a899ac41
--- /dev/null
+++ b/challenge-077/abigail/Part1/input4
@@ -0,0 +1 @@
+377
diff --git a/challenge-077/abigail/Part1/output1.exp b/challenge-077/abigail/Part1/output1.exp
new file mode 100644
index 0000000000..170feacebb
--- /dev/null
+++ b/challenge-077/abigail/Part1/output1.exp
@@ -0,0 +1,2 @@
+1 + 2 + 3 = 6
+1 + 5 = 6
diff --git a/challenge-077/abigail/Part1/output2.exp b/challenge-077/abigail/Part1/output2.exp
new file mode 100644
index 0000000000..d029569c34
--- /dev/null
+++ b/challenge-077/abigail/Part1/output2.exp
@@ -0,0 +1,2 @@
+1 + 3 + 5 = 9
+1 + 8 = 9
diff --git a/challenge-077/abigail/Part1/output3.exp b/challenge-077/abigail/Part1/output3.exp
new file mode 100644
index 0000000000..88b8b236eb
--- /dev/null
+++ b/challenge-077/abigail/Part1/output3.exp
@@ -0,0 +1,15 @@
+2 + 3 + 8 + 21 + 34 + 89 + 233 + 610 = 1000
+2 + 3 + 8 + 55 + 89 + 233 + 610 = 1000
+2 + 3 + 8 + 144 + 233 + 610 = 1000
+2 + 3 + 8 + 377 + 610 = 1000
+2 + 3 + 8 + 987 = 1000
+5 + 8 + 21 + 34 + 89 + 233 + 610 = 1000
+5 + 8 + 55 + 89 + 233 + 610 = 1000
+5 + 8 + 144 + 233 + 610 = 1000
+5 + 8 + 377 + 610 = 1000
+5 + 8 + 987 = 1000
+13 + 21 + 34 + 89 + 233 + 610 = 1000
+13 + 55 + 89 + 233 + 610 = 1000
+13 + 144 + 233 + 610 = 1000
+13 + 377 + 610 = 1000
+13 + 987 = 1000
diff --git a/challenge-077/abigail/Part1/output4.exp b/challenge-077/abigail/Part1/output4.exp
new file mode 100644
index 0000000000..4fc109d510
--- /dev/null
+++ b/challenge-077/abigail/Part1/output4.exp
@@ -0,0 +1,7 @@
+1 + 2 + 5 + 13 + 34 + 89 + 233 = 377
+3 + 5 + 13 + 34 + 89 + 233 = 377
+8 + 13 + 34 + 89 + 233 = 377
+21 + 34 + 89 + 233 = 377
+55 + 89 + 233 = 377
+144 + 233 = 377
+377 = 377
diff --git a/challenge-077/abigail/Part1/solution.js b/challenge-077/abigail/Part1/solution.js
new file mode 100644
index 0000000000..f2d7173403
--- /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);
+}
diff --git a/challenge-077/abigail/Part1/solution.pl b/challenge-077/abigail/Part1/solution.pl
new file mode 100644
index 0000000000..b39028c5b9
--- /dev/null
+++ b/challenge-077/abigail/Part1/solution.pl
@@ -0,0 +1,63 @@
+#!/opt/perl/bin/perl
+
+#
+# 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")
+#
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+chomp (my $N = <>);
+
+#
+# Create a list of Fibonacci Numbers up to $N. We will start with (1, 2),
+# skipping the first two numbers 0 and 1. 0 doesn't add anything, and
+# we cannot duplicate numbers, so we just need one 1.
+#
+my @FIB = (1, 2);
+while ($FIB [-1] + $FIB [-2] <= $N) {
+    push @FIB => $FIB [-1] + $FIB [-2];
+}
+
+sub solutions;
+
+#
+# Create all solutions for number $target, with all Fibonnaci numbers
+# having index $index or above.
+#
+sub solutions ($target, $index = 0) {
+    map {
+        my $fib = $FIB [$_];
+        $target  < $fib ? ()
+      : $target == $fib ? [$target]
+      : map {[$fib, @$_]} solutions ($target - $fib, $_ + 1)
+    } $index .. @FIB - 1;
+}
+
+my @all = solutions $N;
+
+local $" = " + ";
+say "@$_ = $N" for @all;
+
+__END__