- Cierra temporalmente el acuario más grande del mundo por una grieta en su estructura
- Tuenti se lava la cara
- Algunas cosas de la vida y de la empresa que aprendí mientras jugaba al ajedrez (II)
- Los gorrones del Camel
- Google: hechos y cifras
- The Demotivational Posters BlogGlobal Warming
- Pàgines de Facebook per a la difusió
- Datos exactos sobre el crecimiento de Facebook en los últimos tiempos
- The Billion Dollar Kernel
- Recognizr: la realidad aumentada aplicada al reconocimiento facial
- Historia de los frameworks web
- Camino de los 50 millones de «tweets» por día en Twitter
- Las ganancias de Microsoft en una gráfica
- Así de simple es abrir puertas con cerradura de tarjeta magnética, demostración
- Kanban vs. Scrum en castellano
- Microsoft publica las especificaciones de los archivos .pst de Outlook
- geoEuskadi libera información geográfica
- La red de 'blogs' WordPress 'cae' durante dos horas
- Dos escuelas chinas estarían relacionadas con ciberataque a Google
- Microsoft comenzará a ofrecer la “ballot screen” en Europa la próxima semana
- Granny Win
viernes, 26 de febrero de 2010
Selección de noticias de la semana - 26/2/2010
Aquí está la selección de cosillas interesantes que he encontrado por ahí esta semana:
Desafío AbreDatos 2010
Hace unos días publicaba un post sobre pro bono publico, una asociación para promoción de plataformas abiertas entre las instituciones públicas.
Parece que la asociación está empezando a dar sus primeros frutos, han publicado un concurso llamado Desafío AbreDatos 2010, para el desarrollo de servicios tecnológicos al ciudadano basados en el uso de datos públicos.
Se trata de un concurso para el desarrollo exprés en 48 horas, que tendrá lugar el fin de semana del 17 y 18 de abril.
miércoles, 24 de febrero de 2010
El adictivo juego sokoban, y un buscador de soluciones en Java
Hace poco buscaba algún problema para ponerle a mis alumnos de paradigmas de programación (en programación funcional en LISP) que requiriese del uso de la recursividad, y me acordé del juego Sokoban.
Las reglas son muy simples, pero es verdaderamente adictivo. El juego consiste en colocar una serie de cajas en sus casillas de destino, empujándolas con tu personaje. Sólo podemos empujar una caja poniéndonos detrás de ella, por lo que si una caja queda empotrada en una esquina es imposible moverla.
Se puede jugar en multitud de sitios online, entre otros aquí.
El juego engancha, cuando empiezas no puedes dejar de jugar. El caso es que hace muchos años (allá por el 2001, cuando trabajaba en Newknow) me quedé atrapado en un nivel que no era capaz de solucionar, así que decidí implementar un programa en Java que calculase la solución por mí (no me llevó más de un par de horas, aunque es bastante ineficiente y para profundidades mayores de 50 tarda bastante).
La solución tiene unas 200 líneas, y hace uso intensivo de la recursividad y la técnica backtracking.
He conseguido recuperar aquella clase Java que escribí en su día, el puzle a solucionar está a fuego en el código y es el siguiente, aunque podéis cambiarlo por cualquiera que se os ocurra.
La solución que da es la siguiente (leer de abajo a arriba):
Abajo: [3 , 4]
Abajo: [3 , 3]
Abajo: [3 , 2]
Abajo: [3 , 1]
Derecha: [2 , 1]
Arriba: [2 , 2]
Arriba: [2 , 3]
Arriba: [2 , 4]
Arriba: [2 , 5]
Abajo: [2 , 4]
Abajo: [2 , 3]
Izquierda: [3 , 3]
Arriba: [3 , 4]
Arriba: [3 , 5]
Arriba: [3 , 6]
Derecha: [2 , 6]
Abajo: [2 , 5]
Izquierda: [3 , 5]
Abajo: [3 , 4]
Izquierda: [4 , 4]
Arriba: [4 , 5]
Arriba: [4 , 6]
Derecha: [3 , 6]
Derecha: [2 , 6]
Izquierda: [3 , 6]
Izquierda: [4 , 6]
Abajo: [4 , 5]
Abajo: [4 , 4]
Derecha: [3 , 4]
Abajo: [3 , 3]
Derecha: [2 , 3]
Abajo: [2 , 2]
Derecha: [1 , 2]
Y aquí está el código del buscador de soluciones:
/*
* Cajas.java
*
* Created on 30 de abril de 2001, 13:02
*/
public class Cajas extends Object {
public char[][] lab = {
{'#','#','#','#','#','#'},
{'#','#',' ',' ','#','#'},
{'#',' ','H',' ','#','#'},
{'#','#','H',' ','#','#'},
{'#','#',' ','H',' ','#'},
{'#','o','H',' ',' ','#'},
{'#','o','o','X','o','#'},
{'#','#','#','#','#','#'}};
public int initX = 1;
public int initY = 2;
public static int DIRECTION_UP = 1;
public static int DIRECTION_RIGHT = 2;
public static int DIRECTION_DOWN = 3;
public static int DIRECTION_LEFT = 4;
public int MAX_DEPTH = 100;
public static final char WALL = '#';
public static final char TARGET = 'o';
public static final char FREE = ' ';
public static final char BOXOVERFREE = 'H';
public static final char BOXOVERTARGET = 'X';
public static final char STEPOVERFREE = '.';
public static final char STEPOVERTARGET = ',';
public static void main(String args[]) {
new Cajas().go();
}
/** Creates new Cajas */
public Cajas() {
}
public void go() {
System.out.println("Iniciando ejecución...");
for(int i=1; i<MAX_DEPTH; i++) {
State state = new State(initX, initY, lab);
if(!state.step(1, i)) {
System.out.println("No hay soluciones con " + i + " movimientos");
}
else {
System.out.println("Encontrada solución con " + i + " movimientos");
break;
}
}
}
private class State {
public int x;
public int y;
public char[][] matrix;
public State(int x, int y, char[][] matrix) {
this.x = x;
this.y = y;
this.matrix = matrix;
}
public boolean step(int depth, int maxDepth) {
// print();
try {
// System.in.read();
} catch(Exception e) {
}
if(depth > maxDepth) {
return false;
}
if(isDone()) {
System.out.println("Hecho: [" + x + " , " + y + "]");
return true;
}
State newState = alterState(DIRECTION_UP);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Arriba: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_RIGHT);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Derecha: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_DOWN);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Abajo: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_LEFT);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Izquierda: [" + x + " , " + y + "]");
return true;
}
return false;
}
public State alterState(int direction) {
int toGoX=0,nextToGoX=0,toGoY=0,nextToGoY=0;
if(direction == DIRECTION_UP) {
toGoX = x;
nextToGoX = x;
toGoY = y-1;
nextToGoY = y-2;
}
else if(direction == DIRECTION_RIGHT) {
toGoX = x+1;
nextToGoX = x+2;
toGoY = y;
nextToGoY = y;
}
else if(direction == DIRECTION_DOWN) {
toGoX = x;
nextToGoX = x;
toGoY = y+1;
nextToGoY = y+2;
}
else if(direction == DIRECTION_LEFT) {
toGoX = x-1;
nextToGoX = x-2;
toGoY = y;
nextToGoY = y;
}
State newState = null;
char mToGo = matrix[toGoY][toGoX];
// Moverse a sitio libre
if(mToGo == FREE || mToGo == TARGET) {
newState = getCopy();
if(newState.matrix[y][x] == FREE)
newState.matrix[y][x] = STEPOVERFREE;
else if(newState.matrix[y][x] == TARGET)
newState.matrix[y][x] = STEPOVERTARGET;
newState.x = toGoX;
newState.y = toGoY;
return newState;
}
if( nextToGoY < 0 || nextToGoY >= matrix.length
|| nextToGoX < 0 || nextToGoX >= matrix[0].length)
return null;
char mNextToGo = matrix[nextToGoY][nextToGoX];
// Empujar caja que estaba sobre blanco, sobre blanco
if(mToGo == BOXOVERFREE && (mNextToGo == FREE || mNextToGo == STEPOVERFREE)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = FREE;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERFREE;
}
// Empujar caja que estaba sobre blanco, sobre objetivo
else if(mToGo == BOXOVERFREE && (mNextToGo == TARGET || mNextToGo == STEPOVERTARGET)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = FREE;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERTARGET;
}
// Empujar caja que estaba sobre objetivo, sobre blanco
else if(mToGo == BOXOVERTARGET && (mNextToGo == FREE || mNextToGo == STEPOVERFREE)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = TARGET;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERFREE;
}
// Empujar caja que estaba sobre objetivo, sobre objetivo
else if(mToGo == BOXOVERTARGET && (mNextToGo == TARGET || mNextToGo == STEPOVERTARGET)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = TARGET;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERTARGET;
}
return newState;
}
public State getCopy() {
int height = matrix.length;
int width = matrix[0].length;
char[][] newMatrix = new char[height][];
for(int i = 0; i < height; i++) {
newMatrix[i] = new char[width];
for(int j = 0; j < width; j++)
newMatrix[i][j] = matrix[i][j];
}
return new State(x,y,newMatrix);
}
public State getCopyClearStepped() {
int height = matrix.length;
int width = matrix[0].length;
char[][] newMatrix = new char[height][];
for(int i = 0; i < height; i++) {
newMatrix[i] = new char[width];
for(int j = 0; j < width; j++) {
char c = matrix[i][j];
if (c == STEPOVERFREE)
newMatrix[i][j] = FREE;
else if (c == STEPOVERTARGET)
newMatrix[i][j] = TARGET;
else
newMatrix[i][j] = c;
}
}
return new State(x,y,newMatrix);
}
public boolean isDone() {
int height = matrix.length;
int width = matrix[0].length;
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
if(matrix[i][j] == BOXOVERFREE)
return false;
return true;
}
public void print() {
int height = matrix.length;
int width = matrix[0].length;
for(int i = 0; i < height; i++) {
for(int j = 0; j < width; j++) {
if(i == y && j == x)
System.out.print("$");
else
System.out.print(matrix[i][j]);
}
System.out.println("");
}
}
}
}
Suscribirse a:
Entradas (Atom)
Entradas
