Longest palindrome

Via Hacker News, I found the Greplin Programming Challenge, and couldn’t resist trying it in Perl 6. If you’re the sort of person who enjoys that sort of thing, I highly encourage you to stop reading here and go try it yourself!

I’m going to blog about all three challenges one-by-one. I suppose the third will be the most interesting, if for no other reason than my current implementation looks like it will take ~32 hours to run, so I’m probably going to need to find a more clever solution.

Basically, the first challenge is to find the longest palindrome in a string without spaces. As stated, I thought the challenge implied it was case-sensitive; obviously it’s easiest enough to add a call to lc to get a case-insensitive version.

I was pretty sure a naive version would bring Rakudo to its knees, so I tried to be slightly clever. My solution is still O(N^2), but N is the number of occurrences of a given letter rather than the full length of the string, so that’s fairly reasonable.

sub longest-palindrome($string) {
    my @c = $string.comb(/./);
    my %hc;
    for ^ +@c -> $i {
        if %hc{@c[$i]} {
            %hc{@c[$i]}.push($i);
        } else {
            %hc{@c[$i]} = [$i];
        }
    }

    my @candidates := gather for %hc.keys.sort -> $c {
        say "Checking $c";

        my $list = %hc{$c};
        say :$list.perl;
        for $list.list -> $i1 {
            for $list.reverse -> $i2 {
                last if $i2 <= $i1;
                my $j1 = $i1;
                my $j2 = $i2;
                my $candidate = Bool::True;
                while ++$j1 < --$j2 {
                    if @c[$j1] ne @c[$j2] {
                        $candidate = Bool::False;
                        last;
                    }
                }
                if $candidate {
                    say @c[$i1..$i2];
                    take @c[$i1..$i2].join('');
                }
            }
        }
    };

    @candidates.sort({$^a.chars <=> $^b.chars}).perl.say;
}

Basically, my notion was to store all the occurrences of each letter in a hash of arrays, then pair up every two occurrences of the same letter and see if they are a palindrome. This probably isn’t the most elegant solution, nor the fastest, but it was fast enough to get solve the challenge problem in a minute or two, and easy enough to code I could do it in under an hour at three in the morning.

Interestingly, I think there might be a way to solve this using regular expressions…

Update: Moritz has a solution which blows this one out of the water, both much faster and more elegant. (The key idea was using the regex engine to find the center of potential palindromes.) I’ll let him tell you about it

About these ads

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


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: