« 2015年10月 | トップページ | 2015年12月 »

2015年11月 1日 (日)

20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』

 先日、CodeZine で『プログラマ脳を鍛える数学パズル』キャンペーンクイズというのをやっていて、「20個のカラーボックスで作る本棚は何通り?」という問題を解くプログラムを作成して応募しました。そして、28日朝に応募受付終了後に正解が発表されました。
20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』キャンペーンクイズの解答
発表された正解は610通りということで、私のプログラムでもそうなったことから考え方は間違ってなかったようです。

 この問題の解き方ですが、まず、カラーボックスを便宜上小さな正方形が[2個x3個]で組み合わさったボックスと考えます。すると、完成形の面積は[個数x6]となり、20個での縦横のサイズの組み合わせは次の通りになります。
[1x120],[2x60],[3x40],[4x30],[5x24],[6x20],[8x15],[10x12],[12x10],[15x8],[20x6],[24x5],[30x4],[40x3],[60x2],[120x1]
ところが、この中で[1x120]と[120x1]はボックスを置けないことが明らかなので除外します。
(除外しなくても、最初のボックスを置けなくて処理が終わるのでほとんど実行時間に影響はないですが)

 次に、それぞれの長方形の枠に、[2x3]か[3x2]のボックスを敷き詰めていきます。私のプログラムでは、strlen を使用して、上の左で最初にある空白[0]を探します。もし、その位置(pos)が長方形の面積分以上なら、枠が埋まったことになるのでカウントを増やします。

 ということで、これ以降の処理は、位置が面積分未満だった場合です。その位置を左上としてボックスを横置きできるか調べ、置けるなら6箇所に置いたマークをつけ、自分自身の処理を再帰呼出して、その後、6箇所につけたマークを消します。そして、縦置きに関しても同様な処理を行います。

 さて、置けるかどうかを調べる処理ですが、私は3つの条件全てを満たしたらで判定しています。最初に作ったバージョンでは、横置きチェックの3つの条件は次のようにしました。
(座標は外枠の左上を[0,0]とし、右下に向かってプラスとする)
1. 空き位置の x座標 + 3 が外枠の x方向のサイズ以下⇒枠の右端よりはみ出さない
2. 空き位置の y座標 + 2 が外枠の y方向のサイズ以下⇒枠の下端よりはみ出さない
3. 空き位置から右に + 2 の部分にマークがついていない(空きである)
ここで、3番の条件ですが、普通なら[3x2]の6箇所(左上はチェック済なので残る5箇所)を調べなくてはならないように思えますが、実はこのように右上を調べるだけでいいのです。

 その理由は、ボックスの短辺でも長さが2あること、ボックスを上の左から順番に埋めていることの2点です。横置きの場合、左上が空き、右上が空きであれば、その間である上の中央が埋まっていることはありえません。また、上側が空きなのにその下側が埋まっているためには、現在調べているより下、つまりまだ処理を行っていない部分に置いてある必要があるので、これまた処理の順番からありえません。ということで、左上と右上が空きであるならば、6箇所すべてが空きであることが確定するわけです。

 そして、縦置きチェックの3つの条件は次の通りです。
1. 空き位置の x座標 + 2 が外枠の x方向のサイズ以下⇒枠の右端よりはみ出さない
2. 空き位置の y座標 + 3 が外枠の y方向のサイズ以下⇒枠の下端よりはみ出さない
3. 空き位置から右に + 1 の部分にマークがついていない(空きである)
この場合は、上記の後者の理由により、上段の2箇所が共に空きなら2段目・3段目含めた6箇所すべてが空きであることになります。

 再帰呼出を使用するので、スタックオーバーフローを避けるため、パラメータ・ローカル変数はできるだけ少なくするようにしました。私のプログラムでは、カラーボックスの数の深さ分の再帰呼出となるわけですが、変数などが1つ増えると、深さを掛けた分のスタックが使用されるからです。もちろん、出題された20個ぐらいならどうってことないのですが、超巨大本棚にも対応できるようにということで・・・。

 ところが、この通りの処理でプログラムを作成すると、出題された20個ぐらいならすぐ終了しますが、30個ぐらいから処理時間が長くなってきて50個ぐらいになると何時間もかかってしまいます。そこで、長方形の枠のサイズごとに調べてみると、横が3マスとなる場合は高速ですが、縦が3マスとなる場合に処理時間がとんでもなく長くかかっていました。横3マスで左上隅に縦置きしたり、縦3マスで左上隅に横置きすると後で埋められないことは明らかですが、この処理だとそれが置けてしまいます。それでも、前者の場合は、その後右上隅に置こうとしても置けずに処理が終了することになり、無駄な処理は少ないです。それに対して、後者の場合は、その後右に向かってどんどん縦横いずれも置けてしまい、左下隅(または右上隅)まで来た時に初めて置けなくなります。つまり、その間の膨大ともいえる無駄な組み合わせのチェックで時間がかかってしまっていたわけです。

 ということで、新バージョンでは、ブロックを置くと右端か下端が1マスしか残らなくなる場合、ブロックは置けないものとする条件を追加しました。具体的には、横置き・縦置きそれぞれの場合の1番・2番の条件の「以下」に「ただし、差が1になる場合を除外する」を追加しました。そうすることによって、例えば、カラーボックス36個の組み合わせパターンを求める場合は、処理時間が1/500程度までも短縮されました。ちなみに、外枠が縦長~正方形までというように、外枠の縦か横かどちらか長い方を決めて正方形以外のパターン数を倍にすることで処理時間は半分近くに短縮されますが、ちょっとこういうやり方は邪道な気がするので採用しませんでした。

 以下が私が作ったプログラムのソースです。出題された20個の場合だけを求めても面白くないので、任意の範囲(今のだと2~50個)のパターン数をすべて求めるようにしました。
