Find a palindrome using Ruby

Question

I am preparing for an upcoming exam and have the following practice question..

Write a method to determine if a word is a palindrome, without using the reverse method.

Most of you probably know what a palindrome is, but for those that don't.. a palindrome is a word which reads the same backward or forward.

Anyway, here's my answer to the question. I've written my own reverse method as directed.

How would you refactor this?

def reverse(word_arr)
  reverse = []
  index = word_arr.length
  until index == 0 do
    reverse << word_arr[index - 1]
    index -= 1
  end
  reverse
end

def is_palindrome?(word)
  word_arr = word.downcase.gsub(/ /,'').split('')
  true if word_arr == reverse(word_arr)
end

p is_palindrome?('Anna')
p is_palindrome?('Joe')
p is_palindrome?('Go dog')

Answer 1

There are some different ways to look at what a palindrome is, and all of them can translate directly to code.

[For simplicity's sake, I will assume that the word always gets passed as an Array of downcased single-letter Strings, e.g. like palindrome?('Anna'.downcase.chars)]

"A palindrome is the same forwards and backwards":

def palindrome?(word)
  word == reverse(word)
end

This is of course the one you were thinking about, and the one the exam author wants to prohibit. Obviously, one way to "work around" this restriction is to implement the reversal method yourself.

Again, there are several different ways of thinking about reversing an array:

"Appending the first element to the reversed rest":

def reverse(ary)
  return [] if ary.empty?
  reverse(ary.drop(1)) + [ary.first]
end

"Prepending the last element to the reversed rest":

def reverse(ary)
  return [] if ary.empty?
  [ary.last] + reverse(ary[0...-1])
end

"The first and last letters are the same and the rest is a palindrome":

def palindrome?(word)
  return true if word.empty?
  word.first == word.last && palindrome?(word[1...-1])
end

My guess is that this, or something like this, is actually what the exam author was thinking about. However, by explicitly forbidding reverse, they focus the student's mind on "How can I overcome not having reverse" instead of "how could I interpret a palindrome differently". IOW: it's a bad exam question (if my guess is right).

Of course, there are even more ways to think about palindromes (and reversal), and there are some interesting optimizations given in other answers and comments.

Answer 2

What if you changed the algorithm to do the following steps?

1. Remove all Spaces
2. If String Length is Odd, delete middle character
3. Split string in half
4. Reverse one of the halves
5. Compare the two halves

Rationale: In your case, you reverse the entire string, even when it's very large, when you really only need to reverse the first half of the string.

Answer 3

Predicate etiquette

The convention in Ruby is for predicates to end with a ?. That signals that the function returns true or false, rather than true or nil.

Note that when the function name ends in ?, it's redundant to have it start with is_. Starting with is is more like the Java naming convention.

Your function's parameter name is word, yet you discard spaces in it anyway. Perhaps it would be better to call it str instead.

Algorithm

As others have pointed out, implementing your own reverse function complies with the letter of the specification, but probably not with the spirit of the question. It's arguably worse than using Ruby's built-in reverse.

Instead of split(''), prefer String#chars. But you might not need to convert the string to an array at all, since Ruby strings can be indexed and mutated much like arrays.

This implementation is much simpler:

def palindrome?(str)
  str = str.downcase.gsub(/ +/, '')
  (0 ... str.length/2).all? { |i| str[i] == str[-i - 1] }
end

Reverse

If you did want to write such a function, this one-liner would be more idiomatic Ruby.

def reverse(str)
  (1..str.length).map { |i| str[-i] }.join
end

This function, like yours, accepts either a string or an array of characters as input. Unlike yours, it returns a string (due to the use of #join).

Answer 4

Chiming in to share some thoughts. Although my solution verbose but could be a good start point for some beginner.

TDD

Always start from test, it would let you think from different perspective. Make TDD your habit from start.

class TestPalindrome < Test::Unit::TestCase
  def test_empty_or_one_character
    assert palindrome?("")
    assert palindrome?("t")
  end

  def test_string_not_palindrome
    assert !palindrome?("motor")
  end

  def test_string_palindrome
    assert !palindrome?("motor")
  end

  def test_string_length_even
    assert palindrome?("ww")
  end
end

Though these are not perfect but still you can start from here.

Code for humans

Don't try to pre-optimize maintain a good habit from start and code for humans, let them read and understand your intent.

Personally I like helper methods like these:

def firstChar(str)
    str.chars.first
end

def lastChar(str)
    str.chars.last
end

def middleChars(str)
    str[1...-1]
end

Now, the running code:

require 'test/unit'

def palindrome?(str)
    # base case 1
    if str.length <= 1
        return true
    end
    # base case 2
    if firstChar(str) != lastChar(str)
        return false
    end
    # recursive case
    palindrome?(middleChars(str))
end

def firstChar(str)
    str.chars.first
end

def lastChar(str)
    str.chars.last
end

def middleChars(str)
    str[1...-1]
end

class TestPalindrome < Test::Unit::TestCase
  def test_empty_or_one_character
    assert palindrome?("")
    assert palindrome?("t")
  end

  def test_string_not_palindrome
    assert !palindrome?("motor")
  end

  def test_string_palindrome
    assert !palindrome?("motor")
  end

  def test_string_length_even
    assert palindrome?("ww")
  end
end