A palindrome checker in 7 lines, and what String.include really does

A palindrome reads the same forwards and backwards, once you ignore case, spaces and punctuation. In Ruby that's seven lines.

Let's write them, then look at the three decisions hiding inside: the regex, the include, and what happens the first time someone types an accent.

The seven lines

module Palindrome
  def palindrome?
    tmp = downcase.gsub(/[^[[:alnum:]]]/, "")

    tmp == tmp.reverse
  end
end

String.include Palindrome

"lol".palindrome?   # => true

Three steps. downcase normalizes case. The gsub deletes every character that isn't a letter or a digit, so spaces, commas and slashes stop mattering. Then we compare what's left to its reverse.

There's no receiver on downcase, so it's called on self, the string you invoked the method on. Nothing gets mutated: gsub and reverse both hand back new strings.

"racecar".palindrome?                          # => true
"A man, a plan, a canal: Panama".palindrome?   # => true
"11/11/11 11:11:11".palindrome?                # => true
"hello".palindrome?                            # => false

That third one passes because [[:alnum:]] means letters and digits, so the timestamp cleans down to 111111111111. You also get "".palindrome? # => true for free, since an empty string equals its own reverse. Both are defensible. Just decide you agree with them before this method ends up behind a validation.

The regex, and why it isn't [a-z0-9]

/[^[[:alnum:]]]/ looks like a typo. It isn't. Read it from the inside out: [[:alnum:]] is the POSIX bracket expression for "alphanumeric", and POSIX classes are only valid inside a character class, so they always come wrapped in a second pair of brackets. The leading ^ negates it.

The tempting shortcut is \w, and it's wrong in two different ways:

"snake_case".gsub(/[^[[:alnum:]]]/, "")   # => "snakecase"
"snake_case".gsub(/[^\w]/, "")            # => "snake_case"

"café".gsub(/[^[[:alnum:]]]/, "")         # => "café"
"café".gsub(/[^\w]/, "")                  # => "caf"

\w includes the underscore, and in Ruby it's ASCII-only by default while [[:alnum:]] is Unicode-aware on a UTF-8 string. So \w treats every accented letter as punctuation and deletes it. That's not the kind of difference you want to meet in production.

What String.include actually does

String.include Palindrome is a plain method call, public since Ruby 2.1. It doesn't reopen String. It inserts the module into the ancestor chain, directly above the superclass and below the class itself:

String.ancestors   # => [String, Comparable, Object, Kernel, BasicObject]
String.include Palindrome
String.ancestors   # => [String, Palindrome, Comparable, Object, Kernel, BasicObject]

Position in that array is the lookup order, and it decides who wins a name clash. String comes first, so try to override upcase from the module and nothing happens:

module Palindrome
  def upcase = "from the module"
end

String.include Palindrome

"lol".upcase                              # => "LOL"
String.instance_method(:upcase).owner     # => String

That's the feature, not the limitation. An included module can add a method to a core class, but it can't accidentally hijack one you depend on. If you really need to override, you have to reopen the class or reach for prepend.

The accent trap

Here's where the seven lines break. The classic French palindrome:

"Ésope reste ici et se repose".palindrome?   # => false

tmp = "Ésope reste ici et se repose".downcase.gsub(/[^[[:alnum:]]]/, "")

tmp           # => "ésoperesteicietserepose"
tmp.reverse   # => "esoperesteicietsereposé"

É downcases to é, not to e. A French reader treats them as the same letter; Ruby compares code points, and they're two different ones.

The fix is to decompose the accented characters and drop the accent. NFD normalization splits é into a base e plus a combining acute, and combining marks live in Unicode category Mn:

module Palindrome
  def palindrome?
    tmp = downcase
            .unicode_normalize(:nfd)
            .gsub(/\p{Mn}/, "")
            .gsub(/[^[[:alnum:]]]/, "")

    tmp == tmp.reverse
  end
end

String.include Palindrome

"Ésope reste ici et se repose".palindrome?   # => true
"élu par cette crapule".palindrome?          # => true
"hello".palindrome?                          # => false

In a Rails app you could reach for ActiveSupport::Inflector.transliterate instead, which also handles characters like ø that have no decomposition. It's Latin-oriented though, and replaces anything it can't map with a ?, so it's a poor fit for text that might contain Greek, Cyrillic or CJK.

The optimization that makes it slower

reverse allocates a full copy, which invites the classic fix: walk two pointers inward and compare in place, no copy. On a 100,000-character palindrome, that "allocation-free" version runs about 5.8 times slower than the seven lines it replaces.

allocs { subject.palindrome? }              # => 6
allocs { subject.palindrome_two_pointer? }  # => 100005

tmp[i] returns a new one-character String, so the loop allocates two objects per iteration. And the copy you were trying to avoid was never the expensive part anyway: the downcase.gsub accounts for over 99% of the method's cost. Optimize the clean-up if you have to optimize anything.

Global, or scoped to your own code

String.include Palindrome is global. Every string in the process gains palindrome?, yours and every gem's. A refinement scopes the change instead:

module StringPalindrome
  refine String do
    def palindrome?
      tmp = downcase.gsub(/[^[[:alnum:]]]/, "")

      tmp == tmp.reverse
    end
  end
end

using StringPalindrome

"racecar".palindrome?                            # => true
String.instance_methods.include?(:palindrome?)   # => false

String is untouched, and the method only exists from the using line to the end of that file. Rule of thumb: refine when it's a convenience for your own code, include when it's part of your application's vocabulary and every file should have it. Just know that the second one means you now own that name process-wide, and if a gem later defines its own palindrome?, the last one loaded wins silently.

Related quizzes

Two short ones on String behavior that bites the same way:

• Calling += on a frozen String
• When upcase! returns nil mid-chain