The Love-Letter Mystery

See the original problem on HackerRank.

Solutions

To solve this challenge we need to calculate the “distance” between the first and the last character, the second and the second to last, etc. We can do it only for the first half of the string:

1
2
a b c d
=> |a-d| + |b-c|

That can be coded in C++ as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
size_t T;
cin >> T;
string s;
while (T--)
{
	cin >> s;
	auto count = 0;
	auto first = s.begin();
	auto last = s.end() - 1;
	for (; first < last; ++first, --last)
	{
		if (*first != *last)
		{
			count += abs(*first - *last);
		}    
	}
	cout << count << endl;
}

We can actually learn a bit more from this challenge and solve it by combining some patterns. Conceptually, our solution does:

  • each character is turned into its ascii value
  • pairs of ascii values (begin and end, second and last to second, etc) are processed
  • for each pair, calculate absolute difference
  • finally, sum up the differences

So we can turn such a pipeline of patterns into some Python strings:

1
2
3
4
5
6
7
8
def theLoveLetterMystery(s):
    first = s[:len(s)/2]
    last = s[len(s)/2:][::-1]
    first = map(lambda x: ord(x), first)
    last = map(lambda x: ord(x), last)
    zipped = zip(first, last)
    mapped = map(lambda x: abs(x[0]-x[1]), zipped)
    return sum(mapped)

C++ lovers could use inner_product:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
size_t T;
cin >> T;
string s;
while (T--)
{
    cin >> s;
    cout << inner_product(
                 begin(s), 
                 next(begin(s), s.size()/2), 
                 rbegin(s), 
                 0, 
                 plus<>{}, 
                 [](auto l, auto r) { return abs(r-l); }) 
    << "\n";
}

For C++ braves, here is a possible solution using C++20 ranges:

1
2
3
4
5
6
7
auto first = view::take(s, s.size()/2);
auto last = view::reverse(s) | view::take(s.size()/2);   
cout << ranges::accumulate(
         view::zip(first, last) | 
         view::transform([](auto p) { 
              return abs(p.first - p.second); }
         ), 0);
We've worked on this challenge in these gyms: modena 
comments powered by Disqus