Ruby Challenge: Palindrome
A palindrome is any word or phrase that's the same backwards as it is forwards. For example, "madam I'm Adam." Punctuation and capitalization does not count, only the letters themselves. The challenge in this article will be to determine if a given string is a palindrome or not.
When I first solved this problem, I was using C. The exercise was one of iterating over a string in two directions using pointers.
However, leveraging Ruby's modern power and flexibility, we can solve this problem much more simply.
First, all we want is are the word characters. Anything else we want to delete. There are a number of ways to do this, but we'll go back to the commonly used method gsub. The gsub method will replace all instances of a regular expression with something else, in this case we want all non-word characters to be replaced with nothing (with empty strings). The character class we want to use here is the \W character class. The \w class matches any word character, the \W character class matches the inverse of that, or any non-word character. So to start off with we need "string".gsub(/\W/, '').
Second, we want all the characters to be in the same case. We can make them all uppercase or all lowercase, but they must all be the same case for the comparison. We'll use the upcasemethod for this, which makes all word characters in a string uppercase. So we now have "string".gsub(/\W/, '').upcase
Next we have to decide where to put our methods.
I like to leverage Ruby and put these methods in the string class itself. You may not want to do this for larger projects, as this pollutes the namespace and introduces potential conflicts with other libraries, but for small projects like this challenge it's perfectly acceptable. So let's stuff this preparation method into a method in String.
Now all we have to do is compare the result of this method with the reverse of the result of this method. This is very straightforward, again we'll stick it in a method of the String class. Also note that when calling a method on yourself (since the methods here are in the string class itself, we're referring to ourselves) you don't need any message receiver. Where otherwise it might be somestring.upcase_words here it's simply upcase_words. Also, we're leaving off any return statements or conditionals. The equality operator yields a boolean, checking that with a conditional and return true or false would be redundant.
And there you have it. You can try it out on some strings for yourself. For example, "test".is_palindrome? will return false. However "radar".is_palindrome? will return true. And, of course, my favorite palindrome: "I'm a lasagna hog go hang a salami".is_palindrome? will return true.
As mentioned before, I first did this programming exercise in the C language as a way to practice using pointer. A pointer is a variable that refers to a place in memory. When used with strings, a pointer either refers to the start of a string or to any character inside the string. By using two pointers, you can iterate over the string forwards and backwards, extract the next character from either the beginning or the end, and compare them. We'll implement this in Ruby.
The first difference is that Ruby doesn't have pointers. Instead, to refer to a specific character in a string we use the index operator. So instead of pointers we have two variables: idx and ridx, to iterate from the beginning and the end respectively.
In the beginning of the method we set up our index variables. The idx variable starts at the beginning of the string, the ridx variable at the end of the string. We then start a loop, we keep looping until the idx variable reaches the end of the string. We don't bother checking the ridx variable since as they're advanced over the same string in the same way, they'll both reach the beginning or end of the string at the same time.
Within the loop we need to advance over non-word characters. We do this with a simple increment and while loop matching with the \W character class, just like last time. We then return false if we find something that doesn't match. The main loop here is to check for characters that don't match. If it doesn't find any characters that don't match, then all of the characters match and true is returned at the end of the method.
Which of these solutions is best? Which is more clear, which is fastest? The first solution is certainly the shortest, and to a Rubyist it's probably the most clear. And since things like the regular expression engine and gsub methods are implemented in C, it's also probably the fastest. The only real advantage the second solution has is it will take less memory. It creates fewer objects, and tests the existing string in place. But again, this will only really be an issue if you're testing a lot of palindromes.
The Easy Easy Way
When I first solved this problem, I was using C. The exercise was one of iterating over a string in two directions using pointers.
However, leveraging Ruby's modern power and flexibility, we can solve this problem much more simply.
First, all we want is are the word characters. Anything else we want to delete. There are a number of ways to do this, but we'll go back to the commonly used method gsub. The gsub method will replace all instances of a regular expression with something else, in this case we want all non-word characters to be replaced with nothing (with empty strings). The character class we want to use here is the \W character class. The \w class matches any word character, the \W character class matches the inverse of that, or any non-word character. So to start off with we need "string".gsub(/\W/, '').
Second, we want all the characters to be in the same case. We can make them all uppercase or all lowercase, but they must all be the same case for the comparison. We'll use the upcasemethod for this, which makes all word characters in a string uppercase. So we now have "string".gsub(/\W/, '').upcase
Next we have to decide where to put our methods.
I like to leverage Ruby and put these methods in the string class itself. You may not want to do this for larger projects, as this pollutes the namespace and introduces potential conflicts with other libraries, but for small projects like this challenge it's perfectly acceptable. So let's stuff this preparation method into a method in String.
class Stringdef upcase_wordsgsub(/\W/, '').upcaseendendNow all we have to do is compare the result of this method with the reverse of the result of this method. This is very straightforward, again we'll stick it in a method of the String class. Also note that when calling a method on yourself (since the methods here are in the string class itself, we're referring to ourselves) you don't need any message receiver. Where otherwise it might be somestring.upcase_words here it's simply upcase_words. Also, we're leaving off any return statements or conditionals. The equality operator yields a boolean, checking that with a conditional and return true or false would be redundant.
class Stringdef is_palindrome?upcase_words == upcase_words.reverseendendAnd there you have it. You can try it out on some strings for yourself. For example, "test".is_palindrome? will return false. However "radar".is_palindrome? will return true. And, of course, my favorite palindrome: "I'm a lasagna hog go hang a salami".is_palindrome? will return true.
The Hard Way
As mentioned before, I first did this programming exercise in the C language as a way to practice using pointer. A pointer is a variable that refers to a place in memory. When used with strings, a pointer either refers to the start of a string or to any character inside the string. By using two pointers, you can iterate over the string forwards and backwards, extract the next character from either the beginning or the end, and compare them. We'll implement this in Ruby.
The first difference is that Ruby doesn't have pointers. Instead, to refer to a specific character in a string we use the index operator. So instead of pointers we have two variables: idx and ridx, to iterate from the beginning and the end respectively.
class Stringdef is_palindrome?idx = 0ridx = length - 1while idx < lengthidx += 1 while self[idx].match(/\W/)ridx -= 1 while self[ridx].match(/\W/)return false if self[idx].upcase != self[ridx].upcaseidx += 1ridx -= 1endreturn trueendendIn the beginning of the method we set up our index variables. The idx variable starts at the beginning of the string, the ridx variable at the end of the string. We then start a loop, we keep looping until the idx variable reaches the end of the string. We don't bother checking the ridx variable since as they're advanced over the same string in the same way, they'll both reach the beginning or end of the string at the same time.
Within the loop we need to advance over non-word characters. We do this with a simple increment and while loop matching with the \W character class, just like last time. We then return false if we find something that doesn't match. The main loop here is to check for characters that don't match. If it doesn't find any characters that don't match, then all of the characters match and true is returned at the end of the method.
Which of these solutions is best? Which is more clear, which is fastest? The first solution is certainly the shortest, and to a Rubyist it's probably the most clear. And since things like the regular expression engine and gsub methods are implemented in C, it's also probably the fastest. The only real advantage the second solution has is it will take less memory. It creates fewer objects, and tests the existing string in place. But again, this will only really be an issue if you're testing a lot of palindromes.
Source...