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 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 #include #include using namespace std; int main() { int n; cin >> n; auto level = 0; cout << accumulate(istream_iterator(cin), istream_iterator(), 0, [&](int cnt, char c){ if (c == 'U' && level == -1) cnt += 1; level += (c=='D') ? -1 : 1; return cnt; }); } 

  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