Palindrome detection: Difference between revisions
(→{{header|Haskell}}: fix <code> tag for haskell) |
m (Fixed code tags) |
||
Line 28: | Line 28: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<ada> |
<code ada> |
||
function Palindrome (Text : String) return Boolean is |
function Palindrome (Text : String) return Boolean is |
||
begin |
begin |
||
Line 38: | Line 38: | ||
return True; |
return True; |
||
end Palindrome; |
end Palindrome; |
||
</ |
</code> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Line 48: | Line 48: | ||
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). |
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). |
||
<c>#include <string.h> |
<code c>#include <string.h> |
||
int palindrome(const char *s) |
int palindrome(const char *s) |
||
Line 59: | Line 59: | ||
} |
} |
||
return 1; |
return 1; |
||
}</ |
}</code> |
||
More idiomatic version: |
More idiomatic version: |
||
<c>int palindrome(const char *s) |
<code c>int palindrome(const char *s) |
||
{ |
{ |
||
const char *t; /* t is a pointer that traverses backwards from the end */ |
const char *t; /* t is a pointer that traverses backwards from the end */ |
||
Line 70: | Line 70: | ||
} |
} |
||
return 1; |
return 1; |
||
}</ |
}</code> |
||
===Recursive=== |
===Recursive=== |
||
Line 77: | Line 77: | ||
itself a palindrome. |
itself a palindrome. |
||
<c>int palindrome_r(const char *s, int b, int e) |
<code c>int palindrome_r(const char *s, int b, int e) |
||
{ |
{ |
||
if ( e <= 1 ) return 1; |
if ( e <= 1 ) return 1; |
||
if ( s[b] != s[e-1] ) return 0; |
if ( s[b] != s[e-1] ) return 0; |
||
return palindrome_r(s, b+1, e-1); |
return palindrome_r(s, b+1, e-1); |
||
}</ |
}</code> |
||
===Testing=== |
===Testing=== |
||
<c>#include <stdio.h> |
<code c>#include <stdio.h> |
||
#include <string.h> |
#include <string.h> |
||
/* testing */ |
/* testing */ |
||
Line 100: | Line 100: | ||
t, palindrome_r(t, 0, l) ? "" : "n't"); |
t, palindrome_r(t, 0, l) ? "" : "n't"); |
||
return 0; |
return 0; |
||
}</ |
}</code> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
The C solutions also work in C++, but C++ allows a simpler one: |
The C solutions also work in C++, but C++ allows a simpler one: |
||
<cpp> |
<code cpp> |
||
#include <string> |
#include <string> |
||
#include <algorithm> |
#include <algorithm> |
||
Line 112: | Line 112: | ||
return std::equal(s.begin(), s.end(), s.rbegin()); |
return std::equal(s.begin(), s.end(), s.rbegin()); |
||
} |
} |
||
</ |
</code> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
<pre> |
|||
: palindrome? ( caddr len -- ? ) |
|||
1- bounds |
|||
begin 2dup > |
|||
while over c@ over c@ = |
|||
while over c@ over c@ = |
|||
while 1+ swap 1- swap |
|||
repeat 2drop false |
|||
repeat 2drop false |
|||
else 2drop true |
|||
then ; |
|||
</pre> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 166: | Line 168: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
===Non-Recursive=== |
===Non-Recursive=== |
||
<java>public static boolean pali(String testMe){ |
<code java>public static boolean pali(String testMe){ |
||
StringBuilder sb = new StringBuilder(testMe); |
StringBuilder sb = new StringBuilder(testMe); |
||
return sb.toString().equalsIgnoreCase(sb.reverse().toString()); |
return sb.toString().equalsIgnoreCase(sb.reverse().toString()); |
||
}</ |
}</code> |
||
===Recursive=== |
===Recursive=== |
||
<java>public static boolean rPali(String testMe){ |
<code java>public static boolean rPali(String testMe){ |
||
if(testMe.length()<=1){ |
if(testMe.length()<=1){ |
||
return true; |
return true; |
||
Line 179: | Line 181: | ||
} |
} |
||
return rPali(testMe.substring(1, testMe.length()-1)); |
return rPali(testMe.substring(1, testMe.length()-1)); |
||
}</ |
}</code> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
<pre> |
|||
to palindrome? :w |
|||
output equal? :w reverse :w |
|||
end |
|||
</pre> |
|||
=={{header|MAXScript}}== |
=={{header|MAXScript}}== |
||
Line 220: | Line 224: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<ocaml>let is_palindrome str = |
<code ocaml>let is_palindrome str = |
||
let last = String.length str - 1 in |
let last = String.length str - 1 in |
||
try |
try |
||
Line 229: | Line 233: | ||
(true) |
(true) |
||
with Exit -> |
with Exit -> |
||
(false)</ |
(false)</code> |
||
and here a function to remove the white spaces in the string: |
and here a function to remove the white spaces in the string: |
||
<ocaml>let rem_space str = |
<code ocaml>let rem_space str = |
||
let len = String.length str in |
let len = String.length str in |
||
let res = String.create len in |
let res = String.create len in |
||
Line 246: | Line 250: | ||
aux (i+1) (j+1) |
aux (i+1) (j+1) |
||
in |
in |
||
aux 0 0</ |
aux 0 0</code> |
||
and to make the test case insensitive, just use the function <code>String.lowercase</code>. |
and to make the test case insensitive, just use the function <code>String.lowercase</code>. |
||
Line 258: | Line 262: | ||
the same as the original word (this is the definition of a palindrome). |
the same as the original word (this is the definition of a palindrome). |
||
<perl>sub palindrome |
<code perl>sub palindrome |
||
{ |
{ |
||
my $s = shift; |
my $s = shift; |
||
Line 272: | Line 276: | ||
} |
} |
||
return 1; |
return 1; |
||
}</ |
}</code> |
||
===Recursive=== |
===Recursive=== |
||
<perl>sub palindrome_r |
<code perl>sub palindrome_r |
||
{ |
{ |
||
my $s = shift; |
my $s = shift; |
||
Line 282: | Line 286: | ||
elsif (substr($s, 0, 1) ne substr($s, -1, 1)) { return 0; } |
elsif (substr($s, 0, 1) ne substr($s, -1, 1)) { return 0; } |
||
else { return palindrome_r(substr($s, 1, -1)); } |
else { return palindrome_r(substr($s, 1, -1)); } |
||
}</ |
}</code> |
||
===Testing=== |
===Testing=== |
||
<perl>sub mtest |
<code perl>sub mtest |
||
{ |
{ |
||
my ( $t, $func ) = @_; |
my ( $t, $func ) = @_; |
||
Line 297: | Line 301: | ||
mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c; |
mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c; |
||
exit;</ |
exit;</code> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 307: | Line 311: | ||
but right syntax <tt>string[::-1]</tt>) |
but right syntax <tt>string[::-1]</tt>) |
||
<python>def is_palindrome(s): |
<code python>def is_palindrome(s): |
||
return s == s[::-1]</ |
return s == s[::-1]</code> |
||
===Recursive=== |
===Recursive=== |
||
<python>def is_palindrome_r(s): |
<code python>def is_palindrome_r(s): |
||
if len(s) <= 1: |
if len(s) <= 1: |
||
return True |
return True |
||
Line 318: | Line 322: | ||
return False |
return False |
||
else: |
else: |
||
return is_palindrome_r(s[1:-1])</ |
return is_palindrome_r(s[1:-1])</code> |
||
===Testing=== |
===Testing=== |
||
<python>p = "ingirumimusnocteetconsumimurigni" |
<code python>p = "ingirumimusnocteetconsumimurigni" |
||
print "'" + p + "' is palindrome? ", is_palindrome(p) |
print "'" + p + "' is palindrome? ", is_palindrome(p) |
||
print "'" + p + "' is palindrome? ", is_palindrome_r(p)</ |
print "'" + p + "' is palindrome? ", is_palindrome_r(p)</code> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Line 331: | Line 335: | ||
===Non-recursive=== |
===Non-recursive=== |
||
<ruby>def is_palindrome(s) |
<code ruby>def is_palindrome(s) |
||
s == s.reverse |
s == s.reverse |
||
end</ |
end</code> |
||
===Recursive=== |
===Recursive=== |
||
<ruby>def is_palindrome_r(s) |
<code ruby>def is_palindrome_r(s) |
||
if s.length <= 1 |
if s.length <= 1 |
||
true |
true |
||
Line 345: | Line 349: | ||
is_palindrome_r(s[1..-2]) |
is_palindrome_r(s[1..-2]) |
||
end |
end |
||
end</ |
end</code> |
||
===Testing=== |
===Testing=== |
||
<ruby>p = "ingirumimusnocteetconsumimurigni" |
<code ruby>p = "ingirumimusnocteetconsumimurigni" |
||
print "'" + p + "' is palindrome? ", is_palindrome(p), "\n" |
print "'" + p + "' is palindrome? ", is_palindrome(p), "\n" |
||
print "'" + p + "' is palindrome? ", is_palindrome_r(p), "\n"</ |
print "'" + p + "' is palindrome? ", is_palindrome_r(p), "\n"</code> |
Revision as of 23:49, 24 January 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Write at least one function/method (or whatever it is called in your preferred language) to check if a sequence of characters (or bytes) is a palindrome or not. The function must return a boolean value (or something that can be used as boolean value, like an integer).
It is not mandatory to write also an example code that uses the function, unless its usage could be not clear (e.g. the provided recursive C solution needs explanation on how to call the function).
It is not mandatory to handle properly encodings (see String length), i.e. it is admissible that the function does not recognize 'salàlas' as palindrome.
The function must not ignore spaces and punctuations. The compliance to the aforementioned, strict or not, requirements completes the task.
An example of latin palindrome is the sentence "In girum imus nocte et consumimur igni", roughly translated as: we walk around in the night and we are burnt by the fire (of love). To do your test with it, you must make it all the same case and strip spaces.
It might be useful for this task to know how to reverse a string.
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;
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;
}
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());
}
Forth
: palindrome? ( caddr len -- ? ) 1- bounds begin 2dup > while over c@ over c@ = while 1+ swap 1- swap repeat 2drop false else 2drop true then ;
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
J
Non-recursive
Reverse and match method
rmP=: -: |.
example
rmP ;;: tolower 'In girum imus nocte et consumimur igni' 1
Recursive
tacit and explicit verbs:
sPt=:0:`($:@(}.@}:))@.({.={:)`1:@.(1>:#) sPx=: 3 : 0 if. 1>:#y do. 1 return. end. if. ({.={:)y do. sPx }.}:y else. 0 end. )
Java
Non-Recursive
public static boolean pali(String testMe){
StringBuilder sb = new StringBuilder(testMe);
return sb.toString().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));
}
Logo
to palindrome? :w output equal? :w reverse :w end
MAXScript
Non-recursive
fn isPalindrome s = ( local reversed = "" for i in s.count to 1 by -1 do reversed += s[i] local 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)
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
.
Perl
Non-recursive
One solution (palindrome_c) is the same as the C non-recursive solution palindrome; while Perl palindrome sub uses the idea that a word is a palindrome if, once reverted, it looks the same as the original word (this is the definition of a palindrome).
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;
}
Recursive
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)); }
}
Testing
sub mtest
{
my ( $t, $func ) = @_;
printf("sequence \"%s\" is%s palindrome\n",
$t, &$func($t) ? "" : "n't");
}
mtest "ingirumimusnocteetconsumimurigni", \&palindrome;
mtest "ingirumimusnocteetconsumimurigni", \&palindrome_r;
mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c;
exit;
Python
Non-recursive
This one uses the reversing the string technique (to revert 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])
Testing
p = "ingirumimusnocteetconsumimurigni"
print "'" + p + "' is palindrome? ", is_palindrome(p)
print "'" + p + "' is palindrome? ", is_palindrome_r(p)
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
p = "ingirumimusnocteetconsumimurigni"
print "'" + p + "' is palindrome? ", is_palindrome(p), "\n"
print "'" + p + "' is palindrome? ", is_palindrome_r(p), "\n"