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')

• Zack: Is it your intention to return nil instead of false when not a palindrome?
• Joe Ainsworth: I could have used return true if word_arr == reverse(word_arr) to return explicitly and then 'false' at the end of is_palindrome? to return implicitly. I didn't think about it though!

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.

• Mast: and the one the exam author wants to prohibit That's not obvious from the question and may not be true, given this comment by OP.

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.

• Joe Ainsworth: Okay. Great point. In terms of my reverse method, how well is this executed?
• Zack: Really you don't have to reverse the string at all. Just keep two indexes, one at the start and one at the end, and keep comparing values until the indexes meet or pass each other. You can exit on the first mismatch.
• Baronz: I love that even more, Zack. Start at the ends, work towards the middle, and skip spaces. (Just make sure you get a minumum of 1 sucessful match before you exit so that ' ' is not a palindrome)
• Jörg W Mittag: "so that ' ' is not a palindrome" – Is it? :-D (Ah, they joy of corner cases ...)

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