/*

  Palindrome detection in Picat.

  http://rosettacode.org/wiki/Palindrome_detection
  """
  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). 
  """

  Extra:
  gen/1-2 and gen2/1-2 are both generate palindromes and palindrome checking.
  

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import v3_utils.

main => go.

go ?=>
   Strings = ["In girum imus nocte et consumimur igni", 
              "this is a non palindrome string",
              "anna ABcdcBA anna",
              "anna ABcdcBA annax",
              "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!",
              10,
              11,
              111111,
              12221,
              9384212
           ],

   foreach(S in Strings) 
     if is_palindrome(S) then
        println([S, "yes"])
     else
        println([S, "no"])
     end
   end,
   nl.
go => true.

%
% Generating all (lowercase) palindromes of a certain length
%
go2 ?=>
  Alpha = "abcdefghijklmnopqrstuvwxyz",
  between(1,10,Len),
  length(L,Len),
  foreach(I in 1..Len)
    member(L[I],Alpha)
  end,
  L == L.reverse,
  println(palin=L),
  fail,
  nl.

go2 => true.

%
% Count the number of palindromes of a certain length
%
go3 ?=>
  foreach(Len in 1..10)
    time(C = count_all(gen(Len,_L))),
    println(Len=C)
  end,  
  nl.
go3 => true.

go4 ?=>
  between(1,7,Len),
  println(len=Len),
  length(L,Len),
  gen_number(L),
  N = L.to_int,
  println(N),
  fail,
  nl.
go4 => true.


%
% Generate alphanumeric palindromes
%
go5 ?=>
  length(L,5),
  gen2(L),
  println(L),
  fail,
  nl.
go5 => true.

%
% And we're back to the problem at hand, i.e. palindrome detection.
%
go6 ?=>
   Strings = ["In girum imus nocte et consumimur igni", 
              "this is a non palindrome string",
              "anna ABcdcBA anna",
              "anna ABcdcBA annax",
              "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!",
              10,
              11,
              111111,
              12221,
              9384212
           ],
   foreach(S in Strings)
     if gen2(strip2(S.to_string)) then
        println(S=yes)
     else
        println(S=no)
     end 
   end,
   nl.
go6 => true.  


%
% Generate all palindromic DNA codes of length 1..10
%  
go7 ?=>
  between(1,10,Len),
  length(L,Len),
  gen2(L,"ACGT"),
  println(L),
  fail,
  nl.
go7 => true.


% Testing genp/1
go8 ?=>
   Len=4,
   length(X,Len),
   genp(X),
   println(X.to_int),
   fail,
   nl.
go8 => true.

%
% Generates palindromic strings
%
gen(Len,L) =>
  Chars = "abcdefghijklmnopqrstuvwxyz",
  % Chars = "0123456789",  
  length(L,Len),
  foreach(I in 1..Len)
    member(L[I],Chars)
  end,
  L == L.reverse.

%
% Generate and checks for palindromic digits
% This is reversible.
%
gen_number(N),number(N) => gen_number(N.to_string()).
gen_number(L) =>
  Digits = "0123456789",
  (var(L) -> member(Len,1..10) ; true),
  length(L,Len),
  foreach(I in 1..Len)
    member(L[I],Digits)
  end,
  no_leading_zeros(L),
  L == L.reverse.
% Oh, this is a hack!
no_leading_zeros([]).
no_leading_zeros([0]).
no_leading_zeros(['0']).
no_leading_zeros([H|T]) :-
  H != '0',
  H != 0,  
  no_leading_zeros(T).



%
% Generate and check for palindromic strings
%
gen2(L) =>
  gen2(L,"abcdefghijklmnopqrstuvwxyz0123456789").
gen2(N,Chars),number(N) => gen2(N.to_string(),Chars).  
gen2(L,Chars) =>
  length(L,Len),
  foreach(I in 1..Len)
    member(L[I],Chars)
  end,
  L == L.reverse.  



is_palindrome(N), number(N) => is_palindrome(N.to_string()).
is_palindrome(S) =>
    S2 = strip2(S),
    S2 == S2.reverse().

% lowercase and strip everything except a..z0..9
strip(S) = V =>
   V = [],
   Alpha = "abcdefghijklmnopqrstuvwxyz0123456789",
   foreach(C in S.to_lowercase()) 
      if member(C,Alpha) then
         V := V ++ [C]
      end
   end.

% Using list comprehension instead.
% Must use the helper predicate in2/2 since it don't work to have
%   Val in List as a condition.
% strip2(S) = [C : C in S.to_lowercase(), C.in2("abcdefghijklmnopqrstuvwxyz")].
% in2(Val, List) => membchk(Val, List).

strip2(S) = [C : C in S.to_lowercase(), C.membchk("abcdefghijklmnopqrstuvwxyz0123456789")].

%
% Prolog approach
%
genp(N) :-
  number(N),
  number_chars(N,C),
  genp(C).
genp(L) :-
  list(L),
  Digits = "0123456789",
  mem(L,Digits),
  no_leading_zeros(L),
  reverse(L,L).  
mem([],_Chars).
mem([H|T],Chars) :-
   member(H,Chars),
   mem(T,Chars).

% This is just to generate a digit list
genp2(N) :-
  number(N),
  number_chars(N,C),
  genp2(C).
genp2(L) :-
  list(L),
  Digits = "0123456789",
  mem(L,Digits).