¿Cuáles son las formas de programación funcional de implementar el Juego de la vida de Conway [cerrado]?

12

Recientemente implementado por diversión El juego de la vida de Conway en Javascript (en realidad es un coffeescript pero lo mismo). Ya que javascript puede ser usado como un lenguaje funcional, estaba tratando de permanecer en ese extremo del espectro. No estaba contento con mis resultados. Soy un programador OO bastante bueno y mi solución olía a old-same-same-old. Tan larga pregunta corta: ¿cuál es el estilo funcional (pseudocódigo) de hacerlo?

Aquí está Pseudocódigo para mi intento:

class Node
  update: (board) ->
    get number_of_alive_neighbors from board
    get this_is_alive from board
    if this_is_alive and number_of_alive_neighbors < 2 then die
    if this_is_alive and number_of_alive_neighbors > 3 then die
    if not this_is_alive and number_of_alive_neighbors == 3 then alive

class NodeLocations
  at: (x, y) -> return node value at x,y
  of: (node) -> return x,y of node

class Board
  getNeighbors: (node) -> 
   use node_locations to check 8 neighbors 
   around node and return count

nodes = for 1..100 new Node
state = new NodeState(nodes)
locations = new NodeLocations(nodes)
board = new Board(locations, state)

executeRound:
  state = clone state
  accumulated_changes = for n in nodes n.update(board)
  apply accumulated_changes to state
  board = new Board(locations, state)
    
pregunta George Mauer 20.11.2011 - 19:39

5 respuestas

11

Bueno, un par de ideas. No soy un experto en FP, pero ...

Es bastante claro que deberíamos tener un tipo Board que represente un estado de juego. La base de la implementación debe ser una función evolve de tipo evolve :: Board -> Board ; lo que significa que produce un Board al aplicar las reglas del juego a un Board .

¿Cómo deberíamos implementar evolve ? Un Board probablemente debería ser una matriz n x m de Cell s. Podríamos implementar una función cellEvolve de tipo cellEvolve :: Cell -> [Cell] -> Cell que, dada una Cell , y su vecina Cell s calcula el estado Cell en la próxima iteración.

También deberíamos implementar una función getCellNeighbors que extraiga los vecinos Cell s de un Board . No estoy completamente seguro de la firma de este método; Dependiendo de cómo implemente Cell y Board , podría tener, por ejemplo, getCellNeighbors :: Board -> CoordElem -> CoordElem -> [Cell] , que dado un tablero y dos coordenadas ( CoordElem sería el tipo usado para indexar posiciones en un Board ), le da un lista de longitud variable de los vecinos (no todas las celdas del tablero tienen el mismo número de vecinos; las esquinas tienen 3 vecinos, bordes 5 y todos los demás, 8).

Por lo tanto,

evolve se puede implementar combinando cellEvolve y getCellNeighbors para todas las celdas del tablero, de nuevo, la implementación exacta dependerá de cómo implementes Board y Cell , pero debería ser algo como "para todas las celdas de la placa actual, obtenga sus vecinos y utilícelas para calcular la celda correspondiente de la nueva placa". Esto debería ser posible con una aplicación genérica de esas funciones en toda la placa utilizando un "mapa sobre la función de la celda de la placa" .

Otros pensamientos:

  • Realmente deberías implementar cellEvolve para que tome como parámetro un tipo GameRules que codifica las reglas del juego; di una lista de tuplas (State,[(State,NumberOfNeighbors)],State) que dice para un estado dado y el número de vecinos en cada estado, que debe ser el estado en la siguiente iteración. La firma de cellEvolve podría ser cellEvolve :: GameRules -> Cell -> [Cell] -> Cell

  • Lógicamente, esto lo llevaría a hacer que evolve :: Board -> Board se convierta en evolve :: GameRules -> Board -> Board , por lo que podría usar evolve sin cambios con diferente GameRules , pero podría ir un paso más allá y hacer que cellEvolve sea conectable. en lugar de GameRules .

  • Al jugar con getCellNeighbors , también puede hacer que evolve genérico con respecto a la topología de Board . Podría tener getCellNeighbors que se enrolla alrededor de los bordes de la placa, placas 3d, etc.

respondido por el alex 21.11.2011 - 11:05
9

Si estás escribiendo una versión de programación funcional de Life, te debes a ti mismo aprender sobre el algoritmo de Gosper. Utiliza ideas de la programación funcional para lograr billones de generaciones por segundo en tablas trillions de cuadrados en un lado. Eso suena imposible, lo sé, pero es completamente posible; Tengo una implementación pequeña y agradable en C # que maneja con facilidad tableros cuadrados de 2 ^ 64 cuadrados en un lado.

El truco consiste en aprovechar la enorme auto-semejanza de los tableros de vida a lo largo del tiempo y el espacio. Al memorizar el estado futuro de grandes secciones del tablero, puede avanzar rápidamente grandes secciones a la vez.

Hace muchos años que tengo la intención de publicar una introducción para principiantes al algoritmo de Gosper, pero nunca he tenido el tiempo. Si termino haciéndolo, publicaré un enlace aquí.

Tenga en cuenta que desea buscar Algoritmo de Gosper para cálculos de vida , no el Algoritmo de Gosper para calcular sumas hipergeométricas.

    
respondido por el Eric Lippert 21.11.2011 - 19:30
3

Buena coincidencia, cubrimos este problema exacto en nuestra conferencia de Haskell de hoy. Es la primera vez que lo veo, pero aquí hay un enlace al código fuente que nos dieron:

enlace

    
respondido por el Shane 22.11.2011 - 01:42
3

Es posible que desee ver las implementaciones en RosettaCode para inspirarse.

Por ejemplo, hay versiones funcionales de Haskell y OCaml que crean una nueva placa cada turno aplicando una función a la anterior, mientras que la versión gráfica de OCaml utiliza dos matrices y las actualiza alternativamente para la velocidad.

Algunas de las implementaciones descomponen la función actualizar de la placa en funciones para contabilizar el entorno, aplicando la regla de vida y iterando sobre el tablero. Esos parecen componentes útiles para basar un diseño funcional. Intente modificar solo el tablero, manteniendo todo lo demás como funciones puras.

    
respondido por el Toby Kelsey 22.11.2011 - 00:57
1

Aquí hay una versión corta puramente funcional en Clojure. Todo el crédito es para Christophe Grand, que publicó esto en su blog: Juego de Conway de La vida

(defn neighbours [[x y]]
  (for [dx [-1 0 1] 
        dy (if (zero? dx) [-1 1] [-1 0 1])]
    [(+ dx x) (+ dy y)]))

(defn step [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

El juego se puede jugar aplicando repetidamente la función "step" a un conjunto de celdas, por ejemplo:

(step #{[1 0] [1 1] [1 2]})
=> #{[2 1] [1 1] [0 1]}

La inteligencia es la parte (celdas vecinas de mapcat) - lo que esto hace es crear una lista de ocho vecinas para cada una de las celdas activas y las concatena todas juntas. Luego, la cantidad de veces que cada celda aparece en esta lista se puede contar con (frecuencias ...) y, finalmente, las que tienen los conteos de frecuencia correctos pasan a la siguiente generación.

    
respondido por el mikera 22.11.2011 - 12:37

Lea otras preguntas en las etiquetas