Siguiente >>

Palabras clave descriptivas (para búsqueda): hacer equivalentes dos matrices, superponer, ordenar, buscar

Desafío

Santa ha tenido una historia de elfos robando regalos de su bóveda en el pasado, por lo que este año diseñó una cerradura que es muy difícil de romper, y parece haber mantenido a los elfos fuera de este año. ¡Desafortunadamente, ha perdido la combinación y tampoco sabe cómo abrirla! Afortunadamente, te ha contratado para escribir un programa para encontrar la combinación. No tiene que ser el más corto, ¡pero necesita encontrarlo lo más rápido posible!

Tiene un horario muy estricto y no puede permitirse esperar mucho tiempo. Su puntaje será el tiempo de ejecución total de su programa multiplicado por el número de pasos que su programa produce para la entrada de puntaje. La puntuación más baja gana.

Especificaciones

El bloqueo es una matriz cuadrada de 1s y 0s. Se establece en una disposición aleatoria de 1s y 0s y debe establecerse en un código específico. Afortunadamente, Santa recuerda el código requerido.

Hay algunos pasos que puede realizar. Cada paso se puede realizar en cualquier submatriz contigua (es decir, debe seleccionar una submatriz que esté completamente limitada por una esquina superior izquierda e inferior derecha) (puede ser una submatriz no cuadrada):

1. Girar 90 grados a la derecha *
2. Girar a la izquierda 90 grados *
3. Girar 180 grados
4. Realice un ciclo de cada nelemento de fila hacia la derecha o hacia la izquierda (envolturas)
5. Ciclo cada melemento de la columna hacia arriba o hacia abajo (wraps)
6. Voltear horizontalmente
7. Voltear verticalmente
8. Voltee la Diagonal Principal *
9. Voltee el antia diagonal principal *

* solo si la submatriz es cuadrada

Por supuesto, también puede realizar estos pasos en toda la matriz. Dado que 1s y 0s solo se pueden intercambiar en la matriz, pero el valor de un cuadrado no se puede cambiar directamente, el número de 1s y 0s es el mismo para la configuración inicial y final.

Especificaciones de formato + Reglas

Se le dará la entrada como dos matrices cuadradas (posición inicial y posición final) en cualquier formato razonable que desee. La salida debe ser una secuencia de estos pasos en cualquier formato legible. Como no se trata de código de golf, conviértalo en un formato fácilmente verificable, pero ese no es un requisito estricto. Puede elegir tomar la longitud lateral de las matrices en la entrada si lo desea.

Su programa se ejecutará en mi computadora (Linux Mint, detalles exactos de la versión disponibles a pedido si alguien le importa: P) y lo cronometraré en función del tiempo transcurrido entre el momento en que presiono "enter" en la línea de comandos y cuando el comando sale.

Casos de prueba

1 0 0 1    0 0 0 0
0 1 1 0 -> 0 0 0 0
0 1 1 0 -> 1 1 1 1
1 0 0 1    1 1 1 1

1. Toma toda la matriz. Ciclo cada columna hacia arriba 1.
2. Tome las dos columnas del medio como una submatriz. Ciclo cada columna hacia abajo 2.

1 0 1 0 1    0 1 0 1 0
0 1 0 1 0    1 0 1 0 1
1 0 1 0 1 -> 0 1 1 1 0
0 1 0 1 0    1 0 1 0 1
1 0 1 0 1    0 1 0 1 0

1. Toma toda la matriz. Ciclo cada columna hacia abajo 1.
2. Toma la columna del medio. Ciclo hacia abajo 2.
3. Toma las 2 primeras filas. Voltéalo verticalmente.
4. Tome los 2 elementos más a la derecha de la fila superior. Intercambiarlos (girar a la derecha / izquierda 1, voltear horizontalmente).
5. Tome los 2 elementos más a la izquierda de la fila superior. Intercambiarlos.

Puede haber métodos más eficientes, pero eso no importa. Siéntase libre de señalarlos en los comentarios si encuentra uno :)

Juzgar caso de prueba

Este caso de prueba se utilizará para juzgar su presentación. Si creo que una respuesta se está especializando demasiado para el caso de prueba, tengo derecho a repetir una entrada aleatoria y volver a juzgar todas las respuestas con el nuevo caso. El caso de prueba se puede encontrar aquí, donde la parte superior es el inicio y la parte inferior es la configuración deseada.

Si creo que las respuestas se están especializando demasiado, el MD5 del próximo caso de prueba es 3c1007ebd4ea7f0a2a1f0254af204eed. (Esto está escrito aquí ahora mismo para liberarme de las acusaciones de hacer trampa: P)

Se aplican lagunas estándar. No se aceptarán respuestas. ¡Feliz codificación!

