Merge remote-tracking branch 'upstream/master'

2 files changed, 157 insertions, 0 deletions

diff --git a/challenge-077/abigail/node/ch-1.js b/challenge-077/abigail/node/ch-1.js
new file mode 100644
index 0000000000..f2d7173403
--- /dev/null
+++ b/challenge-077/abigail/node/ch-1.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/node/ch-2.js b/challenge-077/abigail/node/ch-2.js
new file mode 100644
index 0000000000..ee04d5c605
--- /dev/null
+++ b/challenge-077/abigail/node/ch-2.js
@@ -0,0 +1,60 @@
+//
+// Exercise:
+//    You are given m x n character matrix consists of O and X only.
+//    Write a script to count the total number of X surrounded by O only.
+//    Print 0 if none found.
+//
+
+//
+// Read in the board:
+//    - Read STDIN
+//    - Split by newlines
+//    - Split each line on spaces
+//    - Map an 'X' to a 1, 'O' to a 0.
+//    - Add a 0 to the beginning and end of each line.
+//
+let fs    = require ("fs");
+let board = fs . readFileSync (0) . toString () . trim () . split ("\n") .
+            map (line => (line . split (" ")) . map (c => c == "X" ? 1 : 0)) .
+            map (line => ([0] . concat (line) . concat ([0])));
+
+//
+// Add top and bottom with 0s
+//
+board . push    (board [0] . map (x => 0));
+board . unshift (board [0] . map (x => 0));
+
+let count = 0;
+
+//
+// Iterate over the cells of the board board, skipping cells on the edge
+// (as we added them). For each 1, check the 8 cells surrounding the cell
+// (this will never be outside of the board). If one of the neighbouring
+// cells is a 1, move on the next cell. If no neighbouring cell is 1,
+// we add 1 to the count.
+//
+for (let x = 1; x < board . length - 1; x ++) {
+  ELEMENT:
+    for (let y = 1; y < board [x] . length - 1; y ++) {
+        if (!board [x] [y]) {
+            continue;
+        }
+        for (let dx = -1; dx <= 1; dx ++) {
+            for (let dy = -1; dy <= 1; dy ++) {
+                if (dx == 0 && dy == 0) {
+                    continue;
+                }
+                if (board [x + dx] [y + dy]) {
+                    continue ELEMENT;
+                }
+            }
+        }
+        count ++;
+    }
+}
+
+
+//
+// Print the results.
+//
+console . log (count);