O(n^2) Solution for Programming Praxis 2010-10-15: Find The Longest Palindrome In A String edit

longest_palindrome.rb

#!/usr/bin/env ruby

## Find The Longest Palindrome In A String
## October 15, 2010
##
## http://programmingpraxis.com/2010/10/15/find-the-longest-palindrome-in-a-string/
##
## Greplin issued a programming challenge recently that required programmers
## to solve three problems; when completed, Greplin issued an invitation to
## send them a resume. The first problem required the programmer to find the
## longest palindrome in the following 1169-character string:
##
##     Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
##     inentanewnationconceivedinzLibertyanddedicatedtotheproposit
##     ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
##     rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
##     atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
##     avecometodedicpateaportionofthatfieldasafinalrestingplacefo
##     rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
##     etherfangandproperthatweshoulddothisButinalargersensewecann
##     otdedicatewecannotconsecratewecannothallowthisgroundThebrav
##     elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
##     ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
##     ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
##     tisforusthelivingrathertobededicatedheretotheulnfinishedwor
##     kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
##     forustobeherededicatedtothegreattdafskremainingbeforeusthat
##     fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
##     ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
##     olvethatthesedeadshallnothavediedinvainthatthisnationunsder
##     Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
##     ythepeopleforthepeopleshallnotperishfromtheearth
##
## Your task is to write a function that finds the longest palindrome in a
## string and apply it to the string given above.

class String
  # Return the middle of the string, counting the given number of characters
  # left and right. Note that mid(0) of a string with an even number of
  # characters is an empty string, while mid(0) of a string with an odd
  # number of characters will be the center chracter.
  def mid(count = 0)
    mid       = self.length / 2
    start_pos = mid - count
    end_pos   = self.length.even? ? mid + (count - 1) : mid + count

    self.slice start_pos..end_pos
  end
end

class PalindromeFinder
  def self.find(string)
    longest = ""

    (0...string.length).each do |count|
      palindrome = find_longest_palindrome_at_char string, count
      longest = palindrome if !palindrome.nil? && palindrome.length > longest.length
    end

    longest
  end

  # Return the longest palindrome in the substring defined by
  # the given string using the character at the position given
  # as the endpoint of the search string.
  def self.find_longest_palindrome_at_char(string, position)
    max_string = string.slice 0..position
    found = nil
    (1..max_string.length/2).each do |count|
      potential = max_string.mid count
      return found unless palindrome? potential
      found = potential
    end
    found
  end

  # Return the middle of the given string,
  # counting count characters left and right.
  def self.mid(string, count)
    length    = string.length
    mid       = length / 2
    start_pos = mid - count
    end_pos   = string.length.even? ? mid + (count - 1) : mid + count

    string.slice start_pos..end_pos
  end

  # Return true if the given string is a palindrome.
  def self.palindrome?(string)
    true if !string.nil? && string.eql?(string.reverse)
  end
end

string = DATA.read.gsub "\n", ""
string.downcase!
puts PalindromeFinder::find string

__END__

Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
forustobeherededicatedtothegreattdafskremainingbeforeusthat
fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
olvethatthesedeadshallnothavediedinvainthatthisnationunsder
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth

The implentation of String#mid in 5b7810 is probably not the best; mid(0) on a string with an even number of characters should probably return the middle two characters instead of an empty string. However, this works okay for the Praxis exercise.

This is really cool! I was surprised at how few lines of code it took to solve this problem...I don't think mine would have been this short. ;)

Neat trick with the END + DATA.read. Being a Ruby novice, I'd never seen it before.