ラベル

Re: ドラクエVIIのバロックタワーのパズルを解く

DQ7はやっていませんが、パズルをプログラミングで解くのはおもしろそうだったので、やってみました。

書いたプログラム

方針は、こんな感じです。

  • 像の向きやボタンをマジックナンバーではなく、列挙型にする。型安全!! 分かりやすい!?
  • 変化するフィールド（副作用）は頭がこんがらがるので、極力なくす。
  • 幅優先探索にする（深さ8までに限るとかしなくてよくする）
  • できるだけ自分で分岐やループを描かない。自家製のLINQ風ライブラリ Queenでどこまでできるか。

できたコードがこちら。

解説

解いてるところを1行ごとに追ってきます。

public static List<Button> solve(final Statues statues) {

４つの像を１つの型（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買おうかな。

どなたか貸してくれませんかねー。

ラベル:

人気の投稿