Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I was trying to solve the Next Palindrome problem listed in SPOJ in Ruby language. Please find the problem statement here. Though i came up with the below solution, i could not get the execution time below 1.4s even after tweaking this code numerous times. Where can this code be optimized in terms of memory and execution time or is there a better approach than the solution i came up with?

def next_palindrome 
  number = gets.chomp
  len = number.length
  if len == 1
    return "11\n" if number == "9"
    return number.next!<<"\n" 
  end
  if len.even?
    f = len/2   
    return number[0..f-1]<<number[0..f-1].reverse<<"\n" if number[0..f-1]>number[f..-1]
    number = number[0..f-1].next!
    return number<<number[0..f-1].reverse<<"\n"
  else
    f = (len-1)/2-1         
    return number[0..f+1]<<number[0..f].reverse<<"\n" if number[0..f]>number[f+2..-1] 
    number = number[0..f+1].next!       
    return number<<number[0..f].reverse<<"\n"
  end
end

def input
  gets.chomp.to_i.times {print next_palindrome}      
end

input
share|improve this question

migrated from stackoverflow.com Nov 30 '12 at 11:24

This question came from our site for professional and enthusiast programmers.

    
First thing I see that's obvious is that you get string ranges over and over and over again. –  Dave Newton Nov 29 '12 at 23:01

2 Answers 2

Cache cache cache! :) All those substrings you take should be stored in variables, rather than using the expensive substring methods. Furthermore, comparing strings can also be expensive. When you store the substring in a variable, you could parse the integer and keep it for comparisons later.

Advanced:

Since you never need to look at the last half number (if it's a palindrome it must be the reverse of the first digits), you can just store two variables: big_half and small_half. for even-digit numbers, they will be equal, but for odd-digit numbers big_half will have the middle digit. This makes creating a that is adjacent to the number (either just smaller or just larger) as simple as big_half + small_half.reverse. If a test shows it's the smaller one, increment big_half and generate a new small_half from it, then add together as above.

share|improve this answer
1  
We do need to look at the second half of the number right? For example if we take 1783, the next palindrome is 1881. If we ignore the second half we might end up with 1771 which is lesser than our input. Caching did help in bringing down execution time, but not significantly. –  Nullset Dec 1 '12 at 20:10
    
sorry, what I meant was that we don't have to store the parsed second half of the number, since we'll never have to look at that "part". We still need the original, whole number for comparisons, of course. Just not the end slice by itself. –  Mark Hubbart Dec 8 '12 at 11:07

I think you are over-complicating things here. I think there's two solutions to your problem.

  • Comparing two halves of the string
  • Recursively comparing chars[i] with chars[n-1-i], where n is the size

Mark did explained our first option, so let me explain the second. We already know that if our number is a palindrome, the first char will equals the last one, the second with equals the one before the last, etc...

As an example, let's start with a first number of 808.

# our number
k = "808"

# let's continue until we break!
while i = k.next! do

  # what is the size of our string?
  size = i.size

  # the next loop returns nil if two chars weren't equal
  # if it doesn't return nil, that means we have a palindrome! We can break
  break if (size / 2).ceil.times do |j|

    # Let's compare the first and the last chars.
    # If they aren't equal, we break (return nil).
    break unless i[j] == i[size - (j + 1)]
  end
end

puts i
share|improve this answer
    
Imagine running a loop with a million digit number. It is definitely going to cross the execution time limit they have set. –  Nullset Dec 1 '12 at 20:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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