0votos
Poker Kata en Haskell
por

josejuan

hace 4 años

Escribir las funciones directamente para evaluar "al vuelo" una única mano son fáciles, pero también es fácil colarse con algún predicado. Aquí hago funciones que evalúan al vuelo cada jugada, sin monos primero y luego con monos. Aprovecho los datos que generé en mi solución anterior para verificar éstas funciones (y recíprocamente que mis archivos son correctos también).

1voto
Poker Kata en Haskell
por

josejuan

hace 4 años

Si nuestro programa correrá en un dispositivo con poco almacenamiento deben usarse algoritmos de cálculo directo, pero en general, es mucho más sencillo y fácil generar todas las combinaciones de interés y precalcularlas en alguna base de datos (ej. unos archivos). Las funciones resultantes son muy sencillas. Se generan todas las combinaciones posibles, con y sin comodines.

0votos
Camino de Hamilton en Haskell
por

josejuan

usando GLPK hace 4 años

El enunciado no está muy bien planteado, porque se pide claramente un camino de hamilton, luego se ponen datos de un grafo direccional con pesos (que apunta al problema del viajante) y con una solución que es un ciclo (¿de viajante o de hamilton?). Se que se pide un algoritmo explícito, pero eso es más aburrido que buscar soluciones prácticas (como usar LPI :)

0votos
Generador de números en orden aleatorio (para practicar pruebas) en Haskell
por

josejuan

hace 4 años

No creo que haya nada más sencillo que un BUEN shufflé (con coste lineal y distribución uniforme, que no lo cumplen todas las implementaciones). Por jugar un poco, podemos obtener el mismo resultado (y con coste lineal aunque al usar factoriales bigint hace que sea peor) sabiendo que podemos indexar todas las permutaciones de N elementos. Entonces, basta tomar un número aleatorio entre 1 y N!. Tiene la ventaja de que podría transferirse esta información (el índice) y no la permutación (por red).

0votos
Acceso Concedido en Haskell
por

josejuan

hace 4 años

El problema creo es muy fácil (no difícil), no se en que cursos se dan series, pero con eso basta, tiene coste O(log n) y pueden calcularse nºs absurdamente grandes (ej. 10^60000) en uno o dos segundos. No pongo la explicación para hacer pensar al resto.

0votos
Minimal Superpermutations en Haskell
por

josejuan

hace 4 años

El algoritmo trivial (concatenar permutaciones hasta terminar) puede hacerse en tiempo casi lineal O(p), lo que pasa que como el número de permutaciones es p=n! resulta que el coste práctico respecto el nº de símbolos es O(n!), aún así puede mejorarse mucho este algoritmo. La pena es que no sirve (ver A007489).

0votos
Escalera en Haskell
por

josejuan

hace 4 años

Se refuerza mi hipótesis de que existe una expresión única para el cálculo del problema. En esta solución doy una expresión O(1) para n <= 2k+1 y queda indicada que existe una expresión para n <= qk+1 para cualquier q. Por tanto, puede calcularse la expresión con coste constante (realmente el coste no es constante debido al coste de las operaciones con precisión arbitraria que no son constantes).

1voto
Escalera en Haskell
por

josejuan

hace 4 años

Pensando un rato en el problema, veo una estrategia de partición que hace al algoritmo con coste lineal O(N), por lo que calcula en milésimas lo que antes calculaba en minutos. Además, me da que podría calcularse más rápidamente, cuando no con coste O(1). Calcula N=100.000 y k=1.000 en menos de 7 segundos (a la versión de C le lleva 3 minutos).

0votos
Escalera en Haskell
por

josejuan

hace 4 años

Como N es menor de 10.000, entonces, está claro que al restar cualquier valor (válido) a N, vamos a tener un elemento de entre 10.000 y sólo de entre esos 10.000. Así, es obvio que memoizando una función de recurrencia tendremos una eficiencia muy buena (máximo habrá que calcular N * k veces esa función). Ésto no quita, que buscando alguna propiedad pueda mejorarse...