Counting Valleys

See the original problem on HackerRank.

Solutions

Intuition: we keep track of how many steps we are on or under the sea (e.g. variable level). When we go down (e.g. we read D) we decrement our level by one. When we go up we increment our level by one and also check if we were just one level below the sea. If the case, we are walking through a valley (e.g. we increment a counter).

C++

Here is a C++ implementation of the idea above:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main() 
{
    char c; int cnt=0, level = 0;
    while (cin >> c)
    {
        // we go up
        if (c=='U')
        {
            if (level == -1) // we are just one level under the sea?
                cnt+= 1;
            level+= 1;
        }    
        if (c=='D') // we go down
        {
            level-= 1;    
        }
    }    
    cout << cnt;
}

The solution hides a pattern: reduce. Here is an implementation which uses std::accumulate, or the C++ idiom for reduce:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iterator>
#include <numeric>
#include <iostream>
using namespace std;

int main() 
{
    int n; cin >> n;
    auto level = 0;
    cout << accumulate(istream_iterator<char>(cin), istream_iterator<char>(), 0, [&](int cnt, char c){
        if (c == 'U' && level == -1)
            cnt += 1;        
        level += (c=='D') ? -1 : 1;
        return cnt;
    });
}

Haskell

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
step 'D' = -1
step 'U' = 1

doStep (valleys, level) s = (newValleys, newLevel)
    where
        newLevel = level + step s
        leavingValley = (level == -1) && (newLevel == 0)
        newValleys = valleys + fromEnum leavingValley

countValleys path = fst $ foldl doStep (0, 0) path

main = do
    _ <- getLine
    path <- getLine
    print $ countValleys path
We've worked on this challenge in these gyms: modena  padua  milan 
comments powered by Disqus