Talk Like A Duck

A few weeks ago, Amazon.com added a nice benefit to Amazon Prime membership, free video streaming. They don't (yet) have a catalog as extensive as say, Netflix, but there is enough to be interesting. I've finally seen all the Steig Larsson, "Millenium Series" movies, so I know what people who mention "The Girl with the Dragon Tatoo" are talking about. They seem to have at least one story from each of the many Doctors Who. More recently I got into a series of documentaries on design related topics.

My talents like more in programming, but I've always had an interest in the arts. My grandfather, and his father before him, were jewelers and engravers. My uncle had a successful career as a graphics artist and corporate identity executive in several large companies. I got very interested in graphic design when graphical user interfaces and desktop publishing came into vogue in the mid-1980s, albeit more from an "art appreciation" viewpoint than an ability to produce good art.

Now there's not much directly applicable to web design in these, but I recommend them for your viewing pleasure:

• Helvetica - covers the Swiss design movement from the 1950s, particularly the Helvetica font, which is probably the most use font of all.
• Objectified - talks mostly about product design, with interviews with designers including Jon Ives of Apple, and Chris Bangle, late of BMW.
• Milton Glazer: To Delight and Inform - Milton Glazer was in a sense the American answer to the Swiss design movement. He is quite prolific. Among other things he started New York Magazine, and has done many magazine designs, he also did the iconic Bob Dylan in silhouette with multi-colored hair poster, the I HEART NY logo, and many other iconic designs. The documentary basically interview him at work, home and at the site of some of his projects.

My friend Brian Adkins just published an article on his blog comparing the performance of his Haskell program to find the longest palindrome in a string to a similar program in Ruby.

His Haskell program runs 25 times faster than his Ruby program. He reports that the Haskell program takes 7 times as long to process an input twice as long.

Brian's approach is to generate all of the substrings in the input string, then filter that list of substrings to those which are palindromes, and then output the longest one which passes through that filter. A cursory analysis indicates that this is O(n^2) which is in-line with his data.

I couldn't resist, so I sat down with my MacBook and my Sunday morning coffee and wrote my version of the program, in about 30-45 minutes.

My first thought was that we want to cut down on the search space, by only examining substrings that could be palindromes. By definition a palindrome starts and ends with the same character, so we only need consider such substrings. It took a few minutes to find a reasonable approach.

My basic idea was to start by looking for the initial substrings of the string ending with the first character, then do the same for subsequent characters. Then it occurred to me that I should find the LONGEST initial substring, since if it were a palindrome shorter substrings can't be longer.

In pondering the best way to do this in Ruby, and thinking about using a regular expression, I realized that rather than starting with the beginning of the string, it would be better to start at the end. I could then use Ruby 1.9's String.match(regexp, pos), to find the longest substring at the end of the string starting and ending with the same character, using the pos parameter to search for a shorter string when the last match is not a palindrome.

So in the end my algorithm examines each initial substring of the input string starting with the longest. For each of those it examines the final substrings which begin and end with the same character, again starting with the longest, and returns the longest of those which is a palindrome. The result of the overall program is the longest palindrome from any initial substring.

Here's the code:

  TEXT = <<END
  I'll just type in some example text here and embed a little
  palindrome - A man, a plan, a canal, Panama! - I expect that will be
  the longest palindrome found in this text.
  Lorem ipsum dolor sit amet, consectetur adipiscing elit.
  Integer volutpat lorem imperdiet ante bibendum ullamcorper. Mauris
  tempor hendrerit justo at elementum. Vivamus elit magna, accumsan id
  condimentum a, luctus a ipsum. Donec fermentum, lectus at posuere
  ullamcorper, mauris lectus tincidunt nulla, ut placerat justo odio sed
   odio. Nulla blandit lorem sit amet odio varius nec vestibulum ante
  ornare. Aliquam feugiat, velit a rhoncus rutrum, turpis metus pretium
  dolor, et mattis leo turpis non est. Sed aliquet, sapien quis
  consequat condimentum, sem magna ornare ligula, id blandit odio nisl
  vitae erat. Nam vulputate tincidunt quam, non lacinia risus tincidunt
  lacinia. Aenean fermentum tristique porttitor. Nam id dolor a eros
  accumsan imperdiet. Aliquam quis nibh et dui ultricies cursus. Nunc
  et ante non sapien vehicula rutrum. Duis posuere dictum blandit. Nunc
  vitae tempus purus.
  END

  def clean(str)
    str.gsub(/[^A-Za-z]/,'').downcase
  end

  class String
    def palindrome?
      self == self.reverse
    end

    def longest_palindrome_at_end
      first_possible_start = 0
      end_match_regexp = /#{self[-1]}/
      palindrome = nil
      while (palindrome.nil? && (candidate_start = self.match(end_match_regexp, first_possible_start)))
        candidate_index = candidate_start.begin(0)
        candidate = self[candidate_index..-1]
        if candidate.palindrome?
          palindrome = candidate
        else
          first_possible_start = candidate_index + 1
        end
      end
      palindrome || ""
    end

    def longest_palindrome
      longest = ""
      self.size.downto(1) do |last|
        break if last < longest.size
        candidate = self[0,last].longest_palindrome_at_end
        longest = candidate if candidate.size > longest.size
      end
      longest
    end
  end

  require 'benchmark'

  double = TEXT + TEXT

  puts Benchmark.measure {puts clean(TEXT).longest_palindrome}
  puts Benchmark.measure {puts clean(double).longest_palindrome}

And here's the output:

  amanaplanacanalpanama
    0.110000   0.000000   0.110000 (  0.110347)
  amanaplanacanalpanama
    0.470000   0.000000   0.470000 (  0.463541)

Now my MacBook Pro is a little newer than Brian's, it's a late 2009 model, with a 2.66 GHz Core 2 Duo. But my version is 36x faster (.11 vs. 4 seconds) than Brian's Haskell program, and 891x faster than his Ruby program. Hence the title of this article!