/*

  Deranged anagrams in Picat.

  http://rosettacode.org/wiki/Anagrams/Deranged_anagrams
  """
  Two or more words are said to be anagrams if they have the same characters, 
  but in a different order. By analogy with derangements we define a deranged 
  anagram as two words with the same characters, but in which the same character 
  does not appear in the same position in both words.

  The task is to use the word list at 
  http://www.puzzlers.org/pub/wordlists/unixdict.txt to find and show 
  the longest deranged anagram. 
  """

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

*/


main => go.

go =>
   FD = open("unixdict.txt"),
   % FD = open("words_lower.txt"),
   Dict = new_map(),
   while (not at_end_of_stream(FD))
      Line = read_line(FD),
      Sorted = Line.sort(),
      Dict.put(Sorted, cond(Dict.has_key(Sorted), Dict.get(Sorted), "") ++ [Line])
   end,
   close(FD),

   Deranged = [Value : _Key=Value in Dict, Value.length > 1, allderanged(Value)],
   MaxLen = max([V[1].length : V in Deranged]),
   println([V : V in Deranged, V[1].length == MaxLen ]),

   nl.

% shorter and faster
go2 =>
  M = new_map(),
  _=[_:W in read_file_lines("unixdict.txt"),S=sort(W),M.put(S,M.get(S,"")++[W])],
  Deranged = [Value : _Key=Value in M, Value.length > 1, allderanged(Value)],
  MaxLen = max([V[1].length : V in Deranged]),
  println([V : V in Deranged, V[1].length==MaxLen]),
  nl.

% using group/2
go3 =>
  M=[W:W in read_file_lines("unixdict.txt")].group(sort),
  Deranged = [Value : _Key=Value in M, Value.length > 1, allderanged(Value)],
  MaxLen = max([V[1].length : V in Deranged]),
  println([V : V in Deranged, V[1].length==MaxLen]),
  nl.


%
% A and B are deranged: i.e. there is no
% position with the same character.
%
deranged(A,B) => 
   foreach(I in 1..A.length)
       A[I] != B[I]
   end.


%
% All words in list Value are deranged anagrams of each other.
%
allderanged(Value) => 
    IsDeranged = 1,
    % foreach(V1 in Value, V2 in Value, compare_terms(V1,V2) < 0, IsDeranged = 1)
    foreach(V1 in Value, V2 in Value, V1 @< V2, IsDeranged = 1)
       if not deranged(V1,V2) then
          IsDeranged := 0
       end
    end,
    IsDeranged == 1.


%
% groups the element in List according to the function F
%
group(List, F) = P, list(List) =>
   P = new_map(),
   foreach(E in List) 
      V = apply(F,E),
      P.put(V, P.get(V,[]) ++ [E])
   end.