Re: ドラクエVIIのバロックタワーのパズルを解く
(※ネタバレあり) / ドラクエVIIのバロックタワーのパズルを解くd.hatena.ne.jp/torazuka/20130…
— torazukaさん (@torazuka) 2013年2月20日
DQ7はやっていませんが、パズルをプログラミングで解くのはおもしろそうだったので、やってみました。
書いたプログラム
方針は、こんな感じです。
- 像の向きやボタンをマジックナンバーではなく、列挙型にする。型安全!! 分かりやすい!?
- 変化するフィールド(副作用)は頭がこんがらがるので、極力なくす。
- 幅優先探索にする(深さ8までに限るとかしなくてよくする)
- できるだけ自分で分岐やループを描かない。自家製のLINQ風ライブラリ Queenでどこまでできるか。
できたコードがこちら。
解説
解いてるところを1行ごとに追ってきます。
public static List<Button> solve(final Statues statues) {
4つの像を1つの型(Statues)として表しています。配列でもよいのですが、statues[0]よりstatues.topのほうが分かりやすくないですか? そんなことはない? 戻り値は、パズルの答えであるボタンの押す順序・回数を、ButtonのListとして表現しました。
return Sequence.from(Button.values())
ボタンを表す列挙型Buttonのすべての配列を、LINQっぽい値の連なりに変えています。
.map(Funcs.<Button>toSingletonList())
おなじみのmap演算子です。各Buttonを、要素が1しかないリストに変換しています。
.iterateBreadthFirst(GROWTH)
GROWTHは、Buttonのリスト末尾に別のButtonを付け加えて、Buttonの押す組み合わせを次々と作っていく関数です。これを幅優先探索していく演算子に与えています。こうすることで、[A]、[A,A]、[A,A,A]……、などとどんどん深くはなっていかずに、[A]、[B]、[C]、[D]、[A,A]、[A,B]……と同じ深さ(回数)でのボタンの組み合わせを色々試してくれます。
.first(new Predicate<List<Button>>() {
private final Statues _ = new Statues(Direction.S, Direction.W, Direction.N, Direction.E);
public boolean evaluate(final List<Button> buttons) {
return Sequence.from(buttons).fold(statues, ROTATE).equals(_);
}
})
条件に合う最初の要素を見つける演算子です。この場合の条件とは、4つの像がすべて中心方向を向いているということ。
.getOrElse(Collections.<Button>emptyList());
}}
first演算子は、値があるかないかを表すOption型を返します。getOrElseは、値がない場合の代用値を指定するメソッドです(LINQの標準演算子FirstOrDefaultをちょっと変えています)。このパズルでは、値がない=答えがない=押すボタンの組み合わせが存在しないということですが、これをnullではなく空のリストとして表現します。nullはやめましょうね!!
そんな感じで、solveメソッド(と、それが使用している関数オブジェクト)は、if文やfor文を使わず書けました。
肝心の実行結果は、こうなりました。良さそうですね。
[TOP_RIGHT(0), TOP_RIGHT(0), TOP_RIGHT(0), BOTTOM_RIGHT(1),
BOTTOM_RIGHT(1), BOTTOM_LEFT(2), BOTTOM_LEFT(2), TOP_LEFT(3)]
ちゃんと使えるかどうか確かめたいので、DQ7買おうかな。
どなたか貸してくれませんかねー。