Algorithms

HackerRank Jumping on the Clouds Challenge

Given the sequence of up and down steps, find the number of valleys walked through

---

The details for the problem detailed in this post can be found at https://www.hackerrank.com/challenges/jumping-on-the-clouds/problem

The following solution is written in Javascript.

Problem

There is a new mobile game that starts with consecutively numbered clouds. Some of the clouds are thunderheads and others are cumulus. The player can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus 1 or 2. The player must avoid the thunderheads. Determine the minimum number of jumps it will take to jump from the starting position to the last cloud. It is always possible to win the game.

Breaking down the challenge into blocks of requirements, we get:

• int 0 = Safe Cloud
• int 1 = Unsafe Cloud
• int c[n] = Clouds - an array of binary integers
• Jump = To any cumulus that is c[i+1] or c[i+2]

Example

    c = [0, 1, 0, 0, 0, 1, 0]
  

Index the array from 0...6. The number on each cloud is its index in the list so the player must avoid the clouds at indices 1 and 5. They could follow these two paths: 0 > 2 > 4 > 6 or 0 > 2 > 3 > 4 > 6 . The first path takes 3 jumps while the second takes 4. Return 3.

Function Description

jumpingOnClouds has the following parameter(s):

• int c[n]: an array of binary integers

Returns

• int: the minimum number of jumps required

Input Format

The first line contains an integer n, the total number of clouds. The second line contains n space-separated binary integers describing clouds c[i].

Sample Input 0

    7
    0 0 1 0 0 1 0
  

Sample Output 0

    4
  

Explanation

The player must avoid c[2] and c[5]. The game can be won with a minimum of 4 jumps:

Sample Input 1

    6
    0 0 0 0 1 0
  

Sample Output 0

    3
  

Explanation

The player must avoid c[4]. The game can be won with a minimum of 3 jumps:

Goal

For each game, you will get an array of clouds numbered 1 if they are safe or 2 if they must be avoided. Write a function that returns the minimum number of jumps required.

Constraints & Validation

• The number of socks clouds will be more than 2 but less than 100
• Each cloud will be 1 or 0

    2 <= n <= 100
    c[i] will consist of {0,1}
  

First Attempt Solution

The first solution I came up with created an array with the path indexes and returned the path length.

    function jumpingOnClouds(c) {

        let path = [];

        for(let i = 0; i < c.length; i++){
            if(c[i+2] == 0) {
                if(i != 0) path.push(i);
                i ++;
            } else if (c[i+1] == 0) {
                if(i != 0) path.push(i);
            }
            if(i == c.length - 1) path.push(i)
        }
        return path.length;
    }

Refactored Solution 1

While looking to refactor the code I realised that each index of c could be used as a boolean (true or false).

Using this we can replace the if statement with a ternary statement and just compute the number of jumps.

    function jumpingOnClouds(c) {

            let jumps = 0;

            for(let i = 0; i < c.length - 1;){
                i += (c[i+2] ? 1 : 2);
                jumps++;
            }
            return jumps;
        }

Refactored Solution 2

The refactored solution above made me think that you could achieve the same simplicity with a while loop.

    function jumpingOnClouds(c) {

        let jumps = 0,
            currentCloud = 0;

        while (currentCloud < c.length-1) {
            currentCloud += (c[currentCloud+2] ? 1 : 2);
            jumps++;
        }
        return jumps;
    }

Conclusion

I'm not sure which of the two refactored solutions above is more optimal, with a simple enough function like the one above I doubt there is any difference in speed, however the second solution using the while loop is definitely easier to read.