Palindrome detection

Palindrome detection
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

<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>

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>

1. 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>

1. include <string>
2. include <algorithm>

bool is_palindrome(std::string const& s) {

 return std::equal(s.begin(), s.end(), s.rbegin());

} </lang>

Forth

: palindrome? ( caddr len -- ? )
  1- bounds
  begin  2dup >
  while  over c@ over c@ =
  while  1+ swap 1- swap
  repeat 2drop false
  else   2drop true
  then ;

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>

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

<lang java> public static boolean pali(String testMe){ StringBuilder sb = new StringBuilder(testMe); return sb.toString().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>

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)

Modula-3

<lang modula3> MODULE Palindrome;

IMPORT Text;

PROCEDURE isPalindrome(string: TEXT): BOOLEAN =

 VAR len := Text.Length(string);
 BEGIN
   FOR i := 0 TO len DIV 2 - 1 DO
     IF Text.GetChar(string, i) # Text.GetChar(string, (len - i - 1)) THEN
       RETURN FALSE;
     END;
   END;
   RETURN TRUE;
 END isPalindrome;

END Palindrome. </lang>

OCaml

<lang ocaml>let is_palindrome str =

 let last = String.length str - 1 in
 try
   for i = 0 to last / 2 do
     let j = last - i in
     if str.[i] <> str.[j] then raise Exit
   done;
   (true)
 with Exit ->
   (false)

</lang>

and here a function to remove the white spaces in the string:

<lang ocaml>let rem_space str =

 let len = String.length str in
 let res = String.create len in
 let rec aux i j =
   if i >= len
   then (String.sub res 0 j)
   else match str.[i] with
   | ' ' | '\n' | '\t' | '\r' ->
       aux (i+1) (j)
   | _ ->
       res.[j] <- str.[i];
       aux (i+1) (j+1)
 in
 aux 0 0

</lang>

and to make the test case insensitive, just use the function String.lowercase.

Perl

Non-recursive

One solution (palindrome_c) is the same as the C non-recursive solution palindrome; while Perl palindrome sub uses the idea that a word is a palindrome if, once reverted, it looks the same as the original word (this is the definition of a palindrome).

<lang perl>sub palindrome {

 my $s = shift;
 return $s eq reverse $s;

}

sub palindrome_c {

 my $s = shift;
 for my $i (0 .. length($s) >> 1)
 {
    return 0 unless substr($s, $i, 1) eq substr($s, -1-$i, 1);
 }
 return 1;

} </lang>

Recursive

<lang perl>sub palindrome_r {

 my $s = shift;
 if (length $s <= 1) { return 1; }
 elsif (substr($s, 0, 1) ne substr($s, -1, 1)) { return 0; }
 else { return palindrome_r(substr($s, 1, -1)); }

} </lang>

Testing

<lang perl>sub mtest {

  my ( $t, $func ) = @_;
  printf("sequence \"%s\" is%s palindrome\n",
          $t, &$func($t) ? "" : "n't");

} mtest "ingirumimusnocteetconsumimurigni", \&palindrome; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_r; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c;

exit; </lang>

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])

<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>

Testing

<lang python>p = "ingirumimusnocteetconsumimurigni" print "'" + p + "' is palindrome? ", is_palindrome(p) print "'" + p + "' is palindrome? ", is_palindrome_r(p) </lang>

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

<lang ruby> p = "ingirumimusnocteetconsumimurigni" print "'" + p + "' is palindrome? ", is_palindrome(p), "\n" print "'" + p + "' is palindrome? ", is_palindrome_r(p), "\n" </lang>