Lychrel numbers

First of all, for those of you, who don't know (or forgot) about Lychrel numbers, here is an entry from Wikipedia: http://en.wikipedia.org/wiki/Lychrel_number.

I want to implement the Lychrel number detector in the range from 0 to 10_000. He开发者_开发技巧re is my solution:

class Integer

  # Return a reversed integer number, e.g.:
  # 
  #   1632.reverse #=> 2361
  #
  def reverse
    self.to_s.reverse.to_i
  end

  # Check, whether given number
  # is the Lychrel number or not.
  #
  def lychrel?(depth=30)
    if depth == 0
      return true
    elsif self == self.reverse and depth != 30 # [1]
      return false
    end
    # In case both statements are false, try
    # recursive "reverse and add" again.
    (self + self.reverse).lychrel?(depth-1)
  end
end

puts (0..10000).find_all(&:lychrel?)

The issue with this code is the depth value [1]. So, basically, depth is a value, that defines how many times we need to proceed through the iteration process, to be sure, that current number is really a Lychrel number. The default value is 30 iterations, but I want to add more latitude, so programmer can specify his own depth through method's parameter. The 30 iterations is perfect for such small range as I need, but if I want to cover all natural numbers, I have to be more agile.

Because of the recursion, that takes a place in Integer#lychrel?, I can't be agile. If I had provided an argument to the lychrel?, there wouldn't have been any changes because of the [1] statement.

So, my question sounds like this: "How do I refactor my method, so it will accept parameters correctly?".

What you currently have is known as tail recursion. This can usually be re-written as a loop to get rid of the recursive call and eliminate the risk of running out of stack space. Try something more like this:

def lychrel?(depth=30)
    val = self
    first_iteration = true

    while depth > 0 do
        # Return false if the number has become a palindrome,
        #   but allow a palindrome as input
        if first_iteration
            first_iteration = false
        else
            if val == val.reverse
                return false
        end

        # Perform next iteration
        val = (val + val.reverse)
        depth = depth - 1
    end
    return true
  end

I don't have Ruby installed on this machine so I can't verify whether that 's 100% correct, but you get the idea. Also, I'm assuming that the purpose of the and depth != 30 bit is to allow a palindrome to be provided as input without immediately returning false.

By looping, you can use a state variable like first_iteration to keep track of whether or not you need to do the val == val.reverse check. With the recursive solution, scoping limitations prevent you from tracking this easily (you'd have to add another function parameter and pass the state variable to each recursive call in turn).

A more clean and ruby-like solution:

class Integer

  def reverse
    self.to_s.reverse.to_i
  end

  def lychrel?(depth=50)
    n = self
    depth.times do |i|
      r = n.reverse
      return false if i > 0 and n == r
      n += r
    end
    true
  end

end

puts (0...10000).find_all(&:lychrel?) #=> 249 numbers

bta's solution with some corrections:

class Integer

  def reverse
    self.to_s.reverse.to_i
  end

  def lychrel?(depth=30)
    this = self
    first_iteration = true

    begin
      if first_iteration
        first_iteration = false
      elsif this == this.reverse
        return false
      end

      this += this.reverse
      depth -= 1
    end while depth > 0

    return true
  end
end

puts (1..10000).find_all { |num| num.lychrel?(255) }

Not so fast, but it works:

code/practice/ruby% time ruby lychrel.rb > /dev/null 
ruby lychrel.rb > /dev/null  1.14s user 0.00s system 99% cpu 1.150 total