Acabo de terminar de implementar una versión de Conway «s Game of Life usando Java.

Siendo solo un estudiante universitario, estoy seguro de que mi código no es ni de lejos perfecto, y me preguntaba si podrías ver mi código. ¿En qué puedo mejorar? ¿Hay formas más rápidas para implementar ciertas áreas de mi código? ¿Hay un exceso de código que pueda recortar? ¿Existe una forma más inteligente de implementar el Juego de la vida de Conway?

EDITAR:

Con la esperanza de recibir más comentarios, aquí está la teoría detrás de mi implementación:

Para referencia, aquí están los reglas para el juego de la vida de Conway (tomadas de wikipedia):

  1. Cualquier célula viva con menos de dos vecinos vivos muere, como por falta de población.
  2. Cualquier célula viva con remolque o tres vecinos vivos viven hasta la próxima generación.
  3. Cualquier célula viva con más de tres vecinos vivos muere, como si hubiera pasado rpoblación
  4. Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva, como por reproducción.

Descripción general:

  1. A perspectiva diferente sobre el juego de la vida de Conway
  2. Reglas tácitas
  3. Explicación de métodos importantes (y estructuras de datos utilizadas)

Una perspectiva diferente del Juego de la vida de Conway

Imaginemos primero el Juego de la vida como una cuadrícula de ansiedad ( también asumirá que esta cuadrícula tiene coordenadas tales que la esquina inferior izquierda se denota como (0,0) y la esquina superior derecha se denota como (n, n) donde n es un número entero positivo). Esta cuadrícula bidimensional representa un grupo de n * n números de celdas. Cada bloque de cuadrícula se puede considerar como una celda, que no solo almacena un valor booleano (vivo o muerto) para describir el estado de la celda, sino que también detalla su ubicación a través de sus coordenadas. Además, el estado actual de todas las células determina qué células morirán, continuarán viviendo o nacerán en la próxima generación de acuerdo con las reglas que se encuentran arriba.

Sin embargo, en una perspectiva diferente, el juego de Conway de la vida es muy similar al juego buscaminas. Podemos pensar en una celda viva como una mina, y sus vecinas almacenan el número de minas más cercanas a ella. De esta manera, podemos usar fácilmente las reglas anteriores para determinar la generación futura (en particular, qué células morirán y qué células nacerán).

¿Qué pasa con las células que están vivas actualmente? ¿pedir? Bueno, podemos representarlos fácilmente como un número entero mayor que 10, donde el lugar de uno indica cuántos vecinos vivos tiene la celda actualmente viva, y los lugares de diez indican que la celda está viva.

Reglas tácitas

Una observación que se me ocurrió es que el juego de la vida solo se preocupa por las células vivas. Solo las células que están vivas pueden morir, las células que continúan viviendo tienen que estar ya vivas y las células solo pueden nacer si tienen vecinos que estén vivos. Como resultado, verificar toda la cuadrícula (complejidad de tiempo: O (n ^ 2)) para determinar la generación futura de células sería un desperdicio total. Sería mucho más rápido si almacenara todas las células vivas actualmente y verificara cada célula viva junto con sus vecinas para determinar la próxima generación (que es exactamente lo que hice).

Explicación de métodos importantes (y estructuras de datos utilizadas)

birth (): itera sobre un HashMap que contiene un par clave-valor de todas las celdas vivas junto con sus vecinas. Si el par clave-valor sigue las reglas del juego de la vida anterior, la clave (un valor entero que representa la ubicación de una celda) se inserta en una pila que contiene la próxima generación de celdas vivas. Después de cada iteración, el valor de la cuadrícula se restablece a 0 y el par clave-valor se elimina del HashMap.

insertAlive (): abre la pila e inserta la celda viva en la cuadrícula. La inserción de una celda viva sigue la estructura del buscaminas (los vecinos de una celda viva se incrementarán en 1 y la celda viva se incrementará en 10 para indicar que está viva). Todos los vecinos y las celdas vivas se colocan en un HashMap para que birth () pueda ejecutarse correctamente

printBoard () (debería llamarse boardToString): usa un generador de cadenas para formatear la cuadrícula en una cadena.

Nota : la mayoría de los comentarios se han eliminado porque no añaden mucho a la legibilidad de el código

CellularAutomaton.java

package first; public abstract class CellularAutomaton{ public abstract String lifeCycle(); public abstract boolean rules(int num); } 

GameOfLife.java

 package first; import java.util.Stack; import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class GameOfLife extends CellularAutomaton { int board[][]; int dim; Stack<Integer> stackCells; HashMap<Integer, Integer> hmapCells; public gameOfLife(int d, Stack<Integer> s){ board = new int[d][d]; dim = d; stackCells = s; hmapCells = new HashMap<>(); } public boolean rules(int num){ return num == 3 || num == 12 || num == 13; } private void birth() { Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator(); while(it.hasNext()) { Map.Entry<Integer,Integer> pair = it.next(); int key = pair.getKey(); if(rules(pair.getValue())){ stackCells.add(key); } board[key/dim][key%dim] = 0; it.remove(); } } private void insertAlive() { while(!stackCells.isEmpty()) { int cell = stackCells.pop(); int x = cell / dim; int y = cell % dim; int startX = (x <= 0) ? 0 : x - 1; int startY = (y <= 0) ? 0 : y - 1; int endX = (x >= dim - 1) ? x + 1 : x + 2; int endY = (y >= dim - 1) ? y + 1 : y + 2; for(int i = startX; i < endX; ++i) { for(int j = startY; j < endY; ++j) { hmapCells.put(i * dim + j, ++board[i][j]); } } hmapCells.put(cell, board[x][y] += 9); } } private String printBoard() { StringBuilder s = new StringBuilder(); for(int elements[] : board) { for(int element : elements) { if(element >= 10){ s.append("* "); } else { s.append(" "); } } s.append("\n"); } return s.toString(); } public String lifeCycle() { birth(); insertAlive(); return printBoard(); } }  

Simulation.java

