SPOJ Adding Reversed Numbers

Question

Recently, I was taking up this challenge and choose my favorite language 'Ruby' to do it. My following solution got accepted (Gist).

For each test case, I am to reverse two numbers, add them, and print the reverse of the sum. Reversing means taking the base-10 digits of a number in reverse order, stripping any leading or trailing zeroes.

### Code
cases = gets.chomp.to_i

if cases.zero?
  puts "Enter number > 0"
  exit
end

def reverse_num(num)
  num.to_s.reverse.to_i
end

def rev_add(data)
  sum = 0
  data.each do |rec|
    sum += reverse_num(rec)
  end
  reverse_num(sum)
end

results = []

cases.times do |index|
  input_str = gets.chomp
  nums = input_str.split(' ').map(&:to_i)
  results[index] = rev_add(nums)
end

results.each { |e| puts e }

### End of Code

It showed that I have used 7.3MB memory which I don't have any idea.

I know this is not the optimized solution. I have used lots of looping which could be minizied. Could you review it and help me to optimize it?

Answer 1

While your performance limits may be satisfied by producing your results as they are available, there are also other issues in your code which you should consider altering.

First up, 1-liner solutions are convenient for saving some typing, but often make compromises that affect other aspects of your code. In your case, the 1-liner for reversing the number:

  num.to_s.reverse.to_i

That line takes a number, converts it to a string, and then reverses the string, and then converts the string back to a number.

Note that in each conversion, you need to convert between base-2 and base-10 number systems, and that you need to allocate space for the String, etc. While the following takes more code, it actually does less work:

def reverse_num(num)
  rev = 0
  while num > 0 do
    rev *= 10
    rev += num % 10
    num /= 10
  end
  rev
end

There are no strings in the above, the loop iterates one time for each decimal digit, and well, just works.

A second issue I want to point out is with your line-by-line algorithm. You read an entire line, split on the spaces, and from the list of strings, you create a list of numbers with to_i. You then iterate this list, and sum the reverses.

A much neater solution is to do a map->reduce operation:

sum = input_str.split(' ').map{ |n| reverse_num(n.to_i) }.reduce(:+)

Then you can eliminate the entire rev_add method. The end result is:

cases = gets.chomp.to_i

def valid_numeric_input?(input)
  input.zero?
end

def reverse_num(num)
  rev = 0
  while num > 0 do
    rev *= 10
    rev += num % 10
    num /= 10
  end
  rev
end

valid_numeric_input?(cases)

cases.times do |index|
  input_str = gets.chomp
  sum = input_str.split(' ').map{ |n| reverse_num(n.to_i) }.reduce(:+)
  puts reverse_num(sum)
end

Answer 2

There is no reason to store all the results to be printed at the end of the program. Each test case is independent, so you should be able to print and discard each result as you go.

Answer 3

Take a look into Enumerable (reduce) to use functional abstractions instead of imperative patterns. A lazy approach, not bothering to write a to_digits function (as your original code), would be:

total_lines = $stdin.readline.to_i
$stdin.take(total_lines).each do |line|
  n1, n2 = line.split.map { |s| s.reverse.to_i }
  reversed_sum = (n1 + n2).to_s.reverse.sub(/^0+/, '')
  puts(reversed_sum)
end