Brute Force Solution

This forum is for discussions related to solving the Modulo puzzle
User avatar
dpwmasters
Posts: 3
Joined: Wed Apr 06, 2011 5:12 am
Contact:

Post by dpwmasters »

Finally I can post something, what can be better than the solver I used in the modulo puzzle...

I use a script wrote in Java, let me share you all my source code, it needs to be optimized a little I suppose... But, by the moment, it was usefull for my porpuse.

Here's my source code... Sorry for the comments in Spanish, that's my native language....

Principal.java

Code: Select all

package dpwmasters;

import java.util.Date;

public class Principal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		// Se creará un objeto para manejar el tiempo de ejecución.
		Date date = new Date();

		// Se guardará el tiempo inicial de ejecución.
		long tiempoInicial = date.getTime();

		// Se guardarán los parámetros de la URL del tablero.
		String parametrosTablero = "00012,10202,11102,11002,02022";

		// Se guardarán los parámetros de la URL del tablero.
		String parametrosPiezas = "X..,XXX,.X. X.,X.,XX,X. XX...,XX..X,.XXXX,....X ...XX,...XX,...X.,XXXX.,...X. XX,.X XX.,.XX,XX.,X.. X..,XXX,XX. XXXX,X... .X,XX,X. ..XX,.XX.,XX..,X... X..,XXX,..X";

		// Se creará un nuevo tablero.
		Tablero tablero = new Tablero(parametrosTablero);

		// Se guardará la información de cada pieza en un arreglo.
		String[] piezas = parametrosPiezas.split(" ");

		// Se leerá la información de cada pieza.
		for (int i = 0; i < piezas.length; i++) {

			// Se guardará la información recodificada de la pieza.
			String informacionPieza = piezas[i].replace("X", "1").replace(".",
					"0");

			// Se agregará cada pieza disponible.
			tablero.AgregarPieza(informacionPieza);
		}

		// Se encontrará e imprimirá la solución del tablero.
		tablero.ObtenerSolucion();

		// Se guardará el tiempo inicial de ejecución.
		long tiempoFinal = date.getTime() - tiempoInicial;

		// Se imprimirá el tiempo total de ejecución en milisegundos.
		System.out.println("Tiempo Total Ejecución: " + tiempoFinal);

	}

}
Tablero.java

Code: Select all


package dpwmasters;

import java.util.ArrayList;
import java.util.Iterator;

public class Tablero {

	// Se confirgurará el estado inicial.
	private String[][] estadoInicialTablero;

	// Se creará una lista de piezas disponibles.
	private ArrayList<String[][]> piezasDisponibles = new ArrayList<String[][]>();

	// Se contará la cantidad de piezas del objeto.
	private int cantidadPiezas = 0;

	// Se contará la cantidad de permutaciones realizadas.
	private int permutacionesRealizadas = 0;

	// Se controlará el estado de la búsqueda de una solución.
	private boolean solucionEncontrada = false;

	// Constructor de la clase.
	public Tablero(String estadoInicialTableroCadena) {

		// Se guardará el estado inicial en un arreglo.
		String[] estadoInicialCadenaArreglo = estadoInicialTableroCadena
				.split(",");

		// Se guardará el ancho del tablero.
		int anchoTablero = estadoInicialCadenaArreglo[0].length();

		// Se guardará el alto del tablero.
		int altoTablero = estadoInicialCadenaArreglo.length;

		// Se creará el arreglo del estado inicial.
		this.estadoInicialTablero = new String[anchoTablero][altoTablero];

		// Se leerá cada posición del ancho del tablero.
		for (int i = 0; i < anchoTablero; i++) {

			// Se leerá cada posición del alto del tablero.
			for (int j = 0; j < altoTablero; j++) {

				// Se agregará el valor de la posición.
				this.estadoInicialTablero[i][j] = estadoInicialCadenaArreglo[j]
						.substring(i, i + 1);
			}
		}
	}