^{Nota: Me inspiré para esta serie de desafíos de Advent Of Code . No estoy afiliado a este sitio}

Puede ver una lista de todos los desafíos de la serie mirando la sección 'Vinculados' del primer desafío aquí .

Java

import java.util.Arrays;

public class SantaMatrix4 {
	
	public static void flipV(int[][] matrix, int row1, int col1, int row2, int col2) {
		for (int row = row1; row <= (row2 - row1) / 2 + row1; row++) {
			for (int col = col1; col <= col2; col++) {
				int tmp = matrix[row][col];
				matrix[row][col] = matrix[row2 - row + row1][col];
				matrix[row2 - row + row1][col] = tmp;
			}
		}
	}
	
	public static void flipH(int[][] matrix, int row1, int col1, int row2, int col2) {
		for (int row = row1; row <= row2; row++) {
			for (int col = col1; col <= (col2 - col1) / 2 + col1; col++) {
				int tmp = matrix[row][col];
				matrix[row][col] = matrix[row][col2 - col + col1];
				matrix[row][col2 - col + col1] = tmp;
			}
		}
	}

	public static void main(String[] args) {
		int counter = 0;
		int n = Integer.parseInt(args[counter++]);
		int[][] matrix1 = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				matrix1[i][j] = Integer.parseInt(args[counter++]);
			}
		}
				
		int[][] matrix2 = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				matrix2[i][j] = Integer.parseInt(args[counter++]);
			}
		}
			
		int[] ops = new int[5 * matrix1.length * matrix1.length * 2];
		int numOps = 0;
		int opsI = 0;
		
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n; col++) {
				int goal = matrix2[row][col];
				boolean gotIt = false;
				
				//Look for required number to the right
				for (int i = row; i < n && !gotIt; i++) {
					for (int j = col; j < n && !gotIt; j++) {
						if (i == row && j == col) continue;
						if (matrix1[i][j] == goal) {
							flipH(matrix1, row, col, i, j);
							flipV(matrix1, row, col, i, j);
							ops[opsI++] = 1;
							ops[opsI++] = row;
							ops[opsI++] = col;
							ops[opsI++] = i;
							ops[opsI++] = j;
							numOps++;
							
							gotIt = true;
						}
					}
				}

				//Look for required number below and to the left
				for (int i = row + 1; i < n && !gotIt; i++) {
					for (int j = 0; j < col && !gotIt; j++) {
						if (matrix1[i][j] == goal) {
							flipH(matrix1, i, j, i, col);
							ops[opsI++] = 2;
							ops[opsI++] = i;
							ops[opsI++] = j;
							ops[opsI++] = i;
							ops[opsI++] = col;
							
							flipV(matrix1, row, col, i, col);
							ops[opsI++] = 3;
							ops[opsI++] = row;
							ops[opsI++] = col;
							ops[opsI++] = i;
							ops[opsI++] = col;
							
							numOps += 2;
							gotIt = true;
						}
					}
				}
				
			}
		}

		System.out.println(Arrays.toString(ops));
		System.out.println(numOps);
	}
}

Versión codificada ligeramente más rápida: ¡ Pruébelo en línea!

La entrada es enteros separados por espacios a través de la línea de comando. El primer entero es el ancho de las dos matrices. Los enteros restantes son sus elementos, fila por fila.

Cada permutación de una matriz se puede obtener solo con los operadores de volteo horizontal y volteo vertical, por lo que ignoré el resto excepto por reemplazar un vFlip y hFlip consecutivos en la misma región con una rotación de 180 grados.

El programa explora cada elemento. Cada vez que encontramos un elemento que tiene el bit incorrecto, mira más adelante a través de la matriz para encontrar un lugar que tenga el bit correcto. He dividido la región de búsqueda en dos: aquellos con una coordenada de columna igual o mayor, y aquellos con una coordenada de columna más pequeña. Tenga en cuenta que este último debe tener una coordenada de fila más grande en función de la forma en que estamos atravesando la matriz. Si encontramos un bit correcto en la primera región de búsqueda, podemos rotar 180 grados la submatriz que abarca los dos elementos para un total de una operación. Si está en la segunda región, podemos usar un giro horizontal para mover el bit correcto a la misma columna que el bit incorrecto y luego voltear verticalmente la submatriz que abarca los dos para un total de dos operaciones.

La salida del programa es una matriz que debe dividirse mentalmente en grupos de cinco. Cada grupo es (i, fila1, col1, fila2, col2) donde i es 0 para un no-op, 1 para una rotación de 180 grados, 2 para un giro horizontal y 3 para un giro vertical. Los 4 componentes restantes describen la región sobre la que se ejecuta la operación. No estoy seguro de si este es un formato legible.

Para el caso de prueba dado, obtengo 258 operaciones y dos o tres milisegundos en mi computadora.