/* 

  Optimal different number of password digits in Picat.

  From
  http://mindyourdecisions.com/blog/2015/06/09/with-apples-new-6-digit-passcode-repeating-a-digit-might-increase-security/
  """
  ...
  Conclusion
  When you make a 6-digit passcode, you should consider repeating a digit once so it 
  makes it harder to guess.

  Here are the total number of 6 digit passcodes you can make, using a certain number of digits.
  ...
  """

  With a password of length 6:
  6 known digits: 720
  5 known digits: 1800 <-
  4 known digits: 1560
  3 known digits: 540
  2 known digits: 62
  1 known digits: 1

  Interestingly, with a password of 9, 8 and 7 digits it's optimal to repeat two digits.

  With 9 digits:
  9 known digits: 362880
  8 known digits: 1451520
  7 known digits: 2328480 <--
  6 known digits: 1905120
  5 known digits: 834120
  4 known digits: 186480
  3 known digits: 18150
  2 known digits: 510
  1 known digits: 1

  8 digits:
  8 known digits: 40320
  7 known digits: 141120
  6 known digits: 191520 <--
  5 known digits: 126000
  4 known digits: 40824
  3 known digits: 5796
  2 known digits: 254
  1 known digits: 1

  7 digits:
  7 known digits: 5040
  6 known digits: 15120
  5 known digits: 16800 <--
  4 known digits: 8400
  3 known digits: 1806
  2 known digits: 126
  1 known digits: 1

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

*/


import cp.

main => go.


go =>
  N = 6, % There are 6 digits

  % We know M digits: How many combinations are there?
  test_n(N),

  nl.


%
% With 8 digits:
% 8 known digits: 40320
% 7 known digits: 141120
% 6 known digits: 191520 <--
% 5 known digits: 126000
% 4 known digits: 40824
% 3 known digits: 5796
% 2 known digits: 254
% 1 known digits: 1

% With 7 digits:
% 7 known digits: 5040
% 6 known digits: 15120
% 5 known digits: 16800 <--
% 4 known digits: 8400
% 3 known digits: 1806
% 2 known digits: 126
% 1 known digits: 1

% With 5 digits:
% 5 known digits: 120
% 4 known digits: 240 <--
% 3 known digits: 150
% 2 known digits: 30
% 1 known digits: 1

% 4 digits:
% 4 known digits: 24
% 3 known digits: 36 <--
% 2 known digits: 14
% 1 known digits: 1


go2 =>
  garbage_collect(250_000_000),

  % We know M digits: How many combinations are there?  
  foreach(N in 8..-1..1) 
    test_n(N),
    nl
  end,

  nl.


% testing alternative ways of counting the 
% solutions. 
go3 =>
  N = 8, % There are N digits
  Map = get_global_map(),
  garbage_collect(200_000_000),
  % We know M digits: How many combinations are there?
  foreach(M in N..-1..1) 
    Map.put(counter,0),
    % check2(N,M,Map),
    (check3(N,M,Map) ; true),
    Len = Map.get(counter),
    printf("%d known digits: %d\n", M,Len)
  end,

  nl.

test_n(N) =>
  garbage_collect(230_000_000),
  printf("N: %d\n", N),
  % We know M digits: How many combinations are there?  
  Res = [],
  foreach(M in N..-1..1) 
    check(N,M,All),
    Len = All.len,
    printf("%d known digits: %d\n", M,Len),
    Res := Res ++ [Len]
  end,
  Max = max(Res),
  Best = [ Pos : Pos in 1..N, Res[Pos] = Max],
  Rev = N..-1..1,
  printf("Best: with %w different digits\n", [Rev[B] : B in Best]), 
  nl.

%
% the main constraint
%
check(N,M,All) =>

  X = new_list(N),
  X :: 1..M, % We know M digits
  % nvalue(M,X), % built-in
  nvalue2(M,X), % faster in this context
  All = solve_all([min,split],X).

%
% testing alternatives to solve_all/2
%
check2(N,M,Map) =>
  X = new_list(N),
  X :: 1..M, % We know M digits
  % nvalue(M,X), % built-in
  nvalue2(M,X), % faster in this context
  (
    (
    solve([max,split],X),
    Map.put(counter,Map.get(counter)+1),
    fail
    )
    ;
    true
  ).

check3(N,M,Map) =>
  X = new_list(N),
  X :: 1..M, % We know M digits
  % nvalue(M,X), % built-in
  nvalue2(M,X), % faster in this context
  solve([max,split],X),
  Map.put(counter,Map.get(counter)+1),
  fail.



%
% nvalue(?N,?X)
%
% Requires that there are N distinct values in X.
%
% Note: This is faster (in this context) than the built-in nvalue/2.
%
nvalue2(N, X) =>
   [Min, Max] = fd_min_max_array(X),
   N #= sum([ (sum([ (X[J] #= I) : J in 1..X.length]) #> 0) : I in Min..Max]).

% Get Min and Max for an array/list
fd_min_max_array(X) = [Min,Max] =>
   Max = fd_max(X[1]),
   Min = fd_min(X[1]),
   foreach(Y in X) 
      if fd_min(Y) < Min then Min = fd_min(Y) end,
      if fd_max(Y) > Max then Max = fd_max(Y) end
   end.