Palindrome detection
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Write at least one function/method (or whatever it is called in your preferred language) to check if a sequence of characters (or bytes) is a palindrome or not. The function must return a boolean value (or something that can be used as boolean value, like an integer).
It is not mandatory to write also an example code that uses the function, unless its usage could be not clear (e.g. the provided recursive C solution needs explanation on how to call the function).
It is not mandatory to handle properly encodings (see String length), i.e. it is admissible that the function does not recognize 'salàlas' as palindrome.
The function must not ignore spaces and punctuations. The compliance to the aforementioned, strict or not, requirements completes the task.
An example of latin palindrome is the sentence "In girum imus nocte et consumimur igni", roughly translated as: we walk around in the night and we are burnt by the fire (of love). To do your test with it, you must make it all the same case and strip spaces.
It might be useful for this task to know how to reverse a string.
ActionScript
The following function handles non-ASCII characters properly, since charAt() returns a single Unicode character. <lang ActionScript>function isPalindrome(str:String):Boolean { for(var first:uint = 0, second:uint = str.length - 1; first < second; first++, second--) if(str.charAt(first) != str.charAt(second)) return false; return true; }</lang>
Ada
<lang ada>function Palindrome (Text : String) return Boolean is begin
for Offset in 0..Text'Length / 2 - 1 loop if Text (Text'First + Offset) /= Text (Text'Last - Offset) then return False; end if; end loop; return True;
end Palindrome;</lang>
ALGOL 68
<lang algol68># Iterative # PROC palindrome = (STRING s)BOOL:(
FOR i TO UPB s OVER 2 DO IF s[i] /= s[UPB s-i+1] THEN GO TO return false FI OD; else: TRUE EXIT return false: FALSE
);
- Recursive #
PROC palindrome r = (STRING s)BOOL:
IF LWB s >= UPB s THEN TRUE ELIF s[LWB s] /= s[UPB s] THEN FALSE ELSE palindrome r(s[LWB s+1:UPB s-1]) FI
- Test #
main: (
STRING t = "ingirumimusnocteetconsumimurigni"; FORMAT template = $"sequence """g""" "b("is","isnt")" a palindrome"l$; printf((template, t, palindrome(t))); printf((template, t, palindrome r(t)))
)</lang> Output:
sequence "ingirumimusnocteetconsumimurigni" is a palindrome sequence "ingirumimusnocteetconsumimurigni" is a palindrome
AutoHotkey
<lang AutoHotkey>MsgBox % isPalindrome("in girum imus nocte et consumimur igni") ; returns 1 for true
isPalindrome(str) {
str := RegexReplace(str, "\W+") If (StrLen(str) < 2) ; single character strings are palindromes Return true Else If (SubStr(str, 1, 1) = SubStr(str, 0, 1)) ; if the first character Return isPalindrome(SubStr(str, 2, -1)) ; is same as last character, recurse Else Return false
}</lang>
AWK
Non-recursive
See Reversing a string.
<lang awk>function is_palindro(s) {
if ( s == reverse(s) ) return 1; return 0
}</lang>
Recursive
<lang awk>function is_palindro_r(s) {
if ( length(s) < 2 ) return 1; if ( substr(s, 1, 1) != substr(s, length(s), 1) ) return 0; return is_palindro_r(substr(s, 2, length(s)-2))
}</lang>
Testing <lang awk>BEGIN {
pal = "ingirumimusnocteetconsumimurigni" print is_palindro(pal) print is_palindro_r(pal)
}</lang>
BASIC
<lang qbasic>DECLARE FUNCTION isPalindrome% (what AS STRING)
DATA "My dog has fleas", "Madam, I'm Adam.", "1 on 1", "In girum imus nocte et consumimur igni"
DIM L1 AS INTEGER, w AS STRING FOR L1 = 1 TO 4
READ w IF isPalindrome(w) THEN PRINT CHR$(34); w; CHR$(34); " is a palindrome" ELSE PRINT CHR$(34); w; CHR$(34); " is not a palindrome" END IF
NEXT
FUNCTION isPalindrome% (what AS STRING)
DIM whatcopy AS STRING, chk AS STRING, tmp AS STRING * 1, L0 AS INTEGER
FOR L0 = 1 TO LEN(what) tmp = UCASE$(MID$(what, L0, 1)) SELECT CASE tmp CASE "A" TO "Z" whatcopy = whatcopy + tmp chk = tmp + chk CASE "0" TO "9" PRINT "Numbers are cheating! ("; CHR$(34); what; CHR$(34); ")" isPalindrome = 0 EXIT FUNCTION END SELECT NEXT
isPalindrome = ((whatcopy) = chk)
END FUNCTION</lang>
Output:
"My dog has fleas" is not a palindrome "Madam, I'm Adam." is a palindrome Numbers are cheating! ("1 on 1") "1 on 1" is not a palindrome "In girum imus nocte et consumimur igni" is a palindrome
Befunge
To check a string, replace "dennis sinned" with your own string.
Note that this has some limits.:
- There must be a quotation mark immediately after the string, and then nothing but spaces for the rest of that line.
- The v at the end of that same line must remain immediately above the 2. (Very important.) The closing quotation mark can be against the v, but can't replace it.
- The potential palindrome can be no longer than 76 characters (which beats the previous version's 11), and everything (spaces, punctuation, capitalization, etc.) is considered part of the palindrome. (Best to just use lower case letters and nothing else.)
<lang befunge>v> "emordnilap a toN",,,,,,,,,,,,,,,,@,,,,,,,,,,,,,,,"Is a palindrome" < 2^ < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < 4 ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v 8 ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v # ^_v
- ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v ^_v
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
>"dennis sinned" v
" 2 """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 0
> ^- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 9
_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ p v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ # v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ v_^ ^< < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < >09g8p09g1+09pv |: < <
^<</lang>
C
Non-recursive
This function compares the first char with the last, the second with the one previous the last, and so on. The first different pair it finds, return 0 (false); if all the pairs were equal, then return 1 (true). You only need to go up to (the length) / 2 because the second half just re-checks the same stuff as the first half; and if the length is odd, the middle doesn't need to be checked (so it's okay to do integer division by 2, which rounds down).
<lang c>#include <string.h>
int palindrome(const char *s) {
int i,l; l = strlen(s); for(i=0; i<l/2; i++) { if ( s[i] != s[l-i-1] ) return 0; } return 1;
}</lang> More idiomatic version: <lang c>int palindrome(const char *s) {
const char *t; /* t is a pointer that traverses backwards from the end */ for (t = s; *t != '\0'; t++) ; t--; /* set t to point to last character */ while (s < t) { if ( *s++ != *t-- ) return 0; } return 1;
}</lang>
Recursive
A single char is surely a palindrome; a string is a palindrome if first and last char are the same and the remaining string (the string starting from the second char and ending to the char preceding the last one) is itself a palindrome.
<lang c>int palindrome_r(const char *s, int b, int e) {
if ( e <= 1 ) return 1; if ( s[b] != s[e-1] ) return 0; return palindrome_r(s, b+1, e-1);
}</lang>
Testing
<lang c>#include <stdio.h>
- include <string.h>
/* testing */ int main() {
const char *t = "ingirumimusnocteetconsumimurigni"; const char *template = "sequence \"%s\" is%s palindrome\n"; int l = strlen(t); printf(template, t, palindrome(t) ? "" : "n't"); printf(template, t, palindrome_r(t, 0, l) ? "" : "n't"); return 0;
}</lang>
C++
The C solutions also work in C++, but C++ allows a simpler one: <lang cpp>#include <string>
- include <algorithm>
bool is_palindrome(std::string const& s) {
return std::equal(s.begin(), s.end(), s.rbegin());
}</lang>
C#
Non-recursive
<lang csharp>using System;
class Program {
static string Reverse(string value) { char[] chars = value.ToCharArray(); Array.Reverse(chars); return new string(chars); }
static bool IsPalindrome(string value) { return value == reverse(value); }
static void Main(string[] args) { Console.WriteLine(IsPalindrome("ingirumimusnocteetconsumimurigni")); }
}</lang>
Clojure
<lang clojure>(defn palindrome? [s]
(= s (apply str (reverse s))))</lang>
Recursive <lang clojure>(defn palindrome? [s]
(loop [i 0 j (dec (. s length))] (cond (>= i j) true (= (get s i) (get s j)) (recur (inc i) (dec j)) :else false)))</lang>
Test
user=> (palindrome? "amanaplanacanalpanama") true user=> (palindrome? "Test 1, 2, 3") false
Common Lisp
<lang lisp>(defun palindrome-p (s)
(string= s (reverse s)))</lang>
D
Hi-level ASCII version: <lang d>bool isPalindrome1(string s) {
return s == s.dup.reverse;
}</lang>
Low-level ASCII version: <lang d>bool isPalindrome2(string str) {
char* s = str.ptr; char* t = &str[$-1]; while (s < t) if (*s++ != *t--) return false; return true;
}</lang>
Mid-level 32-bit Unicode version: <lang d>bool isPalindrome3(T)(T[] s) {
dchar[] dstr; foreach (dchar c; s) dstr ~= c;
for (int i; i < dstr.length / 2; i++) if (dstr[i] != dstr[$ - i - 1]) return false; return true;
}</lang>
E
It is only necessarily to scan the first half of the string, upper(0, upper.size() // 2)
, and compare each character to the corresponding character from the other end, upper[last - i]
.
The for loop syntax is for key pattern => value pattern in collection { ... }
, ?
imposes an additional boolean condition on a pattern (it may be read “such that”), and if the pattern does not match in a for loop then the iteration is skipped, so false is returned only if upper[last - i] != c
.
<lang e>def isPalindrome(string :String) {
def upper := string.toUpperCase() def last := upper.size() - 1 for i => c ? (upper[last - i] != c) in upper(0, upper.size() // 2) { return false } return true
}</lang>
Erlang
<lang erlang>is_palindrome(String) ->
String == lists:reverse(String).</lang>
F#
Forall2 applies the predicate to each member of the two arrays, until it finds a false or it reaches the end. <lang fsharp>let isPalindrome (s: string) =
let arr = s.ToCharArray() Array.forall2 (fun a b -> a = b) ( arr ) ( Array.rev ( arr ) )</lang>
Examples: <lang fsharp>isPalindrome "abcba" val it : bool = true isPalindrome ("In girum imus nocte et consumimur igni".Replace(" ", "").ToLower());; val it : bool = true isPalindrome "abcdef" val it : bool = false</lang>
Factor
<lang factor>USING: kernel sequences ;
- palindrome? ( str -- ? ) dup reverse = ;</lang>
Forth
<lang forth>: palindrome? ( caddr len -- ? )
1- bounds begin 2dup > while over c@ over c@ = while 1+ swap 1- swap repeat 2drop false else 2drop true then ;</lang>
Fortran
(The integer source is artificially split: the functions are contained into the test program palindro)
<lang fortran>program palindro
implicit none
character(len=*), parameter :: p = "ingirumimusnocteetconsumimurigni" print *, is_palindro_r(p) print *, is_palindro_r("anothertest") print *, is_palindro2(p) print *, is_palindro2("test") print *, is_palindro(p) print *, is_palindro("last test")
contains</lang>
Non-recursive
<lang fortran>! non-recursive function is_palindro(t)
logical :: is_palindro character(len=*), intent(in) :: t
integer :: i, l
l = len(t) is_palindro = .false. do i=1, l/2 if ( t(i:i) /= t(l-i+1:l-i+1) ) return end do is_palindro = .true.
end function is_palindro
! non-recursive 2 function is_palindro2(t) result(isp)
logical :: isp character(len=*), intent(in) :: t
character(len=len(t)) :: s integer :: i
forall(i=1:len(t)) s(len(t)-i+1:len(t)-i+1) = t(i:i) isp = ( s == t )
end function is_palindro2</lang>
Recursive <lang fortran>! recursive recursive function is_palindro_r(t) result(isp)
logical :: isp character(len=*), intent(in) :: t
isp = .true. if ( len(t) == 1 ) return if ( (len(t) == 2) ) then if ( t(1:1) == t(2:2) ) return else isp = .false. if ( t(1:1) == t(len(t):len(t)) ) isp = is_palindro_r( t(2:len(t)-1) ) end if
end function is_palindro_r</lang>
<lang fortran>end program palindro</lang>
Groovy
Trivial
Solution: <lang groovy>def isPalindrome = { String s ->
s == s?.reverse()
}</lang>
Test program: <lang groovy>println isPalindrome("") println isPalindrome("a") println isPalindrome("abcdefgfedcba") println isPalindrome("abcdeffedcba") println isPalindrome("abcedfgfedcb")</lang>
Output:
true true true true false
This solution assumes nulls are palindromes.
Non-recursive
Solution: <lang groovy>def isPalindrome = { String s ->
def n = s.size() n < 2 || s[0..<n/2] == s[-1..(-n/2)]
}</lang>
Test program and output are the same. This solution does not handle nulls.
Recursive
Solution follows the C palindrome_r recursive solution: <lang groovy>def isPalindrome isPalindrome = { String s ->
def n = s.size() n < 2 || (s[0] == s[n-1] && isPalindrome(s[1..<(n-1)]))
}</lang>
Test program and output are the same. This solution does not handle nulls.
Haskell
Non-recursive
A string is a palindrome if reversing it we obtain the same string.
<lang haskell>is_palindrome x = x == reverse x</lang>
Recursive
See the C palindrome_r code for an explanation of the concept used in this solution.
<lang haskell>is_palindrome_r x | length x <= 1 = True
| head x == last x = is_palindrome_r . tail. init $ x | otherwise = False</lang>
HicEst
<lang hicest> result = Palindrome( "In girum imus nocte et consumimur igni" ) ! returns 1 END
FUNCTION Palindrome(string)
CHARACTER string, CopyOfString
L = LEN(string) ALLOCATE(CopyOfString, L) CopyOfString = string EDIT(Text=CopyOfString, UpperCase=L) L = L - EDIT(Text=CopyOfString, End, Left=' ', Delete, DO=L) ! EDIT returns number of deleted spaces DO i = 1, L/2 Palindrome = CopyOfString(i) == CopyOfString(L - i + 1) IF( Palindrome == 0 ) RETURN ENDDO
END</lang>
Icon and Unicon
Icon
<lang Icon>procedure main(arglist) every writes(s := !arglist) do write( if palindrome(s) then " is " else " is not", " a palindrome.") end</lang>
The following simple procedure uses the built-in reverse. Reverse creates a transient string which will get garbage collected. <lang Icon>procedure palindrome(s) #: return s if s is a palindrome return s == reverse(s) end</lang>
Note: The IPL procedure strings contains a palindrome tester called ispal that uses reverse and is equivalent to the version of palindrome above.
This version use positive and negative sub-scripting and works not only on strings but lists of strings, such as ["ab","ab"] or ["ab","x"] the first list would pass the test but the second wouldn't. <lang Icon>procedure palindrome(x) #: return x if s is x palindrome local i every if x[i := 1 to (*x+ 1)/2] ~== x[-i] then fail return x end</lang>
Unicon
This Icon solution works in Unicon.
Ioke
<lang ioke>Text isPalindrome? = method(self chars == self chars reverse)</lang>
J
Non-recursive
Reverse and match method <lang j>isPalin0=: -: |.</lang> Example usage <lang j> isPalin0 'ABBA' 1
isPalin0 ;;: tolower 'In girum imus nocte et consumimur igni'
1</lang>
Recursive
Tacit and explicit verbs: <lang j>isPalin1=: 0:`($:@(}.@}:))@.({.={:)`1:@.(1>:#)
isPalin2=: monad define
if. 1>:#y do. 1 return. end. if. ({.={:)y do. isPalin2 }.}:y else. 0 end.
)</lang>
Java
Non-Recursive
<lang java>public static boolean pali(String testMe){ StringBuilder sb = new StringBuilder(testMe); return testMe.equalsIgnoreCase(sb.reverse().toString()); }</lang> Recursive
<lang java>public static boolean rPali(String testMe){ if(testMe.length()<=1){ return true; } if(!(testMe.charAt(0)+"").equalsIgnoreCase(testMe.charAt(testMe.length()-1)+"")){ return false; } return rPali(testMe.substring(1, testMe.length()-1)); }</lang>
JavaScript
<lang javascript>String.prototype.reverse = function(){ return this.split("").reverse().join(""); }
function palindrome(str) { return str == str.reverse(); }
alert(palindrome("ingirumimusnocteetconsumimurigni"));</lang>
<lang javascript>String.prototype.reverse = function () {
return this.split().reverse().join();
};
String.prototype.isPalindrome = function () {
var s = this.toLowerCase().replace(/[^a-z]/g, ); return (s.reverse() === s);
};
('A man, a plan, a canoe, pasta, heros, rajahs, ' + 'a coloratura, maps, snipe, percale, macaroni, ' + 'a gag, a banana bag, a tan, a tag, ' + 'a banana bag again (or a camel), a crepe, pins, ' + 'Spam, a rut, a Rolo, cash, a jar, sore hats, ' + 'a peon, a canal – Panama!').isPalindrome();</lang>
Logo
<lang logo>to palindrome? :w
output equal? :w reverse :w
end</lang>
Lua
<lang lua>function ispalindrome(s) return s == string.reverse(s) end</lang>
M4
Non-recursive
This uses the invert
from Reversing a string.
<lang m4>define(`palindrorev',`ifelse(`$1',invert(`$1'),`yes',`no')')dnl
palindrorev(`ingirumimusnocteetconsumimurigni')
palindrorev(`this is not palindrome')</lang>
Recursive
<lang m4>define(`striptwo',`substr(`$1',1,eval(len(`$1')-2))')dnl define(`cmplast',`ifelse(`striptwo(`$1')',,`yes',dnl substr(`$1',0,1),substr(`$1',eval(len(`$1')-1),1),`yes',`no')')dnl define(`palindro',`dnl ifelse(eval(len(`$1')<1),1,`yes',cmplast(`$1'),`yes',`palindro(striptwo(`$1'))',`no')')dnl palindro(`ingirumimusnocteetconsumimurigni') palindro(`this is not palindrome')</lang>
Mathematica
Custom functions:
Non-recursive
<lang Mathematica>PalindromeQ[i_String] := StringReverse[i] == i</lang>
Recursive
<lang Mathematica>PalindromeRecQ[str_String] := If[
Length[Characters[str]] <= 1, True, If[Characters[str]1 == Characters[str][[Length[Characters[str]]]], PalindromeRecQ[ StringJoin[Take[Characters[str], {2, Length[Characters[str]] - 1}]] ], False ] ]</lang>
Examples: <lang Mathematica>PalindromeQ["TNT"] PalindromeRecQ["TNT"] PalindromeQ["test"] PalindromeRecQ["test"] PalindromeQ["deified"] PalindromeRecQ["deified"] PalindromeQ["salàlas"] PalindromeRecQ["salàlas"] PalindromeQ["ingirumimusnocteetconsumimurigni"] PalindromeRecQ["ingirumimusnocteetconsumimurigni"]</lang>
Note that the code block doesn't correctly show the à in salàlas. Output: <lang Mathematica>True True False False True True True True True True</lang>
MAXScript
Non-recursive
<lang maxscript>fn isPalindrome s = (
local reversed = "" for i in s.count to 1 by -1 do reversed += s[i] return reversed == s
)</lang>
Recursive
<lang maxscript>fn isPalindrome_r s = (
if s.count <= 1 then ( true ) else ( if s[1] != s[s.count] then ( return false ) isPalindrome_r (substring s 2 (s.count-2)) )
)</lang>
Testing
<lang maxscript>local p = "ingirumimusnocteetconsumimurigni" format ("'%' is a palindrome? %\n") p (isPalindrome p) format ("'%' is a palindrome? %\n") p (isPalindrome_r p)</lang>
Modula-3
<lang modula3>MODULE Palindrome;
IMPORT Text;
PROCEDURE isPalindrome(string: TEXT): BOOLEAN =
VAR len := Text.Length(string); BEGIN FOR i := 0 TO len DIV 2 - 1 DO IF Text.GetChar(string, i) # Text.GetChar(string, (len - i - 1)) THEN RETURN FALSE; END; END; RETURN TRUE; END isPalindrome;
END Palindrome.</lang>
OCaml
<lang ocaml>let is_palindrome str =
let last = String.length str - 1 in try for i = 0 to last / 2 do let j = last - i in if str.[i] <> str.[j] then raise Exit done; (true) with Exit -> (false)</lang>
and here a function to remove the white spaces in the string:
<lang ocaml>let rem_space str =
let len = String.length str in let res = String.create len in let rec aux i j = if i >= len then (String.sub res 0 j) else match str.[i] with | ' ' | '\n' | '\t' | '\r' -> aux (i+1) (j) | _ -> res.[j] <- str.[i]; aux (i+1) (j+1) in aux 0 0</lang>
and to make the test case insensitive, just use the function String.lowercase.
Octave
Recursive <lang octave>function v = palindro_r(s)
if ( length(s) == 1 ) v = true; return; elseif ( length(s) == 2 ) v = s(1) == s(2); return; endif if ( s(1) == s(length(s)) ) v = palindro_r(s(2:length(s)-1)); else v = false; endif
endfunction</lang>
Non-recursive <lang octave>function v = palindro(s)
v = all( (s == s(length(s):-1:1)) == 1);
endfunction</lang>
Testing <lang octave>palindro_r("ingirumimusnocteetconsumimurigni") palindro("satorarepotenetoperarotas")</lang>
Oz
<lang oz>fun {IsPalindrome S}
{Reverse S} == S
end</lang>
PHP
<lang php><?php function is_palindrome($string) {
return $string == strrev($string);
} ?></lang>
Pascal
<lang pascal>program Palindro;
{ RECURSIVE } function is_palindro_r(s : String) : Boolean; begin
if length(s) <= 1 then is_palindro_r := true else begin if s[1] = s[length(s)] then
is_palindro_r := is_palindro_r(copy(s, 2, length(s)-2))
else
is_palindro_r := false
end
end; { is_palindro_r }
{ NON RECURSIVE; see Reversing a string for "reverse" } function is_palindro(s : String) : Boolean; begin
if s = reverse(s) then is_palindro := true else is_palindro := false
end;</lang>
<lang pascal>procedure test_r(s : String; r : Boolean); begin
write('"', s, '" is '); if ( not r ) then write('not '); writeln('palindrome')
end;
var
s1, s2 : String;
begin
s1 := 'ingirumimusnocteetconsumimurigni'; s2 := 'in girum imus nocte'; test_r(s1, is_palindro_r(s1)); test_r(s2, is_palindro_r(s2)); test_r(s1, is_palindro(s1)); test_r(s2, is_palindro(s2))
end.</lang>
Perl
Non-recursive
One solution (palindrome_c) is the same as the C non-recursive solution palindrome; while Perl palindrome sub uses the idea that a word is a palindrome if, once reverted, it looks the same as the original word (this is the definition of a palindrome).
<lang perl>sub palindrome {
my $s = shift; return $s eq reverse $s;
}
sub palindrome_c {
my $s = shift; for my $i (0 .. length($s) >> 1) { return 0 unless substr($s, $i, 1) eq substr($s, -1-$i, 1); } return 1;
}</lang>
Recursive
<lang perl>sub palindrome_r {
my $s = shift; if (length $s <= 1) { return 1; } elsif (substr($s, 0, 1) ne substr($s, -1, 1)) { return 0; } else { return palindrome_r(substr($s, 1, -1)); }
}</lang>
Testing
<lang perl>sub mtest {
my ( $t, $func ) = @_; printf("sequence \"%s\" is%s palindrome\n", $t, &$func($t) ? "" : "n't");
} mtest "ingirumimusnocteetconsumimurigni", \&palindrome; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_r; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c;
exit;</lang>
Regular Expression
Perl supports recursive regular expressions, which offer yet another way to compute this predicate. <lang perl>sub palendrome {lc (@_ ? shift : $_) =~ /^(.?|(.)(?1)\2)$/ + 0}
print palendrome, " : $_\n" for qw/a aa ab abba aBbA abca abba1 1abba ingirumimusnocteetconsumimurigni/,
'ab cc ba', 'ab ccb a';</lang>
Output: 1 : a 1 : aa 0 : ab 1 : abba 1 : aBbA 0 : abca 0 : abba1 0 : 1abba 1 : ingirumimusnocteetconsumimurigni 1 : ab cc ba 0 : ab ccb a
Perl 6
<lang perl6>sub palindrome (Str $s --> Bool) { $s eq flip $s }</lang>
PicoLisp
<lang PicoLisp>(de palindrome? (S)
(= (setq S (chop S)) (reverse S)) )</lang>
Output:
: (palindrome? "ingirumimusnocteetconsumimurigni") -> T
Pike
<lang pike>int main(){
if(pal("rotator")){ write("palindrome!\n"); } if(!pal("asdf")){ write("asdf isn't a palindrome.\n"); }
}
int pal(string input){
if( reverse(input) == input ){ return 1; } else { return 0; }
}</lang>
PL/I
<lang PL/I> is_palindrome: procedure (text) returns (bit(1));
declare text character (*) varying;
text = remove_blanks(text); text = lowercase(text); return (text = reverse(text));
remove_blanks: procedure (text);
declare text character (*) varying; declare (i, j) fixed binary (31); j = 0; do i = 1 to length(text); if substr(text, i, 1) = ' ' then do; j = j + 1; substr(text, j, 1) = substr(text, i, 1); end; end; return (substr(text, 1, j));
end remove_blanks; end is_palindrome; </lang>
PowerBASIC
The output is identical to the QBasic version, above.
<lang powerbasic>FUNCTION isPalindrome (what AS STRING) AS LONG
DIM whatcopy AS STRING, chk AS STRING, tmp AS STRING * 1, L0 AS LONG
FOR L0 = 1 TO LEN(what) tmp = UCASE$(MID$(what, L0, 1)) SELECT CASE tmp CASE "A" TO "Z" whatcopy = whatcopy & tmp chk = tmp & chk CASE "0" TO "9" MSGBOX "Numbers are cheating! (""" & what & """)" FUNCTION = 0 EXIT FUNCTION END SELECT NEXT
FUNCTION = ISTRUE((whatcopy) = chk)
END FUNCTION
FUNCTION PBMAIN () AS LONG
DATA "My dog has fleas", "Madam, I'm Adam.", "1 on 1", "In girum imus nocte et consumimur igni" DIM L1 AS LONG, w AS STRING FOR L1 = 1 TO DATACOUNT w = READ$(L1) IF ISTRUE(isPalindrome(w)) THEN MSGBOX $DQ & w & """ is a palindrome" ELSE MSGBOX $DQ & w & """ is not a palindrome" END IF NEXT
END FUNCTION</lang>
Prolog
Non-recursive
From this tutorial.
<lang prolog>palindrome(Word) :- name(Word,List), reverse(List,List).</lang>
Recursive
<lang prolog>pali(Str) :- sub_string(Str, 0, 1, _, X), string_concat(Str2, X, Str), string_concat(X, Mid, Str2), pali(Mid). pali(Str) :- string_length(Str, Len), Len < 2.</lang>
Changing string into atom makes the program run also on GNU Prolog. I.e.
<lang prolog>pali(Str) :- sub_atom(Str, 0, 1, _, X), atom_concat(Str2, X, Str), atom_concat(X, Mid, Str2), pali(Mid). pali(Str) :- atom_length(Str, Len), Len < 2.</lang>
PureBasic
<lang PureBasic>Procedure IsPalindrome(StringToTest.s)
If StringToTest=ReverseString(StringToTest) ProcedureReturn 1 Else ProcedureReturn 0 EndIf
EndProcedure</lang>
Python
Non-recursive
This one uses the reversing the string technique (to reverse a string Python can use the odd but right syntax string[::-1])
<lang python>def is_palindrome(s):
return s == s[::-1]</lang>
Recursive
<lang python>def is_palindrome_r(s):
if len(s) <= 1: return True elif s[0] != s[-1]: return False else: return is_palindrome_r(s[1:-1])</lang>
Python has short-circuit evaluation of Boolean operations so a shorter and still easy to understand recursive function is
<lang python>def is_palindrome_r2(s):
return not s or s[0] == s[-1] and is_palindrome_r2(s[1:-1])</lang>
Testing
<lang python>def test(f, good, bad):
assert all(f(x) for x in good) assert not any(f(x) for x in bad) print '%s passed all %d tests' % (f.__name__, len(good)+len(bad))
pals = (, 'a', 'aa', 'aba', 'abba') notpals = ('aA', 'abA', 'abxBa', 'abxxBa') for ispal in is_palindrome, is_palindrome_r, is_palindrome_r2:
test(ispal, pals, notpals)</lang>
R
Recursive
Note that the recursive method will fail if the string length is too long. R will assume an infinite recursion if a recursion nests deeper than 5,000. Options may be set in the environment to increase this to 500,000. <lang R>palindro <- function(p) {
if ( nchar(p) == 1 ) { return(TRUE) } else if ( nchar(p) == 2 ) { return(substr(p,1,1) == substr(p,2,2)) } else { if ( substr(p,1,1) == substr(p, nchar(p), nchar(p)) ) { return(palindro(substr(p, 2, nchar(p)-1))) } else { return(FALSE) } }
}</lang>
Iterative <lang R>palindroi <- function(p) {
for(i in 1:floor(nchar(p)/2) ) { r <- nchar(p) - i + 1 if ( substr(p, i, i) != substr(p, r, r) ) return(FALSE) } TRUE
}</lang>
Comparative
This method is somewhat faster than the other two.
Note that this method incorrectly regards an empty string as not a palindrome. Please leave this bug in the code, and take a look a the Testing_a_Function page. <lang R>revstring <- function(stringtorev) {
return( paste( strsplit(stringtorev,"")1[nchar(stringtorev):1] ,collapse="") )
} palindroc <- function(p) {return(revstring(p)==p)}</lang>
Example Output
test <- "ingirumimusnocteetconsumimurigni" tester <- paste(rep(test,38),collapse="") > test <- "ingirumimusnocteetconsumimurigni" > tester <- paste(rep(test,38),collapse="") > system.time(palindro(tester)) user system elapsed 0.04 0.00 0.04 > system.time(palindroi(tester)) user system elapsed 0.01 0.00 0.02 > system.time(palindroc(tester)) user system elapsed 0 0 0
REBOL
<lang REBOL>REBOL [
Title: "Palindrome Recognizer" Date: 2010-01-03 Author: oofoe URL: http://rosettacode.org/wiki/Palindrome
]
- In order to compete with all the one-liners, the operation is
- compressed
- parens force left hand side to evaluate first, where I
- copy the phrase, then uppercase it and assign it to 'p'. Now the
- right hand side is evaluated
- p is copied, then reversed in place;
- the comparison is made and implicitely returned.
palindrome?: func [ phrase [string!] "Potentially palindromatic prose." /local p ][(p: uppercase copy phrase) = reverse copy p]
- Teeny Tiny Test Suite
assert: func [code][print [either do code [" ok"]["FAIL"] mold code]]
print "Simple palindromes, with an exception for variety:" repeat phrase ["z" "aha" "sees" "oofoe" "Deified"][ assert compose [palindrome? (phrase)]]
print [crlf "According to the problem statement, these should fail:"] assert [palindrome? "A man, a plan, a canal, Panama."] ; Punctuation not ignored. assert [palindrome? "In girum imus nocte et consumimur igni"] ; Spaces not removed.
- I know we're doing palindromes, not alliteration, but who could resist...?</lang>
Output:
Simple palindromes, with an exception for variety: ok [palindrome? "z"] ok [palindrome? "aha"] ok [palindrome? "sees"] FAIL [palindrome? "oofoe"] ok [palindrome? "Deified"] According to the problem statement, these should fail: FAIL [palindrome? "A man, a plan, a canal, Panama."] FAIL [palindrome? "In girum imus nocte et consumimur igni"]
Ruby
Non-recursive
<lang ruby>def is_palindrome(s)
s == s.reverse
end</lang>
Recursive
<lang ruby>def is_palindrome_r(s)
if s.length <= 1 true elsif s[0] != s[-1] false else is_palindrome_r(s[1..-2]) end
end</lang>
Testing Note that the recursive method is much slower -- using the 2151 character palindrome by Dan Hoey here, we have: <lang ruby>str = "A man, a plan, a caret, [...2110 chars deleted...] a canal--Panama.".downcase.delete('^a-z') puts is_palindrome(str) # => true puts is_palindrome_r(str) # => true
require 'benchmark' Benchmark.bm do |b|
b.report('iterative') {10000.times {is_palindrome(str)}} b.report('recursive') {10000.times {is_palindrome_r(str)}}
end</lang>
output
true true user system total real iterative 0.062000 0.000000 0.062000 ( 0.055000) recursive 16.516000 0.000000 16.516000 ( 16.562000)
Scala
Non-recursive
The coercion to string is necessary because otherwise Scala uses on RichString instead, and comparing a String to a RichString would fail.
<lang scala>def isPalindrome(s: String) = s == (s reverse).toString</lang>
Test <lang scala>scala> isPalindrome("amanaplanacanalpanama") res0: Boolean = true
scala> isPalindrome("Test 1,2,3") res1: Boolean = false
scala> isPalindrome("1 2 1") res2: Boolean = true</lang>
Scheme
Non-recursive
<lang scheme>(define (palindrome? s)
(let ((chars (string->list s))) (equal? chars (reverse chars))))</lang>
Recursive <lang scheme>(define (palindrome? s)
(let loop ((i 0) (j (sub1 (string-length s)))) (or (>= i j) (let ((c-i (string-ref s i)) (c-j (string-ref s j))) (cond ((char=? c-i c-j) (loop (add1 i) (sub1 j))) (else #f))))))</lang>
To test: <lang scheme>> (palindrome? "ingirumimusnocteetconsumimurigni")
- t
> (palindrome? "This is not a palindrome")
- f
></lang>
Slate
Non-Recursive <lang slate>s@(String traits) isPalindrome [
(s lexicographicallyCompare: s reversed) isZero
].</lang>
Recursive Defined on Sequence since we are not using String-specific methods: <lang slate>s@(Sequence traits) isPalindrome [
s isEmpty ifTrue: [True] ifFalse: [(s first = s last) /\ [(s sliceFrom: 1 to: s indexLast - 1) isPalindrome]]
].</lang>
Testing <lang slate>define: #p -> 'ingirumimusnocteetconsumimurigni'. inform: 'sequence ' ; p ; ' is ' ; (p isPalindrome ifTrue: [] ifFalse: ['not ']) ; 'a palindrome.'.</lang>
Smalltalk
<lang smalltalk>isPalindrome := [:aString | str := (aString select: [:chr| chr isAlphaNumeric]) collect: [:chr | chr asLowercase]. str = str reversed. ]. </lang>
<lang smalltalk>String extend [
palindro [ "Non-recursive" ^ self = (self reverse) ] palindroR [ "Recursive" (self size) <= 1 ifTrue: [ ^true ] ifFalse: [ |o i f| o := self asOrderedCollection. i := o removeFirst. f := o removeLast. i = f ifTrue: [ ^ (o asString) palindroR ] ifFalse: [ ^false ] ] ]
].</lang>
Testing
<lang smalltalk>('hello' palindro) printNl. ('hello' palindroR) printNl. ('ingirumimusnocteetconsumimurigni' palindro) printNl. ('ingirumimusnocteetconsumimurigni' palindroR) printNl.</lang>
Tcl
Non-recursive
<lang tcl>package require Tcl 8.5 proc palindrome {s} {
return [expr {$s eq [string reverse $s]}]
}</lang>
Recursive
<lang tcl>proc palindrome_r {s} {
if {[string length $s] <= 1} { return true } elseif {[string index $s 0] ne [string index $s end]} { return false } else { return [palindrome_r [string range $s 1 end-1]] }
}</lang>
Testing
<lang tcl>set p ingirumimusnocteetconsumimurigni puts "'$p' is palindrome? [palindrome $p]" puts "'$p' is palindrome? [palindrome_r $p]"</lang>
Ursala
The algorithm is to convert to lower case, and then compare the intersection of the argument and the set of letters (declared in the standard library) with its reversal. This is done using the built in operator suffixes for intersection (c), identity (i), reversal (x) and equality (E). <lang Ursala>#import std
palindrome = ~&cixE\letters+ * -:~& ~=`A-~rlp letters</lang> This test programs applies the function to each member of a list of three strings, of which only the first two are palindromes. <lang Ursala>#cast %bL
examples = palindrome* <'abccba','foo ba rra bo of','notone'></lang> output:
<true,true,false>
VBScript
Implementation
<lang vb>function Squish( s1 ) dim sRes sRes = vbNullString dim i, c for i = 1 to len( s1 ) c = lcase( mid( s1, i, 1 )) if instr( "abcdefghijklmnopqrstuvwxyz0123456789", c ) then sRes = sRes & c end if next Squish = sRes end function
function isPalindrome( s1 ) dim squished squished = Squish( s1 ) isPalindrome = ( squished = StrReverse( squished ) ) end function</lang>
Invocation
<lang vb>wscript.echo isPalindrome( "My dog has fleas") wscript.echo isPalindrome( "Madam, I'm Adam.") wscript.echo isPalindrome( "1 on 1") wscript.echo isPalindrome( "In girum imus nocte et consumimur igni")</lang>
Output
<lang vb>0 -1 0 -1</lang>
Vedit macro language
This routine checks if current line is a palindrome:
<lang vedit>:PALINDROME: EOL #2 = Cur_Col-2 BOL for (#1 = 0; #1 <= #2/2; #1++) {
if (CC(#1) != CC(#2-#1)) { Return(0) }
} Return(1)</lang>
Testing:
<lang vedit>Call("PALINDROME") if (Return_Value) {
Statline_Message("Yes")
} else {
Statline_Message("No")
} Return</lang>
Factor
<lang Factor>
- palindrome? ( string -- ? ) dup reverse = ;
</lang>
- Programming Tasks
- Text processing
- Recursion
- Classic CS problems and programs
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- Befunge
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- Erlang
- F Sharp
- Factor
- Forth
- Fortran
- Groovy
- Haskell
- HicEst
- Icon
- Icon Programming Library
- Unicon
- Ioke
- J
- Java
- JavaScript
- Logo
- Lua
- M4
- Mathematica
- MAXScript
- Modula-3
- OCaml
- Octave
- Oz
- PHP
- Pascal
- Perl
- Perl 6
- PicoLisp
- Pike
- PL/I
- PowerBASIC
- Prolog
- PureBasic
- Python
- R
- REBOL
- Ruby
- Scala
- Scheme
- Slate
- Smalltalk
- Tcl
- Ursala
- VBScript
- Vedit macro language