4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ First thing I see that's obvious is that you get string ranges over and over and over again. \$\endgroup\$ Nov 29, 2012 at 23:01
  • \$\begingroup\$ because we are looking at less than 1,000,000 - unless you really need to be super fast, why not consider ways of making the code more readable and perhaps more amenable to change (which will inevitably come)? \$\endgroup\$
    – BenKoshy
    Apr 14, 2017 at 0:11

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – abc
    Dec 1, 2012 at 20:10
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 8, 2012 at 11:07
0
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Imagine running a loop with a million digit number. It is definitely going to cross the execution time limit they have set. \$\endgroup\$
    – abc
    Dec 1, 2012 at 20:12

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.