Skip to content

Commit 1249a94

Browse files
committed
Added medium/array_min_jumps
1 parent 03a73a3 commit 1249a94

File tree

2 files changed

+93
-0
lines changed

2 files changed

+93
-0
lines changed

medium/array_min_jumps.js

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
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;

medium/array_min_jumps.test.js

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
const arrayMinJumps = require('./array_min_jumps');
2+
3+
describe('arrayMinJumps()', () => {
4+
test('correctly returns minimum number of jumps', () => {
5+
expect(arrayMinJumps([1, 5, 4, 6, 9, 3, 0, 0, 1, 3])).toBe(3);
6+
7+
expect(arrayMinJumps([3, 4, 2, 1, 1, 100])).toBe(2);
8+
9+
expect(
10+
arrayMinJumps([1, 3, 6, 8, 2, 7, 1, 2, 1, 2, 6, 1, 2, 1, 2])
11+
).toBe(4);
12+
});
13+
});

0 commit comments

Comments
 (0)