(2006.2.10)問題を思い切り勘違いしていたようだ。問題文には「「二つずつ３組に分け，裏返さずに二つを組合せて同じ図形を作りたいと思います」とある。私は重ね合わせた図形もOKと思ったけど新聞の解答欄を見る限りダメみたいだ。ボケッとしていたんだろうな。でももう一つは正解を表示しているからプログラム的には正解と見なしちゃおう。重ね合わせがダメな場合赤字で書いた修正(プログラムコード中に赤字で書いてある)をする必要がある。
プログラムの実行結果は以下の通り。
--------------------------------------------- □■■■ □■■■ ■■■□ □□■□ C と A の組合せ □ＣＣＣ □□ＣＣ □□□□ □□□□ □□□□ □Ａ□□ ＡＡＡ□ □□Ａ□ E と B の組合せ □ＥＥ□ □Ｅ□□ ＥＥ□□ □□□□ □□□Ｂ □□ＢＢ □□Ｂ□ □□Ｂ□ F と D の組合せ □ＦＦＦ □Ｆ□Ｆ □□□□ □□□□ □□□□ □□Ｄ□ ＤＤＤ□ □□Ｄ□ --------------------------------------------- ■■■□ ■■■■ □□■□ □□□□ F と A の組合せ Ｆ□Ｆ□ ＦＦＦ□ □□□□ □□□□ □Ａ□□ □ＡＡＡ □□Ａ□ □□□□ D と B の組合せ □□Ｄ□ ＤＤＤ□ □□Ｄ□ □□□□ ＢＢＢ□ □□ＢＢ □□□□ □□□□ E と C の組合せ Ｅ□□□ ＥＥＥ□ □□Ｅ□ □□□□ □ＣＣ□ □ＣＣＣ □□□□ □□□□
の組合せと
の組合せの２通り。
プログラムのソースは以下の通り。ちょっと長いけど本質部分はそれほどでも無い。
#include "puzutl.h"
const ulong bit0 = 0x00000001;
const ulong bit1 = 0x00000002;
const ulong bit2 = 0x00000004;
const ulong bit3 = 0x00000008;
const ulong bit4 = 0x00000010;
const ulong bit5 = 0x00000020;
const ulong bit6 = 0x00000040;
const ulong bit7 = 0x00000080;
const ulong bit8 = 0x00000100;
const ulong bit9 = 0x00000200;
const ulong bit10 = 0x00000400;
const ulong bit11 = 0x00000800;
const ulong bit12 = 0x00001000;
const ulong bit13 = 0x00002000;
const ulong bit14 = 0x00004000;
const ulong bit15 = 0x00008000;
const ulong bit16 = 0x00010000;
const ulong bit17 = 0x00020000;
const ulong bit18 = 0x00040000;
const ulong bit19 = 0x00080000;
const ulong bit20 = 0x00100000;
const ulong bit21 = 0x00200000;
const ulong bit22 = 0x00400000;
const ulong bit23 = 0x00800000;
const ulong bit24 = 0x01000000;
const ulong bit25 = 0x02000000;
const ulong bit26 = 0x04000000;
const ulong bit27 = 0x08000000;
const ulong bit28 = 0x10000000;
const ulong bit29 = 0x20000000;
const ulong bit30 = 0x40000000;
const ulong bit31 = 0x80000000;
int4 rotate90( int4 d) // 回転
{
int4 newd = 0;
if( d&bit3 ) newd |= bit0;
if( d&bit7 ) newd |= bit1;
if( d&bit11) newd |= bit2;
if( d&bit15) newd |= bit3;
if( d&bit2 ) newd |= bit4;
if( d&bit6 ) newd |= bit5;
if( d&bit10) newd |= bit6;
if( d&bit14) newd |= bit7;
if( d&bit1 ) newd |= bit8;
if( d&bit5 ) newd |= bit9;
if( d&bit9 ) newd |= bit10;
if( d&bit13) newd |= bit11;
if( d&bit0 ) newd |= bit12;
if( d&bit4 ) newd |= bit13;
if( d&bit8 ) newd |= bit14;
if( d&bit12) newd |= bit15;
return newd;
}
int shiftRight( int4 d) // 右シフト
{
int4 newd = 0;
if( d&bit0 ) newd |= bit1;
if( d&bit1 ) newd |= bit2;
if( d&bit2 ) newd |= bit3;
if( d&bit4 ) newd |= bit5;
if( d&bit5 ) newd |= bit6;
if( d&bit6 ) newd |= bit7;
if( d&bit8 ) newd |= bit9;
if( d&bit9 ) newd |= bit10;
if( d&bit10) newd |= bit11;
if( d&bit12) newd |= bit13;
if( d&bit13) newd |= bit14;
if( d&bit14) newd |= bit15;
if( d&bit3 ) newd |= bit16;
if( d&bit7 ) newd |= bit17;
if( d&bit11) newd |= bit18;
if( d&bit15) newd |= bit19;
return newd;
}
int shiftDown( int4 d) // 下シフト
{
int4 newd = 0;
if( d&bit0 ) newd |= bit4;
if( d&bit1 ) newd |= bit5;
if( d&bit2 ) newd |= bit6;
if( d&bit3 ) newd |= bit7;
if( d&bit4 ) newd |= bit8;
if( d&bit5 ) newd |= bit9;
if( d&bit6 ) newd |= bit10;
if( d&bit7 ) newd |= bit11;
if( d&bit8 ) newd |= bit12;
if( d&bit9 ) newd |= bit13;
if( d&bit10) newd |= bit14;
if( d&bit11) newd |= bit15;
if( d&bit12) newd |= bit20;
if( d&bit13) newd |= bit21;
if( d&bit14) newd |= bit22;
if( d&bit15) newd |= bit23;
return newd;
}
int shiftUp( int4 d) // 上シフト
{
int4 newd = 0;
if( d&bit4 ) newd |= bit0;
if( d&bit5 ) newd |= bit1;
if( d&bit6 ) newd |= bit2;
if( d&bit7 ) newd |= bit3;
if( d&bit8 ) newd |= bit4;
if( d&bit9 ) newd |= bit5;
if( d&bit10) newd |= bit6;
if( d&bit11) newd |= bit7;
if( d&bit12) newd |= bit8;
if( d&bit13) newd |= bit9;
if( d&bit14) newd |= bit10;
if( d&bit15) newd |= bit11;
return newd;
}
int shiftLeft( int4 d) // 左シフト
{
int4 newd = 0;
if( d&bit1 ) newd |= bit0;
if( d&bit2 ) newd |= bit1;
if( d&bit3 ) newd |= bit2;
if( d&bit5 ) newd |= bit4;
if( d&bit6 ) newd |= bit5;
if( d&bit7 ) newd |= bit6;
if( d&bit9 ) newd |= bit8;
if( d&bit10) newd |= bit9;
if( d&bit11) newd |= bit10;
if( d&bit13) newd |= bit12;
if( d&bit14) newd |= bit13;
if( d&bit15) newd |= bit14;
return newd;
}
int4 normalize( int4 d) {
if( !d) return d;
while( ( d & 0x0F) == 0) {
d = shiftUp(d);
}
while( ( d & 0x1111) == 0) {
d = shiftLeft(d);
}
return d;
}
int4 translate_parts( int4 d, int rotate, int shiftR, int shiftD)
{
for( int i=0; i< rotate; i++) {
d = rotate90(d);
}
d = normalize(d); // 枠の左上に移動する
for( i=0; i< shiftR; i++) {
d = shiftRight(d);
if( d & 0xFFFF0000) return 0; // 枠をはみ出たのは対象外
}
for( i=0; i< shiftD; i++) {
d = shiftDown(d);
if( d & 0xFFFF0000) return 0;
}
return d;
}
int cmpint4( const void* a, const void* b) { int4 ia = *(int4*)a, ib = *(int4*)b; return ia-ib;}
int dupout( int4* d, int num)
{
//--------------------------------------------------------------------
// ソートして重複を除去する。
//--------------------------------------------------------------------
qsort( d, num, sizeof(int), cmpint4);
int n = 0;
for( int i=1; i< num; i++) {
if( d[i] != d[n]) { d[++n] = d[i];}
}
return n;
}
int4 findsame( int4* d1, int numd1, int4* d2, int numd2, int4* d3, int numd3)
{
//--------------------------------------------------------------------
// ソートされている数字の中から同じ図形の組合せを見つける。
//--------------------------------------------------------------------
int dfind = -1;
int idx1 = 0, idx2 = 0, idx3 = 0;
while( idx1 < numd1 && d1[idx1] == 0) idx1++;
while( idx2 < numd2 && d2[idx2] == 0) idx2++;
while( idx3 < numd3 && d3[idx3] == 0) idx3++;
while( idx1 < numd1 && idx2 < numd2 && idx3 < numd3) {
//------------------------------------------------------------------
// まだ数字は残っている。
//------------------------------------------------------------------
if( d1[idx1] == d2[idx2] &&
d2[idx2] == d3[idx3]) return d1[idx1]; // 同じ数字の組合せが見つかった。
//------------------------------------------------------------------
// ３つの数字は同じ数字では無い。
// 小さな数字を除外する。
//------------------------------------------------------------------
if ( d1[idx1] < d2[idx2]) idx1++;
else if( d1[idx1] < d3[idx3]) idx1++;
else if( d2[idx2] < d1[idx1]) idx2++;
else if( d2[idx2] < d3[idx3]) idx2++;
else if( d3[idx3] < d1[idx1]) idx3++;
else if( d3[idx3] < d2[idx2]) idx3++;
else pe( "Error\n");
}
return 0;
}
// ０１２３
// ４５６７
// ８９1011
// 12131415
int4 partsA = bit1 | bit2 | bit4 | bit5 | bit9; // 図形
int4 partsB = bit1 | bit5 | bit8 | bit9 | bit12;
int4 partsC = bit0 | bit1 | bit4 | bit5 | bit6;
int4 partsD = bit0 | bit1 | bit2 | bit5 | bit9;
int4 partsE = bit1 | bit2 | bit5 | bit8 | bit9;
int4 partsF = bit0 | bit2 | bit4 | bit5 | bit6;
int parts[] = { partsA, partsB, partsC, partsD, partsE, partsF}; // 図形一覧
int partsuse[] = { 1, 2, 4, 8, 16, 32};
void dumpzukei( int iparts, int4 zukei)
{
cstring pc = "ＡＢＣＤＥＦ■"+iparts*2;
int b = 1;
for( int i=0; i< 16; i++) {
if( zukei & b) {
ps( "%.2s", pc);
}
else {
ps( "□");
}
if( ((i+1)%4) == 0) ps( "\n");
b <<= 1;
}
ps( "\n");
}
void dumpzukei( int iparts, int rotate, int shiftR, int shiftD)
{
int4 p = parts[iparts], parts_oped;
parts_oped = translate_parts( p, rotate, shiftR, shiftD);
dumpzukei( iparts, parts_oped);
}
void dump( int iparts1, int iparts2, int4 zukei)
{
int4 parts1 = parts[iparts1], parts1_oped;
int4 parts2 = parts[iparts2], parts2_oped;
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;
if( ( parts1_oped | parts2_oped) == zukei) {
dumpzukei( iparts1, rotate1, shift1R, shift1D);
dumpzukei( iparts2, rotate2, shift2R, shift2D);
return;
}
}
}
}
}
}
}
}
void dumpparts( int kumiawase, int4 zukei)
{
int parts1 = kumiawase % 6;
int parts2 = (kumiawase / 6) % 6;
cstring partsname = "ABCDEFX";
ps( "%c と %c の組合せ\n", partsname[parts1], partsname[parts2]);
dump( parts1, parts2, zukei);
}
void dump( int kumiawase1, int kumiawase2, int kumiawase3, int4 zukei)
{
int parts1, parts2, parts3, parts4, parts5, parts6;
ps( "---------------------------------------------\n");
dumpzukei( 6, zukei);
dumpparts( kumiawase1, zukei);
dumpparts( kumiawase2, zukei);
dumpparts( kumiawase3, zukei);
}
int main( int argc, cstring argv[])
{
int cnt = 0;
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;
if( parts1_oped & parts2_oped) continue; // (2006.2.10)新聞解答欄では重ね合わせがダメだということなので
//----------------------------------------------------
// この組合せでどんな図形が出来るか?
//----------------------------------------------------
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);
}
}
}
}
}
}
return 0;
}