「第5回 オフラインリアルタイムどう書く」参考問題: へなちょこ解答(Java)

今さらながら、第5回の参考問題を解いたのでメモです。

本番の問題よりも、ずっと簡単に感じました(^^;

自分の解答

/**
 * 3x3マスの各位置のタイル。東西南北に位置するタイルのindexを持つ
 */
class Tile {
	int northernIndex;
	int easternIndex;
	int sourthernIndex;
	int westernIndex;
	char name;

	Tile(int n, int e, int s, int w, char nm) {
		northernIndex = n;
		easternIndex = e;
		sourthernIndex = s;
		westernIndex = w;
		name = nm;
	}

	/**
	 * 東西南北のindexを返す。9の場合はタイルの外
	 */
	int get(char bearing) {
		if (bearing == 'N') {
			return northernIndex;
		}
		if (bearing == 'E') {
			return easternIndex;
		}
		if (bearing == 'S') {
			return sourthernIndex;
		}
		return westernIndex;
	}

	@Override
	public String toString() {
		return String.valueOf(name);
	}
}

/**
 * 既定の3つのレール。各方角から入ったときの出口の方角を持つ
 */
class Rail {
	char northernExit;
	char easternExit;
	char sourthernExit;
	char westernExit;

	Rail(char n, char e, char s, char w) {
		northernExit = n;
		easternExit = e;
		sourthernExit = s;
		westernExit = w;
	}

	/**
	 * enter方角から入ってきた場合のexit方角を返す
	 */
	char getExit(char enter) {
		if (enter == 'N') {
			return northernExit;
		}
		if (enter == 'E') {
			return easternExit;
		}
		if (enter == 'S') {
			return sourthernExit;
		}
		return westernExit;
	}
}

/**
 * 問題: http://nabetani.sakura.ne.jp/hena/ord5railsontiles/
 */
public class RailsOnTiles {

	protected String solve(String input) {
		Rail[] rails = createRails();
		Tile[] tiles = createTiles();

		String result = "";
		result = loop(tiles, rails, 'S', 1, input, result);
		return result;
	}

	protected String loop(Tile[] tiles, Rail[] rails, char bearing, int index,
			String input, String result) {
		if (isOut(index)) {
			return result;
		}
		result += tiles[index].toString();
		int railId = Integer.valueOf(String.valueOf(input.charAt(index)));
		Rail rail = rails[railId];
		char exitBearing = rail.getExit(invert(bearing)); // 前回の出口の方角を反転して、入口として与え、次の出口の方角を得る
		int nextIndex = tiles[index].get(exitBearing); // 出て行く方角のindexを得る
		return loop(tiles, rails, exitBearing, nextIndex, input, result);
	}

	protected char invert(char c) {
		if (c == 'N') {
			return 'S';
		}
		if (c == 'E') {
			return 'W';
		}
		if (c == 'S') {
			return 'N';
		}
		return 'E';
	}

	protected boolean isOut(int i) {
		return 8 < i ? true : false;
	}

	protected Rail[] createRails() {
		Rail[] result = new Rail[3];
		result[0] = new Rail('S', 'W', 'N', 'E');
		result[1] = new Rail('E', 'N', 'W', 'S');
		result[2] = new Rail('W', 'S', 'E', 'N');
		return result;
	}

	protected Tile[] createTiles() {
		Tile[] result = new Tile[9];
		result[0] = new Tile(9, 1, 3, 9, 'A');
		result[1] = new Tile(9, 2, 4, 0, 'B');
		result[2] = new Tile(9, 9, 5, 1, 'C');
		result[3] = new Tile(0, 4, 6, 9, 'D');
		result[4] = new Tile(1, 5, 7, 3, 'E');
		result[5] = new Tile(2, 9, 8, 4, 'F');
		result[6] = new Tile(3, 7, 9, 9, 'G');
		result[7] = new Tile(4, 8, 9, 6, 'H');
		result[8] = new Tile(5, 9, 9, 7, 'I');
		return result;
	}
}

考え方の覚書き

レール

正方形のタイルの各辺を、上から時計回りに、北東南西と考えます。

たとえば、タイル1の形状を考えてみます。(左の図)

タイル1のレールの振る舞いは、次のようにまとめられます。

  • 北から入って東へ出る
  • 東から入って北へ出る
  • 西から入って南へ出る
  • 南から入って西へ出る

次のタイルから見ると、「前のレールの出口=自分の入り口」になることに留意します。たとえば、前のレールの出口が南の場合、次のタイルにとっては、入口が北ということになります。(右の図)

タイル

タイルは、3x3マスで配置されています。タイルの位置は、インデックスで扱うことにします。左上が0で、右下が8です。(右の図)

あるタイルから見た東西南北のタイルのインデックスを、タイル自身に持たせることにします。マスの外側を表わすために、インデックスの9を使うことにします。

たとえば、インデックスが0のタイルに着目します。北と西はマスの外側なので9、東は1、南は3です。(左の図)

このマスは、自分の名前として「A」を持ちます。

処理の流れ

入力値は、タイルの名前(0〜2)です。

初期位置はB(つまり、インデックスでいうと1)です。また、北を入り口とすることが定められています。

というわけで、

  1. 入力値から、インデックス1にあるタイルの形状を得る
  2. タイルの形状と、入口の方角から、出口の方角を得る
  3. そのインデックスにとって、出口の方角にある次(のタイル)のインデックスを得る
  4. 次のインデックスと、(2の出口の方角の対象位置から求められる)次の入口の方角を用いて、1以降の処理を繰り返す

出力値は、通過するタイルの配置名(A〜I)です。なので、上記の処理をしながら、次のインデックスが判明するたびに、タイルの名前を取得して、出力値につぎたしていきます。

そんな感じです。