blog dds

2007.06.06

Palindromic Palindrome Checking

Stan Kelly-Bootle's column in the April 2007 ACM Queue, titled Ode or Code? — Programmers Be Mused!, was as always very enjoyable. However, I found its ending, a C function that returns true when given a palindromic string (e.g. ABCCBA), anticlimactic. The function given is recursive; I was expecting it to be palindromic. How difficult can it be to write such a function?

The easiest way is to cheat. The original function is

bool is_palindrome(const char *first, const char *last)
{
	if (first < last) {
		if (*first != *last) return false;
		return is_palindrome(++first, --last);
	}
	return true;
}
All we have to do is to write it in a single line, and continue the line with a comment completing the palindrome. Here is the middle part of this approach
is_palindrome(++first, --last);}return true;}//};eurt nruter};)tsal-- ,tsrif++(emordnilap_si

If we disallow comments, the task becomes harder, but not impossible. Here is a palindromic sequence of Perl statements that evaluates to 1 if the Perl variable $_ forms a palindromic string, and to 0 otherwise.

!!q+(_$ qe esrever ralacs)+;;+(scalar reverse eq $_)+q!!

Stan Kelly-Bootle also discusses how Turing or Knuth would be delighted by binary instructions, especially if those formed a palindrome. Here is a palindromic 30-byte sequence representing i386 machine instructions. At the end of this sequence, if the string starting at the memory position pointed by the register SI and ending at DI is a palindrome, AX will be 1, otherwise it will be 0.

FC 31 C0 A6 75 07 4F 4F 39 FE 72 F6 40 EB 0F
0F EB 40 F6 72 FE 39 4F 4F 07 75 A6 C0 31 FC

Try this yourself, and see if you can improve these programs, or if you can write a palindrome checker in your favorite language. The programs should be syntactically correct, self-standing, concise, and, of course, palindromic. Ideally, all parts of the code should contribute to the end-result (the examples above don't fit this criterion). The Byzantines would say: ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ

Read and post comments, or share through   


Creative Commons License Last modified: Wednesday, June 6, 2007 6:43 pm
Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.