Counting Valleys // Complete the countingValleys function below.

[Monsterboy]

Homework Statement

I am working on improving my programming and/or problem solving aptitude. I am currently trying to solve the problem the following page.

The program should count the number of valleys traversed. Please visit the link for more details

https://www.hackerrank.com/challenges/counting-valleys/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Relevant Equations

s = [UDDDUDUU] "U" stands for up and "D" for down

in the above example the number of valleys is 1

_/\ _
\ /
\/\/

// Complete the countingValleys function below.
// The code is in javaScript

function countingValleys(n, s) {
    let currentLevel = []     // an array of numbers that indicate the number of units of altitude above or below sea level regarding each step
    let altitude = 0              // the altitude above sea level          
    let valleyCount = 0;     // count of the number of valleys
    for (let i = 0; i < s.length; i++) {
        if(s[I] === 'U') {
            altitude++
            currentLevel.push(altitude)
        }
        else {
            altitude--
            currentLevel.push(altitude)
        }
        if(i >= 2) {
            if(currentLevel[I] === 0 && currentLevel[i-1] < 0
                && currentLevel[i-2] <= 0) {
                    valleyCount++
            }
           else if(currentLevel[i+1] < currentLevel[I] && currentLevel[I] < 0 &&
            currentLevel[i-1] < currentLevel[I] &&
            currentLevel[i-2] < currentLevel[i-1]) {
                valleyCount++
            }  
        }
    }
    return valleyCount
}

Right now, my code is passing 18 of the 22 test cases.

The remaining cases are

10
[DUDDDUUDUU]

100
[DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD]

1000
[DUDUUDUUUUUUDDDDDUDDUUUDUUUDDDUUUDDUDDDDUDDDDDUUDUDUDUDDDDUUDDUDDUUUUDDUUUUDUUDUUDUUUUDDDUDDUUUUDUDDDUUDUDUUDDUUUDUDDDUDUDUDUDUUUDUUUUUUDUDDDDDUDUDDDDUUUUUDUDUUUUUUUUDDDUUDUUDUDUDDDDDUDDDUDUUUDUDDDUDUUDUUDDDDDDDUDUDUUUDUDDUDUUDUDDDUUUDUDDDDUDDUDDUDUDUUDUDDDUDUUUDUUDUUUUUUUDUUUUUUUDDDDDUDDDUUUDDDUDDDUDDUUDDUUUDUUDDDUDUUDUUUDDUDDDDUUUUUUDUDUUDDDDUDUDDUUUDUDUUDDUUDDDUUDUUUUUDDUUDDDDUUUDUDUUDDUUDDUUDUDDDUDUDUDDUUDUDDUDUDDUUUDUDDUDDUUDUUDUDDDDDDDDDUDDUUDDUUUUDDUDUUDUUDUUDDDDUUUDUDDDDUDDUUDUDUDUUDDUUDUDUDDDDDUUUDDDDUDDDUUDDUUDDUUUDUDDDUDDDDDUUDUUUDDUDDDDUUUDDDDUUDDUUUDUUUDDUDUUUDUDDUUUDDDDDDDUUDDUDDUUUUUUDDDDUDDUDDUDDUDDDDDUUDDUDDDUDDUDUDDDUDUDUUDDUUDDDDUUDDUUUDUUDDDDDDUDUDDUDUUDDUDDDUUUUDDUUDUDDDDUUUDUUUUDDUDUUUDDUDUUUUUUDUUDDDDDUDDUDUDDDUDDDDUDUUUDUDUUDDUDDDUDUUDDDDDDDDUDUUDUDDUDDUDUUUDDDUDUDDUUUDUDUDDDUDDUDUUUDUDDDDDUDDDDDDUDUUUUDDUDDDUDDDUDUDUUUDDUDDUDDUUDDUDUDUDUUUUUDUUDDUUDUUDUUUDUDUDDUDDDUUDDDDUUDDUUUUDUUDUUUDDDDDUDDDDDUUUDDUUUDUUUDUUDUUUDUDUUDUDDUUUUUDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU]

1000000
[ too big to put here (1 million) ][/I][/I][/I][/I][/I]

 

[FactChecker]

Your link to the problem statement requires registering (which I, for one, will not do). And the examples are very confusing regarding how a valley is defined. Is it two or more Ds surrounded by Us?

I think that you should start with the smallest example where your program gets the wrong answer and show some details on that.

 

[Monsterboy]

Alright I will paste the whole question here.

Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U or a downhill, D step. Gary's hikes start and end at sea level and each step up or down represents a
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 Gary's sequence of up and down steps during his last hike, find and print the number of valleys he walked through.

For example, if Gary's path is s = [DDUUUUDD]

, he first enters a valley 2 units deep. Then he climbs out an up onto a mountain 2 units high. Finally, he returns to sea level and ends his hike.

Function DescriptionComplete the countingValleys function in the editor below. It must return an integer that denotes the number of valleys Gary traversed.

countingValleys() has the following parameter(s):

• n: the number of steps Gary takes
• s: a string describing his path

Constraints

• 2<= n <= 1000000

Output Format
Print a single integer that denotes the number of valleys Gary walked through during his hike.

Sample Input
8
UDDDUDUU

Sample Output
1

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

_/\.... _
...\.../
...\/\/\/

He enters and leaves one valley(Ignore the dots).Input Format
The first line contains an integer n, the number of steps in Gary's hike.
The second line contains a single string s, of n characters that describe his path.

 

[Monsterboy]

And the examples are very confusing regarding how a valley is defined. Is it two or more Ds surrounded by Us?

Yea, from the examples I assumed that two or more consecutive U's means he is climbing out of a valley behind him and the U's should be starting from a previous D which is below sea level.

 

[Monsterboy]

I think that you should start with the smallest example where your program gets the wrong answer and show some details on that.

The smallest example is the first one I mentioned in the post #1.
Writing it down in the form of backward and forward slashes, looks like this.

• 10
• DUDDDUUDUU

__....__
...\/\.../
...\.../\/
...\/

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.

From the above definition, the valley should be counted only if Gary comes back to sea-level from below right ?

So, the above example technically has only 1 valley, but the test case says there are two. Did I do it wrong ?

 

[FactChecker]

From the above definition, the valley should be counted only if Gary comes back to sea-level from below right ?

Are the correct answers given to you or are you determining the correct answers by inspection?

So, the above example technically has only 1 valley, but the test case says there are two. Did I do it wrong ?

Is the first 'DU' not a valley because it needs another step while it is beneath sea level? Otherwise, I count two valleys: 'DU', where the depth following each step is -1,0 followed by 'DDDUUDUU', where the depth following each step is -1, -2, -3, -2, -1, -2, -1, 0. If that is right, then the answer given by your program is correct.

 

[Monsterboy]

Are the correct answers given to you or are you determining the correct answers by inspection?

The expected outputs of the tests are given.

Is the first 'DU' not a valley because it needs another step while it is beneath sea level?

I think you are right, my assumption that Gary needs to go down a minimum of two steps to count a valley is wrong.

Thanks for the help !

 

[Monsterboy]

Very simple problem, I was just overthinking.

function countingValleys(n, s) {
    let currentLevel = []
    let altitude = 0
    let valleyCount = 0;
    for (let i = 0; i < s.length; i++) {
        if(s[i] === 'U') {
            altitude++
            currentLevel.push(altitude)
            }
        else {
            altitude--
            currentLevel.push(altitude)
            }
        if(currentLevel[i] === 0 && currentLevel[i-1] < 0) {
            valleyCount++
        }
    }
    return valleyCount
}