	// Esta función permitirá agregar piezas disponibles al tablero.
	public void AgregarPieza(String piezaCadena) {

		// Se contará la pieza.
		this.cantidadPiezas++;

		// Se guardará la pieza en un arreglo.
		String[] piezaCadenaArreglo = piezaCadena.split(",");

		// Se guardará el ancho de la pieza.
		int anchoPieza = piezaCadenaArreglo[0].length();

		// Se guardará el alto de la pieza.
		int altoPieza = piezaCadenaArreglo.length;

		// Se creará el arreglo de la pieza.
		String[][] nuevaPieza = new String[anchoPieza][altoPieza];

		// Se leerá cada posición del ancho de la pieza.
		for (int i = 0; i < anchoPieza; i++) {

			// Se leerá cada posición del alto de la pieza.
			for (int j = 0; j < altoPieza; j++) {

				// Se agregará el valor de la posición.
				nuevaPieza[i][j] = piezaCadenaArreglo[j].substring(i, i + 1);
			}
		}

		// Se agregará la nueva pieza al listado.
		this.piezasDisponibles.add(nuevaPieza);
	}

	// Esta función encontrará la solución del tablero.
	public void ObtenerSolucion() {

		// Se instanciará el arreglo encargado de obtener las posiciones
		// disponibles para cada pieza dentro del tablero.
		int[][] posicionesDisponibles = new int[this.cantidadPiezas][2];

		// Se guardará la posición de la pieza leída.
		int piezaLeída = 0;

		// Se iterará cada una de las piezas disponibles.
		for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
				.hasNext();) {

			// Se guardará la pieza leída.
			piezaLeída++;

			// Se extraera la pieza disponible.
			String[][] pieza = (String[][]) iterador.next();

			// Se guardarán las posiciones disponibles para el ancho.
			posicionesDisponibles[piezaLeída - 1][0] = this.estadoInicialTablero.length
					- pieza.length + 1;

			// Se guardarán las posiciones disponibles para el alto.
			posicionesDisponibles[piezaLeída - 1][1] = this.estadoInicialTablero[0].length
					- pieza[0].length + 1;
		}

		// Se creará un arreglo para guardar las posiciones disponibles sin
		// combinación por cada pieza.
		Object[] posicionesDisponiblesSinCombinación = new Object[this.cantidadPiezas];

		// Se guardará el total de valores posibles combinatorios.
		int totalValoresCombinatorios = 1;

		// Se leerán las piezas disponibles.
		for (int i = 0; i < this.cantidadPiezas; i++) {

			// Se creará un arreglo con las posiciones disponibles para cada
			// pieza leída.
			int[][] posicionesPiezaLeida = new int[posicionesDisponibles[i][0]
					* posicionesDisponibles[i][1]][2];

			// Se guardará el total de valores combinatorios.
			totalValoresCombinatorios *= posicionesDisponibles[i][0]
					* posicionesDisponibles[i][1];

			// Se leerán las posibles posiciones de x por cada pieza.
			for (int j = 0; j < posicionesDisponibles[i][0]; j++) {

				// Se leerán las posibles posiciones de y por cada pieza.
				for (int k = 0; k < posicionesDisponibles[i][1]; k++) {

					// Se guardará cada posición por pieza leída.
					posicionesPiezaLeida[j * posicionesDisponibles[i][1] + k][0] = j;
					posicionesPiezaLeida[j * posicionesDisponibles[i][1] + k][1] = k;
				}
			}

			// Se guardarán las posiciones disponibles para cada pieza.
			posicionesDisponiblesSinCombinación[i] = (Object) posicionesPiezaLeida;
		}

		// Se imprimirá el número máximo de iteraciones posibles.
		System.out.println("Iteraciones Máximas Posibles: "
				+ totalValoresCombinatorios);

		// Aquí se guardarán todas las posiciones disponibles en la
		// combinatoria de piezas.
		int[][] combinacionesDisponibles = new int[this.cantidadPiezas][2];

