Далее >>

Описательные ключевые слова (для поиска): сделать две матрицы эквивалентными, перекрытие, массив, поиск

Вызов

В прошлом у Санты была история, когда эльфы крали подарки из своего хранилища, поэтому в этом году он разработал замок, который очень трудно взломать, и, похоже, в этом году он не пускал эльфов. К сожалению, он потерял комбинацию и не может понять, как ее открыть! К счастью, он нанял вас написать программу, чтобы найти комбинацию. Он не должен быть самым коротким, но ему нужно найти его как можно быстрее!

У него очень строгий график, и он не может позволить себе ждать очень долго. Ваша оценка будет представлять собой общее время выполнения вашей программы, умноженное на количество шагов, которые ваша программа выдает для ввода оценки. Самый низкий балл побеждает.

Характеристики

Замок представляет собой квадратную матрицу 1 с и 0 с. Для него задано случайное расположение 1 и 0, и его необходимо установить для указанного кода. К счастью, Санта помнит нужный код.

Есть несколько шагов, которые он может выполнить. Каждый шаг может быть выполнен для любой смежной подматрицы (то есть вы должны выбрать подматрицу, которая полностью ограничена верхним левым и нижним правым углом) (это может быть неквадратная подматрица):

1. Поворот вправо на 90 градусов *
2. Повернуть влево на 90 градусов *
3. Повернуть на 180 градусов
4. Цикл каждого nэлемента строки вправо или влево (переносится)
5. Цикл каждого mэлемента столбца вверх или вниз (переносы)
6. Отразить по горизонтали
7. Отразить по вертикали
8. Отразить на главной диагонали *
9. Отразить на основной анти-диагональ *

* только если подматрица квадратная

Конечно, он также может выполнить эти шаги на всей матрице. Поскольку 1 и 0 можно поменять местами только на матрице, но значение квадрата нельзя изменить напрямую, число 1 и 0 одинаково для начальной и конечной конфигурации.

Спецификации форматирования + правила

Вам будет предоставлен ввод в виде двух квадратных матриц (начальная позиция и конечная позиция) в любом разумном формате, который вы хотите. Выходные данные должны быть последовательностью этих шагов в любом читаемом формате. Поскольку это не код-гольф, пожалуйста, сделайте его легко проверяемым форматом, но это не является строгим требованием. Вы можете выбрать длину стороны матриц во входных данных, если хотите.

Ваша программа будет запущена на моем компьютере (Linux Mint, точные сведения о версии доступны по запросу, если кому-то все равно: P), и я рассчитываю время, основываясь на промежутке времени между нажатием клавиши «ввод» в командной строке и моментом, когда команда выходит.

Тестовые случаи

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. Взять всю матрицу. Цикл каждого столбца вверх 1.
2. Возьмите две средние колонки в качестве подматрицы. Цикл каждого столбца вниз 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. Взять всю матрицу. Цикл каждого столбца вниз 1.
2. Возьмите среднюю колонну. Переведите его вниз 2.
3. Возьмите 2 верхних ряда. Переверните его вертикально.
4. Возьмите 2 верхних ряда справа. Поменяйте их местами (поверните вправо / влево на 1, переверните горизонтально).
5. Возьмите 2 верхних ряда слева. Поменяйте их местами.

Могут быть более эффективные методы, но это не имеет значения. Не стесняйтесь указывать их в комментариях, если вы найдете хотя бы один :)

Судебный контрольный пример

Этот контрольный пример будет использоваться для оценки вашего представления. Если я считаю, что ответ слишком специализирован для тестового случая, я имею право повторить случайный ввод и повторно оценить все ответы в новом случае. Тестовый пример можно найти здесь, где верх - это начало, а низ - желаемая конфигурация.

Если я считаю, что ответы слишком специализируются, MD5 следующего контрольного примера будет 3c1007ebd4ea7f0a2a1f0254af204eed. (Это написано здесь и сейчас, чтобы освободиться от обвинений в мошенничестве: P)

Применяются стандартные лазейки. Ответ не будет принят. Удачного кодирования!

^{Примечание: я черпал вдохновение для этой серии испытаний из Advent Of Code . У меня нет связи с этим сайтом}

Вы можете увидеть список всех испытаний в серии, посмотрев раздел «Связанные» первой задачи здесь .

Джава

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

Немного быстрее жестко запрограммированная версия: попробуйте онлайн!

Ввод - это целые числа через пробел через командную строку. Первое целое число - ширина двух матриц. Остальные целые числа являются их элементами, строка за строкой.

Каждая перестановка матрицы может быть получена только с помощью операторов горизонтального и вертикального переворота, поэтому я проигнорировал остальные, за исключением замены последовательных vFlip и hFlip в той же области с поворотом на 180 градусов.

Программа просматривает каждый элемент. Всякий раз, когда мы сталкиваемся с элементом, у которого есть неправильный бит, он смотрит дальше в массиве, чтобы найти место с правильным битом. Я разделил область поиска на две части: с одинаковой или большей координатой столбца и с меньшей координатой столбца. Обратите внимание, что последний должен иметь большую координату строки в зависимости от того, как мы пересекаем массив. Если мы находим правильный бит в первой области поиска, мы можем просто повернуть субматрицу на 180 градусов, охватывающую два элемента, всего за одну операцию. Если он находится во второй области, мы можем использовать горизонтальный переворот, чтобы переместить правильный бит в тот же столбец, что и неправильный бит, а затем вертикально перевернуть подматрицу, охватывающую эти две, всего две операции.

Результатом программы является массив, который должен быть мысленно разбит на группы по пять человек. Каждая группа (i, row1, col1, row2, col2), где i равно 0 для бездействия, 1 для поворота на 180 градусов, 2 для горизонтального переворачивания и 3 для вертикального переворота. Остальные 4 компонента описывают регион, в котором выполняется операция. Я не уверен, что это читаемый формат.

Для данного теста я получаю 258 операций и две-три миллисекунды на моем компьютере.