(archive 'newLISPer)

October 9, 2010

egnellahC nilperG ehT

Filed under: newLISP — newlisper @ 22:19
Tags:

I spent a happy half hour today trying to take the Greplin Challenge.

Unfortunately, I managed to complete only the first level. It wasn’t so much that the problem was hard. It was more that I couldn’t find an elegant solution that satisfied me.

The problem is to find the longest substring of a string that is the same in reverse. In other words, to find the longest palindrome.

Here’s my attempt. If the string is in ‘source-string’:

    (for (character 0 (dec (length source-string)))
            (set 'end-of-word
                    (find (source-string character) source-string nil
                            (+ character 1)))

            (when end-of-word
                    (set 'word (slice source-string character
                                    (+ 1 (- end-of-word character))))
                    (when (= (lower-case word)
                                    (reverse (lower-case word)))
                            (push word palindromes))))

    (first (sort palindromes
                    (fn (a b) (> (length a ) (length b)))))

As you can see, it’s not exactly a one-liner. But at least it avoids a completely ‘brute-force’ technique. It looks for likely palindromes rather than testing every possible substring. Apart from that, it just puts all the palindromes in a list and finds the longest later. I’m sure you can produce a more elegant solution!

It might be a few days before I get round to level 2. But don’t wait for me – have a go!

Update

I realised later that this algorithm isn’t very good. Yes, it finds the correct answer for the particular test case on the Greplin challenge, but it doesn’t always find the longest palindrome. For example, if the string contains the substring “hahah”, then the longest palindrome found will be “hah” rather than “hahah”. That’s because I used find to locate the matching end character for each start character. To obtain more accurate results, I’d need to check for every subsequent matching end character in the rest of the string, not just the next one.

Now a brute force technique starts to look attractive. Instead of being intelligent and looking for a prospective end character for each start character, let’s just try every possible substring and test it for palindromicity. Hammer time! Yes, it’s painful to write such brutal code, but sometimes it’s just easier:

(for (begin-char 0 (- (length source-string) 2))
        (for (end-char begin-char (dec (length source-string)))
                (set 'word (slice source-string begin-char 
                    (+ 2 (- end-char begin-char))))
                (when  (= (lower-case word) (reverse (lower-case word)))    
                        (push word palindromes))))
(first
        (sort palindromes
                (fn (a b) (> (length a ) (length b)))))

Finally, a teaser for you. Notice those two lower-case functions? What would happen if you factored them out and placed a single call to it in the line above?

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: