「第5回 オフラインリアルタイムどう書く」参考問題: へなちょこ解答(Java)
今さらながら、第5回の参考問題を解いたのでメモです。
- Rails on Tiles 〜 横へな 2012.11.9の参考問題 http://nabetani.sakura.ne.jp/hena/ord5railsontiles/
本番の問題よりも、ずっと簡単に感じました(^^;
自分の解答
/** * 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; } }
- 上のコードと、テストコード https://gist.github.com/4086072
考え方の覚書き
レール
正方形のタイルの各辺を、上から時計回りに、北東南西と考えます。
たとえば、タイル1の形状を考えてみます。(左の図)
タイル1のレールの振る舞いは、次のようにまとめられます。
- 北から入って東へ出る
- 東から入って北へ出る
- 西から入って南へ出る
- 南から入って西へ出る
次のタイルから見ると、「前のレールの出口=自分の入り口」になることに留意します。たとえば、前のレールの出口が南の場合、次のタイルにとっては、入口が北ということになります。(右の図)
タイル
タイルは、3x3マスで配置されています。タイルの位置は、インデックスで扱うことにします。左上が0で、右下が8です。(右の図)
あるタイルから見た東西南北のタイルのインデックスを、タイル自身に持たせることにします。マスの外側を表わすために、インデックスの9を使うことにします。
たとえば、インデックスが0のタイルに着目します。北と西はマスの外側なので9、東は1、南は3です。(左の図)
このマスは、自分の名前として「A」を持ちます。
処理の流れ
入力値は、タイルの名前(0〜2)です。
初期位置はB(つまり、インデックスでいうと1)です。また、北を入り口とすることが定められています。
というわけで、
- 入力値から、インデックス1にあるタイルの形状を得る
- タイルの形状と、入口の方角から、出口の方角を得る
- そのインデックスにとって、出口の方角にある次(のタイル)のインデックスを得る
- 次のインデックスと、(2の出口の方角の対象位置から求められる)次の入口の方角を用いて、1以降の処理を繰り返す
出力値は、通過するタイルの配置名(A〜I)です。なので、上記の処理をしながら、次のインデックスが判明するたびに、タイルの名前を取得して、出力値につぎたしていきます。
そんな感じです。