views:

4022

answers:

48
+25  Q: 

Palindrome Golf

The goal: Any language. The smallest function which will return whether a string is a palindrome. Here is mine in Python:

R=lambda s:all(a==b for a,b in zip(s,reversed(s)))

50 characters.

The accepted answer will be the current smallest one - this will change as smaller ones are found. Please specify the language your code is in.

+37  A: 

Here's mine; it's written in a domain-specific language I invented, called 'palindrome'.

p

Edit: Less flippant version (i386 asm, AT&T syntax)

xor %eax, %eax
mov %esi, %edi
#cld    not necessary, assume DF=0 as per x86 ABI
repne scasb
scan:
    dec %edi
    cmpsb
    .byte 0x75, 6    #jnz (short) done
    dec %edi
    cmp %esi, %edi
    .byte 0x72, -9    #jb (short) scan
inc %eax
done:

16 bytes, string pointer goes in ESI, result is in EAX.

Menkboy
Why the p, then? you should run the interpreter with the string as an argument
Vinko Vrsalovic
You must be confusing palindrome with palindrome++, which is a related but different language.
Menkboy
Vinko Vrsalovic, you just didn't read documentation of 'palindrome' language. p - asks user for an argument automatically.
aku
hehe yes, I was afraid t his would happen if I said 'any language'
Claudiu
Joe Pineda
@Joe: Yeah, it's AT the only assembler I had to hand was GNU's as. I have to clear EAX so the rep scasb works, and then to provide the result value for one of the two possible outcomes.
Menkboy
cciotti
17 bytes, nice! Haskell still wins by 1 byte, but yours has the advantage of... not needing a haskell interpreter.
Claudiu
+2  A: 

My attempt in C (70 chars):

P(char*s){char*e=s+strlen(s)-1;while(s<e&&*s==*e)s++,e--;return s>=e;}

[Edit] Now actually working
[Edit 2] Reduced from 74 to 70 by using default int return

In response to some of the comments: I'm not sure if that preprocessor abuse counts - you could just define the whole thing on the command line and make the function one character.

Adam Rosenfield
You can reduce that to ...well, I counted 72 including a newline.int P(char*s){char*e=s+strlen(s)-1;while(s<ereturn s>=e;}Tested on strings "xyx","xyzx""xyyx""yxx".
Jonathan Leffler
And, of course, you can reduce that to:i P(c*s){c*e=s+l(s)-1;w(s<er s>=e;}The compiler command line (gcc) is:gcc -Di=int -Dc=char -Dl=strlen -Dw=while -Dr=return palindrome.c
Jonathan Leffler
@Jonathan: that fails for the strings "ab" and "abb".
Adam Rosenfield
@Adam: OK; that was why I listed the test cases (which did work), in case I was missing the ones that didn't work. Thanks! (And sorry!)
Jonathan Leffler
Three characters saved: `P(char*s){char*e=s;while(*++e);while(s<=--ereturn s>e;}`, but cannot call `P()` with empty string. And no need for `<string.h>` :)
pmg
+24  A: 

Another python version that is rather shorter (21 chars):

R=lambda s:s==s[::-1]
mhawke
Wow, I don't know Python, but that's quite impressive.
harpo
This is great!!!!
Casey
+9  A: 

Perl (27 chars):

sub p{$_[0]eq reverse$_[0]}

Ruby (24 chars):

def p(a)a==a.reverse end
Robert Gamble
You wasted two chars on the parentheses for reverse...And well done; my initial attempt in Perl was 39.
Jonathan Leffler
Good catch, I'll fix that, thanks.
Robert Gamble
This Perl variant has gone too far. Counter-example:sub p{$_ eq reverse}while (<>){ chomp; $x = $_; $_ = "aaaaaaaab"; print "$x is a palindrome\n" if p($x);}
Jonathan Leffler
@Jonathan, thanks for the correction, the 20 char version is simply wrong.
Robert Gamble
@_[0] happens to work here, but is a clear sign of somebody who doesn't understand Perl's sigils; also, I just answered with a 24-character Perl solution.
ephemient
@ephemient, thanks for pointing that out, I'm surprised nobody noticed it sooner.
Robert Gamble
In Ruby 1.9, you can make it a proc `->(e){e.reverse==e}`, but I don't know if its considered as a "function" (I guess it does)
Chubas
+8  A: 

73 clean, readable, chars written in java

boolean p(String s){return s.equals(""+new StringBuffer(s).reverse());}

peace :)

OscarRyz
Since it is so readable, how come the presence of the ""+ in there? If you want readable, I recommend the Haskell solution
1800 INFORMATION
We're talking code-golf here. Readability is irrelevant.
JesperE
a reminder: downvoting is for "unhelpful" answers (read the tooltip!); this was both correct and helpful. Please downvote responsibly. +1 to cancel a thoughtless drive-by downvoting punk
Steven A. Lowe
an upvote much more than cancels a downvote though.
wnoise
No it doesn't, this is a comwiki answer. :P
eyelidlessness
My downvote was neither thoughtless nor driveby. I left a comment to explain it
1800 INFORMATION
+2  A: 
(equal p (reverse p))

lisp. 18 characters.

ok, this is a special case. This would work if typed directly into a lisp interpreter and p was already defined.

otherwise, this would be necessary:

(defun g () (equal p (reverse p)))

28 characters.

contagious
Not fair :)You have to add (defun ....) and count it in
ADEpt
Second that ADEpt - where is your defun?
mhawke
Missing param without which it doesn't work (at least in SBCL) which leaves us with "(defun g (p) (equal p (reverse p)))" (35 characters (your 28 is actually 34). You can get it down to 32 by removing unnecessary whitespace: "(defun g(p)(equal p(reverse p)))". All require p to be a string.
John
No, they don't. `reverse` works on any sequence, `equal` works on strings, bit vectors, and conses (lists), among others that are not interesting with respect to a palindrome.
Svante
Since Common Lisp is a lisp-2, you could write it like this: `(defun p(p)(equal p(reverse p)))` :o)
Svante
+28  A: 

Haskell, 15 chars:

p=ap(==)reverse

More readable version, 16 chars:

p x=x==reverse x
ADEpt
As it is, this has same # of chars as the perl, but doing "p x=x==reverse x" is 16 chars (take out the whitespace). modify your answer if you can
Claudiu
+2  A: 

PHP:

function p($s){return $s==strrev($s);} // 38 chars

or, just

$s==strrev($s); // 15 chars
Henrik Paul
the 15 chars would work but it needs to be in a function def
Claudiu
A: 

CFScript, 39 characters:

function y(x){return(x is reverse(x));}

I was never very good at golf.

Dave DuPlantis
A: 

Java:

boolean y(StringBuffer x){return x.equals(x.reverse());}

The above doesn't work, oops!

boolean y(StringBuffer x){return x.toString().equals(x.reverse().toString()); }

Ew.

Josh
You can always do ""+x instead of x.toString() but that's not really too much better.
MatrixFrog
+1  A: 

Haskell, 28 chars, needs Control.Arrow imported.

p=uncurry(==).(id&&&reverse)
haskell is bizarre to me still. i'll figure it out, though! as it is now the other haskell is shorter than this one, though
Claudiu
Well, than you will have to add that import line to your code, don't you?
Svante
+3  A: 

Lua aims more at readability than conciseness, yet does an honest 37 chars:

function p(s)return s==s:reverse()end

variant, just for fun (same size):

p=function(s)return s==s:reverse''end

The JavaScript version is more verbose (55 chars), because it doesn't has a string reverse function:

function p(s){return s==s.split('').reverse().join('')}
PhiLho
I like the JS version.. wouldn't have thought of it that way.
neonski
To be honest, I found this in a JS FAQ, I think it is common idiom, that's why I didn't mentioned it.
PhiLho
+1  A: 

Straightforward implementation in C using standard library functions, inspired by the strlen in the other C answer.

Number of characters: 57

p(char*s){char*r=strdup(s);strrev(r);return strcmp(r,s);}

Confession: I'm being the bad guy by not freeing r here. My current attempt at being good:

p(char*s){char*r=strdup(s);s[0]=strcmp(strrev(r),s);free(r);return s[0];}

brings it to 73 characters; I'm thinking of any ways to do it shorter.

sundar
p(char*s){return strcmp(strrev(strdup(s)),s);} // leaks!
Skizz
Very nice, but I think to be fully correct, you need to not leak memory and to not modify the original string.
Adam Rosenfield
P(char*s){char r[999];strcpy(r,s);return strcmp(strrev(r));} // Doesn't leak, but limited to strings of at most 998 chars
Adam Rosenfield
I don't think strrev is part of the standard c library (it is available on most linux's though). So to be fair, you'd have to include the implementation of strrev.
Evan Teran
+1  A: 

Without using any library functions (because you should really add in the '#include' cost as well), here's a C++ version in 96:

int p(char*a,char*b=0,char*c=0){return c?b<a||p(a+1,--b,c)&&*a==*b:b&&*b?p(a,b+1):p(a,b?b:a,b);}

Skizz

Skizz
In straight C, you're not required to include the prototypes of all functions - if the compiler sees a function call, it assumes it's a __cdecl function that returns int; it can't validate the parameters, though, but it's perfectly legal.
Adam Rosenfield
A: 

Shell-script (sed + tac + tr):

test "`echo $1|sed -e 's/\(.\)/\1\n/g'|tac|tr -d '\n'`" == "$1"
JesperE
+45  A: 

7 characters in J: Not sure if this is the best way, I'm somewhat new to J :)

p=:-:|.

explanation: |. reverses the input. -: compares. the operands are implicit.

p 'radar'
1

