Palindrome detection
From Rosetta Code
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.
Example
An example of a 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.
Notes
- It might be useful for this task to know how to reverse a string.
- This task's entries might also form the subjects of the task Test a function.
[edit] ActionScript
The following function handles non-ASCII characters properly, since charAt() returns a single Unicode character.
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;
}
[edit] 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;
[edit] ALGOL 68
Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386 Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386 - except for the FORMAT and printf in test
# 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)))
)
Output:
sequence "ingirumimusnocteetconsumimurigni" is a palindrome sequence "ingirumimusnocteetconsumimurigni" is a palindrome
[edit] 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
}
[edit] AWK
Non-recursive
See Reversing a string.
function is_palindro(s)
{
if ( s == reverse(s) ) return 1;
return 0
}
Recursive
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))
}
Testing
BEGIN {
pal = "ingirumimusnocteetconsumimurigni"
print is_palindro(pal)
print is_palindro_r(pal)
}
[edit] BASIC
Works with: 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
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
[edit] Befunge
Works with: CCBI version 2.1
The following code reads a line from stdin and prints "True" if it is a palindrome, or False" otherwise.
v_$0:8p>:#v_:18p08g1-08p >:08g`!v
~->p5p ^ 0v1p80-1g80vj!-g5g80g5_0'ev
:a^80+1:g8<>8g1+:18pv>0"eslaF">:#,_@
[[relet]]-2010------>003-x -^"Tru"<
Works with: Befunge version 93
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.)
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
|: < <
^<
[edit] 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).
#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;
}
More idiomatic version:
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;
}
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.
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);
}
Testing
#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;
}
[edit] C++
The C solutions also work in C++, but C++ allows a simpler one:
#include <string>
#include <algorithm>
bool is_palindrome(std::string const& s)
{
return std::equal(s.begin(), s.end(), s.rbegin());
}
[edit] C#
Non-recursive
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"));
}
}
[edit] Clojure
(defn palindrome? [s]
(= s (apply str (reverse s))))
Recursive
(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)))
Test
user=> (palindrome? "amanaplanacanalpanama") true user=> (palindrome? "Test 1, 2, 3") false
[edit] Common Lisp
(defun palindrome-p (s)
(string= s (reverse s)))
[edit] D
Hi-level ASCII version:
bool isPalindrome1(string s) {
return s == s.dup.reverse;
}
Low-level ASCII version:
bool isPalindrome2(string str) {
char* s = str.ptr;
char* t = &str[$-1];
while (s < t)
if (*s++ != *t--)
return false;
return true;
}
Mid-level 32-bit Unicode version:
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;
}
[edit] 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.
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
}
[edit] Erlang
is_palindrome(String) ->
String == lists:reverse(String).
[edit] F#
Forall2 applies the predicate to each member of the two arrays, until it finds a false or it reaches the end.
let isPalindrome (s: string) =
let arr = s.ToCharArray()
Array.forall2 (fun a b -> a = b) ( arr ) ( Array.rev ( arr ) )
Examples:
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
[edit] Factor
USING: kernel sequences ;
: palindrome? ( str -- ? ) dup reverse = ;
[edit] Forth
: first over c@ ;
: last >r 2dup + 1- c@ r> swap ;
: palindrome? ( c-addr u -- f )
begin
dup 1 <= if 2drop true exit then
first last <> if 2drop false exit then
1 /string 1-
again ;
FIRST and LAST are once-off words that could be beheaded immediately afterwards. The version taking advantage of Tail Call Optimization or a properly tail-recursive variant of RECURSE (easily added to any Forth) is very similar. The horizontal formatting highlights the parallel code - and potential factor; a library of many string tests like this could have ?SUCCESS and ?FAIL .
[edit] Fortran
Works with: Fortran version 90 and later
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
Non-recursive
! 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
Recursive
recursive function is_palindro_r (t) result (isp)
implicit none
character (*), intent (in) :: t
logical :: isp
isp = len (t) == 0 .or. t (: 1) == t (len (t) :) .and. is_palindro_r (t (2 : len (t) - 1))
end function is_palindro_r
end program palindro
[edit] Groovy
Trivial
Solution:
def isPalindrome = { String s ->
s == s?.reverse()
}
Test program:
println isPalindrome("")
println isPalindrome("a")
println isPalindrome("abcdefgfedcba")
println isPalindrome("abcdeffedcba")
println isPalindrome("abcedfgfedcb")
Output:
true true true true false
This solution assumes nulls are palindromes.
Non-recursive
Solution:
def isPalindrome = { String s ->
def n = s.size()
n < 2 || s[0..<n/2] == s[-1..(-n/2)]
}
Test program and output are the same. This solution does not handle nulls.
Recursive
Solution follows the C palindrome_r recursive solution:
def isPalindrome
isPalindrome = { String s ->
def n = s.size()
n < 2 || (s[0] == s[n-1] && isPalindrome(s[1..<(n-1)]))
}
Test program and output are the same. This solution does not handle nulls.
[edit] Haskell
Non-recursive
A string is a palindrome if reversing it we obtain the same string.
is_palindrome x = x == reverse x
Recursive
See the C palindrome_r code for an explanation of the concept used in this solution.
is_palindrome_r x | length x <= 1 = True
| head x == last x = is_palindrome_r . tail. init $ x
| otherwise = False
[edit] 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
[edit] Icon and Unicon
[edit] Icon
procedure main(arglist)
every writes(s := !arglist) do write( if palindrome(s) then " is " else " is not", " a palindrome.")
end
The following simple procedure uses the built-in reverse. Reverse creates a transient string which will get garbage collected.
procedure palindrome(s) #: return s if s is a palindrome
return s == reverse(s)
end
Library: Icon Programming Library
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.
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
[edit] Unicon
This Icon solution works in Unicon.
[edit] Ioke
Text isPalindrome? = method(self chars == self chars reverse)
[edit] J
Non-recursive
Reverse and match method
isPalin0=: -: |.
Example usage
isPalin0 'ABBA'
1
isPalin0 ;;: tolower 'In girum imus nocte et consumimur igni'
1
Recursive
Tacit and explicit verbs:
isPalin1=: 0:`($:@(}.@}:))@.({.={:)`1:@.(1>:#)
isPalin2=: monad define
if. 1>:#y do. 1 return. end.
if. ({.={:)y do. isPalin2 }.}:y else. 0 end.
)
Note that while these recursive verbs are bulkier and more complicated, they are also several thousand times more inefficient than isPalin0.
foo=: foo,|.foo=:2000$a.
ts=:6!:2,7!:2 NB. time and space required to execute sentence
ts 'isPalin0 foo'
2.73778e_5 5184
ts 'isPalin1 foo'
0.0306667 6.0368e6
ts 'isPalin2 foo'
0.104391 1.37965e7
'isPalin1 foo' %&ts 'isPalin0 foo'
1599.09 1164.23
'isPalin2 foo' %&ts 'isPalin0 foo'
3967.53 2627.04
[edit] Java
Non-Recursive
public static boolean pali(String testMe){
StringBuilder sb = new StringBuilder(testMe);
return testMe.equalsIgnoreCase(sb.reverse().toString());
}
Recursive
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));
}
[edit] JavaScript
String.prototype.reverse = function(){ return this.split("").reverse().join(""); }
function palindrome(str) { return str == str.reverse(); }
alert(palindrome("ingirumimusnocteetconsumimurigni"));
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();
[edit] Logo
to palindrome? :w
output equal? :w reverse :w
end
[edit] Lua
function ispalindrome(s) return s == string.reverse(s) end
[edit] M4
Non-recursive
This uses the invert from Reversing a string.
define(`palindrorev',`ifelse(`$1',invert(`$1'),`yes',`no')')dnl
palindrorev(`ingirumimusnocteetconsumimurigni')
palindrorev(`this is not palindrome')
Recursive
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')
[edit] Mathematica
Custom functions:
Non-recursive
PalindromeQ[i_String] := StringReverse[i] == i
Recursive
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
]
]
Examples:
PalindromeQ["TNT"]
PalindromeRecQ["TNT"]
PalindromeQ["test"]
PalindromeRecQ["test"]
PalindromeQ["deified"]
PalindromeRecQ["deified"]
PalindromeQ["salàlas"]
PalindromeRecQ["salàlas"]
PalindromeQ["ingirumimusnocteetconsumimurigni"]
PalindromeRecQ["ingirumimusnocteetconsumimurigni"]
Note that the code block doesn't correctly show the à in salàlas. Output:
True
True
False
False
True
True
True
True
True
True
[edit] MATLAB
function trueFalse = isPalindrome(string)
trueFalse = all(string == fliplr(string)); %See if flipping the string produces the original string
if not(trueFalse) %If not a palindrome
string = lower(string); %Lower case everything
trueFalse = all(string == fliplr(string)); %Test again
end
if not(trueFalse) %If still not a palindrome
string(isspace(string)) = []; %Strip all space characters out
trueFalse = all(string == fliplr(string)); %Test one last time
end
end
Sample Usage:
>> isPalindrome('In girum imus nocte et consumimur igni')
ans =
1
[edit] MAXScript
Non-recursive
fn isPalindrome s =
(
local reversed = ""
for i in s.count to 1 by -1 do reversed += s[i]
return reversed == s
)
Recursive
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))
)
)
Testing
local p = "ingirumimusnocteetconsumimurigni"
format ("'%' is a palindrome? %\n") p (isPalindrome p)
format ("'%' is a palindrome? %\n") p (isPalindrome_r p)
[edit] MMIX
argc IS $0
argv IS $1
LOC Data_Segment
DataSeg GREG @
LOC @+1000
ItsPalStr IS @-Data_Segment
BYTE "It's palindrome",10,0
LOC @+(8-@)&7
NoPalStr IS @-Data_Segment
BYTE "It is not palindrome",10,0
LOC #100
GREG @
% input: $255 points to where the string to be checked is
% returns $255 0 if not palindrome, not zero otherwise
% trashs: $0,$1,$2,$3
% return address $4
DetectPalindrome LOC @
ADDU $1,$255,0 % $1 = $255
2H LDB $0,$1,0 % get byte at $1
BZ $0,1F % if zero, end (length)
INCL $1,1 % $1++
JMP 2B % loop
1H SUBU $1,$1,1 % ptr last char of string
ADDU $0,DataSeg,0 % $0 to data seg.
3H CMP $3,$1,$255 % is $0 == $255?
BZ $3,4F % then jump
LDB $3,$1,0 % otherwise get the byte
STB $3,$0,0 % and copy it
INCL $0,1 % $0++
SUB $1,$1,1 % $1--
JMP 3B
4H LDB $3,$1,0
STB $3,$0,0 % copy the last byte
% now let us compare reversed string and straight string
XOR $0,$0,$0 % index
ADDU $1,DataSeg,0
6H LDB $2,$1,$0 % pick char from rev str
LDB $3,$255,$0 % pick char from straight str
BZ $3,PaliOk % finished as palindrome
CMP $2,$2,$3 % == ?
BNZ $2,5F % if not, exit
INCL $0,1 % $0++
JMP 6B
5H XOR $255,$255,$255
GO $4,$4,0 % return false
PaliOk NEG $255,0,1
GO $4,$4,0 % return true
% The Main for testing the function
% run from the command line
% $ mmix ./palindrome.mmo ingirumimusnocteetconsumimurigni
Main CMP argc,argc,2 % argc > 2?
BN argc,3F % no -> not enough arg
ADDU $1,$1,8 % argv+1
LDOU $255,$1,0 % argv[1]
GO $4,DetectPalindrome
BZ $255,2F % if not palindrome, jmp
SETL $0,ItsPalStr % pal string
ADDU $255,DataSeg,$0
JMP 1F
2H SETL $0,NoPalStr % no pal string
ADDU $255,DataSeg,$0
1H TRAP 0,Fputs,StdOut % print
3H XOR $255,$255,$255
TRAP 0,Halt,0 % exit(0)
[edit] Modula-3
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.
[edit] 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)
and here a function to remove the white spaces in the string:
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
and to make the test case insensitive, just use the function String.lowercase.
[edit] Octave
Recursive
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
Non-recursive
function v = palindro(s)
v = all( (s == s(length(s):-1:1)) == 1);
endfunction
Testing
palindro_r("ingirumimusnocteetconsumimurigni")
palindro("satorarepotenetoperarotas")
[edit] Oz
fun {IsPalindrome S}
{Reverse S} == S
end
[edit] PHP
<?php
function is_palindrome($string) {
return $string == strrev($string);
}
?>
[edit] Pascal
Works with: Free 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;
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.
[edit] Perl
Non-recursive
palindrome( ) checks if the two halves of the string are mirror images, and palindrome_c( ) is a translation of the C non-recursive solution.
sub palindrome
{
(my $s = lc(shift)) =~ s/[\W_]//g;
return $s eq reverse $s;
}
sub palindrome_c
{
(my $s = lc(shift)) =~ s/[\W_]//g;
for my $i (0 .. length($s) >> 1)
{
return 0 unless substr($s, $i, 1) eq substr($s, -1-$i, 1);
}
return 1;
}
Recursive
sub palindrome_r
{
(my $s = lc(shift)) =~ s/[\W_]//g;
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)); }
}
Testing
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;
Regular Expression
Perl supports recursive regular expressions, which offer yet another way to compute this predicate.
sub palindrome {lc (@_ ? shift : $_) =~ /^(.?|(.)(?1)\2)$/ + 0}
print palindrome, " : $_\n" for
qw/a aa ab abba aBbA abca abba1 1abba
ingirumimusnocteetconsumimurigni/,
'ab cc ba', 'ab ccb a';
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
[edit] Perl 6
Works with: Rakudo version #21 "Seattle"
sub palindrome (Str $s --> Bool) { $s eq flip $s }
[edit] PicoLisp
(de palindrome? (S)
(= (setq S (chop S)) (reverse S)) )
Output:
: (palindrome? "ingirumimusnocteetconsumimurigni") -> T
[edit] 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;
}
}
[edit] 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;
[edit] PowerBASIC
The output is identical to the QBasic version, above.
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
[edit] Prolog
Non-recursive
From this tutorial.
palindrome(Word) :- name(Word,List), reverse(List,List).
Recursive
Works with: SWI 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.
Changing string into atom makes the program run also on GNU Prolog. I.e.
Works with: GNU 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.
[edit] PureBasic
Works with: PureBasic version 4.41
Procedure IsPalindrome(StringToTest.s)
If StringToTest=ReverseString(StringToTest)
ProcedureReturn 1
Else
ProcedureReturn 0
EndIf
EndProcedure
[edit] 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])
def is_palindrome(s):
return s == s[::-1]
Recursive
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])
Python has short-circuit evaluation of Boolean operations so a shorter and still easy to understand recursive function is
def is_palindrome_r2(s):
return not s or s[0] == s[-1] and is_palindrome_r2(s[1:-1])
Testing
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)
[edit] 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.
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)
}
}
}
Iterative
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
}
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.
revstring <- function(stringtorev) {
return(
paste(
strsplit(stringtorev,"")[[1]][nchar(stringtorev):1]
,collapse="")
)
}
palindroc <- function(p) {return(revstring(p)==p)}
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
[edit] 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...?
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"]
[edit] Ruby
Non-recursive
def is_palindrome(s)
s == s.reverse
end
Recursive
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
Testing Note that the recursive method is much slower -- using the 2151 character palindrome by Dan Hoey here, we have:
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
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)
[edit] 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.
def isPalindrome(s: String) = s == (s reverse).toString
Test
scala> isPalindrome("amanaplanacanalpanama")
res0: Boolean = true
scala> isPalindrome("Test 1,2,3")
res1: Boolean = false
scala> isPalindrome("1 2 1")
res2: Boolean = true
[edit] Scheme
Non-recursive
(define (palindrome? s)
(let ((chars (string->list s)))
(equal? chars (reverse chars))))
Recursive
(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))))))
To test:
> (palindrome? "ingirumimusnocteetconsumimurigni")
#t
> (palindrome? "This is not a palindrome")
#f
>
[edit] Slate
Non-Recursive
s@(String traits) isPalindrome
[
(s lexicographicallyCompare: s reversed) isZero
].
Recursive Defined on Sequence since we are not using String-specific methods:
s@(Sequence traits) isPalindrome
[
s isEmpty
ifTrue: [True]
ifFalse: [(s first = s last) /\ [(s sliceFrom: 1 to: s indexLast - 1) isPalindrome]]
].
Testing
define: #p -> 'ingirumimusnocteetconsumimurigni'.
inform: 'sequence ' ; p ; ' is ' ; (p isPalindrome ifTrue: [''] ifFalse: ['not ']) ; 'a palindrome.'.
[edit] Smalltalk
Works with: Squeak
isPalindrome := [:aString |
str := (aString select: [:chr| chr isAlphaNumeric]) collect: [:chr | chr asLowercase].
str = str reversed.
].
Works with: GNU 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 ]
]
]
].
Testing
('hello' palindro) printNl.
('hello' palindroR) printNl.
('ingirumimusnocteetconsumimurigni' palindro) printNl.
('ingirumimusnocteetconsumimurigni' palindroR) printNl.
[edit] SNOBOL4
define('pal(str)') :(pal_end)
pal str notany(&ucase &lcase) = :s(pal)
str = replace(str,&ucase,&lcase)
leq(str,reverse(str)) :s(return)f(freturn)
pal_end
define('palchk(str)tf') :(palchk_end)
palchk output = str;
tf = 'False'; tf = pal(str) 'True'
output = 'Palindrome: ' tf :(return)
palchk_end
* # Test and display
palchk('Able was I ere I saw Elba')
palchk('In girum imus nocte et consumimur igni')
palchk('The quick brown fox jumped over the lazy dogs')
end
Output:
Able was I ere I saw Elba Palindrome: True In girum imus nocte et consumimur igni Palindrome: True The quick brown fox jumped over the lazy dogs Palindrome: False
[edit] Tcl
Non-recursive
package require Tcl 8.5
proc palindrome {s} {
return [expr {$s eq [string reverse $s]}]
}
Recursive
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]]
}
}
Testing
set p ingirumimusnocteetconsumimurigni
puts "'$p' is palindrome? [palindrome $p]"
puts "'$p' is palindrome? [palindrome_r $p]"
[edit] 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).
#import std
palindrome = ~&cixE\letters+ * -:~& ~=`A-~rlp letters
This test programs applies the function to each member of a list of three strings, of which only the first two are palindromes.
#cast %bL
examples = palindrome* <'abccba','foo ba rra bo of','notone'>
output:
<true,true,false>
[edit] VBScript
[edit] Implementation
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
[edit] Invocation
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")
[edit] Output
0
-1
0
-1
[edit] Vedit macro language
This routine checks if current line is a palindrome:
:PALINDROME:
EOL #2 = Cur_Col-2
BOL
for (#1 = 0; #1 <= #2/2; #1++) {
if (CC(#1) != CC(#2-#1)) { Return(0) }
}
Return(1)
Testing:
Call("PALINDROME")
if (Return_Value) {
Statline_Message("Yes")
} else {
Statline_Message("No")
}
Return
[edit] Factor
: palindrome? ( string -- ? ) dup reverse = ;
