Coding Problem: Counting Valleys

View original at HackerRank

Problem Verbatim: Hackerrank wants us to solve for how many valleys Gary enters into and exits on his hike. Note: this is not how many times Gary went down a step, that would be quite simple. This program should calculate how many times Gary entered below sea-level and then exited.

We will always be provided an array containing two types of values: D (Down) and U (Up).

Example Input

UDDDUDUU

_/\            _
      \        /
        \/ \/

Example Output
1

Background: Let’s read this array from left to right. Gary begins at sea-level and moves up one space, therefore he has entered a mountain in the program. Given that the program is only asking for valleys, we don’t need to tally the mountains encountered on the trip.

The next move is down one space, leaving us at sea-level. So far, Gary has gone up one space and then down one space. We can better represent this as variables:

up = 1
down = 1

Given that Gary has traveled up as many spaces as he has traveled down, we know that Gary is currently at sea-level. Another way of writing that might be:

up = 1
down = 1

if up = down then it’s true Gary is at sea level

By moving down a space, Gary has now left sea-level and entered a valley, which will be the first one tallied in this program. Instead of returning to sea-level, Gary traverses down deeper into the valley one space, and then up one space.

At this point in the journey, Gary has gone down 3 spaces and up 2. We can represent this like:

up = 2
down = 3

Because down is greater than up, we know that Gary must still be in the valley. We’ll continue this logic until Gary has completed his journey. By the end of the array, we’ll have:

Up = 4
Down = 4

Meaning Gary has returned to sea level and exited the valley, the only valley we have recorded Gary entering on his journey.

Pseudocode
Our code should do the following:
1. Determine whether Gary is at sea-level
2. Determine whether Gary has entered a valley
3. Track the total amount of up spaces and down spaces
4. Determine if Gary has left the valley
5. Tally the total amount of valleys Gary enters on his trip
Python3 solution: