# Tasty Meal

See the original problem on HackerRank.

To solve the problem we can easily observe that swapping the first c with the last p minimizes the tastiness.

The answer is $$0$$ when either:

• there are not p
• there are not c
• the last p is before the first c

For example:

 1  pppccc 

Instead, if neither of the conditions above occur, we swap the first occurrence of c with the last occurrence of p and we proceed with measuring the tastiness.

To count the tastiness, we can just run two loops: one forward and one backwards. Here is the idea in C++:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); auto cnt = 0; for (auto i : s) { if (i == 'c') cnt++; else cost += cnt; } cnt = 0; for (int i=s.size()-1; i>=0; i--) { if (s[i] == 'p') cnt++; else cost += cnt; } } cout << cost; 

The solution is linear and does not allocate extra space.

### Playing with patterns

Can we replace loops with patterns?

Yes we can.

The first pattern we can think of is reduce. Here is the idea:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); cost += accumulate(begin(s), end(s), make_pair(0ll,0ll), [](auto res, auto curr){ return curr == 'c' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second); }).first; cost += accumulate(rbegin(s), rend(s), make_pair(0ll,0ll), [](auto res, auto curr){ return curr == 'p' ? make_pair(res.first, res.second + 1) : make_pair(res.first+res.second, res.second); }).first; } cout << cost; 

CLearly, refactoring is possible to remove code duplication. Left as an exercise.

A second approach consists in the combination of two patterns: map and prefix sum:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  string s; cin >> s; auto firstC = s.find_first_of('c'); auto lastP = s.find_last_of('p'); auto cost = 0ll; if (firstC != string::npos && lastP != string::npos && firstC < lastP) { swap(s[firstC], s[lastP]); vector c(s.begin(), s.end()); transform(begin(c), end(c), begin(c), [](auto i) { return (char)i == 'c'; }); partial_sum(begin(c), end(c), begin(c)); // cakes on the right (dual: pies on the left) vector c2(s.begin(), s.end()); transform(begin(c2), end(c2), begin(c2), [](auto i) { return (char)i == 'p'; }); partial_sum(rbegin(c2), rend(c2), rbegin(c2)); for (auto i=0u; i

c and c2 are used to count respectively the number of c on the left and the number of p on the right.

This core part of this solution can be rewritten with C++20 ranges:

  1 2 3 4 5 6 7 8 9 10 11  auto c = views::transform(s, [](auto c) { return (int)(c == 'c'); }) | views::partial_sum; auto c2 = views::transform(s, [](auto c) { return (int)(c == 'p'); }) | views::reverse | views::partial_sum | ranges::to>(); std::cout << ranges::accumulate( views::zip(s, c, c2 | views::reverse) | views::transform([](auto p) { return std::get<0>(p) == 'p' ? std::get<1>(p) : std::get<2>(p); }), 0); 

Clearly, we pay an extra vector.