/* 

  Euler problem #79 in Picat.
   
  https://projecteuler.net/problem=79
  """
  A common security method used for online banking is to ask the user for three random
  characters from a passcode. For example, if the passcode was 531278, they may ask 
  for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

  The text file, keylog.txt, contains fifty successful login attempts.

  Given that the three characters are always asked for in order, analyse the file 
  so as to determine the shortest possible secret passcode of unknown length.
  """

  Note: assumption is that the password has distinct digits.

  Added a larger test: All 120 combinations for a 0..9 password ([7059426183], generated by euler79_random/0):
  
  Predicate    Original  Larger (0..9)   Method
  ---------------------------------------------
  euler79      0.0s      0.004s          Topological search
  euler79a     0.04s     8.26s           indomain(Len) + nth + #<  (without all_different)
  euler79b     0.004s    0.148s          indomain(Len) + nth + #< + all_different)
  euler79c     0.076s    22.5s           indomain(Len) + between + nth (with fixed Len: 0.004s)
  euler79d     0.028s    0.096s          cp + all_distinct + element
  euler79e     0.0s      0.004s          checking what number are before
  euler79f1    0.056s    0.0s            LP approach + all_different
  euler79f2    0.0s      0.0s            same as euler79f1 but with #< instead of <
  euler79g     0.0s      0.0s            swapping
  euler79h     0.0s      0.0s            statistical approach
  euler79i     0.028s    0.0s            using find/4
  euler79j     0.06s     >1min           permutation and find_first_of
  euler79k     0.0s      0.004s          using matrix to count precedences
  euler79l     [0.25s/0.19s] [0.0s/25.7s] "regular expression" wildcard. [unsorted Digits/sorted Digits]
                                         [The low time for the larger problem is 
                                         because both digits and the hints are in correct (unsorted) order. 
                                         With sorted digits: 25.7s]
  euler79m     0.64s     >1min           Count the number of matches of the permutations.
  euler79n     0.83s     >1min           Weed out the permutations that don't match the hints
  euler79o     0.0s      0.0s            Loop through a map of precedences: 0.0s


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

*/


import cp,util.


main => go.

go =>
  euler79.


%
% topological sort: 0.0s
%
% Cf http://hakank.org/picat/topological_sort.pi
%
euler79 =>
  File = "euler79.txt",
  Lines1 = read_file_lines(File),
  Lines = Lines1.remove_dups(),
  println(num1=Lines1.len),
  println(num=Lines.len),

  Before = [],
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    Before := Before ++ [[A,B],[A,C],[B,C]]
  end,

  Before := Before.remove_dups(),

  topological_sort(Before,Sorted),

  println([I.to_string() : I in Sorted].join('')),
  nl.  


%
% cp + using nth/3 (without all_different/1): 0.04s
%
euler79a =>

  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
       
  Len :: 3..100,
  indomain(Len),
  
  X = new_list(Len),
  X :: 0..9,
  % all_different(X),
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    [P1,P2,P3] :: 1..Len,
    P1 #< P2,
    P1 #< P3,
    P2 #< P3,
    nth(P1,X,A),
    nth(P2,X,B),
    nth(P3,X,C)
  end,

  solve([ffd,split],X),

  println([I.to_string() : I in X].join('')),

  nl.


%
% cp + nth + all_different: 0.004s
%
euler79b =>

  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
       
  Len :: 3..100,
  indomain(Len),
  
  X = new_list(Len),
  X :: 0..9,
  all_different(X),

  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    [P1,P2,P3] :: 1..Len,
    P1 #< P2,
    P1 #< P3,
    P2 #< P3,
    nth(P1,X,A),
    nth(P2,X,B),
    nth(P3,X,C)
  end,

  solve([ffc,split],X),
  println([I.to_string() : I in X].join('')),
  nl.



%
% logic programming (+ indomain): 0.076s
%
euler79c =>

  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  % Digits = [I.to_integer() : I in Lines.flatten().remove_dups()],
  % Len = Digits.len, % much faster
  Len :: 3..100,
  indomain(Len),
  println(len=Len),
  X = new_list(Len),
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    between(1,Len,P1),
    between(P1+1,Len,P2),
    between(P2+1,Len,P3),
    nth(P1,X,A),
    nth(P2,X,B),
    nth(P3,X,C)
  end,

  println([I.to_string() : I in X].join('')),

  nl.

