1voto
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.

0votos
Acceso a edificio en Haskell
por

josejuan

hace 3 años

Claro que (siguiendo la solución anterior), también podemos crear un servicio RESTful CROSS domain que pueda ser atacado desde cualquier aplicación (no sólo websites), exponiendo adecuadamente los posibles mensajes de error que puedan producirse (incluído los mensajes que vengan del backend).

0votos
Acceso a edificio en Haskell
por

josejuan

hace 3 años

Así por ejemplo (ver solución anterior), podemos acceder a nuestro sistema (gestión de usuarios en este caso) desde una aplicación de gestión interna (el típico proceso que se lanza cada X tiempo para revisar y notificar cosas). En este caso, se separan los usuarios normales de los administradores (ej. para notificar a los admins).

0votos
Acceso a edificio en Haskell
por

josejuan

hace 3 años

Hay infinidad de formas de hacer este tipo de apps. En todo caso, un "no mal" punto de partida es independizar el backend (la bbdd) y el negocio de todo lo demás, a partir de ahí, se puede crecer adecuadamente. Aquí se muestra un backend (sólo la tabla de usuarios) y la lógica (de control de acceso y todas las acciones posibles sobre la tabla).