hacker.org

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);

	}

}

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;
	}
}

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;
	}

}