Counting Valleys Algorithm

https://www.hackerrank.com/challenges/counting-valleys/

In this article, I'll be describing how I solved the Counting Valleys Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

An avid hiker keeps meticulous records of their hikes. During the last hike that took exactly steps steps, for every step it was noted if it was an uphill, U, or a downhill, D step. Hikes always start and end at sea level, and each step up or down represents a 1 unit change in altitude. We define the following terms:

A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.

Given the sequence of up and down steps during a hike, find and print the number of valleys walked through.

Example

The hiker first enters a valley 2 units deep. Then they climb out and up onto a mountain 2 units high. Finally, the hiker returns to sea level and ends the hike.

Function Description

Complete the countingValleys function in the editor below.

countingValleys has the following parameter(s):

int steps: the number of steps on the hike
string path: a string describing the path

Returns

int: the number of valleys traversed

Input Format

The first line contains an integer steps, the number of steps in the hike.

The second line contains a single string path, of characters that describe the path.

Sample Input 0:

Sample Output 0:

Explanation:

If we represent _ as sea level, a step up as /, and a step down as \, the hike can be drawn as:

The hiker enters and leaves one valley.

Solution 🔎

In plain English, A valley is a series of steps below sea level, starting with a step down from sea level and ending with a step up to seal level. We need to count how many valleys a hiker enters during a hike.

To test our solution, let's consider the same sample input from above.

Step 1: Loop through the string `path`

To decide if the hiker is in a valley or not, we’ll have to check if each step step is an uphill, U or a downhill D, and then check this position with reference to the sea level because the sea level is what differentiates a valley from a mountain.

Before we begin iterating through the string path, we’ll create two variables:

valley_count: an integer representing the number of valleys walked through.
sea_level: an integer representing the current sea level. sea_level = 0 means the hiker is at sea level. sea_level = -2 means the hiker is in a valley 2 units deep.

For this iteration, we need access to both the index and the character as we iterate through the string, so we use enumerate() An example from a question on StackOverflow:
Now we can access a character and its index in the string path.

    valley_count = 0
    sea_level = 0

    for i, c in enumerate(path):

Step 2: Develop the ‘valley-check’ conditional logic.

Here, we’ll develop conditional statements to check if we have just entered a valley or not. Since we know the hiker starts hiking from sea level, we can easily track any changes in altitude from our conditional logic.

If the hiker makes a downhill step D, from sea level, we’ll subtract a 1 unit change in altitude from the sea_level,
Then we move to the next step in path until we make an uphill step, U. Once this happens we’ll add a 1 unit change in altitude to the sea_level,
Now at this point, we need to check if the hiker is at seal level after this uphill step.
If he is, we simply add 1 to the valley_count variable. If he isn't we'll go to the next step,
Once the iteration completes, we’ll return valley_count.

        if c == 'D':
            sea_level -= 1
            i += 1

        elif c == 'U':
            sea_level += 1

            if sea_level == 0:
                valley_count += 1

    return valley_count

Step 3: Putting it all together

Full code.

def countingValleys(steps, path):
    # Write your code here
    valley_count = 0
    sea_level = 0

    for i, c in enumerate(path):

        if c == 'D':
            sea_level -= 1
            i += 1

        elif c == 'U':
            sea_level += 1

            if sea_level == 0:
                valley_count += 1

    return valley_count

countingValleys(8, 'UDDDUDUU')
# 1

SIde Notes

In hindsight, the conditional logic seemed pretty easy but it took me longer than usual to formulate it. I had a hard time figuring out a way to check if the hiker was at sea level after any given step in path. You’ll also notice I didn’t use the steps parameter given with the function, therefore I am positive a different approach could use it and perhaps simplify the code.

Thanks for reading!

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