Advent Challenge 1:サンタさんの現在の金庫のロック解除を手伝ってください!


Next >>

記述キーワード(検索用):2つの行列を等価、重複、配列、検索

チャレンジ

サンタは、過去に彼の金庫から贈り物を盗んだエルフの歴史を持っていたので、今年はひどく壊れにくいロックをデザインしました。今年はエルフを守ったようです。残念ながら、彼はコンビネーションを失いました。そして、彼はそれを開く方法を理解できません!幸いなことに、彼はあなたに、その組み合わせを見つけるためのプログラムを書くためにあなたを雇いました。それは最短のものである必要はありませんが、彼はできるだけ早くそれを見つける必要があります!

彼は非常に厳しいスケジュールを持っており、非常に長い時間待つ余裕はない。あなたのスコアは、あなたのプログラムの合計実行時間に、あなたのプログラムが得点入力のために出力するステップの数を掛けたものになります。最低得点が勝ちます。

仕様

ロックは、1と0の正方行列です。
1と0のランダムな配置に設定されており、指定されたコードに設定する必要があります。幸いにも、サンタは必要なコードを覚えています。

彼が実行できるいくつかのステップがあります。各ステップは連続したサブマトリックスで実行できます(つまり、左上と右下隅で完全に囲まれたサブマトリックスを選択する必要があります)(非正方形のサブマトリックスでもかまいません)。

  1. 右90度回転*
  2. 左90度回転*
  3. 180度回転
  4. 各行の n 要素を右または左に(ラップして)循環させる
  5. 各列の m 要素を上下に(ラップして)循環させる
  6. 横にフリップする
  7. 縦方向に反転する
  8. メイン対角線を反転する*
  9. メイン対角線上にフリップする*

*サブ行列が正方形である場合のみ

もちろん、彼はまた、マトリックス全体でこれらのステップを実行することもできます。
1と0は行列上でのみスワップできますが、正方形の値は直接変更できませんので、開始と終了の設定では1と0の数は同じです。

Formatting 仕様 + Rules

あなたは、2つの正方行列(開始位置と終了位置)として、入力を任意の適切な形式で与えられます。出力は、これらのステップのシーケンスを読み込み可能な形式で出力する必要があります。これはコードゴルフではないので、簡単に確認できる形式にしてください。ただし、これは厳しい要件ではありません。必要に応じて、入力内の行列の長さを選択することができます。

あなたのプログラムは私のコンピュータ上で実行されます(Linux
Mint、正確なバージョンの詳細は誰でも気にしてください:P)。私はコマンドラインで
“enter”を押してからコマンドは終了します。

テストケース

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つの列を部分行列として取ります。各列を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)

標準的な抜け穴が適用されます。答えは受け入れられません。ハッピーコーディング!

Note: I drew inspiration for this チャレンジ series from
Advent
Of Code
. I have no affiliation with this site

You can see a list of all チャレンジs in the series by looking at the
‘Linked’ section of the first チャレンジ
here
.

ベストアンサー

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!

入力は、コマンドラインでスペースで区切られた整数です。最初の整数は2つの行列の幅です。残りの整数は行単位の要素です。

行列のすべての置換は、水平フリップ演算子と垂直フリップ演算子だけで得ることができるため、同じ領域の連続するvFlipとhFlipを180度置き換える以外は無視しました。

プログラムは各要素をスキャンします。間違ったビットを持つ要素に遭遇するたびに、正しいビットを持つ場所を見つけるために配列をさらに見ています。私は、検索領域を2つに分けました。それらは、等しいまたは大きい列座標を持つものと、小さい列座標を持つものです。後者は、配列をトラバースする方法に基づいて、より大きな行座標を持たなければならないことに注意してください。最初の探索領域で正しいビットが見つかると、2つの要素にまたがる部分行列を180度だけ回転させて、合計1回の操作を行うことができます。第2の領域にある場合は、水平フリップを使用して正しいビットを間違ったビットと同じ列に移動し、次に2つの部分行列全体を上下に反転して合計2つの操作を行うことができます。

プログラムの出力は、精神的に5つのグループに分割されるべき配列です。各グループは、(i、row1、col1、row2、col2)であり、iはノーオペレーションの場合0、180度回転の場合は1、水平フリップの場合は2、垂直フリップの場合は3です。残りの4つのコンポーネントは、操作が実行される領域を示します。これが読みやすい形式であるかどうかはわかりません。

与えられたテストケースに対して、私はコンピュータ上で258回の操作と2〜3ミリ秒を得ます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です