16
\$\begingroup\$

Problem Statement

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'. (b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.

The challange can be found here.

Input Format

The first line contains an integer \$T\$, i.e., the number of test cases. The next \$T\$ lines will contain a string each.

Output Format

A single line containing the number of minimum operations corresponding to each test case.

Constraints

  • \$1 ≤ T ≤ 10\$
  • \$1 ≤\$ length of string \$≤ 104\$

All characters are lower cased English alphabets.

Sample Input

3
abc
abcba
abcd

Sample Output

2
0
4

Test Cases

  • For the first test case, abc → abb → aba.
  • For the second test case, abcba is a palindromic string.
  • For the third test case, abcd → abcc → abcb → abca = abca → abba.

Solution

T = gets.chomp.to_i
result = []
def difference x,y
  (x.ord - y.ord).abs  
end
T.times do
  string = gets.chomp
  i,j = 0, -1
  n = 0
  loop do
    n = n + difference(string[i], string[j])
    i += 1
    j -= 1
    break if string.length % 2 == 0 ? i == (string.length/2) : i + j == -1 && string[i] == string[j] && i == string.length/2
  end    
  result << n
end

puts result
\$\endgroup\$
2
  • 4
    \$\begingroup\$ I do not speak Ruby but I guess there is a way to write this in a more concise/beautiful way. As an example, here's what I wrote in Python : print sum((abs(ord(s[i]) - ord(s[-i-1]))) for i in range(len(s)/2)). Basically, you need to go through your list in both direction (and stop at the middle), summing the differences between the two values you are considering. \$\endgroup\$
    – SylvainD
    Jun 26, 2014 at 17:12
  • 2
    \$\begingroup\$ @Josay Yup, you got it. In Ruby it'd be puts (s.length/2).times.inject(0) {|n, i| n += (s[i].ord - s[-1-i].ord).abs} \$\endgroup\$
    – Flambino
    Jun 26, 2014 at 19:26

3 Answers 3

10
\$\begingroup\$

Josay pretty much gave the answer in the comments. That line of Python is even very close to Ruby's way of writing it.

Meanwhile, ckuhn203 made a good point about the break line being obtuse.

Go upvote those two! This is just to provide alternative code.

Basically, you can do this instead:

# get number of words (T) and repeat that number of times
gets.chomp.to_i.times do
  # get word and map it to its ascii  values
  chars = gets.chomp.chars.map(&:ord)
  # print the sum of the difference between chars from either end of the string
  puts (chars.count/2).times.inject(0) { |sum, i| sum += (chars[i] - chars[-1-i]).abs }
end

Or you can skip the map(&:ord), and get closer Josay's code by getting the difference as (chars[i].ord - chars[-1-i].ord).abs

\$\endgroup\$
10
\$\begingroup\$

There is almost always a better way to loop in Ruby than actually using a loop. Unfortunately, I don't know Ruby well enough to say what that better way is.

What I can say is that this line of code is a bit obtuse.

break if string.length % 2 == 0 ? i == (string.length/2) : i + j == -1 && string[i] == string[j] && i == string.length/2

While it does seem to be a very Ruby way to write something like this, it's not very readable. Ternaries stretching off the screen are not a good thing in my opinion. It's okay to use an If block there.

\$\endgroup\$
6
\$\begingroup\$

Others have already given you good advise about your code. I'd add that the problem is that it's too imperative (change, update, accumulate). That leads to verbose and non-declarative code. Instead, a functional approach using expressions and known abstractions usually leads to more compact, declarative code. I'd write:

nlines = $stdin.readline.to_i
$stdin.take(nlines).each do |line|
  numbers = line.strip.chars.map(&:ord)
  pairs = numbers.zip(numbers.reverse).take(numbers.size / 2)
  sum = pairs.map { |n1, n2| (n1 - n2).abs }.reduce(0, :+)
  puts(sum)
end
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.