		// Se obtendrán las combinaciones disponibles entre las posiciones
		// disponibles para cada pieza.
		combinacionesDisponibles = this.ObtenerPermutacionesPosicionesPiezas(
				posicionesDisponiblesSinCombinación, combinacionesDisponibles,
				0);
	}

	// Esta función retornará todas las combinaciones disponibles entre cada una
	// de las posiciones disponibles para cada pieza.
	public int[][] ObtenerPermutacionesPosicionesPiezas(
			Object[] posicionesSinCombinacion,
			int[][] combinacionesDisponibles, int piezaInicial) {

		// Se evaluará si la pieza a examinar existe.
		if (piezaInicial < this.cantidadPiezas && !this.solucionEncontrada) {

			// Se leerá cada combinación posible para cada pieza.
			int[][] posicionesPieza = (int[][]) posicionesSinCombinacion[piezaInicial];

			// Se leerá cada una de las posiciones de cada pieza.
			// for (int i = 0; i < posicionesPieza.length; i++) {
			for (int i = posicionesPieza.length - 1; i >= 0; i--) {

				// Se actualizará el arreglo de combinaciones.
				combinacionesDisponibles[piezaInicial][0] = posicionesPieza[i][0];
				combinacionesDisponibles[piezaInicial][1] = posicionesPieza[i][1];

				// Se evaluará el la última pieza evaluada.
				if (piezaInicial == this.cantidadPiezas - 1) {

					// Se contará la permutación encontrada.
					permutacionesRealizadas++;

					// Se instanciará el nuevo tablero.
					String[][] estadoTableroReconstruido = new String[this.estadoInicialTablero.length][this.estadoInicialTablero[0].length];

					// Se leerá el ancho del tablero.
					for (int j = 0; j < estadoTableroReconstruido.length; j++) {

						// Se leerá el alto del tablero.
						for (int k = 0; k < estadoTableroReconstruido[0].length; k++) {

							// Se guardarán los valores en el tablero de
							// trabajo.
							estadoTableroReconstruido[j][k] = this.estadoInicialTablero[j][k];
						}
					}

					// Se instanciará el objeto encargado de evaluar la solución
					// propuesta.
					SolucionTablero solucionTablero = new SolucionTablero(
							this.piezasDisponibles, combinacionesDisponibles);

					// Se evaluará que hayan transcurrido 10 millones.
					if (permutacionesRealizadas % 10000000 == 0) {

						// Se imprimirá cada 10 millones de iteraciones.
						System.out.println("Permutaciones Actuales: "
								+ permutacionesRealizadas);
					}

					// Se evaluará la solución leída.
					if (solucionTablero.ObtenerSolucion(
							permutacionesRealizadas, estadoTableroReconstruido)) {

						// Se imprimirá la solución encontrada.
						solucionTablero.ImprimirSolucion(
								permutacionesRealizadas,
								estadoTableroReconstruido);

						// Se marcará la solución como encontrada.
						this.solucionEncontrada = true;
					}
				}

				// Se buscarán las opciones de la siguiente pieza.
				combinacionesDisponibles = this
						.ObtenerPermutacionesPosicionesPiezas(
								posicionesSinCombinacion,
								combinacionesDisponibles, piezaInicial + 1);
			}
		}

		// Se retornarán las combinaciones disponibles.
		return combinacionesDisponibles;
	}
}
SolucionTablero

Code: Select all


package dpwmasters;

import java.util.ArrayList;
import java.util.Iterator;

public class SolucionTablero {

	// Se creará una lista de piezas disponibles.
	private ArrayList<String[][]> piezasDisponibles = null;

	// Se obtendrán las posiciones y combinaciones disponibles para cada
	// pieza dentro del tablero.
	private int[][] posicionesPiezasDisponibles = null;

	// Constructor de la clase.
	public SolucionTablero(ArrayList<String[][]> piezasDisponibles,
			int[][] posicionesPiezasDisponibles) {
		super();

		// Se guardarán las piezas disponibles.
		this.piezasDisponibles = piezasDisponibles;

		// Se guardarán las piezas disponibles.
		this.posicionesPiezasDisponibles = posicionesPiezasDisponibles;
	}

