Advent Challenge 1: Help Santa unlock his present vault!

Question

Next >>

Descriptive Keywords (for searching): Make Two Matrices Equivalent, Overlap, Array, Find

Challenge

Santa has had a history of elves stealing presents from his vault in the past, so this year he designed a lock that is very hard to crack, and it seems to have kept the elves out this year. Unfortunately, he has lost the combination and he can't figure out how to open it either! Fortunately, he has hired you to write a program to find the combination. It doesn't need to be the shortest one, but he needs to find it as fast as possible!

He has a very strict schedule and he can't afford to wait for very long. Your score will be the total run-time of your program multiplied by the number of steps your program outputs for the scoring input. Lowest score wins.

Specifications

The lock is a square matrix of 1s and 0s. It is set to a random arrangement of 1s and 0s and needs to be set to a specified code. Fortunately, Santa remembers the required code.

There are a few steps he can perform. Each step can be performed on any contiguous sub-matrix (that is, you must select a sub-matrix that is entirely bounded by a top-left and bottom-right corner) (it can be a non-square sub-matrix):

1. Rotate right 90 degrees*
2. Rotate left 90 degrees*
3. Rotate 180 degrees
4. Cycle each row n elements right or left (wraps)
5. Cycle each column m elements up or down (wraps)
6. Flip Horizontally
7. Flip Vertically
8. Flip on the Main Diagonal*
9. Flip on the Main Anti-diagonal*

*only if the sub-matrix is square

Of course, he can also perform these steps on the entire matrix. Since 1s and 0s can only be swapped on the matrix but the value of a square cannot be directly changed, the number of 1s and 0s is the same for the start and end configuration.

Formatting Specifications + Rules

You will be given the input as two square matrices (starting position and ending position) in any reasonable format you want. The output should be a sequence of these steps in any readable format. Since this isn't code-golf, please make it an easily verifiable format, but that's not a strict requirement. You can choose to take the side-length of the matrices in the input if you want.

Your program will be run on my computer (Linux Mint, exact version details available upon request if anyone cares :P) and I will time it based on the amount of time between the time I press "enter" on the command line and when the command exits.

Test Cases

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. Take the entire matrix. Cycle each column up 1.
2. Take the middle two columns as a sub-matrix. Cycle each column down 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. Take the entire matrix. Cycle each column down 1.
2. Take the middle column. Cycle it down 2.
3. Take the top 2 rows. Flip it vertically.
4. Take the top row's rightmost 2 elements. Swap them (rotate right/left 1, flip horizontally).
5. Take the top row's leftmost 2 elements. Swap them.

There might be more efficient methods, but that doesn't matter. Feel free to point them out in the comments if you find one though :)

Judging Test Case

This test case will be used to judge your submission. If I believe that an answer is specializing for the test case too much, I have the right to repick a random input and rejudge all answers with the new case. The test case can be found here where the top is the start and the bottom is the desired configuration.

If I believe answers are specializing too much, the MD5 of the next test case is 3c1007ebd4ea7f0a2a1f0254af204eed. (This is written here right now to liberate myself from accusations of cheating :P)

Standard Loopholes Apply. No answer will be accepted. Happy coding!

^{Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site}

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.

Answer 1

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

Slightly faster hard-coded version: Try it online!

Input is space separated integers via the command line. The first integer is the width of the two matrices. The remaining integers are their elements, row-by-row.

Every permutation of a matrix can be obtained with just the horizontal flip and vertical flip operators, so I ignored the rest except for replacing a consecutive vFlip and hFlip in the same region with a rotation by 180 degrees.

The program scans through each element. Whenever we encounter an element that has the wrong bit, it looks further ahead through the array to find a spot that has the correct bit. I've divided the search region in two: those with an equal or larger column coordinate, and those with a smaller column coordinate. Note that the latter must have a larger row coordinate based on the way we're traversing the array. If we find a correct bit in the first search region, we can just rotate by 180 degrees the sub-matrix spanning the two elements for a total of one operation. If it's in the second region, we can use a horizontal flip to move the correct bit to the same column as the wrong bit and then vertically flip the sub-matrix spanning the two for a total of two operations.

The output of the program is an array that should be mentally split into groups of five. Each group is (i, row1, col1, row2, col2) where i is 0 for a no-op, 1 for a rotation by 180 degrees, 2 for a horizontal flip, and 3 for a vertical flip. The remaining 4 components describe the region over which the operation runs. I am not sure if this is a readable format.

For the given test case, I get 258 operations and two to three milliseconds on my computer.