「第4回オフラインリアルタイムどう書く」へなちょこ解答（Java）

昨日は、「第4回オフラインリアルタイムどう書く」でした。

…が、自分は所用で参加できなかったため、1日遅れで問題を解きました(^^;

今回は、テトロミノ認識です！

４つの座標から、テトロミノの名称を判定する。

10x10 のマス目のうち、いくつかを塗る。座標は、塗るマス目の位置を示す。

塗るマス目の指定は46,67,57,47のように行う。

※座標は xy の順でいずれも一桁(009)。座標の区切りはコンマ。

塗った形がテトロミノをなしている場合は、そのテトロミノの名称（下表参照）を出力する。

回転・裏返しなどで同じ形になるものは同じとみなす（つまり、下表の5種類しかない）

テトロミノをなしていない場合は、"-" と出力する。

座標は必ず４つあるが、重複している場合がある。（その場合はテトロミノをなさない）

テトロミノ認識〜横へな 2012.10.6

（参考）テトロミノ-Wikipedia http://ja.wikipedia.org/wiki/%E3%83%86%E3%83%88%E3%83%AD%E3%83%9F%E3%83%8E

テトロミノという言葉を初めて知りました。この図形って、そういう呼び名があるのですね。

解答

Javaです。長いです。

import java.util.ArrayList;
import java.util.List;

public class Tetroid {

	private final int CELL_NUM = 4;

	protected int getX(String str) {
		return Integer.parseInt(String.valueOf(str.charAt(0)));
	}

	protected int getY(String str) {
		return Integer.parseInt(String.valueOf(str.charAt(1)));
	}

	protected final boolean isL(int[][] shape) {
		int firstX = shape[0][0];
		int firstY = shape[0][1];
		if (firstX != shape[1][0] || (firstY + 1) != shape[1][1]) {
			return false;
		}
		if (firstX != shape[2][0] || (firstY + 2) != shape[2][1]) {
			return false;
		}
		if ((firstX + 1) != shape[3][0] || (firstY + 2) != shape[3][1]) {
			return false;
		}
		return true;
	}

	protected final boolean isI(int[][] shape) {
		int firstX = shape[0][0];
		int firstY = shape[0][1];
		if (firstX != shape[1][0] || (firstY + 1) != shape[1][1]) {
			return false;
		}
		if (firstX != shape[2][0] || (firstY + 2) != shape[2][1]) {
			return false;
		}
		if (firstX != shape[3][0] || (firstY + 3) != shape[3][1]) {
			return false;
		}
		return true;
	}

	protected final boolean isT(int[][] shape) {
		int firstX = shape[0][0];
		int firstY = shape[0][1];
		if ((firstX + 1) != shape[1][0] || firstY != shape[1][1]) {
			return false;
		}
		if ((firstX + 1) != shape[2][0] || (firstY + 1) != shape[2][1]) {
			return false;
		}
		if ((firstX + 2) != shape[3][0] || firstY != shape[3][1]) {
			return false;
		}
		return true;
	}

	protected final boolean isO(int[][] shape) {
		int firstX = shape[0][0];
		int firstY = shape[0][1];
		if (firstX != shape[1][0] || (firstY + 1) != shape[1][1]) {
			return false;
		}
		if ((firstX + 1) != shape[2][0] || firstY != shape[2][1]) {
			return false;
		}
		if ((firstX + 1) != shape[3][0] || (firstY + 1) != shape[3][1]) {
			return false;
		}
		return true;
	}

	protected final boolean isS(int[][] shape) {
		int firstX = shape[0][0];
		int firstY = shape[0][1];
		if ((firstY + 1) != shape[1][1]) {
			return false;
		}
		if ((firstX + 1) != shape[2][0] || (firstY + 1) != shape[2][1]) {
			return false;
		}
		if ((firstX + 1) != shape[3][0] || (firstY + 2) != shape[3][1]) {
			return false;
		}
		return true;
	}

	protected int[][] flipHorizontal(int[][] shape) {
		int[][] result = new int[CELL_NUM][2];
		for (int i = 0; i < CELL_NUM; i++) {
			result[i][0] = 4 - shape[i][0];
			result[i][1] = shape[i][1];
		}
		sortCell(result);
		return result;
	}

	protected int[][] flipVertical(int[][] shape) {
		int[][] result = new int[CELL_NUM][2];
		for (int i = 0; i < CELL_NUM; i++) {
			result[i][0] = shape[i][0];
			result[i][1] = 4 - shape[i][1];
		}
		sortCell(result);
		return result;
	}

	protected int[][] rotate90deg(int[][] shape) {
		int[][] result = new int[CELL_NUM][2];
		for (int i = 0; i < CELL_NUM; i++) {
			result[i][0] = 4 - shape[i][1];
			result[i][1] = shape[i][0];
		}
		sortCell(result);
		return result;
	}

	protected int[][] rotate180deg(int[][] shape) {
		int[][] result = new int[CELL_NUM][2];
		for (int i = 0; i < CELL_NUM; i++) {
			result[i][0] = 4 - shape[i][0];
			result[i][1] = 4 - shape[i][1];
		}
		sortCell(result);
		return result;
	}

	protected int[][] rotate270deg(int[][] shape) {
		int[][] result = new int[CELL_NUM][2];
		for (int i = 0; i < CELL_NUM; i++) {
			result[i][0] = shape[i][1];
			result[i][1] = 4 - shape[i][0];
		}
		sortCell(result);
		return result;
	}

	protected int compare(int[] is, int[] target) {
		if (target[0] < is[0]) {
			return 1;
		} else if (is[0] < target[0]) {
			return -1;
		}
		if (target[1] < is[1]) {
			return 1;
		} else if (is[1] < target[1]) {
			return -1;
		}
		return 0;
	}

	protected void sortCell(int[][] shape) {
		for (int i = 0; i < CELL_NUM - 1; i++) {
			for (int k = CELL_NUM - 1; i < k; k--) {
				if (0 < compare(shape[k - 1], shape[k])) {
					int[] tmp = shape[k];
					shape[k] = shape[k - 1];
					shape[k - 1] = tmp;
				}
			}
		}
	}

	protected int[][] getData(String input) {
		int[][] result = new int[4][2];
		String[] strings = input.split(",");
		List<int[]> tmp = new ArrayList<>();
		for (String str : strings) {
			int x = getX(str);
			int y = getY(str);
			int[] point = { x, y };
			tmp.add(point);
		}
		return tmp.toArray(result);
	}

	protected char shapeCheck(int[][] shape) {
		if (isL(shape)) {
			return 'L';
		}
		if (isI(shape)) {
			return 'I';
		}
		if (isT(shape)) {
			return 'T';
		}
		if (isO(shape)) {
			return 'O';
		}
		if (isS(shape)) {
			return 'S';
		}
		return '-';
	}

	protected char execute(String input) {
		int[][] shape = getData(input);
		sortCell(shape);
		int[][][] shapes = new int[8][4][2];
		shapes[0] = shape;
		shapes[1] = rotate90deg(shape);
		shapes[2] = rotate180deg(shape);
		shapes[3] = rotate270deg(shape);
		shapes[4] = flipHorizontal(shape);
		shapes[5] = rotate90deg(shapes[4]);
		shapes[6] = flipVertical(shape);
		shapes[7] = rotate90deg(shapes[6]);

		for (int[][] point : shapes) {
			char result = shapeCheck(point);
			if (result != '-') {
				return result;
			}
		}
		return '-';
	}
}

上のコードとテストコード https://gist.github.com/3847802

考え方の覚書き

マス目の集合がテトロミノをなすかどうか

まず、向きがまっすぐな場合のテトロミノの判定方法を考えました。テトロミノをなす各マスについて、マスが座標の昇順で並んでいると想定して、1つ目のマスからの相対座標を定義しました。

たとえば、Lは、次のとおりです。

書き始めの地点のマスの座標が(x, y)のとき、隣接するマスの座標は(x, y+1)、その次のマスの座標は(x, y+2)、最後のマスの座標は(x+1, y+2)です。

これを、L、I、T、O、Sそれぞれについて定義しました。

コードでいうと、isL、isI、isT、isO、isSというメソッドがそれです。

回転と反転への対応

次に、定義したパターンとの照合方法を考えました。「O」だけは、向きにかかわらず、定義したパターンで照合できますが、それ以外は、回転や反転に対応しなければなりません。

ここで、対称性に最も乏しいLに着目し、あり得るすべての向きを列挙します。

色が薄いパターンは、既出であることを表わします。たとえば、「1´. 垂直反転＋180°回転」は、「1. 正位置の水平反転」と同じであるため、照合を省略できます。これをまとめると、次の8種類の向きに対してパターンと照合すれば、すべての反転と回転をカバーできることになります。

正位置
正位置の90°回転
正位置の180°回転
正位置の270°回転
正位置の水平反転
水平反転＋90°回転
正位置の垂直反転
垂直反転＋90°回転

回転と反転の座標変換は、5x5のマス目を想定して書きました。パターンを相対座標で定義したので、実際の座標値を気にする必要はありません。

コードでいうと、flipHorizontal、flipVertical、rotate90deg、rotate180deg、rotate270degというメソッドがそれです。

実行

というわけで、入力値を8種類の向きに変換して、その都度、座標の昇順にソートし、定義したパターンと照合しました。

所感

1時間じゃ全然終わりませんでした。45分くらい机上でロジックを検証して、45分くらいでコードを書いて、30分くらい誤検出のデバッグをしていました。ひー・・・

書いてる途中に埋め込んだバグは、

回転・反転後に座標のソートを忘れていた
パターン定義で、4マスすべてのX座標、Y座標を定義していなかった

といったところでした(^^;

パターン照合の問題は、あまり解いたことがなかったので新鮮でした！

鍋谷さん、問題ありがとうございました。今度はぜひオフラインで参加させてください。