0votos

Moo en Haskell

por josejuan hace 6 años

En mi humilde Atom calculo el carácter de la posición 10^4365 en menos de un segundo.

Moo

Problema de la entrenamiento de la USACO,sobre relaciones recursivas.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import System.Environment (getArgs) 
 
-- Usando memoization con la definición directa: 
moo_L2 = (map l [0..] !!) 
  where l 0 = 3 
        l n = 2 * l (n - 1) + 3 + n 
 
-- La anterior es rápida, pero es fácil resolver 
-- la recursión de la serie, además, ésta permite 
-- calcular números muchísimo más grandes y por 
-- tanto ésta es muchísimo mejor que la anterior 
moo_L :: Integer -> Integer 
moo_L n = 2^(n + 3) - n - 5 
 
-- La inversa de la longitud no se puede calcular 
-- explícitamente (no puede despejarse la 'n'), pero 
-- es igualmente rápido 
moo_L' :: Integer -> Integer 
moo_L' k = fromIntegral $ length $ takeWhile(<k) $ map moo_L [0..] 
 
-- Obtenemos el caracter: 
 
-- O es la cadena inicial 
moo_K 1 = 'm' 
moo_K 2 = 'o' 
moo_K 3 = 'o' 
 
moo_K k = 
  -- O bien es la 'm' de "en medio" 
  if k == l' + 1 
    then 'm' 
    else 
      -- O bien son las 'o'es de "en medio" 
      if k <= l' + 3 + n 
        then 'o' 
        -- O bien es una subcadena 
        else moo_K (k - l' - 3 - n) 
         
  where n = moo_L' k 
        l' = moo_L (n - 1) 
          
 
main = getArgs >>= print.moo_K.(1+).moo_L.read.head 
 
{-- 
-- Por ejemplo, para n > 0 todas las posiciones 
--       moo_L n + 1 == 'm' 
 
-- En mi humilde Atom, calcular todas las 'm' hasta n==59 le cuesta 0.05 seg 
 
*Main> map (moo_K.(1+).moo_L) [1..59] 
"mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm" 
(0.05 secs, 7240216 bytes) 
 
 
-- Compilando (en mi humilde Atom), en menos de un segundo calcula hasta 
-- el caracter 2^(14500 + 3) - 14500 - 3, que es aproximadamente 10^4365 
$ time -f "%E, %M" ./moo 14500 
'm' 
0:00.99, 30208 
 
 
 
 
 
-- Para testear, basta generar la cadena de una y otra forma y comparar: 
 
-- Generando la cadena usando la definición 
moo_Gen1 0 = "moo" 
moo_Gen1 n = g ++ "moo" ++ (take n $ repeat 'o') ++ g where g = moo_Gen1 (n - 1) 
 
-- Generando la cadena usando el caracter de cada posición 
moo_Gen2 n = map moo_K [1..moo_L n] 
 
-- Testear 
test_Gen n = moo_Gen1 n == moo_Gen2 n 
 
-- ¿Algún test falla para n=1..12? 
test_Gens = and $ map test_Gen [1..12] 
 
 
--} 
 
 
 
 
{-- 
El desarrollo (aunque es sencillo obtenerlo) de la fórmula explícita 
para la longitud es esta: 
 
Tenemos que 
 
   S(0) = "moo" 
   S(1) = "moomooomoo" 
   ... 
   S(n) = S(n-1) + "moo" + {"o"}n + S(n-1) 
   ... 
 
Así, la longitud de cada S(0) será 
 
   L(0) =  3 
   L(1) =  3 + 3 + 1 +  3 = 10 
   L(2) = 10 + 3 + 2 + 10 = 25 
   L(3) = 25 + 3 + 3 + 25 = 56 
   ... 
   L(n) = L(n-1) + 3 + n + L(n-1) 
   ... 
 
La recursión puede resolverse con matemáticas básicas, pues desarrollando, 
se ve rápidamente que: 
 
  L(0) =    k 
  L(1) =  3 k + 1 
  L(2) =  7 k + 1 * 2 + 2 * 1 
  L(3) = 15 k + 1 * 3 + 2 * 2 + 4 * 1 
  L(4) = 31 k + 1 * 4 + 2 * 3 + 4 * 2 + 8 * 1 
  L(5) = 63 k + 1 * 5 + 2 * 4 + 4 * 3 + 8 * 2 + 16 * 1 
  ... 
  L(n) = (2^(n+1) - 1) k + 2^(n+1) - n - 2 
  ... 
 
Es decir 
 
  L(n) = 2^(n+3) - n - 5 
 
--} 
2 comentarios
0votos

Escrito por Santiago hace 4 años

Nunca he visto ese lenguaje. ¿Cual es?
Gracias por compartir.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.