Bonsai Code

In today’s Programming Praxis exercise, our goal is to write an alogrithm to find the longest palindrome in a string. Let’s get started, shall we?

Some imports:

import qualified Data.ByteString.Char8 as B
import qualified Data.List.Key as K

Since the exercise is originally part of a group of 3 that is supposed to be completed in 20 minutes to 2 hours, I’m going to assume I don’t have time to figure out a fancy but complicated suffix trie-based approach. Below is the version I wrote in a minute or two, with two modifications:

1. The list comprehensions was originally a filter and a concatMap. Same thing, but different syntax. I like this version better.
2. The original worked on plain strings and ran in 8 seconds or so. Switching to ByteStrings speeds things up quite a bit and is trivial to do, requiring only a few additions of “B.”.

The algorithm is pretty trivial: get every possible substring, check if it’s a palindrome and return the longest one.

longestPalindrome :: B.ByteString -> B.ByteString
longestPalindrome s = K.maximum B.length
 [p | p <- B.inits =<< B.tails s, p == B.reverse p]

We test the algorithm on the Gettysburg Address.

gettysburg :: B.ByteString
gettysburg = B.pack
 "Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta\
 \inentanewnationconceivedinzLibertyanddedicatedtotheproposit\
 \ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa\
 \rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic\
 \atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh\
 \avecometodedicpateaportionofthatfieldasafinalrestingplacefo\
 \rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog\
 \etherfangandproperthatweshoulddothisButinalargersensewecann\
 \otdedicatewecannotconsecratewecannothallowthisgroundThebrav\
 \elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove\
 \ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl\
 \ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI\
 \tisforusthelivingrathertobededicatedheretotheulnfinishedwor\
 \kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather\
 \forustobeherededicatedtothegreattdafskremainingbeforeusthat\
 \fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh\
 \ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres\
 \olvethatthesedeadshallnothavediedinvainthatthisnationunsder\
 \Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb\
 \ythepeopleforthepeopleshallnotperishfromtheearth"
main :: IO ()
main = B.putStrLn $ longestPalindrome gettysburg

As expected, we get ranynar as the answer. Sure, it’s an O(n³) algorithm, but since this is a fairly short text it doesn’t matter all that much, as evidenced by the half-second running time. If you’re working with longer inputs, use a different algorithm.

Tags: bonsai, code, Haskell, kata, longest, palindrome, praxis, programming

This entry was posted on October 15, 2010 at 2:17 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.