How To Solve The Jumping On The Clouds Challenge
How To Solve HackerRank’s Jumping On The Clouds Code Challenge With JavaScript
Problem
The Jumping On The Cloud code challenge is about a girl named Emma that jumps from one cloud to another, but wants to avoid the thunder clouds:
- 🏃♀️Emma = jumper
- Jumps types available = 1 space jump or 2 space jump
- C = array of clouds container 1’s and 0's
- ⛅️ 0 = Regular cloud
- ⛈️ 1 = Thunder cloud
- N = number of clouds
- N is number of clouds between 2 and 100 (which could be useless if we’re just calculating the array length)
- Assumption, the data passed to us is already formatted as an array
Sample Inputs
// Example 1
// N = 7
// C = 0 0 1 0 0 1 0
// Expected: 4
// Path: 0 -> 1 -> 3 -> 4 -> 6
// Jumps Taken = 4
// Jump Types: 0-1 = 1, 1-3 = 2, 3-4 = 1, 4-6 = 2// Example 2
// N = 6
// C = 0 0 0 0 1 0
// Expected: 3
// Path: 0 -> 2 -> 3 -> 5
// Jumps Taken = 3
// Jump Types: 0-2 = 2, 2-3 = 1, 3-5 = 2
Goal
Write a function or functions that returns the shortest amount of jumps needed to get through the clouds ( c ) without jumping on a thundercloud ( 1 )
Covering Our Bases
Covering our bases, we need to make sure that:
- Number of item (values) of C is in between 2 and 100
- N isn’t be sent in this case so we don’t need to deal with it
- Set the initial number of jumps to 0 and return it if C doesn’t meet the requirements
function jumpingOnClouds(c) {
const min = 2;
const max = 100;
let jumps = 0; if (c.length >= min && c.length <= max) {
// continue
} // return jumps
return jumps;
}
Understanding The Problem
Knowing that Emma can only jump 1 or 2 spaces we need to find a way to traverse the array and keep track of the different paths.
Iterating Over The Array
First step is to iterate over the array, for this first step, we’ll try using a for loop.
// Example 1
// N = 7
// C = 0 0 1 0 0 1 0...
if (c.length >= min && c.length <= max) {
let path1 = [];
for (let a = 0; a < c.length; a++) {
if (c[a] !== 1) {
path1.push(1); // a jump by one
} else {
break;
}
}
// Looping
// 0->0 1 0 0 1 0, path1 = [ 1 ]
// 0->0->1 0 0 1 0, break; (Already wrong route)
}
...
At first glance this might be the first step we take but if we run it, it’s already starting to introduce some problems.
- This is great for jumps of 1, but what about jumps of 2?
- What about different combinations of jumps of 1 and 2?
- If this isn’t the right path we need to go back and try a different route.
We Need Recursion
Knowing that we need to traverse the array and different combinations of the array, we’re going to use good ol’ recursion.
Completely rewriting above, we can assume that we’ll be passing it the array values of ( c ) and making sure to stop once we’ve gotten to the last index the array or if the path is completely wrong. We’ll also need keep track of all the different paths.
function findPaths(c, paths) {
if (c.length > 1) { // remaining item of the array
}
// return the paths that were sent to us
return paths;
} Different Combinations
In order to handle different combinations, we need to create two different directions for the paths to take and track them. For that we’ll need to copy the existing path and increment (jump) by 1 or 2. Additionally, because we’ll know when the jump happens if the next value is a thundercloud (1), we could void the path entirely.
function findPaths(c, paths) {
if (c.length > 1) { // remaining item of the array
// making copies of the path
let path1 = paths.slice();
let path2 = paths.slice();
// check path1 where we iterate over c by a jump of 1
// check if c[1] is 1, quickly invalidate path1
// or add 1 to the path1
path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
// and we do the same for path 2 for a jump of 2
path2 = (c[2] !== 1) ? [ ...path2, 2] : 0; // quickly invalidating that we can't continue with
// a jump of 1 or 2
if (path1 === 0
&& path2 === 0) {
paths = 0; // jump to end of function
}
}
// return the paths that were sent to us
return paths;
}
Running a test
// Example
// N = 8
// C = 1 1 1 0 0 1 0 1
// Expected: 0findPaths([1, 1, 1, 0, 0, 1, 0, 1], []);
// Output: 0
Iterating For The Next Jumps
Now we need to continue the iteration process with recursion and cover the when path1 or path2 fails.
function findPaths(c, paths) {
if (c.length > 1) { // remaining item of the array
// making copies of the path
let path1 = paths.slice();
let path2 = paths.slice();
// check path1 where we iterate over c by a jump of 1
// check if c[1] is 1, quickly invalidate path1
// or add 1 to the path1
path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
// and we do the same for path 2 for a jump of 2
path2 = (c[2] !== 1) ? [ ...path2, 2] : 0; // quickly invalidating that we can't continue with
// a jump of 1 or 2
if (path1 === 0
&& path2 === 0) {
paths = 0; // jump to end of function
} else if (path1 !== 0
&& path2 === 0) { // Path 1 still good
return findPaths(c.slice(1), path1);
} else if (path1 === 0
&& path2 !== 0) { // Path 2 still good
return findPaths(c.slice(2), path2);
}
}
// return the paths that were sent to us
return paths;
}
Walkthrough Test:
// Example
// N = 5
// C = 1 0 1 0 0 findPaths([1, 0, 1, 0, 0], []);// C = [1, 0, 1, 0, 0]
// Paths = []
// Path1 Viable? Yes. Path1 = [1]
// Path2 Viable? No. Path2 = 0// C = [0, 1, 0, 0]
// Paths = [1]
// Path1 Viable? No. Path1 = 0
// Path2 Viable? Yes. Path2 = [1, 2]// C = [0, 0]
// Paths = [1, 2]
// Path1 Viable? Yes. Path1 = [1, 2, 1]
// Path2 Viable? Yes. Path2 = [1, 2, 2]// Result: [1, 2] (Looks like it didn't continue)
Handling When Both Paths Are Viable
We now need to account for when both paths are viable, but also return the shortest.
function findPaths(c, paths) {
if (c.length > 1) { // remaining item of the array
// making copies of the path
let path1 = paths.slice();
let path2 = paths.slice();
// check path1 where we iterate over c by a jump of 1
// check if c[1] is 1, quickly invalidate path1
// or add 1 to the path1
path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
// and we do the same for path 2 for a jump of 2
path2 = (c[2] !== 1) ? [ ...path2, 2] : 0; // quickly invalidating that we can't continue with
// a jump of 1 or 2
if (path1 === 0
&& path2 === 0) {
paths = 0; // jump to end of function
} else if (path1 !== 0
&& path2 === 0) { // Path 1 still good
return findPaths(c.slice(1), path1);
} else if (path1 === 0
&& path2 !== 0) { // Path 2 still good
return findPaths(c.slice(2), path2);
} else if (path1 !== 0
&& path2 !== 0) {
path1 = findPaths(c.slice(1), path1);
path2 = findPaths(c.slice(2), path2);
// compare and return the shortest path
return (path1.length < path2.length) ? path1 : path2;
}
}
// return the paths that were sent to us
return paths;
}
Same Walkthrough Test:
// Example
// N = 5
// C = 1 0 1 0 0findPaths([1, 0, 1, 0, 0], []);// C = [1, 0, 1, 0, 0]
// Paths = []
// Path1 Viable? Yes. Path1 = [1]
// Path2 Viable? No. Path2 = 0// C = [0, 1, 0, 0]
// Paths = [1]
// Path1 Viable? No. Path1 = 0
// Path2 Viable? Yes. Path2 = [1, 2]// C = [0, 0]
// Paths = [1, 2]
// Path1 Viable? Yes. Path1 = [1, 2, 1]
// Path2 Viable? Yes. Path2 = [1, 2, 2]// PATH 1
// C = [0] (which doesn't meet our if (c.length > 1))
// Returned = [1, 2, 1]// PATH 2
// C = [] (which doesn't meet our if (c.length > 1))
// Returned = [1, 2, 2]// Path1 ([1, 2, 1]) < Path2 ([1, 2, 2]) = Nope, so return path 2// Result: [1, 2, 2]
Counting The Steps In The Path Returned
function jumpingOnClouds(c) {
const min = 2;
const max = 100;
let jumps = 0; if (c.length >= min && c.length <= max) {
jumps = findPaths(c, []);
} // return jumps
return ((typeof jumps === "number") ? jumps : jumps.length);
}
Solution
And here is the full solution:
function findPaths(c, paths) {
if (c.length > 1) {
let path1 = paths.slice();
let path2 = paths.slice();
path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
path2 = (c[2] !== 1) ? [ ...path2, 2] : 0; if (path1 === 0 && path2 === 0) {
paths = 0;
} else if (path1 !== 0 && path2 === 0) {
return findPaths(c.slice(1), path1);
} else if (path1 === 0 && path2 !== 0) {
return findPaths(c.slice(2), path2);
} else if (path1 !== 0 && path2 !== 0) {
path1 = findPaths(c.slice(1), path1);
path2 = findPaths(c.slice(2), path2);
return (path1.length < path2.length) ? path1 : path2;
}
}
return paths;
}function jumpingOnClouds(c) {
const min = 2;
const max = 100;
let jumps = 0; if (c.length >= min && c.length <= max) {
jumps = findPaths(c, []);
} return ((typeof jumps === "number") ? jumps : jumps.length);
}
Test Cases
// N = 5, C = [0, 1, 0, 0, 0], Expected 2
// N = 5, C = [1, 1, 1, 0, 0], Expected 0
// N = 0, C = [], Expected 0
// N = 101, C = [1, 0, 1, 0, 0, 1, 0, 1 ... ], Expected 0
// N = 7, C = [0, 0, 1, 0, 0, 1, 0], Expected 4
// N = 6, C = [0, 0, 0, 1, 0, 0], Expected 3jumpingOnClouds([0, 1, 0, 0, 0]); // 2 ✅
jumpingOnClouds([1, 1, 1, 0, 0]); // 0 ✅
jumpingOnClouds([]); // 0 ✅
jumpingOnClouds([1, 0, 1, 0, 0, 1, 0, 1 ... ]); // 0 ✅
jumpingOnClouds([1, 0, 1, 0, 0, 1, 0, 1 ... ]); // 0 ✅
jumpingOnClouds([0, 0, 1, 0, 0, 1, 0]); // 4 ✅
jumpingOnClouds([0, 0, 0, 1, 0, 0]); // 3 ✅
Feedback?
If you have any recommendations on how this can be optimized, or even a better solution, let’s talk. I love feedback.
If you got value from this, please give this article some applause 👏 and share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏
Please also follow me on twitter: @codingwithmanny and instagram at @codingwithmanny.
