0votos
Min and Second Min en Haskell
por

josejuan

hace 3 años

El enunciado es ambiguo. No es lo mismo dos elementos mínimos que dos elementos con el menor valor posible. En el primer caso, los elementos deben ser minimales y en segundo no. Aquí se resuelve ambas versiones *sin usar igualdad*, únicamente una relación de orden (ej. "menor que").

0votos
Contar los Palíndromos en Haskell
por

josejuan

hace 3 años

El problema es fácil si no se exige O(n) (ej. parece razonable que O(n^2) es fácil). Sin embargo, supuesto que podemos obtener los radios de los palíndromos en O(n) (problema que para mí *no* es fácil), entonces, se hace trivial obtener con coste lineal el desafío propuesto.

0votos
Problema de las Olimpiadas rusas en Haskell
por

josejuan

hace 3 años

Aunque el problema deja claro que se trata de los números en base 10, como dice Fernando, puede generalizarse a cualquier base. Esta implementación en Haskell es la más eficiente (asintóticamente es, al menos, exponencialmente más rápida) de todas las otras soluciones (salvo omisión). Claro que no importa mucho si tenemos O(log n) que O(log log n)... Pero por optimizar que no quede :P

0votos
Factorizar el factorial en Haskell
por

josejuan

hace 3 años

Esta solución es de Will Ness y es sencillamente genial. Con la implementación eficiente de Data.Numbers.Primes tiene un rendimiento similar a la versión de C, pero además, si se cachean los primos (o leen de disco) sería inmediato.

0votos
La sucesión de Golomb en Haskell
por

josejuan

hace 3 años

La constante de ésta en Haskell sigue siendo mucho mayor que la versión en C, pero tiene la ventaja de calcular la sucesión infinita. Usa la misma estrategia que la última versión en C y calcula hasta g(4.5e10) en 1 segundo. No requiere predimensionar la memoria (incluso con buffer cíclico haría falta) porque usa un Data.Seq que desecha por la izquierda y crece por la derecha.

0votos
Mejor factorización triple en Haskell
por

josejuan

hace 3 años

Siempre que hay que empaquetar algo, puede usarse programación lineal. En este caso es mixta. Se transforman las ecuaciones pasando a logaritmos, de esta forma transformamos el producto de potencias (la factorización) en suma de logaritmos y así poder aplicar LP. "Parece" funcionar un poco mejor, pero sigue sin ser eficiente.

0votos
Mejor factorización triple en Haskell
por

josejuan

hace 3 años

Yo no encuentro ninguna propiedad que me permita resolver eficientemente el problema. Para mí hay que factorizar n (que tiene complejidad "casi" exponencial) y luego empaquetar una suma de enteros (que en general es NP-hard). Pueden usarse heurísticas, pero no veo ninguna invarianza o suavidad que pueda usarse para acercarse al objetivo. Aquí la solución trivial.

2votos
El problema de Josefo en Haskell
por

josejuan

hace 3 años

El único coste problemático es el del cálculo de la posición para saltos entre desdichados grandes (ej. 10000 o así). Para valores pequeños, el número de desdichados puede ser escandalosamente grande (ej. 10^1000) y el cálculo se hace en pocos milisegundos. De hecho, da igual el número de desdichados, pues el coste viene a ser O(k + log n), por lo que el segundo sumando carece de importancia.