	// Esta función encontrará la solución del tablero.
	public boolean ObtenerSolucion(int numeroSolucion, String[][] tableroTrabajo) {

		// Se guardará aquí si la solución fue exitosa.
		boolean solucionExitosa = false;

		// Se reiniciará la posición de la pieza leída.
		int piezaLeída = 0;

		// Se iterará cada una de las piezas disponibles.
		for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
				.hasNext();) {

			// Se guardará la pieza leída.
			piezaLeída++;

			// Se extraera la pieza disponible.
			String[][] pieza = (String[][]) iterador.next();

			// Se actualizará el estado del trabajo.
			tableroTrabajo = this.ActualizarEstadoTablero(tableroTrabajo,
					pieza, posicionesPiezasDisponibles[piezaLeída - 1][0],
					posicionesPiezasDisponibles[piezaLeída - 1][1]);

		}

		// Se evaluará la solución encontrada.
		solucionExitosa = this.esSolucionTablero(tableroTrabajo);

		// Se retornará el estado de la solución.
		return solucionExitosa;
	}

	// Esta función imprimirá la solución del tablero.
	public void ImprimirSolucion(int numeroSolucion, String[][] tableroTrabajo) {

		// Aquí se guardará el texto informativo de la solución.
		String informacionSolucion = "Número Solución: " + numeroSolucion
				+ "\n";

		// Se reiniciará la posición de la pieza leída.
		int piezaLeída = 0;

		// Se guardará la información del tablero.
		// informacionSolucion += this.ImprimirObjeto(tableroTrabajo) + "\n";

		// Se iterará cada una de las piezas disponibles.
		for (Iterator<String[][]> iterador = piezasDisponibles.listIterator(); iterador
				.hasNext();) {

			// Se guardará la pieza leída.
			piezaLeída++;

			// Se extraera la pieza disponible.
			String[][] pieza = (String[][]) iterador.next();

			// Se guardará la información del tablero.
			// informacionSolucion += this.ImprimirObjeto(pieza) + "\n";

			// Se imprimirá la posición de la pieza.
			informacionSolucion += "Posiciones:"
					+ (posicionesPiezasDisponibles[piezaLeída - 1][0] + 1)
					+ "-"
					+ (posicionesPiezasDisponibles[piezaLeída - 1][1] + 1)
					+ "\n";

			// Se actualizará el estado del trabajo.
			tableroTrabajo = this.ActualizarEstadoTablero(tableroTrabajo,
					pieza, posicionesPiezasDisponibles[piezaLeída - 1][0],
					posicionesPiezasDisponibles[piezaLeída - 1][1]);

			// Se guardará la información del tablero.
			// informacionSolucion += this.ImprimirObjeto(tableroTrabajo) +
			// "\n\n";
		}

		// Se imprimirá la solución.
		System.out.println(informacionSolucion);
	}

	// Esta función actualizará el estado del tablero de acuerdo a la pieza y a
	// la posición recibida.
	public String[][] ActualizarEstadoTablero(String[][] tableroTrabajo,
			String[][] pieza, int posX, int posY) {

		// Se leerá cada posición del alto de la pieza.
		for (int j = 0; j < pieza[0].length; j++) {

			// Se leerá cada posición del ancho de la pieza.
			for (int i = 0; i < pieza.length; i++) {

				// Se evaluará si la pieza afecta al estado.
				if (pieza[i][j].equals("1")) {

					// Se evaluará si la posición esta ocupada.
					if (tableroTrabajo[i + posX][j + posY].equals("0")) {

						// Se actualizará el estado del tablero.
						tableroTrabajo[i + posX][j + posY] = "1";

						// Si no.
					} else {

						// Se evaluará si la posición esta ocupada.
						if (tableroTrabajo[i + posX][j + posY].equals("1")) {

							// Se actualizará el estado del tablero.
							tableroTrabajo[i + posX][j + posY] = "2";

							// Si no.
						} else {

							// Se evaluará si la posición esta ocupada.
							if (tableroTrabajo[i + posX][j + posY].equals("2")) {

								// Se actualizará el estado del tablero.
								tableroTrabajo[i + posX][j + posY] = "0";
							}
						}
					}
				}
			}
		}

		// Se retornará el estado del tablero actualizado.
		return tableroTrabajo;
	}

	// Esta función evaluará si el estado de tablero es la solución esperada.
	public boolean esSolucionTablero(String[][] estadoTablero) {

		// Se guardará el estado del tablero como solucionado.
		boolean solucionTablero = true;

		// Se leerá cada posición del alto del tablero.
		for (int j = 0; j < estadoTablero[0].length; j++) {

			// Se leerá cada posición del ancho del tablero.
			for (int i = 0; i < estadoTablero.length; i++) {

				// Se evaluará si existe algún valor lleno.
				if (!estadoTablero[i][j].equals("0")) {

					// Se marcará la solución como incorrecta.
					solucionTablero = false;

					// Se detendrá el análisis de la solución.
					break;
				}
			}
		}

		// Se retornará la solución.
		return solucionTablero;
	}

	// Esta función imprimirá el objeto recibido, existiendo 2 posibilidades,
	// tablero o pieza.
	public String ImprimirObjeto(String[][] objetoImprimir) {

		// Aquí se guardará el string que será impreso.
		String estadoTableroImpresion = "";

		// Se leerá cada posición del alto del tablero.
		for (int j = 0; j < objetoImprimir[0].length; j++) {

			// Se leerá cada posición del ancho del tablero.
			for (int i = 0; i < objetoImprimir.length; i++) {

				// Se imprimirá cada celda del tablero.
				estadoTableroImpresion += objetoImprimir[i][j];
			}

			// Se imprimirá un salto de línea.
			estadoTableroImpresion += "\n";
		}

		// Se retirnará el tablero actual.
		return estadoTableroImpresion;
	}

}
I hope this help you all, any comment or suggestion please let me know it.

