lcustos = [('A',1),('B',10),('C',18),('Ç',28),('D',38),('E',70),('F',10),('G',43),('H',15),('I',54),('J',10),('K',44),('L',81),('M',19),('N',39),('O',54),('P',91),('Q',72),('R',30),('S',84),('T',75),('U',22),('V',47),('X',66),('Y',59),('Z',32)]

cpalavras = ['F','L','O','R','E','S','T','A','R','S',
         'K','J','G','D','F','T','J','J','U','V',
         'C','A','P','E','L','A','P','I','S','C',
         'D','T','C','A','D','W','Y','E','R','T',
         'F','D','C','C','S','A','L','U','S','E',
         'Q','L','K','C','A','U','E','A','I','O',
         'A','A','S','A','R','P','R','D','K','A',
         'N','E','N','E','F','T','E','B','A','U',
         'J','K','D','D','S','H','W','L','F','L',
         'I','O','T','U','G','J','J','V','A','A']




inverter xs =
    if null xs
       then xs
       else last xs: inverter (init xs)



prefixor xs ys =
    if null xs
        then True
        else if null ys
        then False
        else if(head xs == head ys)
        then prefixor (tail xs) (tail ys)
    else False


sublista xs ys =
    if null ys
        then False
        else if prefixor xs ys
        then True
    else sublista xs (tail ys)

lista_de_linha dimensao =
       if dimensao == 0
       then []
       else linha dimensao:lista_de_linha (dimensao-1)

f dimensao = inverter (lista_de_linha dimensao)


lista_de_colunas dimensao =
       if dimensao == 0
       then []
       else col dimensao:lista_de_colunas (dimensao-1)

g dimensao = inverter (lista_de_colunas dimensao)


lista_de_linhasinversas dimensao =
     if dimensao == 0
         then []
         else inverter (linha dimensao):lista_de_linhasinversas(dimensao-1)
h = inverter

t = truncate (sqrt (fromIntegral (length cpalavras) ) )
--Dado uma matriz t x t, essa função pega a partir do length da matriz o valor de t. O truncate e o fromIntegral foram utilizados para adequar os determinados tipos nas ocasiões corretas.


linha n = take t (drop posicaolinha cpalavras )
  where
    posicaolinha = t*(n - 1)

--Dado um valor de n, a função extraio vetor linha referente a n.

col n = inverter (coluna n t)
    where
    coluna n t  =
                       if t == 0
                       then []
                       else head (drop (n-1) (linha t)):coluna n (t-1)

--Dado um valor de n, a função extrai o vetor coluna referente ao valor de n, é utilizado recursão, a função inverter foi utilizada para normalizar a ordem dos vetores uma vez que a recursão extrai a coluna de baixo pra cima, então é preciso inverter para normalizar.
--l xs = head [x|x<-lcustos, head xs == fst x]
z xs=[x|x<-lcustos, head xs == fst x]
y = head lcustos
custo xs =
    if xs == []
      then 0
      else (snd l) + custo (tail xs)
--  else (-1)

        where
              l = head [x|x<-lcustos, head xs == fst x]

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

custletr k xs = snd (head [ x | x <- xs, fst x == k])

custpala palavra custos = if null palavra
              then 0
              else custletr (head palavra) custos + custpala ( tail palavra ) custos



palamencust palavra1 palavra2  = if custpala palavra1 lcustos > custpala palavra2 lcustos
                        then palavra2
                        else palavra1


ordemalfa palavra1 palavra2 = if (head palavra1) < (head palavra2) || (head palavra1) == (head palavra2) && (palavra1 !! 1) < (palavra2 !! 1) || (head palavra1) == (head palavra2) && (palavra1 !! 1) == (palavra2 !! 1) && (palavra1 !! 2) < (palavra2 !! 2)
                  then palavra1
                  else palavra2
 ----------------------------------------------------------------------------------------------------------------------------------------------------------------

esta_na_linha palavra = [x|x<-(f 10), sublista palavra x]
esta_na_coluna palavra =  [x|x<-(g 10), sublista palavra x]
esta_na_linhainversa palavra = [x|x<-inverter (f 10), sublista palavra x]
esta_na_colunainversa palavra = [x|x<-inverter (g 10) , sublista palavra x]







ocorrenciamc cpal = ( menor_custo_lista cpal ,custpala (menor_custo_lista cpal) (lcustos) )
    where
      menor_custo_lista cpal = foldl (palamencust ) (head cpal) cpal