%
% cp (using element and all_distinct): 0.028s
%
euler79d =>

  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
       
  Len :: 3..100,
  indomain(Len),
  
  X = new_list(Len),
  X :: 0..9,
  % all_different(X),
  all_distinct(X), % faster
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    [P1,P2,P3] :: 1..Len,
    P1 #< P2,
    P2 #< P3,
    element(P1,X,A),
    element(P2,X,B),
    element(P3,X,C)
  end,

  solve([ffd,split],X),

  println([I.to_string() : I in X].join('')),

  nl.

%
% Check the number of numbers before the digits: 0.0s
% 
euler79e =>
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),

  Before = new_map(),
  All = new_map(),
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    Before.put(A,Before.get(A,[])++[B]),
    Before.put(A,Before.get(A,[])++[C]),
    Before.put(B,Before.get(B,[])++[C]),
    All.put(A,1),All.put(B,1),All.put(C,1)
  end,

  % remove duplicates
  foreach(I=A in Before) 
    Before.put(I,A.remove_dups()) 
  end,

  % check the length of each number that is before and sort according to
  % the length: the first number has most, then the second etc.
  Lens = new_map([B.length=I : I=B in Before]).map_to_list().sort().reverse(), 
  Num = [I : _=I in Lens],
  % find the last, i.e. the missing value
  Last = [M : M=_ in All, not member(M,Num)],
  Res = Num ++Last,
  println([I.to_string() : I in Res].join('')),
  
  nl.

%
% LP: without all_different: 4.07s
% With all_different/1: 0.056s.
%
euler79f1 =>
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  
  Digits = [I.to_integer() : I in Lines.flatten().remove_dups()],
  N = Digits.len,
  M = new_map([I=P : {I,P} in zip(Digits,1..N)]),
  Positions = new_list(N),
  all_different(Positions),
  foreach(I in 1..N)
    between(1,N,Positions[I])
    % member(Positions[I],1..N) % slighty slower
  end,

  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    PA = M.get(A),
    PB = M.get(B),
    PC = M.get(C),
    Positions[PA] < Positions[PB],
    Positions[PA] < Positions[PC],
    Positions[PB] < Positions[PC]
  end,

  % find the digits in proper position
  assignment(Positions,Number),
  println(number=[Digits[I].to_string() : I in Number].join('')),

  nl.

%
% Same as euler79f1 but with CP constraints.
% "Plain" CP with or without all_different/1: 0.0s
%
euler79f2 =>
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  Digits = [I.to_integer() : I in Lines.flatten().remove_dups()],
  N = Digits.len,
  M = new_map([I=P : {I,P} in zip(Digits,1..N)]),
  Positions = new_list(N),
  Positions :: 1..N,
  all_different(Positions),
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    PA = M.get(A),
    PB = M.get(B),
    PC = M.get(C),
    Positions[PA] #< Positions[PB],
    Positions[PA] #< Positions[PC],
    Positions[PB] #< Positions[PC]
  end,

  % find the digits in proper position
  assignment(Positions,Number),

  solve(Positions),
  println(number=[Digits[I].to_string() : I in Number].join('')),

  nl.

%
% another approach, using swap/3: 0.0s
%
euler79g => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  Digits = [I.to_integer() : I in Lines.flatten().remove_dups()],
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    PA = find_first_of(Digits,A),
    PB = find_first_of(Digits,B),
    PC = find_first_of(Digits,C),
    if PA > PB then swap(Digits,PA,PB) end,
    if PA > PC then swap(Digits,PA,PC) end,
    if PB > PC then swap(Digits,PB,PC) end
  end,

  println([I.to_string() : I in Digits].join('')),
  nl.

