Sunday, July 1, 2012

Other implementations and solutions

Next year it is 25 years ago since I constructed an algorithm for finding palindromes efficiently. I was 22 years old then, and had just started as a PhD student. I was quite excited about having solved the problem of finding palindromes efficiently, and wrote a scientific paper about it. My excitement wasn't shared by the scientific community though. In the last twenty-five years this paper has been cited less than ten times, and appears at the bottom end of my most cited papers list.

In 2007 we developed the ICFP programming contest. The ICFP programing contest is a very challenging contest, in which thousands of programmers try to show off their programming talents in their programming language of choice. Our contest asked participants to transform the left picture below to the right picture using as few commands as possible. We included a problem related to palindromes in our contest, since this was my pet-problem ever since 1988. After the contest I explained how to solve the palindrome problem efficiently in a blog post.












When some years later I looked at the number of hits the contest pages received, I found that each month, thousands of people are reading the blog message about finding palindromes. Why does this page attract so many visitors?

The palindrome problem is a common question in interviews for jobs for software developers, so the blog post attracts software developers looking for a new job, and preparing themselves for an interview. Another reason the blog post attracts visitors is that I think quite a few people are genuinely interested in the problem and its solution. The concept of palindromes appears in almost all languages, which means that the question of finding palindromes is asked all over the world. The blog post indeed attracts visitors from all over the world. The last 100 (July 1, 2012) visitors come from all continents except Australia.

Many people ask the question of how to find palindromes, but also many people try to answer the question. You can find hundreds of solutions for finding palindromes on the internet. Some of these are variants of my linear-time solution, others are more naive quadratic or sometimes even cubic-time solutions. Below I give the list I found, ordered on the programming language used for the implementation. If there exists a linear-time implementation, I don't list less efficient solutions.

C The same linear-time solution as my blog post.
C++ 1 The same linear-time solution as my blog post. This post has an extensive description of the palindromes in palindromes property, including some pictures which try to explain it.
C++ 2 A C++ implementation of Manacher's algorithm.
C++ 3 The same linear-time solution as my blog post in C++ by Fernando Pelliccioni.
C# As far as I can see, this is a quadratic-time solution.
Factor A cubic-time solution.
F# A quadratic-time solution.
Go A quadratic-time solution, by Lars Björnfot.
Haskell Just as the program for finding palindromes described in my blog post, this blog post describes a linear-time program for finding palindromes in Haskell. The interesting aspect of this solution is that it returns results lazily: as soon as it finds a maximal palindrome, it writes it to the output.
Java 1 A quadratic-time solution.
Java 2 Another quadratic-time solution in Java, by Marcello de Sales.
Java 3 Yet another quadratic-time solution in Java, by Mohit Bhandari.
Matlab A quadratic-time solution, by Lalit Mohan.
PHP 1 As far as I can see this is a quadratic-time solution, by Marc Donaldson.
PHP 2 This is a quadratic- or cubic-time solution, by Joseba Bikandi. You can try it on-line.
Python The same linear-time solution as my blog post, developed by Fred Akalin. This post contains an extensive description of the palindromes in palindromes property too.
R This page describes the interface of functionality for finding palindromes in DNA strings. It doesn't say how efficient the software is.
Ruby 1 A quadratic-time solution, by Matthew Kerry.
Ruby 2 Another quadratic-time solution in Ruby, by Rick DeNatale. The post and the comments mention some more Ruby implementations.
Ruby 3 Yet another quadratic-time solution in Ruby, by Mitchell Fang.
Scheme A quadratic-time solution.
I could only find linear-time implementations for finding palindromes in C, C++, Haskell, and Python. Please let me know if you find better or alternative implementations for finding palindromes. This list easily gets outdated, so please keep me informed.

8 comments:

  1. Professor,
    Is there a way I could mention the programs you have mentioned here on my paper? If so, how would I quote you/your blog?
    Thank you.
    Anjana Ramnath.

    ReplyDelete
  2. How about

    Johan Jeuring. Other implementations and solutions. Blog post on http://finding-palindromes.blogspot.com/, July 22, 2012.

    for the particular blog post, or

    Johan Jeuring. Finding Palindromes -
    Where do palindromes come from, where do they appear, en how do you find them?
    Blog: http://finding-palindromes.blogspot.com/, 2012.

    ReplyDelete
  3. Hi Johan,

    Thanks a lot for the great blog post on longest palindrome. I was wondering if you know where to find an algorithm or more information on picture transforming question you mentioned above. It seems very interesting.

    Thank you,
    Sanka

    ReplyDelete
    Replies
    1. This was the ICFP programming contest we organized in 2007. We wrote a report about it: see

      http://dl.acm.org/authorize?006850

      Delete
    2. Hi Johan,

      Thanks a lot, really appreciate it.

      Sanka

      Delete
  4. Dear Prof. Dr. Johan Jeuring:
    May I take the liberty of writing to you? I am a Japanese amateur math researcher.
    I was wondering if you could show me some major documents on the relationship between palindromes and cellular automata. I would like to prove that no cellular automata rules can produce any kinds of so-called "chaos" or "complex systems". I would like to demonstrate that there are no such things as "chaos" that defies the control of the universe by God, Jesus Christ. Karl Guenter Kroeber: "Ein Esel lese nie," I fail to understand completely.
    Mr. Koiti/Koichi Kimura, B.A.

    ReplyDelete
  5. Dear Mr Koiti,

    The reference I have about cellular automata is:

    Alvy Ray III Smith. Cellular automata complexity trade-offs. Information and Control, 18:466–482, 1971.

    See also `The history of finding palindromes':

    http://www.cs.uu.nl/research/techreps/UU-CS-2013-008.html

    ReplyDelete