Leyendo el hilo de la conjetura de Collatz me he acordado otro juego iterativo que me mantuvo entretenido hace muchos años:
El juego de la Vida de John Horton Conway (1970)Desde entonces ha llovido mucho, han creado organismos que generan los números primos, maquinas de Turing, ... e incluso un ordenador programable (https://conwaylife.com/wiki/index.php?title=Spartan_universal_computer-constructor).
Las reglas (https://es.wikipedia.org/wiki/Juego_de_la_vida) son muy simples:
- Una célula muerta con 3 vecinos nace.
- Una célula viva con 2 ó 3 vecinos sobrevive, en otro caso muere.
(https://farm5.static.flickr.com/4008/4648481638_2d5d91c9d4_o.gif)
El reto es el siguiente:
Usando una rejilla de 40x40 células, mostrar cada generación en la pantalla del NXT para este organismo, que tras 106 generaciones se estabiliza en un cuadro y un deslizador.
(https://conwaylife.com/wiki/images/b/b6/Blockandglider.png) ---> (https://conwaylife.com/wiki/images/9/93/BlockandgliderFinal.png)
Veamos de lo que es capaz el NXT, seguro que nos sorprende. Poner el código y el tiempo y/o cualquier comentario.
| RobotC | | NXC |
1º | PotaG - 89322 ms | | 31415926 - 436389 ms |
2º | 31415926 - 100540 ms | |
Seguro que nadie bate mi record: 100540 milisegundos !!!!
Citar //////////////////////////////////////////////////////////////////////////////////////
//
// Conway's life game en NXT
//
//////////////////////////////////////////////////////////////////////////////////////
task main()
{
byte pantalla[40][40];
byte nuevaPantalla[40][40];
byte x, y, vecinos;
pantalla[20][20]=1; pantalla[21][20]=1;
pantalla[20][21]=1; pantalla[22][21]=1;
pantalla[22][22]=1; pantalla[23][22]=1;
eraseDisplay();
nxtDrawRect(30, 10, 70, 50);
for (x=1; x<39; x++)
for (y=1; y<39; y++)
if (pantalla[x][y]==1)
nxtSetPixel(x+30, y+10);
time1[T1]=0;
while (true) {
memset(nuevaPantalla,0,1600);
for (x=1; x<39; x++)
for (y=1; y<39; y++) {
vecinos = pantalla[x - 1][y - 1] + pantalla[x - 1][y ] + pantalla[x - 1][y + 1] +
pantalla[x ][y - 1] + pantalla[x ][y + 1] +
pantalla[x + 1][y - 1] + pantalla[x + 1][y ] + pantalla[x + 1][y + 1];
// regla 23/3
if (pantalla[x][y] ==1) {// hay vida
if (vecinos == 2 || vecinos == 3) nuevaPantalla[x][y] = 1; // sobrevive
} else { // no hay vida
if (vecinos == 3) nuevaPantalla[x][y] = 1; // nace
}
}
eraseDisplay();
nxtDrawRect(30, 10, 70, 50);
for (x=1; x<39; x++)
for (y=1; y<39; y++)
if (nuevaPantalla[x][y]==1)
nxtSetPixel(x+30, y+10);
memcpy(pantalla, nuevaPantalla, 1600);
}
long t = time1[T1];
nxtDisplayString(0, "Tiempo %d ms", t);
while (nNxtButtonPressed == kNoButton);
}
Usas RobotC ¿verdad? Eso ya te da una ventaja inicial ... :D
Me gusta la propuesta, aunque en estos momentos a duras penas consigo hacer otra cosa aparte de todo lo que ya está comprometido. Sin embargo me parece una manera excelente de aprender a usar la pantalla del NXT por lo que buscaré un momento para profundizar un poco más en cuanto pueda...
Si, con RobotC :E. Pero vale cualquier lenguaje y optimización que se os ocurra o encontréis. Lo importante es que sea el NXT el que lo haga y lo más rápido posible.
Mañana cambio el firmware y lo escribo para NXC con su tiempo, tal cual está ahora.
Vale, yo doy tu tiempo por bueno :lengua:
Tiene pinta de ser un código bastante optimizado X)
Me ha encantado el juego, no lo conocía :} y me hace mucha gracia cómo se genera con la "simple" proposición de las reglas un letrero :O
Este código (con tu permiso) me lo guardo para probarlo :lengua:
PD: Es diferente, pero lo leí hace poco y me hizo gracia:
¿Te atreves con Von Neumann y un elefante (https://francisthemulenews.wordpress.com/2010/05/27/como-dibujar-un-elefante-con-solo-cuatro-numeros-complejos/)? Parece "complejo"... o_o :lengua:
No me des ideas, no me des ideas .... que me lio :guino:. Primero el conjunto de Mandelbrot que es más sencillo y luego el elefante. Aunque ya fundí un ordenador y no quiero quemar el NXT.
PD: No tienes que pedir permiso.
Que conste que no lo he probado, no tengo RobotC, pero se me ocurre una forma de ganar unas centésimas... imprimiendo la pantalla en el momento en que decides si una célula esta viva o no y eliminando así los dos últimos "for".
Por lo demás, dudo que se pueda hacer en menos tiempo debido a que el RobotC es el más rápido procesando (creo).
Por cierto, es posible que haya un error en el listado, en el primero de los dos últimos "for" cuentas hasta 49 cuando debería ser 39 ¿no?
Pues yo no entiendo en qué consiste, alguien me lo explica por favor??
Está muy bien explicado en el link a las reglas (https://es.wikipedia.org/wiki/Juego_de_la_vida) que aparece en el primer mensaje
Otra cosa, en los todos los "for" (excepto el mencionado en mi anterior mensaje) cuentas del 1 al 39, es decir, procesas una cuadricula de 39x39, no 40x40.
Edito: Fallo mío, no me di cuenta de que pones <39.
Puedeís consultar estos enlaces donde hay mucha más información del juego:
Wikipedia https://es.wikipedia.org/wiki/Juego_de_la_vida (https://es.wikipedia.org/wiki/Juego_de_la_vida)
LifeWiki https://www.conwaylife.com/wiki (https://www.conwaylife.com/wiki)
Catalogo y noticias https://pentadecathlon.com/lifeNews/ (https://pentadecathlon.com/lifeNews/)
Extremo https://www.nathanieljohnston.com/index.php/tag/conways-game-of-life (https://www.nathanieljohnston.com/index.php/tag/conways-game-of-life)
Para PC https://golly.sourceforge.net/ (https://golly.sourceforge.net/) como veis el letrero no es de fabricación propia.
Cita de: PotaG en 29 de Mayo de 2010, 14:32:49 PM
Por cierto, es posible que haya un error en el listado, en el primero de los dos últimos "for" cuentas hasta 49 cuando debería ser 39 ¿no?
upsss! Se me coló :O. Lo he corregido y actualizado el tiempo. Además ahora el tiempo lo mide el NXT, se me estaba secando la lengua de contar segundos :P.
La cuadricula es de 40x40 celdas y los índices del array van del 0 al 39. Como a nadie le gusta vivir en la afueras solo se procesan las casillas de 1 a 38 (38x38) de esta forma no hay que distinguir si te sales fuera de la cuadricula al calcular los vecinos.
Por otra parte, que curioso que no nos dejen usar punteros, redimensionar arrays ni (teóricamente) acceder fuera del rango de un array y con el 49 no me daba ningún problema. :( Estas cositas y otras que he encontrado en RobotC hacen que me plantee seriamente cambiar de entorno.
Cita de: PotaG en 29 de Mayo de 2010, 14:32:49 PM
se me ocurre una forma de ganar unas centésimas... imprimiendo la pantalla en el momento en que decides si una célula esta viva o no y eliminando así los dos últimos "for".
Acabas de ahorrar un 11% de tiempo, ENHORABUENA :D eres el namberruan por ahora. Sin que sirva de precedente, lo he probado y he tomado las medidas.
A este ritmo conseguiremos tener que poner un delay para verlo en pantalla. Venga animaros
Citar
time1[T1]=0;
for(int k = 0 ; k<106 ; k++)
{
memset(nuevaPantalla,0,1600);
eraseDisplay();
nxtDrawRect(30, 10, 70, 50);
for (x=1; x<39; x++)
for (y=1; y<39; y++)
{
vecinos = pantalla[x - 1][y - 1] + pantalla[x - 1][y ] + pantalla[x - 1][y + 1] +
pantalla[x ][y - 1] + pantalla[x ][y + 1] +
pantalla[x + 1][y - 1] + pantalla[x + 1][y ] + pantalla[x + 1][y + 1];
// regla 23/3
if (pantalla[x][y] ==1) {// hay vida
if (vecinos == 2 || vecinos == 3) {
nuevaPantalla[x][y] = 1; // sobrevive
nxtSetPixel(x+30, y+10);
}
} else { // no hay vida
if (vecinos == 3) {
nuevaPantalla[x][y] = 1; // nace
nxtSetPixel(x+30, y+10);
}
}
}
// eraseDisplay();
// nxtDrawRect(30, 10, 70, 50);
//
// for (x=1; x<39; x++)
// for (y=1; y<39; y++)
// if (nuevaPantalla[x][y]==1)
// nxtSetPixel(x+30, y+10);
memcpy(pantalla, nuevaPantalla, 1600);
}
He dividido la clasificación.
Esta es la version para NXC, el tiempo :-\ 436389 ms
Por cierto han sacado una nueva versión y no me he enterado hasta hoy, tendría que haber un tema para hacer eco de estas cosas.
Citar
//////////////////////////////////////////////////////////////////////////////////////
//
// Conway's life game
//
//////////////////////////////////////////////////////////////////////////////////////
task main()
{
byte pantalla[40][40];
byte nuevaPantalla[40][40];
byte x, y, vecinos;
pantalla[20][20]=1; pantalla[21][20]=1;
pantalla[20][21]=1; pantalla[22][21]=1;
pantalla[22][22]=1; pantalla[23][22]=1;
RectOut(30, 10, 40, 40, true);
for (x=1; x<39; x++)
for (y=1; y<39; y++)
if (pantalla[x][y]==1) PointOut(x+30, y+10);
long t = CurrentTick();
for(int k = 0 ; k<106 ; k++)
{
for (x=1; x<39; x++)
for (y=1; y<39; y++) nuevaPantalla[x][y] = 0;
//memset(nuevaPantalla,0,1600);
for (x=1; x<39; x++)
for (y=1; y<39; y++)
{
vecinos = pantalla[x - 1][y - 1] + pantalla[x - 1][y ] + pantalla[x - 1][y + 1] +
pantalla[x ][y - 1] + pantalla[x ][y + 1] +
pantalla[x + 1][y - 1] + pantalla[x + 1][y ] + pantalla[x + 1][y + 1];
// regla 23/3
if (pantalla[x][y] ==1) {// hay vida
if (vecinos == 2 || vecinos == 3)
nuevaPantalla[x][y] = 1; // sobrevive
} else { // no hay vida
if (vecinos == 3)
nuevaPantalla[x][y] = 1; // nace
}
}
RectOut(30, 10, 40, 40, true);
for (x=1; x<39; x++)
for (y=1; y<39; y++) {
if (nuevaPantalla[x][y]==1) PointOut(x+30, y+10);
pantalla[x][y] = nuevaPantalla[x][y];
}
//memcpy(pantalla, nuevaPantalla, 1600);
}
TextOut(0, LCD_LINE1, NumToStr(CurrentTick()-t));
while (!ButtonPressed(BTNCENTER,true));
}
Hasta le fecha nunca he usado un array :P y este es un excelente proyecto para por fin iniciarme en eso (aunque con lo que estoy consiguiendo dormir mi cabeza da vueltas incluso sin mirar código :D)
Respecto de NXC, es cierto que no tenemos tema de actualizaciones., aunque por otro lado tan solo esta semana ha habido 3 cambios... claro que se puede distinguir entre pequeñas mejoras y versiones intermedias. Si interesa podemos abrir un tema específico...
De los punteros en RobotC te puedes olvidar (tampoco los hay en NXC ni NBC), no están ni en la lista de posibles futuros cambios y redimensionar arrays tampoco es una prioridad. Aún así, creo que RobotC como herramienta es muy buena y que tiene un equipo de programadores que lo va mejorando bastante comunicativo (en su foro enseguida encontrarás respuesta a cualquier pregunta).
La cuadrícula tiene 1.600 celdas, con lo que al calcular los vecinos hacemos 11.200 sumas por generación, 1.187.200 hasta que se estabiliza tras 106 generaciones.
¿Estaremos repitiendo cálculos? ¿Los podríamos reutilizar? ¿Hace falta analizar las 1.600 celdas? ¿Podemos limitar las celdas a analizar?
Y lo más importante para conocer cómo funciona el NXT:
¿Cómo se evalúa la expresión pantalla[ ][ ]? Lo hace 22.400 veces por generación, 2.374.400 :O veces hasta que se estabiliza.
Cita de: Jetro en 30 de Mayo de 2010, 08:54:06 AM
Hasta le fecha nunca he usado un array
Yo todos los días aprendo algo, no son complicados y muy útiles. A groso modo:
int x; es una caja donde guardas un valor enteros y para usarla escribes x en cualquier expresión.
int x[10]; son 10 cajas done guardas valores enteros y para usarlas escribes x[índice].
Lo que no se puede hacer en RobotC es definirlo así: int x[]; y luego reservar memoria para ubicar el tamaño que quieras.
Tomo nota: Lenguajes e IDEs para NXT