Sorprendido alegremente por la respuesta de los programadores que visitan unocero, a escasas horas de empezar el reto, a eso de las 10 de la noche del sábado -cuando se publicó el artículo- recibí a la 1:30 am del domingo la primera respuesta. Dos más llegaron a eso de las 2:15 am y 4:40 am. En el transcurso de hoy llegaron un par más.
De izquierda a derecha: Adán Enrique, Manuel Alcántara y Charles López
El ganador fue Adán Enrique Aguilar, que escribió un programa en Java, el cual pongo a consideración de todos:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package jugadasgato;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
*
* @author adam
*/
public class JugadasGATO {
/**
* @param args the command line arguments
*/
static class NodoTablero {
public String tab[][] = {{“b”, “b”, “b”}, {“b”, “b”, “b”}, {“b”, “b”, “b”}};
boolean quienTira = true; // true tira la X, False tira la O
public NodoTablero() {
}
public NodoTablero(String t[][]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
this.tab[i][j] = t[i][j];
}
}
}
@Override
public String toString() {
String s = “”;
s = Arrays.toString(tab[0]) + “\n” + Arrays.toString(tab[1]) + “\n” + Arrays.toString(tab[2]);
return s;
}
}
public static void main(String[] args) {
LinkedList colaNodos = new LinkedList();
colaNodos.add(new NodoTablero());
long contadorNodos = 1;
long ti = System.currentTimeMillis();
while (!colaNodos.isEmpty()) {
//Sacamos el primer elemento de la cola
NodoTablero nactual = colaNodos.pollFirst();
//lo guardamos o imprimimos en la pantalla
imprimir(nactual);
//Intentamos tirar en las 9 casillas
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
//Creamos un nuevo tablero, resultado del tiro
NodoTablero tiroNuevo = null;
//Preguntamos al tablero actual a quien le toca tira
//quienTira = true es X
//quienTira = false es 0
String tira = “X”;
if (!nactual.quienTira) {
tira = “O”;
}
//Intentamos tirar en la posición X y Y del tablero actual.
tiroNuevo = regla(tira, x, y, nactual);
//si se pudo tirar en esa posición
if (tiroNuevo != null) {
// se le indica al nuevo tablero a quien le tocara tirar en el siguiente turno
// tira el contrario al que tiro en este turno.
tiroNuevo.quienTira = !nactual.quienTira;
//varificamos si es un tiro ganador
if (tiroGanador(tiroNuevo, tira)) {
//si es un tiro ganador entonces simplemente lo imprimimos
imprimir(tiroNuevo);
System.out.println(“GANADOR”);
contadorNodos++;
} else {
//si no es un tiro ganador lo agregamos a la cola.
colaNodos.add(tiroNuevo);
contadorNodos++;
}
}
}
}
System.out.println(colaNodos.size());
}
saveString(“MovimientosGato.txt”, “\nTableros totales = ” + contadorNodos);
saveString(“MovimientosGato.txt”, “\nTiempo Total = ” + (System.currentTimeMillis() – ti));
}
public static NodoTablero regla(String tira, int casillaX, int casillaY, NodoTablero nt) {
if (nt.tab[casillaX][casillaY].equals(“b”)) {
NodoTablero nuevoNodo = new NodoTablero(nt.tab);
nuevoNodo.tab[casillaX][casillaY] = tira;
return nuevoNodo;
}
return null;
}
public static boolean tiroGanador(NodoTablero nt, String tiro) {
String t[][] = nt.tab;
if (t[0][0].equals(tiro) && t[0][1].equals(tiro) && t[0][2].equals(tiro)) {
return true;
}
if (t[1][0].equals(tiro) && t[1][1].equals(tiro) && t[1][2].equals(tiro)) {
return true;
}
if (t[2][0].equals(tiro) && t[2][1].equals(tiro) && t[2][2].equals(tiro)) {
return true;
}
if (t[0][0].equals(tiro) && t[1][1].equals(tiro) && t[2][2].equals(tiro)) {
return true;
}
if (t[0][2].equals(tiro) && t[1][1].equals(tiro) && t[2][0].equals(tiro)) {
return true;
}
return false;
}
public static void imprimir(NodoTablero nimprimir) {
saveString(“MovimientosGato.txt”, nimprimir.toString());
saveString(“MovimientosGato.txt”, “\n\n”);
System.out.println(nimprimir + “\n”);
}
public static void saveString(String fileName, String data) {
File f = new File(fileName);
try {
if (!f.exists()) {
f.createNewFile();
}
FileWriter fw = new FileWriter(f, true);
BufferedWriter bW = new BufferedWriter(fw);
bW.write(data);
bW.close();
} catch (IOException ex) {
Logger.getLogger(JugadasGATO.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
Enrique es de Veracruz y en un par de días le mando su memoria USB de 16 GBytes, ¡Felicidades!
Debido al interés que presentaron los siguientes dos programas, se dan dos premios más, uno fue para Manuel Alcántara Juárez. Él me mandó, además, los siguientes datos:
El programa genera 255168 posiciones donde 131,184 juegos los gana X, 77,904 los gana O y 46080 terminan en empate. El programa inicia con las “o” pero como dice mi tocayo, es isomorfo.
Éste es su código:
/* -------------------------------------------------------------------
* Main.java
* version 1.0
* Copyright (C) 2014 Manuel Alcantara Juarez
*
* Este programa es software libre; se puede redistribuir
* y/o modificar en los terminos establecidos por la
* Licencia Publica General de GNU tal como fue publicada
* por la Free Software Foundation en la version 2 o
* superior.
*
* Este programa es distribuido con la esperanza de que
* resulte de utilidad, pero SIN GARANTIA ALGUNA; de hecho
* sin la garantia implicita de COMERCIALIZACION o
* ADECUACION PARA PROPOSITOS PARTICULARES. Vease la
* Licencia Publica General de GNU para mayores detalles.
* -------------------------------------------------------------------
*/
/**
* Clase que manda a construir el arbol y lo escribe en un archivo.
* @author Manuel Alcantara Juarez
* @version 1.0
* 21 Junio 2014
*/
public class Main {
public static void main(String[] args){
Arbol gato = new Arbol();
gato.toFiles();
}
}
-------
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.logging.Level;
import java.util.logging.Logger;
/* -------------------------------------------------------------------
* Arbol.java
* version 1.0
* Copyright (C) 2014 Manuel Alcantara Juarez
*
* Este programa es software libre; se puede redistribuir
* y/o modificar en los terminos establecidos por la
* Licencia Publica General de GNU tal como fue publicada
* por la Free Software Foundation en la version 2 o
* superior.
*
* Este programa es distribuido con la esperanza de que
* resulte de utilidad, pero SIN GARANTIA ALGUNA; de hecho
* sin la garantia implicita de COMERCIALIZACION o
* ADECUACION PARA PROPOSITOS PARTICULARES. Vease la
* Licencia Publica General de GNU para mayores detalles.
* -------------------------------------------------------------------
*/
/**
* Clase que implementa Arboles para jugar desentemente al juego del Gato.
*
* @author Manuel Alcantara Juarez
* @version 1.0
* 21 Junio 2014
*/
public class Arbol {
/*Nodo raiz del arbol*/
private NodoArbolGato root;
/*Numero de ramas en el arbol*/
private int n_path, x_win, o_win, draw;
/*Objeto para escribir en archivos¨*/
private PrintWriter escritor;
/**
* Constructor crea un jugador maquina para el juego del gato.
*/
public Arbol() {
root = new NodoArbolGato();
generarArbol(root);
}
public void toFiles() {
try {
LinkedList s = new LinkedList<>();
n_path = x_win = o_win = draw = 0;
escritor = new PrintWriter("ArbolGato.txt");
printPaths(root, s);
escritor.close();
System.out.println("Se generaron: " + n_path + " caminos.\nDe los cuales: ");
System.out.println(x_win+" juegos donde gana x.");
System.out.println(o_win+" juegos donde gana o.");
System.out.println(draw+" donde se empata.");
} catch (FileNotFoundException ex) {
Logger.getLogger(Arbol.class.getName()).log(Level.SEVERE, null, ex);
}
}
/**
* Realiza un DFS sobre todos los caminos.
*
* @param node Nodo a partir del cual se hace la busqueda.
* @param path Trayectoria que se sigue desde el nodo raiz hasta el nodo
* pasado como parametro.
*/
private void printPaths(NodoArbolGato node, LinkedList path) {
//Agrego el nuevo nodo al path
path.add(node);
//Es nodo raiz, tengo que imprimir todo el camino.
if (node.nodos == null) {
escritor.append("############################################\nPath_" + n_path++ + "\n");
Iterator i = path.iterator();
while (i.hasNext()) {
escritor.append(i.next().toString() + "\n");
}
int ganador = terminado(node.tablero);
if (ganador == 0) {
draw++;
} else if (ganador == 1) {
x_win++;
} else {
o_win++;
}
} else {
for (NodoArbolGato nodo : node.nodos) {
printPaths(nodo, path);
}
}
//Elimino el nodo
path.removeLast();
}
/**
* Metodo que dice cuantos espacios vacios contiene el tablero.
*
* @param tablero Arreglo que contiene una representacion de un gato
* @return int que dice cuantos espacios vacios contiene el tablero.
*/
private int espaciosDisponibles(int[] tablero) {
int mov = 0;
for (int i = 0; i < 9; i++) {
if (tablero[i] == 0) {
mov++;
}
}
return mov;
}
/**
* Metodo que devuelve los indices del tablero en donde las pocisiones se
* encuentran vacias.
*
* @param tablero arreglo que contiene la representacion de un gato.
* @return int[] que contiene los indices en donde hay posiciones vacias.
*/
private int[] indicesPosicionesVacias(int[] tablero) {
int[] indices = new int[espaciosDisponibles(tablero)];
int aux = 0;
for (int i = 0; i < 9; i++) {
if (tablero[i] == 0) {
indices[aux] = i;
aux++;
}
}
return indices;
}
/**
* Metodo que dice si el juego ya se encuentra terminado.
*
* @param tablero que representa el gato.
* @return int que dice si ya se termino el juego. Regresa 0 si nadie ha
* ganado, 1 si gano el jugador Uno y 2 si gano el jugador Dos.
*/
private int terminado(int[] tablero) {
if (tablero[0] != 0 && tablero[0] == tablero[1] && tablero[0] == tablero[2]) {
return tablero[0];
} else if (tablero[3] != 0 && tablero[3] == tablero[4] && tablero[3] == tablero[5]) {
return tablero[3];
} else if (tablero[6] != 0 && tablero[6] == tablero[7] && tablero[6] == tablero[8]) {
return tablero[6];
} else if (tablero[0] != 0 && tablero[0] == tablero[3] && tablero[0] == tablero[6]) {
return tablero[0];
} else if (tablero[1] != 0 && tablero[1] == tablero[4] && tablero[1] == tablero[7]) {
return tablero[1];
} else if (tablero[2] != 0 && tablero[2] == tablero[5] && tablero[2] == tablero[8]) {
return tablero[2];
} else if (tablero[0] != 0 && tablero[0] == tablero[4] && tablero[0] == tablero[8]) {
return tablero[0];
} else if (tablero[2] != 0 && tablero[2] == tablero[4] && tablero[2] == tablero[6]) {
return tablero[2];
}
return 0;
}
/**
* Metodo recursivo que genera todo el arbol del juego a partir de un nodo
* que puede ser la raiz o los hijos de este.
*
* @param raiz arbol(Nodo) desde donde se va a comenzar a generar el arbol
* del juego.
*/
private void generarArbol(NodoArbolGato raiz) {
int movimientos = espaciosDisponibles(raiz.tablero);
int indices[] = indicesPosicionesVacias(raiz.tablero);
/*Verificamos si en el Nodo en que estamos ya hay un ganador.Si el metodo terminado nos regresa un 1, quiere decir
*que gana el jugador 1, por lo tanto es mala jugada, si regresa un 2 quiere decir que es muy buena jugada, y si regresa
*0 vemos si ya no hay movimientos, si no entonces seguimos construyendo el arbol.
*/
if (terminado(raiz.tablero) == 0 && movimientos != 0) {
raiz.nodos = new NodoArbolGato[movimientos];
for (int i = 0; i < movimientos; i++) {
//Inicializamos los nodos hijos del arbol con el tablero del padre.
raiz.nodos[i] = new NodoArbolGato();
System.arraycopy(raiz.tablero, 0, raiz.nodos[i].tablero, 0, 9);
//Creamos los diferentes movimientos posibles.
if (raiz.miTurno) {
raiz.nodos[i].tablero[indices[i]] = 1;
} else {
raiz.nodos[i].tablero[indices[i]] = 2;
}
//Cambiamos el turno de los hijos
raiz.nodos[i].miTurno = !raiz.miTurno;
//Generamos todos sus hijos a partir de esta raiz
generarArbol(raiz.nodos[i]);
}
}
}
}
------
/* -------------------------------------------------------------------
* ArbolDeJuegoGato.java
* version 1.0
* Copyright (C) 2014 Manuel Alcantara Juarez,
*
* Este programa es software libre; se puede redistribuir
* y/o modificar en los terminos establecidos por la
* Licencia Publica General de GNU tal como fue publicada
* por la Free Software Foundation en la version 2 o
* superior.
*
* Este programa es distribuido con la esperanza de que
* resulte de utilidad, pero SIN GARANTIA ALGUNA; de hecho
* sin la garantia implicita de COMERCIALIZACION o
* ADECUACION PARA PROPOSITOS PARTICULARES. Vease la
* Licencia Publica General de GNU para mayores detalles.
* -------------------------------------------------------------------
*/
/**
* Estructura base para construir el Arbol de Juego del llamado Gato
*
* @author Manuel Alcantara Juarez
* @version 1.0
* 21 Junio 2014
*/
public class NodoArbolGato {
/**
* Arreglo que contendra a los todos los posibles hijos de este arbol
*/
public NodoArbolGato nodos[];
/**
* Arreglo que guardara una posible jugada del juego.
*/
public int tablero[];
/**
* boolean que representa si es mi turno en el juego.
*/
public boolean miTurno;
/**
* Entero que representa que jugador gano en este posible Nodo.
*/
public int jugadorGanador;
/**
* Constructor crea un nuevo arbol sin definir cuantos hijos tendra.
*/
public NodoArbolGato() {
tablero = new int[9];
}
@Override
public String toString() {
String str="";
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
switch (tablero[i * 3 + j]) {
case 1:
str+="x";
break;
case 2:
str+="o";
break;
default:
str+="b";
}
}
str+="\n";
}
return str;
}
}
Finalmente, Charles López resolvió el problema así:
#include cstdlib
#include iostream
#include fstream
#include vector
using namespace std;
int main(int argc, char *argv[])
{
ofstream txt;
txt.open ("gato.txt");
std::vector< std::vector > map( 1000000, 10 );
int i,ii,iii,a,u,f,c;
map[0][0]='x';
a=0;
u=1;
c=0;
while(a != u) {
txt < < "\n \n";
if(map[a][0]==120){txt << "x";}
else if(map[a][0]==111){txt << "o";}
else if(map[a][0]==119){txt << "w";}
txt << " " << c << "\n";
for(iii=1;iii<10;iii++){
if(map[a][iii]==120){txt << "x";}
else if(map[a][iii]==111){txt << "o";}
else{txt << "#";}
if(iii==3 || iii==6){txt << "\n";}
}
// printf("\n");
// printf("\n");
// printf("%c", map[a][0]);
// printf("%i",c);
// printf(" a-");
// printf("%i",a);
// printf(" u-");
// printf("%i",u);
// printf("\n");
// for(iii=1;iii<10;iii++){
// if(map[a][iii] != 0){printf("%c", map[a][iii]);}else{printf("#");}
//
// if(iii==3 || iii==6){printf("\n");}
// }
if(map[a][0]!='w'){
for(i=1;i<10;i++){
if (map[a][i]==0){
for(ii=0;ii<10;ii++){map[u][ii]=map[a][ii];}
map[u][i]=map[a][0];
if(map[u][0]=='x'){map[u][0]='o';}else if(map[u][0]=='o'){map[u][0]='x';}
if((map[u][1]!=0) && ((map[u][1]==map[u][2]) && (map[u][2]==map[u][3]))){f=1;}else
if((map[u][4]!=0) && ((map[u][4]==map[u][5]) && (map[u][5]==map[u][6]))){f=1;}else
if((map[u][7]!=0) && ((map[u][7]==map[u][8]) && (map[u][8]==map[u][9]))){f=1;}else
if((map[u][7]!=0) && ((map[u][7]==map[u][4]) && (map[u][4]==map[u][1]))){f=1;}else
if((map[u][8]!=0) && ((map[u][8]==map[u][5]) && (map[u][5]==map[u][2]))){f=1;}else
if((map[u][9]!=0) && ((map[u][9]==map[u][6]) && (map[u][6]==map[u][3]))){f=1;}else
if((map[u][1]!=0) && ((map[u][1]==map[u][5]) && (map[u][5]==map[u][9]))){f=1;}else
if((map[u][7]!=0) && ((map[u][7]==map[u][5]) && (map[u][5]==map[u][3]))){f=1;}
if(f==1){map[u][0]='w';}
u++;
f=0;
}
}
}
a++;
c++;
}
txt.close();
system("PAUSE");
return EXIT_SUCCESS;
}
El ganador se lleva la memoria USB y los otros dos se llevan una taza con el logotipo de La_Morsa. Es importante decir que aún no me queda claro cuántas son las posibles posiciones legales. Muchos sitios web dan cifras pero en todos los casos no coinciden. Cuando tenga un rato verificaré esto.
Cabe decir que a las 5:30 pm de hoy se abrirá el siguiente reto, para que estén atentos.
Agradezco realmente el esfuerzo realizado. No pensé que iba a tener estas respuestas y tan rápido. Quien quiera los archivos zipeados de los ganadores, escríbame a [email protected] y se los mando de inmediato.