Added hard/array_jumping

bradhanson · bradhanson · commit 83ac1a784234 · 2018-07-17T07:30:50.000-04:00
diff --git a/hard/array_jumping.js b/hard/array_jumping.js
@@ -0,0 +1,68 @@
+/**
+ * Using the JavaScript language, have the function arrayJumping(arr) take the
+ * array of numbers stored in arr and first determine the largest element in the
+ * array, and then determine whether or not you can reach that same element
+ * within the array by moving left or right continuously according to whatever
+ * integer is in the current spot. If you can reach the same spot within the
+ * array, then your program should output the least amount of jumps it took. For
+ * example: if the input is [2, 3, 5, 6, 1] you'll start at the spot where 6 is
+ * and if you jump 6 spaces to the right while looping around the array you end
+ * up at the last element where the 1 is. Then from here you jump 1 space to the
+ * left and you're back where you started, so your program should output 2. If
+ * it's impossible to end up back at the largest element in the array your
+ * program should output -1. The largest element in the array will never equal
+ * the number of elements in the array. The largest element will be unique.
+ *
+ * https://www.coderbyte.com/results/bhanson:Array%20Jumping:JavaScript
+ *
+ * @param  {array} arr
+ * @return {number}
+ */
+function arrayJumping(arr) {
+    const max = Math.max(...arr);
+    const startIndex = arr.indexOf(max);
+
+    // Iterative "breadth-first search"
+    // `queue` stores an array of arrays.  The inner arrays represent paths of
+    // indexes.  They all start with the index of the largest number and each
+    // jump is appended and the entire new structure is stored in a new queue.
+
+    let queue = [[startIndex]];
+
+    while (queue.length !== 0) {
+        const nextQueue = [];
+
+        for (let i = 0; i < queue.length; i++) {
+            const indexList = queue[i];
+            const lastIndex = indexList[indexList.length - 1];
+
+            const left =
+                (((lastIndex - arr[lastIndex]) % arr.length) + arr.length) %
+                arr.length;
+            const right = (lastIndex + arr[lastIndex]) % arr.length;
+
+            if (left === startIndex || right === startIndex) {
+                // Success!
+                return indexList.length;
+            }
+
+            if (!indexList.includes(left)) {
+                const leftArr = indexList.slice();
+                leftArr.push(left);
+                nextQueue.push(leftArr);
+            }
+
+            if (!indexList.includes(right)) {
+                const rightArr = indexList.slice();
+                rightArr.push(right);
+                nextQueue.push(rightArr);
+            }
+        }
+        queue = nextQueue;
+    }
+
+    // No path possible
+    return -1;
+}
+
+module.exports = arrayJumping;
diff --git a/hard/array_jumping.test.js b/hard/array_jumping.test.js
@@ -0,0 +1,25 @@
+const arrayJumping = require('./array_jumping');
+
+describe('arrayJumping()', () => {
+    test('passes Coderbyte.com tests', () => {
+        expect(arrayJumping([1, 2, 3, 4, 2])).toBe(3);
+
+        expect(arrayJumping([1, 7, 1, 1, 1, 1])).toBe(2);
+
+        expect(arrayJumping([2, 3, 5, 6, 1])).toBe(2);
+
+        expect(arrayJumping([1, 2, 1])).toBe(2);
+
+        expect(arrayJumping([1, 2, 1, 2, 1, 9])).toBe(3);
+
+        expect(arrayJumping([1, 2, 1, 2, 1, 12])).toBe(1);
+
+        expect(arrayJumping([0, 5, 2])).toBe(2);
+
+        expect(arrayJumping([1, 6, 5, 7, 9, 2])).toBe(-1);
+
+        expect(arrayJumping([1, 3, 5, 7, 9, 2])).toBe(2);
+
+        expect(arrayJumping([1, 5, 1, 6, 2, 3, 3])).toBe(2);
+    });
+});
