朝日新聞2006年12月22日パズル横丁解答

(2007.1.5)最初に作ったプログラムは「1,4」と「3,6」のパターンを見逃していた(出力中のの赤い「Find」の部分)。原因はソース中の赤い部分。恥ずかしい。

プログラムの実行結果は以下の通り。行頭にFindが付いているのが正解の黒白パターン。

     0  0 ......
     1  1 1.....
     1  2 .2....
Find 2  3 12....
     1  4 ..3...
Find 2  5 1.3...
Find 2  6 .23...
     3  7 123...
     1  8 ...4..
Find 2  9 1..4..
Find 2  a .2.4..
     3  b 12.4..
     2  c ..34..
     3  d 1.34..
     3  e .234..
Find 4  f 1234..
     1 10 ....5.
Find 2 11 1...5.
     2 12 .2..5.
     3 13 12..5.
Find 2 14 ..3.5.
     3 15 1.3.5.
     3 16 .23.5.
Find 4 17 123.5.
Find 2 18 ...45.
     3 19 1..45.
     3 1a .2.45.
Find 4 1b 12.45.
     3 1c ..345.
Find 4 1d 1.345.
     4 1e .2345.
     5 1f 12345.
     1 20 .....6
     2 21 1....6
Find 2 22 .2...6
     3 23 12...6
Find 2 24 ..3..6
     3 25 1.3..6
     3 26 .23..6
Find 4 27 123..6
Find 2 28 ...4.6
     3 29 1..4.6
     3 2a .2.4.6
Find 4 2b 12.4.6
     3 2c ..34.6
     4 2d 1.34.6
Find 4 2e .234.6
     5 2f 1234.6
Find 2 30 ....56
     3 31 1...56
     3 32 .2..56
     4 33 12..56
     3 34 ..3.56
Find 4 35 1.3.56
Find 4 36 .23.56
     5 37 123.56
     3 38 ...456
Find 4 39 1..456
Find 4 3a .2.456
     5 3b 12.456
Find 4 3c ..3456
     5 3d 1.3456
     5 3e .23456
     6 3f 123456

上から順に見ていくと以下のように「隣り合う2面が黒の場合と,それを白黒反転した場合」であることがわかる。

「向かい合う2面」の場合は駄目なので,答えには「隣り合う2面」と書かなければならない。

サイコロを振ったとき出る目のパターンとしては以下の3通り。

プログラムのソースは以下の通り。

#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;

int num[0x3F+1];                // 

int getbit( int val, int bitpos) // 1オリジンでビットを取り出す
{
  int b = 1 << (bitpos-1);      // 1オリジンなので-1してからシフトする
  if( val & b) return    1;     // ビットがONか調べる
  return    0;
}

int rotate3x3( int val)         // 3x3の矩形を左に90度回転する
{
  // 012   258
  // 345 ⇒ 147
  // 678   036
  int newval = 0;
  if( val&bit0) newval |= bit6;
  if( val&bit1) newval |= bit3;
  if( val&bit2) newval |= bit0;
  if( val&bit3) newval |= bit7;
  if( val&bit4) newval |= bit4;
  if( val&bit5) newval |= bit1;
  if( val&bit6) newval |= bit8;
  if( val&bit7) newval |= bit5;
  if( val&bit8) newval |= bit2;
  return    newval;
}

int min4( int v1, int v2, int v3, int v4) // 4つの数字の最小値を取得する
{
  return    min(min(v1,v2),min(v3,v4));
}

cstring bitstr( int val)        // 黒く塗った部分の数値,白い部分は.を出力する
{
  static char bits[10];
  if( val & bit0) bits[0] = '1'; else bits[0] = '.';
  if( val & bit1) bits[1] = '2'; else bits[1] = '.';
  if( val & bit2) bits[2] = '3'; else bits[2] = '.';
  if( val & bit3) bits[3] = '4'; else bits[3] = '.';
  if( val & bit4) bits[4] = '5'; else bits[4] = '.';
  if( val & bit5) bits[5] = '6'; else bits[5] = '.';
  bits[6] = NIL;
  return    bits;
  
}

void expand( int val, int face1, int face2, int face3, int face4, int face5) // 上から見た展開図で考える
{
  // face1が上面,それ以外は側面
  // それぞれの面の黒/白を取得する
  int b1 = getbit( val, face1); // 上面の黒白
  int b2 = getbit( val, face2); // 側面の黒白(展開図の上)
  int b3 = getbit( val, face3); // 側面の黒白(展開図の左)
  int b4 = getbit( val, face4); // 側面の黒白(展開図の下)
  int b5 = getbit( val, face5); // 側面の黒白(展開図の右)
  int pattern1 = (b1<<4) | (b2<<1) | (b3<<3) | (b4<<7) | (b5<<5); // これを3x3の矩形内に配置し9ビットの数と見なす
  int pattern2 = rotate3x3(pattern1); // 「正規化」のために回転して考える(90度)
  int pattern3 = rotate3x3(pattern2); // 「正規化」のために回転して考える(180度)
  int pattern4 = rotate3x3(pattern3); // 「正規化」のために回転して考える(270度)
  int pattern = min4( pattern1, pattern2, pattern3, pattern4);  // 回転して一番小さな数をこの展開図の値とする
  num[pattern]++;               // 展開図の値を記憶する
}

int main( int argc, cstring argv[])
{
  for( int i=0; i<= 0x3F; i++) {  // 6面全てに色を付けてみる
    for( int k=0; k<= 0x3F; k++) num[k] = 0; // 色付けし直す毎に前の記録を削除する
    // この色付けでサイコロを振る。1から6の出る確率は1/6で同じ。
    expand( i, 1,2,3,5,4); // 1が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    expand( i, 2,3,1,4,6); // 2が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    expand( i, 3,1,2,6,5); // 3が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    expand( i, 4,1,5,6,2); // 4が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    expand( i, 5,1,3,6,4); // 5が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    expand( i, 6,2,4,5,3); // 6が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
    // 正規化した値が3通り出現し同じ回数の場合,iが答えになる
    int num_value = 0;          // 出現した数
    int num_cnt = 0;            // 出現した回数
    YesNo ynFind = YES;         // 解が見つかった?
    for( k=0; k<= 0x3F; k++) {  // 正規化した数字を調べる
      if( num[k] != 0) {        // 正規化した数がある
        num_value++;            // 出現回数を勘定する
        if( num_cnt == 0) num_cnt = num[k]; // 出現した数
        else if( num_cnt != num[k]) { // 違う数が出現した,出現する確率が違うってこと
          ynFind = NO;
        }
      }
    }
    if( num_value != 3) {       // 出現した数字は3種類?
      ynFind = NO;              // 3種類でない場合ジャンケンには使えない
    }
    if( ynFind) {               
      ps( "Find %d %2x %s\n", bitcount(i), i, bitstr(i));
    }
    else {
      ps( "     %d %2x %s\n", bitcount(i), i, bitstr(i));
    }
  }
  return    0;
}