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);

Haskell. Conversion from Char to Int must be explicit and here is done mapping all character in the list through fromEnum. The <$> operator is the map operator. half is a function that takes integral half of the passed list. Integral half is ok, because the central character, when the list has an odd number of element, must not change. The powerful zipWith zips together the two halves applying the absolute difference. The solution is just the sum of those differences.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
solve :: String -> Int
solve s = sum $ zipWith diff l r
  where
    xs = fromEnum <$> s
    half = take $ length s `div` 2
    l = half xs
    r = half $ reverse xs
    diff x y = abs $ x - y

main = interact $ unlines . fmap (show . solve) . tail . lines

Same, with list comprehension

1
2
3
4
5
6
solve s = sum [abs (a - b) | (a, b) <- zip l r]
  where
    xs = fromEnum <$> s
    half = take $ length s `div` 2
    l = half xs
    r = half (reverse xs)
We've worked on this challenge in these gyms: modena 
comments powered by Disqus