Dalej >>

Słowa kluczowe opisowe (do wyszukiwania): zrównanie dwóch macierzy, nakładanie się, tablica, wyszukiwanie

Wyzwanie

Święty Mikołaj miał w przeszłości historię elfów kradnących prezenty ze swojego skarbca, więc w tym roku zaprojektował zamek, który jest bardzo trudny do złamania, i wydaje się, że trzymał elfy w tym roku. Niestety przegrał kombinację i nie może też wymyślić, jak ją otworzyć! Na szczęście zatrudnił cię do napisania programu do znalezienia kombinacji. Nie musi być najkrótszy, ale musi go znaleźć tak szybko, jak to możliwe!

Ma bardzo ścisły harmonogram i nie może sobie pozwolić na długie oczekiwanie. Twój wynik będzie równy całkowitemu czasowi działania programu pomnożonemu przez liczbę kroków, które program wykonuje dla danych wejściowych oceniania. Najniższy wynik wygrywa.

Dane techniczne

Blokada jest kwadratową matrycą 1s i 0s. Jest ustawiony na losowy układ 1 i 0 i musi być ustawiony na określony kod. Na szczęście Święty Mikołaj pamięta wymagany kod.

Jest kilka kroków, które może wykonać. Każdy krok można wykonać na dowolnej ciągłej podmacierzy (tzn. Należy wybrać macierz podrzędną, która jest całkowicie ograniczona przez lewy górny i prawy dolny róg) (może to być podmacierz nie kwadratowa):

1. Obróć w prawo o 90 stopni *
2. Obróć w lewo o 90 stopni *
3. Obróć o 180 stopni
4. Przełączaj każdy nelement wiersza w prawo lub w lewo (zawija się)
5. Cykluj każdą kolumnę w mgórę lub w dół (zawija)
6. Obróć poziomo
7. Odwróć w pionie
8. Włącz główną przekątną *
9. Włącz główną anty-przekątną *

* tylko jeśli podmacierz jest kwadratowa

Oczywiście może również wykonywać te kroki na całej matrycy. Ponieważ jedynek i zer można zamieniać tylko na macierzy, ale wartości kwadratu nie można bezpośrednio zmienić, liczba zer i jedynek jest taka sama dla konfiguracji początkowej i końcowej.

Specyfikacje formatowania + reguły

Otrzymasz dane wejściowe w postaci dwóch kwadratowych macierzy (pozycji początkowej i końcowej) w dowolnym rozsądnym formacie. Dane wyjściowe powinny być sekwencją tych kroków w dowolnym czytelnym formacie. Ponieważ nie jest to golf kodowy, uczyń go łatwym do zweryfikowania formatem, ale nie jest to ścisły wymóg. Jeśli chcesz, możesz wybrać długość boku macierzy na wejściu.

Twój program zostanie uruchomiony na moim komputerze (Linux Mint, dokładne szczegóły wersji dostępne na żądanie, jeśli ktoś się tym przejmuje: P), a ja ustalę czas na podstawie czasu między naciśnięciem klawisza „enter” w wierszu polecenia a momentem polecenie kończy się.

Przypadki testowe

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. Weź całą matrycę. Przełącz każdą kolumnę w górę 1.
2. Weź dwie środkowe kolumny jako podmacierz. Przełączaj każdą kolumnę w dół 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. Weź całą matrycę. Cykluj każdą kolumnę w dół 1.
2. Weź środkową kolumnę. Wyłącz go 2.
3. Weź 2 górne rzędy. Odwróć w pionie.
4. Weź 2 górne prawe elementy górnego rzędu. Zamień je (obróć w prawo / w lewo 1, odwróć w poziomie).
5. Weź 2 górne rzędy po lewej stronie elementów. Zamień je.

Mogą istnieć bardziej wydajne metody, ale to nie ma znaczenia. Jeśli jednak je znajdziesz, możesz je wskazać w komentarzach :)

Ocenianie przypadku testowego

Ten przypadek testowy zostanie wykorzystany do oceny Twojego zgłoszenia. Jeśli uważam, że odpowiedź zbytnio specjalizuje się w przypadku testowym, mam prawo powtórzyć losowe dane wejściowe i ponownie ocenić wszystkie odpowiedzi w nowym przypadku. Przypadek testowy można znaleźć tutaj, gdzie góra jest początkiem, a dół pożądaną konfiguracją.

Jeśli uważam, że odpowiedzi zbytnio się specjalizują, to MD5 następnego przypadku testowego jest 3c1007ebd4ea7f0a2a1f0254af204eed. (Jest to teraz napisane tutaj, aby uwolnić się od oskarżeń o oszukiwanie: P)

Obowiązują standardowe luki. Żadna odpowiedź nie zostanie zaakceptowana. Miłego kodowania!

^{Uwaga: Inspirację do tej serii wyzwań czerpałem z Advent Of Code . Nie mam powiązań z tą stroną}

Możesz zobaczyć listę wszystkich wyzwań w serii, patrząc na sekcję „Połączone” pierwszego wyzwania tutaj .

Jawa

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

Nieco szybsza wersja zakodowana na stałe: Wypróbuj online!

Dane wejściowe to liczby całkowite rozdzielone spacjami za pomocą wiersza polecenia. Pierwsza liczba całkowita to szerokość dwóch macierzy. Pozostałe liczby całkowite to ich elementy, rząd po rzędzie.

Każdą permutację macierzy można uzyskać tylko za pomocą operatorów odwracania w poziomie i odwracania w pionie, więc zignorowałem resztę, z wyjątkiem zamiany kolejnych vFlip i hFlip w tym samym obszarze na obrót o 180 stopni.

Program skanuje każdy element. Za każdym razem, gdy napotykamy element, który ma zły bit, patrzy dalej przez tablicę, aby znaleźć miejsce, które ma prawidłowy bit. Obszar wyszukiwania podzieliłem na dwa: te o takiej samej lub większej współrzędnej kolumny, i te o mniejszej współrzędnej kolumny. Zauważ, że ta ostatnia musi mieć większą współrzędną rzędu w zależności od sposobu, w jaki przemierzamy tablicę. Jeśli znajdziemy poprawny bit w pierwszym obszarze wyszukiwania, możemy po prostu obrócić podmacierz o 180 stopni obejmującą dwa elementy w sumie dla jednej operacji. Jeśli znajduje się w drugim obszarze, możemy użyć poziomego odwrócenia, aby przesunąć prawidłowy bit do tej samej kolumny co niewłaściwy bit, a następnie pionowo odwrócić podmacierz obejmującą dwa w sumie dla dwóch operacji.

Dane wyjściowe programu to tablica, którą należy mentalnie podzielić na pięcioosobowe grupy. Każda grupa to (i, rząd1, kolumna1, rząd2, kolumna2), gdzie i wynosi 0 dla braku operacji, 1 dla obrotu o 180 stopni, 2 dla obrotu poziomego i 3 dla obrotu pionowego. Pozostałe 4 komponenty opisują region, w którym działa operacja. Nie jestem pewien, czy jest to czytelny format.

W danym przypadku testowym otrzymuję 258 operacji i dwie do trzech milisekund na moim komputerze.