以下の６種類の図形がある。これらを２個ずつ３組に分け，裏返さずに同じ図形を作る。
先週から昨日(1/31)迄はやることが多すぎパニック状態でプログラムが手に着かず。
焦ると頭の中が真っ白になって，時間ばかりが経過してしまう。ようやく時間が持てるようになったので再チャレンジ。
ありゃ？先日あれほど大変だと思っていたのが結構簡単に出来ちゃった。
アプローチの仕方は色々あるだろうけど，兎に角枝刈りしないと大変だ。
組み合わせた図形の形をなるべく小さいビット数で表現したい。一番横幅を使うのが以下のように３と４の組合せ。
だけどこんな図形では他と一致しないことは明らか。多分４ｘ４以下の図形になるんだろうなーと思いながらも理論武装が出来ない。
困った。
だけど４ｘ４という前提で見切り発車。しかしこれで見つからないと悲惨だぞ。４ｘ５だと数が多すぎるんじゃないか？
４ｘ４だと例えば以下のような配置が考えられる。これに回転を加えると１６通りになる。
図形によって配置できる数は異なるが，処理を簡単にするため，右シフトが４通り，下シフトが４通り，回転が４通りの計43(=64)通り考える。
図形を２個組み合わせると64x64(4096)通りの図形が考えられる。
組み合わせた図形は16ビットで表現する。例えば以下の組合せだと 0x4EBE になる。
６個の図形から２個を取り出す方法は６ｘ５（＝３０）通りある。但しこれも処理の都合上６ｘ６の領域を確保する。
そうすると全ての図形は以下のような領域に記録できる。4x4がダメな時を考えて図形は4バイトで表現する。
int4* parts_kumiawase[36] = { NULL};
parts_kumiawase[idx_kumiawase] = new int4 [ 4096 ]; // ２つの図形の組合せで出来るのは最大4096個
全ての図形を求めるコードは以下のようになる。同じ図形が出現した場合最後に重複を除去しておく。
int4* parts_kumiawase[36] = { NULL};
int parts_num[36] = {0};
int parts_use[36] = {0};
for( int iparts1=0; iparts1< 6; iparts1++) {
for( int iparts2=iparts1+1; iparts2< 6; iparts2++) {
//----------------------------------------------------------
// ２つの図形を選択した場合の全ての組合せ
// この組合せを回転させたり，移動したりして求まる組合せが以下のようになる。
//----------------------------------------------------------
int4 parts1 = parts[iparts1], parts1_oped;
int4 parts2 = parts[iparts2], parts2_oped;
int idx_kumiawase = iparts1*6 + iparts2;
parts_kumiawase[idx_kumiawase] = new int4 [ 4096 ]; // ２つの図形の組合せで出来るのは最大4096個
parts_use[idx_kumiawase] = partsuse[iparts1] | partsuse[iparts2]; // この図形を構成する図形
int inum = 0;
for( int rotate1=0; rotate1< 4; rotate1++) {
for( int shift1R=0; shift1R< 4; shift1R++) {
for( int shift1D=0; shift1D< 4; shift1D++) {
parts1_oped = translate_parts( parts1, rotate1, shift1R, shift1D);
if( parts1_oped == 0) continue;
for( int rotate2=0; rotate2< 4; rotate2++) {
for( int shift2R=0; shift2R< 4; shift2R++) {
for( int shift2D=0; shift2D< 4; shift2D++) {
parts2_oped = translate_parts( parts2, rotate2, shift2R, shift2D);
if( parts2_oped == 0) continue;
//----------------------------------------------------
// この組合せでどんな図形が出来るか?
//----------------------------------------------------
int4 new_parts = parts1_oped | parts2_oped;
//----------------------------------------------------
// この図形をA,B というような組合せの結果として記憶しておく。
//----------------------------------------------------
parts_kumiawase[idx_kumiawase][inum] = new_parts;
inum++;
cnt++;
}
}
}
}
}
}
//----------------------------------------------------------------
// 記憶した図形の組合せから重複を除去しておく。
//----------------------------------------------------------------
parts_num[idx_kumiawase] = dupout( parts_kumiawase[idx_kumiawase], inum);
}
}
求まった図形のうち同じ図形を使っている組合せを求める。
//--------------------------------------------------------------------
// 求まった組合せの図形のうち３つを選択し，同じ図形が存在すればOK。
// 但し，基本図形は全て異なる必要がある。
//--------------------------------------------------------------------
int4 zukei;
set<int4> zukeifind;
for( int ikumiawase1=0; ikumiawase1< 36; ikumiawase1++) {
if( parts_kumiawase[ikumiawase1] == NULL) continue;
for( int ikumiawase2=0; ikumiawase2< 36; ikumiawase2++) {
if( parts_kumiawase[ikumiawase2] == NULL) continue;
for( int ikumiawase3=0; ikumiawase3< 36; ikumiawase3++) {
if( parts_kumiawase[ikumiawase3] == NULL) continue;
if( ( parts_use[ikumiawase1] | parts_use[ikumiawase2] | parts_use[ikumiawase3] ) == 0x3F) {
//------------------------------------------------------------
// 全て異なる図形が使われている。
//------------------------------------------------------------
if( (zukei=findsame( parts_kumiawase[ikumiawase1], parts_num[ikumiawase1],
parts_kumiawase[ikumiawase2], parts_num[ikumiawase2],
parts_kumiawase[ikumiawase3], parts_num[ikumiawase3])) ) {
//----------------------------------------------------------
// 同じ図形が見つかった。回転やShiftで数多く見つかるはずなので，最初の一つだけを表示する。
//----------------------------------------------------------
if( zukeifind.find(zukei) == zukeifind.end()) {
dump( ikumiawase1, ikumiawase2, ikumiawase3, zukei);
zukeifind.insert( zukei);
}
}
}
}
}
}
答えは２件出力されました(１件じゃないのね)。(2006.2.11)図形を重ねてはならないようなので新聞での解答は1件。
久々にVisioを使って絵を描く問題が出た気がする。
以前MOに書き込んだとき，ハードディスクとMOの書き込みデータが違っていてひどい目に遭ったことがある。
それ以来リムーバルメディアに書き込むときは必ず書き込んだデータをハードディスクのデータと比較することにしている。
それが面倒なのでリムーバブルメディアは余り使わないことにしている。
今回CD-Rの書き込みエラーは出ないが比較すると違っているという結果になり，もう随分古いCD-Rドライブだからと諦めて
新しいのを買ってきた。今のは殆どUSB接続。ドライバを入れる必要も無いし便利便利。
ところがこのドライブを使って書き込みをしたけど何回書いてもハードディスクのデータと
違ってしまう。毎回同じファイルが異なるわけでも無いし，書き込みソフトでエラーが出るわけでも無い。
次の日販売店に行って事情を説明した。私の使っているメディアがおかしい可能性もあるので，数枚メディアを貰ってきて
そこに書いてみた。それでもダメ。
もう一度行って新しい機械に代えて貰った。
しかーし，それでも同じ症状が出る。ぎょえー，ドライブの問題じゃないな，これは。
うーん，流石にもう一度行くことは出来ないよな。恥ずかしい。
それにしても書き込みエラーくらい出して欲しいものだ。
結局zipで圧縮し，サーバに置いてダウンロードして貰った。今度からそうしようかな。それにしても便利な世の中になったものだ。
そういえばここ２回ほど応募を忘れていた。
解速度
即