/* 

  Jewels and stones (Rosetta code) in Picat.

  
  http://rosettacode.org/wiki/Jewels_and_stones
  """
  Task

  Create a function which takes two string parameters: 'stones' and 'jewels' and 
  returns an integer.

  Both strings can contain any number of upper or lower case letters. However, in the case of 
  'jewels', all letters must be distinct.

  The function should count (and return) how many 'stones' are 'jewels' or, in other words, 
  how many letters in 'stones' are also letters in 'jewels'.


  Note that:

  - Only letters in the ISO basic Latin alphabet i.e. 'A to Z' or 'a to z' need be considered.
  - A lower case letter is considered to be different from its upper case equivalent for this 
    purpose, i.e., 'a' != 'A'.
  - The parameters do not need to have exactly the same names.
  - Validating the arguments is unnecessary. 

  So, for example, if passed "aAAbbbb" for 'stones' and "aA" for 'jewels', the function should return 3.

  This task was inspired by this problem. [https://leetcode.com/problems/jewels-and-stones/description/]
  """

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

*/

import util.

main => go.

% list comprehension
jewels_and_stones1(Jewels,Stones) = sum([1 : S in Stones, J in Jewels, S == J]).

% recursion
jewels_and_stones2(Jewels,Stones) = N =>
  jewels_and_stones2(Jewels,Stones,0,N).

jewels_and_stones2([],_Stones,N,N).
jewels_and_stones2([J|Jewels],[S|Stones],N0,N) :-
  jewels_and_stones2_(J,[S|Stones],0,JN),
  jewels_and_stones2(Jewels,Stones,N0+JN,N).

% Check just this jewel on all the stones
jewels_and_stones2_(_J,[],N,N).
jewels_and_stones2_(J,[S|Stones],N0,N) :-
  ( J == S ->
     N1 = N0+1
    ;
    N1 = N0
  ),
  jewels_and_stones2_(J,Stones,N1,N).

% loop
jewels_and_stones3(Jewels,Stones) = N =>
  N = 0,
  foreach(J in Jewels, S in Stones)
     if J == S then
       N := N + 1
     end
  end.

go =>
  Tests = [["aA","aAAbbbb"],
           ["z","ZZ"]
           ],
  println(tests=Tests),
  foreach([Jewels,Stones] in Tests)
    println([jewels=Jewels,stone=Stones]),
    println(js1=jewels_and_stones1(Jewels,Stones)),
    println(js2=jewels_and_stones2(Jewels,Stones)),
    println(js3=jewels_and_stones3(Jewels,Stones)),
    nl
  end,

  nl.
go => true.

/*  
  NumStones: 100_000_000  NumJewels = 5
js1 = 7688786

CPU time 6.925 seconds.

js2 = 7688786

CPU time 3.995 seconds.

js3 = 7688786

CPU time 4.36 seconds.

 Recursion is a little faster.

  NumStones: 100_000_000  NumJewels = 15
jewels = TwurtRabSXx
js1 = 21154798

CPU time 15.087 seconds.

js2 = 21154796

CPU time 11.024 seconds.

js3 = 21154798

CPU time 11.94 seconds.


*/
go2 ?=>
  Alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
  Len = Alpha.len,
  % _ = random2(),
  NumStones = 100_000_000,
  NumJewels = 15, % Atmost number of jewels (duplicates are removed)
  
  Stones = [Alpha[random(1,Len)] : _ in 1..NumStones],
  Jewels = [Alpha[random(1,Len)] : _ in 1..NumJewels].sort_remove_dups,
  println(jewels=Jewels),
  
  time(println(js1=jewels_and_stones1(Jewels,Stones))),
  time(println(js2=jewels_and_stones2(Jewels,Stones))),
  time(println(js3=jewels_and_stones3(Jewels,Stones))),


  nl.
go2 => true.