(ブログ用に多少書き足した部分がありますが、アルゴリズムは応募したものと同一です)

#include "string.h"
#include "time.h"
#define BoxMin 2 // 何個から調べる
#define BoxMax 50 // 何個まで調べる
#define Question 20 // 出題された個数
char work[BoxMax * 6 + 1]; // 0:空き, 0以外:既に置いてある
// 置けるかどうかを調べる為の配列(関数にしてもいいけど配列の方が高速かと)
bool check[BoxMax * 3 + 1];
int numbox, xmax, ymax, count;
void putbox() // パラメータはなし
{
int pos; // ローカル変数は1つのみ
// strlen で最初の空きデータ[0]の位置を探す
if ((pos = strlen(work)) >= numbox * 6) {
count++; // 外枠内がすべて埋まっているのでカウントする
return;
}
// 横置き(旧バージョン)
// if (pos % xmax < xmax - 2 && pos / xmax < ymax - 1 && work[pos + 2] == 0) {
// 横置き(新バージョン)
if (check[xmax - (pos % xmax) - 1] && check[ymax - (pos / xmax)] &&
work[pos + 2] == 0) {
work[pos] = work[pos + 1] = work[pos + 2] = work[pos + xmax] =
work[pos + xmax + 1] = work[pos + xmax + 2] = '*';
putbox(); // 再帰呼出
work[pos] = work[pos + 1] = work[pos + 2] = work[pos + xmax] =
work[pos + xmax + 1] = work[pos + xmax + 2] = 0;
}
// 縦置き(旧バージョン)
// if (pos % xmax < xmax - 1 && pos / xmax < ymax - 2 && work[pos + 1] == 0) {
// 縦置き(新バージョン)
if (check[xmax - (pos % xmax)] && check[ymax - (pos / xmax) - 1] &&
work[pos + 1] == 0) {
work[pos] = work[pos + 1] = work[pos + xmax] = work[pos + xmax + 1] =
work[pos + xmax * 2] = work[pos + xmax * 2 + 1] = '*';
putbox(); // 再帰呼出
work[pos] = work[pos + 1] = work[pos + xmax] = work[pos + xmax + 1] =
work[pos + xmax * 2] = work[pos + xmax * 2 + 1] = 0;
}
}
int main()
{
int i, cnt0;
clock_t start, start1;
for (i = BoxMax * 6; i >= 0; i--) work[i] = 0;
// 右端か下端に1マス残る置き方を除外
for (i = BoxMax * 3; i >= 0; i--) check[i] = (i >= 2 && i != 3);
printf("カラーボックスで作る本棚\n");
for (numbox = BoxMin; numbox <= BoxMax; numbox++) {
start = clock();
count = 0;
// 個数分で長方形となる枠を作成し、[2x3]・[3x2]のボックスをはめ込む
for (ymax = numbox * 3; ymax > 1; ymax--) {
if (numbox * 6 % ymax == 0) {
xmax = numbox * 6 / ymax;
cnt0 = count;
start1 = clock();
putbox();
// 詳細表示
// printf("box=%d\tx=%d\ty=%d\ttime=%dms\tcnt=%d\n",
// numbox, xmax, ymax, clock() - start1, count - cnt0);
}
}
printf("%3d 個の場合%8d パターン 処理時間%6dms%s\n",
numbox, count, clock() - start,
numbox == Question ? " ← [問題の回答]":"");
}
return 0;
}

 ところで、正解例として発表された Ruby のソースですが、正直言って余り上手くないのではないかと思います。その理由は、「一行を埋めた場合」と「現在の位置が埋まっている場合」までも再帰呼出をしている点です。私の処理では、カラーボックス20個の場合は、最初の呼出を除き再帰呼出の深さは20回となりますが、このソースでは160回となります。36個の場合は288回となります。つまり、私の処理では個数分の深さですが、このソースでは個数の8倍の深さとなります。上記2つの場合の「次の行」や「次の位置」の処理は、再帰呼出を使うのではなく bookshelf の内部での移動処理にすべきでしょう。

 あともう1点、再帰呼出に使われる bookshelf のパラメータのうち、box, w, h の3つは常に同じものとなり変化することはありません。それなら、この3つはグローバル変数として外に出すべきです。再帰呼出で常に同じ値を渡しても、それは単なるスタックバッファの無駄遣いにしかならないと思います。
(私は Ruby を知らないので推測で書いていますが、万一、Ruby ではそれができないとかならごめんなさい)

| | コメント (1) | トラックバック (0)

« 2015年10月 | トップページ | 2015年12月 »