p 'moose'
0
Jimmy
Wow, that's cryptic. I can't actually say I've seen a more cryptic language, personally.
The Wicked Flea
The Wicked Flea: Oh, there's far more cryptic, like unlambda, befunge, or INTERCAL. A friend of mine wrote a compiler *to* unlambda...
wnoise
Brainfuck (and gracklefuck: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/7690921145?r=6310971145#6310971145) and whitespace are far more cryptic.
eyelidlessness
well, unlike Brainfuck, befunge, or INTERCAL, J wasn't designed to be cryptic, just terse :)
Jimmy
where do you learn J?
Casey
@Casey I believe http://www.jsoftware.com/ is the place to start. If you're solve any Project Euler problems, look at people's J solutions in there, and they will make your puny readable code look incredibly long-winded. http://projecteuler.net/
MatrixFrog
@wnoise: compiling to an esoteric language isn't too hard. they're very simple, so you just have to set it up properly and recursion handles the rest.
Claudiu
Impressive... but I would hate to write a real program in that language !
Thomas Levesque
@Thomas Writing J is actually a lot of fun. Reading it (even if you wrote it) is the hard part
cobbal
honestly, the parser needs a "english-translation" mode.
Jimmy
+3  A: 

Isn't using the reverse function in your language kind of cheating a bit? I mean, looking at the Ruby solution give as

def p(a)a==a.reverse end

you could easily rewrite that as

def p(a)a==a.r end

and just say that you made an extension method in your code so that "r" called reverse. I'd like to see people post solutions that don't contain calls to other functions. Of course, the string length function should be permitted.

Ruby without reverse - 41 characters

def m(a)a==a.split('').inject{|r,l|l+r}end

VB.Net - 173 Chars

Function P(ByVal S As String) As Boolean
    For i As Integer = 0 To S.Length - 1
     If S(i) <> S(S.Length - i - 1) Then
      Return False
     End If
    Next
    Return True
End Function
Kibbee
you could make it a bit shorter by putting the return false at the end of the if statement and deleting the end if.
osp70
Not, that's not cheating, as long as reverse is part of the standard distribution (but it advantage languages with rich libraries). Note that Lua cannot access individual chars out of strings without library! The extension argument doesn't stand, because the code is supposed to work out of the box.
PhiLho
There are languages where almost the whole standard is usually implemented as functions.
Svante
+2  A: 

C# Without Reverse Function 84 chars

int p(char[]s){int i=0,l=s.Length,t=1;while(++i<l)if(s[i]!=s[l-i-1])t&=0;return t;}

C# Without Reverse Function 86 chars

int p(char[]s){int i=0;int l=s.Length;while(++i<l)if(s[i]!=s[l-i-1])return 0;return 1;}

VBScript 41 chars

function p:p=s=strreverse(s):end function
Terrapin
int p(char[]s){int i=0,l=s.Length,t=1;while(++i<l)if(s[i]!=s[l-i-1])treturn t;}84 chars
Dykam
A: 

Definitely not the smallest, but I still wanted to add a entry:

sub p{return @_==reverse split//;}

My perl's rusty tho and this is untested.

mstrobl
Doesn't work: == forces scalar context, which turns @_ into its length. Not to mention that split operates on $_, not @_.
ephemient
+1  A: 

Groovy 17B:

p={it==it[-1..0]}

Downside is that it doesn't work with emptry string.

On second thought, throwing exception for empty string is reasonable since you can't tell if nothing is palindrome or not.

matyr
An empty string is by definition a palindrome, I think. makes the definition much shorter: <legal> = <empty-string> | <char><legal><char>
Christian Mann
+15  A: 

At the risk of getting down votes, most all of these just call a command reverse of some sort that hides all the real programming logic.

I wonder what the shortest manual way to do this is in each of these languages.

Hugoware
It turns out that is part of the core lib of the platform. Probably a algorithm-golf will do. 1+ though
OscarRyz
i believe in that case the assembly code wins
Claudiu
What about languages with built-in backwards iteration then? technically, python's string[::-1] isn't "built-in reverse"... its much more general.
Jimmy
See my answer to Kibbee. In Lua, you cannot access individual chars of strings without string library!Now, it can be interesting to give two versions (for languages able to do both), the shortest and the shortest algorithmic one, indeed.
PhiLho
+3  A: 

F# (a lot like the C# example)

let p s=let i=0;let l=s.Length;while(++i<l)if(s[i]!=[l-i-1]) 0; 1;;
nyxtom
A: 

Josh's Java snippet above will return true every time.

Thanks for catching the gotcha, I corrected it.
Josh
These remarks, not answering the original request, are better put in comments. With added bonus of notifying the person... :-)
PhiLho
+3  A: 

Pointless Haskell version (15 chars, though doesn't really work unless you include Control.Arrow and Control.Monad and ignore the monomorphism restriction):

p=ap(==)reverse
Steven Dee
where does 'ap' come from here?
Claudiu
It's in Control.Monad, though Control.Arrow is needed to give an instance for (Monad ((->) a). ap can also be written/understood as "ap f g h = f h (g h)", and acts like the S combinator (in the S K I calculus) in this instance. Think of it as applying a function in the environment of another.
Steven Dee
+3  A: 

I'll take it a little bit further: full c code, compile and go.

90 characters

main(int n,char**v){char*b,*e;b=e=v[1];while(*++e);for(e--;*b==*e&&b++<e--;);return b>e;}
Figo
+2  A: 

Common Lisp, short-and-cheating version (23 chars):

#L(equal !1(reverse !1))

#L is a reader macro character implemented by SHARPL-READER in the iterate package. It's basically equivalent to (lambda (!1) ...).

Common Lisp, long version using only primitives (137 including whitespace, compressible down to 108):

(defun p (s)
  (let ((l (1- (length s))))
    (iter (for i from l downto (/ l 2))
          (always (equal (elt s i) (elt s (- l i)))))))

Again, it uses iterate, which is basically a cleaner version of the builtin LOOP facility, so I tend to treat it as being in the core language.

+8  A: 

With C# and LINQ operators:

public bool IsPalindrome(string s)
{
    return s.Reverse().SequenceEqual(s);
}

If you consider Reverse as cheating, you can do the entire thing with a reduction:

public bool IsPalindrome(string s)
{
    return s.Aggregate(new StringBuilder(),
                       (sb, c) => sb.Insert(0, c),
                       (sb) => sb.ToString() == s);
}
OdeToCode
+1, very creative use of Aggregate... But I wouldn't consider Reverse as cheating, since it's a standard Linq operator and almost every other answer used it.
Thomas Levesque
You could write the first one shorter as `s.Reverse().ToString()==s;` and the second as `!s.Where((c,i)=>c!=s[s.Length-i-1]).Any()`
Gabe
+32  A: 
Underflow
hahaha what the hell is that? Maybe I shouldn't look at SOF while drinking.... +1 lol
Casey
LabView is a dataflow language used to program hardware controllers and the like. You are looking at the source code (it's all icons and arrows)
1800 INFORMATION
Btw it is also used in the most geekiest and coolest ever invented toy that exist: LEGO. Legos Mindstorms are programmed in LabView
flolo
LabView is just another attempt to make programming more accessible to non-programmers. It has its uses, maybe as a teaching tool, but I wouldn't use it for serious purposes... (It's not the only way to program LEGO.)
Artelius
...<shrug> http://www.ni.com/solutions. There might be some serious ones in there.
Underflow
Similar dataflow languages are used to program embedded systems.
swegi
+1  A: 

Clojure using 37 characters:

user=> (defn p[s](=(seq s)(reverse(seq s))))
#'user/p
user=> (p "radar")
true
user=> (p "moose")
false
You don't need to call (seq s) within reverse. Also, you can shave off a few chars by using an anonymous function. Since you already have a clojure answer, I'll just stick mine down here. Feel free to steal it. (def p #(=(seq %)(reverse %))) 30 chars.
nilamo
A: 

C, no libraries, 70 characters:

p(char*a){char*b=a-1;while(*++b);while(a<b&&*a++==*--b);return!(a<b);}

As one of the comments on another C solution mentioned, prototypes are completely optional in C, int is assumed everywhere a type would go but isn't mentioned. Has nobody ever programmed in pre-ANSI C?

Edit: shorter and handles empty strings.

ephemient
This doesn't quite work - you need to decrement b one extra time to move before the terminating NUL, which adds an extra 4 characters.
Adam Rosenfield
Ah. I mistyped -- I should have copy'n'pasted from the C file I was testing in. If I replace *b++ with *++b, it works out (as long as the string is nonempty).
ephemient
Well somebody used pre-ANSI C, but he sure didn't recall any of that as being a "feature"!
gbarry
This function fails on non-palindromes of even length where the only differing characters are in the center. Examples: "ab", "abca", "abcdezdcba" — it gives these a false positive.
Deadcode
+1  A: 

24 characters in Perl.

sub p{$_[0][email protected]_}
ephemient
+2  A: 

Inspired by previous post, 69 characters

p(char*a){char*b=a,q=0;while(*++b);while(*a)q|=*a++!=*--b;return!q;}

EDIT: Down one char:

p(char*a){char*b=a,q=0;while(*++b);while(*a)q|=*a++%*--b;return!q;}

EDIT2: 65 chars:

p(char*a){char*b=a;while(*b)b++;while(*a&&*a++==*--b);return!*a;}
Jasper Bekkers
Very nice - the second one _almost_ works, but it fails when you have two characters which are negatives of each other (when char is signed), e.g. the string "\x40\xC0".
Adam Rosenfield
Whether or not the modulo operator can return a negative number is actually implementation defined. Also 0xC0 is not in the ASCII range so it's really not that relevant. It's nice that you actually spotted it though, I didn't.
Jasper Bekkers
Very nice, but note that your function has undefined behavior when passed an empty string. If all the bytes in the string buffer following the initial null are nonzero, and all the bytes following the string buffer are nonzero up to the end of mapped memory, the `while(*++b);` will crash accessing unmapped memory. I'm not sure if there are any implementations in which this can happen, but fixing it costs one character: `while(*b)++b;` Since it's currently 64 chars (not 65), that'd bring it up to 65 chars.
Deadcode
@Deadcode thanks for the fix!
Jasper Bekkers
A: 

JavaScript: 55 chars

p=function(x){return (x==x.split('').reverse().join())}

The above won't work because you need to call join with ""

JavaScript: 55 chars

function p(s){return s==s.split("").reverse().join("")}
scunliffe
A: 

Java, without using reverse:

boolean p(String s){int i=0,l=s.length();while(i<l){if(s.charAt(i++)!=s.charAt(--l))l=-1;}return l>=0;
Skip Head
A: 

Standard ML (34 characters and boring):

fun p s=s=implode(rev(explode(s)))
bk1e
A: 

C, 68 characters, no libs:

p(char *s){char *e=s;while(*++e);for(;*s==*--e&&s++<e;);return s>e;}
+2  A: 

Not the shortest, and very after-the-fact, but I couldn't help giving it a try in MATLAB:

[email protected](s)all(s==fliplr(s));

24 chars.

gnovice
A: 

may was well give a c++ example which uses the standard library:

bool p(const std::string &s){std::string s2(s);std::reverse(s2);return s==s2;}

Thanks to Jon For pointing out that this could be shorter if we make some unnecessary copies. Totalling 67 chars.

bool p(std::string s){std::string x=s;std::reverse(x);return s==x;}
Evan Teran
How about `int p(std::string s){std::string t(s);std::reverse(t);return s==t;}` (67), or `int p(std::string s){return std::equal(s.begin(),s.end(),s.rbegin());}` (70)? C++0x lets you reduce the former from `std::string t` to `auto t`, for a savings of seven characters.
Jon Purdy
+1  A: 

Haskell, 36 characters including its own reverse function. (Actually, if you use semicolons to make it a one-liner, and ignore the newline at the end, it'd be 35...)

r[]y=y
r(a:x)y=r x$a:y
p s=s==r s[]

As with other implementations, "p" is the palindrome predicate.

A: 

58 characters in Python, without reversing the string:

r="y"
for i in range(len(s)):
 if(s[i]!=s[-i-1]):
  r="n"

Maybe the for loop could be optimized? Python is new to me...

Daniel
A: 

18 character perl regex

/^(.?|(.)(?1)\2)$/
Eric Strom
A: 

52 characters in C, with the caveat that up to half the string will be overwritten:

p(char*s){return!*s||!(s[strlen(s)-1]-=*s)&&p(++s);}

Without library calls it's 64 characters:

p(char*s){char*e=s;while(*e)++e;return!*s||!(*--e-=*s)&&p(++s);}

Deadcode
A: 

Perl (21 characters):

sub{"@_"eq [email protected]_}

Hey, the question didn't specify a named subroutine!

Sean
A: 

javascript recursive version (no reverse junk)

function p(s){l=s.length;return l<2||(s[0]==s[l-1]&&p(s.substr(1,l-2)))}

(72 chars)

or implement reverse inside:

p=function(s,y){return y?(s==p(s)):s[1]?(p(s.substr(1))+s[0]):s[0]}

p("hannah",1);

(67 chars)

or, using no built in functions at all...

p=function(s,y,i){
return i?s[i]?s[i]+p(s,0,i+1):'':y?(s==p(s)):s[1]?(p(p(s,0,1))+s[0]):s[0]
}

p("hannah",1);

(92 chars)

shortest I could come up with: (iterative)

function p(s,l){for(c in s){if(s[c]!=s[l-1-c])s=0}return s}

p("hannah",6);// (is this cheating?)

(59 chars)

looking forward to seeing you do it better in javascript!

(preferably without using any built in functions, especially reverse)

(not really very impressed by the 'return s==s.reverse()' type answers)

FishyFingers
+3  A: 

Golfscript, 5 char

.-1%=

$ echo -n abacaba | ruby golfscript.rb palindrome.gs
1

$ echo -n deadbeef | ruby golfscript.rb palindrome.gs
0
mobrule
A: 

F#: 29 chars

let p(s:string)=s=s.Reverse()

(assuming System.Linq is imported)

Thomas Levesque
A: 

C# using a recursive lambda function and not using the Reverse function (115 chars):

Func<string,bool>p=null;p=w=>{if(w.Length<2)return true;return w[0]==w[w.Length-1]&&p(w.Substring(1,w.Length-2));};
Ray Vega
A: 

Impossible! language, assuming that string is passed by using normal args:

;~=

3 chars

Jack