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] ACL2
(defun reverse-split-at-r (xs i ys)
(if (zp i)
(mv xs ys)
(reverse-split-at-r (rest xs) (1- i)
(cons (first xs) ys))))
(defun reverse-split-at (xs i)
(reverse-split-at-r xs i nil))
(defun is-palindrome (str)
(let* ((lngth (length str))
(idx (floor lngth 2)))
(mv-let (xs ys)
(reverse-split-at (coerce str 'list) idx)
(if (= (mod lngth 2) 1)
(equal (rest xs) ys)
(equal xs ys)))))
[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
# 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
Concise version reversing the string,:
IsPalindrome( Str ){
StringLower, str, str
str := (RegexReplace(str,"\W+" ))
Loop, Parse, Str
reversedStr := A_LoopField . ReversedStr
Return ( ReversedStr = Str )
}
[edit] AutoIt
;AutoIt Version: 3.2.10.0
$mystring="In girum imus nocte, et consumimur igni"
MsgBox(0, "Palindrome", $mystring & " is palindrome: " & isPalindrome($mystring))
;output is: "In girum imus nocte, et consumimur igni is palindrome: True"
$mystring="Madam, I'm Adam."
MsgBox(0, "Palindrome", $mystring & " is palindrome: " & isPalindrome($mystring))
;output is: "Madam, I'm Adam. is palindrome: True"
$mystring="no salàlas no"
MsgBox(0, "Palindrome", $mystring & " is palindrome: " & isPalindrome($mystring))
;output is: "no salàlas no is palindrome: False"
Func isPalindrome($Str_palindrome)
$palindrome="False"
$Str_palindrome=StringLower($Str_palindrome)
$str_length = StringLen($Str_palindrome)
$new_str="" ;to rebuild string with only alphanumeric characters
For $i = 1 to $str_length
$nth_chr = StringTrimRight(StringRight($Str_palindrome, $i),$i-1)
if StringIsAlpha($nth_chr) Then
$new_str=$new_str & $nth_chr ; add in string if alphabet
EndIf
if StringIsAlNum($nth_chr) Then
$new_str=$new_str & $nth_chr ; add in string if numeric
EndIf
Next
$Str_palindrome=$new_str ;string without punctuations and spaces
$Str_reverse=reverse($Str_palindrome) ;reverse this string
;compare characters from both strings until half string is compared
For $i=1 to $str_length/2
$First=StringLeft($Str_palindrome, 1)
$Last=StringLeft($Str_reverse, 1)
If $First == $Last Then
$palindrome="True"
EndIf
Next
Return $palindrome
EndFunc
; returns reverse of input string
Func reverse($string)
$str_length = StringLen($string)
$rev_str = ""
For $i = 1 to $str_length
$rev_str = $rev_str & StringTrimRight(StringRight($string, $i), $i-1)
Next
Return $rev_str
EndFunc
[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
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] BBC BASIC
test$ = "A man, a plan, a canal: Panama!"
PRINT """" test$ """" ;
IF FNpalindrome(FNletters(test$)) THEN
PRINT " is a palindrome"
ELSE
PRINT " is not a palindrome"
ENDIF
END
DEF FNpalindrome(A$) = (A$ = FNreverse(A$))
DEF FNreverse(A$)
LOCAL B$, P%
FOR P% = LEN(A$) TO 1 STEP -1
B$ += MID$(A$,P%,1)
NEXT
= B$
DEF FNletters(A$)
LOCAL B$, C%, P%
FOR P% = 1 TO LEN(A$)
C% = ASC(MID$(A$,P%))
IF C% > 64 AND C% < 91 OR C% > 96 AND C% < 123 THEN
B$ += CHR$(C% AND &5F)
ENDIF
NEXT
= B$
Output:
"A man, a plan, a canal: Panama!" is a palindrome
[edit] Befunge
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"<
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());
}
Or, checking half is sufficient (on odd-length strings, this will ignore the middle element):
#include <string>
#include <algorithm>
bool is_palindrome(std::string const& s)
{
return std::equal(s.begin(), s.begin()+s.length()/2, 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"));
}
}
Using LINQ operators
using System;
using System.Linq;
class Program
{
static bool IsPalindrome(string text)
{
return text == new String(text.Reverse().ToArray());
}
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] CoffeeScript
isPalindrome = (str) ->
stripped = str.toLowerCase().replace /\W/g, ""
stripped == (stripped.split "").reverse().join ""
Testing it:
strings = [
"In girum imus nocte et consumimur igni"
"A man, a plan, a canal: Panama!"
"There is no spoon."
]
console.log "'#{str}' : #{isPalindrome str}" for str in strings
'In girum imus nocte et consumimur igni' : true 'A man, a plan, a canal: Panama!' : true 'There is no spoon.' : false
[edit] Common Lisp
(defun palindrome-p (s)
(string= s (reverse s)))
[edit] Delphi
uses
SysUtils, StrUtils;
function IsPalindrome(const aSrcString: string): Boolean;
begin
Result := SameText(aSrcString, ReverseString(aSrcString));
end;
[edit] D
[edit] High-level 32-bit Unicode Version
import std.traits, std.algorithm;
bool isPalindrome1(C)(in C[] s) pure /*nothrow*/
if (isSomeChar!C) {
auto s2 = s.dup; // not nothrow
s2.reverse(); // works on Unicode too
return s == s2;
}
void main() {
alias isPalindrome1 pali;
assert(pali(""));
assert(pali("z"));
assert(pali("aha"));
assert(pali("sees"));
assert(!pali("oofoe"));
assert(pali("deified"));
assert(!pali("Deified"));
assert(pali("amanaplanacanalpanama"));
assert(pali("ingirumimusnocteetconsumimurigni"));
assert(pali("salà las"));
}
[edit] Mid-level 32-bit Unicode Version
import std.traits;
bool isPalindrome2(C)(in C[] s) pure if (isSomeChar!C) {
dchar[] dstr;
foreach (dchar c; s) // not nothrow
dstr ~= c;
for (int i; i < dstr.length / 2; i++)
if (dstr[i] != dstr[$ - i - 1])
return false;
return true;
}
void main() {
alias isPalindrome2 pali;
assert(pali(""));
assert(pali("z"));
assert(pali("aha"));
assert(pali("sees"));
assert(!pali("oofoe"));
assert(pali("deified"));
assert(!pali("Deified"));
assert(pali("amanaplanacanalpanama"));
assert(pali("ingirumimusnocteetconsumimurigni"));
assert(pali("salà las"));
}
[edit] Low-level 32-bit Unicode Version
import std.stdio, core.exception, std.traits;
// assume alloca() to be pure for this program
extern(C) pure nothrow void* alloca(in size_t size);
bool isPalindrome3(C)(in C[] s) pure if (isSomeChar!C) {
auto p = cast(dchar*)alloca(s.length * 4);
if (p == null)
// no fallback heap allocation used
throw new OutOfMemoryError();
dchar[] dstr = p[0 .. s.length];
// use std.utf.stride for an even lower level version
int i = 0;
foreach (dchar c; s) { // not nothrow
dstr[i] = c;
i++;
}
dstr = dstr[0 .. i];
foreach (j; 0 .. dstr.length / 2)
if (dstr[j] != dstr[$ - j - 1])
return false;
return true;
}
void main() {
alias isPalindrome3 pali;
assert(pali(""));
assert(pali("z"));
assert(pali("aha"));
assert(pali("sees"));
assert(!pali("oofoe"));
assert(pali("deified"));
assert(!pali("Deified"));
assert(pali("amanaplanacanalpanama"));
assert(pali("ingirumimusnocteetconsumimurigni"));
assert(pali("salà las"));
}
[edit] Low-level ASCII Version
bool isPalindrome4(in string str) pure nothrow {
if (str.length == 0) return true;
immutable(char)* s = str.ptr;
immutable(char)* t = &(str[$ - 1]);
while (s < t)
if (*s++ != *t--) // ugly
return false;
return true;
}
void main() {
alias isPalindrome4 pali;
assert(pali(""));
assert(pali("z"));
assert(pali("aha"));
assert(pali("sees"));
assert(!pali("oofoe"));
assert(pali("deified"));
assert(!pali("Deified"));
assert(pali("amanaplanacanalpanama"));
assert(pali("ingirumimusnocteetconsumimurigni"));
//assert(pali("salà las"));
}
[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] Ela
open Core
let isPalindrome xs = xs == reverse xs
isPalindrome "ingirumimusnocteetconsumimurigni"
Function reverse is taken from Core module and is defined as:
let reverse xs = foldl (flip (::)) (nil xs) xs
let foldl f z (x::xs) = foldl f (f z x) xs
foldl _ z [] = z
This function works for both strings and linked lists (strings in Ela are not lists but indexed immutable arrays, however then can emulate lists when needed).
[edit] Erlang
is_palindrome(String) ->
String == lists:reverse(String).
[edit] Euphoria
function isPalindrome(sequence s)
for i = 1 to length(s)/2 do
if s[i] != s[$-i+1] then
return 0
end if
end for
return 1
end function
[edit] F#
let isPalindrome (s: string) =
let arr = s.ToCharArray()
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] Fantom
class Palindrome
{
// Function to test if given string is a palindrome
public static Bool isPalindrome (Str str)
{
str == str.reverse
}
// Give it a test run
public static Void main ()
{
echo (isPalindrome(""))
echo (isPalindrome("a"))
echo (isPalindrome("aa"))
echo (isPalindrome("aba"))
echo (isPalindrome("abb"))
echo (isPalindrome("salàlas"))
echo (isPalindrome("In girum imus nocte et consumimur igni".lower.replace(" ","")))
}
}
[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
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] GAP
ZapGremlins := function(s)
local upper, lower, c, i, n, t;
upper := "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
lower := "abcdefghijklmnopqrstuvwxyz";
t := [ ];
i := 1;
for c in s do
n := Position(upper, c);
if n <> fail then
t[i] := lower[n];
i := i + 1;
else
n := Position(lower, c);
if n <> fail then
t[i] := c;
i := i + 1;
fi;
fi;
od;
return t;
end;
IsPalindrome := function(s)
local t;
t := ZapGremlins(s);
return t = Reversed(t);
end;
[edit] GML
//Setting a var from an argument passed to the script
str=argument0
//Takes out all spaces/anything that is not a letter or a number and turns uppercase letters to lowercase
str=string_lettersdigits(string_lower(string_replace(str,' ','')));
inv='';
//for loop that reverses the sequence
for (i=0;i<string_length(str);i+=1;)
{
inv=inv+string_copy(str,string_length(str)-i,1);
}
//returns true if the sequence is a palindrome else returns false
if str=inv{check=ture;}else{check=false;}
return(check);
[edit] Go
package pal
func IsPal(s string) bool {
mid := len(s) / 2
last := len(s) - 1
for i := 0; i < mid; i++ {
if s[i] != s[last-i] {
return false
}
}
return true
}
[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
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
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 uses 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] 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] k
is_palindrome:{x~|x}
[edit] LabVIEW
This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
[edit] Liberty BASIC
Print isPalindrome("In girum imus nocte et consumimur igni")
Print isPalindrome("atta")
Function isPalindrome(string$)
string$ = Lower$(removeSpaces$(string$))
reverseString$ = reverseString$(string$)
If string$ = reverseString$ Then isPalindrome = 1
End Function
Function reverseString$(string$)
For i = Len(string$) To 1 Step -1
reverseString$ = reverseString$ + Mid$(string$, i, 1)
Next i
End Function
Function removeSpaces$(string$)
For i = 1 To Len(string$)
If Mid$(string$, i, 1) <> " " Then
removeSpaces$ = removeSpaces$ + Mid$(string$, i, 1)
End If
Next i
End Function
[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
Test numbers:
PalindromeQ[i_Integer] := Reverse[IntegerDigits[i]] == IntegerDigits[i];
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] Maxima
palindromep(s) := block([t], t: sremove(" ", sdowncase(s)), sequal(t, sreverse(t)))$
palindromep("In girum imus nocte et consumimur igni"); /* true */
[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] Mirah
def reverse(s:string)
StringBuilder.new(s).reverse.toString()
end
def palindrome?(s:string)
s.equals(reverse(s))
end
puts palindrome?("anna") # ==> true
puts palindrome?("Erik") # ==> false
puts palindrome?("palindroom-moordnilap") # ==> true
puts nil # ==> null
[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] Nemerle
using System;
using System.Console;
using Nemerle.Utility.NString; //contains methods Explode() and Implode() which convert string -> list[char] and back
module Palindrome
{
IsPalindrome( text : string) : bool
{
Implode(Explode(text).Reverse()) == text;
}
Main() : void
{
WriteLine("radar is a palindrome: {0}", IsPalindrome("radar"));
}
}
And a function to remove spaces and punctuation and convert to lowercase
Clean( text : string ) : string
{
def sepchars = Explode(",.;:-?!()' ");
Concat( "", Split(text, sepchars)).ToLower()
}
[edit] Objeck
bundle Default {
class Test {
function : Main(args : String[]) ~ Nil {
IsPalindrome("aasa")->PrintLine();
IsPalindrome("acbca")->PrintLine();
IsPalindrome("xx")->PrintLine();
}
function : native : IsPalindrome(s : String) ~ Bool {
l := s->Size();
for(i := 0; i < l / 2; i += 1;) {
if(s->Get(i) <> s->Get(l - i - 1)) {
return false;
};
};
return true;
}
}
}
[edit] NetRexx
y='In girum imus nocte et consumimur igni'
-- translation: We walk around in the night and
-- we are burnt by the fire (of love)
say
say 'string = 'y
say
pal=isPal(y)
if pal==0 then say "The string isn't palindromic."
else say 'The string is palindromic.'
method isPal(x) static
x=x.upper().space(0) /* removes all blanks (spaces). */
return x==x.reverse() /* returns 1 if exactly equal, */
[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] PARI/GP
ispal(s)={
s=Vec(s);
for(i=1,#v\2,
if(v[i]!=v[#v-i+1],return(0))
);
1
};
[edit] PHP
<?php
function is_palindrome($string) {
return $string == strrev($string);
}
?>
[edit] 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
There is more than one way to do this.
- palindrome uses the built-in function reverse().
- palindrome_c uses iteration; it is a translation of the C solution.
- palindrome_r uses recursion.
- palindrome_e uses a recursive regular expression.
All of these functions take a parameter, or default to $_ if there is no parameter. None of these functions ignore case or strip characters; if you want do that, you can use ($s = lc $s) =~ s/[\W_]//g before you call these functions.
# Palindrome.pm
package Palindrome;
use strict;
use warnings;
use Exporter 'import';
our @EXPORT = qw(palindrome palindrome_c palindrome_r palindrome_e);
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;
}
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)); }
}
sub palindrome_e
{
(@_ ? shift : $_) =~ /^(.?|(.)(?1)\2)$/ + 0
}
This example shows how to use the functions.
# pbench.pl
use strict;
use warnings;
use Benchmark qw(cmpthese);
use Palindrome;
printf("%d, %d, %d, %d: %s\n",
palindrome, palindrome_c, palindrome_r, palindrome_e, $_)
for
qw/a aa ab abba aBbA abca abba1 1abba
ingirumimusnocteetconsumimurigni/,
'ab cc ba', 'ab ccb a';
printf "\n";
my $latin = "ingirumimusnocteetconsumimurigni";
cmpthese(100_000, {
palindrome => sub { palindrome $latin },
palindrome_c => sub { palindrome_c $latin },
palindrome_r => sub { palindrome_r $latin },
palindrome_e => sub { palindrome_e $latin },
});
This is the output on a machine running Perl 5.10.1 on amd64-openbsd.
$ perl pbench.pl
1, 1, 1, 1: a
1, 1, 1, 1: aa
0, 0, 0, 0: ab
1, 1, 1, 1: abba
0, 0, 0, 0: aBbA
0, 0, 0, 0: abca
0, 0, 0, 0: abba1
0, 0, 0, 0: 1abba
1, 1, 1, 1: ingirumimusnocteetconsumimurigni
1, 1, 1, 1: ab cc ba
0, 0, 0, 0: ab ccb a
(warning: too few iterations for a reliable count)
Rate palindrome_r palindrome_e palindrome_c palindrome
palindrome_r 51020/s -- -50% -70% -97%
palindrome_e 102041/s 100% -- -41% -94%
palindrome_c 172414/s 238% 69% -- -90%
palindrome 1666667/s 3167% 1533% 867% --
With this machine, palindrome() ran far faster than the alternatives (and too fast for a reliable count). The Perl regular expression engine recursed twice as fast as the Perl interpreter.
[edit] Perl 6
sub palin(Str $s --> Bool) {
my @chars = $s.lc.comb(/\w/);
while @chars > 1 {
return False unless @chars.shift eq @chars.pop;
}
return True;
}
my @tests =
"A man, a plan, a canal: Panama.",
"My dog has fleas",
"Madam, I'm Adam.",
"1 on 1",
"In girum imus nocte et consumimur igni";
for @tests { say (palin($_) ?? "Yes" !! "No"),"\t",$_ };
Output:
Yes A man, a plan, a canal: Panama. No My dog has fleas Yes Madam, I'm Adam. No 1 on 1 Yes In girum imus nocte et consumimur igni
One can also just flip the string and compare, but this way minimizes comparisons without resorting to recursion or indexes.
[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
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.
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
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] Racket
(define (palindromb str)
(let* ([lst (string->list (string-downcase str))]
[slst (remove* '(#\space) lst)])
(string=? (list->string (reverse slst)) (list->string slst))))
;;example output
> (palindromb "able was i ere i saw elba")
#t
> (palindromb "waht the hey")
#f
> (palindromb "In girum imus nocte et consumimur igni")
#t
>
[edit] Rascal
import String;
public bool palindrome(str text){ return text == reverse(text);}
[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] Retro
needs hash'
: palindrome? ( $-f ) dup ^hash'hash [ ^strings'reverse ^hash'hash ] dip = ;
"ingirumimusnocteetconsumimurigni" palindrome? putn
[edit] REXX
y='In girum imus nocte et consumimur igni'
/*translation: We walk around in the night and */
/* we are burnt by the fire (of love). */
say
say 'string='y
say
pal=isPal(y)
if pal==0 then say "The string isn't palindromic."
else say 'The string is palindromic.'
say
exit
/*------------------------------------------------------------------*/
isPal: procedure; arg x /*this uppercases the value of arg X. */
/*PARSE ARG X --- wouldn't. */
/*ARG X is equivalent to: */
/*PARSE UPPER ARG X */
x=space(x,0) /*removes all blanks (spaces). */
return x==reverse(x) /*returns 1 if exactly equal, */
/*returns 0 if not. */
/*------------------------------------------------------------------*/
/*also: if x==reverse(x) then return 1 */
/* else return 0 */
/*Note: the exactly equal to (==) must be used instead of */
/* equal to (=) because a string of 0100 */
/* would be equal to +100 */
/* would be equal to 100. */
/* would be equal to 1e2 */
/* would be equal to 1e+2 */
/* would be equal to +1e2 */
/* would be equal to 1e02 */
/* would be equal to _100 */
/* would be equal to 100_ */
/* where _ is a blank. */
Output:
string=In girum imus nocte et consumimur igni The string is palindromic.
[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] Run BASIC
data "My dog has fleas", "Madam, I'm Adam.", "1 on 1", "In girum imus nocte et consumimur igni"Output:
for i = 1 to 4
read w$
print w$;" is ";isPalindrome$(w$);" Palindrome"
next
FUNCTION isPalindrome$(str$)
for i = 1 to len(str$)
a$ = upper$(mid$(str$,i,1))
if (a$ >= "A" and a$ <= "Z") or (a$ >= "0" and a$ <= "9") then b$ = b$ + a$: c$ = a$ + c$
next i
if b$ <> c$ then isPalindrome$ = "not"
My dog has fleas is not Palindrome Madam, I'm Adam. is Palindrome 1 on 1 is not Palindrome In girum imus nocte et consumimur igni is Palindrome
[edit] Scala
Non-recursive
def isPalindrome(s: String) = s == s.reverse
Test
scala> isPalindrome("amanaplanacanalpanama")
res0: Boolean = true
scala> isPalindrome("Test 1,2,3")
res1: Boolean = false
scala> isPalindrome("1 2 1")
res2: Boolean = true
Bonus: Detect and account for odd space and punctuation
def isPalindromeSentence(s: String) = { val p = s.replaceAll("[^\\p{L}]", "").toLowerCase; p == p.reverse }
Test
scala> isPalindromeSentence("A man a plan a canal Panama.")
res3: Boolean = true
Recursive
def isPalindrome(s : String) : Boolean = s match {
case s if s.length > 1 => (s.head == s.last) && isPalindrome(s.slice(1, s.length-1))
case _ => 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 (- (string-length s) 1)))
(or (>= i j)
(and (char=? (string-ref s i) (string-ref s j))
(loop (+ i 1) (- j 1))))))
;; Or:
(define (palindrome? s)
(let loop ((s (string->list s))
(r (reverse (string->list s))))
(or (null? s)
(and (char=? (car s) (car r))
(loop (cdr s) (cdr r))))))
<lang scheme>> (palindrome? "ingirumimusnocteetconsumimurigni")
#t
> (palindrome? "This is not a palindrome")
#f
>
[edit] Seed7
const func boolean: palindrome (in string: stri) is func
result
var boolean: isPalindrome is TRUE;
local
var integer: index is 0;
var integer: length is 0;
begin
length := length(stri);
for index range 1 to length div 2 do
if stri[index] <> stri[length - index + 1] then
isPalindrome := FALSE;
end if;
end for;
end func;
For palindromes where spaces shuld be ignore use:
palindrome(replace("in girum imus nocte et consumimur igni", " ", ""))
[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
isPalindrome := [:aString |
str := (aString select: [:chr| chr isAlphaNumeric]) collect: [:chr | chr asLowercase].
str = str reversed.
].
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.
SequenceableCollection>>isPalindrome
^self reverse = self
[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] TUSCRIPT
$$ MODE TUSCRIPT
pal="ingirumimusnocteetconsumimurigni"
pal_r=TURN(pal)
IF (pal==pal_r) THEN
result=1
ELSE
result=0
ENDIF
SELECT result
CASE "0"
PRINT/ERROR "untrue"
DEFAULT
PRINT "true"
ENDSELECT
Output:
true
[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] VBA
This function uses function Reverse() (or Rreverse()) from Reverse a string, after first stripping spaces from the string using the built-in function Replace and converting it to lower case. It can't handle punctuation (yet).
Public Function isPalindrome(aString as string) as Boolean
dim tempstring as string
tempstring = Lcase(Replace(aString, " ", ""))
isPalindrome = (tempstring = Reverse(tempstring))
End Function
Example:
print isPalindrome("In girum imus nocte et consumimur igni")
True
[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] XPL0
include c:\cxpl\codes; \intrinsic 'code' declarations
string 0; \use zero-terminated strings
func StrLen(Str); \Return number of characters in an ASCIIZ string
char Str;
int I;
for I:= 0 to -1>>1-1 do
if Str(I) = 0 then return I;
func Palindrome(S); \Return 'true' if S is a palindrome
char S;
int L, I;
[L:= StrLen(S);
for I:= 0 to L/2-1 do
if S(I) # S(L-1-I) then return false;
return true;
]; \Palindrome
int Word, I;
[Word:=
["otto", "mary", "ablewasiereisawelba", "ingirumimusnocteetconsumimurigni"];
for I:= 0 to 4-1 do
[Text(0, if Palindrome(Word(I)) then "yes" else "no");
CrLf(0);
];
]
Output:
yes no yes yes
[edit] Yorick
Function is_palindrome meets the task description. Function prep_palindrome demonstrates how to convert an English sentence into a form that can be tested with is_palindrome (by changing case and stripping non-alphabetical characters).
func is_palindrome(str) {
s = strchar(str)(:-1);
return allof(s == s(::-1));
}
func prep_palindrome(str) {
s = strchar(strlower(str));
w = where(s >= 'a' & s <= 'z');
return strchar(s(w));
}
Categories:
- Programming Tasks
- Text processing
- Recursion
- Classic CS problems and programs
- ACL2
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AutoIt
- AWK
- BASIC
- BBC BASIC
- Befunge
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- Delphi
- D
- E
- Ela
- Erlang
- Euphoria
- F Sharp
- Factor
- Fantom
- Forth
- Fortran
- GAP
- GML
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- Ioke
- J
- Java
- JavaScript
- K
- LabVIEW
- Liberty BASIC
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- Maxima
- MAXScript
- Mirah
- MMIX
- Modula-3
- Nemerle
- Objeck
- NetRexx
- OCaml
- Octave
- Oz
- PARI/GP
- PHP
- Pascal
- Perl
- Perl 6
- PicoLisp
- Pike
- PL/I
- PowerBASIC
- Prolog
- PureBasic
- Python
- R
- Racket
- Rascal
- REBOL
- Retro
- REXX
- Ruby
- Run BASIC
- Scala
- Scheme
- Seed7
- Slate
- Smalltalk
- SNOBOL4
- Tcl
- TUSCRIPT
- Ursala
- VBA
- VBScript
- Vedit macro language
- XPL0
- Yorick
- String manipulation
