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
|