/* 

  emirps in Picat.

  https://challenges.wolfram.com/challenge/emirps-is-primes-backward
  """
  Emirps Is Primes Backward

  An "emirp" is a prime number that yields a different prime number when its 
  digits are reversed. Write a function that outputs all emirps less than or 
  equal to a given positive integer.

  Mathematicians have given a silly name to any prime number that produces a 
  different prime number when it is written backward: an 'emirp'.

  One example is the number 13, since both 13 and 31 are prime.

  Although 313 is prime, it is not an emirp because it does not produce a 
  different prime when its digits are written backward.
  """

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

*/

import util.
import v3_utils.

main => go.

%
% 0.105s
% 
go ?=>
  println(emirps(100_000)),
  nl.
go => true.

%
% 0.169s (slowest)
%
go2 ?=>
  N = 100_000,
  emirps(N,P),
  println(P),
  nl.
go2 => true.

%
% 0.097s (fastest)
%
go3 ?=>
  N = 100_000,
  emirps2(N,P),
  println(P),
  nl.
go3 => true.

%
% Generate an endless stream of emirps.
% (Using the 'length trick')
%
go4 ?=>
  length(L,N),
  emirp(N),
  println(N),
  flush(stdout),
  fail,
  nl.
go4 => true.


%
% Loop approach
%
emirps(N) = P =>
  P = [],
  foreach(I in 1..N)
     if emirp(I) then
        P := P ++ [I]
     end
  end.

%
% LP approach
%
emirps(N,P) :-
  emirps(1,N,P).
emirps(N,N,[]).
emirps(I,N,[I|P]) :-
  I < N,
  emirp(I),
  emirps(I+1,N,P).
emirps(I,N,P) :-
  I < N,
  \+ emirp(I),
  emirps(I+1,N,P).

%
% combining last two clauses in emirps/3
%
emirps2(N,P) :-
  emirps2(1,N,P).
emirps2(N,N,[]) :- !.
emirps2(I,N,PP) :-
  I < N,
  (emirp(I) ->
     PP = [I|P]
  ;
     PP = P
  ),
  emirps2(I+1,N,P).

% 
% emirp(N)
% is N an emirp?
%
emirp(N) =>
  prime(N),
  M = N.to_string.reverse.to_int,
  M != N,
  prime(M).