朝日新聞2005年4月8日パズル横丁解答

プログラムの出力結果は以下の通り。

A : 正直者
B : 嘘つき
C : 正直者
D : 嘘つき
E : 正直者

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

#include "puzutl.h"

const int LEFT  = 1;
const int RIGHT = 2;
const int NONE  = 4;

int direction0[5] = { RIGHT/*A*/, LEFT/*B*/, LEFT/*C*/, NONE/*D*/, LEFT/*E*/}; // 問題文にあるA〜Eの向き

int getdirection( int sts, int pos) // 向きの可能性を求める,複数の向きのORになる
{
  int numLeft = 0, numRight = 0; // posの位置にいる人から見た左右の嘘つきの人数
  int dir = 0;                  // posの位置にいる人の向きの可能性(戻り値)
  for( int i=0; i< pos; i++) {
    if( sts & 1) numLeft++;
    sts >>= 1;
  }
  int lie = sts&1;              // posの位置にいる人は嘘つき?
  sts >>= 1;
  for( i=pos+1; i< 5; i++) {
    if( sts & 1) numRight++;
    sts >>= 1;
  }
#if 1
  if( lie) {
    // 嘘つき,嘘つきの場合全ての向きの可能性から正直に答える可能性を除去する
    dir = LEFT|RIGHT|NONE;
    if( numLeft ) dir &= ~LEFT; // 左に嘘つきがいれば左を向かない
    if( numRight) dir &= ~RIGHT;  // 右に嘘つきがいれば右を向かない
    if( numLeft == 0 && numRight == 0) dir &= ~NONE; // 左右に嘘つきがいなければ正面を向かない
  }
  else {
    // 正直者,正直者の行動は単純明快。
    if( numLeft ) dir |= LEFT;  // 左に嘘つきがいれば左を向く可能性あり
    if( numRight) dir |= RIGHT; // 右に嘘つきがいれば右を向く可能性あり
    if( !dir)     dir =  NONE;  // 左右どちらにも嘘つきがいなければ正面を向く
  }
#else
  // 私は上のようにプログラムしたけど，以下のようにプログラムしても結果は同じ。結果は同じになるが，論理に自信がない。
  // 正直者の行動を求める。
  if( numLeft ) dir |= LEFT;    // 左に嘘つきがいれば左を向く可能性あり
  if( numRight) dir |= RIGHT;   // 右に嘘つきがいれば右を向く可能性あり
  if( !dir)     dir =  NONE;    // 左右どちらにも嘘つきがいなければ正面を向く
  if( lie) dir = ~dir;          // 嘘つきの行動は正直者とは反対になる。
#endif
  return    dir;
}

YesNo check( int sts) 
{
  // Bitが1:嘘つき,0:正直
  int direction[5];             // 5人の向き
  for( int k=0; k< 5; k++) { // 5人
    direction[k] = getdirection( sts, k);
  }
  for( k=0; k< 5; k++) {
    if( !(direction[k] & direction0[k])) return NO;
  }
  return    YES;
}
  
void dump( int sts) 
{
  for( int i=0; i< 5; i++) {
    ps( "%c : ", "ABCDE"[i]);
    if( sts&1) ps( "嘘つき"); else ps( "正直者");
    ps( "\n");
    sts >>= 1;
  }
}

int main( int argc, cstring argv[])
{
  // 高々32通りしか場合が存在しない。
  // それでも☆２つということは頭で考えるにはちょっと難しいということか。
  for( int sts=0; sts< 32; sts++) {
    if( check( sts)) dump(sts);
  }
  return    0;
}