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

どう書く

昨日の夜、「第3回 オフラインリアルタイムどう書く」に参加してきました。

オフラインリアルタイムどう書くとは？
出されたお題を好きなプログラミング言語で解いて遊ぶ集まりです。制限時間は約1時間で、主催の鍋谷さんがお題を作成してくださいます。

解答言語の内訳は、C++ 1人、Haskell 1人、Java 1人、Perl 1人、Ruby 4人でした。

鍋谷さんが、「そのうち問題が溜まって、もし電子書籍にしたら、欲しい人なんていますかね」と懇親会でおっしゃっていました。ゼッタイに売れると思います！！！と答えたのですが、1人じゃアレなので、欲しい方はこの記事のコメント欄にわっふるわっふると（ｒｙ

実際、鍋谷さんの問題は、

  • 現実に存在する題材（テトリス、ポーカー、野球など）があるとき、そのルールを知らなくても解けるレベルにまで、問題が厳密に仕様定義されている
  • 仕事でプログラムを書いている人が複数人集まって挑戦して、制限時間内に解けたり解けなかったりするくらい、需要に対する難易度調整が絶妙
  • うれしいことに日本語で提供されている

と、かくも素晴らしいのです。新しい言語を学ぶときのお題にもピッタリですよね。わっふるわっふる

問題

今回は、Y字路巡りです！

下図の通りの地図がある。
BからAへ向かう道の途中からスタート。
Y字路に到達するたびに、入力文字列の指示に従って右折/左折/後戻り のいずれかを選択する。
通過したY字路名前を順に出力せよ。

詳細は、問題ページをご覧ください。

自分の解答

Javaでかきました。

import static org.junit.Assert.assertEquals;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

public class TripY {

	Map<String, String> dic;

	public TripY() {
		dic = new HashMap<>();
		dic.put("BAr", "C");
		dic.put("BAl", "D");
		dic.put("ABr", "E");
		dic.put("ABl", "C");
		dic.put("ACr", "B");
		dic.put("ACl", "F");
		dic.put("CAr", "D");
		dic.put("CAl", "B");
		dic.put("ADr", "F");
		dic.put("ADl", "E");
		dic.put("DAr", "B");
		dic.put("DAl", "C");
		dic.put("BCr", "F");
		dic.put("BCl", "A");
		dic.put("CBr", "A");
		dic.put("CBl", "E");
		dic.put("BEr", "D");
		dic.put("BEl", "F");
		dic.put("EBr", "C");
		dic.put("EBl", "A");
		dic.put("DEr", "F");
		dic.put("DEl", "B");
		dic.put("EDr", "A");
		dic.put("EDl", "F");
		dic.put("CFr", "E");
		dic.put("CFl", "D");
		dic.put("FCr", "A");
		dic.put("FCl", "B");
		dic.put("DFr", "C");
		dic.put("DFl", "E");
		dic.put("FDr", "E");
		dic.put("FDl", "A");
		dic.put("EFr", "D");
		dic.put("EFl", "C");
		dic.put("FEr", "B");
		dic.put("FEl", "D");
	}

	protected String execute(String input) {
		String result = "A";
		String current = "BA";

		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			if (c == 'b') {
				result += current.charAt(0);
				current = String.valueOf(current.charAt(1))
						+ String.valueOf(current.charAt(0));
			} else if (c == 'r' || c == 'l') {
				String tmp = current + String.valueOf(c);
				String to = dic.get(tmp);
				result += to;
				current = String.valueOf(current.charAt(1)) + to;
			}
		}
		return result;
	}

	public static void main(String[] args) {
		TripY trip = new TripY();
		System.out.println(trip.execute("llllllrllrlbrrr")); // ADEBADEFCBADABED
	}
}
考え方のメモ

Mapで辞書を定義します。

  • key: "{from}{to}{指示器}"という文字列
    • 次の行程を示すr、l、bを指示器と考える
  • value: "{from}{to}"のベクトルにいるときに{指示器}を与えられて選択する次の位置

メインの処理であるexecuteメソッドは、解答文字列resultと、現在のベクトルを表わす文字列currentを持ちます。resultには、位置を表わす文字がどんどん継ぎ足されていきます。currentは、指示器を1つ処理するごとに代入で上書きするため、常に1ベクトル（"{from}{to}"の2文字）だけ入っています。

b（後戻り）がきたら、元いた場所が次の位置になるので、resultにcurrentの{from}を足します。そして、向きを逆にするため、currentのベクトルの前と後ろを入れ替えます。

r（右折）かl（左折）がきたら、currentの{from}{to}に{指示器}を継ぎ足して、辞書を引き、次の位置を得ます。得た値をresultに足します。currentを{from}{to}から、{to}{得た値}に更新します。

所感

初めて時間内に解けました。ヤッター。でも、35分くらいかかりました。

残り時間で、スタックで解けないかと考えて迷走した結果がこちらです。すっきり解けなかったので、説明は省略……。

また、C/C++/Java用に提供してくださっているテストデータの使い方が、初めて分かりました。配列に突っ込んで回せばよかったんですね。どこでコケたかが分かりづらいので、テストデータの通し番号を出力すればよいですね。

皆さんの解答

皆さんの解答を集めておけば、参加しなかった方が読んでも面白いかなと思ったのですが、追いきれませんでした。すいません。

所感

というわけで

楽しかったです！ 鍋谷さん、参加された皆さん、ありがとうございました。