Jumping on the Clouds

Earlier today I was scrolling through YouTube videos and Jumping on the Clouds HackerRank Solution by JAVAAID came up. About the time this channel was starting the author and I exchanged some messages. In general I do not spend too much time watching this channel, but I became curios today and decided to solve the challenge and then watch the video.

Besides that and work not much else going on. My wife cooked too much for lunch so she decided to go with a friend for a walk and some shopping to the Mall of America. I assume she will be back towards the end of my workday. We need to get a birthday card for one of my sons. Hopefully she remembers and gets it while at the MOA.

If interested, the Jumping on the Clouds problem description is described in the HackerRank web site.

7
0 1 0 0 0 1 0

0 -> 2 -> 4 -> 6
3


7
0 0 1 0 0 1 0

0 -> 1 -> 3 -> 4 -> 6
4


6
0 0 0 0 1 0

0 -> 2 -> 3 -> 5
3


10
0 0 1 0 0 0 0 1 0 0

0 -> 1 -> 3 -> 5 -> 6 -> 8 -> 9
6

The idea is simple. Emma starts at cloud labeled 0 and jumps from cloud to cloud until she reaches the last one. Emma can only jump on to clouds with value 0. Clouds with value 1 may not be used. Emma can jump over 1 cloud. In other words, given the current cloud i.e., 0, she can jump to the next i.e., 1 or skip it and jump to the following i.e., 2. The purpose of this exercise is for

Emma to jump the least number of times. Your job, if you choose to accept, is to write some code (in our case in Java 8) to let Emma know how can she jump from the start cloud 0 to the end cloud n – 1 with the minimum number of jumps.

The first input line contains the number of clouds. The next line contains the values for the clouds. A value of 0 indicates the cloud can be used for landing, while a value of 1 indicates that Emma cannot land but she could jump over it.

In our first case the answer is 3 jumps. Note that as a bonus I decided to display the path similar to what is used by the requirements page. I labeled the associated instructions “bonus points”. Of course you need to at least comment out the code that displays the path. When I submitted my solution I just commented out such lines.

  // **** open scanner ****
  private static final Scanner scanner = new Scanner(System.in);

 /**
   * Test scaffolding.
   */
  public static void main(String[] args) throws IOException, IllegalArgumentException {

    // **** ****
    // BufferedWriter bufferedWriter = new BufferedWriter(new
    // FileWriter(System.getenv("OUTPUT_PATH")));
    BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    // **** ****
    int n = scanner.nextInt();
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    // **** ****
    int[] c = new int[n];

    // **** ****
    String[] cItems = scanner.nextLine().split(" ");
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    // **** ****
    for (int i = 0; i < n; i++) {
      int cItem = Integer.parseInt(cItems[i]);
      c[i] = cItem;
    }

    // **** ****
    int result = jumpingOnClouds(c);

    // **** output result ****
    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    // **** close buffered writer ****
    bufferedWriter.close();

    // **** close scannner ****
    scanner.close();
  }

I always like to read and comment the test scaffolding. In this case I changed the line instantiating the buffered writer. I like to use System.out and not a file.

The scaffolding is simple. Read the number of clouds. Define an array to hold the values for the clouds in the next line. Read the line and populate the array.

Now we are ready to compute an answer for Emma.

Once we do we display the number of jumps. Remember not to display the suggested path if you decide to go for the added bonus.

 /**
   * Complete the jumpingOnClouds function below.
   */
  static int jumpingOnClouds(int[] c) {

 // **** bonus points ****
    ArrayList<Integer> clouds = new ArrayList<Integer>();
    clouds.add(0);

    // **** initialize number of jumps ****
    int jumps = 0;

    // **** traverse the path ****
    for (int i = 0; i < c.length - 1; jumps++) {

      // **** determine the length of the jump ****
      if ((i + 2 < c.length) && (c[i + 2] == 0)) {
        i += 2;
      } else if ((i + 1 < c.length) && (c[i + 1] == 0)) {
        i += 1;
      } else {
        // System.out.println("jumpingOnClouds <<<< unexpected input c: " +
        // Arrays.toString(c));
        // throw new IllegalArgumentException("invalid array contents");
      }

      // **** bonus points ****
      clouds.add(i);
    }

    // **** display path (bonus points) ****
    for (int i = 0; i < clouds.size(); i++) { if (i + 1 >= clouds.size()) {
        System.out.print(clouds.get(i));
      } else {
        System.out.print(clouds.get(i) + " -> ");
      }
    }
    System.out.println();

    // **** return the number of jumps ****
    return jumps;
  }

We will use an array list to keep track of the path on the clouds. We initialize the path with cloud 0 since Emma must start there.

We then initialize the number of jumps to 0.

The idea is to loop from the first cloud to the last cloud. We implement this as a loop. On each pass we check if we could jump over a cloud or have to jump to the next cloud. We updated the index to the current cloud. We then count the jump.

Before we return, we display the path from the first to the last cloud. This bonus code will help Emma visualize her route.

When done we return the number of jumps.

Note that I have included a final else condition (which is currently commented out) in the if-else-if statement. The reason is that if we do not have it and the input is incorrect we may end in a forever loop.

8
0 0 0 0 0 1 1 0

Loops forever unless our code throws an exception.

After running the code, enable the commented out lines in the else condition and give the code a try.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.