The Love Letter Mystery [closed]

At Hackerrank.com, the love letter mystery is a simple programming problem, which I already solved.

My solution involved calculating the palindrome and counting the number of operations to do it. On Hackerrank, they have another approach, which I don't understand completely:

Given a string, you have to convert it into a palindrome using a certain set of operations.

Let's assume that the length of the string is L, and the characters are indexed from 0 to L-1. The string will be palindrome, only if the characters at index i and the characters at index (L-1-i) are same. So, we need to ensure that the characters for all such indices are same.

Let's assume that one such set of indices can be denoted by A' and B'. It is given that it takes one operation in decreasing value of a character by 1. So, the total number of operations will be |A'-B'|.We need to calculate this for all such pairs of indices, which can be done in a single for loop. Take a look at the setter's code.

I understand everything up until they mention that the total number of operations are |A'-B'|, the absolute value between the two indices. Why is that? For some reason, my head is being thicker (than usual).

Thanks!

======== EDIT ==========

Hey guys, thanks for your input. I thought that this stackexchange site would had been more appropiate than stackoverflow. Is there any stackexchange site where this question is more appropiate?

• This question appears to be off-topic because it is not a programming contest or a question about code golfing. Jun 14, 2014 at 16:21
• @m.buettner It's a question about a specific approach to solve a programming puzzle, but it has nothing to do with code. Jun 14, 2014 at 16:25
• @Dennis this is currently being discussed in a lot of detail in chat and on meta, and there are a fairly large number of people who would welcome more non-challenge posts on the site, as it is still a site about Programming Puzzles & Code Golf (in addition to being a site for Programming Puzzles & Code Golf). As long as no consensus on this has been reached, I'd say closing or downvoting such questions is up to everyone's own opinion, but my opinion is we should welcome these questions, because they seem very much on topic to me and could well increase our traffic. Jun 14, 2014 at 16:38
• @m.buettner I agree that we should welcome non-challenge questions, but this question is more related to algorithms than to programming and code. Jun 14, 2014 at 16:45
• HackerRank has its own discussion pages for each problem. Here's the discussion page for the problem you mentioned. Jun 16, 2014 at 10:38

The algorithm might make more sense with a sample implementation to look at (here, in Python):

S = raw_input()
L = len(S)
T = 0
for i in range(L/2):
A = ord(S[i])
B = ord(S[L-1-i])
T += abs(A-B)
print T


Let's review the problem description. Each character decrement (e.g. --'b' == 'a') counts as a single operation. The problem is to determine the number of operations required to transform the input string into a palindrome.

The algorithm iterates over half the string, and compares the ordinal value of the character at the current index with that of the character across from it (in its mirrored position). If they are not the same, the one that is larger needs to be decremented, but it doesn't actually need to be checked which is which. Taking the absolute value of the difference will produce the correct number of operations needed regardless.

I think a source of confusion might be the wording, "Let's assume that one such set of indices can be denoted by A' and B'." I believe that the author intended A' and B' to refer to the characters at each of these indices, and not the indices themselves. If they had actually meant to refer to the indices, the algorithm would return the same value for any given string length, which is obviously incorrect.

A golfed version might look like this:

s=map(ord,raw_input())
print sum(abs(s[i]-s[~i])for i in range(len(s)/2))


I suspect Ruby might be a bit shorter, because indexing a string returns the ordinal value, rather than the individual character.