/* 

  Last letter-first letter (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Last_letter-first_letter
  """
  A certain childrens game involves starting with a word in a particular category. Each 
  participant in turn says a word, but that word must begin with the final letter of the 
  previous word. Once a word has been given, it cannot be repeated. If an opponent cannot 
  give a word in the category, they fall out of the game. For example, with "animals" as 
  the category,

  Child 1: dog 
  Child 2: goldfish
  Child 1: hippopotamus
  Child 2: snake
  ...

  Task Description

  Take the following selection of 70 English Pokemon names (extracted from Wikipedia's list of Pokemon) 
  and generate the/a sequence with the highest possible number of Pokemon names where the 
  subsequent name starts with the final letter of the preceding name. No Pokemon name is 
  to be repeated.

     audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
     cresselia croagunk darmanitan deino emboar emolga exeggcute gabite
     girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan
     kricketune landorus ledyba loudred lumineon lunatone machamp magnezone mamoswine
     nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2
     porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking
     sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko
     tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask

  Extra brownie points for dealing with the full list of 646 names.
  """

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

*/


main => go.


go ?=>
   words(Words),
  Starts = new_map(), % words that starts with same letter as "this" 
  Ends = new_map(), % words that ends with same letter as this word
  foreach(Word in Words)
     S = [ Word2 : Word2 in Words, Word != Word2, Word.last() = Word2.first()],
     Starts.put(Word,S),
     E = [ Word2 : Word2 in Words, Word != Word2, Word2.last() = Word.first()],
     Ends.put(Word,E)
  end,
  println(starts_ordered=Starts.map_to_list().qsort(sortf)),
  Words2 = [W : W=_ in Starts.map_to_list().qsort(sortf)],
  println(words2=Words2),
  foreach(Len in 2..Words2.length)
     % once(play1(Words2,Starts,Ends,Len,List)),
     play1(Words2,Starts,Ends,Len,List),
     println(List),
     println(len=Len)
  end,
  nl.

go => true.

%
% Get all of length 23 lists: 1248
%
go2 ?=>
   Sols = get_global_map(),
   Sols.put(count,0),
  Starts = new_map(), % words that starts with same letter as "this" 
  Ends = new_map(), % words that ends with same letter as this word
  words(Words),
  foreach(Word in Words)
     S = [ Word2 : Word2 in Words, Word != Word2, Word.last() = Word2.first()],
     Starts.put(Word,S),
     E = [ Word2 : Word2 in Words, Word != Word2, Word2.last() = Word.first()],
     Ends.put(Word,E)
  end,
  Words2 = [W : W=_ in Starts.map_to_list().qsort(sortf)],
  Len = 23,
  play1(Words2,Starts,Ends,Len,List),
  println(list=List),
  Sols.put(count,Sols.get(count)+1),
  fail,
  nl.

go2 => 
  println(count=get_global_map().get(count)).


play1(Words, Starts, Ends, Len, LLFL) ?=> 
  LLFL = new_list(Len),
  % select(LLFL[1],[W : W=K in Starts, K != []],Rest),
  select(LLFL[1], Words, Rest),
  C = 2,
  while (C <= Len) 
    Among = Starts.get(LLFL[C-1]),
    Among != [],
    select(Word,Among,_Rest2),
    This = [LLFL[I] : I in 1..C-1],
    not member(Word,This),
    LLFL[C] := Word,
    Rest := delete(Rest,LLFL[C]),
    C := C +1
  end.
  

%
% qsort(List, SortFunction)
% returns a sorted list according to the sort function SortFunction.
%
qsort([],_F)    = [].
qsort([H|T],F) = qsort([E : E in T, call(F,E,H)], F) 
                 ++ [H] ++
                 qsort([E : E in T, not call(F,E,H)],F).


sortf(L1,L2) =>
  (K1=V1) = L1,
  (K2=V2) = L2,
  V1.length >= V2.length.


words(Words) => 
  Words = 
[
"audino", "bagon", "baltoy", "banette", "bidoof", "braviary", "bronzor", "carracosta", "charmeleon",
"cresselia", "croagunk", "darmanitan", "deino", "emboar", "emolga", "exeggcute", "gabite",
"girafarig", "gulpin", "haxorus", "heatmor", "heatran", "ivysaur", "jellicent", "jumpluff", "kangaskhan",
"kricketune", "landorus", "ledyba", "loudred", "lumineon", "lunatone", "machamp", "magnezone", "mamoswine",
"nosepass", "petilil", "pidgeotto", "pikachu", "pinsir", "poliwrath", "poochyena", "porygon2",
"porygonz", "registeel", "relicanth", "remoraid", "rufflet", "sableye", "scolipede", "scrafty", "seaking",
"sealeo", "silcoon", "simisear", "snivy", "snorlax", "spoink", "starly", "tirtouga", "trapinch", "treecko",
"tyrogue", "vigoroth", "vulpix", "wailord", "wartortle", "whismur", "wingull", "yamask"
].