%
% Statistical approach by
% assigning points to the positions of each line: 0.0s
%
euler79h => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  Points = new_map(),
  Occ = new_map(),
  foreach(Line in Lines, I in 1..Line.len)
    V = Line[I].to_integer(),
    Points.put(V,Points.get(V,0)+I),
    Occ.put(V,Occ.get(V,0)+1)
  end,
  M2 = [I=Count/Occ.get(I) : I=Count in Points ].new_map().map_to_list().sort(2),
  println([I.to_string() : I=_ in M2].join('')),
  nl.


%
% Using find/4 to generate the positions: 0.028s
%
euler79i => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  Len = [I.to_integer() : I in Lines.flatten().remove_dups()].len,
  Digits = new_list(Len),
  foreach(Line in Lines)
    % find/4 requires that the substring is a string (not a char)
    [A,B,C] = [C.to_string() : C in Line],
    find(Digits,A,FromA,_),
    find(Digits,B,FromB,_),
    find(Digits,C,FromC,_),
    FromA < FromB,
    FromA < FromC,
    FromB < FromC
  end,
  println([I.to_string() : I in Digits].join('')),
  nl.

%
% permutations + indomain: 0.06s (sorted Digits)
% Note: It is sensitive of the order of digits: unsorted Digits: 13.9s
%
euler79j => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  % Digits = [I : I in Lines.flatten().remove_dups()], % 13.9s
  Digits = [I : I in Lines.flatten().remove_dups().sort()], % faster
  Permutations = permutations(Digits),
  println(len=Permutations.len),
  P :: 1..Permutations.len,
  indomain(P),
  foreach(Line in Lines)
    [A,B,C] = Line,
    PA = find_first_of(Permutations[P],A),
    PB = find_first_of(Permutations[P],B),
    PC = find_first_of(Permutations[P],C),
    PA < PB,
    PA < PC,
    PB < PC
  end,
  println(p=P),
  println(Permutations[P]),
  nl.

%
% Using a matrix to count the before relation: 0.0s
%
euler79k => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),  
  Digits = [I.to_integer() : I in Lines.flatten().remove_dups()],
  Len = Digits.len,
  X = new_array(10,10),
  bind_vars(X,0),
  foreach(Line in Lines)
    [A,B,C] = [I.to_integer() : I in Line],
    X[A+1,B+1] := 1,
    X[A+1,C+1] := 1,
    X[B+1,C+1] := 1
  end,
  Positions = [Len-sum([X[D+1,J] : J in 1..10]) :  D in Digits ],
  Number = new_list(Digits.len),
  foreach(I in 1..Len) 
    Number[Positions[I]] := Digits[I]
  end,
  println([I.to_string() : I in Number].join('')),
  nl.


%
% pattern matching: 0.19s
% Without all_different/1: 4.89s
%
euler79l => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  Digits = Lines.flatten().remove_dups().sort(),
  Len = Digits.len,
  Number = new_list(Len),
  all_different(Number),
  foreach(I in 1..Len)
    member(Number[I],Digits)
  end,  
  foreach(Line in Lines)  
    pattern(Line,Number)
  end,
  println(Number),
  nl.

%
% Count the number of matches for the permutations: 0.64s
%
euler79m => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  Len = Lines.len,
  Digits = Lines.flatten().remove_dups().sort(),
  M = new_map(),
  foreach(Permutation in permutations(Digits))  
    foreach(Line in Lines)
      if pattern(Line,Permutation) then
        M.put(Permutation,M.get(Permutation,0)+1)
      end
    end
  end,
  println([K : K=V in M, V = Len]),
  nl.

%
% Weed out all permutations that don't match the hints: 0.83s
%
euler79n => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  Digits = Lines.flatten().remove_dups().sort(),
  Permutations = new_map([P=1 : P in permutations(Digits)]),
  foreach(Line in Lines)
    foreach(P=1 in Permutations)
      if not pattern(Line,P) then
        Permutations.put(P,0)
      end
    end
  end,
  println([P : P=1 in Permutations]),
  nl.


