「今週のお題：壊れたピンチハンガー」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ちょっと遅くなりましたがネタバレです。
問題
詳細は、以下のCodeIQ Magazineの記事にありますが、一種のドミノ配置の問題です。
横10×縦7の領域を、1×2 ( 縦・横の向きはどちらでも良い ) のドミノ ( 問題では「ピンチハンガー」 ) を配置して埋め尽くす時、予め最低何個配置すれば配置が一意に決まるか、その個数を求めるのが目的です。
今回は自動採点ではないので、いつもの「実行時間1秒」の縛りはありません。
解説
方針
例えば、次のような4ペアを指定することで全て決定できるため、答えは高々4であることが分かります。
※空いた隙間に次々配置していくと、結局1通りしかないのです。
しかしながら、3で済む配置がないのか、確信があるわけではありません。 だからと言って全部の配置を検索していてはとても終わりません。 そこで次の仮定を元に、現実時間で済むようにしました。( 実際Rubyで10秒以内で終わります )
- 配置を追加していく時には必ず「端に臨んだ」場所にする
これは、中央部分だけにペアを配置してもそれだけで全部が決定できないことから、 必ず ( 決定済みのエリアを除いた中での ) 端に臨んだ場所に次々配置していける、ということからきています。 具体的には、ペアを囲む ( 3×4の領域の外周の ) 10か所のいずれかが決定済み ( あるいは端を超えて領域外 ) であるような配置を指します ( 次の図の水色の部分 )
これはどういうことかというと、既に配置が決まっている領域がすぐ隣にあれば、次のように新たに配置が決まって埋まっていく可能性があるからです。逆に隣になければ決まりようがない、ということです。
なお、普段の自動採点のように1秒程度で終わらせるなら、次の仮定も必要になります
- 配置を追加していく時には必ず、追加で決定済みのペアができる場所にする
例えば次の図のように配置しても、すぐには決定済みの場所は増えません。
次やその次のペアの配置のおかげで増える可能性があるにしても、決定済みの場所の数が増えていくうえでは不利であるとみなして検索対象から外します これは、後で紹介する実装中のメソッドfillの実装を変更することで対応できます。が、やや決め打ちが過ぎるようにも感じたので今回は見送りました。
実装
配置の状況を、任意精度の整数を用いたbit列として扱うことで、論理演算ベースで一括処理できるように実装しました。 ただ、そのまま1次元データとして扱うと、行またぎの処理で不正が出るため、ダミーの領域を設け対処しています。 例えば、4×3の領域の場合、上下と右に配置済みの領域を設けそれから1次元化します
まあ、ダミーを挟んで1次元化ってのは良くやる手ですね。( だと思う… )
こうすることで、「端かどうか」を気にする必要なく、セル同士の位置関係に注力できるというわけです。ダミーを挟まないと「前の行の終わりと次の行の始まり」なのか「左右の隣接」なのか混同してしまいますので、要注意。
ちょっとオブジェクトの意味付けが分かりにくくなるのですが、配置状況のみならず、「端に面した配置が可能な箇所」等も同じクラスで表すことにしました。
ということで、詳細についてはソースコード中のコメントをご参照を。
終わりに
本当の事いうと、中央に配置する場合でも、3個目位で追加決定できるところができるパターンがあるので、このやり方完全じゃないんですけど…。
まあただ今回はどうせ4個目で打ち切るんだから、ま、いっか、という感じで。
