Palindrome detection: Difference between revisions
Keithpinson (talk | contribs) Undo revision 121824 by Keithpinson (talk) |
Keithpinson (talk | contribs) |
||
Line 1,884: | Line 1,884: | ||
scala> isPalindrome("1 2 1") |
scala> isPalindrome("1 2 1") |
||
res2: Boolean = true</lang> |
res2: Boolean = true</lang> |
||
'''Bonus: Detect and account for odd space and punctuation''' |
|||
<lang scala>def isPalindromeSentence(s: String) = { val p = (s.replaceAll("[^\\p{L}]", "").toLowerCase); p == p.reverse }</lang> |
|||
'''Test''' |
|||
<lang scala>scala> isPalindromeSentence("A man a plan a canal Panama.") |
|||
res3: Boolean = true |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
Revision as of 00:00, 30 September 2011
![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.
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.
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
Concise version reversing the string,: <lang AutoHotkey>IsPalindrome( Str ){ StringLower, str, str str := (RegexReplace(str,"\W+" )) Loop, Parse, Str reversedStr := A_LoopField . ReversedStr Return ( ReversedStr = Str ) }</lang>
AutoIt
<lang 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 </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
BBC BASIC
<lang bbcbasic> 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$</lang>
Output:
"A man, a plan, a canal: Panama!" is a palindrome
Befunge
The following code reads a line from stdin and prints "True" if it is a palindrome, or False" otherwise. <lang befunge>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"<</lang>
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>
Using LINQ operators <lang csharp>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")); } } </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
CoffeeScript
<lang coffeescript>isPalindrome = (str) -> stripped = str.toLowerCase().replace /\W/g, "" stripped == (stripped.split "").reverse().join ""</lang>
Testing it: <lang coffeescript>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</lang>
'In girum imus nocte et consumimur igni' : true 'A man, a plan, a canal: Panama!' : true 'There is no spoon.' : false
Common Lisp
<lang lisp>(defun palindrome-p (s)
(string= s (reverse s)))</lang>
Delphi
<lang Delphi>uses
SysUtils, StrUtils;
function IsPalindrome(const aSrcString: string): Boolean; begin
Result := SameText(aSrcString, ReverseString(aSrcString));
end;</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> Low-level 32-bit Unicode version: <lang d>import std.stdio, core.stdc.stdlib, core.exception;
bool isPalindrome4(T)(const T[] s) {
auto p = cast(dchar*)alloca(s.length * 4); if (p == null) throw new OutOfMemoryError(); dchar[] dstr = p[0 .. s.length];
int i = 0; foreach (dchar c; s) dstr[i++] = c; dstr = dstr[0 .. i];
foreach (j; 0 .. dstr.length / 2) if (dstr[j] != dstr[$ - j - 1]) return false; return true;
}
void main() {
assert(isPalindrome4("")); assert(isPalindrome4("z")); assert(isPalindrome4("aha")); assert(isPalindrome4("sees")); assert(!isPalindrome4("oofoe")); assert(isPalindrome4("deified")); assert(!isPalindrome4("Deified")); assert(isPalindrome4("amanaplanacanalpanama")); assert(isPalindrome4("ingirumimusnocteetconsumimurigni")); assert(isPalindrome4("salàlas"));
}</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>
Euphoria
<lang 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</lang>
F#
<lang fsharp>let isPalindrome (s: string) =
let arr = s.ToCharArray() 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>
Fantom
<lang 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(" ",""))) }
} </lang>
Forth
<lang 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 ;
</lang>
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 .
Fortran
<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 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</lang>
<lang fortran>end program palindro</lang>
GAP
<lang 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;</lang>
GML
<lang go> //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); </lang>
Go
<lang 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
}</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
<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 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. <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>
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>
Note that while these recursive verbs are bulkier and more complicated, they are also several thousand times more inefficient than isPalin0.
<lang j> 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</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>
k
<lang k>is_palindrome:{x~|x}</lang>
Liberty BASIC
<lang lb>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</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>
Test numbers:
PalindromeQ[i_Integer] := Reverse[IntegerDigits[i]] == IntegerDigits[i];
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>
MATLAB
<lang 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</lang>
Sample Usage: <lang MATLAB>>> isPalindrome('In girum imus nocte et consumimur igni')
ans =
1
</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>
Mirah
<lang 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</lang>
MMIX
<lang 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)</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>
Nemerle
<lang 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")); }
}</lang> And a function to remove spaces and punctuation and convert to lowercase <lang Nemerle>Clean( text : string ) : string {
def sepchars = Explode(",.;:-?!()' "); Concat( "", Split(text, sepchars)).ToLower()
}</lang>
Objeck
<lang 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; } }
} </lang>
NetRexx
<lang 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, */
</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>
PARI/GP
<lang>ispal(s)={
s=Vec(s); for(i=1,#v\2, if(v[i]!=v[#v-i+1],return(0)) ); 1
};</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
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.
<lang perl># 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
}</lang>
This example shows how to use the functions.
<lang perl># 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 },
});</lang>
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.
Perl 6
<lang perl6>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",$_ };</lang> 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.
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
Racket
<lang 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
> </lang>
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"]
Retro
<lang Retro> needs hash'
- palindrome? ( $-f ) dup ^hash'hash [ ^strings'reverse ^hash'hash ] dip = ;
"ingirumimusnocteetconsumimurigni" palindrome? putn </lang>
REXX
<lang 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. */
</lang> Output:
string=In girum imus nocte et consumimur igni The string is palindromic.
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>
Bonus: Detect and account for odd space and punctuation
<lang scala>def isPalindromeSentence(s: String) = { val p = (s.replaceAll("[^\\p{L}]", "").toLowerCase); p == p.reverse }</lang>
Test <lang scala>scala> isPalindromeSentence("A man a plan a canal Panama.") res3: Boolean = true
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 (- (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
></lang>
Seed7
<lang 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;</lang>
For palindromes where spaces shuld be ignore use: <lang seed7>palindrome(replace("in girum imus nocte et consumimur igni", " ", ""))</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>
SNOBOL4
<lang 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</lang>
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
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>
TUSCRIPT
<lang 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 </lang> Output:
true
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>
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).
<lang yorick>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));
}</lang>
- Programming Tasks
- Text processing
- Recursion
- Classic CS problems and programs
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AutoIt
- AWK
- BASIC
- BBC BASIC
- Befunge
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- Delphi
- D
- E
- Erlang
- Euphoria
- F Sharp
- Factor
- Fantom
- Forth
- Fortran
- GAP
- GML
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- Ioke
- J
- Java
- JavaScript
- K
- Liberty BASIC
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- 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
- REBOL
- Retro
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- Slate
- Smalltalk
- SNOBOL4
- Tcl
- TUSCRIPT
- Ursala
- VBScript
- Vedit macro language
- Yorick
- String manipulation