2009年05月17日

[パズル]円環の塗り分け

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
放射状にn等分された円環を2色で塗り分けて、図のように内環と外環とを切り離します。外環を固定し、内環を回転してずらしたとき、どの位置でも(最初の位置を除き)内外同色の組み合わせと、内外異色の組み合わせの数の差を1以下にしたいとします。
n=31の時に、このような塗り分け方をひとつ求めるプログラムを作ってください。
Ring_335_297
図の例では、
同色:2つ
異色:6つ
となり、差は4となり、当てはまりません。

----
これをどうやって実現するかですが、問題がn=31であり、色が2色なので、ビット配列で円環を表すこととします。

そのために、BitArrayというクラスを作成します。
このクラスは、Rotateという要素を右にひとつずらすメソッドがあります。
はみ出た要素は、ぐるっと回って先頭に格納されます。
つまり、円環を表しているということです。
またインデクサも用意し、bits[n] のようにアクセスできるようにしています。 各要素のとりうる値は、1 と 0 です。
クラス Ringは、外環と内環をデータに持っています。IsOKメソッドは、どの位置でも、内外同色の数と内外異色の数の差が1以下ならば、trueを返します。
つまり、その円環は、求める円環ということになります。
このIsOKの下請けメソッドとして、Turn と、CountSameColorがあります。
同じ色の数がわかれば、異なる色の数もわかるので、カウントするのは、同色の数だけです。
Printメソッドは確認用です。

クラスSolverは、円環の配色のパターンすべてに対して、求める円環かどうかを調べていきます。問題は一つだけ求めれば良いので、求まった時点で、ループをやめています。
なお、すべての塗り分けパターンを求めるのは、数字を 1から2,3,4.. と加算することで、そのビットパターンを求めています。これを 0 と 1の組み合わせとして求めようとすると、もっと複雑なコードを書かなければならなくなります。

以下が、C#で書いたコードです。今回は、ちょっと LINQ度が低かったかな。
僕のPCだと、 46秒かかっています。もっと効率のよいやり方があるとは思うのですが、深入りはしていません。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51820984