package first; import java.util.Stack; public class Simulation { public static void main(String args[]) throws InterruptedException{ int dim = 70; Stack<Integer> init = new Stack<>(); //all vals pushed to init is of the form: xPos * dim + yPos init.push(351); init.push(352); init.push(421); init.push(422); init.push(245); init.push(246); init.push(315); init.push(316); init.push(361); init.push(431); init.push(501); init.push(292); init.push(572); init.push(223); init.push(643); init.push(224); init.push(644); init.push(435); init.push(296); init.push(576); init.push(367); init.push(437); init.push(507); init.push(438); init.push(231); init.push(301); init.push(371); init.push(232); init.push(302); init.push(372); init.push(163); init.push(443); init.push(165); init.push(445); init.push(95); init.push(515); GameOfLife gOL = new GameOfLife(dim, init); while(true) { System.out.print(gOL.lifeCycle()); Thread.sleep(100); System.out.print("\033[H\033[2J"); } } } 

Comentarios

  • Usted ‘ ha hecho Un punto de decir que esta es una implementación diferente, pero no hay nada que explique la teoría detrás de su implementación o los algoritmos y fórmulas relativamente oscuros que ‘ estás usando.
  • Este es un ejercicio popular, por lo que también te aconsejo que eches un vistazo a las implementaciones que puedes encontrar en línea: es ‘ muy instructivo. Me gusta especialmente esta esencia que muestra una implementación reactiva en Java 8 (usando RxJava) – no sa Sin embargo, sería un buen código de producción .

Respuesta

Primero de Todos, creo que el algoritmo es bastante inteligente, lo cual, para mi humilde experiencia, no es tan común para un estudiante universitario. ¡Así que felicidades si se le ocurrió por sí mismo! Si está buscando implementaciones inteligentes, le recomendaría algunas funcionales, por ejemplo, en Haskell ; consulte también Shortest game de la vida .

Ahora, tenga cuidado con la inteligencia. Un buen código debe ser fácil de leer , fácil de entender . Por supuesto, esto no siempre es posible cuando se trata de un algoritmo complejo, pero creo que debería ser un objetivo.

jjjjjjjjjjjj dijo:
Nota: la mayoría de los comentarios se han eliminado porque no agregan en gran medida para la legibilidad del código

El objetivo de los comentarios es ayudar a las personas a entender su código (en términos generales, céntrese en » por qué » en lugar de » qué «). Aquí, para ayudar a las personas a entender que tenía que agregar mucho texto a su publicación. Idealmente, esto no es necesario porque el código está:

  • auto-documentado,
  • comentado para borrar cosas complejas / implícitas.

Por ejemplo, aquí hay una reescritura rápida de su código en un intento de hacer que el código sea más expresivo:

GameOfLife.java

 /** * Computes the next state of the automaton by using Conway"s original rules. */ public class GameOfLife extends CellularAutomaton { /** * Stores all cells in a two-dimensional matrix. The value stored is * the number of live neighbors of the cell, +10 if the cell is alive. */ private int board[][]; private int dim; /* * index(cell) = cellX * dim + cellY */ private Stack<Integer> indexesOfCellsAliveAtNextGeneration; private HashMap<Integer, Integer> cellsMaybeAliveAtNextGeneration; public GameOfLife(int d, Stack<Integer> s){ board = new int[d][d]; dim = d; indexesOfCellsAliveAtNextGeneration = s; cellsMaybeAliveAtNextGeneration = new HashMap<>(); } public String newGeneration() { populateWorldWithAliveCellsFromPreviousGeneration(); computeCellsMaybeAliveAtNextGeneration(); return boardAsString(); } private void populateWorldWithAliveCellsFromPreviousGeneration() { for (Map.Entry<Integer, Integer> cell : cellsMaybeAliveAtNextGeneration.entrySet()) { int cellIndex = cell.getKey(); int cellValue = cell.getValue(); if(willBeAlive(cellValue)){ indexesOfCellsAliveAtNextGeneration.add(cellIndex); } board[cellIndex/dim][cellIndex%dim] = 0; } } private static boolean willBeAlive(int cell){ return (!isAlive(cell) && nbOfNeighbors(cell) == 3) || (isAlive(cell) && (nbOfNeighbors(cell) == 2 || nbOfNeighbors(cell) == 3)); } private static boolean isAlive(int cell) { return cell >= 10; } private static int nbOfNeighbors(int cell) { return cell % 10; } private void computeCellsMaybeAliveAtNextGeneration() { cellsMaybeAliveAtNextGeneration.clear(); while(!indexesOfCellsAliveAtNextGeneration.isEmpty()) { int cellIndex = indexesOfCellsAliveAtNextGeneration.pop(); int cellX = cellIndex / dim; int cellY = cellIndex % dim; int topLeftNeighbourX = (cellX <= 0) ? 0 : cellX - 1; int topLeftNeighbourY = (cellY <= 0) ? 0 : cellY - 1; int bottomRightNeighbourX = (cellX >= dim - 1) ? cellX + 1 : cellX + 2; int bottomRightNeighbourY = (cellY >= dim - 1) ? cellY + 1 : cellY + 2; // Iterate through every cell"s neighbor to increate their neighbor number for(int i = topLeftNeighbourX; i < bottomRightNeighbourX; ++i) { for(int j = topLeftNeighbourY; j < bottomRightNeighbourY; ++j) { boolean isNeighbor = i != cellX || j != cellY; if (isNeighbor) { int neighborIndex = i * dim + j; cellsMaybeAliveAtNextGeneration.put(neighborIndex, incrementedNumberOfNeighbors(i, j)); } } } cellsMaybeAliveAtNextGeneration.put(cellIndex, makeAlive(cellX, cellY)); } } private int incrementedNumberOfNeighbors(int x, int y) { return ++board[x][y]; } private int makeAlive(int x, int y) { return board[x][y] += 10; } private String boardAsString() { StringBuilder s = new StringBuilder(); for(int[] cells : board) { for(int cell : cells) { if(isAlive(cell)){ s.append("* "); } else { s.append(" "); } } s.append("\n"); } return s.toString().trim(); } }  

Cambié el nombre de algunas variables / métodos e introduje algunos métodos de utilidad. El código es un poco más largo y se siente más detallado, pero en mi humilde opinión también es más fácil de entender. Sigue siendo muy procedimental (lo que no es malo en sí, especialmente para un programa tan simple) pero es posible que desee intentar agregar más expresividad al introducir nuevas clases como Board o Cell. Encontrarás estas implementaciones de OO en GitHub .

Su código también puede tener problemas de memoria con placas grandes. De hecho, su variable board[][] almacena todas las celdas, incluso las muertas. Con una placa de 10000 x 10000 que contiene solo ~ 5/6 celdas, desperdiciará mucha memoria. Una solución es usar una matriz dispersa (básicamente, una conjunto que contiene solo células vivas).

Como nota al margen, hace unos años también intenté modelar un GoL altamente configurable en un » pure » OO way; mi código está en GitHub si quieres comprobarlo. El método que calcula la próxima generación del world es ImmutableGeneration :: nextGeneration ; dado un conjunto de celdas vivas, básicamente: 1) calcula todas las celdas vecinas y luego 2) mantiene solo las que estarán vivas. Las reglas que indican si una celda estará viva o muerta se implementan en Rule.java .


EDIT : personal opinión sobre concisión versus verbosidad cuando se trata de n Estoy deseando responder un comentario

En primer lugar, creo que no hay respuestas correctas: se trata de compensaciones y preferencias personales. Nombrar es difícil y encontrarás muchos artículos sobre el tema.

Solo hay dos cosas difíciles en Ciencias de la Computación: invalidación de caché y nombrar cosas
– Phil Karlton

Mi opinión es que la concordia es agradable pero puede llevar a ambigüedades. Y la ambigüedad, especialmente la oculta, es una amenaza.El primer ejemplo que me viene a la mente es mezclar unidades por error:

 // Everything looks good... double pathLength = distanceFromGoal + distanceToTarget; // ... but adding units makes easy to spot bugs double pathLengthInKilometers = distanceFromGoalInMeters + distanceToTargetInMillimeters;  

Eso Dicho esto, los nombres largos hacen que el código sea más difícil de leer. Se pueden reducir teniendo en cuenta dos cosas:

  • el contexto (por ejemplo, el nombre del método / clase / paquete adjunto),
  • el alcance (una variable local en un método de 3 líneas puede estar bien con un nombre corto, mientras que una función utilizada varias veces en todo el código puede necesitar uno más largo).

Eso también es lo que recomienda Convenciones de nomenclatura de Google .

Como última nota, como sugirió, los nombres muy largos pueden verse como olores de código. Por lo general, el problema es falta de cohesión (la clase / método hace cosas muy diferentes; una vez más, no hay métricas claras al respecto, depende de sentimiento del desarrollador). Por ejemplo, en el código que propuse, podemos pensar en populateWorldWithAliveCellsFromPreviousGeneration como un método que tiene responsabilidades: 1) calcular las células que estarán vivas en la próxima generación y 2) poblar el mundo. Así podríamos dividirlo en dos: populateWorldWith(aliveCellsFromPreviousGeneration()).

De la misma manera podríamos reunir los atributos cuyo nombre termina con » atNextGeneration » bajo una nueva Generation clase:

 public class GameOfLife extends CellularAutomaton { private Generation lastGeneration; public String newGeneration() { this.lastGeneration = lastGeneration.nextGeneration(); return this.lastGeneration.toString(); } } public class Generation { public Generation nextGeneration() { return new Generation(aliveAtNextGeneration(this.aliveCells)); } ... }  

Pero dividir la lógica en demasiadas clases también aumentará la complejidad de la arquitectura y dificultará la comprensión del flujo.

Como Conclusión Le aconsejaría que tenga en cuenta que cualquier parte del código es susceptible de ser modificado por desarrolladores que no tienen conocimientos previos sobre el proyecto y que deben entender qué hace el código y por qué lo hace para que puedan mantenerlo o reutilizar partes sin introducir regresiones. No hay una fórmula mágica: solo compensaciones, y lo que importa cuando hace una elección es que:

  • puede identificar las compensaciones,
  • comprende los pros y los contras de cada alternativa y elija una de ellas a sabiendas.

(pero no le presione demasiado: KISS y recuerde que el código puede ser refactorizado a partir de entonces)

Comentarios

  • Muchas gracias por su comentario. Estoy muy contento de que hayas comentado porque nunca hubiera pensado en almacenar solo las celdas vivas (esto cambia mucho mi código y, en mi opinión, lo hace mucho mejor). Quería preguntarle un poco sobre su opinión sobre el equilibrio entre ser claro con los nombres de las variables y ser conciso. En otras palabras, ¿cómo se puede determinar si el programa es demasiado detallado? ¿Significa eso que tienes que pasar un tiempo extraordinariamente largo creando los nombres de variables correctos o que hay algo defectuoso en tu lógica y diseño del código? Gracias de nuevo.
  • Edité mi respuesta para compartir mi opinión sobre ella. Es ‘ un montón de texto que básicamente dice que » no hay respuestas correctas, es ‘ s todo acerca de las compensaciones, así que piense en los pros y los contras al hacer una elección «.

Respuesta

Solo tengo una pequeña recomendación con respecto a la legibilidad. Cuando tienes un método llamado printBoard, normalmente esperarías que imprima el tablero . Un mejor nombre para ese método sería boardToString.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *