A menudo, una tarea requiere matrices reales. Tome por ejemplo la tarea de implementar Befunge o> <>. Traté de usar el Array
módulo para esto, pero es realmente engorroso, ya que parece que estoy codificando demasiado detallado. ¿Alguien puede ayudarme a resolver tales tareas de código de golf menos detalladas y más funcionales?
11
Respuestas:
En primer lugar, recomiendo mirar Data.Vector , una alternativa mejor a Data.Array en algunos casos.
Array
yVector
son ideales para algunos casos de memorización, como se demuestra en mi respuesta a "Encontrar las rutas máximas" . Sin embargo, algunos problemas simplemente no son fáciles de expresar en un estilo funcional. Por ejemplo, el problema 28 en el Proyecto Euler llama a la suma de los números en las diagonales de una espiral. Claro, debería ser bastante fácil encontrar una fórmula para estos números, pero construir la espiral es más difícil.Data.Array.ST proporciona un tipo de matriz mutable. Sin embargo, la situación de tipo es un desastre: utiliza una clase MArray para sobrecargar cada uno de sus métodos, excepto runSTArray . Entonces, a menos que planee devolver una matriz inmutable de una acción de matriz mutable, tendrá que agregar una o más firmas de tipo:
Sin embargo, mi solución para Euler 28 resultó bastante bien, y no requería esa firma de tipo porque la usé
runSTArray
.Usando Data.Map como una "matriz mutable"
Si está buscando implementar un algoritmo de matriz mutable, otra opción es usar Data.Map . Cuando usa una matriz, desea tener una función como esta, que cambia un solo elemento de una matriz:
Desafortunadamente, esto requeriría copiar toda la matriz, a menos que la implementación utilizara una estrategia de copia en escritura para evitarla cuando sea posible.
La buena noticia es que
Data.Map
tiene una función como esta, insertar :Debido a que
Map
se implementa internamente como un árbol binario equilibrado,insert
solo toma O (log n) tiempo y espacio, y conserva la copia original. Por lo tanto,Map
no solo proporciona una "matriz mutable" algo eficiente que es compatible con el modelo de programación funcional, sino que incluso le permite "retroceder en el tiempo" si así lo desea.Aquí hay una solución para Euler 28 usando Data.Map:
Los patrones de explosión evitan un desbordamiento de la pila causado por los elementos del acumulador (cursor, número y mapa) que no se utilizan hasta el final. Para la mayoría de los códigos de golf, los casos de entrada no deberían ser lo suficientemente grandes como para necesitar esta disposición.
fuente
La respuesta simplista es: no use matrices. La respuesta no tan fácil es: Intente repensar su problema para que no necesite matrices.
A menudo, un problema con algo de pensamiento se puede hacer sin ningún tipo de estructura como matriz. Por ejemplo, aquí está mi respuesta a Euler 28:
Lo que se expresa en el código aquí es el patrón de la secuencia de números a medida que crecen alrededor de la espiral rectangular. No había necesidad de representar realmente la matriz de números en sí.
La clave para pensar más allá de las matrices es pensar en lo que realmente significa el problema en cuestión, no en cómo podría representarlo como bytes en la RAM. Esto solo viene con la práctica (¡tal vez una razón por la que codifico tanto golf!)
Otro ejemplo es cómo resolví la búsqueda de rutas máximas de código-golf. Allí, el método de pasar las soluciones parciales como una onda a través de la matriz, fila por fila, se expresa directamente mediante la operación de plegado. Recuerde: en la mayoría de las CPU, no puede manejar la matriz como un todo a la vez: el programa tendrá que funcionar a través de ella con el tiempo. Es posible que no necesite toda la matriz a la vez en cualquier momento.
Por supuesto, algunos problemas se plantean de tal manera que están inherentemente basados en matrices. Idiomas como> <>, Befunge o Brainfuck tienen arrays en su corazón. Sin embargo, incluso allí, las matrices a menudo se pueden prescindir. Por ejemplo, vea mi solución para interpretar Brainfuck , el núcleo real de su semántica es una cremallera . Para comenzar a pensar de esta manera, concéntrese en los patrones de acceso y en la estructura más cercana al significado del problema. A menudo, esto no necesita ser forzado a una matriz mutable.
Cuando todo lo demás falla y necesitas usar una matriz, los consejos de @ Joey son un buen comienzo.
fuente