Now I have to improve this source code or look for other way to have the high scores in this puzzle. "Tails" I'm gonna go for you!!! :)
Karian
Posts: 75
Joined: Wed Jan 09, 2008 10:21 am

Post by Karian »

since this is in java, what is the added value for this compared with the code of bok on the first page of this thread.
User avatar
dpwmasters
Posts: 3
Joined: Wed Apr 06, 2011 5:12 am
Contact:

Added Value!!!!

Post by dpwmasters »

Hi Karian!!!

I haven't reviewed the first source code wrote in Java, this is just my own version of the posibles implementations to solve the puzzle. Everybody could use this source, put the parameters from the game and get the solution. This is not the best implementation yet, but is one of them.
Karian
Posts: 75
Joined: Wed Jan 09, 2008 10:21 am

Post by Karian »

The thing is that, except for basic (brute force) solutions, no code should be posted here. The posted code is just to give people an idea how they can start.

I must say I haven't checked your code. With the comments in between, it certainly is less readable for me than the original post. The idea is just that people learn by doing the challenges, and we don't give them already a good solution to start with. You learn more if you find the solution yourself.

With that idea in mind, I don't see the reason why to post a second java program.
User avatar
dpwmasters
Posts: 3
Joined: Wed Apr 06, 2011 5:12 am
Contact:

mmm??

Post by dpwmasters »

All right,
The idea is just that people learn by doing the challenges, and we don't give them already a good solution to start with
This was enough convincing to me, I'll retire my source code.
0xDEAD BEEF
Posts: 9
Joined: Wed Aug 17, 2011 11:29 am

Post by 0xDEAD BEEF »

How far would I get with pure brute force?
Thnx,
Beef
Adzeye
Posts: 9
Joined: Sat Apr 04, 2009 1:52 am
Location: Canada

Post by Adzeye »

Not far, if you look at the high score table you'll see people slow down in the early 20ish.
Post Reply