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?

• Cristian Lupascu: My guess is that the 7.3MB are a fixed memory consumption when starting the Ruby Virtual Machine. My trivial solution to "TEST - Life, the Universe, and Everything" alo consumed 7.3MB.
• Jay Mitchell: Side note, the call to valid_numeric_input? doesn't affect the program at all.

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.

• Dhanu Gurung: As per the question, it displayed the results at the end. I didn't find any alternative other than to store into result
• 200_success: I don't see any requirement to buffer up all the results to be printed all at once.
• Dhanu Gurung: Yes, submitted without buffering results. It got accepted. :) I thought the answer should be printed at the end.

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

• rolfl: I also considered the keep-it-as-a-string option, but it breaks on input like 003 007 .... I was not sure that it was a valid solution. But, it is still a really good observation in that it skips a conversion for each value.