|
| 1 | +/** |
| 2 | + * Using the JavaScript language, have the function arrayMinJumps(arr) take the |
| 3 | + * array of integers stored in arr, where each integer represents the maximum |
| 4 | + * number of steps that can be made from that position, and determine the least |
| 5 | + * amount of jumps that can be made to reach the end of the array. For example: |
| 6 | + * if arr is [1, 5, 4, 6, 9, 3, 0, 0, 1, 3] then your program should output the |
| 7 | + * number 3 because you can reach the end of the array from the beginning via |
| 8 | + * the following steps: 1 -> 5 -> 9 -> END or 1 -> 5 -> 6 -> END. Both of these |
| 9 | + * combinations produce a series of 3 steps. And as you can see, you don't |
| 10 | + * always have to take the maximum number of jumps at a specific position, you |
| 11 | + * can take less jumps even though the number is higher. |
| 12 | + * |
| 13 | + * If it is not possible to reach the end of the array, return -1. |
| 14 | + * |
| 15 | + * https://www.coderbyte.com/results/bhanson:Array%20Min%20Jumps:JavaScript |
| 16 | + * |
| 17 | + * @param {array} arr of integers |
| 18 | + * @return {number} |
| 19 | + */ |
| 20 | +function arrayMinJumps(arr) { |
| 21 | + // Brute force |
| 22 | + |
| 23 | + // Generate combos |
| 24 | + let combos = []; |
| 25 | + for (let max = Math.pow(2, arr.length), i = max / 2; i < max; i++) { |
| 26 | + let combo = i.toString(2); |
| 27 | + // Pad combo |
| 28 | + while (combo.length < arr.length) { |
| 29 | + combo = '0' + combo; |
| 30 | + } |
| 31 | + combos.push(combo); |
| 32 | + } |
| 33 | + |
| 34 | + // Find combos that can reach the end |
| 35 | + let goodCombos = []; |
| 36 | + combos.forEach(combo => { |
| 37 | + let goodCombo = true; |
| 38 | + |
| 39 | + for (let i = 0, last = 0, skips = 0; i < combo.length; i++) { |
| 40 | + if (combo[i] === '1') { |
| 41 | + if (i - last > skips) { |
| 42 | + // fail |
| 43 | + goodCombo = false; |
| 44 | + break; |
| 45 | + } |
| 46 | + |
| 47 | + skips = arr[i]; |
| 48 | + last = i; |
| 49 | + } |
| 50 | + } |
| 51 | + |
| 52 | + // Must be able to get to the end |
| 53 | + if (combo[combo.length - 1] !== '1') { |
| 54 | + goodCombo = false; |
| 55 | + } |
| 56 | + |
| 57 | + if (goodCombo) { |
| 58 | + goodCombos.push(combo); |
| 59 | + } |
| 60 | + }); |
| 61 | + |
| 62 | + // Replace combos with number of jumps to reach the end, |
| 63 | + // and sort combos by number of jumps ascending |
| 64 | + const numJumps = goodCombos |
| 65 | + .map(combo => { |
| 66 | + return combo |
| 67 | + .split('') |
| 68 | + .map(Number) |
| 69 | + .reduce((sum, value) => (sum += value), -1); |
| 70 | + }) |
| 71 | + .sort((a, b) => a - b); |
| 72 | + |
| 73 | + if (numJumps.length === 0) { |
| 74 | + return -1; |
| 75 | + } |
| 76 | + |
| 77 | + return numJumps[0]; |
| 78 | +} |
| 79 | + |
| 80 | +module.exports = arrayMinJumps; |
0 commit comments