%
% Loop through a map of precedences: 0.0s
%
euler79o => 
  File = "euler79.txt",
  Lines = read_file_lines(File).remove_dups(),
  Digits = Lines.flatten().remove_dups().sort(),
  Len = Digits.len,
  M = new_map([D=[] : D in Digits]),
  foreach(Line in Lines)
    [A,B,C] = Line,
    M.put(A,M.get(A,[])++[B]),
    M.put(A,M.get(A,[])++[C]),
    M.put(B,M.get(B,[])++[C])
  end,
  foreach(K in M.keys())
    M.put(K,M.get(K).remove_dups())
  end,
  % Get the last value, i.e. the one with no follower
  Last = [V : V in M.keys(), M.get(V) = []].first(),
  Number = [Last],
  foreach(_ in 1..Len-1)
    % weed out Last
    M := new_map([K=V : K=V in M, K!=Last]),
    % remove all instances of the last digit
    foreach(K in M.keys())
       M.put(K,delete(M.get(K),Last))
    end,
    Last := [V : V=_ in M, M.get(V) = []].first(),
    Number := [Last] ++ Number
  end,
  println(Number),
  nl.

euler79_random =>
  generate_random(10).

%
% swap L[I] <=> L[J]
%
swap(L,I,J)  =>
  T = L[I],
  L[I] := L[J],
  L[J] := T.


topological_sort(Precedences, Sorted) =>

  % Note: Picat don't support multi-maps so we work with a 
  %       list of K=V (i.e. key=value)
  Edges = [K=V : [K,V] in Precedences],
  % Nodes = [[K,V] : K=V in Edges].flatten().remove_dups(),
  Nodes = (domain(Edges) ++ range(Edges)).remove_dups(),

  Sorted1 = [],
  while (member(X,Nodes), not member(X,range(Edges))) 
      Sorted1 := Sorted1 ++ [X],
      Nodes := Nodes.delete(X),
      Edges := Edges.delete_key(X)
  end,
  % detect a cycle
  if Nodes.length > 0 then
    println("\nThe graph is cyclic. Here's the detected cycle."),
    println(nodes_in_cycle=Nodes),
    println(edges_in_cycle=Edges),
    Sorted = [without_cycle=Sorted1,cycle=Nodes]
  else 
    Sorted = Sorted1
  end,
  nl.

% domain are the keys in L
domain(L) = [K : K=_V in L].

% range are the values of L
range(L) = [V : _K=V in L].

% deletes all pairs in L where a key is X
% (this is lessf on a multi-map in GNU SETL)
delete_key(L,X) = [K=V : K=V in L, K!=X].


%
% Generate a password and all possible 3-combinations.
%
% password: [7,0,5,9,4,2,6,1,8,3]
% password: 7059426183
generate_random(Len) =>
  % generate password
  _ = random2(),
  Password = random_perm(0..Len-1,100),
  printf(stderr, "%% password: %w\n", Password),
  foreach(I in 1..Len, J in I+1..Len,K in J+1..Len)
     println([Password[P].to_string() : P in [I,J,K]].join(''))
  end,

  nl.

%
% generate Num random instances of a password of length Len
%
generate_random1(Len, Num) =>
  % generate password
  _ = random2(),
  Password = random_perm(0..Len-1,100),
  printf(stderr, "%% password: %w\n", Password),
  I = 0,
  while(I < Num) 
    Pos = [random() mod Len : _ in 1..3].sort(),
    if all_different(Pos) then 
      println([Password[P+1].to_string() : P in Pos].join('')),
      I := I + 1
    end
  end,

  nl.

random_perm(L,N) = Perm => 
  Perm = L,
  Len = L.length,
  _ = random2(),
  foreach(_I in 1..N) 
     R1 = 1+(random() mod Len),
     R2 = 1+(random() mod Len),
     T = Perm[R1],
     Perm[R1] := Perm[R2],
     Perm[R2] := T
  end.

%
% Pattern matching.
%

%
% regex(Pattern, StringToMatch)
%
pattern([],_) => 
   true.

pattern(HP@[H|P],[S|Ss]) => 
  ( H == S -> 
     % eat one char of both pattern and string
     pattern(P,Ss) 
   ;
     % eat one char of the string
     pattern(HP,Ss)
  ).