1votos

Palabras Bonitas en Haskell

por josejuan hace 4 años

En una máquina viejilla se pueden contar, usando un segundo de tiempo, palabras con entorno a 100 espacios en blanco.

Encontrar la maxima cantidad de estas palabras que puedan ser formadas a partir de una de estas palabras.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
{-# LANGUAGE BangPatterns #-} 
import System.Environment 
import Data.Function.Memoize 
 
nbonitas :: String -> Integer 
nbonitas = o False 0 0 
  where o :: Bool -> Int -> Int -> String -> Integer 
        o _ 3 _ _ = 0 
        o _ _ 3 _ = 0 
        o !e _ _ [] = if e then 1 else 0 
        o !e !v !k (x:xs) | x == '_'         = sum $ map (q e v k . (:xs)) "vk" 
                          | x `elem` "AEIOU" = q e (v + 1) 0 xs 
                          | x == 'L'         = q True 0 (k + 1) xs 
                          | x == 'v'         = 5 * q e v k ('A':xs) 
                          | x == 'k'         = 20 * q e v k ('K':xs) + q e v k ('L':xs) 
                          | otherwise        = q e 0 (k + 1) xs 
        q = memoize4 o 
 
main = getArgs >>= print . nbonitas . head 
 
{- 
 
$ for i in $(seq 10 10 100); do echo "**** $i ****"; time ./words.exe `perl -E "say\"_\"x$i"`; done 2>&1 | grep -v '^\(user\|sys\|$\)' 
**** 10 **** 
1101146269250 
real    0m0.101s 
**** 20 **** 
4542920544717012470562500 
real    0m0.130s 
**** 30 **** 
14439644230792093150555765273691406250 
real    0m0.185s 
**** 40 **** 
41224169487739995552522403114610881591936035156250 
real    0m0.257s 
**** 50 **** 
111176087607075736407010537656017913108674730772173461914062500 
real    0m0.363s 
**** 60 **** 
289715548909167882375700577427117804005300531107056066001112556457519531250 
real    0m0.500s 
**** 70 **** 
738362841921241646526988870498113970467057640539960125865853853502489018440246582031250 
real    0m0.632s 
**** 80 **** 
1853533327504087381634073954954488216387897636782888539306252160484249982275704914331436157226562500 
real    0m0.814s 
**** 90 **** 
4603880608696025217890894555270178977815001488057319182871484820396309143637303527026565024629235267639160156250 
real    0m1.010s 
**** 100 **** 
11348652199975658627021530418279598146867679090661391488624224623345973478564688854874546063582411039853468537330627441406250 
real    0m1.278s 
 
-} 
3 comentarios
0votos

Escrito por Sayd hace 3 años

Bueno podrias decirme cómo funciona tu algoritmo, no entiendo muy bien que es lo que hace :D saludos
0votos

Escrito por josejuan hace 3 años

Hola @sayd,

avanzamos con cada símbolo de entrada (siempre mayúsculas) considerando cada posible caso.

El peor de los casos, es el comodín, que divide las posibilidades en dos alternativas a considerar, el resto, sólo es ir multiplicando cada factor.

Las ecuaciones indican lo siguiente:

Sin contener la L (false), con 0 vocales y 0 consonantes consecutivas:
nbonitas = o False 0 0 


Si tenemos 3 vocales, no puede ser bonita:
        o _ 3 _ _ = 0 


Si tenemos 3 consonantes, tampoco puede ser bonita:
        o _ _ 3 _ = 0 


Si ya no quedan símbolos, será bonita si había alguna L:
        o !e _ _ [] = if e then 1 else 0 


Si es un comodín, será la suma de las palabras con cualquier vocal (v) y con cualquier consonante (k):
        o !e !v !k (x:xs) | x == '_'         = sum $ map (q e v k . (:xs)) "vk" 


Si es una vocal, incrementamos vocal:
                          | x `elem` "AEIOU" = q e (v + 1) 0 xs 


Si es la L, marcamos la L como "recibida" e incrementamos consonante:
                          | x == 'L'         = q True 0 (k + 1) xs 


Si es cualquier vocal, son 5 posibilidades y ponemos una A de señuelo:
                          | x == 'v'         = 5 * q e v k ('A':xs) 


Si es cualquier consonante, son 20 posibilidades y ponemos una K de señuelo, más el caso de la L (porque es cualquier consonante):
                          | x == 'k'         = 20 * q e v k ('K':xs) + q e v k ('L':xs) 


Si no es ninguna de las anteriores, sólo puede ser una consonante distinta de la L, que la contabilizamos:
                          | otherwise        = q e 0 (k + 1) xs 


La explosión combinacional, podemos podarla eficientemente usando memoización:
        q = memoize4 o 


Y ya está ;)
0votos

Escrito por Sayd hace 3 años

Muchas gracias, Muy bien explicado y buena solucion. Te dejo mi voto :D

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.